PaperlayerView exact revision on arXiv

Source-linked AI summary

Thresholding-based Iterative Selection Procedures for Model Selection and Shrinkage

Yiyuan She

arXiv:0812.5061v2math.ST

TL;DR

The paper addresses the difficulty of using nonconvex penalties for model selection and shrinkage with nonorthogonal regression matrices. It develops thresholding-based iterative selection procedures that transfer orthogonal-design ideas to general designs and studies their convergence and nonasymptotic properties. Hybrid-TISP combines hard- and ridge-thresholding and reports superior test-error and sparsity performance, subject to stated regularity and penalty-form limitations.

  • Problem

    Nonconvex penalties can improve sparsity and accuracy, but their theory and computation are difficult for nonorthogonal regression matrices.

  • Method

    TISP starts from thresholding rules, uses an orthogonal-design mechanism for general penalized regression, and includes Hybrid-TISP’s hard- and ridge-thresholding fusion.

  • Results

    Hybrid-TISP shows superior performance in test-error and sparsity, while TISP converges with a nonincreasing objective when X is scaled down properly.

  • Takeaways & Limitations

    Thresholding-based procedures provide a simple computational and analytical route to nonconvex model selection and shrinkage for general design matrices.

  • Takeaways & Limitations

    The analysis assumes P depends only on β and λ, excluding iterative weighting with β-dependent penalties; some sparsity results also require a regularity condition.

Abstract

from arXiv · show

This paper discusses a class of thresholding-based iterative selection procedures (TISP) for model selection and shrinkage. People have long before noticed the weakness of the convex $l_1$-constraint (or the soft-thresholding) in wavelets and have designed many different forms of nonconvex penalties to increase model sparsity and accuracy. But for a nonorthogonal regression matrix, there is great difficulty in both investigating the performance in theory and solving the problem in computation. TISP provides a simple and efficient way to tackle this so that we successfully borrow the rich results in the orthogonal design to solve the nonconvex penalized regression for a general design matrix. Our starting point is, however, thresholding rules rather than penalty functions. Indeed, there is a universal connection between them. But a drawback of the latter is its non-unique form, and our approach greatly facilitates the computation and the analysis. In fact, we are able to build the convergence theorem and explore theoretical properties of the selection and estimation via TISP nonasymptotically. More importantly, a novel Hybrid-TISP is proposed based on hard-thresholding and ridge-thresholding. It provides a fusion between the $l_0$-penalty and the $l_2$-penalty, and adaptively achieves the right balance between shrinkage and selection in statistical modeling. In practice, Hybrid-TISP shows superior performance in test-error and is parsimonious.

1. Introduction

The paper targets model selection and shrinkage beyond the lasso by using nonconvex penalties, while addressing the difficulty of applying them to general regression matrices.

  • Lasso offers efficient, continuous variable selection and stable sparse solutions, but its shrinkage and thresholding are less direct for general regression matrices.
  • The paper positions its approach within extensive lasso algorithms, theory, and extensions such as grouped, Dantzig, adaptive, and relaxed lasso.
  • The authors use nonconvex penalties to improve model selection and shrinkage beyond the naïve l1-penalty.

2. Motivation – From Orthogonal Designs to Non-orthogonal Designs

The motivation is to address lasso limitations and transfer flexible nonconvex thresholding ideas from orthogonal designs to general penalized regression. The paper formulates this transfer through an iterative procedure that remains computationally tractable.

  • The penalized regression models sparse coefficients β using a regression matrix X, response y, and penalty P(β; λ), including settings where p exceeds n.
  • Lasso is computationally efficient but can mishandle collinearity, produce inconsistent selection, and introduce estimation bias.
  • Orthogonal designs support established theories and algorithms for many nonconvex penalties, unlike the more difficult general-design setting.
  • Hard-penalties include the l0-penalty and other nonconvex forms, illustrating alternatives to the l1 penalty in orthogonal settings.
  • Different penalty functions can produce the same estimator and thresholding, motivating thresholding rules as the paper’s starting point.
  • The proposed mechanism replaces the original problem with an orthogonal, separable optimization that can incorporate flexible nonconvex penalties.

3. Thresholding-based Iterative Selection Procedures (TISP)

TISP starts from thresholding rules, connects them to penalty functions, and iteratively solves penalized regressions for general design matrices. The procedure supports convergence and optimality results while accommodating soft, hard, SCAD, and ridge-related thresholding choices.

  • Thresholding Rules and Penalties: Thresholding rules provide a computationally convenient starting point because multiple penalties can yield the same estimator and thresholding.The paper also establishes a universal connection between thresholding rules and penalty functions.
  • Thresholding Rules and Penalties: A thresholding rule is odd, nondecreasing on nonnegative inputs, shrinking, and diverges as its input grows.It may additionally set outputs to zero below a threshold τ.
  • Thresholding Rules and Penalties: Every continuous thresholding rule in the construction corresponds to the unique optimizer of a univariate penalized quadratic problem.The constructed penalty is continuous and positive.
  • TISP Construction: TISP updates coefficients by applying Θ to (I −Σ)β + X^T y and avoids matrix inversion or other complicated operations.Soft, hard, SCAD, and ridge-related thresholding choices fit within the framework.
  • Convergence: For nonsingular Σ, the TISP mapping is a contraction and the sequence converges to a stationary point; large-p settings require additional analysis because the mapping may not be nonexpansive.Hard-thresholding is explicitly noted as non-nonexpansive, unlike the contraction case.
  • Convergence and Optimality: Under stated spectral conditions, TISP limit points are stationary, and fixed points can be global minimizers when the design is sufficiently close to orthogonal.For SCAD, the paper gives a sufficient range including 0.61 ≤µ(X) ≤1.27 when a = 3.7.
  • Θ-Estimators: The paper defines Θ-estimators through the Θ-equation and associates them with penalized regressions whose penalties can be constructed from thresholding functions.With suitable Θ, the resulting estimator is intended to combine accuracy and sparsity.
  • Connections: TISP also connects thresholding-based estimators with robust M-estimation through the relation Θ(t; λ) + ψ(t; λ) = t.The paper contrasts Soft-TISP’s convex penalty with redescending ψ-functions associated with nonconvex penalties.

4. Selection and Estimation via TISP

TISP provides nonasymptotic selection and estimation guarantees for thresholding rules, including sign recovery, risk bounds, and stronger sparsity results for hard-thresholding-like procedures.

  • Theoretical framework: TISP offers a nonasymptotic framework for variable selection and coefficient estimation based on different thresholding rules.The analysis studies fixed points of the iterative procedures under thresholding-based assumptions.
  • Assumptions on Θ: The thresholding value τ(λ) separates zero from nonzero thresholding outputs and supports the sign-recovery analysis.For soft-, hard-, and SCAD-thresholdings, τ(λ)=λ.
  • Sparsity recovery: A small mean correlation κ between relevant and irrelevant predictors helps TISP recover the sparsity pattern correctly.The paper identifies κ as measuring mean correlations between relevant and irrelevant predictors.
  • Sparsity recovery: Under fixed signal and sparsity dimensions, sign consistency follows when τ/√n→0; with growing dz, n need only grow faster than log dz under additional regularity conditions.The latter result also assumes β_nz and d_nz are fixed and μ≥(1+ε)κd_nz.
  • Sparsity recovery: The regularity condition μ≥κd_nz cannot generally be removed, although hard-thresholding-like rules avoid it and obtain stronger results.For hard- and SCAD-thresholding, large nonzero components are not biased, and the resulting variable-selection bound can be better than the general bound.
  • Estimation risk: The nonasymptotic risk result covers soft-, hard-, and SCAD-thresholdings, agrees with classical soft-thresholding results, and is sharper than earlier bounds.In the orthogonal case, the paper also establishes oracle inequalities, while the general bound is described as essentially unimprovable in general.

5. TISP Designs: An Empirical Study

The empirical study compares TISP variants and related methods across simulation settings, emphasizing test error, sparsity, and the Hybrid-TISP trade-off between selection and shrinkage.

  • Simulation design: The simulations compare lasso, one-step SCAD, Hard-TISP, SCAD-TISP, elastic net, and Hybrid-TISP using test error, sparsity error, proper sparsity, and proper nonsparsity.Results are summarized as 40% trimmed means over 50 simulations.
  • Simulation results: Hard-TISP and SCAD-TISP are more parsimonious than lasso and outperform it in test error and sparsity error in the reported simulations.The authors attribute this to directly tackling the original nonconvex penalized regressions rather than using a convex approximation.
  • Simulation results: When noise is very high, Soft-TISP can produce more accurate estimates because shrinking nonzero coefficients may reduce predictive test error.Hard-thresholding methods perform better when signal-to-noise ratios are more favorable, but can be less effective under very high noise.
  • Hybrid-TISP design: Hybrid-TISP combines a continuous hard-penalty component with a ridge-like component, and its nonzero estimates result from partial ridge regression.Its tuning parameters separately regulate selection and shrinkage through the hybrid thresholding construction.
  • Hybrid-TISP design: Hybrid-TISP offers a trade-off between l0-like selection and l2-like shrinkage while avoiding overlapping shrinkage of zero and nonzero coefficients.Hard-thresholding handles zeros, whereas ridge-thresholding handles nonzeros.
  • Large-scale experiments: In both large-sample and large-dimension simulations, the Hybrid-TISP path is preferred for accuracy and sparsity.The experiments vary n and d across settings up to d = 500 and n = 200.

6. Real Data

The paper applies Hybrid-TISP to a prostate dataset with a full quadratic predictor model and uses resampling to assess variable-selection stability.

  • Data and model: The prostate dataset has 97 observations, 9 clinical measures, and 43 predictors formed from main effects, squares, and interactions.The response is log(cancer volume), and the model includes 8 main effects, 7 squares, and 28 interactions.
  • Evaluation: Hybrid-TISP regularization parameters are tuned by leave-one-out cross-validation, while bootstrap resampling evaluates coefficient-selection stability over 100 replications.Predictors are standardized before applying Hybrid-TISP with fixed parameters in each bootstrap sample.
  • Evaluation: Figure 3 reports the percentage of bootstrap coefficient estimates that are nonzero for all 43 predictors.This provides a variable-by-variable summary of selection frequency.

7. Discussion

The paper presents TISP as a computational and analytical framework for nonconvex penalized regression, with Hybrid-TISP combining selection and shrinkage. It reports strong empirical sparsity and test-error performance, while identifying assumptions and unresolved extensions.

  • TISP addresses the theoretical and computational difficulty of applying nonconvex penalties with nonorthogonal regression matrices.
  • Starting from thresholding rules rather than penalty functions avoids non-unique penalty representations and facilitates computation and analysis.
  • Hard-thresholding-family TISP procedures provide good variable-selection results in the paper’s experiments.
  • In the prostate example, eight variables had nonzero Hybrid-TISP estimates more often than zero across 100 bootstrap replications.
  • Hybrid-TISP fuses l0- and l2-based regularization and outperforms commonly used methods in test error and sparsity.
  • The framework assumes penalties depend only on β and λ, excludes penalties involving β from its analysis, and leaves GLM generalization for future work.
  • Nonconvex penalty solution paths are generally discontinuous in λ, making pathwise algorithms inappropriate for this setting.

A.1. Proofs of Theorem 3.1, Proposition 3.2, and Proposition 3.3

The appendix proves convergence-related properties by showing that TISP limits satisfy fixed-point relations under a spectral condition. The argument connects the iterative updates to the penalized objective through global inequalities.

  • The argument begins from a penalized regression formulation and relates its minimizer to the TISP fixed-point characterization.
  • The proof uses a global inequality that applies for every h and for A=(I−H)∨0.
  • The appendix derives the TISP update by recalling g and obtaining the relevant equations through direct calculation.
  • Under the condition μmax(Σ)<1∨(2−μmax(H)), a convergent TISP sequence has a limit that is a fixed point of TISP.
  • The proof of Proposition 3.3 uses γo(β*)=β* together with an inequality derived from the preceding bound.

A.2. Proofs of Theorem 4.1 and Theorem 4.2

The appendix establishes theoretical selection and estimation results for TISP using normalized-design assumptions, Gaussian bounds, and properties of the design submatrices. The proofs rely on lemmas controlling covariance structure and estimator equations.

  • The proof assumes column-normalized X and uses index-set submatrices of Σ=XT X in the theorem derivations.
  • Lemma A.1 supplies equations satisfied by the TISP estimate when Σnz is nonsingular.
  • Lemma A.2 compares Gaussian vectors with matching covariance diagonals, using Šidák’s classical result.
  • Gaussian tail bounds control events involving maxima, producing probability bounds such as [1−2Φ(−M)]^dz[1−2Φ(−L)]^dnz.
  • The remaining proof steps use scaling arguments and properties of the thresholding function to establish the stated theorems.

A.3. Proof of Theorem 4.3

The proof of Theorem 4.3 combines spectral properties, Gaussian calculations, and scaling arguments. It concludes by transferring the resulting bound to the theorem through a similar scaling step.

  • The proof introduces rz=∥β̂z∥2 as a quantity used in the theorem’s supporting calculations.
  • The proof analyzes the spectral decomposition of Σnz and bounds its eigenvalue-related quantities.
  • The argument uses the lower bound μmin(Sz)≥ν−κ2dzdnz/μ to control the relevant submatrix.
  • Gaussian-density and indicator calculations are used to bound the events appearing in the proof.
  • Theorem 4.3 follows after applying a similar scaling argument to the established bounds.

A.4. Proof of Theorem 4.4

The appendix proves nonasymptotic risk bounds for hard and soft thresholding by reducing the analysis to the univariate case and combining the resulting inequalities. It also notes why Stein’s lemma is inadequate for estimators close to hard thresholding.

  • Univariate reduction: The analysis reduces the estimation-risk calculation to scalar soft- and hard-thresholding rules with Gaussian noise.The scalar model is y = µ + ǫ with ǫ ∼ N(0,1), and the corresponding risks are denoted ρS(τ,µ) and ρH(τ,µ).
  • Hard-thresholding bounds: The proof establishes ρH(τ,µ) ≤ 1 + τ^2 for τ > 1 and ρH(τ,µ) ≤ ρH(τ,0) + 1.2µ^2.These bounds supply the hard-thresholding risk controls used later in the argument.
  • Proof strategy: The hard-thresholding inequalities are obtained by analyzing the risk derivative and directional derivatives of an auxiliary function g.The argument considers directions in the parameter plane and uses the explicit risk expression involving the normal density ϕ and distribution function Φ.
  • TISP risk bound: For τ > 1, combining the hard- and soft-thresholding bounds yields a univariate TISP risk bound through ρ(τ,µ) ≤ max(ρS(τ,µ), ρH(τ,µ)).The appendix then invokes this combined bound to conclude Theorem 4.4.
  • Technical caveat: The appendix cautions that Stein’s lemma does not handle oracle bounds well for estimators very close to hard thresholding because hard thresholding is not weakly differentiable.It contrasts this difficulty with an identified derivative error in a cited adaptive-lasso oracle bound.
Loading 0812.5061v2…