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

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 by appointment in 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:
- Sam Lobel, Ruo Yu Tao, Tuluhan Akbulut. Robust Linear Reinforcement Learning.
- Advay Mansingka, Joanna Tasmin. Robust Flow Navigation via Reinforcement Learning.
- Alessio Mazzetto. Nonparametric Density Estimation under Distribution Drift.
- Nicholas Petrocelli. Robust Mean Estimation for Few-Shot Classification Meta-Learning.
- Qiuhong Wei, Tianqi Liu. Privacy-Preserving Machine Learning.
Top Reviewers:
- Sudatta Hor.
- Qiuhong Wei.
List of all reviewers. The following students participated in the peer-review process: Sudatta Hor, Naomi Lee, Sam Lobel, Jacob Makar-Limanov, Chris Mascioli, Rohit Mohanty, Yiyang Nan, Arjun Prakash, Joanna Tasmin, Mete Akbulut Tuluhan, Aaron Wang, Qiuhong (Anna) Wei, Sean Yamamoto, Jiaqi Zhang. 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 and presentation (paper reading guidelines).

Oct 10: Decide which paper to read.
Nov 7: Paper reading presentation video due.

Final project (project guidelines).

Oct 24: Decide final project teams, topics, and presentation dates.
Nov 28 - Dec 12: Project presentations.
Dec 16: Project reports due.

Schedule

Week 1 (Sep 5): No classes. Labor Day.
Week 2 (Sep 12): Robust Non-Convex Optimization I (Lecture 1, Lecture 1 Slides).

Introduction to the Course.
Introduction to Non-Convex Optimization.
Non-Convex Matrix Completion.

[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 19): Robust Non-Convex Optimization II (Lecture 2).

Semi-Random Models.
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 26): Robust Non-Convex Optimization III (Lecture 3).

Tractable Non-Convex Problems.
Semi-Random Sparse and Low-Rank Problems.

[3] Y. Zhang, Q. Qu, J. Wright. From Symmetry to Geometry: Tractable Nonconvex Problems. 2020.

Week 5 (Oct 3): High-Dimensional Robust Statistics I (Lecture 4).

Introduction to Robust Statistics.
High-Dimensional Robust Mean Estimation.

[4] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, A. Stewart. Robust Estimators in High Dimensions without the Computational Intractability. FOCS 2016.

Week 6 (Oct 10): No classes. Columbus Day.
Week 7 (Oct 17): High-Dimensional Robust Statistics II (Lecture 5).

Robust Mean Estimation in Nearly-Linear Time.
Robust Mean Estimation via Gradient Descent.

[5] Y. Cheng, I. Diakonikolas, R. Ge. High-Dimensional Robust Mean Estimation in Nearly-Linear Time. SODA 2019.
[6] Y. Cheng, I. Diakonikolas, R. Ge, M. Soltanolkotabi. High-dimensional Robust Mean Estimation via Gradient Descent. ICML 2020.

Week 8 (Oct 24): High-Dimensional Robust Statistics III (Lecture 6).

Beyond Robust Mean Estimation.
Robust Sparse Mean Estimation.
Robust Covariance Estimation.

[7] I. Diakonikolas, D. M. Kane. Recent Advances in Algorithmic High-Dimensional Robust Statistics. 2019.

Week 9 (Oct 31): Spectral Graph Theory I (Lecture 7).

Introduction to Spectral Graph Theory.
Graph Sparsification by Effective Resistances.
Linear-Sized Graph Sparsifiers.

[8] Y. Lee, H. Sun. An SDP-Based Algorithm for Linear-Sized Spectral Sparsification. STOC 2017.

Week 10 (Nov 7): Spectral Graph Theory II (Lecture 8).

Multiplicative Weight Update.
Faster and Simpler Solvers for Positive SDPs.

[9] R. Peng, K. Tangwongsan, P. Zhang. Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming. SPAA 2012.

Week 11 (Nov 14): Learning with Strategic Agents I (Lecture 9, Lecture 9 Slides).

Introduction to Game Theory.
Information Structure Design.
Strategic Classification.

[10] S. Dughmi. Algorithmic Information Structure Design: A Survey. SIGecom Exch. 2017.
[11] M. Hardt, N. Megiddo, C. H. Papadimitriou, M. Wootters. Strategic Classification. ITCS 2016.

Week 12 (Nov 21): Learning with Strategic Agents II (Lecture 10).

Learning from Strategically Provided Samples.
Planning with Participation Constraints.

[12] H. Zhang, Y. Cheng, V. Conitzer. When Samples Are Strategically Selected. ICML 2019.
[13] H. Zhang, Y. Cheng, V. Conitzer. Efficient Algorithms for Planning with Participation Constraints. EC 2022.

Week 13-15 (Nov 28): Project Presentations.
Additional Readings (optional):

Robust Non-Convex Optimization (Weeks 2-4):

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. 2022.
R. Ge, J. D. Lee, T. Ma. Matrix Completion has No Spurious Local Minimum. NIPS 2016.
X. Zhang, L. Wang, Y. Yu, Q. Gu. A Primal-Dual Analysis of Global Optimality in Nonconvex Low-Rank Matrix Recovery. ICML 2018.
J. Sun, Q. Qu, J. Wright. A Geometric Analysis of Phase Retrieval. ISIT 2016.
R. Ge, T. Ma. On the Optimization Landscape of Tensor Decompositions. NIPS 2017.
J. Sun, Q. Qu, J. Wright. Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture. IEEE Trans. Inf. Theory. 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. Found. Trends Mach. Learn. 2015.

High-Dimensional Robust Statistics (Weeks 5-8):

B. Tran, J. Li, A. Madry. Spectral Signatures in Backdoor Attacks. NeurIPS 2018.
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, A. Stewart. Being Robust (in High Dimensions) Can Be Practical. ICML 2017.
I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, A. Stewart. SEVER: A Robust Meta-Algorithm for Stochastic Optimization. ICML 2019.
Y. Cheng, I. Diakonikolas, R. Ge, D. P. Woodruff. Faster Algorithms for High-Dimensional Robust Covariance Estimation. COLT 2019.
S. Balakrishnan, S. S. Du, J. Li, A. Singh. Computationally Efficient Robust Sparse Estimation in High Dimensions. COLT 2017.
I. Diakonikolas, W. Kong, A. Stewart. Efficient Algorithms and Lower Bounds for Robust Linear Regression. SODA 2019.
Y. Cheng, H. Lin. Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time. ICLR 2021.
I. Diakonikolas, D. Kane, D. Kongsgaard, J. Li, K. Tian. List-Decodable Mean Estimation in Nearly-PCA Time. NeurIPS 2021.
S. B. Hopkins, J. Li, F. Zhang. Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization. NeurIPS 2020.
Y. Cheng, I. Diakonikolas, D. M. Kane, R. Ge, S. Gupta, M. Soltanolkotabi. Outlier-Robust Sparse Estimation via Non-Convex Optimization. NeurIPS 2022.
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.

Spectral Graph Theory (Weeks 9-10):

D. Spielman. Spectral and Algebraic Graph Theory. 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 (Weeks 11-12):

J. M. Kleinberg, M. Raghavan. How Do Classifiers Induce Agents to Invest Effort Strategically? EC 2019.
S. Ahmadi, H. Beyhaghi, A. Blum, K. Naggita. The Strategic Perceptron. EC 2021.
H. Zhang, Y. Cheng, V. Conitzer. Distinguishing Distributions When Samples Are Strategically Transformed. NeurIPS 2019.
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.
J. D. Abernethy, Y. Chen, J. W. Vaughan. Efficient Market Making via Convex Optimization, and a Connection to Online Learning. ACM Trans. Economics and Comput. 2013.

Theoretical Deep Learning:

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.
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.
Z. Allen-Zhu, Y. Li, Z. Song. A Convergence Theory for Deep Learning via Over-Parameterization. ICML 2019.
A. Jacot, C. Hongler, F. Gabriel. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. NeurIPS 2018.
D. Soudry, E. Hoffer, M. S. Nacson, N. Srebro. The Implicit Bias of Gradient Descent on Separable Data. ICLR 2018.
J. D. Lee, Q. Lei, N. Saunshi, J. Zhuo. Predicting What You Already Know Helps: Provable Self-Supervised Learning. NeurIPS 2021.
S. Arora et al. Theory of Deep Learning. 2019.

Grading

Participation (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 (15%): 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.