Statistics, Optimization and Information Theory: Interplay and Connections

Abstract:

There are various problems which involve a combination of techniques from statistics, optimization, and information theory, and we illustrate this interplay with a few examples in this talk.

First, we consider a problem in optimization theory: namely, how to characterize the minimal computational effort required to solve a certain class of convex programs? This problem was studied in seminal work by Nemirovski and Yudin (1983), who introduced the oracle model of complexity. Working within this framework, we show how stochastic optimization can be reduced to a problem of statistical estimation, and how information theory can be used to characterize the oracle complexity of various problems.

Second, we consider a class of statistical estimators based on solving regularized loss functions. We provide an intuitive set of conditions on the associated optimization problem, and use them to derive a general result on the statistical error. As we illustrate with several examples, the rates obtained by this general approach are minimax-optimal in several well-studied cases.

Based on joint works with Alekh Agarwal, Peter Bartlett, Sahand Negahban, Bin Yu (UC Berkeley), and Pradeep Ravikumar (UT Austin).

Biography:

Martin Wainwright is currently an associate professor at University of California at Berkeley, with a joint appointment between the Department of Statistics and the Department of Electrical Engineering and Computer Sciences. He received a Bachelor's degree in Mathematics from University of Waterloo, Canada, and Ph.D. degree in Electrical Engineering and Computer Science (EECS) from Massachusetts Institute of Technology (MIT). His research interests include coding and information theory, machine learning, mathematical statistics, and statistical signal processing. He has been awarded an Alfred P. Sloan Foundation Fellowship, an NSF CAREER Award, the George M. Sprowls Prize for his dissertation research (EECS department, MIT), a Natural Sciences and Engineering Research Council of Canada 1967 Fellowship, an IEEE Signal Processing Society Best Paper Award in 2008, and several outstanding conference paper awards