PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaled Sparse Linear Regression

Tingni Sun, Cun-Hui Zhang

arXiv:1104.4595v2stat.MLmath.ST

TL;DR

High-dimensional regression needs simultaneous estimation of coefficients and noise when the appropriate penalty depends on unknown noise. The paper studies an iterative scaled sparse-regression procedure, establishes oracle guarantees and noise-estimation theory, and reports favorable numerical comparisons with earlier joint convex minimization.

  • Problem

    The paper addresses simultaneous estimation of regression coefficients and noise level in high-dimensional linear models, where penalty calibration depends on the unknown noise level.

  • Method

    The method iteratively estimates noise from residuals and scales the sparse-regression penalty accordingly, with scaled lasso represented as convex joint penalized-loss minimization.

  • Results

    The scaled lasso satisfies oracle inequalities for prediction and estimation, while simulations show it outperforms penalized maximum likelihood and bias correction without post processing.

  • Takeaways & Limitations

    The theory provides sufficient conditions for consistency and asymptotic normality of the noise estimator, including some settings where variables outnumber observations.

  • Takeaways & Limitations

    Simulation examples show that consistently selecting a penalty level to remove noise-estimation bias is difficult.

Abstract

from arXiv · show

Scaled sparse linear regression jointly estimates the regression coefficients and noise level in a linear model. It chooses an equilibrium with a sparse regression method by iteratively estimating the noise level via the mean residual square and scaling the penalty in proportion to the estimated noise level. The iterative algorithm costs little beyond the computation of a path or grid of the sparse regression estimator for penalty levels above a proper threshold. For the scaled lasso, the algorithm is a gradient descent in a convex minimization of a penalized joint loss function for the regression coefficients and noise level. Under mild regularity conditions, we prove that the scaled lasso simultaneously yields an estimator for the noise level and an estimated coefficient vector satisfying certain oracle inequalities for prediction, the estimation of the noise level and the regression coefficients. These inequalities provide sufficient conditions for the consistency and asymptotic normality of the noise level estimator, including certain cases where the number of variables is of greater order than the sample size. Parallel results are provided for the least squares estimation after model selection by the scaled lasso. Numerical results demonstrate the superior performance of the proposed methods over an earlier proposal of joint convex minimization.

1. INTRODUCTION

The paper addresses simultaneous estimation of regression coefficients and noise level in high-dimensional linear models, where penalty choice must reflect the unknown noise level. It builds on iterative and joint-penalization approaches while targeting theoretical guarantees and practical performance.

  • High-dimensional linear regression requires estimating both regression coefficients and the noise level when the number of unknowns may exceed the number of observations.
  • Penalty levels proportional to the noise level are theoretically motivated, but cross-validation for selecting them is computationally costly and theoretically limited.
  • Earlier work proposed joint penalized likelihood, bias correction, and an iterative algorithm alternating noise estimation with penalty rescaling.
  • The paper studies the iterative algorithm, proving oracle inequalities for scaled lasso prediction and joint estimation, plus consistency and asymptotic normality for its noise estimator.
  • Numerical experiments compare scaled penalized methods and post-selection least squares with earlier joint convex minimization approaches.

2. AN ITERATIVE ALGORITHM

The algorithm alternates sparse regression with noise-level estimation, scaling the penalty by the estimated noise level. For the scaled lasso, this procedure corresponds to minimizing a jointly convex penalized loss and can be implemented using a solution path.

  • AN ITERATIVE ALGORITHM: The method chooses a penalty level proportional to the estimated noise level, with λ0 fixed independently of σ and a allowing degrees-of-freedom adjustment.
  • AN ITERATIVE ALGORITHM: For p < n and (a, λ0) = (p/n, 0), initialization with least squares gives the non-iterative estimate bσ2 = |y − Xbβ(lse)|2/(n − p).
  • AN ITERATIVE ALGORITHM: The implementation computes a sparse-regression solution path beginning at λ = |X′y/n|∞ and uses it to cover the relevant penalty range.
  • AN ITERATIVE ALGORITHM: For the scaled lasso, a = 0 and ρ(t) = t; concave penalties, including minimax concave penalty, yield related scaled methods.
  • AN ITERATIVE ALGORITHM: With the ℓ1 penalty, the joint penalized loss is convex and the alternating algorithm converges; the resulting coefficient and noise estimators are scale equivariant in y.
  • AN ITERATIVE ALGORITHM: The joint estimator may not be unique for some data, although the noise estimate is always unique and coefficient uniqueness holds under an almost-everywhere lasso condition.

Analysis of scaled lasso

The scaled lasso jointly estimates regression coefficients and noise using prediction-based oracle bounds, with assumptions that support consistency and asymptotic normality of the noise estimator. Its theory extends fixed-penalty lasso results and applies when p may exceed n.

  • Objectives: The analysis targets simultaneous estimation of the noise level and regression coefficients through prediction and estimation oracle inequalities.The asymptotic framework allows parameters and variables to depend on n, including p ≥ n ≥ |β|0 → ∞.
  • Prediction guarantees: The relative noise-estimation error is controlled by τ0, which is determined by minimizing a prediction-error bound over candidate vectors and supports.The bound uses the compatibility factor and a cone condition for sparse estimation.
  • Relation to prior theory: The results extend fixed-penalty lasso oracle inequalities and improve the earlier noise-level convergence rate of penalized maximum likelihood estimation.Theorem 1 unifies prediction inequalities for fixed penalties, while later bounds automatically extend existing ℓq inequalities to the scaled lasso.
  • Prediction guarantees: The prediction bound compares scaled-lasso error with the best sparse linear predictor plus a capped-ℓ1 approximation cost.This result permits an arbitrary, possibly non-sparse β∗ and yields consistency of the noise-level estimator.
  • Noise-level estimation: Theorem 2 sharpens the noise-level rate to essentially the square of the earlier rate and establishes corresponding ℓ1 coefficient-error bounds.The sharper rate is based on an ℓ1 error bound for estimating β.
  • Noise-level estimation: When the compatibility factor is bounded, the relative noise error is of order |β∗|0(log p)/n, supporting asymptotic normality when |β∗|0(log p)/√n → 0.The result provides a basis for statistical inference about σ in certain large-p-smaller-n settings.
  • Technical conditions: The theory relies on compatibility, restricted-eigenvalue-type, and cone conditions linking design geometry to prediction and coefficient-error control.The proofs derive bounds from a basic inequality associated with the Karush–Kuhn–Tucker conditions and analyze the profile loss near σ/σ∗ = 1.

Estimation after model selection

The paper establishes theoretical guarantees for least-squares estimation after scaled-lasso model selection, including prediction, estimation, noise-level, and false-positive bounds. It also notes that scaled lasso estimates the noise level without requiring prior knowledge of σ, while bias-removing scaled penalties remain outside the paper’s theoretical scope.

  • Noise-level estimation: Without knowing σ, scaled lasso attains prediction and estimation properties comparable to results for known σ, while its noise-level estimate can be consistent and asymptotically normal under proper conditions.These properties apply under regularity conditions and include settings where the number of variables can exceed the sample size.
  • Scope: The paper focuses on least-squares estimation after selection because theoretical analysis of scaled smoothly clipped absolute deviation and minimax concave penalties is beyond its scope.Those penalties were introduced to reduce lasso bias, which the paper reports as substantial in simulations.
  • Theoretical results: Least-squares estimation after scaled-lasso selection has prediction and estimation error bounds, together with an upper bound on false positives.The false-positive bound |bS \ S| < m is central to the analysis and is weaker than exact variable-selection consistency.
  • Theoretical results: Theorem 3 gives these post-selection guarantees under conditions involving the true support, compatibility factors, sparse eigenvalues, and a tuning-related threshold.The theorem applies to the scaled-lasso estimator and the least-squares estimator in the selected model.
  • Numerical evaluation: Table 1 evaluates five methods across 100 replications using bias and standard error of noise-level ratios, average model size, and sure-screening frequency.The table covers both selector estimates and least-squares estimates after model selection at three penalty levels.

Simulation study

The simulations compare scaled penalized methods, penalized maximum likelihood estimators, and post-selection least squares across synthetic and real-data settings. Results indicate strong performance for scaled nonconvex selection and substantial bias reduction from least squares post-processing, while penalty choice remains difficult.

  • Simulation design: The study compares five scaled or penalized methods and also evaluates least squares after model selection.The methods include scaled lasso, scaled minimax concave penalty, scaled SCAD, penalized maximum likelihood, and bias correction.
  • Results: At λ2 = √{(2/n) log p}, scaled minimax concave penalized selection clearly outperforms the other procedures without post-processing.The comparison concerns the example’s selector performance at the universal penalty level.
  • Limitations: Choosing the penalty level consistently is difficult because larger penalties select too few variables, smaller penalties select too many, and the scaled noise estimate varies with penalty.The paper notes that a specific penalty can reduce bias for each example, but that such a choice is not consistently available.
  • Results: The scaled lasso outperforms penalized maximum likelihood and its bias correction, but its noise estimate remains biased in the difficult Example 2 setting.The reported error-bound order is (|S|/n) log p = 0.47; |S| = 35 and signals are weak.
  • Results: Least squares after model selection reduces bias substantially in all cases, even when model selection is unsuccessful.At λ2, its results are nearly identical to the top performer across all five methods.

Real data example

The real-data example analyzes gene-expression probes for TRIM32 using high-dimensional linear regression and compares sparse-selection and prediction procedures. Scaled methods provide stable selections and prediction performance comparable to cross-validation.

  • Data and setup: The study uses 120 rats, 18,975 candidate covariates, and either 200 or 3,000 probes to identify probes related to TRIM32.The response is probe 1389163_at, and the 200-probe set is selected by marginal correlation.
  • Variable selection: Four selection procedures are compared using stability selection, including cross-validation lasso, adjusted cross-validation, scaled lasso, and scaled MCP.The comparison uses the same probe-selection task across p = 200 and p = 3000 settings.
  • Variable selection: The scaled MCP produces the sparsest and most stable selection, followed by adjusted cross-validation, scaled lasso, and plain cross-validation.The passage reports this ordering directly from the stability-selection analysis.
  • Variable selection: Model sizes range from 6 to 8 in all eight stability-selection cases, while scaled MCP gives consistent results for both p = 200 and p = 3000.Scaled lasso and adjusted cross-validation also agree in several of the reported selections.
  • Prediction: In prediction, scaled lasso with λ2 = {2(log p)/n}^1/2 performs almost as well as lasso with the optimal fixed penalty.The evaluation uses 1,000 random 80-training/40-test splits.
  • Prediction: Across the broader comparison, scaled lasso has prediction performance comparable to cross-validation, while original cross-validation tends to select larger models.Table 4 reports prediction mean squared error, estimated model size, and correlation coefficient.

5. DISCUSSION

The discussion addresses penalty calibration and presents fixed-penalty oracle inequalities used in the scaled-lasso theory. It notes that the theoretical penalty choice is conservative and that weaker design conditions can support the bounds.

  • Penalty choice: The theoretical choice λ0 = A{(2/n) log p}^1/2 with A > 1 is described as somewhat conservative.Simulation results suggest that requiring A > 1 may be a mathematical technicality.
  • Penalty choice: The theoretical results remain valid with a smaller penalty min(λ0, Aλ*) when |X′ε/n|∞ ≤ λ* holds with large probability.The value of λ* can be estimated by simulation for the given design matrix.
  • Penalty choice: The difference between the original and smaller penalty choices is limited unless log p = {1 + o(1)} log n.The discussion also cites a method for selecting penalties that nearly minimizes the order of penalized prediction error.
  • Oracle inequalities: The paper develops fixed-penalty oracle inequalities that unify and somewhat sharpen existing results for use in the scaled-lasso analysis.Theorem 4 concerns the lasso minimizer under a bound on |X′(y − Xβ*)|∞/n.
  • Oracle inequalities: The bounds require a compatibility condition κ(ξ,S) ≍ 1, which is weaker than the corresponding restricted-eigenvalue condition.The paper notes that the condition can be slightly weakened using F1(ξ,S).

APPENDIX

The appendix proves the paper’s propositions and theorems through penalized-loss inequalities, cone conditions, concentration arguments, and convexity. It establishes bounds for coefficient estimation, noise estimation, and model-selection-related errors.

  • Fixed-penalty bounds: Theorem 4 derives fixed-penalty lasso bounds from a basic inequality, cone constraints, and compatibility quantities.The resulting bounds control prediction error and coefficient error through η(λ, ξ, w, T) and related quantities.
  • Fixed-penalty bounds: The appendix bounds the coefficient error by converting an inequality in |h_T|_1 and |h_Tc|_1 into a maximization problem.This yields an explicit bound involving λ, |T|, and κ^2.
  • Noise estimation: Theorem 1’s noise-level analysis uses strict convexity of the profile loss to establish lower and upper bounds for the estimated noise level.The proof compares derivatives below and above the target noise level.
  • Probability bounds: A t-distribution lemma and Gaussian concentration arguments control the stochastic terms used in the noise-estimation proofs.The lemma uses ε_m → 0 as m → ∞, while the noise ratio is connected to a chi-squared distribution.
  • Scaled estimation: Theorem 2 controls the scaled estimator through φ− and φ+ bounds, then transfers the noise-level bound to the coefficient estimate.The resulting coefficient bound is expressed through μ(σ*λ0, ξ)(1 + φ+).
  • Probability bounds: The appendix obtains asymptotic normality because n^1/2(σ*/σ − 1) converges to N(0, 1/2), combined with the scaled estimator bound under φ(σ) = o(n^-1/2).This is the stated probabilistic conclusion for the noise-level estimator.
  • Post-selection analysis: Theorem 3 bounds selected-model size and prediction error using sparse eigenvalues, compatibility constants, and Gaussian concentration.The proof shows that the selected support cannot contain a subset of size m under the stated inequalities.
Loading 1104.4595v2…