Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Local Optima of Nonconvex Regularized M-Estimators

Po-Ling Loh

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2013-54
May 10, 2013

http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-54.pdf

We establish theoretical results concerning all local optima of various regularized $M$-estimators, where both loss and penalty functions are allowed to be nonconvex. Our results show that as long as the loss function satisfies restricted strong convexity and the penalty function satisfies suitable regularity conditions, any local optimum of the composite objective function lies within statistical precision of the true parameter vector. Our theory covers a broad class of nonconvex objective functions, including corrected versions of the Lasso for error-in-variables linear models; regression in generalized linear models using nonconvex regularizers such as SCAD and MCP; and graph and inverse covariance matrix estimation. On the optimization side, we show that a simple adaptation of composite gradient descent may be used to compute a global optimum up to the statistical precision epsilon in log(1/epsilon) iterations, which is the fastest possible rate of any first-order method. We provide a variety of simulations to illustrate the sharpness of our theoretical predictions.

Advisor: Martin Wainwright


BibTeX citation:

@mastersthesis{Loh:EECS-2013-54,
    Author = {Loh, Po-Ling},
    Title = {Local Optima of Nonconvex Regularized M-Estimators},
    School = {EECS Department, University of California, Berkeley},
    Year = {2013},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-54.html},
    Number = {UCB/EECS-2013-54},
    Abstract = {We establish theoretical results concerning all local optima of various regularized $M$-estimators, where both loss and penalty functions are allowed to be nonconvex. Our results show that as long as the loss function satisfies restricted strong convexity and the penalty function satisfies suitable regularity conditions, any local optimum of the composite objective function lies within statistical precision of the true parameter vector. Our theory covers a broad class of nonconvex objective functions, including corrected versions of the Lasso for error-in-variables linear models; regression in generalized linear models using nonconvex regularizers such as SCAD and MCP; and graph and inverse covariance matrix estimation. On the optimization side, we show that a simple adaptation of composite gradient descent may be used to compute a global optimum up to the statistical precision epsilon in log(1/epsilon) iterations, which is the fastest possible rate of any first-order method. We provide a variety of simulations to illustrate the sharpness of our theoretical predictions.}
}

EndNote citation:

%0 Thesis
%A Loh, Po-Ling
%T Local Optima of Nonconvex Regularized M-Estimators
%I EECS Department, University of California, Berkeley
%D 2013
%8 May 10
%@ UCB/EECS-2013-54
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-54.html
%F Loh:EECS-2013-54