PaperlayerView exact revision on arXiv

Source-linked AI summary

Support recovery without incoherence: A case for nonconvex regularization

Po-Ling Loh, Martin J. Wainwright

arXiv:1412.5632v1math.STcs.ITstat.ML

TL;DR

The paper addresses whether support recovery and ℓ∞ guarantees can be established for sparse regression when losses or regularizers are nonconvex. It extends the primal-dual witness method and shows that certain nonconvex penalties can recover support without usual incoherence conditions, across several regression and graphical-model settings.

  • Problem

    ℓ1 regularization can suffer finite-sample bias, while support consistency for stationary points of nonconvex objectives remained unresolved.

  • Method

    The paper extends the primal-dual witness technique using generalized gradients and restricted strong convexity to analyze nonconvex losses and regularizers.

  • Results

    Certain nonconvex regularizers, including SCAD and MCP, guarantee support recovery for stationary points without usual ℓ1 incoherence conditions, with corroborating simulations.

  • Takeaways & Limitations

    Nonconvex regularization can provide support recovery in non-incoherent designs where the usual ℓ1-regularized program fails.

  • Takeaways & Limitations

    The stated theory requires proper choices of λ, R, and δ, and a covariance condition used in one corollary can be fairly strong.

Abstract

from arXiv · show

We demonstrate that the primal-dual witness proof method may be used to establish variable selection consistency and $\ell_\infty$-bounds for sparse regression problems, even when the loss function and/or regularizer are nonconvex. Using this method, we derive two theorems concerning support recovery and $\ell_\infty$-guarantees for the regression estimator in a general setting. Our results provide rigorous theoretical justification for the use of nonconvex regularization: For certain nonconvex regularizers with vanishing derivative away from the origin, support recovery consistency may be guaranteed without requiring the typical incoherence conditions present in $\ell_1$-based methods. We then derive several corollaries that illustrate the wide applicability of our method to analyzing composite objective functions involving losses such as least squares, nonconvex modified least squares for errors-in variables linear regression, the negative log likelihood for generalized linear models, and the graphical Lasso. We conclude with empirical studies to corroborate our theoretical predictions.

1 Introduction

High-dimensional sparse regression commonly replaces computationally difficult ℓ0 optimization with ℓ1 relaxations, but ℓ1 bias motivates nonconvex penalties. The paper asks whether stationary points of nonconvex objectives can consistently recover support without incoherence conditions.

  • The ℓ0 constraint directly encodes sparsity but yields optimization problems that may be NP-hard to solve or approximate.
  • ℓ1 relaxations have a developed theory, but their linear penalty increases with coefficient magnitude and introduces finite-sample estimation bias.
  • SCAD, MCP, and LSP combine ℓ1-like behavior near zero with penalties that become asymptotically constant for larger coefficients.
  • Prior theory established consistency for global optima and oracle properties for selected algorithmic outputs, leaving stationary-point support consistency unresolved.
  • The central question is whether stationary points recover the true support with high probability and how quickly their error probability vanishes.
  • The paper extends the primal-dual witness method to problems with nonconvex losses and regularizers using generalized gradients and restricted strong convexity.
  • Under suitable conditions, SCAD- and MCP-type regularizers guarantee support recovery for all stationary points without the usual ℓ1 incoherence condition.
  • The framework is applied to least squares, errors-in-variables regression, generalized linear models, and the graphical Lasso, with simulations designed to corroborate the theory.

2 Problem formulation

The paper formulates regularized M-estimation with potentially nonconvex losses and coordinate-separable penalties, then extends primal-dual witness analysis to establish support and error guarantees. Its assumptions combine restricted strong convexity with amenable regularizers and suitable feasibility constraints.

  • 2.1 Regularized M-estimators: The framework studies composite objectives formed from a continuous empirical loss and a continuous penalty, allowing either or both to be nonconvex.
  • 2.1 Regularized M-estimators: An ℓ1 constraint ensures existence of a global minimizer, while an optional open convex set models additional parameter restrictions.
  • 2.1 Regularized M-estimators: The analysis restricts penalties to coordinate-separable forms, primarily using a homogeneous univariate regularizer across coordinates.
  • 2.1 Regularized M-estimators: The estimator targets the unique population-risk minimizer β*, with the feasible radius chosen so that β* belongs to the constraint set.
  • 2.2 Class of regularizers: Amenability imposes symmetry, monotonicity, and curvature-related conditions; selection and unbiasedness properties strengthen the requirements for support and ℓ∞ guarantees.
  • 2.2 Class of regularizers: SCAD and MCP are (µ, γ)-amenable, whereas the ℓ1 penalty and LSP are only µ-amenable under the stated classification.
  • 2.3 Nonconvexity and restricted strong convexity: Restricted strong convexity supplies curvature in relevant directions while allowing tolerance for non-sparse directions, and it holds for all k-sparse vectors when n ≿ k log p.
  • 2.4 Primal-dual witness proof technique: The PDW extension uses generalized gradients to analyze local optima, establish support recovery and ℓ∞ bounds, and under suitable restrictions show stationary-point uniqueness.

3 Main statistical results and consequences

The paper extends primal-dual witness analysis to nonconvex losses and regularizers, establishing support-recovery and ℓ∞ guarantees for stationary points under explicit sufficient conditions. Its corollaries show that suitable nonconvex regularizers can remove incoherence requirements in several regression settings, while the guarantees remain conditional on regularity and covariance assumptions.

  • General results: Theorem 1 establishes support recovery and uniqueness for stationary points when restricted strong convexity, regularizer amenability, and strict dual feasibility hold.The incoherence requirement enters through strict dual feasibility and can be weakened for (µ, γ)-amenable regularizers.
  • Conditions and limitations: The guarantees are sufficient rather than necessary and depend on assumptions including µ < 2α1 and, in one least-squares comparison, a strong covariance condition.The paper notes that some covariance structures fail the latter condition and that stationary points may still behave well when the theorem assumptions fail.
  • General results: Theorem 2 controls ℓ∞ error and shows that a beta-min condition yields a tighter oracle-rate bound for (µ, γ)-amenable regularizers.Under these conditions, the local or global optimum agrees with the oracle estimator.
  • Ordinary least squares: SCAD and MCP can guarantee support recovery without incoherence, whereas ℓ1-based recovery requires comparatively stringent incoherence conditions.For amenable regularizers, the unique stationary point can equal the oracle estimator.
  • Ordinary least squares: In ordinary least squares, the nonconvex objective has a unique stationary point with high probability, and under stronger conditions this point equals the oracle estimator.The stated probability is at least 1 − c1 exp(−c2 min{k, log p}).
  • Further applications: The same framework extends to modified nonconvex least squares and generalized linear models, where strict dual feasibility or amenability supports unique stationary-point and oracle guarantees.For generalized linear models, the incoherence condition may be removed for (µ, γ)-amenable regularizers such as SCAD and MCP.

4 Simulations

The simulations test the theoretical guarantees across least-squares, corrupted-covariate, and logistic settings, including designs that violate incoherence. They also examine how regularizer choice and curvature conditions affect support recovery, error consistency, and stationary-point uniqueness.

  • Optimization and theory: The composite gradient descent analysis assumes restricted strong convexity and smoothness, a µ-amenable regularizer, and convex qλ.Under these conditions, Proposition 1 analyzes convergence to the unique global optimum.
  • Optimization and theory: With sample size n ≥ c0k^2 log p, the iterates satisfy an ℓ∞-bound that yields correct-support recovery.The support conclusion follows by combining the ℓ∞-error bound with a minimum signal condition.
  • Simulation design: The first simulations use matrices with bounded eigenvalues that violate incoherence, then test least squares, corrupted covariates, and logistic regression.The non-incoherent matrix class is characterized by bounded eigenvalues but failure of the incoherence condition.
  • Support recovery and error: In corrupted-covariate least squares, SCAD and MCP show a sharp transition to correct support recovery as sample size increases, while their ℓ∞-error decreases to zero.The three problem-size curves roughly align with the predicted k log p scaling.
  • Support recovery and error: All four regularizers are ℓ2-consistent, but SCAD and MCP have noticeably smaller ℓ2-error than the ℓ1-penalty and LSP in the reported setting.The ℓ1-penalty and LSP curves nearly agree for the shared regularization parameter used here.
  • Stationary points: When µ exceeds 2α1, SCAD and MCP can produce multiple stationary points with incorrect support, whereas larger curvature can restore uniqueness.The logistic simulations similarly show multiple stationary points at σx = 1 but unique SCAD and MCP stationary points at σx = 3.

5 Discussion

The paper extends primal-dual witness analysis to composite objectives whose loss and regularizer may both be nonconvex. It presents this framework as theoretical support for nonconvex regularization while identifying open questions about mildly violated conditions and empirical performance.

  • Discussion: The extended framework analyzes composite optimization programs with both nonconvex losses and nonconvex regularizers.It generalizes machinery previously developed for convex objective functions.
  • Discussion: The authors identify guarantees under weaker assumptions than the ℓ1-norm as a reason to use nonconvex regularizers such as SCAD and MCP.The discussion connects this conclusion to the paper’s support-recovery and error-bound results.
  • Open questions: Future work includes guarantees when µ < 2α1 is mildly violated and a rigorous explanation for SCAD and MCP’s improved ℓ2-error performance.The authors also leave open how generally these conclusions extend.

A.1 Main part of proof

The proof constructs a restricted solution, extends its subgradient, and verifies that it is a local minimum while all stationary points lie on the true support. Restricted strict convexity then establishes uniqueness and supports the error analysis.

  • Primal-dual witness construction: The proof follows the primal-dual witness construction, beginning with a restricted problem and a shifted objective.The shifted loss is defined by subtracting qλ from Ln.
  • Primal-dual witness construction: The constructed estimator is shown to be a local minimum by verifying sufficient generalized-gradient conditions.The argument uses the extended subgradient and the concavity and differentiability properties required by the proof framework.
  • Restricted strict convexity: Under the stated conditions, the restricted program is strictly convex on the support subspace.This follows from restricted strong convexity when the regularizer’s concavity parameter satisfies µ < α1.
  • Support and uniqueness: Every stationary point is supported on S, and strict convexity of the restricted program makes that stationary point unique.The proof first excludes support outside S, then invokes strict convexity on the restricted coordinates.
  • Error analysis: The error analysis combines restricted strong convexity, norm inequalities, and a cone condition to control the estimation error.The proof derives bounds by combining inequalities for the loss, subgradient, and error vector.

B Proof of Theorem 2

The proof of Theorem 2 uses the zero-subgradient condition and invertibility on the support to derive coordinatewise control of the estimator. A minimum signal bound then ensures active coefficients remain separated from zero.

  • Restricted solution: Strict convexity on the support makes the restricted zero-gradient solution the unique global minimum of the restricted program.The full estimator agrees with this restricted solution after the support restriction is established.
  • Coordinatewise error bound: The proof uses the zero-subgradient condition together with invertibility of the restricted Hessian or design operator.These steps establish the key bound used in Theorem 2.
  • Minimum signal condition: Under the stated amenability and signal conditions, every active coordinate satisfies |bβj| ≥ γλ.This ensures the derivative of qλ vanishes on the active coordinates in the relevant regime.

C Establishing strict dual feasibility

The appendix derives strict dual feasibility conditions needed for the primal-dual witness argument and compares how penalty properties affect those conditions. Unbiased penalties such as SCAD and MCP avoid an additional incoherence requirement imposed for LSP and ℓ1 penalties.

  • Strict dual feasibility: Proposition 2 establishes strict dual feasibility for an amenable regularizer when inequality (19a) holds.The result applies under Theorem 1's conditions and assumes (µ, γ)-amenability.
  • Strict dual feasibility: Proposition 3 establishes strict dual feasibility under Theorem 1's conditions when Assumption 2 is additionally satisfied.The proof uses the zero-subgradient property and bounds involving the regularizer gradient.
  • Penalty comparison: Unbiased penalties such as SCAD and MCP avoid the additional incoherence condition required for LSP and the usual ℓ1-norm.The comparison states that the relevant bound is essentially unchanged, while Proposition 3 adds incoherence for the non-unbiased penalties.

D.1.1 Proof of part (a)

The proof of part (a) combines the Appendix C machinery with concentration and projection arguments to establish strict dual feasibility and then variable-selection consistency. The resulting bounds hold with high probability under a sample-size scaling involving k and log p.

  • Proof strategy: The proof uses a direct analysis of (bΓ, bγ) to obtain tighter bounds than Proposition 3.The argument is organized around the quantities defined in equation (26).
  • Concentration bounds: Sub-Gaussian tail bounds and union bounds establish the required concentration inequalities.These bounds are applied to the projected quantities appearing in the strict-dual-feasibility argument.
  • Strict dual feasibility: With probability at least 1−c exp(−c′ log p), strict dual feasibility holds when n ≿ k log p.The result follows from the concentration bound and the stated sample-size condition.
  • Support recovery: The resulting strict dual feasibility implies variable-selection consistency by Theorem 1.The proof explicitly invokes Theorem 1 after establishing the feasibility condition.
  • ℓ∞ guarantee: The proof also concludes that the desired ℓ∞-bound holds under the stated assumptions.This conclusion follows by combining the probability bound with part (a) of Theorem 2.

D.2 Proof of Corollary 2

The proof of Corollary 2 verifies concentration and restricted strong convexity conditions for the modified least-squares setting, then applies the strict-dual-feasibility propositions and Theorem 2. The argument yields support recovery and an ℓ∞ error guarantee under explicit sample-size scalings.

  • Model conditions: The required deviation bounds hold for sub-Gaussian X, W, and ε under the stated general corrupted-linear-model setup.The proposition is formulated to indicate applicability to other corrupted linear models.
  • Concentration bounds: Under n ≿ k·max{k, log p}, the concentration bounds hold with probability at least 1−c exp(−c′ min{k, log p}).These bounds feed into the strict-dual-feasibility verification.
  • Strict dual feasibility: The bounds in (68) and (69) imply strict dual feasibility through Propositions 3 and 4, so the primal-dual witness technique succeeds.This connects the model-specific concentration analysis to the general proof framework.
  • Estimator error: Proposition 5 supplies the additional bound needed to control the estimator error.The proof then plugs inequality (77) into Theorem 2's inequality (18).

D.3 Proof of Corollary 3

The proof of Corollary 3 establishes the needed concentration and restricted strong convexity properties for the generalized loss using bounded curvature and sub-Gaussian covariates. These ingredients yield the desired strict dual feasibility and estimator guarantee through Theorem 2.

  • Restricted strong convexity: The restricted strong convexity condition holds with high probability when ψ′′ is bounded and the covariates are sub-Gaussian.The proof invokes a prior corollary establishing this condition for the generalized loss.
  • Hessian concentration: The Hessian analysis treats the relevant terms as averages of products of sub-Gaussian variables with uniformly bounded ψ′′.A discretization argument over the k-dimensional unit sphere then controls the resulting operator behavior.
  • Concentration bounds: The concentration bounds hold with probability at least 1−c exp(−c′ min{k, log p}) for the quantities needed in the proof.These bounds are combined with the Hessian and gradient controls.
  • Strict dual feasibility: The proof combines the resulting bounds to control the terms in the strict-dual-feasibility conditions.The argument uses the mean value theorem, triangle inequalities, and perturbation terms involving the Hessian.
  • Final guarantee: Theorem 2 then yields the desired result after the strict-dual-feasibility bounds are established.The proof explicitly concludes by invoking Theorem 2.

D.4 Proof of Corollary 4

The proof constructs a primal-dual witness for the graphical Lasso and uses fixed-point and convexity arguments to establish the desired estimator properties. Restricted strong convexity, matrix perturbation bounds, and strict convexity together yield a unique global optimum.

  • Construction: A modified primal-dual witness construction produces a restricted zero-subgradient point for the graphical Lasso program.The construction adapts the standard framework while preserving support constraints.
  • Optimality: Strict convexity of the objective over the feasible set makes any zero-subgradient point the unique global minimum.For the graphical Lasso, the Hessian is (Θ⊗Θ)^−1, and the component terms are shown to be convex.
  • Fixed-point argument: The map F preserves an ℓ∞-ball when dr < λmin(Θ∗), so Brouwer’s theorem supplies a fixed point.The invertibility of Θ∗+∆ ensures continuity of F before applying the fixed-point argument.
  • Bounds: The proof combines sub-Gaussian concentration, matrix expansions, norm inequalities, and the scaling n ≿ d^2 log p to verify the required bounds.These estimates establish the conditions needed for the primal-dual witness argument.
  • Conclusion: The resulting estimator is concluded to be the unique global optimum with the desired properties.The final conclusion invokes the established theorem after verifying the construction and feasibility conditions.

E.2 Proof of Corollary 5

The proof of Corollary 5 derives the claimed result under a sample-size condition and analyzes the associated incoherence and spectral properties. The argument uses explicit bounds for the relevant matrix quantities.

  • Statistical bound: Under the scaling n ≿ k^2 log p, the desired result follows from the preceding statistical-consistency bound.The proof transfers the bound under the stated sample-size regime.
  • Matrix properties: The incoherence parameter is computed directly, while the spectral analysis bounds the quadratic form vTΓv.The extremal expression is maximized at α = 1, with equality attained by a specified vector.
  • Spectral bounds: The lower-eigenvalue bound is obtained by an analogous argument with equality for a specified coordinate configuration.The proof identifies the equality case for the lower spectral bound.

F Some useful auxiliary results

The auxiliary results define stationarity and establish conditions ensuring isolated local minima, while collecting matrix and regularizer lemmas used throughout the proofs. These tools support both nonconvex optimization arguments and graphical-model analysis.

  • Regularizer tools: The regularizer analysis uses concavity and differentiability properties of its component functions.These properties support the auxiliary inequalities required by the optimization proofs.
  • Stationarity: A stationary point satisfies a variational inequality involving the gradient of the loss and regularizer over the feasible region.The definition accommodates possible nondifferentiability of the regularizer at zero.
  • Stationarity: Under restricted strong convexity, amenability, and suitable sample-size scaling, stationary points satisfy the auxiliary lemma’s guarantees.The key regularizer condition is µ < 2α1.
  • Local minima: A second-order condition for a composite objective establishes that a feasible point is an isolated local minimum.The proof extends prior arguments to objectives containing a nonsmooth composite component.
  • Local minima: The local-minimum proof analyzes convergent feasible directions and uses Taylor expansion to rule out nearby points with no larger objective value.Accumulation directions are shown to satisfy the relevant criticality conditions.
  • Matrix tools: Matrix lemmas provide perturbation bounds and Kronecker-product norm identities used in the graphical Lasso analysis.The collection includes bounds for A⊗A−B⊗B and the infinity norm of A⊗B.
Loading 1412.5632v1…