Regularized M -estimators with nonconvexity: Statistical and algorithmic theory for local optima
We establish theoretical results concerning local optima of regularized Mestimators, where both loss and penalty functions are allowed to be nonconvex. Our results show that as long as the loss satisfies restricted strong convexity and the penalty satisfies suitable regularity conditions, any local optimum of the composite objective 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 and regression in generalized linear models using nonconvex regularizers such as SCAD and MCP. 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 stat in log(1/ stat ) iterations, the fastest possible rate for any first-order method. We provide simulations to illustrate the sharpness of our theoretical predictions.
summary: This paper extends a previous 
      line of work on analysis of the effectiveness of estimators based on 
      non-convex optimization; in particular, it provides statistical guarantees 
      for a class of separable non-convex functions: those that are a sum of a 
      loss function that is non-convex but has RSC, and regularizers which are 
      potentially non-convex themselves. For such settings the paper shows the 
      consistency of any local (as opposed to global, or special) minimum. 
      clarity: The paper is clearly written, except for 
      (a) the issue of the side-function g. Except for a brief 
      discussion, there is not much to go by in trying to understand the purpose 
      of this function. A better discussion of this would enhance the paper. 
      Also maybe synthetic experiments to see whether this is needed in 
      "practice". (b) it is casually mentioned that generalizations to 
      other "decomposable" regularizers is possible. doing so would 
      significantly increase the applicability of this work, e.g. extending to 
      settings like low-rank matrices etc. originality: The 
      reviewer feels the paper has limited originality. In particular, a lot of 
      the proof borrows from the previous work of Loh and Wainwright; this fact 
      is highlighted, for example, by the fact that the result holds for very 
      specific regularizers: those which are separable into a sum of terms, one 
      for each coordinate (like the \ell_1 norm is). Similarly, another 
      generalization - to non-convex functions with RSC, instead of functions 
      that arise from "corrected LASSO" in Loh-Wainwright - is not fleshed out 
      much. Do these represent a straightforward generalization (along the lines 
      of Negahban et al), or a substantial new advance ? significance: 
      The significance of this paper is not immediately clear to the 
      reviewer. In particular, while it is clear that a result about all local 
      minima is more powerful than just a result for global minima or special 
      initializations, it is not clear what are the settings where all the 
      assumptions would hold. For example, the paper seems to be focused 
      on sparse recovery type settings, given that the regularizer is separable 
      and has other "ell_1 - like" properties. The authors give two examples 
      which satisfy the assumptions, but these are not widely popular in the 
      literature. What about, for example, the more popular example of \rho(t) = 
      |t|^p for some p less than 1 ? Also, are there interesting/natural 
      loss functions that are non-convex, but still have RSC and to whom the 
      results of this a paper can be applied ? The paper seem to give no 
      examples in this direction.