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

By Jaouad Mourtada. Annals of Statistics, 2019

60 citations recorded by the source corpus.

The first part of this paper is devoted to the decision-theoretic analysis of random-design linear prediction. It is known that, under boundedness constraints on the response (and thus on regression coefficients), the minimax excess risk scales, up to constants, as $\sigma^2 d / n$ in dimension $d$ with $n$ samples and noise $\sigma^2$. Here, we study the expected excess risk with respect to the full linear class. We show that the ordinary least squares estimator is exactly minimax optimal in the well-specified case for every distribution of covariates. Further, we express the minimax risk in terms of the distribution of \emph{statistical leverage scores} of individual samples. We deduce a precise minimax lower bound of $\sigma^2d/(n-d+1)$ for general covariate distribution, which nearly matches the risk for Gaussian design. We then obtain nonasymptotic upper bounds on the minimax risk for covariates that satisfy a "small ball"-type regularity condition, which scale as $(1+o(1))\sigma^2d/n$ as $d=o(n)$, both in the 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 around $0$. We establish a lower bound on this lower tail, valid for any distribution in dimension $d \geq 2$, together with a matching upper bound under a necessary regularity condition. Our proof relies on the PAC-Bayesian technique for controlling empirical processes, and extends an analysis of Oliveira devoted to a different part of the lower tail. Equivalently, our upper bound shows that the operator norm of the inverse sample covariance matrix has bounded $L^q$ norm up to $q \asymp n$, and our lower bound implies that this exponent is unimprovable. Finally, we show that the regularity condition naturally holds for independent coordinates.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2a7e2bd54e7b4a4b41df02b89806b17d1699724c