CSCI 2952Q: Robust Algorithms for Machine Learning (Fall 2024)

Basic Information

• Lectures: Monday 3:00-5:30pm in CIT 477.
• Instructor: Yu Cheng.
  • Email: yu_cheng@brown.edu
  • Office Hours: Monday 5:30pm (until all questions are answered) in CIT 477 or CIT 413.

Course Description

As machine learning systems start to make more important decisions in our society, we need learning algorithms that are reliable and robust. In this course, we will (1) cover basic tools in linear algebra, matrix calculus, and statistics that are useful in theoretical machine learning, (2) explore different adversarial models and examine whether existing algorithms are robust in these models, and (3) design and analyze provably robust algorithms for fundamental tasks in machine learning. In particular, we will focus on the research areas of high-dimensional robust statistics, non-convex optimization, learning with strategic agents, and spectral graph theory. This is a research-oriented course where students will be asked to read and present sophisticated papers in top machine learning and theoretical computer science conferences. Knowledge of basic linear algebra, algorithms and data structures, and probability and statistics is essential. Prior experience with machine learning is useful but not required.

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:
  • Praccho Muna-McQuay, Mindy Kim. Robustness through Forgetting: Unlearning Adversarial Contexts in Transformers.
  • Heon Lee, George Chemmala, Arjan Chakravarthy. Robust Estimation for the Erdős-Rényi Model.
  • Kyle Lee, Yuechuan Yang. Gravitational Waves Inference.
  • Lukas Jarasunas, Hrithik Nambiar. Robust Online Portfolio Optimisation.
• Top Reviewers:
  • George Chemmala.
  • Kyle Lee.
  • Arjan Chakravarthy.
  • Colin Baker.
• List of all reviewers. The following students participated in the peer-review process: Colin Baker, Arjan Chakravarthy, George Chemmala, Jiaying Cheng, Leyang Hu, Bitao Jin, Preetish Juneja, Mindy Kim, Kyle Lee, Heon Lee, Morgan Lo, David Lubawski, Yuyang Luo, Shangyang Min, Praccho Muna-McQuay, Yuechuan Yang. Thank you for your time and effort in reviewing the final projects of CSCI 2952Q!

Important Dates

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


• Paper-reading presentation (paper-reading presentation guidelines).
  • Sep 30: Decide which paper to present.
  • Oct 21: Submit your presentation video.
• Final project (project guidelines).
  • Oct 7: Decide on teams and project titles.
  • Oct 14: Confirm presentation dates.
  • Nov 18 - Dec 2: Present your project in class.
  • Dec 16: Submit your project report.

Schedule

• Week 1 (Sep 2): No classes. Labor Day.
• Week 2 (Sep 9): Robust Non-Convex Optimization I (Lecture 1, Lecture 1 Slides).
  • Introduction to the Course.
  • Non-Convex Matrix Factorization.
  • [1] R. Ge, C. Jin, Y. Zheng. No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis. ICML 2017.
• Week 3 (Sep 16): Robust Non-Convex Optimization II (Lecture 2).
  • Non-Convex Matrix Completion.
  • Semi-Random Non-Convex Matrix Completion.
  • [2] Y. Cheng, R. Ge. Non-Convex Matrix Completion Against a Semi-Random Adversary. COLT 2018.
• Week 4 (Sep 23): Robust Non-Convex Optimization III (Lecture 3).
  • Tractable Non-Convex Problems.
  • Semi-Random Non-Convex Matrix Sensing.
  • [3] X. Gao, Y. Cheng. Robust Matrix Sensing in the Semi-Random Model. NeurIPS 2023.
• Week 5 (Sep 30): High-Dimensional Robust Statistics I (Lecture 4).
  • Introduction to Robust Statistics.
  • Robust Mean Estimation.
  • [4] Y. Cheng, I. Diakonikolas, R. Ge, M. Soltanolkotabi. High-dimensional Robust Mean Estimation via Gradient Descent. ICML 2020.
• Week 6 (Oct 7): No classes. Columbus Day.
• Week 7 (Oct 14): High-Dimensional Robust Statistics II (Lecture 5).
  • Robust Mean Estimation via Gradient Descent.
  • Robust Mean Estimation in Nearly-Linear Time.
  • [5] Y. Cheng, I. Diakonikolas, R. Ge. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. SODA 2019.
• Week 8 (Oct 21): High-Dimensional Robust Statistics III (Lecture 6).
  • Beyond Robust Mean Estimation.
  • Robust Stochastic Optimization.
  • [6] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, A. Stewart. SEVER: A Robust Meta-Algorithm for Stochastic Optimization. ICML 2019.
• Week 9 (Oct 28): Ask Me Anything (Lecture 7).
• Week 10 (Nov 4): Spectral Graph Theory I (Lecture 8).
  • Graph Sparsification by Effective Resistances.
  • Linear-Sized Graph Sparsifiers.
  • [7] Y. Lee, H. Sun. An SDP-Based Algorithm for Linear-Sized Spectral Sparsification. STOC 2017.
• Week 11 (Nov 11): Spectral Graph Theory II (Lecture 9).
  • Multiplicative Weight Update.
  • Faster and Simpler Solvers for Positive SDPs.
  • [8] R. Peng, K. Tangwongsan, P. Zhang. Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming. SPAA 2012.
• Week 12-14 (Nov 18): Project Presentations.
• Week 15 (Dec 9): Learning with Strategic Agents I (Lecture 10, Lecture 10 Slides).
  • Information Structure Design.
  • Strategic Classification.
  • Planning with Participation Constraints.
  • [9] H. Zhang, Y. Cheng, V. Conitzer. Efficient Algorithms for Planning with Participation Constraints. EC 2022.
• Additional Readings:
  • Robust Non-Convex Optimization (Lectures 1-3):
    • S. Bubeck. Convex Optimization: Algorithms and Complexity. Found. Trends Mach. Learn. 2015.
    • C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, M. I. Jordan. How to Escape Saddle Points Efficiently. ICML 2017.
    • Y. Zhang, Q. Qu, J. Wright. From Symmetry to Geometry: Tractable Nonconvex Problems. 2020.
    • J. Sun, Q. Qu, J. Wright. Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture. IEEE Trans. Inf. Theory. 2017.
    • J. Sun, Q. Qu, J. Wright. A Geometric Analysis of Phase Retrieval. ISIT 2016.
    • R. Ge, J. D. Lee, T. Ma. Matrix Completion has No Spurious Local Minimum. NIPS 2016.
    • R. Ge, T. Ma. On the Optimization Landscape of Tensor Decompositions. NIPS 2017.
    • X. Zhang, L. Wang, Y. Yu, Q. Gu. A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery. ICML 2018.
    • J. A. Kelner, J. Li, A. Liu, A. Sidford, K. Tian. Matrix Completion in Almost-Verification Time. FOCS 2023.
    • C. Jin, L. T. Liu, R. Ge, M. I. Jordan. On the Local Minima of the Empirical Risk. NeurIPS 2018.
    • J. A. Kelner, J. Li, A. Liu, A. Sidford, K. Tian. Semi-Random Sparse Recovery in Nearly-Linear Time. COLT 2023.
  • High-Dimensional Robust Statistics (Lectures 4-6):
    • I. Diakonikolas, D. M. Kane. Algorithmic High-Dimensional Robust Statistics. 2022.
    • I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, A. Stewart. Robust Estimators in High Dimensions without the Computational Intractability. FOCS 2016.
    • K. A. Lai, A. B. Rao, S. S. Vempala. Agnostic Estimation of Mean and Covariance. FOCS 2016.
    • I. Diakonikolas, D. M. Kane, A. Stewart. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. FOCS 2017.
    • S. Balakrishnan, S. S. Du, J. Li, A. Singh. Computationally Efficient Robust Sparse Estimation in High Dimensions. COLT 2017.
    • S. B. Hopkins, J. Li, F. Zhang. Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. NeurIPS 2020.
    • Y. Cheng, I. Diakonikolas, R. Ge, D. P. Woodruff. Faster Algorithms for High-Dimensional Robust Covariance Estimation. COLT 2019.
    • Y. Cherapanamjeri, E. Aras, N. Tripuraneni, M. I. Jordan, N. Flammarion, P. L. Bartlett. Optimal Robust Linear Regression in Nearly Linear Time. 2020.
    • I. Diakonikolas, D. Kane, D. Kongsgaard, J. Li, K. Tian. List-Decodable Mean Estimation in Nearly-PCA Time. NeurIPS 2021.
    • Y. Cheng, H. Lin. Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time. ICLR 2021.
    • Y. Cheng, I. Diakonikolas, D. M. Kane, R. Ge, S. Gupta, M. Soltanolkotabi. Outlier-Robust Sparse Estimation via Non-Convex Optimization. NeurIPS 2022.
    • S. Li, Y. Cheng, I. Diakonikolas, J. Diakonikolas, R. Ge, S. Wright. Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing. NeurIPS 2023.
    • I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, A. Stewart. Being Robust (in High Dimensions) Can Be Practical. ICML 2017.
    • B. Tran, J. Li, A. Madry. Spectral Signatures in Backdoor Attacks. NeurIPS 2018.
  • Spectral Graph Theory (Lectures 7-8):
    • N. K. Vishnoi. Lx = b Laplacian Solvers and Their Algorithmic Applications. 2012.
    • D. Spielman. Spectral and Algebraic Graph Theory. 2019.
    • S. Teng. Scalable Algorithms for Data and Network Analysis. 2019.
    • S. Arora, E. Hazan, S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory Comput. 2012.
    • D. A. Spielman, S. Teng. Spectral Sparsification of Graphs. SIAM J. Comput. 2011.
    • D. A. Spielman, N. Srivastava. Graph Sparsification by Effective Resistances. STOC 2008.
    • J. D. Batson, D. A. Spielman, N. Srivastava. Twice-Ramanujan Sparsifiers. STOC 2009.
    • Z. Allen-Zhu, Y. Lee, L. Orecchia. Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. SODA 2016.
  • Learning with Strategic Agents (Lecture 9):
    • S. Dughmi. Algorithmic Information Structure Design: A Survey. SIGecom Exch. 2017.
    • S. Dughmi, H. Xu. Algorithmic Bayesian Persuasion. STOC 2016.
    • Y. Cheng, H. Cheung, S. Dughmi, E. Emamjomeh-Zadeh, L. Han, S. Teng. Mixture Selection, Mechanism Design, and Signaling. FOCS 2015.
    • U. Bhaskar, Y. Cheng, Y. Ko, C Swamy. Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games. EC 2016.
    • M. Hardt, N. Megiddo, C. H. Papadimitriou, M. Wootters. Strategic Classification. ITCS 2016.
    • J. M. Kleinberg, M. Raghavan. How Do Classifiers Induce Agents to Invest Effort Strategically? EC 2019.
    • H. Zhang, Y. Cheng, V. Conitzer. When Samples Are Strategically Selected. ICML 2019.
    • H. Zhang, Y. Cheng, V. Conitzer. Distinguishing Distributions When Samples Are Strategically Transformed. NeurIPS 2019.
    • S. Ahmadi, H. Beyhaghi, A. Blum, K. Naggita. The Strategic Perceptron. EC 2021.
    • H. Zhang, Y. Cheng, V. Conitzer. Automated Mechanism Design for Classification with Partial Verification. AAAI 2021.
    • Z. Feng, D. C. Parkes, H. Xu. The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation. ICML 2020.
  • Theoretical Deep Learning:
    • S. Arora et al. Theory of Deep Learning. 2019.
    • D. Soudry, E. Hoffer, M. S. Nacson, N. Srebro. The Implicit Bias of Gradient Descent on Separable Data. ICLR 2018.
    • A. Jacot, C. Hongler, F. Gabriel. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. NeurIPS 2018.
    • 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.
    • 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.
    • M. Zhou, R. Ge, C. Jin. A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network. COLT 2021.
    • C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals. Understanding Deep Learning Requires Rethinking Generalization. ICLR 2017.
    • M. Belkin, D. Hsu, S. Ma, S. Mandal. Reconciling Modern Machine Learning Practice and the Bias-Variance Trade-off. PNAS 2019.
    • C. Tosh, A. Krishnamurthy, D. Hsu. Contrastive Estimation Reveals Topic Posterior Information to Linear Models. JMLR 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. Madry, A. Makelov, L. Schmidt, D. Tsipras, A. Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. ICLR 2018.
    • D. Song, K. Eykholt, I. Evtimov, E. Fernandes, B. Li, A. Rahmati, F. Tramèr, A. Prakash, T. Kohno. Physical Adversarial Examples for Object Detectors. WOOT @ USENIX 2018.
    • W. Nie, B. Guo, Y. Huang, C. Xiao, A. Vahdat, A. Anandkumar. Diffusion Models for Adversarial Purification. ICML 2022.
    • A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin. Attention Is All You Need. NIPS 2017.
    • J. V. Oswald, E. Niklasson, E. Randazzo, J. Sacramento, A. Mordvintsev, A. Zhmoginov, M. Vladymyrov. Transformers Learn In-Context by Gradient Descent. ICML 2023.

Grading

• Paper-reading presentation (40%): Students will form groups to read research papers. Each group will read and present a paper to the class.
• Course project (60%): 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 (24%): There are bonus points for top paper-reading presentations, top final projects, and top reviewers.

Academic Integrity

Academic achievement is evaluated on the basis of work that a student produces independently. A student who obtains credit for work, words, or ideas that are not the products of their own effort is dishonest. Such dishonesty undermines the integrity of the academic standards of the University. Infringement of the Academic Code entails penalties ranging from reprimand to suspension, dismissal, or expulsion from the University. Students who have questions about any aspect of the Academic Code should consult the instructor or an academic dean.

Disability Policies

Brown University is committed to full inclusion of all students. Students who need accommodations should reach out to Student Accessibility Services (SAS) for assistance (sas@brown.edu, 401-863-9588, Brown SAS Website).

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, students shall notify the instructor at least five days in advance of the date when they will be absent. The instructor shall make every reasonable effort to honor the request.