PaperlayerView exact revision on arXiv

Source-linked AI summary

A unified approach to model selection and sparse recovery using regularized least squares

Jinchi Lv, Yingying Fan

arXiv:0905.3573v2math.ST

TL;DR

High-dimensional model selection and sparse recovery face computational, collinearity, and sparsity challenges, while L1 regularization does not always identify the true sparse model. This paper studies both problems through regularized least squares with concave penalties, obtaining weak-oracle model-selection guarantees and a sufficient sparse-recovery condition linked to a smooth L0–L1 penalty family.

  • Problem

    High-dimensional model selection and sparse recovery are difficult because collinearity and computational costs increase with dimensionality, while L1 regularization is not always an oracle for the true sparse model.

  • Method

    The paper uses a unified regularized least squares framework with concave penalties, including a family that provides a smooth homotopy between L0 and L1 penalties.

  • Results

    The regularized least squares estimator has a nonasymptotic weak oracle property with dimensionality potentially exponential in sample size, while concave penalties admit a sufficient condition for ρ/L0 equivalence.

  • Takeaways & Limitations

    The unified concave-penalty framework supports theoretical treatment of both model selection and sparse recovery across penalties connecting L0 and L1.

  • Takeaways & Limitations

    Extending the results beyond regularized least squares to generalized linear models and more general models or loss functions remains outside the paper’s scope.

Abstract

from arXiv · show

Model selection and sparse recovery are two important problems for which many regularization methods have been proposed. We study the properties of regularization methods in both problems under the unified framework of regularized least squares with concave penalties. For model selection, we establish conditions under which a regularized least squares estimator enjoys a nonasymptotic property, called the weak oracle property, where the dimensionality can grow exponentially with sample size. For sparse recovery, we present a sufficient condition that ensures the recoverability of the sparsest solution. In particular, we approach both problems by considering a family of penalties that give a smooth homotopy between $L_0$ and $L_1$ penalties. We also propose the sequentially and iteratively reweighted squares (SIRS) algorithm for sparse recovery. Numerical studies support our theoretical results and demonstrate the advantage of our new methods for model selection and sparse recovery.

1. Introduction.

Model selection and sparse recovery are related high-dimensional problems where sparsity helps isolate informative variables, but noise, collinearity, and computational cost make recovery difficult. The paper unifies their analysis through regularized least squares with concave penalties and establishes results for increasingly high dimensions.

  • Sparsity is used because large-scale data are often assumed to contain a small informative fraction amid substantial noise.
  • Model selection locates predictors with nonzero true coefficients, while sparse recovery seeks the minimum L0 solution to a linear equation.
  • Direct L0 optimization is combinatorial, motivating continuous penalty methods such as L1-based basis pursuit for sparse recovery.
  • Noise makes recovering the true model more challenging than recovering the sparsest solution, even though the problems are interrelated.
  • The paper develops a weak oracle property for regularized least squares when dimensionality p can be of exponential order in sample size n.
  • Both problems are studied using concave penalties, including a family providing a smooth homotopy between L0 and L1 penalties.

2. Regularization methods with concave penalties.

The paper examines concave penalties within regularized least squares, emphasizing their trade-offs among sparsity, unbiasedness, continuity, curvature, and computational tractability. Its SICA family smoothly connects L0 and L1 penalties while retaining useful penalty properties under stated conditions.

  • The L0 penalty targets sparsest recovery but is discontinuous and computationally unattractive, whereas L2 is tractable but generally produces nonsparse solutions.
  • Condition 1 requires the penalty to be increasing and concave, with a continuous derivative and specified behavior of its derivative with respect to λ.
  • Concavity supports unbiasedness and sparsity when the derivative decreases to zero, but continuity does not generally hold for every penalty in this class.
  • SCAD and MCP satisfy Condition 1 and simultaneously provide unbiasedness, sparsity, and continuity, while L1 lacks unbiasedness because its derivative is identically one.
  • For twice-differentiable penalties, maximum concavity equals the supremum of negative second derivatives, while local concavity is determined by the largest coordinatewise curvature.
  • The SICA family satisfies lim a→0+ ρa(t) = I(t ≠ 0) and ρ∞(t) = t, creating a smooth homotopy from L0 to L1.
  • For finite a, SICA penalties have derivatives tending to zero and therefore provide unbiasedness and sparsity; continuity additionally requires a ≥ a0.
  • The parameter a controls SICA maximum concavity, decreasing from infinity toward zero as the family moves from L0 toward L1.

3. Sparse recovery.

The paper studies sparse recovery through regularized least squares, contrasting computationally tractable penalties with the sparsest L0 solution. It derives sufficient local-recovery conditions and characterizes penalties that balance recoverability with concavity.

  • Sparse recovery problem: Sparse recovery seeks the minimum-L0 solution, but direct L0 optimization is combinatorial and impractical in high dimensions.The L2 penalty is tractable but generally yields nonsparse solutions, motivating continuous approximations such as L1 and concave penalties.
  • Unified analysis: The analysis constructs solutions to the regularization problem by studying regularized least squares and letting λ → 0+.This connects finite-λ optimization to sparse-recovery solutions while accommodating nonconvex penalties through local-minimizer analysis.
  • Recovery condition: Theorem 2 gives a sufficient condition under which the true sparse vector β0 is a local minimizer of the ρ-regularization problem.The condition assumes finite maximum concavity and nonsingularity of the Gram matrix on the true support.
  • Penalty choice: For the penalty family ρa, smaller a makes the recovery condition less restrictive, providing flexibility beyond the L1 penalty.The paper also identifies an optimal a that minimizes maximum concavity among theoretically recoverable penalties.
  • Penalty choice: Any ρa with a ∈ (0,aopt(ε)) makes β0 a local minimizer, while aopt depends on the signal strength, predictor correlation, and support size.When |r| ≤ s^-1/2, the theory gives aopt(ε) = ∞, making L1 optimal in that regime.

4. Model selection.

For model selection, the paper analyzes concave-penalized regularized least squares under growing dimensionality. It establishes a weak oracle property and explains how the penalty parameter controls statistical performance and computational difficulty.

  • Model-selection challenge: Model selection must recover the true sparse model despite predictor collinearity and computational costs that increase with dimensionality.Classical best subset selection becomes impractical in high-dimensional settings.
  • Weak oracle property: Theorem 4 establishes a weak oracle property combining sparsity with consistency under L∞ loss for a regularized least squares estimator.The property is explicitly weaker than the oracle property of Fan and Li (2001).
  • Weak oracle property: The dimensionality p may grow exponentially with the diverging sequence un, while the sequence also controls the exponential probability bound.When κ0 is small, the paper allows un = o(n^γ), implying log p = o(n^(2γ)).
  • Penalty effects: Concave penalties can reduce estimation bias relative to L1 because ρ′(c0b0)/ρ′(0+) may be much smaller than one.For L1, this ratio equals one; for other concave penalties, it can be smaller.
  • Penalty effects: For ρa, decreasing a improves the theoretical estimation-loss bound but increases maximum concavity and may increase computational difficulty.The paper suggests choosing a adaptively from data, for example by cross-validation.

5. Implementation.

The paper implements concave-penalty regularization with SIRS for sparse recovery and LLA for model selection. SIRS uses iteratively reweighted quadratic problems, with fixed-point results and complexity comparable to LARS.

  • 5.1. SIRS algorithm for sparse recovery.: SIRS solves the ρa-regularization problem for sparse recovery through sequentially and iteratively reweighted squares.Each iteration uses a weighted L2 penalty, with sequential initialization designed to find sufficiently sparse solutions.
  • 5.1. SIRS algorithm for sparse recovery.: For each iterate, SIRS solves a weighted L2 regularization problem whose penalty agrees locally with the concave penalty ρa.The weighted quadratic is constructed from the current iterate and matches ρa at that point.
  • 5.1.1. Justification.: Any convergent SIRS sequence reaches a fixed point, and under spark and sparsity conditions every fixed point is either β0 or denser than (n + 1)/2.The condition is p > n, spark(X) = n + 1, and ∥β0∥0 < (n + 1)/2.
  • 5.1.2. Computational complexity.: SIRS has complexity O(np(n∧p)LM), matching LARS for the main step when the iteration and sequential-step counts are fixed.The main step has complexity O(np(n∧p)); L and M denote the numbers of iterations and sequential steps.
  • 5.2. LLA algorithm for model selection.: LLA solves the ρa-regularized least-squares problem for model selection using local linear approximations and weighted lasso subproblems.The parameter a is tuned by grid search.

6. Numerical examples.

Numerical studies evaluate ρa penalties for sparse recovery and model selection across simulated and real-data settings. Finite-a ρa with optimal SICA outperformed L1 in sparse recovery, while the model-selection experiments compared prediction error and selected-model size across several methods.

  • 6.1. Simulation 1.: 100 datasets with (s,n,p) = (7,35,1000) tested sparse recovery under correlations r = 0, 0.2 and 0.5.Design columns were rescaled to unit L2 norm after sampling from correlated Gaussian designs.
  • 6.1. Simulation 1.: Finite-a ρa with optimal SICA significantly outperformed L1, while performance approached L1 as a increased.Success percentage first increased and then decreased as a approached zero, suggesting greater computational difficulty for very small a.
  • 6.2. Simulation 2.: Model-selection simulations used 100 datasets with (n,p) = (100,50), two noise levels, and comparisons among SICA, lasso, SCAD and MCP.Prediction error, selected-variable count (#S), and missed-variable count (FN) were used; all four methods had median FN = 0.
  • 6.2. Simulation 2.: Figure 3 displays PE and #S boxplots over 100 Simulation 2 runs, with methods on the x-axis and PE above #S.The design has p = 50 and Gaussian rows with covariance Σ0.
  • 6.3. Simulation 3.: When (n,p) = (100,600), five-fold cross-validation replaced BIC because p exceeded n, and all four methods had median FN = 0.Table 3 and Figure 4 summarize PE and #S, with lasso boxplots truncated for visibility.
  • 6.4. Real data analysis.: On the diabetes data, lasso selected 9 variables, whereas SCAD, MCP and SICA selected the same 6 variables; all excluded hdl.The dataset contained 442 patients and 10 baseline variables.

7. Proofs.

The proofs establish local-minimizer results for concave-penalized regularized least squares and connect these results to sparse recovery through the limit λ → 0+.

  • Proof strategy: The singular-value decomposition reduces the constraint y = Xβ to an equivalent transformed system involving D and Vβ.Orthogonality preserves the Euclidean norm, supporting the characterization of solutions under rank-deficient designs.
  • Local minimizers: Strict inequalities and concavity are used to show that a candidate estimator is a strict local minimizer of the regularized least-squares objective.The proof compares points outside a neighborhood with their projections and uses decreasing ρ′ to establish a strict objective increase.
  • Sparse recovery: For noiseless sparse recovery, a sequence of strict local minimizers converges to β0, which is then shown to be a local minimizer of the constrained problem.The construction uses regularized least squares with y = Xβ0 and lets λ approach zero from above.
  • Model selection: The model-selection proof constructs a solution near β0 under events controlling the noise correlations and bounds its sup-norm error.Gaussian tail bounds and a continuity argument are used to establish existence within a neighborhood of the true active coefficients.
  • Sparse recovery: The sparse-recovery uniqueness argument uses spark(X): any distinct solution with support size at most (n + 1)/2 would contradict the definition of spark.The difference between two solutions lies in the null space while having support smaller than spark(X).

8. Discussion.

The paper provides regularity conditions for a nonasymptotic weak oracle property with exponentially growing dimensionality and generalizes earlier concave-penalty results in regularized least squares.

  • Discussion: Regularized least-squares estimators satisfy a nonasymptotic weak oracle property under stated regularity conditions, even when dimensionality is of exponential order.The result concerns model selection in the unified concave-penalty framework.
  • Discussion: The paper generalizes results of Fan and Li (2001) and Fan and Peng (2004) to regularized least squares for a broader triple (s,n,p).The extension is formulated for concave penalties.
  • Discussion: Extending the analysis to generalized linear models and more general models and loss functions is identified as future research.These settings are explicitly outside the paper’s scope.
Loading 0905.3573v2…