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