Special Colloquium
Lev Reyzin
Georgia Institute of Technology
The Complexity of Statistical Algorithms
Abstract: We develop a framework for studying optimization problems over
distributions. We define a class of algorithms, called statistical
algorithms, that captures many natural approaches to optimization. We show
that for specific problems over distributions, the complexity of any
statistical algorithm grows exponentially in their input parameters. Our
techniques are inspired by (and generalize) the statistical query model in
learning theory, and in parallel to that concept, we can prove lower bounds
on statistical algorithms using a single parameter that we call statistical
dimension. Applications of our theory indicate the limitations of known
heuristics for a variety of optimization problems. We shall also discuss
advances in some related problems in learning theory.
Wednesday January 18, 2012 at 3:00 PM in SEO 636