A note on the minimax risk of sparse linear regression

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

TL;DR

This paper provides the first asymptotically "constant-sharp" characterization of the minimax risk for sparse linear regression under Gaussian random designs. The authors prove that as the problem dimensions grow, the minimum possible worst-case error is precisely $2\sigma^2 \frac{k}{n} \log(p/k)$, finally pinning down the exact constant that has eluded researchers for decades.

What Problem Does This Paper Address?

In high-dimensional statistics, we often try to estimate a signal $\beta$ from noisy observations $y = X\beta + z$, where the number of features $p$ is much larger than the number of observations $n$. To make this solvable, we assume the signal is "sparse"—meaning only $k$ components are non-zero.

The "minimax risk" represents the best possible performance an estimator can achieve against the worst-case signal. While researchers have long known the rate of this risk (it scales as $O(\frac{k \log(p/k)}{n})$), the exact constant multiplying that rate remained a mystery for general design matrices. Previous theoretical bounds often featured constants that were loose by factors of thousands, making them mathematically interesting but practically difficult to use for predicting actual performance. This paper aims to close that gap for the widely used isotropic Gaussian random design.

Methods

The authors derive the sharp constant by constructing a novel "aggregated estimator" and proving its performance matches a theoretical lower bound.

Key techniques include:

  • Aggregated Estimation: The authors combine two different approaches. They primarily use the Lasso (a standard $L_1$-penalized estimator) when the design matrix $X$ is "well-conditioned" (which happens with very high probability for Gaussian matrices). On the rare occasions where the matrix is poorly conditioned, they fall back to a Restricted Maximum Likelihood Estimator (MLE).
  • Oracle Comparison: To prove the Lasso is optimal, they compare it to an "oracle" soft-thresholding estimator. They show that the distance between the Lasso solution and this oracle is negligible in the limit.
  • Refined Analysis of Expectations: Most previous work provided results "with high probability." This paper performs a much more difficult analysis of the expected risk, which requires carefully controlling the "tails" of the error distribution to ensure that rare, large errors don't blow up the average.

Datasets

As a theoretical statistics paper, it does not use empirical "real-world" datasets. Instead, it relies on a standard mathematical model:

  • Isotropic Gaussian Random Design: The design matrix $X$ is generated such that its entries are independent and identically distributed (i.i.d.) standard normal variables.
  • Gaussian Noise: The errors $z$ are i.i.d. normal variables with variance $\sigma^2$.

Key Insights and Ideas

  • The Magic Number 2: The paper establishes that the constant is exactly 2. This is an "aha moment" because it shows that high-dimensional Gaussian designs asymptotically behave just as well as the much simpler "orthogonal design" (where features don't interfere with each other at all).
  • Lasso is (Asymptotically) Perfect: The results show that the Lasso isn't just a good heuristic; with a specifically tuned regularization parameter $\lambda$, it actually achieves the theoretical limit of performance.
  • Tuning Matters: The authors highlight that to achieve this sharp constant, the tuning parameter $\lambda$ must be chosen more aggressively (smaller) than what is typically suggested in earlier "rate-optimal" literature.
  • Bridging the Gap: By moving from "rates" to "sharp constants," the paper moves theoretical statistics closer to information theory, providing a precise "speed limit" for sparse recovery.

Key Results

  • The Main Formula: Under the condition that $(k \log p)/n \to 0$ and $k/p \to 0$, the minimax risk $R_R$ satisfies: $$R_R(\Theta_k, \sigma) \approx 2\sigma^2 \frac{k \log(p/k)}{n}$$
  • Lower Bound: They demonstrate that no estimator, no matter how complex, can achieve a risk lower than this value in the limit.
  • Upper Bound: They prove their aggregated estimator achieves this risk, thereby proving the constant "2" is sharp.

Limitations and Future Work

  • Isotropic Assumption: The results are strictly for isotropic Gaussian designs (where features are uncorrelated). In many real-world applications, features are highly correlated. Extending this sharp analysis to correlated (anisotropic) designs remains a major open challenge.
  • Fixed Design: The paper focuses on "random design" (where $X$ is a random variable). Determining the sharp constant for a specific, "fixed" design matrix $X$ is still an unresolved problem in the field.
  • Strict Sparsity: The model assumes the signal is exactly $k$-sparse. Future work could explore "weakly sparse" signals (e.g., signals in $L_p$ balls) to see if the same constants hold.

Summary updated

Abstract

Sparse linear regression is one of the classical and extensively studied problems in high-dimensional statistics and compressed sensing. Despite the substantial body of literature dedicated to this problem, the precise determination of its minimax risk remains elusive. This paper aims to fill this gap by deriving asymptotically constant-sharp characterization for the minimax risk of sparse linear regression. More specifically, the paper focuses on scenarios where the sparsity level, denoted as k, satisfies the condition $(k \log p)/n {\to} 0$, with p and n representing the number of features and observations respectively. We establish that the minimax risk under isotropic Gaussian random design is asymptotically equal to $2σ^2k/n log(p/k)$, where $σ$ denotes the standard deviation of the noise. In addition to this result, we will summarize the existing results in the literature, and mention some of the fundamental problems that have still remained open.
BibTeX
@misc{guo2024note,
  author = {Yilin Guo and S. Ghosh and Haolei Weng and Arian Maleki},
  title = {{A note on the minimax risk of sparse linear regression}},
  year = {2024},
  eprint = {2405.05344},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.05344},
}
Figure