$\displaystyle\geq\frac{1}{512}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\left(1-\frac{2}{1-\alpha}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha-1}\frac{1}{r^{1-\alpha}}\right)\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}$
$\displaystyle=\frac{1}{512}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\left(1-\frac{2}{1-\alpha}\frac{(4k\sigma_{\min}^{2}/(\sigma^{4}\kappa))^{1/\alpha-1}}{n^{q(1/\alpha-\alpha)-1/\alpha+1}}\right)\frac{(\sigma^{4}/\sigma_{\min}^{2})^{2}}{n^{2(1-q)}}.$

To obtain the required bound, we can simply follow the previous steps to bound
$1\geq(1-\lambda_{\min})^{2}\geq 1/4$ due to
$\sigma_{\min}\leq\sigma/\sqrt{2}$, and write
$\min\\{1-\varepsilon,\varepsilon\\}=\text{Dist}_{\delta}(\lambda_{\star},\Gamma)$.

###  B.6 Proofs for Individual Classes of Ridge Regression Estimators

In this section we present upper and lower bounds on the estimation error of
model classes produced by ridge regression. Section B.6.1 presents the proof
of Proposition 1, which provides upper and lower bounds when the
discretization length is _smaller_ than the optimal amount of regularization.
Section B.6.2 presents the proof of Proposition 5, which gives upper and lower
bounds when the discretization length is _larger_ than the optimal amount of
regularization.

####  B.6.1 Proof of Proposition 1

Writing $\lambda=\lambda_{\star}+\Delta$ for some $\Delta>-\lambda_{\star}$ we
find

$\displaystyle\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda})]-\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s)$
$\displaystyle=\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left(\frac{\lambda}{\lambda+s_{i}}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle=\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}.$

The above function is increasing in $\Delta$ for $\Delta>0$ and decreasing in
$\Delta$ for $-\lambda_{\star}<\Delta<0$. Recall that
$\lambda_{\star}=\lambda_{\min}+j\delta+\delta^{\prime}$ for an integer
$j\in\\{0,1,\dots,k-2\\}$, where $\frac{1-\lambda_{\min}}{\delta}=k-1$ and
$\delta\geq\delta^{\prime}\geq 0$. Therefore,

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))=\min_{\lambda\in\\{\lambda_{\min},\lambda_{\min}+\delta,\lambda_{\min}+2\delta,\dots,1\\}}\left(\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda})]-\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s)\right)$
$\displaystyle=\min_{\Delta\in\\{-j\delta-\delta^{\prime},-(j-1)\delta-\delta^{\prime},\dots,-\delta^{\prime},\delta-\delta^{\prime},2\delta-\delta^{\prime},\dots,(k-1-j)\delta-\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}$
$\displaystyle=\min_{\Delta\in\\{-\delta^{\prime},\delta-\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})},$

where for the second equality we rewrote the minimum in terms of the
difference $\lambda-\lambda_{\star}$, and for the third we used the
monotonicity in $\Delta$ noted previously. Since
$\delta^{\prime}=\varepsilon\delta$ for $\varepsilon\in[0,1]$, we find

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))=\min_{\kappa\in\\{-\varepsilon,(1-\varepsilon)\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\kappa^{2}\delta^{2}}{(\lambda_{\star}+\kappa\delta+s_{i})^{2}(\lambda_{\star}+s_{i})}.$

Since by assumption $0<\delta\leq\lambda_{\star}$ we then find for any $s\geq
0$

$\displaystyle(1-\varepsilon)\frac{\delta}{\lambda_{\star}+s}\geq\frac{(1-\varepsilon)\delta}{\lambda_{\star}+(1-\varepsilon)\delta+s}\geq\frac{1-\varepsilon}{2}\frac{\delta}{\lambda_{\star}+s}$
$\displaystyle\frac{\varepsilon}{1-\varepsilon}\frac{\delta}{\lambda_{\star}+\delta}\geq\Big{|}\frac{-\varepsilon\delta}{\lambda_{\star}-\varepsilon\delta+s}\Big{|}=\frac{\varepsilon\delta}{\lambda_{\star}-\varepsilon\delta+s}\geq\varepsilon\frac{\delta}{\lambda_{\star}+s}.$

This provides the upper and lower bound

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\geq\frac{\min\\{1-\varepsilon,\varepsilon\\}^{2}}{4}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\delta^{2}}{(\lambda_{\star}+s_{i})^{3}}$
$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\leq\min\left\\{1-\varepsilon,\frac{\varepsilon}{1-\varepsilon}\right\\}^{2}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\delta^{2}}{(\lambda_{\star}+s_{i})^{3}}.$

The final bound is arrived at by noting that for $s>0$ we have

$\displaystyle\frac{1}{8}G^{\text{Ridge}}(s)\leq\frac{s\delta^{2}}{\lambda_{\star}(\lambda_{\star}+s)^{3}}\leq
G^{\text{Ridge}}(s)$

and
$\min\\{1-\varepsilon,\frac{\varepsilon}{1-\varepsilon}\\}\leq\min\\{1-\varepsilon,2\varepsilon\\}\leq
2\min\\{1-\varepsilon,\varepsilon\\}$.

####  B.6.2 Proof of Proposition 5

Following the proof of Proposition 1, write $\lambda=\lambda_{\star}+\Delta$
for some $1-\lambda_{\star}\geq\Delta\geq 0$. We then have with
$\lambda_{\min}=0$, $\lambda_{\star}=\delta-\delta^{\prime}$, and recalling
that $\delta^{\prime}<\delta$

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(0,k))$
$\displaystyle=\min_{\lambda\in\\{0,\delta,2\delta,\dots,1\\}}\left(\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda})]-\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s)\right)$
$\displaystyle=\min_{\Delta\in\\{-\delta+\delta^{\prime},\delta^{\prime},\delta+\delta^{\prime},,\dots,1-\delta+\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}$
$\displaystyle=\min_{\Delta\in\\{-\delta+\delta^{\prime},\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})},$

where we recall that the function is monotonic for $\Delta>0$ and $\Delta<0$.
Picking $\Delta=\delta^{\prime}$ we find the upper bound

$\displaystyle\min_{\Delta\in\\{-\delta+\delta^{\prime},\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}\leq\delta^{\prime
2}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}^{2}}{(\delta+s_{i})^{2}(\lambda_{\star}+s_{i})^{2}}.$

Meanwhile for the lower bound, taking the minimum into the sum

$\displaystyle\min_{\Delta\in\\{-\delta+\delta^{\prime},\delta^{\prime}\\}}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}$
$\displaystyle\geq\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\min_{\Delta\in\\{-\delta+\delta^{\prime},\delta^{\prime}\\}}\frac{s_{i}\Delta^{2}}{(\lambda_{\star}+\Delta+s_{i})^{2}(\lambda_{\star}+s_{i})}$
$\displaystyle=\delta^{\prime
2}\frac{\sigma^{2}}{n\lambda_{\star}}\sum_{i=1}^{r}\frac{s_{i}}{(\delta+s_{i})^{2}(\lambda_{\star}+s_{i})}.$

We used that for $s>0$

$\displaystyle\frac{\delta^{\prime}}{\delta+s}\leq\frac{\delta-\delta^{\prime}}{s}$
$\displaystyle\iff\delta^{\prime}s\leq\delta^{2}-\delta^{\prime}\delta-\delta^{\prime}s+s\delta$
$\displaystyle\iff
s(2\delta^{\prime}-\delta)\leq\delta(\delta-\delta^{\prime}),$

which holds since $\delta^{\prime}\leq\delta/2$. From (24) we have

$\displaystyle\frac{1}{4}G^{\text{Coarse
Ridge}}(s)\leq\frac{s\delta^{2}}{\lambda_{\star}(\delta+s)^{2}(\lambda_{\star}+s)}\leq
G^{\text{Coarse Ridge}}(s),$

which yields the result.

###  B.7 Proofs for Individual Classes of Gradient Descent Estimators

In this section we present the proofs for bounds on the estimation error of
gradient descent. Before providing the proof of these results, we need to
define the following function, for $s\in(0,1/\eta)$:

$\displaystyle t^{\star}(s):=\frac{\log(1+s/\lambda_{\star})}{-\log(1-\eta
s)}.$ (40)

By continuity, we may also define $t^{\star}(0):=\lim_{s\searrow
0}t^{\star}(s)=1/(\eta\lambda_{\star})$. The follow proposition presents a
bound on $t^{\star}(s)$ when eigenvalues are below the level of
regularization, i.e., $s\in[0,\lambda_{\star}]$. We note that $t^{\star}(s)$
is well defined on this interval since we assume $\eta\leq
1/\max\\{s_{1},\lambda_{\star}\\}$. If $s_{1}=\lambda_{\star}$ and
$\eta=1/s_{1}$, by continuity we define $t^{\star}(\lambda_{\star})=0$.

######  Proposition 8 (Discretization Limit)

For $u\in[0,\lambda_{\star}]$, we have

$\displaystyle\frac{1}{\eta\lambda_{\star}}-t^{\star}(u)\leq\frac{u}{\lambda_{\star}}\left(1+\frac{1}{2\eta\lambda_{\star}}\right).$

Given this result, we can now present the proofs for bounding the estimation
error of models produced by gradient descent. Section B.7.1 presents the proof
of Proposition 2 which considers the fine discretization case. Section B.7.2
presents the proof Proposition 7, which considers the coarse discretization
case. Section B.7.3 then presents the proof of Proposition 8.

####  B.7.1 Proof of Proposition 2

Let us begin by proving the upper bound. Since the sub-optimality gap
evaluates the minimum over all models up to iteration $t$, it is enough to
consider $t=\lceil\frac{1}{\eta\lambda_{\star}}\rceil$. Following the proof of
Lemma 1 we find

$\displaystyle\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,t})]-\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s)=\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s_{i})^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}.$ (41)

We now set to bound $((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s})^{2}$ splitting into two
cases: $s\in(\lambda_{\star},1/\eta]$ and $s\in(0,\lambda_{\star}]$. For the
upper bound we will use both cases, whereas for the lower bound we will only
consider $s\in(0,\lambda_{\star}]$.

Let us begin with the upper bound when $s\in(\lambda_{\star},1/\eta)$. One can
check that $s\rightarrow t^{\star}(s)$ from (40) is a decreasing function of
$s$ over the entire interval $s\in[0,1/\eta)$ with the maximum achieved at the
limit $\lim_{s\rightarrow 0}t^{\star}(s)=\frac{1}{\eta\lambda_{\star}}$.
Noting that $\frac{\lambda_{\star}}{\lambda_{\star}+s}=(1-\eta
s)^{t^{\star}(s)}$ as well as that $t\geq\frac{1}{\eta\lambda_{\star}}\geq
t^{\star}(s)$ we immediately find for $s\in(\lambda_{\star},1/\eta)$

$\displaystyle 0$
$\displaystyle\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}.$

When $s=1/\eta$ we get $\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}=\frac{\lambda_{\star}}{\lambda_{\star}+s}$. Using this upper bound the
terms within the sum in (41) can be bounded when
$s\in(\lambda_{\star},1/\eta]$ as

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left(\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}=\frac{1}{s}\frac{\lambda_{\star}}{\lambda_{\star}+s}\leq\frac{\lambda_{\star}}{s^{2}}.$
(42)

Let us now consider $s\in(0,\lambda_{\star}]$. From Proposition 8 we have
$t-t^{\star}(s)=\lceil\frac{1}{\eta\lambda_{\star}}\rceil-t^{\star}(s)\leq
1+\frac{1}{\eta\lambda_{\star}}-t^{\star}(s)\leq
1+\frac{s}{2\eta\lambda_{\star}^{2}}+\frac{s}{\lambda_{\star}}\leq
1+\frac{3}{2}\frac{s}{\eta\lambda_{\star}^{2}}$ where we have
$\eta\lambda_{\star}^{2}\leq 1$ from the assumption on the step size $\eta\leq
1/\max\\{s_{1},\lambda_{\star}\\}$ and $\lambda_{\star}\leq 1$.

Therefore, using that $(1-\eta s)^{t-t^{\star}(s)}\geq(1-\eta
s)^{1+2\frac{s}{\eta\lambda_{\star}^{2}}}$ since $0\leq t-t^{\star}(s)\leq
1+3/2\cdot\frac{s}{\eta\lambda_{\star}^{2}}$ and $1-\eta s\leq 1$, and from
Bernoulli’s inequality $1-(1-x)^{\alpha}\leq\alpha x$ for $\alpha\geq 1$ and
$x\in[0,1]$, we find

$\displaystyle 0$
$\displaystyle\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}=(1-\eta s)^{t^{\star}(s)}-(1-\eta s)^{t}=(1-\eta
s)^{t^{\star}(s)}\left(1-(1-\eta s)^{t-t^{\star}(s)}\right)$
$\displaystyle\leq 1-(1-\eta s)^{t-t^{\star}(s)}\leq 1-(1-\eta
s)^{1+\frac{3}{2}\frac{s}{\eta\lambda_{\star}^{2}}}$ $\displaystyle\leq\eta
s\left(1+\frac{3}{2}\frac{s}{\eta\lambda_{\star}^{2}}\right)\leq
3\max\left\\{\eta s,\left(\frac{s}{\lambda_{\star}}\right)^{2}\right\\}.$

Thus, for $s\in(0,\lambda_{\star}]$

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\frac{18}{s}\max\left\\{\eta
s,\left(\frac{s}{\lambda_{\star}}\right)^{2}\right\\}^{2}.$ (43)

Combining (42), (43) we then find for $s\in(0,1/\eta]$

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq
18G^{\text{GD}}(s),$

as required. The same bound holds for any
$t\geq\lceil\frac{1}{\eta\lambda_{\star}}\rceil$ since
$\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}\geq\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{\lceil\frac{1}{\eta\lambda_{\star}}\rceil}\geq 0$.

We now prove the lower bound. Recall $\frac{1}{\eta\lambda_{\star}}=k+\kappa$
for some $\kappa\in(0,1)$. We first consider
$t^{\text{Upper}}=\lceil\frac{1}{\eta\lambda_{\star}}\rceil=\frac{1}{\eta\lambda_{\star}}+1-\kappa$
and
$t^{\text{Lower}}=\lfloor\frac{1}{\eta\lambda_{\star}}\rfloor=\frac{1}{\eta\lambda_{\star}}-\kappa$
in turn. The bound for other values of $t$ follows as a direct consequence,
due to the monotonicity of the objective we consider.

Case 1 Suppose $t=t^{\text{Upper}}$. Then $t\geq t^{\star}(s)$ for any
$s\in(0,\lambda_{\star}]$, so we have

$\displaystyle\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t^{\text{Upper}}}$ $\displaystyle=(1-\eta s)^{t^{\star}(s)}-(1-\eta
s)^{t^{\text{Upper}}}$ $\displaystyle=(1-\eta s)^{t^{\star}(s)}\left(1-(1-\eta
s)^{t^{\text{Upper}}-t^{\star}(s)}\right)$
$\displaystyle=\left(\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)\left(1-(1-\eta
s)^{1-\kappa+\frac{1}{\eta\lambda_{\star}}-t^{\star}(s)}\right)$
$\displaystyle=\left(\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)\left(1-(1-\eta
s)^{1-\kappa}(1-\eta s)^{\frac{1}{\eta\lambda_{\star}}-t^{\star}(s)}\right)$
$\displaystyle\geq\frac{1}{2}\left(1-(1-\eta
s)^{1-\kappa}\right)\geq\frac{1}{2}(1-\kappa)\eta s,$

where we have used that $\frac{1}{\eta\lambda_{\star}}\geq t^{\star}(s)$ as
well as that $s\leq\lambda_{\star}$ and therefore
$\frac{\lambda_{\star}}{\lambda_{\star}+s}\geq\frac{1}{2}$. In the final
inequality we used that $1-(1-x)^{\alpha}\geq\alpha x$ for $\alpha\in[0,1]$.
Plugging in this bound we find for $s\in(0,\lambda_{\star}]$

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t^{\text{Upper}}}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}$
$\displaystyle\geq\frac{1}{4}(1-\kappa)^{2}\eta^{2}s,$

as required. The same bound holds for any $t\geq t^{\text{Upper}}$ since
$\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}\geq\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t^{\text{Upper}}}$. The lower bound on the expression in (41) for $t\geq
t^{\text{Upper}}$ is then arrived at by considering the eigenvalues less than
or equal to $\lambda_{\star}$, specifically,

$\displaystyle\eqref{gdid}$
$\displaystyle\geq\frac{(1-\kappa)^{2}\sigma^{2}}{4n}\sum_{i:0<s_{i}\leq\lambda_{\star}}\eta^{2}s_{i}$
$\displaystyle=\frac{(1-\kappa)^{2}\lambda_{\star}}{4d}\sum_{i:0<s_{i}\leq\lambda_{\star}}\eta^{2}s_{i}\geq\frac{1}{4}(1-\kappa)^{2}\lambda_{\star}\int_{0}^{\kappa\eta\lambda_{\star}^{2}/4}G^{\text{GD}}(s)d\widehat{H}(s).$

Case 2 Let us suppose that
$t=t^{\text{Lower}}=\frac{1}{\eta\lambda_{\star}}-\kappa$. From Proposition 8,
we find
$t^{\star}(s)\geq\frac{1}{\eta\lambda_{\star}}-\frac{s}{\eta\lambda_{\star}^{2}}-\frac{s}{\lambda_{\star}}\geq\frac{1}{\eta\lambda_{\star}}-2\frac{s}{\eta\lambda_{\star}^{2}}$,
where we used once again used that $\eta\lambda_{\star}^{2}\leq 1$. Therefore,
if $s\in(0,\frac{\kappa}{4}\eta\lambda_{\star}^{2}]$, we have
$t^{\star}(s)\geq\frac{1}{\eta\lambda_{\star}}-\frac{\kappa}{2}\geq\frac{1}{\eta\lambda_{\star}}-\kappa=t^{\text{Lower}}$.
As such for $s\in(0,\frac{\kappa}{4}\eta\lambda_{\star}^{2}]$ we have

$\displaystyle(1-\eta s)^{t^{\text{Lower}}}-(1-\eta s)^{t^{\star}(s)}$
$\displaystyle=(1-\eta s)^{t^{\text{Lower}}}(1-(1-\eta
s)^{t^{\star}(s)-t^{\text{Lower}}})$ $\displaystyle=(1-\eta
s)^{t^{\text{Lower}}}(1-(1-\eta
s)^{t^{\star}(s)-\frac{1}{\eta\lambda_{\star}}+\kappa})$
$\displaystyle\geq(1-\eta s)^{t^{\text{Lower}}}(1-(1-\eta
s)^{\kappa-\frac{\kappa}{2}})\geq\frac{1}{4}\eta s\kappa,$

where in the final inequality we used that $(1-\eta
s)^{t^{\text{Lower}}}\geq(1-\eta
s)^{t^{\star}(s)}=\frac{\lambda_{\star}}{\lambda_{\star}+s}\geq\frac{1}{2}$
(as $s\leq\lambda_{\star}$) as well as that $1-(1-x)^{\alpha}\geq\alpha x$ for
$\alpha\in[0,1]$. Thus we find for
$s\in(0,\frac{\kappa}{4}\eta\lambda_{\star}^{2}]$

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t^{\text{Lower}}}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}$
$\displaystyle\geq\frac{1}{16}\eta^{2}s\kappa^{2}.$

All other cases $t\leq t^{\text{Lower}}$ then arise from the above inequality
since $(1-\eta s)^{t}\geq(1-\eta s)^{t^{\text{Lower}}}$ in this case. Similar
to the case of $t^{\text{Upper}}$, the lower bound on (41) for $t\leq
t^{\text{Lower}}$ is arrived at by considering the eigenvalues in the interval
$(0,\frac{\kappa}{4}\eta\lambda_{\star}^{2}]$, precisely,

$\displaystyle\eqref{gdid}\geq\frac{\kappa^{2}\lambda_{\star}}{16}\frac{1}{d}\sum_{i:0<s_{i}\leq\kappa\eta\lambda_{\star}^{2}/4}\eta^{2}s_{i}=\frac{\kappa^{2}\lambda_{\star}}{16}\int_{0}^{\kappa\eta\lambda_{\star}^{2}/4}G^{\text{GD}}(s)d\widehat{H}(s)$

Taking a minimum over the lower bounds for
$t=t^{\text{Upper}},t^{\text{Lower}}$ in (41) then yields the result.

####  B.7.2 Proof of Proposition 7

For $u\in(\lambda^{\star},1/\eta)$, we parametrize the number of iterations as
$t=\frac{1}{\eta\sqrt{\lambda_{\star}u}}$. We can recover the stated result by
setting $u=1/((t\eta)^{2}\lambda_{\star})$. We present a bound for the
eigenvalues in each of the sets $(u,1/\eta]$, $(\sqrt{\lambda_{\star}u},u]$,
$(\lambda_{\star},\sqrt{\lambda_{\star}u}]$ and $(0,\lambda_{\star}]$.

Case 1 Consider $s\in(u,1/\eta]$. Using the inequality
$\log(1+x)\leq\frac{x}{\sqrt{1+x}}$ as well as that $\frac{1}{-\log(1-\eta
u)}\leq\frac{1}{\eta u}$ we have
$t^{\star}(u)\leq\frac{u/\lambda_{\star}}{\eta
u\sqrt{1+u/\lambda_{\star}}}=\frac{1}{\eta\sqrt{\lambda_{\star}}\sqrt{\lambda_{\star}+u}}\leq\frac{1}{\eta\sqrt{\lambda_{\star}u}}=t$.
Using that $t^{\star}(\cdot)$ is decreasing, we have
$t=\frac{1}{\eta\sqrt{\lambda_{\star}u}}\geq t^{\star}(u)\geq t^{\star}(s)$
for $s\in(u,1/\eta)$. Therefore for $s\in(u,1/\eta)$ we have

$\displaystyle 0\leq(1-\eta s)^{t^{\star}(s)}-(1-\eta
s)^{t}=\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}.$

For the case $s=1/\eta$ we have
$\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}=\frac{\lambda_{\star}}{\lambda_{\star}+s}$. Bringing together these
cases we find, for $s\in(u,1/\eta]$,

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left(\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\frac{\lambda_{\star}}{s^{2}}.$

Case 2 Consider $s\in(\sqrt{\lambda_{\star}u},u]$. Note that for

$\displaystyle(1-\eta
s)^{k}\leq\frac{\lambda_{\star}u}{\lambda_{\star}u+s^{2}}$

it is sufficient to have
$k\geq\frac{\log(1+s^{2}/(\lambda_{\star}u))}{-\log(1-\eta s)}$. This is
satisfied with $k=t$ since

$\displaystyle t=\frac{1}{\eta\sqrt{\lambda_{\star}u}}\geq\frac{1}{\eta
s}\frac{s^{2}/(\lambda_{\star}u)}{\sqrt{1+s^{2}/(\lambda_{\star}u)}}\geq\frac{\log(1+s^{2}/(\lambda_{\star}u))}{-\log(1-\eta
s)},$

where we used the inequalities $\log(1+x)\leq\frac{x}{\sqrt{1+x}}$ and
$\log(1/(1-x))\geq x$. Therefore if $t<t^{\star}(s)$ we find

$\displaystyle 0\leq(1-\eta s)^{t}-(1-\eta
s)^{t^{\star}(s)}\leq\frac{\lambda_{\star}u}{\lambda_{\star}u+s^{2}}.$

Meanwhile if $t\geq t^{\star}(s)$ we have

$\displaystyle 0\leq(1-\eta s)^{t^{\star}(s)}-(1-\eta s)^{t}\leq(1-\eta
s)^{t^{\star}(s)}=\frac{\lambda_{\star}}{\lambda_{\star}+s}\leq\frac{\lambda_{\star}u}{\lambda_{\star}u+s^{2}},$

where the last inequality arises from $x\rightarrow x/(1+x)$ being increasing,
and by using $s\leq u$. Therefore we have for
$s\in(\sqrt{\lambda_{\star}u},u]$ (so that $s\geq\lambda_{\star}$)

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\frac{2}{\lambda_{\star}}\left(\frac{\lambda_{\star}u}{\lambda_{\star}u+s^{2}}\right)^{2}\leq
2\frac{u^{2}\lambda_{\star}}{s^{4}}.$

Case 3 Let us suppose that $s\in(\lambda_{\star},\sqrt{\lambda_{\star}u}]$. In
this case, if $t<t^{\star}(s)$ we find

$\displaystyle 0\leq(1-\eta s)^{t}-(1-\eta s)^{t^{\star}(s)}\leq
1-\frac{\lambda_{\star}}{\lambda_{\star}+s}=\frac{s}{\lambda_{\star}+s}.$

On the other hand, if $t^{\star}(s)\leq t$ we have

$\displaystyle 0<(1-\eta s)^{t^{\star}(s)}-(1-\eta
s)^{t}\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}\leq\frac{s}{\lambda_{\star}+s},$

where we note that $s>\lambda_{\star}$ and therefore
$\frac{\lambda_{\star}}{\lambda_{\star}+s}\leq\frac{s}{\lambda_{\star}+s}$.
Plugging in we find for $s\in(\sqrt{\lambda_{\star}u},u]$

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\frac{1}{\lambda_{\star}}.$

Case 4 Let us suppose that $s\in(0,\lambda_{\star}]$. Now, note that

$\displaystyle t^{\star}(s)=\frac{\log(1+s/\lambda_{\star})}{-\log(1-\eta
s)}\geq\frac{1-\eta s}{\eta
s}\frac{s/\lambda_{\star}}{1+s/\lambda_{\star}}=\frac{1-\eta
s}{\eta}\frac{1}{s+\lambda_{\star}}\geq\frac{1-\eta
s}{\eta}\frac{1}{2\lambda_{\star}}\geq\frac{1-\eta\lambda_{\star}}{2\eta\lambda_{\star}}\geq
t.$

Therefore

$\displaystyle 0\leq(1-\eta s)^{t}-(1-\eta s)^{t^{\star}(s)}\leq
1-\frac{\lambda_{\star}}{\lambda_{\star}+s}=\frac{s}{\lambda_{\star}+s},$

which when plugging in yields

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq\frac{s}{\lambda_{\star}(\lambda_{\star}+s)}\
\leq\frac{s}{\lambda_{\star}^{2}}.$

Combining the bounds for each of the cases, plugging in $u=(\eta
t)^{2}/\lambda_{\star}$, and recalling (25) then yields the required result

$\displaystyle\left(\frac{1}{s}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s)^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s}\right)^{2}\leq
2G^{\text{Coarse GD}}(s).$

####  B.7.3 Proof of Proposition 8

We only need to consider the case when $s\eta<1$. We proceed to prove the
following more general inequality for $u,s$ such that $1/\eta>u\geq s>0$:

$\displaystyle t^{\star}(s)-t^{\star}(u)\leq\frac{\sqrt{1-\eta
u}}{2\eta\lambda_{\star}}\int_{s}^{u}\frac{1}{z+\lambda_{\star}}dz+\log\left(1+\frac{s}{\lambda_{\star}}\right)\frac{u-s+\eta
s^{2}/12}{s\sqrt{1-\eta s}}.$ (44)

Proposition 8 then arises from taking $s\rightarrow 0$ in the above bound.
Indeed, we have $\lim_{s\rightarrow
0}t^{\star}(s)=\frac{1}{\eta\lambda_{\star}}$. We can bound the integral
$\int_{s}^{u}\frac{1}{z+\lambda_{\star}}dz\leq\frac{u}{\lambda_{\star}}$ and
note that $\lim_{s\rightarrow
0}\log(1+s/\lambda_{\star})/s=1/\lambda_{\star}$, leading to Proposition 8.

To prove (44), we use the inequality [Top06]191919 The lower bound follows
from $\log(1+x)/x\geq\frac{3(2+x)}{6+6x+x^{2}}$ [Top06], since we have we have
that $\frac{3(2+x)}{\sqrt{6}\sqrt{6+6x+x^{2}}}\geq 1$.

$\displaystyle\frac{1}{\sqrt{1+x+x^{2}/6}}\leq\frac{\log(1+x)}{x}\leq\frac{1}{\sqrt{1+x}}\quad\text{
for }x>0.$ (45)

Using this upper bound for $-\log(1-\eta u)=\log(\frac{\eta u}{1-\eta u}+1)$
and the lower bound for $-\log(1-\eta s)=\log\left(\frac{\eta s}{1-\eta
s}+1\right)$, we find

$\displaystyle
t^{\star}(s)-t^{\star}(u)=\frac{\log(1+s/\lambda_{\star})}{-\log(1-\eta
s)}-\frac{\log(1+u/\lambda_{\star})}{-\log(1-\eta u)}$
$\displaystyle\leq\log(1+s/\lambda_{\star})\frac{1-\eta s}{\eta
s}\sqrt{1/(1-\eta s)+(1/(1-\eta
s)-1)^{2}/6}-\log(1+u/\lambda_{\star})\frac{\sqrt{1-\eta u}}{\eta u}$
$\displaystyle=\sqrt{1-\eta u}\left(\frac{\log(1+s/\lambda_{\star})}{\eta
s}-\frac{\log(1+u/\lambda_{\star})}{\eta u}\right)$ (46)
$\displaystyle\quad\quad+\log\left(1+\frac{s}{\lambda_{\star}}\right)\frac{1}{\eta
s}\left(\sqrt{1-\eta s}-\sqrt{1-\eta u}\right)$ (47)
$\displaystyle\quad\quad+\log\left(1+\frac{s}{\lambda_{\star}}\right)\frac{1}{\eta
s}\left((1-\eta s)\sqrt{1/(1-\eta s)+(1/(1-\eta s)-1)^{2}/6}-\sqrt{1-\eta
s}\right).$ (48)

By the fundamental theorem of calculus, we can bound the term in (46) as

$\displaystyle\frac{\log(1+s/\lambda_{\star})}{\eta
s}-\frac{\log(1+u/\lambda_{\star})}{\eta u}$
$\displaystyle=\frac{1}{\eta}\int_{s}^{u}\left[\frac{1}{z^{2}}\log(1+z/\lambda_{\star})-\frac{1}{z+\lambda_{\star}}\frac{1}{z}\right]dz$
$\displaystyle\leq\frac{1}{\eta}\int_{s}^{u}\left[\frac{1}{z^{2}}\frac{z}{\lambda_{\star}}\frac{1}{\sqrt{1+z/\lambda_{\star}}}-\frac{1}{z+\lambda_{\star}}\frac{1}{z}\right]dz$
$\displaystyle=\frac{1}{\eta}\int_{s}^{u}\left[\frac{1}{\sqrt{z+\lambda_{\star}}}\frac{1}{z}\left(\frac{1}{\sqrt{\lambda_{\star}}}-\frac{1}{\sqrt{z+\lambda_{\star}}}\right)\right]dz$
$\displaystyle\leq\frac{1}{2\eta\lambda_{\star}}\int_{s}^{u}\frac{1}{z+\lambda_{\star}}dz,$

where we use the second inequality in (45). The final inequality arises from
using $\sqrt{1+x}-1\leq x/2$ for $x\geq 0$ to conclude
$\frac{1}{\sqrt{\lambda_{\star}}}-\frac{1}{\sqrt{z+\lambda_{\star}}}=\frac{\sqrt{1+z/\lambda_{\star}}-1}{\sqrt{z+\lambda_{\star}}}\leq\frac{z}{2\lambda_{\star}}\frac{1}{\sqrt{z+\lambda_{\star}}}$.

To bound the term in (47) we have, since $u\geq s$,

$\displaystyle\sqrt{1-\eta s}-\sqrt{1-\eta u}=\frac{\eta(u-s)}{\sqrt{1-\eta
s}+\sqrt{1-\eta u}}\leq\frac{\eta(u-s)}{\sqrt{1-\eta s}}.$

Finally, for the term (48), we note that

$\displaystyle(1-\eta s)\sqrt{1/(1-\eta s)+(1/(1-\eta
s)-1)^{2}/6}-\sqrt{1-\eta s}$ $\displaystyle=\sqrt{1-\eta
s}\left(\sqrt{1+\frac{(\eta s)^{2}}{6(1-\eta s)}}-1\right)$
$\displaystyle\leq\frac{(\eta s)^{2}}{12\sqrt{1-\eta s}}.$

Bringing together the last three displays then yields (44).

###  B.8 Proofs for Relative Sub-optimality with Fast Decaying Eigenvalues

In this section we present the proofs of the lower bounds on the relative sub-
optimality when the eigenvalues decay either exponentially or as a power law
with a power greater than one. We begin with a series of technical results.
The first shows that the error of gradient descent is decreasing for a
particular number of iterations.

###### Lemma 2

Let for $i=1,\dots,r$, $b_{i}=\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}$
as well as

$\displaystyle
u_{\min}(\eta):=\arg\inf_{u>2\lambda_{\star}}\left\\{A(u,\eta)\leq
1-\exp\left(-\frac{1}{64}\right)\right\\},$ (49)

where

$A(u,\eta):=\frac{\sum_{i:s_{i}>u}b_{i}+\eta/2\cdot\sum_{i=1}^{r}b_{i}s_{i}(1+\frac{s_{i}}{\lambda_{\star}})^{2}}{\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}b_{i}}.$ (50)

If $\eta\leq\frac{1}{64s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})}$ and
$u_{\min}(\eta)\leq s_{1}$, then the expected estimation error of gradient
descent is decreasing up to $t=\lceil t^{\star}(u_{\min}(\eta))\rceil$
iterations so that

$\displaystyle\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,t+1})]\leq\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,t})]\quad\quad\text{
for }t\leq t^{\star}(u_{\min}(\eta)).$

With slight abuse of notation, we will often abbreviate $A(u)=A(u,\eta)$.

A consequence of this lemma is that the optimal number of iterations is at
least $t^{\star}(u_{\min}(\eta))$. This allows us to prove that gradient
descent essentially overfits the large eigenvalue directions, which provides
the required lower bounds.

###### Theorem 8

Suppose $\eta\leq\frac{1}{64s_{1}\log(1+s_{1}/\lambda_{\star})}$ and
$t\geq\frac{1}{\eta\lambda_{\star}}$. If $u_{\min}(\eta)<s_{1}/2$, then the
error of gradient descent is lower bounded as

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))\geq\frac{1}{4}(1-\exp(-32^{-1}))^{2}\lambda_{\star}\int^{s_{1}}_{2u_{\min}(\eta)}G^{\text{GD}}(s)d\widehat{H}(s),$

where $G^{\text{GD}}(s)$ is defined in Lemma 2.

Given this, it is clear that an upper bound on $u_{\min}(\eta)$ is sufficient,
which then depends upon the stepsize and eigenvalue spectrum. We now present
two propositions, which provide upper bounds when the eigenvalues decay
exponentially or as a power law.

###### Proposition 9

Suppose $s_{i}=\exp(-\rho(i-1))$ for $i=1,\dots,r$ and $\rho>0$. If

$\displaystyle\eta\leq\frac{\lambda_{\star}}{8e}\frac{e^{\rho}}{1+e^{\rho}}(1-e^{-\frac{1}{64}}),$
(51)

then $u_{\min}(\eta)\leq
2e\lambda_{\star}\left(1+2e^{\rho}(1-e^{-\frac{1}{64}})^{-1}\right).$

We now consider the case of eigenvalues decaying at a fast power law rate.

###### Proposition 10

Suppose $s_{i}=i^{-\alpha}$ for $i=1,2,3,\dots,r$ and $\alpha>1$. If
$\lambda_{\star}\leq 2^{-\alpha}$ and

$\displaystyle\eta\leq\frac{\lambda_{\star}^{1-1/\alpha}}{17\cdot
2^{\alpha}}\frac{\alpha-1}{1+\alpha}(1-e^{-\frac{1}{64}}).$ (52)

Then $u_{\min}(\eta)\leq
2^{1+\alpha}\lambda_{\star}\left[1+2^{4+3\alpha}(1-e^{-\frac{1}{64}})^{-1}\right]^{\frac{\alpha}{1+\alpha}}.$

Given these technical results we are ready to the present the proofs, with the
remainder of this section structured as follows. Section B.8.1 presents the
proof of Theorem 4, which gives the lower bound on the estimation error when
the eigenvalues decay exponentially. Section B.8.2 presents the proof of
Theorem 5, which gives the lower bound on the estimation error when the
eigenvalues decay as a power law. The remaining sections then give the proofs
for the aforementioned technical results. Section B.8.3 presents the proof of
Lemma 2. Section B.8.4 presents the proof of Theorem 8. Section B.8.5 presents
the proof of Proposition 9. Section B.8.6 presents the proof of Proposition
10.

####  B.8.1 Proof of Theorem 4

We begin by checking that the conditions of Theorem 8 and Proposition 9 are
satisfied. We recall $\eta=\frac{1}{k\lambda_{\min}}$ and condition (13).
Considering the conditions in Proposition 9 we see from
$k\geq\frac{8e(1+e^{-\rho})}{\lambda_{\star}\lambda_{\min}(1-e^{-\frac{1}{64}})}$
that (51) holds. As a consequence of Proposition 9 alongside that
$\lambda_{\star}<\frac{s_{1}}{2}(2e+4e^{\rho+1}(1-e^{-\frac{1}{64}})^{-1})^{-1}$
we have $u_{\min}(\eta)<s_{1}/2$. Moreover, the conditions of Theorem 8 are
satisfied since since
$k\geq\frac{64}{\lambda_{\min}}s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})$
implies $\eta\leq\frac{1}{64s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})}$.

Applying Theorem 8 to gradient descent alongside the upper bound from
Proposition 1 for ridge regression with $\delta=(1-\lambda_{\min})/(k-1)$
yields

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,t),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
$\displaystyle=\frac{\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))}{\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))}$
$\displaystyle\geq\frac{1}{16}(1-\exp(-\frac{1}{32}))^{2}\frac{1}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\frac{\int^{s_{1}}_{2u_{\min}(\eta)}G^{\text{GD}}(s)d\widehat{H}(s)}{\int
G^{\text{Ridge}}(s)d\widehat{H}(s)}.$

We now need to bound the rightmost integrals. From Proposition 9 we recall
that $u_{\min}(\eta)\leq\lambda_{\star}c_{\rho}$ where
$c_{\rho}=2e+4e^{1+\rho}(1-e^{-\frac{1}{64}})^{-1}>1$. This allows us to lower
bound

$\displaystyle\int^{s_{1}}_{2u_{\min}(\eta)}G^{\text{GD}}(s)d\widehat{H}(s)\geq\int^{s_{1}}_{2c_{\rho}\lambda_{\star}}G^{\text{GD}}(s)d\widehat{H}(s)=\int^{s_{1}}_{2c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s).$

For ridge regression we have

$\displaystyle\int G^{\text{Ridge}}(s)d\widehat{H}(s)$
$\displaystyle=\left(\frac{1-\lambda_{\min}}{\lambda_{\star}k}\right)^{2}\left[\int^{s_{1}}_{c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{c_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)\right].$

Bringing everything together yields

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,t),\mathcal{C}^{Ridge}(\lambda_{\min},k))$
$\displaystyle\geq\frac{1}{16}(1-\exp(-\frac{1}{32}))^{2}\frac{1}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2}$
$\displaystyle\quad\quad\times\frac{\int^{s_{1}}_{c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)}{\int^{s_{1}}_{c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{c_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)}.$
(53)

We must now bound the ratio of integrals. From
$\exp(2\rho(i-1))\leq\int_{i-1}^{i}\exp(2\rho x)dx$ we have

$\displaystyle\int^{c_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)$
$\displaystyle=\frac{1}{d}\sum_{i:\lambda_{\star}<s_{i}\leq
c_{p}\lambda_{\star}}\frac{\lambda_{\star}}{s_{i}^{2}}=\frac{\lambda_{\star}}{d}\sum_{i=\lceil
1+\frac{1}{\rho}\log(1/(c_{p}\lambda_{\star}))\rceil}^{\lceil\frac{1}{\rho}\log(1/\lambda_{\star})\rceil}\exp(2\rho(i-1))$
$\displaystyle\leq\frac{\lambda_{\star}}{d}\int_{\frac{1}{\rho}\log(1/(c_{p}\lambda_{\star}))}^{1+\frac{1}{\rho}\log(1/\lambda_{\star})}\exp(2\rho
x)dx=\frac{\lambda_{\star}}{2\rho
d}\left(\frac{e^{2\rho}}{\lambda_{\star}^{2}}-\frac{1}{c_{p}^{2}\lambda_{\star}^{2}}\right)\leq\frac{e^{2\rho}}{2\rho
d\lambda_{\star}}.$

Similarly we have

$\displaystyle\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)\\!=\\!\frac{1}{d\lambda_{\star}^{2}}\sum_{i=\lceil
1+\frac{1}{\rho}\log(1/\lambda_{\star})\rceil}^{r}\exp(-\rho(i-1))\leq\frac{1}{d\lambda_{\star}^{2}}\int_{\frac{1}{\rho}\log(1/\lambda_{\star})}^{r}\\!\exp(-\rho
x)dx\\!\leq\\!\frac{1}{d\rho\lambda_{\star}}.$

Finally, we have the lower bound

$\displaystyle\int_{c_{\rho}\lambda_{\star}}^{s_{1}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)$
$\displaystyle=\frac{\lambda_{\star}}{d}\sum_{i=1}^{\lceil\frac{1}{\rho}\log(1/(c_{\rho}\lambda_{\star}))\rceil}\exp(2\rho(i-1))$
$\displaystyle\geq\frac{\lambda_{\star}}{d}\int_{0}^{\frac{1}{\rho}\log(1/(c_{\rho}\lambda_{\star}))}\exp(2\rho
x)dx=\frac{\lambda_{\star}}{2\rho
d}\left(\frac{1}{c_{\rho}^{2}\lambda_{\star}^{2}}-1\right)\geq\frac{1}{4d\rho
c_{\rho}^{2}\lambda_{\star}},$

where in the last inequality we used that
$\lambda_{\star}\leq\frac{s_{1}}{2c_{\rho}}\leq\frac{1}{\sqrt{2}c_{\rho}}$.
Combining these bounds we have

$\displaystyle\frac{\int^{s_{1}}_{c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)}{\int^{s_{1}}_{c_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{c_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)}\geq\frac{1}{1+4c_{\rho}^{2}(1+e^{2\rho})}\geq\frac{1}{c_{\rho}^{2}}\frac{1}{8(1+e^{2\rho})}.$

Plugging this into (B.8.1) yields the result.

####  B.8.2 Proof of Theorem 5

Similar to the proof of Theorem 4 we begin by checking the conditions of
Theorem 8 and Proposition 10. Since $\eta=\frac{1}{k\lambda_{\min}}$ and (14),
(15) hold, (52) holds. Since
$\lambda_{\star}<\frac{s_{1}}{2}\frac{1}{2^{1+\alpha}}[1+2^{4+3\alpha}(1-e^{-\frac{1}{64}})^{-1}]^{\frac{-\alpha}{\alpha+1}}$
we have from Proposition 10 that $u_{\min}(\eta)<s_{1}/2$. Moreover, since
$k\geq\frac{64}{\lambda_{\min}}s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})$, we
have $\eta\leq\frac{1}{64s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})}$, and
thus the conditions for Theorem 8 are met.

Writing $u_{\min}(\eta)\leq\lambda_{\star}b_{\rho}$ where
$b_{\rho}=2^{1+\alpha}(1+2^{4+3\alpha}(1-e^{-\frac{1}{64}})^{-1})^{\frac{\alpha}{\alpha+1}}>1$,
we have

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,t),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
$\displaystyle\geq\frac{1}{16}(1-\exp(-\frac{1}{32}))^{2}\frac{1}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2}$
$\displaystyle\quad\quad\times\frac{\int^{s_{1}}_{b_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)}{\int^{s_{1}}_{b_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{b_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)}.$
(54)

We now bound the ratio of integrals in a similar way to the argument in the
proof of Theorem 4. First,

$\displaystyle\int^{s_{1}}_{b_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)=\frac{\lambda_{\star}}{d}\sum_{i:b_{\rho}\lambda_{\star}<s_{i}\leq
s_{1}}i^{2\alpha}=\frac{\lambda_{\star}}{d}\sum_{i=1}^{\lceil(b_{\rho}\lambda_{\star})^{-1/\alpha}\rceil-1}i^{2\alpha}\geq\frac{\lambda_{\star}}{d}\int_{0}^{\lceil(b_{\rho}\lambda_{\star})^{-1/\alpha}\rceil-1}x^{2\alpha}dx$
$\displaystyle\geq\\!\frac{\lambda_{\star}}{d}\\!\int_{0}^{(b_{\rho}\lambda_{\star})^{-1/\alpha}-1}\\!x^{2\alpha}dx\\!=\\!\frac{1}{1\\!+\\!2\alpha}\frac{\lambda_{\star}}{d}((b_{\rho}\lambda_{\star})^{-1/\alpha}\\!-\\!1)^{1+2\alpha}\\!\geq\\!\frac{1}{1+2\alpha}\frac{1}{2^{1+2\alpha}}\frac{\lambda_{\star}}{d}(b_{\rho}\lambda_{\star})^{-(2+1/\alpha)},$

where in the last inequality we used that
$\lambda_{\star}\leq\frac{1}{2^{\alpha}b_{\rho}}$. For the second integral we
have

$\displaystyle\int^{b_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)$
$\displaystyle=\frac{\lambda_{\star}}{d}\sum_{i:\lambda_{\star}<s_{i}\leq
b_{\rho}\lambda_{\star}}i^{2\alpha}=\frac{\lambda_{\star}}{d}\sum_{i=\lceil(b_{\rho}\lambda_{\star})^{-1/\alpha}\rceil}^{\lceil\lambda_{\star}^{-1/\alpha}\rceil-1}i^{2\alpha}\leq\frac{\lambda_{\star}}{d}\int_{(b_{\rho}\lambda_{\star})^{-1/\alpha}}^{1+\lambda_{\star}^{-1/\alpha}}x^{2\alpha}dx$
$\displaystyle\leq\frac{\lambda_{\star}}{d}\frac{1}{1+2\alpha}2^{1+2\alpha}\left(\lambda_{\star}^{-(1+2\alpha)/\alpha}-(b_{\rho}\lambda_{\star})^{-(2+1/\alpha)}\right)$
$\displaystyle\leq\frac{\lambda_{\star}}{d}2^{1+2\alpha}\lambda_{\star}^{-(2+1/\alpha)}.$

Finally, since $\alpha>1$, we have

$\displaystyle\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)$
$\displaystyle=\frac{1}{d\lambda_{\star}^{2}}\sum_{i:s_{r}\leq
s_{i}\leq\lambda_{\star}}i^{-\alpha}=\frac{1}{d\lambda_{\star}^{2}}\sum_{i=\lceil\lambda_{\star}^{-1/\alpha}\rceil}^{r}i^{-\alpha}\leq\frac{1}{d\lambda_{\star}^{2}}\int_{\lambda_{\star}^{-1/\alpha}}^{r+1}x^{-\alpha}dx$
$\displaystyle=\frac{1}{(\alpha-1)d\lambda_{\star}^{2}}\left(\lambda_{\star}^{1-1/\alpha}-(r+1)^{1-\alpha}\right)\leq\frac{1}{(\alpha-1)d\lambda_{\star}^{1+1/\alpha}}.$

Bringing everything together we have

$\displaystyle\frac{\int^{s_{1}}_{b_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)}{\int^{s_{1}}_{b_{\rho}\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{b_{\rho}\lambda_{\star}}_{\lambda_{\star}}\frac{\lambda_{\star}}{s^{2}}d\widehat{H}(s)+\int^{\lambda_{\star}}_{0}\frac{s}{\lambda_{\star}^{2}}d\widehat{H}(s)}$
$\displaystyle\geq\frac{1}{1+2^{2(1+2\alpha)}(1+2\alpha)b_{\rho}^{1/\alpha+2}\frac{\alpha}{\alpha-1}}$
$\displaystyle\geq\frac{1}{2}\frac{1}{2^{2(1+2\alpha)}(1+2\alpha)b_{\rho}^{1/\alpha+2}\frac{\alpha}{\alpha-1}}.$

Plugging in the above bound into (54) yields the result.

####  B.8.3 Proof of Lemma 2

Fix some number of iterations $t\geq 0$. The error decreases with an
additional iteration if and only if the following quantity is negative:

$\displaystyle\frac{n}{\sigma^{2}}\left(\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,t+1})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,t})]\right)$
$\displaystyle=\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s_{i})^{t+1}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}-\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left((1-\eta
s_{i})^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle=\sum_{i=1}^{n}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)(1-\eta
s_{i})^{t}(\eta
s_{i})\left[2\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t}(2-\eta s_{i})\right]=:D.$

For a $t=t^{\star}(u)$ for some $s_{1}>u>0$, we now bound the term within the
square brackets by considering three different cases for the eigenvalues : (A)
$\lambda_{\star}<s_{i}\leq u/2$; (B) $u/2<s_{i}\leq u$ and (C) $u<s_{i}$.

Recall the function $t^{\star}$ from (40). For case (A) observe that we have
the lower bound for $\lambda_{\star}<s_{i}\leq u/2$

$\displaystyle\eta s_{i}(t^{\star}(s_{i})-t^{\star}(u))\geq\frac{1}{64},$ (55)

the proof of which is given at the end of this subsection, starting with
display (57). Using this we have, for $\lambda_{\star}<s_{i}\leq u/2$,

$\displaystyle\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u)}$ $\displaystyle=(1-\eta
s_{i})^{t^{\star}(s_{i})}-(1-\eta s_{i})^{t^{\star}(u)}$
$\displaystyle=(1-\eta s_{i})^{t^{\star}(u)}\left((1-\eta
s_{i})^{t^{\star}(s_{i})-t^{\star}(u)}-1\right)$ $\displaystyle\leq(1-\eta
s_{i})^{t^{\star}(u)}\left(\exp(-\eta
s_{i}(t^{\star}(s_{i})-t^{\star}(u)))-1\right)$
$\displaystyle\leq\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\left(\exp\left(-\frac{1}{64}\right)-1\right).$

Meanwhile for case (B), i.e., $u\geq s_{i}>u/2$, we immediately have from
$s\rightarrow t^{\star}(s)$ being decreasing that
$\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u)}=(1-\eta s_{i})^{t^{\star}(s_{i})}-(1-\eta
s_{i})^{t^{\star}(u)}\leq 0$. Finally for case (C), i.e., $s_{i}>u$, we have

$\displaystyle\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u)}\leq\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}.$

Combining these three bounds and denoting $a_{i}(u)=(1-\eta
s_{i})^{t^{\star}(u)}$ yields

$\displaystyle D\leq 2\sum_{i:s_{i}>u}\eta
a_{i}(u)+2(\exp(-\frac{1}{64})-1)\sum_{i:\lambda_{\star}<s_{i}\leq u/2}\eta
a_{i}(u)+\sum_{i=1}^{r}\eta^{2}a_{i}(u)s_{i}(1+s_{i}/\lambda_{\star}).$

The above is then negative when

$\displaystyle\frac{\sum_{i:s_{i}>u}a_{i}(u)}{\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}a_{i}(u)}+\eta\frac{\sum_{i=1}^{r}a_{i}(u)s_{i}(1+\frac{s_{i}}{\lambda_{\star}})}{2\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}a_{i}(u)}\leq 1-\exp\left(-\frac{1}{64}\right).$ (56)

We can further upper bound the terms $a_{i}(u)$. In particular for $s_{i}>u$
we have $(1-\eta
s_{i})^{t^{\star}(u)}\leq\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}$, and
for $s_{i}\leq u$ we have $(1-\eta
s_{i})^{t^{\star}(u)}\geq\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}$. With
$A(u)$ from (50), it is sufficient that $A(u)\leq 1-\exp(-\frac{1}{64}),$
where for the numerator of the second term in (56) we used that $(1-\eta
s_{i})^{t^{\star}(u)}\leq 1$ to bound
$\sum_{i=1}^{r}a_{i}(u)s_{i}(1+\frac{s_{i}}{\lambda_{\star}})\leq\sum_{i=1}^{r}b_{i}s_{i}(1+\frac{s_{i}}{\lambda_{\star}})^{2}$.

Since $t^{\star}$ is decreasing in $u$, for any $t\leq
t^{\star}(u_{\min}(\eta))$ we have $u\geq u_{\min}(\eta)$. Since $A(u)$ is
decreasing, from (49) it follows that the required condition $A(u)\leq
1-\exp(-\frac{1}{64})$ holds, concluding the proof.

Proof of (55). We now prove the inequality (55), writing $s=s_{i}$ for
simplicity. Using $\frac{x}{1+x}\leq\log(1+x)\leq x$ we immediately have

$\displaystyle
t^{\star}(s)-t^{\star}(u)=\frac{\log\left(1+\frac{s}{\lambda_{\star}}\right)}{-\log(1-\eta
s)}-\frac{\log\left(1+\frac{u}{\lambda_{\star}}\right)}{-\log(1-\eta u)}$ (57)
$\displaystyle\geq\frac{1-\eta s}{\eta
s}\log\big{(}1\\!+\\!\frac{s}{\lambda_{\star}}\big{)}-\frac{1}{\eta
u}\log\big{(}1+\frac{u}{\lambda_{\star}}\big{)}=\frac{1}{\eta}\left[\frac{\log\big{(}1\\!+\\!\frac{s}{\lambda_{\star}}\big{)}}{s}\\!-\\!\frac{\log\big{(}1\\!+\\!\frac{u}{\lambda_{\star}}\big{)}}{u}\right]\\!-\\!\log\big{(}1\\!+\\!\frac{s}{\lambda_{\star}}\big{)}.$
(58)

We then have, using the first inequality in (45), and with
$S(z)=\sqrt{1+\frac{z}{\lambda_{\star}}+\frac{1}{6}\left(\frac{z}{\lambda_{\star}}\right)^{2}}$

$\displaystyle\frac{\log\left(1+\frac{s}{\lambda_{\star}}\right)}{s}-\frac{\log\left(1+\frac{u}{\lambda_{\star}}\right)}{u}=\int_{s}^{u}\frac{1}{z}\left[\frac{1}{z}\log(1+\frac{z}{\lambda_{\star}})-\frac{1}{z+\lambda_{\star}}\right]dz$
$\displaystyle\geq\int_{s}^{u}\frac{1}{z}\left[\frac{1}{\lambda_{\star}S(z)}-\frac{1}{z+\lambda_{\star}}\right]dz=\int_{s}^{u}\frac{dz}{z(z+\lambda_{\star})}\left[\frac{1+\frac{z}{\lambda_{\star}}}{S(z)}-1\right].$
(59)

However,

$\displaystyle\frac{1+x}{\sqrt{1+x+x^{2}/6}}\geq 1+\frac{1}{8}\min(x,1).$ (60)

To see this, split into cases $x\in[0,1]$ and $x\in(1,\infty)$. For the case
$x\in[0,1]$ consider the function
$f(x)=\frac{1+x}{\sqrt{1+x+x^{2}/6}}-1-\frac{1}{8}x$. Observe that $f(0)=0$.
Computing the derivative we have
$f^{\prime}(x)=\frac{1}{2}\frac{1+x/6}{(1+x+x^{2}/6)^{3/2}}-\frac{1}{8}$. For
$0\leq x\leq 1$ we then see that
$f^{\prime}(x)\geq\frac{1}{2}\frac{1}{(2+1/6)^{3/2}}-\frac{1}{8}\geq 0$.
Therefore $f(x)$ is non-negative on $[0,1]$. Meanwhile for $x\in[1,\infty)$
consider $g(x)=\frac{1+x}{\sqrt{1+x+x^{2}/6}}-1-\frac{1}{8}$. We then see that
$g(1)=\frac{2}{\sqrt{2+1/6}}-1-\frac{1}{8}\geq 0$, while from the calculation
just above this, $g^{\prime}(x)=\frac{1}{2}\frac{1+x/6}{(1+x+x^{2}/6)^{3/2}}$,
which is non-negative. Plugging in (60) into (59) we have

$\displaystyle\frac{\log\left(1+\frac{s}{\lambda_{\star}}\right)}{s}-\frac{\log\left(1+\frac{u}{\lambda_{\star}}\right)}{u}$
$\displaystyle\geq\frac{1}{8}\int_{s}^{u}\frac{1}{z(z+\lambda_{\star})}\min(1,\frac{z}{\lambda_{\star}})dz.$

Recalling that $s>\lambda_{\star}$ in the case considered here then yields

$\displaystyle\frac{\log\left(1+\frac{s}{\lambda_{\star}}\right)}{s}-\frac{\log\left(1+\frac{u}{\lambda_{\star}}\right)}{u}$
$\displaystyle\geq\frac{1}{16}\int_{s}^{u}\frac{1}{z^{2}}dz=\frac{1}{16}\left[\frac{1}{s}-\frac{1}{u}\right].$

Plugging this into (58) and using that in the case considered here $u\geq 2s$
and by assumption $\eta s\log(1+\frac{s}{\lambda_{\star}})\leq\eta
s_{1}\log(1+\frac{s_{1}}{\lambda_{\star}})\leq\frac{1}{64}$ yields

$\displaystyle\eta
s\left(t^{\star}(s)-t^{\star}(u)\right)\geq\frac{1}{16}\left[\frac{s}{s}-\frac{s}{u}\right]-\eta
s\log\left(1+\frac{s}{\lambda_{\star}}\right)$
$\displaystyle\geq\frac{1}{32}-\eta
s\log\left(1+\frac{s}{\lambda_{\star}}\right)\geq\frac{1}{64},$

as required.

####  B.8.4 Proof of Theorem 8

From Lemma 2, and recalling (40), we know the error is decreasing for $t\leq
t^{\star}(u_{\min})$. Therefore the optimal number of iterations is greater
than or equal to $t^{\star}(u_{\min})$. Thus we have

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))$
$\displaystyle=\min_{j\in\\{1,\dots,t\\}}\left(\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,j})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]\right)$
$\displaystyle=\min_{j\in\\{\lceil
t^{\star}(u_{\min}(\eta))\rceil,\dots,t\\}}\left(\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\eta,j})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]\right)$
$\displaystyle\geq\min_{j\in\\{\lceil
t^{\star}(u_{\min}(\eta))\rceil,\dots,t\\}}\frac{\sigma^{2}}{n}\sum_{i:s_{i}>u_{\min}(\eta)}\frac{1}{\lambda_{\star}}\left((1-\eta
s_{i})^{j}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle\geq\frac{\sigma^{2}}{n}\sum_{i:s_{i}>u_{\min}(\eta)}\frac{1}{\lambda_{\star}}\left(\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u_{\min}(\eta))}\right)^{2}$
$\displaystyle\geq\frac{\sigma^{2}}{n}\sum_{i:s_{i}>2u_{\min}(\eta)}\frac{1}{\lambda_{\star}}\left(\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u_{\min}(\eta))}\right)^{2},$ (61)

where we use that $\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}=(1-\eta
s_{i})^{t^{\star}(s_{i})}\geq(1-\eta
s_{i})^{t^{\star}(u_{\min}(\eta))}\geq(1-\eta s_{i})^{j}$ for
$s_{i}>u_{\min}(\eta)$ and $j\geq\lceil t^{\star}(u_{\min}(\eta))\rceil$.
Since $\lambda_{\star}<u_{\min}(\eta)<s_{i}/2$ we can then lower bound using
inequality (55), which implies $\eta
u_{\min}(\eta)(t^{\star}(u_{\min}(\eta))-t^{\star}(s_{i}))\geq\frac{1}{64}$
and thus also $\eta
s_{i}(t^{\star}(u_{\min}(\eta))-t^{\star}(s_{i}))\geq\frac{1}{32}$

$\displaystyle\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}-(1-\eta
s_{i})^{t^{\star}(u_{\min}(\eta))}$ $\displaystyle=(1-\eta
s_{i})^{t^{\star}(s_{i})}(1-(1-\eta
s_{i})^{t^{\star}(u_{\min}(\eta))-t^{\star}(s_{i})})$
$\displaystyle\geq(1-\eta s_{i})^{t^{\star}(s_{i})}(1-\exp(-\eta
s_{i}(t^{\star}(u_{\min}(\eta))-t^{\star}(s_{i}))))$ $\displaystyle\geq(1-\eta
s_{i})^{t^{\star}(s_{i})}\left(1-\exp\left(-\frac{1}{32}\right)\right)$
$\displaystyle=\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\left(1-\exp\left(-\frac{1}{32}\right)\right)\geq\frac{1}{2}\frac{\lambda_{\star}}{s_{i}}\left(1-\exp\left(-\frac{1}{32}\right)\right).$

Plugging in this lower bound into (61) then yields the result.

####  B.8.5 Proof of Proposition 9

Since $s_{i}=\exp(-\rho(i-1))$, we have the following upper bound, using that
$\exp(\rho(i-1))\leq\int_{i-1}^{i}\exp(\rho x)dx$ and recalling the definition
of $b_{i}$ and that $b_{i}\leq\frac{\lambda_{\star}}{s_{i}}$:

$\displaystyle\sum_{i:s_{i}>u}b_{i}$
$\displaystyle\leq\lambda_{\star}\sum_{i=1}^{\lceil\frac{1}{\rho}\log(1/u)\rceil}\exp(\rho(i-1))$
$\displaystyle\leq\lambda_{\star}\int_{0}^{1+\frac{1}{\rho}\log(1/u)}\exp(\rho
x)dx=\frac{\lambda_{\star}}{\rho}\left(\frac{e^{\rho}}{u}-1\right)\leq\frac{\lambda_{\star}e^{\rho}}{\rho
u}.$

Using that $\exp(\rho(i-1))\geq\int_{i-2}^{i-1}\exp(\rho x)dx$, as well as
that $s_{i}>\lambda_{\star}$—which implies
$b_{i}\geq\frac{1}{2}\frac{\lambda_{\star}}{s_{i}}$—we have

$\displaystyle\sum_{i:\lambda_{\star}<s_{i}\leq u/2}b_{i}$
$\displaystyle\geq\frac{\lambda_{\star}}{2}\sum_{i=\lceil
1+\frac{1}{\rho}\log(2/u)\rceil}^{\lceil\frac{1}{\rho}\log(1/\lambda_{\star})\rceil}\exp(\rho(i-1))\geq\frac{\lambda_{\star}}{2}\int_{\lceil
1+\frac{1}{\rho}\log(2/u)\rceil-2}^{\lceil\frac{1}{\rho}\log(1/\lambda_{\star})\rceil-1}\exp(x\rho)dx$
$\displaystyle\geq\frac{\lambda_{\star}}{2}\int_{\frac{1}{\rho}\log(2/u)}^{\frac{1}{\rho}\log(1/\lambda_{\star})-1}\exp(x\rho)dx=\frac{\lambda_{\star}}{2}\frac{1}{\rho}\left(\frac{1}{e\lambda_{\star}}-\frac{2}{u}\right)=\frac{1}{2\rho}\left(e^{-1}-\frac{2\lambda_{\star}}{u}\right).$

Taking the ratio of the bounds in the above two displays we then have

$\displaystyle\frac{\sum_{i:s_{i}>u}b_{i}}{\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}b_{i}}\leq 2e^{\rho+1}\frac{\lambda_{\star}}{u-2e\lambda_{\star}}.$

For the second term in the numerator of (50) we have, since $s_{i}\leq 1$ and
$\lambda_{\star}\leq 1$,

$\displaystyle\sum_{i=1}^{r}b_{i}s_{i}(1+\frac{s_{i}}{\lambda_{\star}})^{2}$
$\displaystyle=\sum_{i=1}^{r}s_{i}^{2}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\leq\frac{2}{\lambda_{\star}}\sum_{i=1}^{r}s_{i}=\frac{2}{\lambda_{\star}}\sum_{1=1}^{r}\exp(-\rho(i-1))$
$\displaystyle\leq\frac{2}{\lambda_{\star}}\left(1+\int_{0}^{r}\exp(-\rho
x)dx\right)<\frac{2}{\lambda_{\star}}\left(1+\int_{0}^{\infty}\exp(-\rho
x)dx\right)=\frac{2}{\lambda_{\star}\rho}.$

Using this bound and the lower bound for $\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}b_{i}$ from above we then have

$\displaystyle\frac{\sum_{i=1}^{r}b_{i}s_{i}(1+\frac{s_{i}}{\lambda_{\star}})^{2}}{\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}b_{i}}\leq\frac{\frac{2}{\lambda_{\star}\rho}}{\frac{1}{2\rho}(\frac{1}{e}-\frac{2\lambda_{\star}}{u})}=\frac{1}{\lambda_{\star}}\frac{4e}{1-\frac{2e\lambda_{\star}}{u}}$

and bringing everything together yields

$\displaystyle A(u)\leq
2e^{\rho+1}\frac{\lambda_{\star}}{u-2e\lambda_{\star}}+\frac{\eta}{\lambda_{\star}}\frac{4e}{1-\frac{2e\lambda_{\star}}{u}}.$
(62)

For $u=2e\lambda_{\star}\left(1+2e^{\rho}(1-e^{-\frac{1}{64}})^{-1}\right)$,
we have

$\displaystyle
2e^{\rho+1}\frac{\lambda_{\star}}{u-2e\lambda_{\star}}=\frac{1}{2}\left(1-\exp\left(-\frac{1}{64}\right)\right).$

Moreover, by (51),

$\displaystyle\frac{\eta}{\lambda_{\star}}\frac{4e}{1-\frac{2e\lambda_{\star}}{u}}\leq\frac{1}{2}(1-e^{-\frac{1}{64}})\frac{e^{\rho}}{1+e^{\rho}}=\frac{1}{2}\left(1-\exp\left(-\frac{1}{64}\right)\right).$

Thus, from (62) and (49), the conclusion follows.

####  B.8.6 Proof of Proposition 10

This argument follows the proof of Proposition 9. Since $s_{i}=i^{-\alpha}$,
we have, using that $i^{\alpha}\leq\int_{i}^{i+1}x^{\alpha}dx$

$\displaystyle\sum_{i:s_{i}>u}b_{i}$
$\displaystyle\leq\lambda_{\star}\sum_{i=1}^{\lceil
u^{-1/\alpha}\rceil-1}i^{\alpha}\leq\lambda_{\star}\int_{1}^{1+u^{-1/\alpha}}x^{\alpha}dx$
$\displaystyle=\frac{\lambda_{\star}}{\alpha+1}\left((1+u^{-1/\alpha})^{1+\alpha}-1\right)\leq\frac{2^{1+\alpha}\lambda_{\star}}{\alpha+1}u^{-(1+1/\alpha)}.$

Meanwhile using the lower bounds $i^{\alpha}\geq\int_{i-1}^{i}x^{\alpha}dx$
and $b_{i}\geq\frac{1}{2}\frac{\lambda_{\star}}{s_{i}}$ we have

$\displaystyle\sum_{i:\lambda_{\star}<s_{i}\leq
u/2}b_{i}\geq\frac{\lambda_{\star}}{2}\sum_{i=\lceil(u/2)^{-1/\alpha}\rceil}^{\lceil\lambda_{\star}^{-1/\alpha}\rceil-1}i^{\alpha}\geq\frac{\lambda_{\star}}{2}\int_{\lceil(u/2)^{-1/\alpha}\rceil-1}^{\lceil\lambda_{\star}^{-1/\alpha}\rceil-1}x^{\alpha}dx\geq\frac{\lambda_{\star}}{2}\int_{(u/2)^{-1/\alpha}}^{\lambda_{\star}^{-1/\alpha}-1}x^{\alpha}dx$
$\displaystyle\geq\frac{\lambda_{\star}}{2(\alpha\\!+\\!1)}\\!\left((\lambda_{\star}^{-1/\alpha}\\!-\\!1)^{\alpha+1}\\!-\\!(u/2)^{-(1+1/\alpha)}\right)\\!\geq\\!\frac{\lambda_{\star}}{2^{2+\alpha}(\alpha\\!+\\!1)}(\lambda_{\star}^{-(1+1/\alpha)}\\!-\\!2^{2+\alpha+1/\alpha}u^{-(1+1/\alpha)}),$

where in the last inequality we have used that
$\lambda_{\star}^{-1/\alpha}-1\geq\frac{1}{2}\lambda_{\star}^{-1/\alpha}$
since $\lambda_{\star}\leq 2^{-\alpha}$. Since $s_{i}\leq 1$ and
$\lambda_{\star}\leq 1$

$\displaystyle\sum_{i=1}^{r}b_{i}s_{i}(1+\frac{s_{i}}{\lambda_{\star}})^{2}$
$\displaystyle\leq\frac{2}{\lambda_{\star}}\sum_{i=1}^{r}s_{i}\leq\frac{2}{\lambda_{\star}(\alpha-1)}(1-r^{1-\alpha})\leq\frac{2}{\lambda_{\star}(\alpha-1)}.$

Combining these bounds we have

$\displaystyle A(u)$
$\displaystyle\leq\frac{2^{3+2\alpha}\lambda_{\star}^{1+1/\alpha}+\frac{\eta}{\lambda_{\star}}2^{3+\alpha}\frac{\alpha+1}{\alpha-1}\lambda_{\star}^{1/\alpha}u^{1+1/\alpha}}{u^{1+1/\alpha}-2^{2+\alpha+1/\alpha}\lambda_{\star}^{1+1/\alpha}}.$
(63)

Now for
$u=2^{1+\alpha}\lambda_{\star}\left(1+2^{4+3\alpha}(1-e^{-\frac{1}{64}})^{-1}\right)^{\alpha/(1+\alpha)}$
we have

$\displaystyle
2^{3+2\alpha}\frac{\lambda_{\star}^{1+1/\alpha}}{u^{1+1/\alpha}-2^{2+\alpha+1/\alpha}\lambda_{\star}^{1+1/\alpha}}=\frac{1}{2}\big{(}1-e^{-\frac{1}{64}}\big{)}.$

From (52), bounding $\frac{1}{17\times
2^{\alpha}}=\frac{1}{2^{4+\alpha}}\frac{2^{4}}{1+2^{4}}\leq\frac{1}{2^{4+\alpha}}\frac{2^{4+3\alpha}}{1-e^{-\frac{1}{64}}+2^{4+3\alpha}}$,

$\displaystyle\frac{\frac{\eta}{\lambda_{\star}}2^{3+\alpha}\frac{\alpha+1}{\alpha-1}\lambda_{\star}^{1/\alpha}u^{1+1/\alpha}}{u^{1+1/\alpha}-2^{2+\alpha+1/\alpha}\lambda_{\star}^{1+1/\alpha}}\leq\frac{1}{2}\frac{\frac{2^{4+3\alpha}}{1-e^{-\frac{1}{64}}+2^{4+3\alpha}}u^{1+1/\alpha}}{u^{1+1/\alpha}-2^{2+\alpha+1/\alpha}\lambda_{\star}^{1+1/\alpha}}$
$\displaystyle=\big{(}1-e^{-\frac{1}{64}}\big{)}\frac{(u/\lambda_{\star})^{1+1/\alpha}}{1-e^{-\frac{1}{64}}+2^{4+3\alpha}}\leq\frac{1}{2}\big{(}1-e^{-\frac{1}{64}}\big{)}.$

Thus, from (63), we find that $A(u)\leq 1-\exp(-\frac{1}{64})$ holds for this
value of $u$, hence we have $u_{\min}\leq u$.

###  B.9 Ridge Regression with a Logarithmic Grid

In this section we provide proofs for the results associated to tuning ridge
regression with a logarithmic grid. Precisely, let us consider the ridge
regression estimator with the sequence of regularization parameters on a
logarithmic grid. Thus, for $k\geq j\geq 1$,

$\displaystyle\lambda_{j}=e^{\frac{j-1}{k-1}\log(\lambda_{\min})}.$

We have $\lambda_{1}=1$ and $\lambda_{k}=\lambda_{\min}$ i.e., the sequence is
decreasing as a function of the index $j$, and covers the range
$[\lambda_{\min},1]$. Naturally, we let the set of estimators then be denoted

$\displaystyle\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k):=\\{\widehat{\beta}_{\lambda}:\lambda=\lambda_{j},j\in\\{1,\dots,k\\}\\}.$

Given this, we can then bound the ratio of the excess risks of ridge with a
logarithmic grid and gradient descent. This is summarized within the proof of
Theorem 7 which is provided in the following Section B.9.1. This is followed
by the proof of Proposition 6 presented within Section B.9.2.

####  B.9.1 Proof of Theorem 7

We split the proof into two subsections: one for the upper bound and one for
the lower bound. We begin with the upper bound.

Upper Bound Consider the lower bound from Proposition 6 for ridge regression
with a logarithmic grid and the upper bound of gradient descent from
Proposition 2. Using these results, the ratio of errors is then upper bounded
as

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq 216\frac{\int G^{\text{GD}}(s)d\widehat{H}(s)}{\int
G^{\text{$\log$-Ridge}}(s)d\widehat{H}(s)}.$

Considering the lower bound

$\displaystyle\int
G^{\text{$\log$-Ridge}}(s)d\widehat{H}(s)\geq\frac{1}{d}\frac{1}{8}\frac{\log^{2}(1/\lambda_{\min})}{(k-1)^{2}}\Big{(}\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\Big{)}$

alongside the equality (29) for $\int G^{\text{GD}}(s)d\widehat{H}(s)$ leads
to the upper bound

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\frac{1728}{\log^{2}(1/\lambda_{\min})}\Bigg{[}k^{2}\frac{\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}}{\Big{(}\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\Big{)}}$
$\displaystyle\quad\quad\quad\quad+k^{2}\frac{\frac{1}{\lambda_{\star}^{4}}\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}}{\Big{(}\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\Big{)}}+\frac{1}{\lambda_{\min}^{2}}\frac{\sum_{i:s_{i}\leq\lambda_{\star}^{2}/(k\lambda_{\min})}s_{i}}{\Big{(}\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\Big{)}}\Bigg{]}$
$\displaystyle\leq\frac{1728}{\log^{2}(1/\lambda_{\min})}\Bigg{[}k^{2}\lambda_{\star}^{3}\frac{\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}}{\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}}+\frac{k^{2}}{\lambda_{\star}^{2}}\frac{\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}}{\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}}+\frac{\lambda_{\star}^{2}}{\lambda_{\min}^{2}}\Bigg{]}.$

Using the bounds (30), (31) and (32) for
$\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}$,
$\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}$ and
$\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}$
respectively, we find

$\displaystyle\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}\leq\lambda_{\star}^{-(2+1/\alpha)},\qquad\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\geq\frac{r^{1-\alpha}}{2},\qquad\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}\leq\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min}).$

Hence

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\frac{3456}{\log^{2}(1/\lambda_{\min})}$
$\displaystyle\quad\quad\quad\quad\times\Big{[}\frac{k^{2}}{r^{1-\alpha}}\Big{(}\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\frac{1}{\lambda_{\star}^{2}}\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\Big{)}+\frac{\lambda_{\star}^{2}}{\lambda_{\min}^{2}}\Big{]}.$

Following the proof of Theorem 1, choosing

$\displaystyle\overline{r}_{\alpha,\lambda_{\star},k,\lambda_{\min}}=\Big{[}\frac{\lambda_{\min}^{2}k^{2}}{\lambda_{\star}^{2}}\Big{(}\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\frac{1}{\lambda_{\star}^{2}}\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\Big{)}\Big{]}^{1/(1-\alpha)},$

we see that once $r\geq\overline{r}_{\alpha,\lambda_{\star},k,\lambda_{\min}}$
we find

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)\leq\frac{6912}{\log^{2}(1/\lambda_{\min})}\frac{\lambda_{\star}^{2}}{\lambda_{\min}^{2}},$

as required. Plugging in the definition of
$\lambda_{\min}=d\sigma_{\min}^{2}/n$ and $\lambda_{\star}=d\sigma^{2}/n$ then
yields the result.

Lower Bound For ridge regression with a logarithmic grid, considering the
upper bound from Proposition 6 to get

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k))$
$\displaystyle\leq\lambda_{\star}\int
G^{\text{$\log$-Ridge}}(s)d\widehat{H}(s)$
$\displaystyle\leq\frac{\lambda_{\star}}{d}\frac{\log^{2}(1/\lambda_{\min})}{(k-1)^{2}}\Big{(}\lambda_{\star}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\Big{)}$
$\displaystyle\leq
2\frac{\lambda_{\star}}{d}\frac{\log^{2}(1/\lambda_{\min})}{(k-1)^{2}}\frac{1}{\lambda_{\star}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}$

where the second equality comes from
$\sum_{i:s_{i}<\lambda_{\star}}s_{i}\geq\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}$
when $r\geq 2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha})$, see equation
(34).

Meanwhile, for gradient descent follow the proof of Theorem 3, precisely,
combine equations (35) and (36) which arise from applying Proposition 2, to
get the lower bound

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,k))$
$\displaystyle\geq\frac{1}{16}\min\\{1-\kappa,\kappa\\}^{2}\lambda_{\star}\left(\frac{1}{\lambda_{\min}k}\right)^{2}\frac{1}{d}\sum_{i:s_{i}\leq\frac{\lambda_{\star}^{2}\kappa}{4k\lambda_{\min}}}s_{i}$

Taking the ratio of the risks and applying the upper and lower bounds yields

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\geq\frac{\min\\{1-\kappa,\kappa\\}^{2}}{32\log^{2}(1/\lambda_{\min})}\Big{(}1-\frac{1}{k}\Big{)}^{2}\frac{\lambda_{\star}^{2}}{\lambda_{\min}^{2}}\frac{\sum_{i:s_{i}\leq\frac{\lambda_{\star}^{2}\kappa}{4k\lambda_{\min}}}s_{i}}{\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}}$
$\displaystyle\geq\frac{\min\\{1-\kappa,\kappa\\}^{2}}{128\log^{2}(1/\lambda_{\min})}\frac{\lambda_{\star}^{2}}{\lambda_{\min}^{2}}\Big{(}1\\!-\\!\frac{2}{1\\!-\\!\alpha}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha-1}\\!\\!\frac{1}{r^{1-\alpha}}\Big{)}$

where the second inequality arises from $k\geq 2$ and the lower bound on the
ratio of series (37). If we then let

$\displaystyle\underline{r}_{\alpha,\lambda_{\star},k,\lambda_{\min}}=\max\Big{\\{}2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha}),\Big{(}\frac{4}{1-\alpha}\Big{)}^{1/(1-\alpha)}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha}\Big{\\}}$

then we have the desired lower bound once
$r\geq\underline{r}_{\alpha,\lambda_{\star},k,\lambda_{\min}}$.

####  B.9.2 Proof of Proposition 6

Since $\lambda_{\star}\in(\lambda_{\min},1)$ there exists a $2\leq
j_{\star}\leq k$ such that
$\lambda_{j_{\star}}<\lambda_{\star}<\lambda_{j_{\star}-1}$. Furthermore,
there exists an $\epsilon\in(0,1)$ such that
$\lambda_{\star}=\exp\big{(}\frac{j_{\star}-2+\epsilon}{k-1}\log(\lambda_{\min})\big{)}$.
Leveraging this alongside the risk being monotonic yields

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k))$
$\displaystyle=\min_{j=1,\dots,k}\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{j}})]-\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s)$
$\displaystyle=\min_{j=1,\dots,k}\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left(\frac{\lambda_{j}}{\lambda_{j}+s_{i}}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle=\min_{j=1,\dots,k}\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\left(\frac{\lambda_{j}}{\lambda_{j}+s_{i}}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle=\min_{j=j_{\star},j_{\star}-1}\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\left(\frac{1}{s_{i}}+\frac{1}{\lambda_{\star}}\right)\frac{s^{2}_{i}}{(\lambda_{j}+s_{i})^{2}(\lambda_{\star}+s_{i})^{2}}(\lambda_{j}-\lambda_{\star})^{2}$

We now set to bound this minimum for the two cases $j=j_{\star},j_{\star}-1$.
Begin by noting that

$\displaystyle|\lambda_{j_{\star}}-\lambda_{\star}|$
$\displaystyle=\lambda_{\star}\Big{|}\frac{\lambda_{j_{\star}}}{\lambda_{\star}}-1\Big{|}$
$\displaystyle=\lambda_{\star}\big{|}\exp\Big{(}-\frac{1-\epsilon}{k-1}\log(1/\lambda_{\min})\Big{)}-1\big{|}$
$\displaystyle=\lambda_{\star}\Big{(}1-\exp\Big{(}-\frac{1-\epsilon}{k-1}\log(1/\lambda_{\min})\Big{)}\Big{)},$
$\displaystyle|\lambda_{j_{\star}-1}-\lambda_{\star}|$
$\displaystyle=\lambda_{j_{\star}-1}\Big{|}1-\frac{\lambda_{\star}}{\lambda_{j_{\star}-1}}\Big{|}=\lambda_{j_{\star}-1}\Big{(}1-\exp\big{(}-\frac{\epsilon}{k-1}\log(1/\lambda_{\min})\big{)}\Big{)}.$

Moreover, since $k\geq 1+3\log(1/\lambda_{\min})\geq
1+\frac{\epsilon\log(1/\lambda_{\min})}{\log(2)}$ and
$\lambda_{\star}=\exp\big{(}-\frac{\epsilon\log(1/\lambda_{\min})}{k-1}\big{)}\lambda_{j_{\star}-1}$
we have $2\lambda_{\star}\geq\lambda_{j_{\star}-1}\geq\lambda_{\star}$, and
thus, can bound for $i=1,\dots,r$

$\displaystyle\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\leq\frac{\lambda_{j_{\star}-1}}{\lambda_{j_{\star}-1}+s_{i}}\leq
2\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}.$

Similarly,
$\lambda_{\star}=\exp\big{(}\frac{(1-\epsilon)\log(1/\lambda_{\min})}{k-1}\big{)}\lambda_{j_{\star}}\leq
2\lambda_{j_{\star}}$ and thus
$\frac{1}{2}\lambda_{\star}\leq\lambda_{j_{\star}}\leq\lambda_{\star}$ leading
to

$\displaystyle\frac{1}{\lambda_{\star}+s_{i}}\leq\frac{1}{\lambda_{j_{\star}}+s_{i}}\leq\frac{2}{\lambda_{\star}+s_{i}}$

Utilising these two facts as well as the inequality $2\geq u\geq 0$,
$\frac{u}{3}\leq 1-e^{-u}\leq u$, since $k\geq 1+\log(1/\lambda_{\min})$ we
get the desired upper and lower bounds.

##  Appendix C Proofs for Orthogonal Design

In this section we present the proofs associated to the orthogonal design
setting. This section is structured as follows. Section C.1 presents the proof
of Theorem 6. Section C.2 presents the proof of Proposition 3. Section C.3
presents the proof of Proposition 4.

###  C.1 Proof of Theorem 6

By (26), using $n=d$ and $\sigma=1$, the excess risk of an estimator
$\Phi_{j}$ with $\phi_{j}=\Phi_{j}(s)$ is

$\displaystyle\frac{(1+\psi s)}{s}\left(\phi_{j}-\frac{1}{1+\psi
s}\right)^{2}=\frac{1}{s}\left(\sqrt{1+\psi
s}\cdot\phi_{j}-\sqrt{\frac{1}{1+\psi s}}\right)^{2}.$

Since $\psi\in[\psi_{-},\psi_{+}]$, for $x:=\sqrt{1+\psi s}$ we have
$x\in[x_{-},x_{+}]$. We can equivalently write the minimax excess risk
objective (19) as

$\inf_{T_{k}=\\{\phi_{1},\ldots,\phi_{k}\\}\in
E}\,\sup_{x\in[x_{-},x_{+}]}\,\min_{j\in[k]}\,\left(x\phi_{j}-\frac{1}{x}\right)^{2}.$

Moreover, by monotonicity of the transform $z\to z^{2}$ for $z\geq 0$, we can
equivalently study the objective

$\displaystyle\inf_{T_{k}=\\{\phi_{1},\ldots,\phi_{k}\\}\in
E}\,\sup_{x\in[x_{-},x_{+}]}\,\min_{j\in[k]}\,\left|x\phi_{j}-\frac{1}{x}\right|.$
(64)

Define the function $g:(0,\infty)\times(0,\infty)\mapsto[0,\infty)$ by
$g(x,l)=|xl-\frac{1}{x}\big{|}$. For any fixed $l>0$, the one-variable
function $x\to g(x,l)$ has a unique zero for $x^{*}(l)=1/\sqrt{l}$. Moreover,
$g(x,l)=xl-\frac{1}{x}$ for $x\geq x^{*}$ and $g(x,l)=\frac{1}{x}-xl$ for
$x<x^{*}$. Further, the map $l\mapsto x^{*}(l)$ is monotonically decreasing
for $l\in(0,\infty)$. Thus, if $x>x^{*}(l)$, then $g(x,l)<g(x,l^{\prime})$.
Similarly, for $l<l^{\prime}$ and $x<x^{*}(l^{\prime})$, we have
$g(x,l)>g(x,l^{\prime})$.

In the interval $x\in[x^{*}(l^{\prime}),x^{*}(l)]$, we have $g(x,l)\leq
g(x,l^{\prime})$ if and only if

$\displaystyle\frac{1}{x}-xl$ $\displaystyle\leq xl^{\prime}-\frac{1}{x},$

or also $\sqrt{\frac{2}{l+l^{\prime}}}\leq x$.

Thus, for a grid $\phi_{1}\leq\phi_{2}\leq\ldots\leq\phi_{k}$, defining
$q_{i}=\sqrt{\frac{2}{\phi_{i}+\phi_{i+1}}}$, with $q_{k}:=0$, $q_{0}=\infty$,
and thus

$q_{k}\leq q_{n-1}\leq\ldots\leq q_{1}\leq q_{0},$

we have that the minimum of the functions $g(x,\phi_{i})$, $i=0,\ldots,k$ has
a value equal to $g(x,\phi_{j})$ precisely for $x\in I_{j}:=[q_{j},q_{j-1}]$.
In addition, the functions $g(x,\phi_{j})$, $g(x,\phi_{j+1})$ are equal at
$q_{j}$, $j=1,\ldots,k-1$.

Moreover, the value at the maximum on the interval $I_{j}$ (for
$j=1,\ldots,k-1$) can be verified to be

$g(q_{j},\phi_{j})=g(q_{j},\phi_{j+1})=\frac{\phi_{j+1}-\phi_{j}}{\sqrt{2(\phi_{j+1}+\phi_{j})}}.$

In (64), we need to find the supremum for $x\in[x_{-},x_{+}]$, so we can
restrict to grid points such that $1/x_{+}^{2}\leq\phi_{1}$, $\phi_{k}\leq
1/x_{-}^{2}$. Since we also need to consider the boundary values, problem (64)
simplifies to

$\displaystyle\inf_{x_{+}^{-2}\leq\phi_{1}\leq\ldots\leq\phi_{k}\leq
x_{-}^{-2}}\,m(\phi_{1},\ldots,\phi_{k})$ (65)
$\displaystyle:=\max\left(\frac{1}{x_{-}}-x_{-}\phi_{k},\max_{j=1,\ldots,k-1}\frac{\phi_{j+1}-\phi_{j}}{\sqrt{2(\phi_{j+1}+\phi_{j})}},x_{+}\phi_{1}-\frac{1}{x_{+}}\right).$
(66)

Now, we provide a compactness and “infinite descent” argument to find the
minimizer and prove that the minimum is achieved. We claim that the solution
is achieved when the $k+1$ quantities in (65) are equal. Otherwise, we argue
that we can decrease the objective. Suppose that the $k+1$ terms are not all
equal. Then there is an index $j\in\\{2,\ldots,k-1\\}$ such that
$\max(t_{j-1},t_{j+1})\leq t_{j}$, with $t_{j}=m$ achieving the maximum, and
at least one inequality is strict. Suppose without loss of generality that
$t_{j-1}<t_{j}$. Then, $t_{j}=t_{j}(\phi_{j-1},\phi_{j})$ is strictly
increasing in $\phi_{j}$, and strictly decreasing in $\phi_{j-1}$. This is
readily verified by elementary calculus. Thus, if we decrease $\phi_{j}$, then
we decrease $t_{j}$, while increasing $t_{j-1}$. By continuity, after
decreasing $\phi_{j}$ sufficiently, we will have $t_{j-1}=t_{j}$. This
procedure keeps $\phi_{j}\geq\phi_{j-1}$, because
$t_{j}(\phi_{j-1},\phi_{j-1})=0$, which is less than $m$, as $m>0$ must be
strictly positive (otherwise all terms must be equal, which is a
contradiction).

This shows that if not all $t_{j}$ are equal, then we can decrease $m$. Now,
by the compactness of $x_{+}^{-2}\leq\phi_{1}\leq\ldots\leq\phi_{k}\leq
x_{-}^{-2}$ and the continuity of $m$, $m$ has a minimum that is attained.
Since the minimum cannot be attained when any $t_{j}$ are unequal, at the
minimizing $\phi_{j}$, all $t_{j}$ are equal.

In conclusion, the minimax optimal grid is characterized as a sequence

$\frac{1}{1+\psi s_{+}}\leq\phi_{1}\leq\ldots\leq\phi_{k}\leq\frac{1}{1+\psi
s_{-}}$

such that

$\frac{1}{x_{-}}-x_{-}\phi_{k}=x_{+}\phi_{1}-\frac{1}{x_{+}}=\frac{\phi_{j+1}-\phi_{j}}{\sqrt{2(\phi_{j+1}+\phi_{j})}},\,j=1,\ldots,k-1.$

Let $\phi_{1}\geq x_{+}^{-2}$ and $c=x_{+}\phi_{1}-\frac{1}{x_{+}}\geq 0$. If
$c=0$, then all grid points $\phi_{j}$ must be equal, thus
$\psi_{-}=\psi_{+}$, and the conclusion clearly holds. Otherwise, $c>0$ and
$\phi_{1}>x_{+}^{-2}$. The above display implies the quadratic equation

$\phi_{j+1}^{2}-2\phi_{j+1}(\phi_{j}+c^{2})+\phi_{j}^{2}-2c^{2}\phi_{j}=0$

for $\phi_{j+1}$. This has the only solution $\phi_{j+1}>\phi_{j}$ given by

$\displaystyle\phi_{j+1}$
$\displaystyle=\phi_{j}+c\left(c+\sqrt{c^{2}+4\phi_{j}}\right).$

Then $u_{j}:=c^{2}+4\phi_{j}$ satisfies

$\displaystyle u_{j+1}=u_{j}+4c(c+\sqrt{u_{j}})=(\sqrt{u_{j}}+2c)^{2}.$

Thus $v_{j}:=\sqrt{u_{j}}/2$ is an arithmetic progression with
$v_{j+1}=v_{j}+c$. From $c=x_{+}\phi_{1}-1/x_{+}$ and
$v_{1}=\sqrt{\phi_{1}+c^{2}/4}$, we find
$v_{1}=\frac{1}{{x_{+}}}+\frac{c}{2}$; and similarly
$v_{k}=\frac{1}{{x_{-}}}-\frac{c}{2}$. Using $v_{k}=v_{1}+(k-1)c$, we find
$c=\frac{1}{k}\left(\frac{1}{{x_{-}}}-\frac{1}{{x_{+}}}\right)$. This finishes
the proof.

###  C.2 Proof of Proposition 3

Minimizing over $j$, for a fixed $x$. With the notations from Theorem 6, we
need to evaluate

$\sup_{x\in[x_{-},x_{+}]}\,\min_{j\in[k]}\,\left(x\phi_{j}-\frac{1}{x}\right)^{2}$

for $\phi_{j}=(j/k)/[(j/k)+s]=j/(j+a)$, where $a=ks$. For a fixed $x$ the
minimum over $j$ is achieved when $\phi_{j}$ is closest to $1/x^{2}$, i.e., at
either $\lfloor b\rfloor$ or $\lceil b\rceil$ (where $\lceil b\rceil$ denotes
the ceiling of $b$), with

$b:=\frac{a}{x^{2}-1},$

or, the unique integer $j\in[k]$ closest to these two values if neither
belongs to $[k]$. One can verify that the minimum is achieved at $\lfloor
b\rfloor$ or $\lceil b\rceil$ iff $\lfloor b\rfloor\leq k$, or equivalently
$b<k+1$. Since $\psi_{-}>k/(k+1)$, this condition holds for all
$x\in[x_{-},x_{+}]$. As in the proof of Theorem 6, we can equivalently study
the objective, for $j=1,\ldots,k$

$\displaystyle o_{j}:=\left|x\phi_{j}-\frac{1}{x}\right|.$

The minimizer is either $j_{b}=\lfloor b\rfloor$ or $j_{b}+1$. Writing
$b=j_{b}+\tau_{b}$, for some $\tau_{b}\in[0,1)$, using that
$b+a=ax^{2}/(x^{2}-1)$ the objective at $j_{b}$ is

$\displaystyle o_{j_{b}}$
$\displaystyle=x\left|\frac{j_{b}}{j_{b}+a}-\frac{1}{x^{2}}\right|=xa\frac{\tau_{b}}{(j_{b}+a)(b+a)}=\frac{\tau_{b}}{j_{b}+a}\frac{x^{2}-1}{x}.$

We can also write $x^{2}-1=a/b$ and $x=(1+a/b)^{1/2}$. Using
$b=j_{b}+\tau_{b}$, we can express

$\displaystyle o_{j_{b}}$
$\displaystyle=\frac{\tau_{b}}{j_{b}+a}\frac{a/b}{(1+a/b)^{1/2}}=\frac{\tau_{b}}{j_{b}+a}\frac{a/[j_{b}+\tau_{b}]}{(1+a/[j_{b}+\tau_{b}])^{1/2}}.$

Similarly, one can verify that the objective at $j_{b}+1$ is

$\displaystyle o_{j_{b}+1}$
$\displaystyle=\frac{1-\tau_{b}}{j_{b}+1+a}\frac{a/[j_{b}+\tau_{b}]}{(1+a/[j_{b}+\tau_{b}])^{1/2}}.$

The objective for a fixed $x$ (or equivalently for a fixed $b$) equals the
minimum of $o_{j_{b}}$ and $o_{j_{b}+1}$. Since $x$ ranges in
$x\in[x_{-},x_{+}]=[\sqrt{1+s\psi_{-}},\sqrt{1+s\psi_{+}}]$, we have that
$b=sk/(x^{2}-1)$ ranges in $b\in[b_{-},b_{+}]=[k/\psi_{+},k/\psi_{-}]$. Thus,
the objective can be written as

$\sup_{b\in[k/\psi_{+},k/\psi_{-}]}\,Q(j_{b},\tau_{b}):=\frac{a/[j_{b}+\tau_{b}]}{(1+a/[j_{b}+\tau_{b}])^{1/2}}\min\left(\frac{\tau_{b}}{j_{b}+a},\frac{1-\tau_{b}}{j_{b}+1+a}\right)$
(67)

where $b=j_{b}+\tau_{b}$, and $j_{b}=\lfloor b\rfloor$ is the integer part of
$b$, while $\tau_{b}\in[0,1)$ is the fractional part.

Maximizing over $x$. To maximize over $x$, it is enough to maximize over
$b=j_{b}+\tau_{b}$, and we maximize over each component separately. It is
readily verified that the objective $Q$ from (67) is decreasing in $j_{b}$,
for any fixed $\tau_{b}$. Hence, it achieves its maximum for the smallest
possible integer $j_{b}$ such that
$b=j_{b}+\tau_{b}\in[k/\psi_{+},k/\psi_{-}]$, which is $j_{b}=\lfloor
k/\psi_{+}\rfloor$ or $j_{b}=\lfloor k/\psi_{+}\rfloor+1$, depending on a
condition on $\tau_{b}$. Due to the assumption $\lfloor
k/\psi_{+}\rfloor+1\leq k/\psi_{-}$, the condition is
$\tau_{b}\in[\\{k/\psi_{+}\\},1)$ for $j_{b}=\lfloor k/\psi_{+}\rfloor$, and
$\tau_{b}\in[0,k/\psi_{-}-(\lfloor k/\psi_{+}\rfloor+1)]$, and $\tau_{b}<1$
for $j_{b}=\lfloor k/\psi_{+}\rfloor+1$.

One can readily verify that for any fixed $j\geq 0$, with
$\tau^{*}=\tau^{*}(j,a):=(j+a)/[2(j+a)+1]$, the function $Q(j,\tau)$ is
strictly increasing in $\tau_{b}$ on the interval $[0,\tau^{*})$, and strictly
decreasing on the interval $(\tau^{*},1)$.

Finally, we maximize over $\tau_{b}$, for a fixed $j_{b}$. Then, for
$j_{b}=\lfloor k/\psi_{+}\rfloor$ it is readily verified that the maximum over
$\tau_{b}$ in the allowed set is achieved at

$\displaystyle\tau^{*}_{j_{b}}$
$\displaystyle=\max\left(\\{k/\psi_{+}\\},\frac{\lfloor
k/\psi_{+}\rfloor+a}{2(\lfloor k/\psi_{+}\rfloor+a)+1}\right).$

Moreover, for $j_{b}=\lfloor k/\psi_{+}\rfloor+1$ the maximum over $\tau_{b}$
is achieved at

$\displaystyle\tau^{*}_{j_{b}+1}$ $\displaystyle=\min\left(k/\psi_{-}-(\lfloor
k/\psi_{+}\rfloor+1),\frac{\lfloor k/\psi_{+}\rfloor+1+a}{2(\lfloor
k/\psi_{+}\rfloor+1+a)+1}\right).$

The optimal objective can be checked to be

$O_{*}=\max\left\\{Q(j_{b},\tau^{*}_{j_{b}}),Q(j_{b}+1,\tau^{*}_{j_{b}+1})\right\\}.$

Squaring and multiplying by $1/s$, we find the excess risk of ridge
regression, finishing the proof.

###  C.3 Proof of Proposition 4

Following the proof of Proposition 3, we need to evaluate

$\displaystyle
E:=\sup_{x\in[x_{-},x_{+}]}\min_{j=1,2,\dots,k}\left(xb^{j-1}-\frac{1}{x}\right)^{2},$

where $b=1-s\eta$. Let $h_{x}=2\log_{1/b}(x)$ and $\tau_{x}=\\{h_{x}\\}$. The
inner minimum is achieved at either $j(x)=\lfloor h_{x}\rfloor+1$ or $j(x)+1$.
Writing $j(x)=h_{x}-\tau_{x}+1$, we find

$\displaystyle\min_{j=1,2,\dots,k}\left|xb^{j-1}-\frac{1}{x}\right|=\min\left\\{xb^{h_{x}-\tau_{x}}-\frac{1}{x},\frac{1}{x}-xb^{h_{x}-\tau_{x}+1}\right\\}=\frac{1}{x}\min\big{\\{}b^{-\tau_{x}}-1,1-b^{1-\tau_{x}}\big{\\}}$

since $xb^{h_{x}}=\frac{1}{x}$. Factoring out $b^{-\tau_{x}}$ from the above
and squaring we can then write

$\displaystyle E$
$\displaystyle=\sup_{x\in[x_{-},x_{+}]}\frac{1}{x^{2}}b^{-2\tau_{x}}\min\big{\\{}1-b^{\tau_{x}},b(b^{\tau_{x}-1}-1)\big{\\}}^{2}$
$\displaystyle=\sup_{x\in[x_{-},x_{+}]}b^{j(x)-1-\tau_{x}}\min\big{\\{}1-b^{\tau_{x}},b(b^{\tau_{x}-1}-1)\big{\\}}^{2},$

where for the second equality we note that
$x^{-2}=b^{h_{x}}=b^{j(x)+\tau_{x}-1}$. The fractional part that maximizes the
minimum for $\tau_{x}\in[\\{h_{x}\\},1)$ occurs at
$\tau^{*}=\log_{1/b}(2/(b+1))$. Thus, with

$\displaystyle Q_{\star}(\tau)=\min\\{1-b^{\tau},b(b^{\tau-1}-1)\\},$

we find since $(1-\eta)^{k}<(1+\psi_{+})^{-1}$ that

$\displaystyle E$ $\displaystyle=b^{\lfloor
h_{x_{-}}\rfloor-\tau^{*}}\max\bigg{\\{}\max_{\tau\in[\\{h_{x_{-}}\\},1)}Q_{\star}(\tau)^{2},b\cdot\max_{\tau\in[0,\\{h_{x_{-}}\\})}Q_{\star}(\tau)^{2}\bigg{\\}}.$
(68)

Where we note that $b^{j(x)}$ is decreasing in $x$, therefore, the first term
within the maximum above is associated to choosing $x$ over the range
$[x_{-},\lceil x_{-}\rceil)$, and the second is associated to choosing $x$
over the range $[\lceil x_{-}\rceil,\lceil x_{-}\rceil+1)$.

Since $Q_{\star}(\cdot)$ attains its maximum at $\tau^{\star}$ and is
decreasing on either side of $\tau^{\star}$, we can rewrite (68), with $a\vee
b=\max\\{a,b\\}$ as well as $a\wedge b=\min\\{a,b\\}$, as follows

$\displaystyle E$ $\displaystyle=b^{\lfloor
h_{x_{-}}\rfloor-\tau^{*}}\max\big{\\{}Q_{\star}(\\{h_{x_{-}}\\}\vee\tau^{\star})^{2},b\cdot
Q_{\star}(\\{h_{x_{-}}\\}\wedge\tau^{\star})^{2}\big{\\}}.$

This quantity can take a total of four values as a function of
$\\{h_{x_{-}}\\}$, $\tau^{\star}$ and $b$.

## References

  * [AB09] Sylvain Arlot and Francis Bach.  Data-driven calibration of linear estimators with minimal penalties.  In NIPS 2009-Advances in Neural Information Processing Systems, volume 22, pages 46–54, 2009.
  * [AC10] Sylvain Arlot and Alain Celisse.  A survey of cross-validation procedures for model selection.  Statistics surveys, 4:40–79, 2010.
  * [ADT20] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani.  The implicit regularization of stochastic gradient flow for least squares.  In International Conference on Machine Learning, pages 233–244. PMLR, 2020.
  * [AKT19] Alnur Ali, J Zico Kolter, and Ryan J Tibshirani.  A continuous-time view of early stopping for least squares regression.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1370–1378, 2019.
  * [All74] David M Allen.  The relationship between variable selection and data agumentation and a method for prediction.  technometrics, 16(1):125–127, 1974.
  * [AM09] Sylvain Arlot and Pascal Massart.  Data-driven calibration of penalties for least-squares regression.  Journal of Machine Learning Research, 10(10):245–279, 2009.
  * [Bah67] Raghu Raj Bahadur.  Rates of convergence of estimates and test statistics.  The Annals of Mathematical Statistics, 38(2):303–324, 1967.
  * [Bah71] Raghu Raj Bahadur.  Some limit theorems in statistics.  SIAM, 1971.
  * [Ber13] James O Berger.  Statistical decision theory and Bayesian analysis.  Springer Science & Business Media, 2013.
  * [BGH09] Yannick Baraud, Christophe Giraud, and Sylvie Huet.  Gaussian model selection with an unknown variance.  The Annals of Statistics, 37(2):630–672, 2009.
  * [BHMR07] Nicolai Bissantz, Thorsten Hohage, Axel Munk, and Frits Ruymgaart.  Convergence rates of general regularization methods for statistical inverse problems and applications.  SIAM Journal on Numerical Analysis, 45(6):2610–2636, 2007.
  * [BM01] Lucien Birgé and Pascal Massart.  Gaussian model selection.  Journal of the European Mathematical Society, 3(3):203–268, 2001\.
  * [BM18] Gilles Blanchard and Nicole Mücke.  Optimal rates for regularization of statistical inverse learning problems.  Foundations of Computational Mathematics, 18(4):971–1013, 2018\.
  * [BMR+20] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901, 2020.
  * [BPR07] Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco.  On regularization algorithms in learning theory.  Journal of Complexity, 23(1):52–72, 2007.
  * [BS10] Zhidong Bai and Jack W Silverstein.  Spectral analysis of large dimensional random matrices, volume 20.  Springer, 2010.
  * [Bub15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [BY20] Pierre Bellec and Dana Yang.  The cost-free nature of optimally tuning tikhonov regularizers and other ordered smoothers.  In International Conference on Machine Learning, pages 746–755. PMLR, 2020.
  * [CDV07] Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  Foundations of Computational Mathematics, 7(3):331–368, 2007.
  * [DFKU13] Paramveer Dhillon, Dean Foster, Sham Kakade, and Lyle Ungar.  A risk comparison of ordinary least squares vs ridge regression.  The Journal of Machine Learning Research, 14:1505–1511, 2013.
  * [Dic13] Lee Dicker.  Optimal equivariant prediction for high-dimensional linear models with arbitrary predictor covariance.  Electron. J. Stat., 7:1806–1834, 2013.
  * [Dic16] Lee H. Dicker.  Ridge regression and asymptotic minimax estimation over spheres of growing dimension.  Bernoulli, 22(1):1–37, 2016.
  * [Dob17] Edgar Dobriban.  Sharp detection in pca under correlations: All eigenvalues matter.  The Annals of Statistics, 45(4):1810–1833, 2017.
  * [DW18] Edgar Dobriban and Stefan Wager.  High-dimensional asymptotics of prediction: Ridge regression and classification.  The Annals of Statistics, 46(1):247–279, 2018.
  * [EHN96] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.  Regularization of inverse problems, volume 375.  Springer Science & Business Media, 1996.
  * [EK18] Noureddine El Karoui.  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, 170(1-2):95–175, 2018.
  * [EKK11] Noureddine El Karoui and Holger Kösters.  Geometric sensitivity of random matrix results: consequences for shrinkage estimators of covariance and related statistical methods.  arXiv preprint arXiv:1105.1404, 2011.
  * [Gei75] Seymour Geisser.  The predictive sample reuse method with applications.  Journal of the American statistical Association, 70(350):320–328, 1975.
  * [Gru17] Marvin HJ Gruber.  Improving efficiency by shrinkage: the James-Stein and ridge regression estimators.  Routledge, 2017.
  * [Har69] JA Hartigan.  Linear bayesian methods.  Journal of the Royal Statistical Society. Series B (Methodological), pages 446–454, 1969.
  * [HK70] Arthur E Hoerl and Robert W Kennard.  Ridge regression: Biased estimation for nonorthogonal problems.  Technometrics, 12(1):55–67, 1970.
  * [HMRT19] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  arXiv preprint arXiv:1903.08560, 2019.
  * [HP88] Stephen Hanson and Lorien Pratt.  Comparing biases for minimal network construction with back-propagation.  Advances in neural information processing systems, 1:177–185, 1988\.
  * [JS61] W James and Charles Stein.  Estimation with quadratic loss.  In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, 1961.
  * [KKV11] Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii.  Cross-validation and mean-square stability.  In In Proceedings of the Second Symposium on Innovations in Computer Science (ICS2011. Citeseer, 2011.
  * [KSH12] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [Lan51] Louis Landweber.  An iteration formula for fredholm integral equations of the first kind.  American journal of mathematics, 73(3):615–624, 1951.
  * [LBH15] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [LC98] EL Lehmann and George Casella.  Theory of point estimation.  Springer Texts in Statistics, 1998.
  * [LD19] Sifan Liu and Edgar Dobriban.  Ridge regression: Structure, cross-validation, and sketching.  In International Conference on Learning Representations, 2019.
  * [LH17] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [LR05] Erich L Lehmann and Joseph P Romano.  Testing statistical hypotheses.  Springer Science & Business Media, 2005.
  * [LRRC20] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.  Optimal rates for spectral algorithms with least-squares regression over hilbert spaces.  Applied and Computational Harmonic Analysis, 48(3):868–890, 2020\.
  * [MM18] Léo Miolane and Andrea Montanari.  The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning.  arXiv preprint arXiv:1811.01212, 2018.
  * [MP67] Vladimir Alexandrovich Marchenko and Leonid Andreevich Pastur.  Distribution of eigenvalues for some sets of random matrices.  Matematicheskii Sbornik, 114(4):507–536, 1967.
  * [Nes13] Yurii Nesterov.  Introductory lectures on convex optimization: A basic course, volume 87.  Springer Science & Business Media, 2013.
  * [NR18] Gergely Neu and Lorenzo Rosasco.  Iterate averaging as regularization for stochastic gradient descent.  In Proceedings of the 31st Conference On Learning Theory, pages 3222–3242, 2018.
  * [PR19] Nicolò Pagliana and Lorenzo Rosasco.  Implicit regularization of accelerated methods in hilbert spaces.  Advances in Neural Information Processing Systems, 32:14481–14491, 2019.
  * [PWRT21] Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani.  Uniform consistency of cross-validation estimators for high-dimensional ridge regression.  In International Conference on Artificial Intelligence and Statistics, pages 3178–3186. PMLR, 2021.
  * [QQ19] Qian Qian and Xiaoyuan Qian.  On the connections between algorithmic regularization and penalization for convex losses.  arXiv preprint arXiv:1909.03371, 2019.
  * [Rao75] C Radhakrishna Rao.  Simultaneous estimation of parameters in different linear models and applications to biometric problems.  Biometrics, pages 545–554, 1975.
  * [RMR21] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco.  Asymptotics of ridge (less) regression under general source condition.  In International Conference on Artificial Intelligence and Statistics, pages 3889–3897. PMLR, 2021.
  * [RV15] Lorenzo Rosasco and Silvia Villa.  Learning with incremental iterative regularization.  In Advances in Neural Information Processing Systems, pages 1630–1638, 2015.
  * [RWY14] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu.  Early stopping and nonparametric regression: an optimal data-dependent stopping rule.  Journal of Machine Learning Research, 15:335–366, 2014.
  * [SA22] Yue Sheng and Alnur Ali.  Accelerated gradient flow: Risk, stability, and implicit regularization.  arXiv preprint arXiv:2201.08311, 2022.
  * [Sch15] Jurgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural networks, 61:85–117, 2015.
  * [SGB94] K Skouras, C Goutis, and MJ Bramson.  Estimation in linear models using gradient descent with early stopping.  Statistics and Computing, 4(4):271–278, 1994.
  * [Ste56] Charles Stein.  Inadmissibility of the usual estimator for the mean of a multivariate normal distribution.  In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1956.
  * [Ste81] Charles M Stein.  Estimation of the mean of a multivariate normal distribution.  The annals of Statistics, pages 1135–1151, 1981.
  * [Sto77] Mervyn Stone.  Asymptotics for and against cross-validation.  Biometrika, pages 29–35, 1977.
  * [Thi77] Ronald A. Thisted.  Ridge Regression, minimax estimation, and empirical Bayes methods.  PhD thesis, Stanford University, 1977.
  * [Tik43] Andrey Nikolayevich Tikhonov.  On the stability of inverse problems.  In Dokl. Akad. Nauk SSSR, volume 39, pages 195–198, 1943.
  * [Top06] Flemming Topsok.  Some bounds for the logarithmic function.  Inequality theory and applications, 4:137, 2006.
  * [TV04] Antonio M Tulino and Sergio Verdú.  Random matrix theory and wireless communications.  Communications and Information theory, 1(1):1–182, 2004.
  * [VBS18] Sharan Vaswani, Francis Bach, and Mark Schmidt.  Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron.  arXiv preprint arXiv:1810.07288, 2018.
  * [vW15] Wessel N van Wieringen.  Lecture notes on ridge regression.  arXiv preprint arXiv:1509.09169, 2015.
  * [WV73] A Wayne and DE Varberg.  Convex functions, 1973.
  * [WX20] Denny Wu and Ji Xu.  On the optimal weighted l2 regularization in overparameterized linear regression.  Advances in Neural Information Processing Systems, 33, 2020.
  * [WZF22] Li Wang, Yingcong Zhou, and Zhiguo Fu.  The implicit regularization of momentum gradient descent with early stopping.  arXiv preprint arXiv:2201.05405, 2022.
  * [XMR19] Ji Xu, Arian Maleki, and Kamiar Rahnama Rad.  Consistent risk estimation in high-dimensional linear regression.  arXiv preprint arXiv:1902.01753, 2019.
  * [YRC07] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  Constructive Approximation, 26(2):289–315, 2007.
  * [ZWB+21] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P Foster, and Sham M Kakade.  The benefits of implicit regularization from SGD in least squares problems.  arXiv preprint arXiv:2108.04552, 2021.