NIPS 2011 Sparse Representation & Low-rank Approximation Workshop: Fast global convergence...

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.