The goal of this project was to design new algorithms for some fundamental problems in machine learning (described below). Additionally it contributed new perspectives in the form of (1) A new framework for analyzing non-convex optimization (2) Using semi-definite programming hierarchies to explore the statistical limits of computationally efficient algorithms for representation learning (3) A toolbox for making algorithms based on the methods of moments robust to adversarial corruptions and (4) new non-markov chain based approaches for approximate counting and inference. 

Dictionary Learning: Many types of data turn out to be sparse in an appropriately chosen bases (e.g. representing signals in a wavelet basis). Modern approaches such as dictionary learning attempt to discover such a basis automatically from data by solving a challenging non-convex optimization problem. Despite their widespread use, there are limited provable guarantees. The PI and collaborators gave simple new algorithms for dictionary learning that work in the practically important overcomplete setting. Their analysis was based on a new general framework for analyzing alternating minimization by viewing it as noisy gradient descent on an unknown convex function instead. 

Tensor Completion: A popular model for building recommendation systems is to view our data as coming from a low-rank matrix or tensor. While the problem of completing an unknown low-rank matrix from few observations has been intensively studied, and tight bounds are known, much less is known about completing low-rank tensors. The PI and collaborators gave the first algorithms that asymptotically improve upon the naive algorithm of completing the low-rank tensor as a collection of unrelated low-rank matrices. Furthermore the PI and collaborators showed computational vs. statistical tradeoffs based on existing conjectures about the difficulty of refuting random constraint satisfaction problems. 

Robustness: In 1960, Tukey asked: Are there e cient estimators for learning the parameters of a one-dimensional Gaussian in the presence of noise? His paper launched the field of robust statistics and there are many simple, provably robust estimators in one-dimension. However they all lead to hard optimization problems in high-dimensions. In practice, this means that robust statistical methods are limited to dimension at most six. The PI and collaborators gave the first efficient algorithm for robustly learning a high-dimensional Gaussian. Later, the PI and collaborators extended this to mixtures of Gaussians. The area of algorithmic robust statistics has subsequently seen a flurry of activity, with many exciting results. 

Sampling: A graphical model is a natural framework for modeling statistical dependencies for high-dimensional distributions. Most existing algorithms for sampling and inference rely on the notion of correlation decay, which stipulates that there are no long-range dependencies. In many cases, correlation decay demarcates where the problem goes from computationally easy to hard. The PI considered the problem of uniformly sampling from the set of satisfying assignments to a bounded degree instance of k-SAT. The PI gave the first algorithms that work when the degree is exponentially large in k. It gives a powerful new methodology for designing algorithms that work even when the solution space is disconnected (the freezing regime) where no local markov chain can work. Furthermore the PI gave applications to inference in a natural class of graphical models. 

The project also supported the training of several graduate students and postdocs. Furthermore the PI supervised over fifty summer research projects in mathematics at the highschool and undergraduate level, including many for underrepresented minorities. The PI also wrote a book titled Algorithmic Aspects of Machine Learning which has been used as a primary text in courses run at other universities, and was recently published by Cambridge University Press. 

Last Modified: 11/27/2021
Modified by: Ankur Moitra