Calculations for A1
## Uniform Convergence on Ridge Regression
We next show that ridge regression with regularization $1/t$ and uniform convergence cannot cover our results.
We consider a case with data covariance $\lambda_i=\frac{1}{i^{1.5}}$, and show that ridge regression would return a bound with compatibility region shorter than $(0, \sqrt{n})$, which cannot cover our results with compatibility region $(0,n)$.
The uniform convergence bound scales like
$O\left(\frac{||\theta_\lambda||}{\sqrt{n}}\right)$ (see, e.g., Theorem 5.10 in [12]), where $\theta_\lambda$ denote the ERM solution of ridge regression with regularization $\lambda$. We calculate the excess risk of $\theta_\lambda$ as follows. The key insight comes from the fact that the noise matters a lot in the parameter norm.
$$\mathbb{E}\left[||\theta_\lambda||^2\right]=\mathbb{E}\left[||X^\top (XX^\top+\lambda I)^{-1}Y||^2\right]=\mathbb{E}\left[||X^\top (XX^\top+\lambda I)^{-1}(X\theta^*+\varepsilon)||^2\right]
=\mathbb{E}\left[||X^\top (XX^\top+\lambda I)^{-1}(X\theta^*)||^2\right]+\mathbb{E}\left[||X^\top (XX^\top+\lambda I)^{-1}\varepsilon||^2\right]\ge \mathbb{E}\left[||X^\top (XX^\top+\lambda I)^{-1}\varepsilon||^2\right]
=\mathbb{E}\text{Tr}\left[X^\top (XX^\top+\lambda I)^{-1}\varepsilon\varepsilon^\top (XX^\top+\lambda I)^{-1}X\right]\ge \sigma_\varepsilon^2 \mathbb{E}\text{Tr}\left[XX^\top (XX^\top+\lambda I)^{-2} \right]
=\sigma_\varepsilon^2 \sum_{i=1}^n \frac{\mu_i}{(\mu_i+\lambda)^2},$$
where we assume the noise vector is conditionally unbiased and has a lower bounded variance, as in Theorem B.2.
We next assumes that $t = 1/\lambda > \sqrt{n}$.
Then, according to Lemma A.1 and B.2 in our paper, it holds that $ \mu_n=\Theta(\frac{1}{\sqrt{n}})=\Omega(\lambda)$ for $\lambda_i=i^{\frac{-3}{2}}$, where $k_0$ denotes the effective rank in the paper. Therefore, it holds that
$$\sigma_\varepsilon^2 \sum_{i=1}^n \frac{\mu_i}{(\mu_i+\lambda)^2}=\Omega\left(\sigma_\varepsilon^2 \sum_{i=1}^n \frac{1}{\mu_i}\right) = \Omega(\sqrt{n}),$$
which leads to a vacuous generalization bound in uniform convergence. Therefore, the related compatibility region must be shorter than $(0, \sqrt{n})$.
However, in this case, our results show a compatibility region $(0,n)$, which is better.
## Benign Overfitting in Ridge Regression
We additionally show that even if we apply benign overfitting in ridge regression, the returned compatibility region still cannot cover our results.
To apply Theorem 1 in [2], we first calculate the effective rank $k^*$. Note that by plugging in $\lambda_i=\frac{1}{i^{1.5}}$ and $\lambda = 1/\sqrt{n}$,
$$
r_k=\frac{1}{\lambda_{k+1}}\left(\lambda+\sum_{i>k} \lambda_i\right)=\Theta\left(\frac{k^{\frac{3}{2}}}{\sqrt{n}}+k\right),
$$
which increase monotonically with $r_n = \Theta(n)$ and therefore
$$
k^*=\min \lbrace\kappa: \rho_\kappa>b\rbrace=\min \lbrace\kappa: r_\kappa>b n\rbrace=\Theta(n)
$$
According to Lemma 11 in [2], we have $\bar{k}=\Theta(n)$, $k=\min\lbrace k^*,\bar{k}\rbrace=\Theta(n)$ and the first term in the variance part $\frac{k}{n}=\Omega(1)$, which makes the bound vacuous for this setting.