The Sum-of-Squares Algorithmic Paradigm in Statistics

(STATS 319: "Literature of Statistics", Winter 2021)
Course description

This seminar course will introduce and explore Sum-of-Squares (SoS) algorithms in the context of statistics. In recent years, the powerful SoS "proofs-to-algorithms" methodology has led to numerous breakthroughs in algorithmic statistics, yielding polynomial-time 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 high-quality 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.

Potential works by topic

Tensor decomposition & latent variable models: Tensor decomposition provides a powerful primitive for learning latent variable models, and sum-of-squares algorithms have revolutionized algorithmic guarantees for tensor decomposition. These algorithms were some of the first to use the "proofs-to-algorithms" paradigm, meaning that simple proofs of identifiability immediately yield SoS algorithms.

Fast Algorithms: Sum-of-squares algorithms use large semidefinite programs as a subroutine, with running times which are at best super-quadratic 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:

Clustering, Robust Estimation, and Robust Regression: the SoS paradigm has yielded the first-ever 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.

Lower Bounds: Since SoS algorithms are, in some sense, the most powerful polynomial-time algorithms known, proving lower bounds against sum-of-squares algorithms provides convincing evidence that solving certain algorithmic problems is beyond our reach. Below are a few representative papers on the topic.

More:

Resources

If you feel I have left something important out of this list, please do not hesitate to email me.