MPI-INF Logo
Campus Event Calendar

Event Entry

New for: D1, D2, D3, INET, D4, D5

What and Who

Quest for a unified theory of efficient optimization and estimation (Video Lecture)

David Steurer
ETH Zürich
INF Distinguished Lecture Series
AG 1, AG 2, AG 3, INET, AG 4, AG 5, SWS, RG1, MMCI  
MPI Audience
English

Date, Time and Location

Thursday, 26 March 2020
14:00
60 Minutes
E1 4
Video
Saarbrücken

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 with provable guarantees 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.

My collaborators and I show in a sequence of recent works that for a wide range of optimization and estimation problems, this meta-algorithm achieves the best known provable guarantees, often improving significantly over all previous methods.
For example, for mixtures of spherical Gaussians, we obtain guarantees that improve exponentially over the previous best ones and approach, for the first time, the information-theoretic limits.
Remarkably, the SOS meta-algorithm achieves these guarantees without being tailored to this specific problem.

Moreover, we prove that for a rich class of problems, the guarantees that SOS achieves are best possible with respect to a restricted but very powerful model of computation.
This result leads to the strongest known concrete lower bounds for NP-complete problems.

Taken together these results point toward a unified theory for efficient optimization and estimation centered around SOS that could change how we think about efficient computation in general.

Contact

Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only

Uwe Brahm, 04/20/2020 18:01
Kurt Mehlhorn, 03/25/2020 08:25
Kurt Mehlhorn, 03/23/2020 08:41
Kurt Mehlhorn, 03/17/2020 11:23
Kurt Mehlhorn, 03/11/2020 08:56 -- Created document.