Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity

Speaker: 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

Public: Yes

Location: Patil/Kiva G449

Event Type:

Room Description:

Host: Ankur Moitra

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity

Abstract:

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)
complexity:
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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin at Friday, February 10, 2017 at 7:56 AM.