2010/10/31 by Sahand N. Negahban, Pradeep Ravikumar, Martin J. Wainwright +1 · 2 citations
Mathematics · Computer Science · #math.ST #cs.IT #math.IT #stat.ME #stat.TH
paper · pdf · doi:10.1214/12-sts400
published as Statistical Science 2012, Vol. 27, No. 4, 538-557 · Published in at http://dx.doi.org/10.1214/12-STS400 the Statistical Science (http://www.imstat.org/sts/) by the Institute of Mathematical Statistics (http://www.imstat.org)
arxiv created 2013/03/12 · arxiv updated 2013/03/13
High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless p/n→0, a line of recent work has studied models with various types of low-dimensional structure, including sparse vectors, sparse and structured matrices, low-rank matrices and combinations thereof. In such settings, a general approach to estimation is to solve a regularized optimization problem, which combines a loss function measuring how well the model fits the data with some regularization function that encourages the assumed structure. This paper provides a unified framework for establishing consistency and convergence rates for such regularized M-estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive some existing results, and also to obtain a number of new results on consistency and convergence rates, in both ℓ2-error and related norms. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure corresponding regularized M-estimators have fast convergence rates and which are optimal in many well-studied cases.