Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima

By Po-Ling Loh, Martin J. Wainwright. 2013

564 citations recorded by the source corpus.

We provide novel theoretical results regarding local optima of regularized $M$-estimators, allowing for nonconvexity in both loss and penalty functions. Under restricted strong convexity on the loss and suitable regularity conditions on the penalty, we prove that \emph{any stationary point} of the composite objective function will lie within statistical precision of the underlying parameter vector. Our theory covers many nonconvex objective functions of interest, including the corrected Lasso for errors-in-variables linear models; regression for generalized linear models with nonconvex penalties such as SCAD, MCP, and capped-$\ell_1$; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the $\ell_1$-, $\ell_2$-, and prediction error between stationary points and the population-level optimum. We also propose a simple modification of composite gradient descent that may be used to obtain a near-global optimum within statistical precision $\epsilon$ in $\log(1/\epsilon)$ steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.

Subfields: Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Deeply-Supervised Nets (2014, background): “In [19], a convergence rate is given for M-estimators with locally convex function with compositional loss and regularization terms.”
Best Subset Selection via a Modern Optimization Lens (2015, methodology): “Various effective nonlinear optimization based methods [see, e.g., Candès, Wakin and Boyd (2008), Fan and Li (2001), Loh and Wainwright (2013), Mazumder, Friedman and Hastie (2011), Zhang (2010a), Zou and Li (2008) and the references therein] have been proposed in the literature to obtain good…”
A General Theory of Hypothesis Tests and Confidence Regions for Sparse High Dimensional Models (2014, background): “an and Li,2001), and capped- L 1 penalty (Zhang,2010b), among others. The estimation consistency and oracle properties of the nonconvex estimators are investigated byFan et al.(2012);Fan and Lv(2011);Loh and Wainwright (2013);Wang et al.(2013a);Zhang et al.(2013);Wang et al.(2013b). Though signicant”
Challenges of Big Data Analysis (2013, unknown): “We also refer to [101] and [102] for research studies in this direction.”
Matrix Completion has No Spurious Local Minimum (2016, result): “ the regularizer to restrict the geometry. Parallel to our work Bhojanapalli et al.[BNS16] showed similar results for matrix sensing, which is closely related to matrix completion. Loh and Wainwright [LW15] showed that for many statistical settings that involve missing/noisy data and non-convex regu”
Restricted Strong Convexity Implies Weak Submodularity (2016, result): “Next we define the restricted versions of strong concavity and smoothness, consistent with [2, 19].”
Adaptive Huber Regression (2017, methodology): “We refer to the monographs, Bühlmann and van de Geer (2011) and Hastie, Tibshirani, and Wainwright (2015), for a systematic coverage of contemporary statistical methods for high-dimensional data.”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, methodology): “This procedure works for other classes of undirected graphical models, including Ising models (Ravikumar et al., 2010) and discrete graphical models (Loh and Wainwright, 2013).”
Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions (2019, background): “A similar restricted smoothness condition was considered in [10] by assuming this approximation error to be bounded by L1 w − w̃ (2)2 + L2 log(d) w − w̃ (2)1, where L1 and L2 are two constants (L2 may be very small and depend on the sample size).”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Building a Telescope to Look Into High-Dimensional Image Spaces (2018, background): “In some settings, the landscape has only slight non-convexity, and optimizing the non-convex energy function leads to a solution close to the global minimum, as in [30].”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, background): “low-rank solution, although it is not shown to converge in polynomial time. Finally, our work is completely dierent from other recent works on nonconvex optimization for sparse linear regression. In [42], it is shown that all local optima of a particular non-convex optimization problem are relativel”
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (2017, background): “Although this fact introduces challenges to the analysis, we show that its non-asymptotic efﬁciency can be characterized by a positive quantity called the restricted Cheeger constant .”