PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Po-Ling Loh, Martin J. Wainwright

arXiv:1305.2436v2math.STcs.ITstat.ML

TL;DR

The paper asks whether nonconvex regularized M-estimators can provide reliable solutions despite potentially many local optima and computational difficulty. It develops conditions ensuring that every stationary point is statistically accurate, and modifies composite gradient descent to reach statistical precision rapidly. The theory covers nonconvex losses and penalties across several high-dimensional models and is supported by simulations.

  • Problem

    Nonconvex M-estimation can have computationally difficult local optima, while standard statistical guarantees often concern only global optima.

  • Method

    The paper analyzes regularized M-estimators under restricted strong convexity of the loss and regularity conditions on potentially nonconvex penalties, then studies modified composite gradient descent.

  • Results

    Every stationary point lies within statistical precision of the population-level optimum, and modified composite gradient descent reaches near-global statistical accuracy in log(1/εstat) steps.

  • Takeaways & Limitations

    Optimization methods that converge to stationary points can produce statistically consistent solutions without requiring a specially designed algorithm to find one particular local optimum.

  • Takeaways & Limitations

    The stated penalty assumptions exclude bridge and capped-ℓ1 penalties, and the proof of a main theorem requires 4µ < α1, though the authors note a weaker alternative may suffice.

Abstract

from arXiv · show

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 $ε$ in $\log(1/ε)$ steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.

1. Introduction

The paper addresses the gap between practical optimization of nonconvex M-estimators and theory limited to global optima. It shows that local and stationary solutions can have strong statistical guarantees and can be reached efficiently.

  • Motivation: Nonconvex objectives can have undesirable local optima, while standard statistical theory often guarantees properties only for global optima.This creates a gap between theoretical guarantees and the solutions produced by iterative optimization methods.
  • Contributions: The paper studies regularized M-estimators with nonconvex loss and penalty, establishing bounds on the distance between local optima and the unique population-risk minimizer.The results include ℓ1-, ℓ2-, and prediction-error bounds.
  • Contributions: All stationary points, including local and global optima, lie within a small statistical-error neighborhood of the population-level minimum under suitable regularity conditions.This means methods converging to stationary points need not target a specially selected local optimum.
  • Optimization: A modified composite gradient descent method reaches statistical precision in log(1/εstat) steps, with geometric convergence under the paper’s sufficient conditions.The paper describes this as the rate expected for strongly convex functions.
  • Illustration: The theory applies when both the corrected least-squares cost and MCP regularizer are nonconvex, while retaining the same qualitative statistical and optimization-error behavior.Figure 1 illustrates this setting for corrected least squares with MCP and logistic regression with SCAD.
  • Scope: The techniques extend beyond least-squares and convex losses, and cover regularizers such as capped-ℓ1 that do not satisfy smoothness constraints on the entire positive axis.The paper also gives rigorous applicability results for generalized linear models.
  • Relation to Prior Work: The paper distinguishes its contribution from related work by guaranteeing statistical consistency for all local optima rather than only analyzing iterates along one path-following algorithm.It also establishes applicability to broad classes of generalized linear models.

2. Problem Formulation

The paper formulates regularized M-estimation with potentially nonconvex loss and penalty under convex feasibility constraints, then specifies regularity conditions for penalties and restricted strong convexity for losses.

  • 2.1 Background: The estimator combines an empirical loss with a separable regularizer controlled by tuning parameters, plus an ℓ1-dominating side constraint that ensures feasibility and existence of a global minimum.An additional convex set may impose problem-specific constraints, such as positive semidefiniteness for graphical models.
  • 2.1 Background: The framework allows nonconvexity in both the empirical loss and regularizer, while retaining convex side constraints and requiring the target parameter to be feasible.Continuity together with the bounded feasible region guarantees existence of a global minimizer.
  • Assumption 1: The regularizer assumptions require symmetry, normalization at zero, monotone derivative behavior, differentiability away from zero, subdifferentiability at zero, and weak convexity.These conditions regulate the penalty’s nonconvexity and behavior near the origin.
  • Assumption 1: The assumptions include the standard ℓ1 penalty and many commonly used regularizers, but exclude bridge penalties and capped-ℓ1 because of derivative or differentiability restrictions.The paper notes that capped-ℓ1 also fails the stated weak-convexity condition, while explaining that modified arguments can handle it.
  • Assumption 1: SCAD and MCP satisfy Assumption 1 with L = 1 and µ = 1 under their stated parameterizations.SCAD uses a fixed parameter a > 2, while MCP uses a fixed parameter b > 0.
  • 2.3 Nonconvex Loss Functions and Restricted Strong Convexity: The loss need not be convex; instead, it must be differentiable and satisfy restricted strong convexity, which lower-bounds Taylor remainders over specified regions.RSC is the main loss-side condition used by the statistical theory.
  • 2.3 Nonconvex Loss Functions and Restricted Strong Convexity: RSC can hold for high-dimensional losses that are nonconvex or not strongly convex, enforcing strong-convexity-like behavior only over cones with positive curvature and tolerance terms.For a strongly convex loss, the tolerance terms vanish; for convex but not strongly convex losses, the relevant remainder is nonnegative.
  • 2.3 Nonconvex Loss Functions and Restricted Strong Convexity: The paper uses two RSC inequalities and prefers a uniform condition over all subsets of a given size, extending beyond formulations specialized to convex or quadratic losses.The formulation is no stronger than prior conditions in the convex and quadratic cases described.

3. Statistical Guarantees and Consequences

The paper proves statistical error bounds for any stationary point under restricted strong convexity and regularity conditions, including nonconvex losses and penalties. These guarantees extend across corrected regression, generalized linear models, and graphical models, while supporting fast optimization to statistical precision.

  • Main statistical guarantees: Any stationary point satisfying the first-order conditions lies close to the target β∗ under suitable regularity and restricted strong convexity conditions.The results include interior local maxima as well as local and global optima.
  • Main statistical guarantees: The squared ℓ2-error scales proportionally with the sparsity level k and λ^2, yielding k log p/n scaling under typical choices of λ.Here k is the number of nonzeros in β∗.
  • Prediction error: Theorem 2 bounds the prediction-error measure, which behaves similarly to the squared Euclidean distance between the stationary point and β∗.For generalized linear models, this measure is equivalent to a symmetrized Bregman divergence.
  • Curvature and nonconvexity: The condition 4µ < α1 is sufficient for the proof but may be replaced by cµ < α1 for any c > 1; extreme cases with α1 significantly smaller than µ can degrade local-optimum behavior.The paper reports empirical evidence that good behavior may still occur when α1 < 3/2µ.
  • Corrected linear regression: For corrected errors-in-variables regression, any stationary point satisfies ℓ1-, ℓ2-, and prediction-error bounds with high probability when n ≥ C max{R^2, k} log p.The error prefactor increases with both covariate-noise and additive-noise levels.
  • Corrected linear regression: These corrected-regression bounds match earlier global-minimum rates while strengthening them to hold for any stationary point and broader possibly nonconvex penalties.The result removes the need for an algorithmic proof route to establish statistical accuracy.
  • Nonconvex penalized regression: In clean linear regression with nonconvex penalties, any algorithm guaranteed to reach a stationary point is sufficient, rather than requiring an algorithm targeting a specific local optimum.The paper also gives a theoretical motivation for the usual SCAD choice a = 3.7.

Suppose 3

The analysis establishes error bounds for stationary points under restricted curvature and regularity assumptions, using first-order conditions and cone arguments to control estimation error.

  • Suppose 3: For the ℓ1 penalty, the resulting Frobenius-norm graphical-model rate matches minimax rates for s-sparse inverse covariance estimation.This comparison is stated for Corollary 3.
  • Suppose 3: The proof bounds the distance between a stationary point and the population minimizer through restricted curvature, penalty regularity, and first-order conditions.The argument introduces the error vector, establishes a cone condition, and combines deviation and curvature inequalities.
  • Suppose 3: The proof first shows the error vector has bounded ℓ2 norm, then applies the restricted strong-convexity bound to obtain the desired estimation result.The ℓ2 norm is shown to be at most 1 under the chosen regularization and sample-size conditions.
  • Suppose 3: A cone condition controls the error outside the indices corresponding to the largest coordinates of the estimation difference.The index set A contains the k largest coordinates of the error in magnitude.

4. Optimization Algorithms

The paper adapts composite gradient descent to objectives with a differentiable nonconvex component and a convex possibly nonsmooth penalty. Under RSC/RSM and penalty conditions, iterates contract to statistical accuracy in logarithmically many steps.

  • 4. Optimization Algorithms: Composite gradient descent decomposes the objective into a differentiable nonconvex function and a possibly nonsmooth convex penalty.This decomposition enables the composite updates used for the nonconvex program.
  • 4.1 Fast Global Convergence: Theorem 3 guarantees convergence to a δ-neighborhood of a global optimum when the tolerance is at least on the order of the statistical error.The squared tolerance δ^2 cannot be arbitrarily small, but may match the squared statistical error ε_stat^2.
  • 4.1 Fast Global Convergence: κ ∈ (0, 1) acts as a contraction factor, so squared optimization error falls below δ^2 after O(log(1/δ^2) / log(1/κ)) iterations.The theorem guarantees δ-accuracy for iterations beyond a logarithmic threshold.
  • 4.1 Fast Global Convergence: The convergence result assumes RSC/RSM conditions, suitable regularization, µ < 2α, and a sufficiently small stepsize.The curvature and nonconvexity parameters enter through the denominator 2α − µ; larger curvature or weaker nonconvexity tightens the bound.
  • 4. Optimization Algorithms: When additional constraints are present, each update still requires only a convex optimization problem, and the fast-convergence theory carries over.The result applies, for example, to graphical Lasso settings.
  • 4. Optimization Algorithms: An initialization within a constant radius of a global optimum keeps all successive iterates within the same radius.Lemma 2 states this for an initial vector satisfying ∥β0 − β̂∥2 ≤ 3.

5. Simulations

Simulations across linear and logistic regression support the paper’s statistical-consistency and optimization-convergence claims, while also showing multiple local optima for nonconvex penalties and degradation in extreme curvature regimes.

  • 5. Simulations: For SCAD, a = 3.7 produces a tighter cluster of optimization trajectories than a different parameter choice.This setting is identified as the empirically suggested choice in the simulations.
  • 5. Simulations: The estimation error decreases toward zero with increasing rescaled sample size for Lasso, SCAD, and MCP, demonstrating statistical consistency.The curves stack across problem sizes when plotted against n/(k log p).
  • 5. Simulations: Nonconvex SCAD and MCP programs exhibit multiple local optima, whereas the Lasso program has a unique global optimum in the convex case.The simulations compare trajectories from 20 initializations for logistic regression.
  • 5. Simulations: When loss curvature is severely weaker than penalty nonconvexity, convergence can break down and local-optimum behavior can deteriorate.Figure 5 reports good behavior for some violations but breakdown for much smaller α1 values.

6. Discussion

The discussion concludes that stationary points in these nonconvex regularized M-estimation problems can be statistically reliable, while identifying regimes where the theory and algorithms may break down.

  • All stationary points are close to the truth, so methods converging to stationary points can provide statistically consistent solutions.
  • Figure 5 examines breakdown points as a function of the curvature parameter α1.
  • A modified composite gradient descent method can obtain near-global optima in linear time.
  • Future work includes extending consistency results to bridge penalties and non-coordinatewise regularizers.
  • For nonsmooth losses and penalties, whether modified composite gradient descent reaches near-global optima in polynomial time remains open.

A.1 General Properties

This section develops general regularizer properties used in the theory and verifies that key penalties, including SCAD and MCP, satisfy the required assumptions.

  • Assumption 1 supplies regularity conditions used to establish the paper’s theoretical bounds.
  • The penalty ρλ is λL-Lipschitz, so its subgradients and derivatives are bounded in magnitude by λL.
  • Under Assumption 1, Lemma 5 provides sparsity-related inequalities for vectors and their largest coordinates.
  • The SCAD and MCP regularizers satisfy Assumption 1 with L = 1 and µ = 1.
  • The appendix derives restricted strong convexity conditions for convex losses under stated scaling and deviation requirements, then applies Theorem 1.
  • For generalized linear models, bounded curvature and sub-Gaussian arguments establish the required RSC conditions with high probability.

B.4 Proof of Corollary 3

The proof verifies the restricted strong convexity and smoothness conditions needed for the graphical-model corollary, then invokes the main theorem.

  • For the matrix loss, vectorization and the mean value theorem are used to establish the local curvature bound.
  • The RSC condition holds with α1 = (|||Θ∗|||2 + 1)−2 and τ1 = 0.
  • Lemma 9 supplies the corresponding global condition with α2 = (|||Θ∗|||2 + 1)−2.
  • Applying Theorem 1 yields the desired corollary.

C.1 Derivation of Three-Step Procedure

This appendix derives the constrained three-step update and its SCAD/MCP closed forms, then establishes the contraction and error bounds used for the optimization result.

  • Derivation of Three-Step Procedure: The three-step procedure distinguishes whether the unconstrained update is feasible and otherwise projects onto the constraint boundary.
  • Derivation of Three-Step Procedure: Lagrangian duality shows that the constrained program is equivalent to projection with the original constraint radius.
  • Derivation of Three-Step Procedure: Because the coordinatewise program separates, the SCAD and MCP updates reduce to scalar subgradient equations with closed-form solutions.
  • Derivation of Three-Step Procedure: The iterates remain within the prescribed neighborhood of the unconstrained optimum by induction under the stated assumptions.
  • Derivation of Three-Step Procedure: The error analysis introduces objective gaps and iterates a contraction inequality to bound optimization error over time.
  • Derivation of Three-Step Procedure: The appendix verifies RSC and RSM conditions for generalized linear models using mean-value and concentration arguments.

D.2 Proof of Lemma 11

The proof derives a uniform probabilistic bound by truncating and controlling summands, then extends the result across ratios of ||∆||1 and ||∆||2 using peeling and a union bound.

  • The truncation function satisfies ϕτ′(u) ≤ u^2·I{|u| ≤ τ′}, providing the key summand bound.
  • Choosing T ≥ 3τ′ ensures T ≥ τ′||∆||2 under the assumption ||∆||2 ≤ 3.
  • Bounded differences, Gaussian-process comparisons, and auxiliary lemmas are combined to obtain a high-probability bound uniformly over the relevant region.The stated probability is at least 1 − c1 exp(−c2n).
  • The proof concludes by combining the intermediate inequalities to obtain the desired result.
  • A peeling argument extends the bound uniformly over the ratio ||∆||1/||∆||2.The argument partitions the region by integer-indexed sets and applies a union bound.

Appendix E. Auxiliary Results

The appendix collects empirical-process and Gaussian-process tools, including symmetrization, sub-Gaussian maximum bounds, complexity comparison, and Sudakov–Fernique comparison.

  • The auxiliary results begin with symmetrization and desymmetrization of empirical processes using Rademacher variables.
  • The appendix relates Gaussian complexity to Rademacher complexity through a comparison involving independent standard normal and Rademacher variables.
  • The Sudakov–Fernique comparison inequality compares centered Gaussian processes through pairwise increment variances.
  • A sub-Gaussian tail definition and a bound for the expected maximum of N zero-mean sub-Gaussian variables are stated.
  • A separate lemma addresses maxima of products of sub-Gaussian variables, under an i.i.d. sub-Gaussian-vector condition and a sample-size requirement involving log p.

Appendix F. Capped-ℓ1 Penalty

This section extends the stationary-point theory to regularizers lacking gradients or subgradients everywhere, using a convex upper-bound construction and modified regularity conditions.

  • The extension targets regularizers such as capped-ℓ1 that do not possess gradients or subgradients everywhere.
  • A surrogate function eρλ is assumed to handle points where ρλ lacks both a gradient and a subderivative.
  • For SCAD or MCP, the original penalty can serve as the surrogate after convexification; for capped-ℓ1, a separate convex upper bound is constructed.
  • Under the stated RSC and penalty assumptions, any stationary point satisfies the theorem’s error bounds, including a prediction-error bound.
  • For capped-ℓ1, the regularizer satisfies the extended assumptions with µ1 = 0, µ2 = 1/c, and L = 1.
  • The capped-ℓ1 penalty is piecewise linear, locally equals |t| within a specified range, and is constant outside it, but is nonsmooth at t = ±λc.
Loading 1305.2436v2…