Timezone: »
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 errors-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.
Author Information
Po-Ling Loh (University of Wisconsin - Madison)
Martin J Wainwright (UC Berkeley)
Related Events (a corresponding poster, oral, or spotlight)
-
2013 Spotlight: Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima »
Sat. Dec 7th 11:34 -- 11:38 PM Room Harvey's Convention Center Floor, CC
More from the Same Authors
-
2022 Poster: Bellman Residual Orthogonalization for Offline Reinforcement Learning »
Andrea Zanette · Martin J Wainwright -
2016 Poster: Computing and maximizing influence in linear threshold and triggering models »
Justin Khim · Varun Jog · Po-Ling Loh -
2014 Poster: Concavity of reweighted Kikuchi approximation »
Po-Ling Loh · Andre Wibisono -
2013 Poster: Information-theoretic lower bounds for distributed statistical estimation with communication constraints »
Yuchen Zhang · John Duchi · Michael Jordan · Martin J Wainwright -
2013 Oral: Information-theoretic lower bounds for distributed statistical estimation with communication constraints »
Yuchen Zhang · John Duchi · Michael Jordan · Martin J Wainwright -
2013 Poster: Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation »
John Duchi · Martin J Wainwright · Michael Jordan -
2012 Poster: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2012 Oral: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2011 Poster: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright -
2011 Oral: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright