The SumofSquares Algorithmic Paradigm in Statistics
(STATS 319: "Literature of Statistics", Winter 2021)
 Instructor: Tselil Schramm
 Time: Mondays 13:00–14:20 Pacific, Winter 2021
 Office hours: by appointment
Course description
This seminar course will introduce and explore SumofSquares (SoS) algorithms in the context of statistics. In recent years, the powerful SoS "proofstoalgorithms" methodology has led to numerous breakthroughs in algorithmic statistics, yielding polynomialtime algorithms with provable guarantees for previously unreachable problems including learning latent variable models (via tensor decomposition), clustering, problems in robust statistics, and more.
The course will begin with an introductory lecture designed to bring the uninitiated up to speed. We will then cover several fundamental topics including tensor decomposition for latent variable models, robust clustering, and fast algorithms based on SoS. After this, the remaining topics will be guided by student choice. See below for a list of possible papers.
Format:
The course will follow a seminar format; with the exception of the first lecture, each lecture will be delivered by one or two students.
For each lecture, I will designate a student scribe to produce highquality notes.
Prerequisites: The prerequisites for this course are "mathematical maturity" and a solid foundation in probability.
You should be comfortable reading material at the level of e.g. this blog post, or e.g. this paper.
Lectures
Lecture notes will be posted within a week or two of each lecture date.
 (0111) Lecture 0: Introduction to SoS, robust mean estimation. [notes]
(0118) NO CLASS: Martin Luther King Jr. Day.
 (0125) Lecture 1: Tensor decomposition & learning latent variable models. [notes]
 (0201) Lecture 2: Clustering and learning mixtures. [notes]
 (0208) Lecture 3: Robust linear regression. [slides]
(0215) NO CLASS: Presidents' Day.
 (0222) Lecture 4: Speeding up SumofSquares: Gradient Methods for HeavyTailed Mean Estimation. [notes]
 (0301) Lecture 5: Speeding up SumofSquares: Spectral Algorithms from SoS Analyses. [notes]
 (0308) Lecture 6: TBD, student choice.
 (0315) Lecture 7: TBD, student choice.
Potential works by topic
Tensor decomposition & latent variable models:
Tensor decomposition provides a powerful primitive for learning latent variable models, and sumofsquares algorithms have revolutionized algorithmic guarantees for tensor decomposition.
These algorithms were some of the first to use the "proofstoalgorithms" paradigm, meaning that simple proofs of identifiability immediately yield SoS algorithms.
Fast Algorithms: Sumofsquares algorithms use large semidefinite programs as a subroutine, with running times which are at best superquadratic in the input size. For this reason, realizing the guarantees of these algorithms in practice remains an exciting challenge. There are a number of approaches for taking an SoS algorithm and extracting a faster algorithm, and we will explore a number of these. Relevant resources include:
 Fast spectral algorithms from sumofsquares proofs: tensor decomposition and planted sparse vectors by Hopkins, Schramm, Shi and Steurer.
 Fast and robust tensor decomposition with applications to dictionary learning by Schramm and Steurer.
 Fast Mean Estimation with SubGaussian Rates by Cherapanamjeri, Flammarion, and Bartlett.
 Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection by Dong, Hopkins, and Li.

List Decodable Mean Estimation in Nearly Linear Time by Cherapanamjeri, Mohanty, and Yau, and ListDecodable Mean Estimation in NearlyPCA Time by Diakonikolas, Kane, Kongsgaard, Li, and Tian.
Clustering, Robust Estimation, and Robust Regression: the SoS paradigm has yielded the firstever polynomial time algorithms with provable guarantees for a number of algorithmic tasks in statistics; this has been especially true for problems where robustness plays an important role.
Here are several works on this topic, though this is a very active area of research and this list is by no means exhaustive.
 Mixture Models, Robustness, and Sum of Squares Proofs by Hopkins and Li,
Outlierrobust momentestimation via sumofsquares by Kothari and Steurer, and Better Agnostic Clustering Via Relaxed Tensor Norms by Kothari and Steinhardt. See also this series of blog posts by Sam Hopkins.
 Efficient Algorithms for OutlierRobust Regression, by Klivans, Kothari, and Meka.
 Mean Estimation with SubGaussian Rates in Polynomial Time, by Hopkins. The first polynomialtime algorithm for heavytailed mean estimation.
 Algorithms for HeavyTailed Statistics: Regression, Covariance Estimation, and Beyond, by Cherapanamjeri, Hopkins, Kathuria, Raghavendra, and Tripuraneni.
Lower Bounds: Since SoS algorithms are, in some sense, the most powerful polynomialtime algorithms known, proving lower bounds against sumofsquares algorithms provides convincing evidence that solving certain algorithmic problems is beyond our reach.
Below are a few representative papers on the topic.
 A Nearly Tight SumofSquares Lower Bound for the Planted Clique Problem by Barak, Hopkins, Kelner, Kothari, Moitra, and Potechin. See also the prior works of
DeshpandeMontanari,
HopkinsKothariPotechinRaghavendraSchramm, and
MekaPotechinWigderson, which are significantly weaker but also less technically involved.
 Sum of squares lower bounds for refuting any CSP by Kothari, Mori, O'Donnell, and Witmer.
 The power of sumofsquares for detecting hidden structures by Hopkins, Kothari, Potechin, Raghavendra, Schramm, and Steurer.
More:
 Online and DistributionFree Robustness: Regression and Contextual Bandits with Huber Contamination by Chen, Koehler, Moitra, and Yau.
 Sparse PCA: Algorithms, Adversarial Perturbations and Certificates by d'Orsi, Kothari, Novikov, and Steurer.
 Meanfield approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective by Jain, Koehler, and Risteski.
Resources
If you feel I have left something important out of this list, please do not hesitate to email me.