IC Colloquium : Quest for a unified theory of efficient optimization
Event details
| Date | 27.02.2017 |
| Hour | 10:15 › 11:30 |
| Location | |
| Category | Conferences - Seminars |
By : David Steurer - Cornell University
IC Faculty candidate
Abstract :
Non-convex and discrete optimization problems are at the heart of many algorithmic tasks that arise in machine learning and other computing applications.
A promising approach to solve such problems is the sum-of-squares (SOS) meta-algorithm, which has been discovered multiple times across different disciplines including control theory, proof complexity, and quantum information.
We show in a sequence of recent works that for a wide range of optimization problems this meta-algorithm achieves the best known provable guarantees, often improving significantly over all previous methods.
For example, we obtain the first polynomial-time algorithm for learning sparse dictionaries in the case of non-independent coordinates beyond the square-root of dimension sparsity threshold that has been a inherent barrier for previous provable methods.
Remarkably, SOS achieves these guarantees without being tailored to specific problems.
Moreover, we prove that for a rich class of problems, the guarantees that SOS achieves are optimal with respect to a restricted but very powerful model of computation.
This result leads to the strongest known unconditional lower bounds for NP-complete problems.
Taken together these results point toward a unified theory for efficient optimization centered around SOS that could change how we think about efficient computation and bring a kind of conceptual clarity to the design of algorithms we had never anticipated.
Bio :
David Steurer is an Assistant Professor in the department of computer science at Cornell University and a Visiting Assistant Professor at the Institute for Advanced Study in Princeton.
His research interests are in the theory of algorithms, complexity, and machine learning.
His goal is to identify the underlying principles that distinguish tractable problems from intractable ones.
Steurer received his PhD from Princeton University advised by Sanjeev Arora and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University.
For his work, he received best paper awards at STOC and FOCS, a Microsoft Research Faculty Fellowship, an ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship.
More information
IC Faculty candidate
Abstract :
Non-convex and discrete optimization problems are at the heart of many algorithmic tasks that arise in machine learning and other computing applications.
A promising approach to solve such problems is the sum-of-squares (SOS) meta-algorithm, which has been discovered multiple times across different disciplines including control theory, proof complexity, and quantum information.
We show in a sequence of recent works that for a wide range of optimization problems this meta-algorithm achieves the best known provable guarantees, often improving significantly over all previous methods.
For example, we obtain the first polynomial-time algorithm for learning sparse dictionaries in the case of non-independent coordinates beyond the square-root of dimension sparsity threshold that has been a inherent barrier for previous provable methods.
Remarkably, SOS achieves these guarantees without being tailored to specific problems.
Moreover, we prove that for a rich class of problems, the guarantees that SOS achieves are optimal with respect to a restricted but very powerful model of computation.
This result leads to the strongest known unconditional lower bounds for NP-complete problems.
Taken together these results point toward a unified theory for efficient optimization centered around SOS that could change how we think about efficient computation and bring a kind of conceptual clarity to the design of algorithms we had never anticipated.
Bio :
David Steurer is an Assistant Professor in the department of computer science at Cornell University and a Visiting Assistant Professor at the Institute for Advanced Study in Princeton.
His research interests are in the theory of algorithms, complexity, and machine learning.
His goal is to identify the underlying principles that distinguish tractable problems from intractable ones.
Steurer received his PhD from Princeton University advised by Sanjeev Arora and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University.
For his work, he received best paper awards at STOC and FOCS, a Microsoft Research Faculty Fellowship, an ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host : O. Svensson