# Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices

arXiv: https://arxiv.org/abs/1912.10754 · HTML: https://mlsanity.com/paper/1912.10754/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2019.

## Built on by (most cited first, 30 of 34)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [An elementary analysis of ridge regression with random design](https://mlsanity.com/paper/2203.08564/) (2022)
- [A transfer learning framework for weak-to-strong generalization](https://mlsanity.com/paper/2405.16236/) (2024)
- [A Non-parametric View of FedAvg and FedProx: Beyond Stationary Points](https://mlsanity.com/paper/2106.15216/) (2021)
- [Discrepancies are Virtue: Weak-to-Strong Generalization through Lens of Intrinsic Dimension](https://mlsanity.com/paper/2502.05075/) (2025)
- [Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge](https://mlsanity.com/paper/2111.01602/) (2021)
- [Demographic Parity Constrained Minimax Optimal Regression under Linear Model](https://mlsanity.com/paper/2206.11546/) (2022)
- [The noise level in linear regression with dependent data](https://mlsanity.com/paper/2305.11165/) (2023)
- [Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits](https://mlsanity.com/paper/2202.13603/) (2022)
- [Unlabeled Data Help: Minimax Analysis and Adversarial Robustness](https://mlsanity.com/paper/2202.06996/) (2022)
- [On Optimal Interpolation In Linear Regression](https://mlsanity.com/paper/2110.11258/) (2021)
- [Minimax Linear Regression under the Quantile Risk](https://mlsanity.com/paper/2406.12145/) (2024)
- [The Statistical Fairness-Accuracy Frontier](https://mlsanity.com/paper/2508.17622/) (2025)
- [Conditionally Strongly Log-Concave Generative Models](https://mlsanity.com/paper/2306.00181/) (2023)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [Invariant Subspace Decomposition](https://mlsanity.com/paper/2404.09962/) (2024)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Minimax rate of consistency for linear models with missing values](https://mlsanity.com/paper/2202.01463/) (2022)
- [How many samples are needed to leverage smoothness?](https://mlsanity.com/paper/2305.16014/) (2023)
- [Unbiased least squares regression via averaged stochastic gradient descent](https://mlsanity.com/paper/2406.18623/) (2024)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Long-time accuracy of ensemble Kalman filters for chaotic and machine-learned dynamical systems](https://mlsanity.com/paper/2412.14318/) (2024)
- [On the Injective Norm of Sums of Random Tensors and the Moments of Gaussian Chaoses](https://mlsanity.com/paper/2503.10580/) (2025)
- [Breaking the curse of dimensionality for linear rules: optimal predictors over the ellipsoid](https://mlsanity.com/paper/2509.21174/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [Near-Optimal and Tractable Estimation under Shift-Invariance](https://mlsanity.com/paper/2411.03383/) (2024)
- [Handling Covariate Mismatch in Collaborative Linear Prediction](https://mlsanity.com/paper/2602.02083/) (2026)
- [Accelerating Single-Pass SGD for Generalized Linear Prediction](https://mlsanity.com/paper/2603.01951/) (2026)

## Abstract (arXiv)

We consider random-design linear prediction and related questions on the lower tail of random matrices. It is known that, under boundedness constraints, the minimax risk is of order d/n in dimension d with n samples. Here, we study the minimax expected excess risk over the full linear class, depending on the distribution of covariates. First, the least squares estimator is exactly minimax optimal in the well-specified case, for every distribution of covariates. We express the minimax risk in terms of the distribution of statistical leverage scores of individual samples, and deduce a minimax lower bound of d/(n-d+1) for any covariate distribution, nearly matching the risk for Gaussian design. We then obtain sharp nonasymptotic upper bounds for covariates that satisfy a "small ball"-type regularity condition in both well-specified and misspecified cases. Our main technical contribution is the study of the lower tail of the smallest singular value of empirical covariance matrices at small values. We establish a lower bound on this lower tail, valid for any distribution in dimension d ≥ 2, together with a matching upper bound under a necessary regularity condition. Our proof relies on the PAC-Bayes technique for controlling empirical processes, and extends an analysis of Oliveira devoted to a different part of the lower tail.