Algorithmic Robust Statistics

CSE 599K | Fall 2025

Course information

Instructor: Jerry Li, OH: Tuesdays 3-4 CSE2 315
Teaching Assistants: Ziyun Chen
Times: Mon, Weds 3-4:30, ECE 003
Canvas

Course description

As machine learning is applied to increasingly sensitive tasks, and applied on noisier and noisier data, it has become important that the algorithms we develop for ML are robust to potentially worst-case noise, a field of study known as robust statistics. This is a rich subject of study, dating back to foundational work of statisticians from the 60s and 70s, and has recently experienced a renaissance, with the development of a new field of algorithmic robust statistics. In this class we will cover this developing theory, and explore the deep connections between it and well-studied topics in theoretical computer science, such as differential privacy, semi-definite hierarchies, and hardness of approximation. This class is intended for CS graduate students in theoretical computer science and/or machine learning who are interested in doing research in this area. However, interested undergraduates and graduate students from other departments are more than welcome to attend as well. The coursework will be light and consists of two problem sets as a well as a final project.

Prerequisites

Mathematical maturity will be expected. Students should be comfortable with probability theory and linear algebra.

A good resource for learning some of the topics covered here in more depth is this book.

Tentative course schedule†

Unit 1: Fundamentals of algorithmic robust statistics

Lecture 1 (9/24): Course introduction. Introduction to robust statistics. notes
Lecture 2 (9/29): Total variation, statistical models, and lower bounds notes
10/1: NO CLASS (instructor travel)
Lecture 3 (10/6): Robust mean estimation in high dimensions.
Lecture 4 (10/8): Spectral signatures and efficient certifiability.
Lecture 5 (10/13): Stronger spectral signitures for Gaussian datasets.
Lecture 6 (10/15): Spectral signatures in empirical datasets.
Lecture 7 (10/20): Efficient filtering from spectral signatures for Gaussian data.
Lecture 8 (10/22): Properties of Gaussian polynomials. Robustly learning arbitrary Gaussians (I).
Lecture 9 (10/27): Robustly learning arbitrary Gaussians (II). Introduction to list learning.
Lecture 10 (10/22): Efficient algorithms for list learning with bounded second moments.

Unit 2: Advanced topics in algorithmic robust statistics

Lecture 11 (11/3): Introduction to sum-of-squares.
Lecture 12 (11/5): Efficient algorithms for robust mean estimation via sum-of-squares.
Lecture 13 (11/10): Fast LP/SDP solvers. Matrix multiplicative weights.
Lecture 14 (11/12): Nearly linear-time algorithms for robust mean estimation.
Lecture 15 (11/17): Introduction to differential privacy.
Lecture 16 (11/19): Connections between robustness and privacy.
Lecture 17 (11/24): Computational/statistical gaps in learning. SQ hardness, low-degree hardness, and reduction-based hardness.
Lecture 18 (11/16): Computational/statistical gaps in robust statistics.
Lecture 19 (12/1): Open directions in robust statistics.
Lecture 20 (12/3): Final project presentations.

Problem sets

There will be 2 homework throughout the class. Homeworks will be due on Wednesdays anywhere on earth. Please submit your homework via Canvas.

Final Project

Your final project will consist of a short (10 minute) presentation on the last day of class. Students can collaborate with up to 1 partner on this final project. Projects can be reading projects, where you survey the literature on some area that we didn't cover, or research projects, where you try (but not necessarily succeed at) tackling an open problem in the area. Projects can be either theoretical or applied. If you're short of ideas, please feel free to ask the instructor.

Please turn in (or email) a one page project proposal by November 12th.

Guidelines, Resources and Expectations

The following is consistent with the standards set at the University of Washington at large.

Academic Integrity

The University takes academic integrity very seriously. Behaving with integrity is part of our responsibility to our shared learning community. If you’re uncertain about if something is academic misconduct, ask me. I am willing to discuss questions you might have.

Acts of academic misconduct may include but are not limited to:

Cheating (working collaboratively on quizzes/exams and discussion submissions, sharing answers, and previewing quizzes/exams)
Plagiarism (representing the work of others as your own without giving appropriate credit to the original author(s))

Concerns about these or other behaviors prohibited by the Student Conduct Code will be referred for investigation and adjudication by (include information for specific campus office).

Students found to have engaged in academic misconduct may receive a zero on the assignment (or other possible outcome).

Conduct

The University of Washington Student Conduct Code (WAC 478-121) defines prohibited academic and behavioral conduct and describes how the University holds students accountable as they pursue their academic goals. Allegations of misconduct by students may be referred to the appropriate campus office for investigation and resolution. More information can be found online here.

Accessibility and Disability Resources

Your experience in this class is important to me. It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), please activate your accommodations via myDRS so we can discuss how they will be implemented in this course.

If you have not yet established services through DRS, but have a temporary health condition or permanent disability that requires accommodations (conditions include but not limited to; mental health, attention-related, learning, vision, hearing, physical or health impacts), contact DRS directly to set up an Access Plan. DRS facilitates the interactive process that establishes reasonable accommodations. Contact DRS at disability.uw.edu.

Religious Accomodations

Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy (https://registrar.washington.edu/staffandfaculty/religious-accommodations-policy/). Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form (https://registrar.washington.edu/students/religious-accommodations-request/).

Safety

Call SafeCampus at 206-685-7233 anytime – no matter where you work or study – to anonymously discuss safety and well-being concerns for yourself or others. SafeCampus’s team of caring professionals will provide individualized support, while discussing short- and long-term solutions and connecting you with additional resources when requested.

The University of Washington prohibits sex discrimination and sex-based harassment and expects all UW community members to respect one another in our shared academic and work environments. Sex discrimination and sex-based harassment can include sexual assault, relationship violence, stalking, unwanted sexual contact, sexual exploitation, sexual harassment, and discrimination based on sex.

Students who believe they have experienced sex discrimination or sex-based harassment are encouraged to contact a Title IX case manager by making a Title IX report. The case manager can provide guidance on available support resources and resolution options.

^{†. Course schedule and contents subject to change and will be announced throughout the term.↩}