Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Estimation Algorithms from Identifiability Proofs

An emerging theme in a recent line of research is that proofs in restricted proof systems like sum-of-squares can inform the design of provably efficient algorithms, especially for the kind of estimation problems that arise in statistics and machine learning. To illustrate this theme, we discuss examples like clustering and community detection, where we obtain provable guarantees that significantly improve the state of the art and are potentially optimal.

Based on joint works with Sam Hopkins, Pravesh Kothari, and Jacob Steinhardt.

Type of Seminar:
Control Seminar Series
Prof. David Steurer
ETH Zurich, D-INFK
May 14, 2018   17:15 h

Contact Person:

No downloadable files available.
Biographical Sketch:
David Steurer is an assistant professor in the department of computer science at ETH Zurich.
He obtained his PhD at Princeton University in 2010 and was a postdoctoral researcher at Microsoft Research New England for two years.
After that, he was an assistant professor at Cornell University and a visiting assistant professor at the Institute for Advanced Study.
He investigates the power and limitations of efficient algorithms for optimization and estimation problems.
His work has made major contributions to the Unique Games Conjecture and the sum-of-squares method, two central developments toward the effort of uncovering a unified theory for efficient optimization.
He has received the 2010 FOCS best paper award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, the 2014 Microsoft Research Faculty Fellowship, and the 2015 STOC best paper award.
In 2018, he was awarded the Held Prize by the US National Academy of Sciences and he is an invited speaker at the International Congress of Mathematicians.