Theory of Computing Seminar

Thursday October 13, 2016 1:30 PM

From algorithms to lower bounds and back via the statistical query complexity

Speaker: Vitaly Feldman, IBM Research Almaden
Location: Annenberg 213


In this talk I'll show how algorithms for convex optimization can be used to derive lower bounds against general convex relaxations for well-studied constraint satisfaction problems. This technique relies on several recent advances in understanding of statistical query (SQ) algorithms*:
1. A notion of SQ dimension of a problem that lower bounds the SQ complexity of the problem.
2. Analysis of the SQ dimension of a class of constraint satisfaction problems.
3. SQ algorithms for stochastic convex optimization.
I'll overview these results and give some of their additional applications.
* Statistical query algorithms [Kearns 1993] are algorithms that instead of random samples from an input distribution D over a domain X, have access to a SQ oracle for D. Given a real-valued query function g over X, the oracle returns an estimate of the expectation of g on a sample chosen randomly from D.
Based on joint works with C. Guzman, W. Perkins and S. Vempala.


Series Theory of Computing Seminar Series

Contact: Thomas Vidick