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

Abstract

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\ge 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.

arXiv comment39 pages

References in corpus (13)

• Aggregation for Gaussian regression
• Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles
• Loss minimization and parameter estimation with heavy tails
• Robust linear least squares regression
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Covariance estimation for distributions with $2+\epsilon$ moments
• Ridge regression and asymptotic minimax estimation over spheres of growing dimension
• Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions
• Geometric sensitivity of random matrix results: consequences for shrinkage estimators of covariance and related statistical methods
• Lower bounds on the smallest eigenvalue of a sample covariance matrix
• Performance of empirical risk minimization in linear aggregation
• A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares
• Linear regression through PAC-Bayesian truncation

Cited by in corpus (13)

• Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping
• Distribution-Free Robust Linear Regression
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
• On the Universality of the Double Descent Peak in Ridgeless Regression
• Adversarially Robust Estimate and Risk Analysis in Linear Regression
• Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge
• Naive imputation implicitly regularizes high-dimensional linear models
• Logarithmic Regret in Feature-based Dynamic Pricing
• Unbiased least squares regression via averaged stochastic gradient descent
• Conditionally Strongly Log-Concave Generative Models
• Non-Asymptotic Bounds for the ${\ell }_{\infty }$ Estimator in Linear Regression with Uniform Noise
• Convergence guarantees for forward gradient descent in the linear regression model
• An elementary analysis of ridge regression with random design