NIPS 2011 Sparse Representation & Low-rank Approximation Workshop: Fast global convergence... February 8, 2012

Favorite:

Sparse Representation and Low-rank Approximation Workshop at NIPS 2011

Invited Talk: Computation meets Statistics: Fast global convergence for high-dimensional statistical recovery by Martin Wainwright, University of California at Berkeley, Department of Statistics and EECS

Abstract: Many statistical estimators are based on convex optimization problems formed by the weighted sum of a loss function with a norm-based regularizer. Particular examples include $\ell_1$-based methods for sparse vectors, nuclear norm for low-rank matrices, and various combinations thereof for matrix decomposition. In this talk, we describe an interesting connection between computational and statistical efficiency, in particular showing that the same conditions that guarantee that an estimator has low statistical error can also be used to certify fast convergence of first-order optimization methods up to statistical precision.