CSCI 1952Q: Algorithmic Aspects of Machine Learning (Spring 2024)

Basic Information

Lectures: Tue-Thu 1:00-2:20 pm in CIT 241.
Instructor: Yu Cheng.

Email: yu_cheng@brown.edu
Office Hours: Tuesday 2:30-3:30 pm in CIT 413, or by appointment.

TAs:

Jay Sarva (Head TA). Office Hours: Thursday, 6:00 – 8:00pm in CIT 102.
Suraj Anand. Office Hours: Wednesday, 8:00 – 10:00am in CIT 102.
Nishka Pant. Office Hours: Friday, 10:00am - 12:00pm in CIT 102.
Sagar Raichandani. Office Hours: Wednesday, 3:00 – 5:00pm in CIT 203.
Zhengyu Zou. Office Hours: Monday, 3:00 – 5:00pm in CIT 102.

hours.cs.brown.edu

Textbook:
- [LRU] Mining of Massive Datasets (Third Edition). Jure Leskovec, Anand Rajaraman, Jeff Ullman.
- [M] Algorithmic Aspects of Machine Learning. Ankur Moitra.
- [A] Theory of Deep Learning (book draft). Sanjeev Arora et al.

Course Description

In this course, we will explore the theoretical foundations of machine learning and deep learning, with a focus on the design and analysis of learning algorithms with provable guarantees. Throughout the course, we will (1) investigate why simple algorithms can solve machine learning problems that are computationally hard in the worst case, (2) discuss data mining and machine learning algorithms for analyzing very large amounts of data, and (3) understand the success of deep learning by studying the emerging theory of deep learning. Example topics include non-convex optimization, non-negative matrix factorization, locality-sensitive hashing, streaming algorithms, local graph algorithms, and over-parameterization and implicit bias in deep learning. Prior knowledge of linear algebra, algorithms and data structures, probability, and statistics is recommended.

Top Projects and Reviewers

The course uses a peer-review process to evaluate all final project submissions. Based on this peer-review process, the following projects/students are chosen as top projects/reviewers:

Top Projects:
- Chia-Hong Hsu. Consistency Training Inverse: An Alignment Learning Approach for Representation Learning.
- Naveen Sharma. Query by Humming via Locality Sensitive Hashing.
- Asher Labovich, Fate Bussey. Time-Based Bayesian Optimization for High-Cost Evaluation.
Top Reviewers (excluding instructor and TAs):
- Michael Fu.
- Boran Wang.
List of all reviewers. The following students and TAs participated in the peer-review process: Michael Fu, Chia-Hong Hsu, Rohit Mohnani, Nishka Pant, Sagar Raichandani, Jay Sarva, Boran Wang, Peter Zhu, Zhengyu Zou, Kai Zuang. Thank you for your time and effort in reviewing the final projects of CSCI 1952Q!

Assignments

Warning: the following assignments and due dates are from the past. If you are taking CSCI 1952Q this semester, please refer to the current course webpage.

Written 1, due at 1:00pm on Feb 16 (Fri).
Coding 1, due at 1:00pm on Feb 23 (Fri).
Written 2, due at 1:00pm on Mar 1 (Fri).
Coding 2, due at 1:00pm on Mar 8 (Fri).
Written 3, due at 1:00pm on Mar 15 (Fri).
Written 4, due at 1:00pm on Apr 12 (Fri).
Coding 3, due at 1:00pm on May 3 (Fri).

Course Project

Project guidelines.
Important dates:

Mar 4: Decide on teams and topics.
Apr 18 - Apr 25: Presentations.
May 13: Project report due.

Schedule

Week 1 (Jan 22): Introduction.
- Introduction to the Course (Lecture 1).
Week 2 (Jan 29): Non-Convex Optimization I (Chapter 7 of [A], Chapter 9 of [LRU], Chapter 8 of [M]).
- Non-Convex Matrix Factorization (Lecture 2).
- Non-Convex Matrix Completion (Lecture 3).
- [1] R. Ge, C. Jin, Y. Zheng. No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis. ICML 2017.
Week 3 (Feb 5): Non-Convex Optimization II (Chapter 7 of [A], Chapter 9 of [LRU], Chapter 8 of [M]).
- Tractable Non-Convex Problems (Lecture 4).
- Singular Value Decomposition (Lecture 5).
- [2] Y. Zhang, Q. Qu, J. Wright. From Symmetry to Geometry: Tractable Nonconvex Problems. 2020.
Week 4 (Feb 12): Nonnegative Matrix Factorization I (Chapter 1 of [M], Chapter 11 of [LRU]).
- Nonnegative Matrix Factorization (Lecture 6).
- Algorithms for Separable NMF (Lecture 7).
- [3] S. Arora, R. Ge, R. Kannan, A. Moitra. Computing a Nonnegative Matrix Factorization -- Provably. STOC 2012.
Week 5 (Feb 19): Nonnegative Matrix Factorization II (Chapter 1 of [M], Chapter 11 of [LRU]).
- NMF and Topic Modeling (Lecture 8).
- [4] S. Arora, R. Ge, A. Moitra. Learning Topic Models -- Going Beyond SVD. FOCS 2012.
Week 6 (Feb 26): Finding Similar Items I (Chapter 3 of [LRU]).
- Set Similarity and MinHash (Lecture 9).
- Locality Sensitive Hashing (Lecture 10).
- [5] A. Z. Broder. On the Resemblance and Containment of Documents. SEQUENCES 1997.
Week 7 (Mar 4): Finding Similar Items II (Chapter 3 of [LRU]).
- Locality-Sensitive Functions and Amplification (Lecture 11).
- Sampling Data in a Stream, Bloom Filter (Lecture 12).
- [6] P. Indyk and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998.
Week 8 (Mar 11): Algorithms for Data Streams (Chapter 4 of [LRU]).
- Counting Distinct Elements in a Stream (Lecture 13).
- PageRank and Computation of PageRank (Lecture 14).
- [7] P. Flajolet, G. N. Martin. Probabilistic Counting Algorithms for Data Base Applications. JCSS 1985.
Week 9 (Mar 18): Network Analysis (Chapters 5 and 10 of [LRU]).
- Personalized PageRank, Graph Partitioning (Lecture 15).
- Ask Me Anything (Lecture 16).
- [8] L. Page, S. Brin, R. Motwani, T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. 1999.
Week 10 (Mar 25): No classes. Spring Recess.
Week 11 (Apr 1): Theory of Deep Learning I (Chapters 9 and 10 of [A]).
- Spectral Clustering, Local Graph Algorithms (Lecture 17).
- Implicit Bias of Gradient Descent (Lecture 18).
- [9] D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, N. Srebro. The Implicit Bias of Gradient Descent on Separable Data. ICLR 2018.
Week 12 (Apr 8): Theory of Deep Learning II (Chapters 9 and 10 of [A]).
- Neural Tangent Kernels (Lecture 19).
- Self-Supervised Learning (Lecture 20).
- [10] S. Arora, S. S. Du, W. Hu, Z. Li, R. Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019.
- [11] C. Tosh, A. Krishnamurthy, D. Hsu. Contrastive Estimation Reveals Topic Posterior Information to Linear Models. JMLR 2021.
Week 13-14 (Apr 15): Project Presentations.
- Transformers Learn In-Context (Lecture 21).
- Project Presentations.
- [12] J. V. Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, M. Vladymyrov. Transformers Learn In-Context by Gradient Descent. ICML 2023.
Additional Readings (optional):
- Non-Convex Optimization:
  - R. Ge, J. D. Lee, T. Ma. Matrix Completion has No Spurious Local Minimum. NIPS 2016.
  - J. Sun, Q. Qu, J. Wright. Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture. IEEE Trans. Inf. Theory. 2017.
  - R. Ge, T. Ma. On the Optimization Landscape of Tensor Decompositions. NIPS 2017.
  - C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, M. I. Jordan. How to Escape Saddle Points Efficiently. ICML 2017.
  - S. Bubeck. Convex Optimization: Algorithms and Complexity (monograph). Found. Trends Mach. Learn. 2015.
- Nonnegative Matrix Factorization:
  - S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag, Y. Wu, M. Zhu. A Practical Algorithm for Topic Modeling with Provable Guarantees. ICML 2013.
  - S. A. Vavasis. On the Complexity of Nonnegative Matrix Factorization. SIOPT 2009.
  - D. D. Lee, H. S. Seung. Learning the Parts of Objects by Nonnegative Matrix Factorization. Nature 1999.
  - D. D. Lee, H. S. Seung. Algorithms for Non-negative Matrix Factorization. NIPS 2000.
  - N. Gillis. Nonnegative Matrix Factorization (book). 2020.
- Locality-Sensitive Hashing:
  - A. Gionis, P. Indyk, R. Motwani. Similarity Search in High Dimensions via Hashing. VLDB 1999.
  - A. Z. Broder, M. Charikar, A. M. Frieze, M. Mitzenmacher. Min-Wise Independent Permutations. STOC 1998.
  - M. Datar, N. Immorlica, P. Indyk, V. S. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. SCG 2004.
  - R. O'Donnell, Y. Wu, Y. Zhou. Optimal Lower Bounds for Locality Sensitive Hashing (Except When q Is Tiny). ICS 2011.
  - A. Andoni, I. Razenshteyn. Optimal Data-Dependent Hashing for Approximate Near Neighbors. STOC 2015.
- Streaming Algorithms:
  - B. H. Bloom. Space/Time Trade-Offs in Hash Coding With Allowable Errors. Commun. ACM. 1970.
  - J. S. Vitter. Random Sampling With a Reservoir. TOMS 1985.
  - N. Alon, Y. Matias, M. Szegedy. The Space Complexity of Approximating the Frequency Moments. STOC 1996.
  - P. Gopalan, T. S. Jayram, R. Krauthgamer, R. Kumar. Estimating the Sortedness of a Data Stream. SODA 2007.
  - E. Kushilevitz, N. Nisan. Communication Complexity (book). 1996.
- Network Analysis:
  - S. Brin, L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Comput. Networks. 1998.
  - R. Andersen, F. Chung, K. Lang. Local Graph Partitioning using PageRank Vectors. FOCS 2006.
  - J. Shi and J. Malik. Normalized Cuts and Image Segmentation. CVPR 1997.
  - D. A. Spielman. Spectral and Algebraic Graph Theory (book draft). 2019.
  - S.-H. Teng. Scalable Algorithms for Data and Network Analysis (book). 2016.
- Theoretical Deep Learning:
  - S. S. Du, X. Zhai, B. Póczos, A. Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. ICLR 2019.
  - Z. Allen-Zhu, Y. Li, Z. Song. A Convergence Theory for Deep Learning via Over-Parameterization. ICML 2019.
  - C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals. Understanding Deep Learning (Still) Requires Rethinking Generalization. Commun. ACM. 2021.
  - J. D. Lee, Q. Lei, N. Saunshi, J. Zhuo. Predicting What You Already Know Helps: Provable Self-Supervised Learning. NeurIPS 2021.
  - M. Chidambaram, C. Wu, Y. Cheng, R. Ge. Hiding Data Helps: On the Benefits of Masking for Sparse Coding. ICML 2023.
  - A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin. Attention Is All You Need. NIPS 2017.
  - M. Belkin, D. Hsu, S. Ma, S. Mandal. Reconciling Modern Machine Learning and the Bias-Variance Trade-off. PNAS 2019.

Grading

Homework assignments (54%): The course includes 4 written assignments and 4 coding assignments. Students are encouraged to discuss with others, but each student must write up their solutions independently and acknowledge who they worked with.
Course project (46%): Students will form groups to work on research projects or explore in depth a topic that we did not cover in class. Each group will do a project presentation and write a project report.
Bonus points (21%): There are extra-credit questions in all assignments. There are bonus points for top final projects and reviewers.

Disability Policies

Brown University is committed to full inclusion of all students. Any student with a documented disability is welcome to contact the instructor as early in the semester as possible so that reasonable accommodations can be arranged. If you need accommodations around online learning or in-classroom accommodations, please be sure to reach out to Student Accessibility Services (SAS) for their assistance (sas@brown.edu, 401-863-9588, Brown SAS Website). Students may also speak with Student Accessibility Services at 401-863-9588 to discuss the process for requesting accommodations.

Religious Holidays

Students who wish to observe their religious holidays shall inform the instructor within the first four weeks of the semester, unless the religious holiday is observed in the first four weeks. In such cases, the students shall notify the faculty member at least five days in advance of the date when he/she will be absent. The instructor shall make every reasonable effort to honor the request.