Signal-to-noise ratio aware minimax analysis of sparse linear regression

S. Ghosh, Yilin Guo, Haolei Weng, Arian MalekiarXiv 2025 · DOI · arXiv

TL;DR

Traditional statistical theory often suggests that Lasso and Best Subset Selection are the "gold standard" for sparse linear regression. However, this paper reveals that these methods fail when signals are weak, proving through a new "SNR-aware" framework that Ridge and Elastic-net are actually the optimal choices in low-to-medium signal-to-noise ratio (SNR) regimes.

What Problem Does This Paper Address?

In high-dimensional statistics, we often try to solve the "sparse linear regression" problem: finding a few important needles (signals) in a massive haystack of data (features). For decades, the minimax framework has been the yardstick for "optimal" estimation. Under this framework, estimators like the Lasso and Best Subset Selection are considered optimal.

However, there is a nagging mismatch between theory and practice. Practitioners have long observed that when the signal is weak relative to the noise (low SNR), simple Ridge regression—which doesn't even promote sparsity—often outperforms the "optimal" Lasso. Standard minimax theory fails to explain this because its formulas typically ignore the signal strength entirely, focusing only on the noise level and the number of features. The authors tackle this discrepancy by introducing a framework that explicitly accounts for SNR.

Methods

The authors move beyond "first-order" asymptotics (which only look at the biggest terms in an equation) to higher-order asymptotic analysis.

  1. SNR-Aware Parameter Space: They redefine the set of possible signals to include a constraint on signal strength ($\tau$), not just sparsity ($k$).
  2. Regime Analysis: They divide the problem into three distinct SNR regimes:
  3. Low-SNR: The signal is so weak it's vanishing.
  4. Medium-SNR: The signal is growing but still relatively small.
  5. High-SNR: The signal is strong enough to be easily distinguished from noise.
  6. Second-Order Approximations: Standard theory says the risk in low SNR is just $k\tau^2$ (the risk of guessing zero). By calculating the "second-order" terms, the authors can finally distinguish which estimators perform better than the "zero estimator" and by how much.

Datasets

The paper relies on synthetic datasets to provide controlled environments for testing their theoretical predictions.

  • Design: Isotropic Gaussian design matrices where $x_i \sim \mathcal{N}(0, \frac{1}{n}I_p)$.
  • Signals: Sparse vectors $\beta$ where $k$ components are set to a magnitude $\tau$, and the rest are zero.
  • Scale: They tested large-scale settings ($n=500, p=1000$) to compare Lasso, Ridge, and Elastic-net, and smaller-scale settings ($n=75, p=150$) to include the computationally expensive Best Subset Selection.

Key Insights and Ideas

  • The "Hardest Spot" Fallacy: Traditional minimax analysis only looks at the specific signal strength that makes the problem the most difficult. This usually happens at high SNR, which is why standard theory is "blind" to what happens when signals are weak.
  • The Dominance of Variance: In low-SNR settings, the error is dominated by the variance of the noise. Because Ridge regression (L2 regularization) is better at suppressing variance than Lasso (L1 regularization), it becomes the mathematically superior choice, even if the underlying truth is sparse.
  • The Elastic-net Bridge: In the "Medium-SNR" regime, neither pure sparsity nor pure variance reduction is enough. The authors show that the Elastic-net (a hybrid of L1 and L2) is nearly minimax optimal here.
  • Phase Transitions: The paper identifies clear "switching rules" where the optimal strategy shifts from Ridge to Elastic-net to Lasso as the signal gets stronger.

Key Results

The authors provide sharp mathematical bounds for the minimax risk in each regime:

  • Low-SNR: The minimax risk is approximately $k\tau^2(1 - \frac{k\tau^2}{p\sigma^2})$. They prove that Ridge regression is the unique optimal estimator here.
  • Medium-SNR: They show that Elastic-net achieves a lower risk than both Ridge and Lasso.
  • High-SNR: They recover the classical result where the risk is $\approx 2\sigma^2 k \log(p/k)$, confirming that Lasso and Best Subset Selection are optimal only when the signal is sufficiently strong.

Simulations (Figure 2 and 3 in the paper) perfectly mirror these results, showing the Mean Squared Error (MSE) of Ridge starting lower than Lasso in high-noise settings and crossing over as the noise decreases.

Limitations and Future Work

  • Isotropic Design: The current proofs assume features are independent (isotropic Gaussian design). In real-world data, features are often highly correlated, which might change the boundaries of these SNR regimes.
  • Regime II Gap: In the Medium-SNR regime, there is still a small gap between the theoretical lower bound and the upper bound achieved by the Elastic-net (differing by a factor of the SNR). Closing this gap remains a mathematical challenge.
  • Beyond MSE: The study focuses on parameter estimation (MSE). Future work could apply this SNR-aware lens to other goals, such as variable selection (identifying which features are important) or prediction.

Summary updated

Abstract

We consider parameter estimation under sparse linear regression -- an extensively studied problem in high-dimensional statistics and compressed sensing. While the minimax framework has been one of the most fundamental approaches for studying statistical optimality in this problem, we identify two important issues that the existing minimax analyses face: (i) The signal-to-noise ratio appears to have no effect on the minimax optimality, while it shows a major impact in numerical simulations. (ii) Estimators such as best subset selection and Lasso are shown to be minimax optimal, yet they exhibit significantly different performances in simulations. In this paper, we tackle the two issues by employing a minimax framework that accounts for variations in the signal-to-noise ratio (SNR), termed the SNR-aware minimax framework. We adopt a delicate higher-order asymptotic analysis technique to obtain the SNR-aware minimax risk. Our theoretical findings determine three distinct SNR regimes: low-SNR, medium-SNR, and high-SNR, wherein minimax optimal estimators exhibit markedly different behaviors. The new theory not only offers much better elaborations for empirical results, but also brings new insights to the estimation of sparse signals in noisy data.
BibTeX
@misc{ghosh2025signal,
  author = {S. Ghosh and Yilin Guo and Haolei Weng and Arian Maleki},
  title = {{Signal-to-noise ratio aware minimax analysis of sparse linear regression}},
  year = {2025},
  eprint = {2501.13323},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.13323},
  howpublished = {arXiv},
}

Loading related content...

Figure