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

通过研究新颖的偏尾分析技巧，我们在随机设计的线性预测和相关问题上考虑最小化期望风险。我们发现，当每个样本所代表的统计杠杆得分在高斯设计时是最小的。我们通过控制经验过程的 PAC-Bayes 技术扩展了 Oliveira 的分析。

线性最小二乘的确切极小极大风险及样本协方差矩阵的下尾

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

We provide an exact non-asymptotic lower bound on the minimax expected excess
risk (EER) in the agnostic probably-ap\-proximately-correct (PAC) machine
learning classification model and identify minimax learning algorithms as
certain maximally symmetric and minimally randomized "voting" procedures. Based
on this result, an exact asymptotic lower bound on the minimax EER is provided.
This bound is of the simple form $c_\infty/\sqrt{\nu}$ as $\nu\to\infty$, where
$c_\infty=0.16997\dots$ is a universal constant, $\nu=m/d$, $m$ is the size of
the training sample, and $d$ is the Vapnik--Chervonenkis dimension of the
hypothesis class. It is shown that the differences between these asymptotic and
non-asymptotic bounds, as well as the differences between these two bounds and
the maximum EER of any learning algorithms that minimize the empirical risk,
are asymptotically negligible, and all these differences are due to ties in the
mentioned "voting" procedures. A few easy to compute non-asymptotic lower
bounds on the minimax EER are also obtained, which are shown to be close to the
exact asymptotic lower bound $c_\infty/\sqrt{\nu}$ even for rather small values
of the ratio $\nu=m/d$. As an application of these results, we substantially
improve existing lower bounds on the tail probability of the excess risk. Among
the tools used are Bayes estimation and apparently new identities and
inequalities for binomial distributions.

提出了一种关于最小二倍经验风险下界的理论证明，并明确了最小二倍经验风险学习算法的特点，其中包括极限对称性和最小随机化 “投票” 程序。