Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Quest for a unified theory of efficient optimization and estimation (Video Lecture)
Speaker:David Steurer
coming from:ETH Zuerich
Speakers Bio:
Event Type:INF Distinguished Lecture Series
Visibility:D1, D3, D4, RG1, MMCI, D2, INET, D5, SWS
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Thursday, 26 March 2020
Duration:60 Minutes
Building:E1 4
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.

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Kurt Mehlhorn, 03/25/2020 08:25 AM
  • Kurt Mehlhorn, 03/23/2020 08:41 AM
  • Kurt Mehlhorn, 03/17/2020 11:23 AM
  • Kurt Mehlhorn, 03/11/2020 08:56 AM -- Created document.