- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Fall 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
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 independently invented in multiple disciplines including control theory, quantum information, and proof complexity.
In a sequence of recent works, we show 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 previously known methods. For example, we obtain the first improvement on the classical spectral algorithm for clustering due to Vempala and Wang (2004). As a special case, we partially resolve a recent open question due to Regev and Vijayraghavan by giving an efficient algorithm for the benchmark problem of learning mixtures of high-dimensional Gaussians with center-separations approaching the information theoretically optimal bounds.
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 build two general methods for establishing tight SoS lower bounds for fundamental average-case problems with applications to machine learning, cryptography, and game theory. For example, we show 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 algorithm design for average-case problems based on the SoS method.
Bio:
Pravesh K. 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 algorithm design. Earlier, he obtained his Ph.D. from UT Austin in August 2016 advised by Adam Klivans where his research was partially supported by a Simons award for graduate students in theoretical computer science.