PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal computational and statistical rates of convergence for sparse nonconvex learning problems

Zhaoran Wang, Han Liu, Tong Zhang

arXiv:1306.4960v5stat.ML

TL;DR

Nonconvex penalized M-estimators may have desirable statistical properties, but their global solutions are generally computationally intractable. The paper proposes an approximate regularization path-following method and jointly analyzes its finite-precision computation and statistical behavior. It obtains geometric convergence for the full path, refined statistical rates, and oracle properties for the final estimator.

  • Problem

    Global solutions of nonconvex penalized M-estimators are generally computationally intractable, while prior analyses often assumed exact optimization and left computational complexity unclear.

  • Method

    The paper uses an approximate regularization path-following method for penalized M-estimators with possibly nonconvex loss or penalty functions, analyzing approximate local solutions at finite numerical precision.

  • Results

    The algorithm achieves a global geometric convergence rate for the full regularization path, while the final approximate local solution attains the optimal statistical rate and exact local solutions have refined oracle properties.

  • Takeaways & Limitations

    Nonconvex penalties yield oracle statistical properties, including refined rates and exact support recovery, while the proposed analysis characterizes all approximate and exact local solutions along the path.

  • Takeaways & Limitations

    The constant in one theoretical bound is rather large for practical purposes because the analysis does not optimize constants.

Abstract

from arXiv · show

We provide theoretical analysis of the statistical and computational properties of penalized $M$-estimators that can be formulated as the solution to a possibly nonconvex optimization problem. Many important estimators fall in this category, including least squares regression with nonconvex regularization, generalized linear models with nonconvex regularization and sparse elliptical random design regression. For these problems, it is intractable to calculate the global solution due to the nonconvex formulation. In this paper, we propose an approximate regularization path-following method for solving a variety of learning problems with nonconvex objective functions. Under a unified analytic framework, we simultaneously provide explicit statistical and computational rates of convergence for any local solution attained by the algorithm. Computationally, our algorithm attains a global geometric rate of convergence for calculating the full regularization path, which is optimal among all first-order algorithms. Unlike most existing methods that only attain geometric rates of convergence for one single regularization parameter, our algorithm calculates the full regularization path with the same iteration complexity. In particular, we provide a refined iteration complexity bound to sharply characterize the performance of each stage along the regularization path. Statistically, we provide sharp sample complexity analysis for all the approximate local solutions along the regularization path. In particular, our analysis improves upon existing results by providing a more refined sample complexity bound as well as an exact support recovery result for the final estimator. These results show that the final estimator attains an oracle statistical property due to the usage of nonconvex penalty.

1. Introduction.

The paper develops an approximate regularization path-following method for nonconvex penalized M-estimators and jointly analyzes computation and statistics. It establishes geometric convergence for the full path, refined statistical rates, and oracle properties including exact support recovery.

  • Motivation: Nonconvex penalized M-estimators can have statistically attractive global solutions, but computing those global solutions is generally intractable.The paper instead targets local solutions satisfying first-order optimality conditions.
  • Method: The proposed approximate path-following method handles nonconvex losses and penalties, including SCAD, MCP, and semiparametric elliptical-design losses.It analyzes approximate and exact local solutions along the full regularization path.
  • Computational results: A logarithmic number of proximal-gradient iterations suffices to calculate the entire regularization path, with a global geometric convergence rate optimal among first-order methods.The optimality claim follows because the rate attains the first-order lower bound for strongly convex and smooth objectives, a subclass of the considered objectives.
  • Statistical results: All approximate local solutions along the path achieve statistical recovery rates, while the final estimator attains the optimal rate in the d ≫ n regime.At the target stage, λN = λtgt = C′√(log d/n).
  • Oracle properties: The exact local solutions have a refined oracle rate of order s*/n, versus the general rate of order s*log d/n when s*=s*1 and t=N.The analysis also guarantees exact support recovery when the nonzero coefficients exceed a specified minimum signal strength.
  • Scope of analysis: The joint analysis characterizes the statistical and computational behavior of the entire regularization path, including finite numerical precision.This addresses prior analyses that assumed optimization problems could be solved exactly.

2. Some Nonconvex Sparse Learning Problems.

This section introduces nonconvex penalties and a semiparametric elliptical design regression problem, whose robust covariance estimation can produce a nonconvex loss.

  • Nonconvex Penalty: SCAD and MCP decompose into an ℓ1 penalty plus a concave component, reducing bias relative to ℓ1 regularization for large coefficients.The paper illustrates their penalty functions, concave components, and derivatives, and states that nonconvex penalties can have more attractive statistical properties.
  • Nonconvex Penalty: SCAD and MCP satisfy the paper’s regularity conditions through concavity parameters ζ− and ζ+ governing qλ(βj).For SCAD, ζ− = 1/(a −1) and ζ+ = 0; for MCP, ζ− = 1/b and ζ+ = 0.
  • Nonconvex Penalty: The framework is not limited to SCAD and MCP, relying instead on regularity conditions imposed on the concave penalty component.The paper explicitly presents SCAD and MCP as examples satisfying these conditions.
  • Semiparametric Elliptical Design Regression: Semiparametric elliptical design regression models n observations from an elliptical distribution while assuming E(Y | X = x) = x^Tβ∗.The model extends Gaussian random-design regression to heavy-tailed data through an elliptical family.
  • Semiparametric Elliptical Design Regression: A rank-based covariance estimator replaces the unknown population covariance, but its possible indefiniteness makes the resulting loss function nonconvex.The estimator is calculated by a two-step procedure and is designed for robustness within the elliptical family.
  • Optimization Setup: The method targets approximate local solutions because globally solving these nonconvex M-estimators is generally computationally intractable.The paper then introduces approximate regularization path following and a proximal-gradient building block for nonconvex problems.

3. Approximate Regularization Path Following Method.

The method follows a decreasing regularization path, using sparse-solution initialization and a modified proximal-gradient procedure to obtain approximate local solutions for nonconvex objectives. Its precision schedule preserves statistical accuracy across intermediate stages and targets sharper final-stage recovery.

  • Approximate Regularization Path: The path starts at λ0 = ∥∇L(0)∥∞, where the exact local solution is all-zero, and decreases toward a target λtgt.The target may be selected by cross-validation or a high-dimensional BIC criterion.
  • Approximate Regularization Path: Regularization parameters follow λt = η^tλ0 with η ∈ [0.9, 1), and λN = λtgt.The number of stages is determined by the ratio λ0/λtgt, with η chosen as an absolute constant.
  • Optimization Precision: Intermediate stages use optimization precision ϵt = λt/4, while the final stage solves to ϵopt ≪ λtgt/4.This schedule keeps intermediate optimization error at the statistical scale and enables sharper final-stage recovery.
  • Approximate Regularization Path: Each stage uses the previous approximate local solution and stored proximal-gradient curvature information to initialize the next stage efficiently.The algorithm obtains an approximate local solution at each λt and uses it to initialize the following stage.
  • Proximal-Gradient Method: Directly applying Nesterov’s proximal-gradient method can encounter bad local optima because the loss and penalty may be nonconvex.The paper therefore modifies the proximal-gradient method using the surrogate-loss reformulation.
  • Proximal-Gradient Method: The nonconvex penalty is decomposed as Pλ(β) = λ∥β∥1 + Qλ(β), treating L(β) + Qλ(β) as a surrogate loss.The new penalty is convex, while the surrogate loss is proved strongly convex on a sparse set.
  • Analysis: The paper establishes iteration-complexity and statistical-performance guarantees for the approximate regularization path method.These results jointly characterize the computational and statistical behavior of the full path.

4. Theoretical Results.

The paper establishes geometric computational convergence along the full regularization path and refined statistical guarantees for local solutions under nonconvex regularization. The final estimator achieves minimax estimation rates, while nonconvex penalties improve rates for sufficiently large coefficients.

  • Assumptions and scope: The analysis requires bounded logistic curvature and uses a sparse-eigenvalue condition that can follow from RIP assumptions, while the practical constants may be large.Under RIP with s = 877s* and δ = 0.01, the paper derives a compatible sparse-eigenvalue condition; it separately notes that the constant in (4.4) is large for practical use.
  • Computational results: Theorem 4.5 establishes geometric convergence within each path stage and a global geometric rate for computing the entire regularization path.The global rate is stated to be optimal among first-order optimization methods.
  • Computational results: Each non-final stage requires no more than a logarithmic number of proximal-gradient iterations, and the full path needs logarithmic complexity in optimization precision.The same order also applies to the required line-search iterations.
  • Statistical results: All approximate local solutions along the regularization path satisfy statistical convergence guarantees, with the final approximate solution attaining the minimax parameter-estimation rate.Theorem 4.7 characterizes approximate solutions at every regularization parameter.
  • Statistical results: Exact local solutions benefit from nonconvex regularization through refined rates for coefficients exceeding the penalty-dependent threshold ν_t.For SCAD and MCP, the threshold scales as ν_t = Cλ_t, and the threshold decreases along the path.
  • Statistical results: For least-squares loss, the refined 1/n rate removes the log d factor from the usual s*log d/n rate under the stated signal-strength condition.The paper states analogous results for logistic and semiparametric elliptical design losses.

5. Proof of Main Results.

The proofs maintain sparsity and statistical control across proximal-gradient iterations, enabling restricted strong convexity and smoothness within each path stage. Induction then transfers these properties across the entire regularization path.

  • Stagewise convergence: Geometric convergence is established by proving strong convexity and smoothness of the surrogate objective on sparse sets.The loss may be nonconvex globally, but becomes strongly convex and smooth on the relevant sparse region.
  • Path-following induction: The initialization for stage t is the approximate solution from stage t−1, which supplies statistical recovery and suboptimality conditions for the next stage.The proof uses the previous stage's output as β^0_t and verifies the required conditions recursively.
  • Stagewise convergence: Monotone objective decrease preserves the statistical conditions needed for all proximal-gradient iterates within a stage.The argument combines closeness to the target objective with sparsity and boundedness conditions.
  • Sparsity propagation: Sparse proximal-gradient inputs produce sparse outputs, allowing sparsity to be propagated recursively through every iteration within a path stage.This sparsity propagation is used to establish the solution path by induction.
  • Path-wide conclusion: Theorem 5.5 gives geometric convergence and logarithmic iteration bounds for approximate local solutions under the stage assumptions.The induction across stages yields the global geometric convergence result.
  • Statistical consequences: The proof chain supplies the statistical rates of approximate solutions, refined exact-local-solution rates, and support-recovery results used later.These results are obtained after combining the preceding lemmas and theorem applications.

6. Discussion.

The discussion contrasts the proposed method with nonconvex optimization procedures that require exact subproblem solutions, stronger signal conditions, or prior sparsity knowledge. It also reports numerical evaluations of computational efficiency and statistical accuracy.

  • Comparison with prior methods: MC+ may be inefficient because its solution path can contain exponentially many switching points.The multi-stage path-following approach is presented as a way to address this issue.
  • Comparison with prior methods: Unlike multi-stage convex relaxation, the proposed analysis explicitly accounts for finite numerical precision and provides iteration complexity for the full regularization path.The comparison emphasizes simultaneous computational and statistical analysis rather than exact optimization at every stage.
  • Comparison with prior methods: The proposed minimum signal-strength requirement scales as log d/n, whereas the compared LLA analysis requires s*log d/n.The paper identifies the former scaling as optimal and the latter as suboptimal.
  • Comparison with prior methods: The method avoids the prior knowledge of the true sparsity level required by IHT for fast global convergence.The discussion also states that IHT's bound becomes weak when cast into the paper's sub-Gaussian noise setting.
  • Numerical evaluation: Numerical experiments illustrate computational efficiency and statistical accuracy on problems combining nonconvex loss and penalty functions.The experiments also compare the proposed method with existing nonconvex procedures.

7. Numerical Results.

The numerical experiments examine convergence and statistical recovery for the proposed path-following method. Across synthetic sparse-regression settings, the method converges rapidly and nearly recovers the true support with error close to the oracle estimator.

  • Semiparametric elliptical design regression: n = 500 samples and d = 2500 dimensions are used for semiparametric elliptical design regression with MCP.The experiment uses the semiparametric elliptical random-design loss and MCP penalty.
  • Convergence: The objective-function gap decays exponentially with k within each path-following stage.Each line represents a stage, and the proximal-gradient iterations begin from the preceding stage’s approximate solution.
  • Convergence: The suboptimality measure also decays exponentially, requiring only a logarithmic number of iterations per stage to reach the desired precision.This behavior supports the stated iteration-complexity result for the approximate local solutions.
  • Convergence: The preceding stage’s approximate solution initializes the next stage inside the optimization-precision and fast-convergence regions.This describes the mechanism by which local fast convergence yields global progress along the path.
  • Statistical recovery: The ℓ2 recovery error decreases toward a small value as optimization proceeds, consistent with the predicted statistical properties.The figure’s behavior is characterized by Theorem 4.7.
  • Comparison with existing procedures: With n = 200, d = 2000, and ∥β∗∥0 = 10, the proposed method almost exactly recovers S∗ and achieves ℓ2 error close to the oracle estimator.It outperforms the existing nonconvex procedures in this example, while all nonconvex procedures outperform the Lasso.

8. Conclusion.

The supplementary material supports the paper’s framework through penalty, elliptical-distribution, covariance-estimation, and proximal-gradient details. It also records robust covariance-estimation properties and verifies relevant regularity conditions for the considered models.

  • Nonconvex penalties: The supplement provides analytical forms for SCAD and MCP and illustrates regularity condition (e) for both penalties.For SCAD, the illustration considers the cases λ2 ≥ aλ1 and λ2 < aλ1.
  • Elliptical distributions: An elliptical distribution is represented using a uniformly spherical direction, an independent nonnegative scale variable, and a scatter matrix.The generalized correlation matrix standardizes the scatter matrix, and becomes the correlation matrix when the scale has a finite second moment.
  • Covariance estimation: The elliptical covariance procedure combines a Kendall’s tau estimator for generalized correlation with scale estimates from Catoni’s M-estimator.The rank-based correlation estimator is invariant to the generating variable’s distribution within the elliptical family.
  • Covariance estimation: Catoni’s M-estimator achieves Gaussian-like deviation behavior under a weak moment condition at a fixed confidence level.This property is used for estimating the component standard deviations in the covariance procedure.
  • Optimization updates: The supplement gives proximal-gradient update schemes for the nonconvex losses and penalties considered in the paper.It derives the unconstrained soft-thresholding update and the constrained update obtained by projection or rescaling.

B.2. Derivation of Optimization Update Schemes.

The optimization-update derivation obtains unconstrained and ℓ2-constrained proximal-gradient steps. The constrained solution is formed from the unconstrained solution by a boundary-preserving rescaling when necessary.

  • Constraint handling: For an inactive ℓ2-ball constraint, complementary slackness gives τ = 0, so the constrained and unconstrained updates coincide.The unconstrained update already lies inside B2(R) in this case.
  • Unconstrained update: The unconstrained minimizer is obtained by soft-thresholding.This yields the first update scheme for Ω = Rd.
  • Constraint handling: For an active ℓ2-ball constraint, the constrained minimizer lies on the boundary and is obtained by rescaling the unconstrained solution.The rescaling factor is determined by the Lagrangian multiplier and enforces the radius constraint.
  • Constrained update: The resulting projection formula is T_L,λ(β′; R) = R · T_L,λ(β′; +∞)/∥T_L,λ(β′; +∞)∥2.This produces the second update scheme for Ω = B2(R).
  • Assumption verification: The supplement verifies with high probability the gradient condition needed for least-squares, logistic, and semiparametric elliptical design losses.For semiparametric elliptical design loss, the target regularization level is proportional to √(log d/n).

C.2. Justification of Assumption 4.4 in Wang et al. (2014a).

The supplement justifies the sparse-eigenvalue assumption underlying the theory. It shows that restricted strong convexity and smoothness imply the required condition, and applies this reasoning to semiparametric elliptical and logistic losses.

  • Semiparametric elliptical design loss: For semiparametric elliptical design loss, the Hessian is the estimated predictor covariance submatrix bKX.The relevant sparse eigenvalues are therefore controlled through the covariance estimator.
  • Semiparametric elliptical design loss: The supplement concludes that Assumption 4.4 holds with high probability in the semiparametric elliptical setting.It reports probability at least 1 − 4d−1 − 6d−2 under the stated conditions.
  • Assumption comparison: Assumption 4.4 is weaker than the restricted strong convexity and smoothness assumption used by Loh and Wainwright (2013).The supplement establishes this implication through sparse-vector Hessian bounds.
  • Sparse-eigenvalue bounds: For sparse unit vectors, the Hessian quadratic form is bounded between C′′ and 3C, yielding finite sparse-eigenvalue bounds.The argument takes β′ toward β after applying Taylor and mean-value expansions.
  • Logistic loss: The same framework establishes Assumption 4.4 for generalized linear models with sub-Gaussian design, including logistic loss but excluding the Poisson model cited there.This transfers the relevant high-probability assumption from the referenced restricted-convexity results.
  • Computational analysis: The proximal-gradient lemmas used in the computational analysis rely on sparse-eigenvalue conditions and penalty-concavity parameters.These lemmas bound objective decrease and approximate-solution suboptimality within each path-following stage.

D.5. Proof of Lemma 5.4 in Wang et al. (2014a).

The proof establishes sparsity control for the soft-thresholding proximal-gradient update, including explicit bounds for support-related error components and preservation of the sparsity pattern under the ℓ2 constraint.

  • Constraint handling: Projecting the unconstrained update onto B2(R) preserves its sparsity pattern.Thus, the sparsity analysis can focus on the unconstrained proximal update even when the feasible set is an ℓ2 ball.
  • Soft-thresholding structure: The proximal-gradient update acts as soft-thresholding on an intermediate vector with threshold λ/L.The analysis reduces sparsity control to bounding coordinates whose intermediate magnitudes exceed λ/L.
  • Support control: At most es coordinates in S∗ satisfy the threshold condition, using the decomposition es1 + es2 + es3 ≤ es.The proof separately bounds three coordinate groups and combines them to control the update support.
  • Component bounds: The first two components are bounded by es1 = 250κs∗ and es2 = 0.These bounds follow from inequalities involving the estimation error, penalty regularity, and the condition number κ.

D.6. Proof of Theorem 5.5 in Wang et al. (2014a).

The proof shows that each path-following stage remains sparse, converges to a unique exact local solution, and achieves geometric convergence under the stated restricted curvature and line-search conditions.

  • Stagewise sparsity: The path-following iterates remain sufficiently sparse throughout each stage under the induction argument.The resulting iterates retain the statistical recovery properties supplied by the cited sparse-estimation lemma.
  • Local-solution convergence: Within each stage, the iterate sequence converges to a unique exact local solution satisfying the required optimality condition.Monotone objective decrease, boundedness, and restricted strong convexity support existence and uniqueness.
  • Geometric convergence: The proximal-gradient method has a geometric convergence rate within each path-following stage.The proof combines the stopping criterion, restricted strong convexity, and the line-search bound.
  • Iteration complexity: The total proximal-gradient complexity is bounded by stagewise iteration bounds derived from the line-search and objective-decrease conditions.The proof concludes Theorem 5.5 after aggregating the per-iteration inequalities.

D.7. Proof of Theorem 4.5 in Wang et al. (2014a).

The proof establishes geometric convergence for the approximate regularization path, controls the number of proximal-gradient steps across stages, and derives objective-value guarantees and support-recovery consequences.

  • Stage transitions: The output of one stage is sufficiently suboptimal for initializing the next regularization parameter.Lemma D.4 supplies the transition property required for induction across the path.
  • Path-wide invariants: All path-following outputs satisfy ∥eβt∥0 ≤ es and Lt ≤ 2(ρ+ − ζ+) for t = 1, …, N.The bounds follow by induction from the initialization and the preceding stage theorem.
  • Stagewise complexity: Each intermediate stage and the final stage have explicit proximal-gradient iteration bounds.The proof states separate complexity bounds for t = 1, …, N−1 and for the N-th stage.
  • Full-path complexity: The full regularization path has a bounded total number of proximal-gradient steps obtained by summing the stagewise costs.The total complexity combines the number of path-following stages with the per-stage geometric rates.
  • Objective guarantees: The approximate solutions satisfy objective-value accuracy guarantees relative to the target regularization parameter.The proof applies Lemma D.3 to transfer suboptimality across successive regularization parameters and at the target value.
  • Oracle recovery: The final local solution equals the oracle estimator and has positive coefficients on the true support.The proof uses restricted convexity and optimality conditions to identify the local solution with the oracle estimator.

D.10. Proof for Lemma 4.9 and Theorem 4.10.

The proof establishes uniqueness of the oracle minimizer under sparse strong convexity and analyzes its recovery properties, while the appendix also introduces Catoni-based scale estimation for elliptical designs.

  • Oracle uniqueness: The loss is strongly convex on vectors supported by S∗, making the oracle minimizer unique even for nonconvex loss functions.The argument applies Taylor expansion and sparse eigenvalue conditions on the restricted support.
  • Least-squares oracle: For least-squares loss, the oracle estimator is the ordinary least-squares solution restricted to S∗.Its restricted coordinates are characterized through the design matrix XS∗ and the ordinary least-squares problem.
  • Oracle identification: The local solution at the target regularization parameter equals the oracle estimator under the stated curvature and regularity assumptions.The proof compares their optimality conditions and uses ρ− − ζ− > 0.
  • Support recovery: The oracle estimator has nonzero coefficients on every coordinate of the true support.The proof combines the minimum-signal condition with support containment to obtain exact support recovery.
  • Elliptical-design estimation: Catoni’s estimator is introduced to estimate marginal means and standard deviations for the elliptical random-design analysis.The mean equation can be solved efficiently with Newton’s method, and a related estimator is used for marginal standard deviations.

E.2. Proof of Lemma C.3.

The proof establishes concentration bounds for marginal scale and correlation estimators, then combines them to control the smallest and largest sparse eigenvalues of the estimated covariance structure.

  • Scale and correlation concentration: The proof assumes positive marginal scales and uses concentration bounds for their estimators to control variance-estimation errors.The argument relates variance error to standard-deviation error and invokes a lower bound σ_min on all marginal standard deviations.
  • Sparse eigenvalue bounds: The smallest sparse eigenvalue of the estimated covariance matrix is bounded by combining the correlation-estimator result with marginal-scale concentration.The proof takes an infimum after controlling the two contributing terms and concludes a lower sparse-eigenvalue bound with probability at least 1 − 2d^-2.
  • Sparse eigenvalue bounds: The largest sparse eigenvalue is controlled analogously by taking a supremum and combining correlation and marginal-scale bounds.The proof uses the corresponding concentration results and concludes that the upper sparse-eigenvalue quantity is finite with probability at least 1 − 2d^-1 − 3d^-2.
  • Elliptical design regression: For semiparametric elliptical design regression, the proof applies the same concentration strategy to the augmented vector Z = (Y, X)^T and its rank-based generalized-correlation estimator.The marginal standard deviations of Z are estimated with Catoni estimators, while the correlation component uses the rank-based estimator.

APPENDIX F: DETAILED SETTINGS OF NUMERICAL EXPERIMENTS

The appendix specifies the data-generating settings, regularization path, optimization parameters, comparison methods, and repetition protocol for two numerical experiments.

  • First numerical experiment: The first experiment uses n = 500 samples and d = 2500 predictors from a t-distributed design with 5 degrees of freedom and correlation matrix Σ0.The true parameter has 100 nonzero coordinates, generated independently from a standard Gaussian distribution.
  • First numerical experiment: The first experiment sets λtgt = 0.05, λ0 = 2.8516, η = 0.9015, and N = 39 regularization parameters.It also uses MCP parameter b = 1.1, optimization precision ϵopt = 10^-6, and Lmin = 10^-6.
  • Second numerical experiment: The second experiment uses n = 200 samples and d = 2000 predictors from a correlated Gaussian design with off-diagonal covariance 0.9 and diagonal covariance 1.The response noise is Gaussian with identity covariance, and the experiment compares several competing procedures.
  • Second numerical experiment: The comparison includes LLA, calibrated CCCP, SparseNet, and the multi-stage convex relaxation method.SparseNet uses the same regularization-parameter sequence, while other procedures compute Lasso problems with glmnet at each stage.
  • Second numerical experiment: Each method selects its most suitable regularization parameter by cross-validation, and the second experiment is repeated 1000 times.The multi-stage convex relaxation method uses at most 20 stages, and calibrated CCCP uses τ = 1/log(n).
Loading 1306.4960v5…