SCS Faculty Candidate
- Gates Hillman Centers
- ASA Conference Room 6115
- PRAVESH KOTHARI
- Research Instructor
- Institute for Advanced Study
- Princeton University
Sum-of-Squares Method: Towards a Unified Approach to Average-case Problems
Recovering a hidden signal or structure in the presence of random noise is a recurring theme in fundamental problems arising in computational complexity, cryptography, machine learning, and statistics. In this talk, I'll present a promising approach for such average-case problems based on the sum-of-squares (SoS) meta-algorithm, a systematic hierarchy of convex programs invented independently in control theory, quantum information, and proof complexity.
In a sequence of recent works, we showed that this meta-algorithm yields the best-known provable guarantees for well-studied non-convex optimization problems arising in unsupervised machine learning, cryptography, statistics, and quantum information. These results often significantly outperform those obtained via previously known methods.
For example, we obtain the first improvement to the classical spectral algorithm for clustering due to Vempala and Wang (2002). As one of the consequences, we obtain a quasi-polynomial time algorithm for the fundamental problem of clustering mixtures of high-dimensional Gaussians whenever statistically possible. No sub-exponential time algorithm was previously known.
Remarkably, such results are obtained without tailoring the algorithm to the problem at hand.
On the flip side, establishing strong lower bounds for the SoS method has proven challenging and has been actively investigated in both proof complexity and hardness of approximation. In a sequence of recent works, we developed two general methods for establishing tight SoS lower bounds for fundamental average-case problems of interest in machine learning, cryptography, and game theory. As one consequence, we obtained a tight SoS lower bound for the Planted Clique problem completing a program begun in an influential recent work of Meka and Wigderson (2013).
Taken together, these results present the tantalizing possibility of a unified theory of algorithms and complexity for average-case problems based on the SoS method.
Pravesh Kothari is a Research Instructor at the Institute for Advanced Study and Princeton University. His research focuses on the analysis of general-purpose algorithmic-schemes for non-convex optimization problems arising in machine learning, cryptography, quantum information in addition to classical combinatorial optimization. He obtained his Ph.D. from UT Austin in August 2016 advised by Adam Klivans where his research was partially supported by the Simons award for graduate students in theoretical computer science.
Faculty Host: Anupam Gupta (CSD)