Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity
Vitaly Feldman, IBM Research, Almaden Research Center
Date: Tuesday, February 14, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: Patil/Kiva G449
Host: Ankur Moitra
Contact: Deborah Goodwin, 617.324.7303, email@example.com
Speaker URL: None
TALK: Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity
In this talk I'll show how algorithms for convex optimization can be
used to derive lower bounds against general convex relaxations for
constraint satisfaction problems. This technique relies on several
recent advances in understanding of statistical query* (SQ)
1. A notion of SQ dimension of a problem that lower bounds the SQ complexity
2. Lower bounds on the SQ dimension 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.
Created by Deborah Goodwin at Friday, February 10, 2017 at 7:56 AM.