Source-linked AI summary
One-step sparse estimates in nonconcave penalized likelihood models
Hui Zou, Runze Li
TL;DR
Nonconcave penalized likelihood offers promising theoretical properties but is difficult to maximize because its objective is nondifferentiable and nonconvex. The paper develops an LLA-based algorithm and recommends its one-step estimator, which naturally produces sparse estimates and shows competitive finite-sample performance.
Problem
Maximizing nonconcave penalized likelihood is computationally challenging because the objective is nondifferentiable and nonconvex.
Method
The paper develops an iterative local linear approximation algorithm, framed as an MM procedure, and proposes its one-step estimator for sparse estimation.
Results
One-step sparse estimates naturally produce sparse representations, enjoy oracle properties under suitable initial estimators, and show very competitive finite-sample performance.
Takeaways & Limitations
The one-step LLA estimator can serve as a model selector while reducing the computational cost of fully iterative methods.
Takeaways & Limitations
The LQA approach requires prespecified numerical thresholds or perturbation sizes that can affect sparsity and convergence speed.
Abstract
from arXiv · showhide
Fan and Li propose a family of variable selection methods via penalized likelihood using concave penalty functions. The nonconcave penalized likelihood estimators enjoy the oracle properties, but maximizing the penalized likelihood function is computationally challenging, because the objective function is nondifferentiable and nonconcave. In this article, we propose a new unified algorithm based on the local linear approximation (LLA) for maximizing the penalized likelihood for a broad class of concave penalty functions. Convergence and other theoretical properties of the LLA algorithm are established. A distinguished feature of the LLA algorithm is that at each LLA step, the LLA estimator can naturally adopt a sparse representation. Thus, we suggest using the one-step LLA estimator from the LLA algorithm as the final estimates. Statistically, we show that if the regularization parameter is appropriately chosen, the one-step LLA estimates enjoy the oracle properties with good initial estimators. Computationally, the one-step LLA estimation methods dramatically reduce the computational cost in maximizing the nonconcave penalized likelihood. We conduct some Monte Carlo simulation to assess the finite sample performance of the one-step sparse estimation methods. The results are very encouraging.
1. Introduction.
High-dimensional variable selection is computationally difficult with subset methods and challenging for nonconcave penalized likelihood because the objective is nondifferentiable and nonconvex. The paper develops LLA-based one-step sparse estimates that address these computational and sparsity concerns.
- Motivation: Best subset selection becomes infeasible for high-dimensional data because of its computational cost and also lacks stability.LASSO offers continuous shrinkage, while nonconcave penalized likelihood methods target significant-variable selection.
- Problem: Nonconcave penalized likelihood has promising theoretical properties, but its singularity and nonconvexity make numerical maximization difficult.The existing LQA approach uses a modified Newton–Raphson algorithm but can permanently delete covariates during iteration.
- Problem: One-step LQA cannot produce a sparse representation, losing a central property of nonconcave penalized likelihood estimators.This limitation prevents one-step LQA from directly serving as a sparse variable-selection estimator.
- Contribution: The proposed LLA algorithm avoids coefficient deletion and perturbation-size selection, is an MM algorithm with an ascent-based convergence argument, and naturally produces sparse estimates.The paper proposes the one-step LLA estimator as the final estimate to reduce computation and address potential local maxima.
2. Local linear approximation algorithm.
The section formulates penalized likelihood variable selection and develops LQA and LLA algorithms for optimizing its nondifferentiable, nonconcave objective. LLA provides a convex MM update with natural sparsity, ascent and convergence properties, while avoiding key LQA tuning and deletion issues.
- Penalized likelihood: Penalized likelihood assumes some coefficients are zero and seeks to identify and estimate the corresponding subset model.
- Penalized likelihood: Concave penalties make the objective nondifferentiable at the origin and nonconcave, creating difficulties for direct maximization.The section discusses L0.5 and SCAD penalties as examples.
- Local quadratic approximation: LQA uses quadratic penalty approximations with modified Newton–Raphson optimization, but small coefficients may be deleted and the threshold ε0 affects sparsity and convergence.Deleting a covariate at any iteration excludes it from the final model, making ε0 an additional tuning parameter.
- Local linear approximation: LLA replaces the penalty with a local linear approximation, producing a convex optimization update without deleting small coefficients or selecting a perturbation size.The LLA update is numerically stable and naturally yields sparse estimates that can be computed using efficient algorithms such as LARS.
- Local linear approximation: LLA is an MM algorithm whose surrogate minorizes the penalized likelihood and has an ascent property under the stated concavity conditions.The LLA approximation is described as the best convex majorization of the penalty function.
- Convergence: If the LLA sequence has a limit point and equality under the update occurs only at stationary points, that limit point is stationary for the objective.Continuity of the update map follows from the penalty's continuous first derivative and convexity of each update problem.
3. One-step sparse estimates.
The one-step LLA estimator provides sparse model selection while retaining oracle properties under stated regularity and tuning conditions. Its continuity extends one-step estimation to Bridge penalties and relates estimators from penalties with similar derivatives.
- One-step sparse estimates: The one-step LLA estimator automatically adopts a sparse representation and can therefore be used as a model selector.Unlike one-step or k-step LQA, LLA can produce exact zero coefficients.
- One-step sparse estimates: With reasonably good initial estimators, the one-step method is described as empirically and theoretically as efficient as the fully iterative method.
- Linear regression models: The one-step estimator enjoys sparsity and asymptotic normality under two regularity conditions, with tuning requirements specified for penalties whose derivatives may diverge near zero.The conditions include independent errors and convergence of n^-1X^TX to a positive definite matrix.
- Penalized likelihood: In general likelihood models, the one-step estimator is identified with the desired one-step estimate, and the oracle results require less regularity than the corresponding Fan–Li theorem.The penalty function need not be twice differentiable, and normality is not required in Theorem 4.
- Continuity of the one-step estimator: Bridge penalties with 0 < q < 1 can yield continuous one-step estimates under weaker continuity requirements on the positive-argument penalty derivative.This contrasts with the continuity condition imposed directly on the original nonconcave penalized-likelihood estimates.
- Continuity of the one-step estimator: In orthogonal designs, one-step L0.01 and logarithm estimators produce continuous thresholding rules, while the corresponding original penalties yield discontinuous rules.The one-step L0.01 estimator with λ = 200 is very similar to the one-step logarithm estimator with λ = 2; SCAD versions are continuous and unbiased for large coefficients but differ.
4. Implementation.
The implementation reduces one-step estimation to efficient LASSO-related computations using LARS. Type 1 penalties permit efficient entire solution profiles, whereas SCAD requires solving separately for each fixed regularization parameter.
- Implementation: The one-step estimator can be computed efficiently because solving β(1) is closely related to solving LASSO.Standard quadratic programming, shooting, and LARS path algorithms are identified as applicable computational tools.
- Implementation: The implementation adopts the LARS idea, whose computation in both algorithms has the same order as a single OLS fit.This makes the one-step estimator very efficient to compute.
- Type 1 penalties: For Type 1 penalties, including Bridge and logarithm penalties, the entire one-step estimator profile as a function of λ can be efficiently constructed.Type 1 penalties have the form pλ(t) = λp(t) with p′(t) > 0 for all t.
- Type 1 penalties: The Type 1 implementation creates working data and applies LARS to solve the resulting optimization problem.
- Type 1 penalties: A nonzero coefficient in the computed solution corresponds to selecting its associated covariate in the final model.
- SCAD-type penalties: The SCAD implementation computes β(1) through a separate algorithm using working data, projection operations, and LARS.
- SCAD-type penalties: For SCAD-type penalties, the sets of variables can change with λ, so the one-step estimator must still be solved separately for each fixed λ.SCAD is an example where the derivative can be zero and λ cannot be separated from the penalty function.
5. Numerical examples.
The numerical studies evaluate one-step sparse estimates across linear, logistic, and Poisson regression, comparing model error, sparsity, fit selection, and computational cost. Across examples, one-step methods show competitive finite-sample performance, with especially strong results for one-step SCAD.
- Linear regression: In linear regression, one-step SCAD has the smallest model error and the highest probability of correct fit among the compared procedures.One-step LOG and one-step L0.01 perform very similarly, while concave-penalty methods outperform best subset selection in model error.
- Overall findings: The one-step sparse estimates perform very well in the simulations because of their oracle properties.
- Logistic regression: In logistic regression, best-subset BIC has the best model error, but one-step sparse estimates require the least computational cost.One-step SCAD matches fully iterative SCAD estimates in model error; one-step logarithm and L0.01 penalties have lower model error and under-fit rates than one-step SCAD.
- Poisson regression: In Poisson regression, one-step SCAD outperforms LQA- and perturbed-LQA-based SCAD in model error, model complexity, and correct-fit rate.Best subset selection has the highest correct-fit rate, while one-step sparse estimates improve their correct-fit rate as sample size increases from 60 to 120.
- Data analysis: In the burns-data analysis, one-step SCAD selects age and log(burn area + 1), matching the model selected by SCAD with the LQA algorithm.The logarithm penalty selects more variables, consistent with its higher over-fit rate than one-step SCAD; the one-step L0.01 fit is almost identical to the logarithm-penalty fit.
6. Proofs.
The proofs establish the theoretical properties of the one-step estimator through asymptotic convergence arguments and probability bounds for zero coefficients. The argument combines normal-limit behavior for stochastic terms with diverging penalty contributions to prove sparsity-related results.
- Proof strategy: The proof uses convexity and limiting arguments to establish inequalities underlying the LLA algorithm's theoretical properties.Several steps derive equivalent formulations and complete the required inequality arguments.
- Algorithmic connection: The LLA algorithm is identical to the EM algorithm when the relevant objective representations are equivalent.
- Penalty properties: The proof also verifies that the penalty function is strictly increasing and unbounded under the stated construction.
- Selection consistency: For zero true coefficients, the proof shows that the one-step estimator is zero with probability tending to one.This stronger sparsity statement is obtained by proving P(β̂_j(ose) ≠ 0) → 0 when β0j = 0.
- Asymptotic argument: The stochastic terms converge in distribution to normal limits, while the penalty contribution diverges for nonzero local perturbations of zero coefficients.These contrasting limits support the probability bound used to establish selection consistency.
7. Discussion.
The discussion presents the one-step LLA estimator as a sparse, oracle-property-preserving alternative to fully iterative optimization. It reports competitive finite-sample performance, reduced computational cost, and extensions beyond the models studied.
- Main conclusions: The one-step LLA estimator naturally adopts a sparse representation, enjoys oracle properties, and can dramatically reduce computational cost relative to fully iterative methods.
- Finite-sample performance: Simulation results show that one-step sparse estimates have very competitive finite-sample performance.
- Scope and extensions: The method is concentrated on linear and likelihood-based models, including generalized linear models, and can be extended to survival, longitudinal, and semiparametric regression.