# Comparing Classes of Estimators: When Does Gradient Descent Beat Ridge
Regression in Linear Models?

Dominic Richards,111Amazon. 222Research performed whilst at the University of
Oxford. Edgar Dobriban,333Department of Statistics and Data Science, and
Department of Computer and Information Science, University of Pennsylvania.
E-mail<EMAIL_ADDRESS>and Patrick Rebeschini444Department of
Statistics, Oxford University. E-mail<EMAIL_ADDRESS>
###### Abstract

Methods for learning from data depend on various types of tuning parameters,
such as penalization strength or step size. Since performance can depend
strongly on these parameters, it is important to compare _classes_ of
estimators—by considering prescribed _finite sets_ of tuning parameters— not
just particularly tuned methods. In this work, we investigate classes of
methods via the relative performance of the _best method in the class_. We
consider the central problem of linear regression—with a random isotropic
ground truth—and investigate the estimation performance of two fundamental
methods, gradient descent and ridge regression. We unveil the following
phenomena. (1) For general designs, constant stepsize gradient descent
outperforms ridge regression when the eigenvalues of the empirical data
covariance matrix decay slowly, as a power law with exponent less than unity.
If instead the eigenvalues decay quickly, as a power law with exponent greater
than unity or exponentially, we show that ridge regression outperforms
gradient descent. (2) For orthogonal designs, we compute the exact minimax
optimal _class_ of estimators (achieving min-max-_min_ optimality), showing it
is equivalent to gradient descent with decaying learning rate. We find the
sub-optimality of ridge regression and gradient descent with constant step
size. Our results highlight that statistical performance can depend strongly
on tuning parameters. In particular, while optimally tuned ridge regression is
the best estimator in our setting, it can be outperformed by gradient descent
by an _arbitrary/unbounded_ amount when both methods are only tuned over
finitely many regularization parameters.

##  1 Introduction

Least squares regression is a workhorse in modern statistics, machine
learning, engineering, and signal processing, often lying at the heart of more
complex algorithms and methodologies. It is well known that various forms of
shrinkage or regularization often improve estimation performance in the
presence of noise [Ste56, JS61, Ste81]. The optimal level of shrinkage
required can depend upon _unknown_ properties of the problem, such as the
signal-to-noise ratio. As a result, in practice the regularization strength is
routinely chosen through a two-step procedure: first, a _finite_ class, or
collection, of candidate models (estimators) is proposed by considering a
range of regularization values. Then a candidate model is chosen from the
class through a criterion—such as prediction or estimation error—which itself
is estimated, say, through cross-validation using held-out data [All74, Sto77,
Gei75]. This leads to a natural statistical question: How should _classes_ of
candidate models be chosen and compared?

We investigate this fundamental question when classes of candidate models are
compared through the _best-in-class model_. Studying the best candidate model
in a class allows us to understand the behavior and sensitivity of model
classes with respect to their tuning parameters at a level of precision that
has not been investigated before. Indeed, the standard approach is to compare
estimators that are optimally tuned with respect to hyperparameters, say by
balancing bias and variance. In contrast, our approach allows us to evaluate
model classes when their hyperparameters are restricted to a finite
collection/grid; as they must be in practice.

We instantiate this approach for two popular classes of estimators, the
iterates of gradient descent (GD), and ridge regression with a varying
regularization strength. Each of these classes is extremely important and
widely used. Gradient descent is the canonical first-order optimization
algorithm, and its variants are currently the method of choice for training
state-of-the art machine learning models, including deep neural networks
[Nes13, Bub15, KSH12, BMR+20, LBH15, Sch15]. Ridge regression, and more
broadly $\ell_{2}$ regularization, has been possibly the most fundamental
approach to regularization in inverse problems and statistical estimation from
the 1940s onwards [Tik43, Ste56, JS61, HK70, Ste81]. For modern deep neural
networks, it is linked to the highly popular method of weight decay [HP88,
LH17].

Figure 1: Ratio of the minimum excess risk achieved by $k$ iterates of
gradient descent (with constant step size $\eta=O(1/k)$) and the minimum
excess risk achieved by $k$ ridge regression estimators (with ridge
regularization parameter spread uniformly in the interval $[0,1]$). Plot is as
a function of the optimal ridge regularization parameter $\lambda_{\star}>0$
(left) and the exponent $\alpha\geq 0$ controlling the polynomial decay of the
eigenvalues $s_{i}=i^{-\alpha}$ for $i\geq 1$, of the empirical covariance
matrix of the data (right). Dimension and sample size $d=n=10^{6}$ with
$k=100$.

We develop an extensive set of theoretical results characterizing their
relative performance for least squares regression, in the central problem of
linear regression—with a random isotropic ground truth parameter. It is well
known that _optimally tuned_ ridge regression is a linear Bayes method—and
thus optimal—in this setting; henceforth, let $\lambda_{\star}>0$ be the
optimal choice of the ridge penalty term. In particular, the class of _all_
ridge regression estimators is at least as good as, and possibly much better
than, the class of _all_ gradient descent estimators. One may thus expect that
this is the case even for finite classes, when one considers a finite set of
tuning parameters. However, we show that this is far from true. Along the way,
we unveil several properties that do not seem to have been previously noticed
in the literature. These are summarised within our two main contributions:

  1. 1.

Gradient Descent vs. Ridge Regression. We perform a detailed analysis of the
ratio of excess risks (_relative sub-optimality_ , c.f. Definition 3) between
classes of gradient descent estimators (with constant step size, i.e., with a
step size independent of iteration time and only depending on the time
horizon) and ridge regression estimators (with choices of regularization
parameters discussed later; including uniform discretization). Throughout, by
_excess risk of a class of estimators_ we mean the best (i.e., minimal) excess
risk achieved by the estimators in the class. This turns out to depend
strongly on the structure of the data, and on the rate of decay of the
eigenvalues of the empirical covariance matrix of the data.
Fast Eigenvalue Decay. When eigenvalues of the empirical covariance matrix
decay fast— according to a power law with exponent greater than unity, or
exponentially fast—then _ridge regression outperforms gradient descent_. This
mirrors the behavior when all estimators are considered; and thus is the
expected behavior. Precisely, there are problem sequences with a sample of
size $n$, in dimension $d$, and number of estimators $k$, such that 555Formal
result in Corollary 3 Appendix B.4.

$\displaystyle\lim_{\begin{subarray}{c}k\rightarrow\infty\\\
\lambda_{\star}\rightarrow
0\end{subarray}}\lim_{\begin{subarray}{c}d,n\rightarrow\infty\end{subarray}}\frac{\text{Excess
Risk of $k$ Gradient Descent Iterates}}{\text{Excess Risk of $k$ Ridge
Regression Estimators}}=\infty.$

However, surprisingly, the performance of ridge regression relative to
gradient descent behaves differently when the eigenvalues _decay slowly_
(Figure 1 and Theorem 1).

Slow Eigenvalue Decay & High SNR. When eigenvalues of the empirical covariance
matrix of the data decay according to a power law with exponent less than
unity, and with a high signal-to-noise ratio (SNR), _gradient descent
outperforms ridge regression_. In particular, with sample of size $n$,
dimension $d$ and number of estimators $k$ 666Formal result in Corollary 2
Appendix B.4.

$\displaystyle\liminf_{\begin{subarray}{c}k\rightarrow\infty\\\
\lambda_{\star}\rightarrow
0\end{subarray}}\lim_{\begin{subarray}{c}d,n\rightarrow\infty\end{subarray}}\frac{\text{Excess
Risk of $k$ Gradient Descent Iterates}}{\text{Excess Risk of $k$ Ridge
Regression Estimators}}=0.$

The fact that the excess risk ratio tends to zero for appropriate sequences of
problems highlights that gradient descent can outperform ridge regression by
an _arbitrary factor_. More generally, Theorem 1 characterizes the excess risk
ratio for finite $n,d,k,\lambda_{\star}$.

Overall, the ratio of excess risks can behave in subtle ways, see Figure 1.
Precisely, we find that the excess risk ratio is highly oscillatory as a
function of the optimal ridge regularization parameter (for other parameters
fixed), and has several regions of monotonicity as a function of the
eigenvalue decay rate $\alpha$ (we identify three), see the discussion after
Theorem 1. To control the ratio, we develop new upper and lower bounds on the
excess risk of individual classes of gradient descent and ridge regression
estimators (Section 2.4).

  2. 2.

Min-Max-Min Optimality, Exact Computations, and Phase Transitions. For
orthogonal designs, i.e., when the empirical covariance matrix of the data is
a scaled identity matrix, we find the _exact minimax optimal classes_ of
estimators over a range of signal-to-noise ratios (Theorem 6). We refer to
these as _min-max-min_ optimal due to the formulation we consider, c.f.
equation (19), which evaluates the minimum over classes, the maximum over the
problems, and the minimum (best-in-class) performance. Perhaps surprisingly,
this class is achieved _neither_ by ridge regression with a uniform
discretization grid (or other common discretizations such as log-uniform)
_nor_ by gradient descent with a constant step size. However, it can be
represented as gradient descent with a step size decreasing polynomially in
the iteration counter (Section A.6).

For orthogonal designs, we find the _exact_ sub-optimality of ridge regression
and gradient descent (Section 3.1) compared to the optimum. We find that the
sub-optimality has a “switching” behavior as a function of the number $k$ of
estimators in the class, behaving as either $1/k$ or $1/k^{2}$ for certain
ranges of $k$; this matches numerical results (Figure 4) and results for
general designs, c.f. equation (17).

For further details on Figure 1, the left plot illustrates the highly
oscillatory behavior of the excess risk ratio (relative sub-optimality) of the
two methods. This is partly due to the discreteness of the grid of tuning
parameters: when a ridge regularization grid element falls close to the
optimal regularizer, the best-in-class method performs very well. The right
plot illustrates the non-trivial behavior of the same performance metric as a
function of the geometry of the data/design matrix, as captured by the decay
rate of the eigenvalues of the empirical covariance matrix. Our results
identify several regions of monotonicity of these curves.

The code to reproduce our experimental results is available at
https://github.com/DominicRichards/ComparingGradientDescentRidge.

###  1.1 Related Literature

From the early works of [Tik43, Ste56, JS61, HK70, Ste81], a vast literature
investigating the performance of shrinkage methods in the context of mean
estimation, inverse problems, and least squares regression has developed. The
PhD thesis by Thisted [Thi77], in particular, studies ridge regression, making
connections with minimax estimation and empirical Bayes methods, including a
thorough historical review. [Thi77] argues for the importance of making a
distinction between ridge regression estimators for a fixed regularization,
for adaptively chosen regularization, and for classes of models with varying
regularization strengths. Our work makes steps towards rigorously formalizing
such a distinction, focusing on the performance of classes of models defined
by varying the regularization strength. General references on ridge regression
include [Gru17, vW15].

We highlight works related to inverse problems and kernel regression, such as
[Lan51, EHN96, BHMR07, CDV07, YRC07, BPR07, RWY14, RV15, BM18, PR19, LRRC20],
where the shrinkage performance of iterative methods like gradient descent has
gained much attention. Here statistical performance is encoded by an _optimal
rate_ at which the estimation or prediction error decays with respect to the
sample size [CDV07, BM18]. The rate depends on both the regularity of the
problem (e.g., smoothness of the optimal regression function), and the
effective dimension (often referred to as the capacity) of the kernel. The
guarantees for various estimators—e.g., ridge regression and early stopped
gradient descent—aim to show that the optimal rate is achieved in a worst case
sense. However, the bounds usually do not capture the dependence on the
discretization, which is a key component of our results.

The concurrent work [ZWB+21] compares the sample inflation, in a Bahadur
efficiency sense [Bah67, Bah71], of single-pass stochastic gradient descent
(SGD) to ridge regression i.e., the additional sample size required by SGD in
order to have comparable or better performance than ridge regression, when
each is optimally tuned. Notably, they observe (Corollary 5.1 within) when the
population eigenvalues decay with a power law with exponent less than unity,
then the sample inflation is mild (logarithmic). This finding is connected to
our results (Theorem 1), in that we find that gradient descent can outperform
ridge regression when the empirical eigenvalues decay at this rate. However,
our perspective and results are different and complementary. For instance, we
consider a fixed-design setting instead of a random-design setting, and focus
on the sensitivity to tuning parameters with respect to the underlying unknown
signal-to-noise level, including the effects of discretization, instead of
looking at optimal tuning.

The two concurrent works [SA22, WZF22] use an error decomposition similar to
Lemma 1 to explore the excess risk of spectral filters arising from continuous
time accelerated gradient descent. While our work is linked to excess risk
(see the relative sub-optimality definition 3 and Section 2.4.1), we study
finite classes of estimators. The continuous time limit could perhaps be
associated to an infinitely sized class, but this is distinct from our work. A
natural future direction is to explore using our problem dependent class
bounds for ridge regression or gradient descent, to compare with accelerated
gradient descent. For extended related literature see supplementary material
A.1.

###  1.2 Setup

Consider a standard noisy least squares regression setting with $n$ data
points of dimension $d$. We observe a design matrix $X\in\mathbb{R}^{n\times
d}$ (also referred to as a data matrix, inputs, features, or covariates) and
response $Y\in\mathbb{R}^{n}$ (also referred to as outcomes or outputs) such
that

$\displaystyle Y=X\beta_{\star}+\sigma\epsilon,$ (1)

where the ground truth regression parameter $\beta_{\star}\in\mathbb{R}^{d}$,
noise $\epsilon\in\mathbb{R}^{n}$, and noise level $\sigma>0$ are unknown. We
assume that the noise and ground truth $(\epsilon,\beta_{\star})$ are random
and satisfy the following distributional assumptions:

$\displaystyle\mathbf{E}[\epsilon]=0,\quad\quad\mathbf{E}[\epsilon\epsilon^{\top}]=I_{n},\quad\quad\mathbf{E}[\beta_{\star}\beta_{\star}^{\top}]=\frac{\psi}{d}I_{d},\quad\quad\epsilon\perp\\!\\!\\!\perp\beta_{\star}.$
(2)

The noise $\epsilon$ and ground truth $\beta_{\star}$ are mutually
independent, each with zero mean and an isotropic covariance matrix. The
scalar $\psi>0$ controls the expected squared norm of $\beta_{\star}$, as
$\mathbf{E}\|\beta_{\star}\|_{2}^{2}=\psi$, and we will refer to it as the
_signal strength_. Given $X$ and $Y$, we focus on estimating the associated
ground truth $\beta_{\star}$ with squared $\ell_{2}$-norm loss, for estimators
$\widehat{\beta}$

$\displaystyle
L_{\beta_{\star}}(\widehat{\beta}):=\|\widehat{\beta}-\beta_{\star}\|_{2}^{2}.$

We denote the eigenvector-eigenvalue decomposition of the un-centered
empirical covariance matrix as $n^{-1}X^{\top}X$ $=$
$\sum_{i=1}^{r}s_{i}v_{i}v_{i}^{\top}$, where the rank is denoted
$r\leq\min(n,d)$, the non-zero eigenvalues $\\{s_{i}\\}_{i=1}^{r}$, and
associated eigenvectors $\\{v_{i}\\}_{i=1}^{r}$. For a measurable function
$\Phi:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$, where
$\mathbb{R}_{\geq 0}=[0,\infty)$, we then denote the application of a function
to a matrix by applying it to the eigenspectrum, i.e.,
$\Phi(n^{-1}X^{\top}X)=\sum_{i=1}^{r}\Phi(s_{i})v_{i}v_{i}^{\top}$.777Sometimes
we will refer to $\Phi$ as a _spectral shrinker_. Given this, we will study
estimators $\widehat{\beta}_{\Phi}:\mathbb{R}^{n(p+1)}\to\mathbb{R}^{p}$ of
the form

$\displaystyle\widehat{\beta}_{\Phi}=\widehat{\beta}_{\Phi}(X,Y)=\Phi\Big{(}\frac{X^{\top}X}{n}\Big{)}\frac{X^{\top}Y}{n}.$
(3)

We now introduce two estimators studied in this work, beginning with ridge
regression.

######  Definition 1 (Ridge Regression)

Define ridge regression with penalty $\lambda>0$ as 888The expression
$\widehat{\beta}_{\lambda}$ is a slight abuse of notation compared to
$\widehat{\beta}_{\Phi_{\lambda}}$, and is only used for convenience.

$\displaystyle\widehat{\beta}_{\lambda}:=\Big{(}\frac{X^{\top}X}{n}+\lambda
I_{d}\Big{)}^{-1}\frac{X^{\top}Y}{n}=\operatorname{argmin}_{\beta\in\mathbb{R}^{d}}\Big{\\{}\frac{1}{n}\|X\beta-Y\|_{2}^{2}+\lambda\|\beta\|_{2}^{2}\Big{\\}}.$

This corresponds to the spectral shrinker $\Phi_{\lambda}$ in (3), such that
for any $u\geq 0$, $\Phi_{\lambda}(u)=1/(u+\lambda)$.

The second estimator arises from the iterates of gradient descent applied to
the squared loss $\frac{1}{2n}\|X\beta-Y\|_{2}^{2}$ with a fixed stepsize.

######  Definition 2 (Gradient Descent)

Initialized at $\widehat{\beta}_{\eta,0}=0$, define the iterates of gradient
descent recursively for stepsize $\eta\geq 0$ and iteration $t\geq 0$ as

$\displaystyle\widehat{\beta}_{\eta,t+1}:=\widehat{\beta}_{\eta,t}-\frac{\eta}{n}X^{\top}(X\widehat{\beta}_{\eta,t}-Y)=\sum_{\ell=0}^{t}\eta\left(I_{d}-\eta\frac{X^{\top}X}{n}\right)^{\ell}\frac{X^{\top}Y}{n}.$

This corresponds to the spectral shrinker $\Phi$ in (3), such that for any
$u\geq 0$, $\Phi(u)=\eta\sum_{\ell=0}^{t-1}(1-\eta u)^{\ell}$.

The optimal choice of regularization parameter for the ridge regression
estimator is $\lambda_{\star}=\sigma^{2}d/(\psi n)$, as shown in the following
known lemma, which states that ridge regression with the appropriate
regularization parameter is a _linear Bayes_ estimator, see [Har69, Rao75,
Gru17].

###### Lemma 1

Consider data generated according to (1) and (2). Then for any
$\Phi:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ we have
$\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\Phi})]\geq\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]$.

Motivated by this, we define the expected excess risk (or, sub-optimality) of
an estimator $\widehat{\beta}$ by

$\mathcal{E}(\widehat{\beta})=\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})-L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})].$
(4)

####  1.2.1 Comparing classes via the relative sub-optimality

It is clear from Lemma 1 that when the noise variance $\sigma^{2}$ and signal
strength $\psi$ is known, it is not possible to outperform ridge regression in
expectation. However, in practice $\sigma^{2}$ and $\psi$ are usually not
known, and may be hard to estimate. This leaves open the choice of a “best”
estimator.

One approach is to use hyperparameter search to choose the best regularization
parameter from a class. In general, one can consider a class
$\mathcal{C}=\\{\widehat{\beta}^{i}\\}_{i=1}^{k}$ of $k\geq 1$ estimators
$\widehat{\beta}^{i}$, for $i=1,\dots,k$. For instance, for ridge regression
we can choose a grid $\Gamma=\\{0,1/(k-1),2/(k-1),\dots,1\\}$ of size $k$ over
the unit interval $[0,1]$, and set
$\mathcal{C}=\\{\widehat{\beta}_{\lambda}\\}_{\lambda\in\Gamma}$.

We now introduce the measure by which we compare _two classes_ of models. This
definition applies to any estimation problem, and any classes of estimators,
not just linear regression with quadratic loss and the specific estimators
that we focus on in this paper.

######  Definition 3 (Relative Sub-optimality)

For two classes of estimators $\mathcal{C}_{1}=\\{\widehat{\beta}^{u}\\}_{u\in
U_{1}}$ and $\mathcal{C}_{2}=\\{\widehat{\beta}^{u}\\}_{u\in U_{2}}$ define
their _relative sub-optimality_ using the sub-optimality $\mathcal{E}$ from
(4) as999We assume
$\min_{\widehat{\beta}\in\mathcal{C}_{2}}\mathcal{E}(\widehat{\beta})>0$.

$\displaystyle\mathcal{S}(\mathcal{C}_{1},\mathcal{C}_{2}):=\frac{\min_{\widehat{\beta}\in\mathcal{C}_{1}}\mathcal{E}(\widehat{\beta})}{\min_{\widehat{\beta}\in\mathcal{C}_{2}}\mathcal{E}(\widehat{\beta})}=\frac{\min_{\widehat{\beta}\in\mathcal{C}_{1}}\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]}{\min_{\widehat{\beta}\in\mathcal{C}_{2}}\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]}.$
(5)

The relative sub-optimality $\mathcal{S}(\cdot,\cdot)$ is directly related to
the excess risk of each class when compared to optimally tuned ridge
regression. Indeed, if we have $m_{1}\geq 0,m_{2}>0$ such that

$\displaystyle\min_{\widehat{\beta}\in\mathcal{C}_{i}}\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})]=(1+m_{i})\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]$

then precisely $\mathcal{S}(\mathcal{C}_{1},\mathcal{C}_{2})=m_{1}/m_{2}$.

##  2 Gradient Descent versus Ridge Regression

In this section we compare the classes of models produced by the
regularization path of gradient descent to ridge regression with a grid of
penalization parameters. For simplicity of notation, in this section we assume
without loss of generality that $\psi=1$. This can always be achieved by
rescaling the problem. We assume that there is a _known_ lower bound
$\lambda_{\min}>0$ on the optimal ridge regularization parameter, such that
$\lambda_{\star}\in[\lambda_{\min},1]$. We will specify $\lambda_{\min}$ in
each result to follow. This is equivalent to having a known lower bound
$\sigma_{\min}>0$ on the variance of the noise, so that
$\sigma\geq\sigma_{\min}$, with the relationship

$\lambda_{\star}=\frac{d}{n}\sigma^{2}\geq\frac{d}{n}\sigma_{\min}^{2}=\lambda_{\min}.$
(6)

Given this, we define the following two classes of models, for $k\geq
2$101010The class $\mathcal{C}^{\text{GD}}(\eta,k)$ is defined for $k\geq 1$,
but we only consider $k\geq 2$, because we want to have an equal number of GD
and ridge estimators.

$\displaystyle\mathcal{C}^{\text{GD}}(\eta,k)$
$\displaystyle:=\\{\widehat{\beta}_{\eta,t}:1\leq t\leq k\\},$ (7)
$\displaystyle\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)$
$\displaystyle:=\left\\{\widehat{\beta}_{\lambda}:\lambda\in\\{\lambda_{\min},\lambda_{\min}+\delta,\lambda_{\min}+2\delta,\dots,1\\},\delta=\frac{1-\lambda_{\min}}{k-1}\right\\},$
(8)

The first class $\mathcal{C}^{\text{GD}}(\eta,k)$ contains the first $k$
iterates of gradient descent. Meanwhile,
$\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)$ is the class of ridge
regression estimators with regularization parameters chosen from _uniformly_
discretizing the interval $[\lambda_{\min},1]$, with window $\delta>0$.

Since the two sets are of the same size $k$, it is natural to scale
$\eta\\!=\\!(k\lambda_{\min})^{-1}$. In this case, if
$\lambda_{\min}=\Theta(\lambda_{\star})$, then we have
$k=O((\eta\lambda_{\star})^{-1})$, which aligns with the scaling within prior
work on inverse problems and linear regression [NR18, AKT19,
LRRC20].111111Intuitively, this scaling ensures the shrinkage of gradient
descent in the direction associated to the smallest eigenvalue is _at least as
strong_ as for optimally tuned ridge regression. That is, for an eigenvalue
$s>0$, let $k^{\star}(s)$ be the theoretical number of gradient descent
iterations—not necessarily an integer—that matches optimally tuned ridge
regression, so $(1-\eta
s)^{k^{\star}(s)}=\lambda_{\star}/(\lambda_{\star}+s)$. Noting that
$k^{\star}(s)$ is a decreasing function in $s$, the maximum number of gradient
descent iterations (to match ridge regression) occurs when $s\rightarrow 0$ in
which case $k^{\star}(s)=\log(1+s/\lambda_{\star})/\log(1/(1-\eta
s))\rightarrow 1/(\eta\lambda_{\star})$. Now, when $\lambda_{\min}$ is of a
smaller order, one should either perform additional iterations if the step
size is fixed, or choose a larger step size if the number of iterations is
fixed, to ensure gradient descent includes sufficiently regularized models.

We now give a theorem which describes the main insights in this section. We
recall that $A\gtrsim B$ if there is a constant $C$ independent of
$d,n,\sigma,k$ such that $A\geq CB$.121212When this statement refers to an
assumption, the constant needs to be sufficiently large. We write $A\lesssim
B$ when $B\gtrsim A$, and $A\simeq B$ when $A\lesssim B$ and $B\lesssim A$.
For a real number $a$ and a set of real numbers
$\Gamma=\\{b_{1},b_{2},\dots,b_{k}\\}$ let
$\text{Dist}(a,\Gamma)=\min_{b\in\Gamma}|a-b|$. We denote the distance scaled
by a real number $c>0$ as

$\text{Dist}_{c}(a,\Gamma)=\text{Dist}(a,\Gamma)/c=\frac{\min_{b\in\Gamma}|a-b|}{c}.$
(9)

For a number $k>1$ of classes, let $\delta=(1-\lambda_{\min})/(k-1)$ be size
of the window of a grid, and define the grid

$\Gamma=\\{\lambda_{\min},\lambda_{\min}+\delta,\lambda_{\min}+2\delta,\dots,1\\}$

of ridge regularization parameters. Further, let $\eta=1/(k\lambda_{\min})$
the learning rate for gradient descent. To avoid a degenerate problem we
assume that the optimal ridge regularization parameter does not intersect the
discretization, i.e.,
$\lambda_{\star}\not\in\Gamma=\\{\lambda_{\min},\lambda_{\min}+\delta,\lambda_{\min}+2\delta,\dots,1\\}$.
Similarly, we assume
$(\eta\lambda_{\star})^{-1}\not\in\\{0,1,2,3,\dots,k-1\\}$, which is
associated to the “optimal” number of gradient descent iterations.

###### Theorem 1

In the random-effects linear model (1), (2) in the above setting, assume that
the lower bound $\sigma_{\min}$ on the noise level $\sigma$ obeys
$0<\sigma_{\min}\leq\sigma/\sqrt{2}$ and the number $k$ of classes is large
enough that, for the optimal regularization parameter $\lambda_{\star}$ and
its known lower bound $\lambda_{\min}$ from (6)

$k\gtrsim\lambda_{\star}^{-1}\max\left\\{1,\frac{1}{\lambda_{\min}}\log\left(1+\frac{1}{\lambda_{\star}}\right)\right\\}.$

We then have the following results, under two sets of conditions for the non-
zero eigenvalues $\\{s_{i}\\}_{i=1}^{r}$, of $n^{-1}X^{\top}X$.131313See the
related work section for a motivation of these conditions.

  * •

Slow Power Law Decay: Suppose $s_{i}=i^{-\alpha}$, $i=1,\ldots,r$, for
$\alpha\in(0,1)$. Then there is a function
$r_{\alpha,\lambda_{\star},k,\lambda_{\min}}>1$ of
$\alpha,\lambda_{\star},k,\lambda_{\min}$ such that if the rank $r\geq
r_{\alpha,\lambda_{\star},k,\lambda_{\min}}$, the relative sub-optimality (5)
of the class of gradient descent and ridge regression estimators from (7), (8)
has the order, with the scaled distance from (9)

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\simeq\frac{1}{\mathrm{Dist}_{\delta}(\lambda_{\star},\Gamma)^{2}}\left(\frac{d}{n}\right)^{2}\left(\frac{\sigma^{2}}{\sigma_{\mathrm{min}}}\right)^{4}.$

  * •

Fast Power Law or Exponential Decay: Suppose $s_{i}=i^{-\alpha}$,
$i=1,\ldots,r$, for $\log(k)\gtrsim\alpha>1$ or $s_{i}=\exp(-\rho(i-1))$,
$i=1,\ldots,r$, for $\log(k)\gtrsim\rho>0$. Further, suppose that
$s_{r}\leq\lambda_{\star}$. Then the relative sub-optimality (5) of the class
of gradient descent and ridge regression estimators from (7), (8) is lower
bounded as

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\gtrsim\frac{1}{\mathrm{Dist}_{\delta}(\lambda_{\star},\Gamma)^{2}}\left(\frac{d}{n}\right)^{2}\left(k\sigma^{2}\right)^{2}.$

The above theorem provides insights into the relative sub-optimality of
gradient descent and ridge regression under different assumptions of the
eigenvalue decay. The bounds are scaled by
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)^{-2}$ (recall (9)), which
encodes the distance between the optimal regularization $\lambda_{\star}$ and
the ridge regression discretization grid $\Gamma$. In particular, if
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for an integer $k-2\geq
j\geq 0$ and $\varepsilon\in(0,1)$ then
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)=\min\\{1-\varepsilon,\varepsilon\\}$.
Therefore, if $\lambda_{\star}$ lands in the middle of two discretization
points—so $\varepsilon=1/2$—we find
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)=1/2$. Alternatively, if the
optimal regularization $\lambda_{\star}$ nears a point within the
discretization $\Gamma$—so $\varepsilon\rightarrow 0$ or $1$—we then get
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)\rightarrow 0$, reflecting that
the denominator of
$\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
vanishes. In this case ridge regression becomes “infinitely more accurate”
than gradient descent; which is the expected behavior.

Theorem 1 then considers two main types of problem structures. In the first
case, when the eigenvalues decay slowly (at a power law rate of
$s_{i}=i^{-\alpha}$ for $0<\alpha<1$), the ratio is on the order of
$\left(d/n\right)^{2}\left(\sigma^{2}/\sigma_{\text{min}}\right)^{4}$ provided
the rank $r=\min(n,d)$ is sufficiently large with respect to the problem
parameters $(\alpha,\lambda_{\star})$ as well as the model parameters
$(k,\lambda_{\min})$. When $d\simeq n$ and $\sigma_{\min}=\Theta(\sigma)$, the
relative sub-optimality is on the order of $O(\sigma^{4})$, and thus, perhaps
surprisingly, gradient descent performs better then ridge regression in low
noise settings. In particular, if $\sigma\to 0$, gradient descent can
outperform ridge regression by an _arbitrary factor_.

In general, the smaller the _a priori_ lower bound $\sigma_{\min}$, the less
efficient gradient descent becomes. The reason is that it “wastes” models in
this case, because the number of models $k$ is fixed, and thus the step size
$\eta=O(1/(k\sigma_{\min}^{2}))$ is large. Therefore gradient descent takes
large steps with most of the iterations being close to the convergence point,
i.e., the least squares estimator. In particular, the bound is of a constant
order if $\sigma_{\min}\simeq\sigma^{2}$. Similar results hold in the “low-
dimensional” setting where $d=n^{q}$ for some $q\in[0,1)$, details of which
are provided in the results to follow.

The second case of Theorem 1 considers eigenvalues that decay _more quickly_ ,
namely, with a power law so that $s_{i}=i^{-\alpha}$ for
$\log(k)\gtrsim\alpha>1$, or exponentially quickly. In either of these cases
we see that the relative sub-optimality grows at least with the _square of the
number of models $k$ for any rank $r$_. This implies that ridge regression is
the better choice as number of models grows; which aligns with our
expectations based on considering all ridge estimators.

When considering the monotonicity of the relative sub-optimality
$\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
as a function of the eigenvalue polynomial decay rate $\alpha\geq 0$ i.e.,
$s_{i}=i^{-\alpha}$, we note an alignment between the empirical evaluation in
Figure 1 and our theoretical results. Precisely, we highlight three regimes:
(1) a slow decay $\alpha\in(0,1)$, which is favorable to gradient descent
(Theorem 1); (2), a faster decay $\log(k)\gtrsim\alpha\geq 1$, which is
favorable to ridge regression (Theorem 5) ; (3), a very fast decay
$\alpha\gtrsim\log(k)$, which we conjecture is favorable to gradient descent.
The cases of very small or large $\alpha$ are consistent with our findings
from the orthogonal design setting in Section 3, which intuitively corresponds
to $\alpha\to 0$ or $\alpha\to\infty$.

Computational Questions. Within the results above, we fix the class sizes to
be equal, so
$|\mathcal{C}^{\text{GD}}(\eta,k)|=|\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)|=k$.
Alternatively, the estimator’s computational cost (run-time or memory) can be
encoded in the class sizes. More generally, we can consider
$|\mathcal{C}^{\text{GD}}(\eta,k_{GD})|=k_{\text{GD}}$ and
$|\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k_{\text{Ridge}})|=k_{\text{Ridge}}$
and provide bounds in terms of relative size
$c=k_{\text{GD}}/k_{\text{Ridge}}$. When the eigenvalues decaying slowly, the
relative sub-optimality will then be scaled by a multiplicative factor 141414
Looking to the dominant second term in equation (23), with
$\eta=1/(k_{\text{GD}}\lambda_{\star})$ and $\delta=O(1/k_{\text{Ridge}})$ we
note it is scaled by $\eta^{2}/\delta^{2}=1/(c^{2}\lambda_{\star}^{2})$.  of
$1/c^{2}$ in this case. As gradient descent is typically cheaper to compute
than ridge regression, we are lead to consider $c\geq 1$. Thus, accounting for
computational cost typically only further improves the performance of gradient
descent relative to ridge regression.

Supplementary Results and Discussion Additional results and discussion are
included within Section A of the supplementary material. Precisely, Theorem 7
in Section A.2 demonstrates gradient descent still outperforms ridge
regression tuned over a logarithmic grid when eigenvalues decay slowly,
mirroring Theorem 1. Section A.3 provides discussion related to the framework
investigated within this work as well as directions for future research, and
Section A.4 contains a proof sketch for Theorem 1.

The following subsection, Section 2.1, provides an empirical investigation
into the upper and lower bounds from Theorem 1 alongside an extension to the
random design setting. The following sections then provide more detailed
results for the relative sub-optimality, for various assumptions on the
eigenvalues. Section 2.2 provides the results for a slow power law eigenvalue
decay, while Section 2.3 provides the results for exponential and fast power
law decays. Finally, Section 2.4 provides bounds for individual classes of
estimators.

###  2.1 Experiments

We study how the relative sub-optimality
$\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
between gradient descent and ridge regression scales with the noise standard
deviation $\sigma$ in the _slow power law decay_ regime. To do so, we consider
two experiment settings. The first evaluates the upper and lower bounds on the
relative sub-optimality
$\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
when $s_{i}=i^{-\alpha}$ for $i=1,\dots,r$. The second considers the
randomness introduced from generating data according to (1) and (2) with the
eigenvalue decay at the population level, specifically when each row in the
design matrix $X$ is drawn from a multivariate normal distribution with a
population covariance matrix $\text{Diag}(s_{1},s_{2},\dots,s_{d})$ where
$s_{i}=i^{-\alpha}$. This slightly differs from our theoretical analysis,
which considers a _fixed design_ setting; and the goal is to evaluate our
results in a somewhat broader range of settings. Each of these experiments is
presented in its own paragraph.

Numerical Evaluation of Upper and Lower Bounds. Looking to Figure 2, we see
the relative sub-optimality plotted against the optimal amount of
regularization, alongside the theoretical upper and lower bounds from Theorems
2 and 3, (these are more precise versions of Theorem 1), and we are using
constants of unity instead of $1152$ and $1/512$, respectively).

We observe that the numerically computed relative sub-optimality can indeed be
much smaller than unity when $\lambda_{\star}$ is small; in which case the
grid of gradient descent estimators performs much better than ridge
regression. This supports our theoretical observations about the two
estimators. The upper bound captures the variation in the relative sub-
optimality arising from the discretization.

Currently, when the rank $r=10^{6}$, a gap remains between the upper and the
lower bounds. The general qualitative behavior of the bounds appears correct,
but the constants could be tightened with additional work. Tightening the
dependence on the rank $r$ is left for future work.

Figure 2: Plot of relative sub-optimality
$\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
against the optimal regularization $\lambda_{\star}$ on a $\log-\log$ scale.
Problem parameters: $\lambda_{\min}=0.71245212\cdot\lambda_{\star}$ (the
factor of $0.71245212$ ensures $1/\eta\lambda_{\min}$ is not an integer),
$k=100$, $\eta=1/(k\lambda_{\min})$, $\alpha=0.5$, $r=10^{6}$,
$s_{i}=i^{-\alpha}$ for $i=1,\dots,r$. Also plotted for 100 values of
$\lambda^{\star}\in[10^{-2},1]$ is the upper bound from Theorem 2 with
constant equal to unity instead of $1152$, and the lower bound from Theorem 3
with constant equal to unity instead of $1/512$ and with $r=10^{10}$.

Random Design Setting. Looking to Figure 3 an estimate of the relative sub-
optimality is plotted against the optimal regularization
$\lambda_{\star}=\sigma^{2}d/(\psi n)$, for a particular choice of
$n,d,k$.151515In this experiment $\psi\neq 1$, but this is immaterial as it
only amounts to a scaling of the results. We observe a roughly linear
relationship (on a $\log-\log$ scale), with the relative sub-optimality
decreasing as the optimal regularization decreases. This is consistent with
the theoretical results in Theorem 1. The estimated relative sub-optimality
does not decrease monotonically in $\lambda_{\star}$. A possible explanation
is that the discretization grid is fixed, and thus, as the optimal
regularization parameter varies, so does its distance to the closest grid
point. Moreover, the relative sub-optimality is increasing in $\alpha$, which
is consistent with our theoretical results for this range of $\alpha$.

Figure 3: Estimate of relative sub-optimality
$\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
as a function of optimal regularization $\lambda_{\star}$ on a $\log-\log$
scale. Problem parameters: $\eta=1$, $\sigma\in[10^{0.8},10^{1.3}]$,
$\psi=10$, $\alpha\in\\{0.01,0.1,0.25\\}$, $d=5\cdot 10^{3}$, $n=2\cdot
10^{5}$, $k=\lceil 1/(\eta\lambda_{\min})\rceil=10$ where
$\lambda_{\min}=0.99\cdot 10^{1.6}d/(n\psi)$. Fixed
$\beta^{\star}=\mathbf{1}\sqrt{\psi/d}$ where $\mathbf{1}$ is a vector of
ones. For each estimator, the expected sub-optimality is estimated as an
average over 20 replications, with the best estimator chosen thereafter. For
gradient descent, we choose the best estimator from the class
$\\{\hat{\beta}_{\eta,s}\\}_{s=1,\dots,k}$, for ridge regression we choose the
best regularization out of
$\\{\lambda_{\star}+(1-\lambda_{\min})/(k-1),\ldots,\lambda_{\star}-(1-\lambda_{\min})/(k-1)\\}$.
The error bars (short and barely visible) show two standard deviations over
ten replications of this process.

###  2.2 Eigenvalues with a Slow Power Law Decay

In this section we consider eigenvalues decaying according to a slow power
law, i.e., $s_{i}=i^{-\alpha}$ for $\alpha\in(0,1)$. In this case we show,
when the rank $r$ is sufficiently large, that the relative sub-optimality of
gradient descent and ridge regression is on the order of
$\Theta(\lambda_{\star}^{4}/\lambda_{\min}^{2})$. This is summarized in the
following two theorems, the first providing the upper bound and the second a
lower bound.

###### Theorem 2

Let $2/k<\lambda_{\min}\leq\lambda_{\star}\leq 1$,
$\delta=(1-\lambda_{\min})/(k-1)$, $\eta=1/(k\lambda_{\min})$ and
$s_{i}=i^{-\alpha}$ for $i=1,\dots,r$, with $\alpha\in(0,1)$. If $r\geq
2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha})$ and
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for some
$j\in\\{0,\dots,k-2\\}$ and $\varepsilon\in[0,1]$,161616When
$\varepsilon\in\\{0,1\\}$, the denominator equals zero; and in that case we
use the convention that $1/0=+\infty$.

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\frac{1152}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\cdot\left[A(k,r,\alpha,\lambda_{\star},\lambda_{\min})+\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}\right]$

where
$A(k,r,\alpha,\lambda_{\star},\lambda_{\min})=\frac{k^{2}}{r^{1-\alpha}}\left(\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\right)$
and

$\displaystyle\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})=1+\begin{cases}\frac{\lambda_{\star}^{3-1/\alpha}}{3\alpha-1}&\text{if
}\alpha>1/3\\\ 3\log(k\lambda_{\min}/\lambda_{\star})&\text{ if }\alpha=1/3\\\
\frac{1}{1-3\alpha}\left(\frac{k\lambda_{\min}}{\lambda_{\star}^{2}}\right)^{1/\alpha-3}&\text{
if }\alpha<1/3.\end{cases}$ (10)

The upper bound in Theorem 2 goes to infinity as $\varepsilon\rightarrow 0$ or
$\varepsilon\to 1$. We recall that this is due to $\lambda_{\star}$ converging
to a grid point in the discretization of ridge regression. A similar
phenomenon occurs as $\lambda_{\min}\rightarrow 1$, because
$\lambda_{\star}\rightarrow 1$ converges to a grid point. The bound also
diverges as $\lambda_{\min}\rightarrow 0$, because gradient descent performs
many wasteful iterations i.e., $k=1/(\eta\lambda_{\min})\rightarrow\infty$.
Specifically, gradient descent gets compared to ridge regression with
$\delta\rightarrow 0$, which converges to the Bayes optimal estimator, so the
denominator in
$\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
goes to zero.

The bound in Theorem 2 consists of three terms. The first two decrease with
the number of eigenvalues $r$, with the third depending upon the factor
$\lambda_{\star}^{4}/\lambda_{\min}^{2}$. Precisely, defining
$r_{\lambda_{\star},\alpha,k,\lambda_{\min}}^{\text{Upper}}$ as

$\displaystyle
r_{\lambda_{\star},\alpha,k,\lambda_{\min}}^{\text{Upper}}:=\left(\frac{\lambda_{\min}k}{\lambda_{\star}^{2}}\right)^{2/(1-\alpha)}\left(\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\right)^{1/(1-\alpha)},$

then the bound is $O(\lambda_{\star}^{4}/\lambda_{\min}^{2})$ provided the
rank is sufficiently large that $r\geq
r_{\lambda_{\star},\alpha,k,\lambda_{\min}}^{\text{Upper}}$. Each term within
the bound represents the ratio between the error of gradient descent and ridge
regression in different parts of the spectrum (for a precise definition see
Section 2.4). The third term is associated to eigenvalues below the
regularization level, i.e., $s_{i}<\lambda_{\star}$, and becomes the
“dominant” source of error when the eigenvalues decay slowly and the rank is
sufficiently large, i.e., $r\geq
r_{\lambda_{\star},\alpha,k,\lambda_{\min}}^{\text{Upper}}$. Gradient descent
then has a smaller error on these eigenvalues than ridge regression by a
factor of $O(\lambda_{\star}^{2}/\lambda_{\min})$. For details on how this
factor arises see the discussion in Section 2.4.2.

We give a lower bound which shows that the dependence on $\lambda_{\star}$ and
$\lambda_{\min}$ is sharp as the number $r$ of non-zero eigenvalues grows.

###### Theorem 3

Consider the setting of Theorem 2. Moreover, suppose that
$1/(\eta\lambda_{\star})=\ell+\kappa$ for some integer
$\ell\in\\{0,1,2,\dots,k-1\\}$ and $\kappa\in(0,1)$. Then

$\displaystyle\mathcal{S}\\!\left(\mathcal{C}^{\text{GD}}(\eta,\\!k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},\\!k)\right)\\!\geq\\!\frac{\min\\{1-\kappa,\kappa\\}^{2}}{512\min\\{1\\!-\\!\varepsilon,\varepsilon\\}^{2}(1\\!-\\!\lambda_{\min})^{2}}\\!\\!\left(\\!\\!1\\!-\\!\frac{2\left(4k\lambda_{\min}/(\lambda_{\star}^{2}\kappa)\right)^{\frac{1}{\alpha}-1}}{(1-\alpha)r^{1-\alpha}}\\!\right)\\!\\!\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}.$

Theorem 3 implies, when the rank $r$ is large, the ratio of errors is lower
bounded by a factor of $\lambda_{\star}^{4}/\lambda_{\min}^{2}$. Thus, Theorem
2 is sharp in the large $r$ regime. Precisely, define
$r^{\text{Lower}}_{\lambda_{\star},\alpha,k,\lambda_{\min}}$ as

$\displaystyle
r^{\text{Lower}}_{\lambda_{\star},\alpha,k,\lambda_{\min}}:=\left(\frac{4}{1-\alpha}\right)^{1/(1-\alpha)}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha}.$

If $r\geq r^{\text{Lower}}_{\lambda_{\star},\alpha,k,\lambda_{\min}}$, the
lower bound is on the order of $\lambda_{\star}^{4}/\lambda_{\min}^{2}$. When
considering Theorem 1 we see that it is then sufficient to pick
$r_{\lambda_{\star},\alpha,k,\lambda_{\min}}=\max\\{r^{\text{Lower}}_{\lambda_{\star},\alpha,k,\lambda_{\min}},r^{\text{Upper}}_{\lambda_{\star},\alpha,k,\lambda_{\min}}\\}$,
for the upper and lower bounds to be of the same order.

We note that the lower bound goes to zero as $\kappa\rightarrow 1$ or
$\kappa\rightarrow 0$, due to the proof approach. In particular, we leverage
that gradient descent must perform a discrete number of iterations, i.e.,
$\lfloor 1/(\eta\lambda_{\star})\rfloor$ or $\lceil
1/(\eta\lambda_{\star})\rceil$, each of which, respectively, under- or
overshrinks smaller eigenvalues ($s\leq\lambda_{\star})$. For more details see
proof in Appendix B.7.1. This is reasonable as we expect the upper bound to
also decrease in this setting.

Following Theorem 2 and 3, we now consider a low-dimensional setting where the
ambient dimension $d=n^{q}$ for some $q\in(0,1)$. In this case some care is
required when interpreting the bounds, as the optimal regularization
$\lambda_{\star}=O(n^{-(1-q)})$ and rank $r=O(n^{q})$ are coupled to the
sample size $n$ and dimension $d=n^{q}$.

###### Corollary 1

Consider the setting of Theorem 2. Suppose $r=d=n^{q}$ for some
$q\in(1/(\alpha+1),1]$, $\lambda_{\min}=\sigma_{\min}^{2}d/n$ for
$0<\sigma_{\min}<\sigma/\sqrt{2}$ where
$n\geq\max\\{4^{1/(q(1-\alpha))},(4^{1/(1-\alpha)}\sigma^{-2/\alpha})^{\alpha/(q(1+\alpha)-1)},\sigma_{\min}^{2/(1-q)}\\}$
and $k>2n^{1-q}/\sigma_{\min}^{2}$. Then, with
$\tau_{n}=\frac{(\sigma^{2}/\sigma_{\min})^{4}}{n^{2(1-q)}}$ and
$B(\sigma,\alpha,k,\sigma_{\min},n)=\sigma^{-2(\alpha^{-1}-1)}+n^{2(q-1)}(k\sigma_{\min}^{2}/\sigma^{4})^{1/\alpha-3}$,

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\lesssim\\!\frac{1}{\mathrm{Dist}_{\delta}(\lambda_{\star},\Gamma)^{2}}\Bigg{[}\\!\frac{k^{2}\\!\log\left(\\!\frac{k\sigma_{\min}^{2}}{\sigma^{2}}\\!\right)}{n^{q(\alpha^{-1}\\!-\\!\alpha)\\!-\\!\alpha^{-1}+1}}B(\sigma,\alpha,k,\sigma_{\min},n)\\!+\\!\tau_{n}\\!\Bigg{]}.$
(11)

Moreover under the assumptions Theorem 3 the following lower bound holds

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\gtrsim\frac{1}{\mathrm{Dist}_{\delta}(\lambda_{\star},\Gamma)^{2}}\left(1-\frac{(4k\sigma_{\min}^{2}/(\sigma^{4}\kappa))^{1/\alpha-1}}{n^{q(1/\alpha-\alpha)-1/\alpha+1}}\right)\tau_{n}.$
(12)

As the optimal amount of regularization $\lambda_{\star}$ decreases with the
sample size, the upper bound also decreases with the sample size. When
$\sigma,\sigma_{\min},k$ are fixed, the upper bound decreases—up to
logarithmic factors—at an
$O(n^{-\min\\{q(1/\alpha-\alpha)-1/\alpha+1,2(1-q)\\}})$ rate, with
$q>(\alpha\\!+\\!1)/(1\\!+\\!\alpha(2\\!-\\!\alpha))$ yielding a rate matching
the lower bound (12) of $\Theta(n^{-2(1-q)})$. One interpretation of this is
that the rates are optimal provided the rank or dimension, as controlled by
$q$, is sufficiently large.

###  2.3 Eigenvalues Decaying Exponentially or with a Fast Power Law

In this section we consider eigenvalues decaying at either an exponential rate
i.e., for all $i=1,\ldots,r$, $s_{i}=\exp(-\rho(i-1))$, or a fast power law
rate $s_{i}=i^{-\alpha}$ for $\alpha>1$. In this case we show that ridge
regression outperforms gradient descent as the number $k$ of models increases,
regardless of the rank $r$. This is summarized within the following two
theorems, the first considering exponentially decaying eigenvalues and the
second considering eigenvalues that decay at a fast power law rate.

###### Theorem 4

Let $\delta=(1-\lambda_{\min})/(k-1)$, $\eta=1/(k\lambda_{\min})$ and
$s_{i}=\exp(-\rho(i-1))$ for $i=1,2,\dots,r$ with $\rho>0$, for $r\geq
1+{\rho}^{-1}\log(1/\lambda_{\star})$. Furthermore, suppose that
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for some
$j\in\\{0,\dots,k-2\\}$ and $\varepsilon\in[0,1]$. If

$\displaystyle\lambda_{\star}<\frac{1}{2}\left(2e+\frac{4e^{1+\rho}}{1-e^{-\frac{1}{64}}}\right)^{-1}\quad\text{
and }\quad
k\geq\frac{1}{\lambda_{\min}}\max\left\\{64\log\left(1+\frac{1}{\lambda_{\star}}\right),\frac{8e}{\lambda_{\star}}\frac{1+e^{-\rho}}{1-e^{-{64}^{-1}}}\right\\},$
(13)

then

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\geq\frac{C_{\rho}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2},$

where
$C_{\rho}=(1-\exp(-{64}^{-1}))^{3}/[512e^{2}(1+e^{2\rho})(1-e^{-{64}^{-1}}+2e^{\rho})^{2}]$.

###### Theorem 5

Suppose $\delta=(1-\lambda_{\min})/(k-1)$, $\eta=1/(k\lambda_{\min})$ and
$s_{i}=i^{-\alpha}$ for $i=1,2,\dots,r$ and $\alpha>1$, for
$r\geq\lambda_{\star}^{-1/\alpha}$. Furthermore, suppose that
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for some
$j\in\\{0,\dots,k-2\\}$ and $\varepsilon\in[0,1]$. If

$\displaystyle\lambda_{\star}$
$\displaystyle<\frac{1}{2^{1+2\alpha}}\left[1+2^{4+3\alpha}(1-e^{-\frac{1}{64}})^{-1}\right]^{\frac{-\alpha}{\alpha+1}}$
(14) $\displaystyle k$
$\displaystyle\geq\frac{1}{\lambda_{\min}}\max\left\\{64\log\left(1+\frac{1}{\lambda_{\star}}\right),\frac{17\cdot
2^{\alpha}}{\lambda_{\star}^{1-1/\alpha}}\frac{\alpha+1}{\alpha-1}(1-e^{-{64}^{-1}})^{-1}\right\\},$
(15)

then

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\geq\frac{C_{\alpha}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2},$

where
$C_{\alpha}=\frac{\alpha-1}{\alpha}(1-\exp(-{32}^{-1}))^{2}/[32(2^{(1+2\alpha)(2+\alpha(1+\alpha))})(1+2\alpha)(1+2^{4+3\alpha}(1-e^{-\frac{1}{64}}))^{\frac{1+2\alpha}{\alpha+1}}]$.

The theorems state, provided the optimal regularization is smaller than the
specified constants, and the number of models $k$ is large with respect to
$1/(\lambda_{\star}\lambda_{\min})$, that the relative sub-optimality is lower
bounded by a factor independent of $k,\lambda_{\star}$ times
$(\lambda_{\star}k)^{2}$. Thus, as $k$ grows, ridge regression outperforms
gradient descent, since the ratio increases. This behavior aligns with what we
have when we consider gradient descent estimators with all possible
regularization parameters.

The condition on the number of models $k$ differs from the previous results,
in that we now require
$k\gtrsim(\lambda_{\min}\lambda_{\star})^{-1}\gtrsim\lambda_{\star}^{-2}$
whereas Theorem 2 and 3 required $k\gtrsim\lambda_{\min}^{-1}$. This is to
ensure a sufficiently small step size $\eta$ which then ensures certain
technical conditions needed in the proof. We leave refining the lower bound to
values of $k$ within the range $(\lambda_{\star}\lambda_{\min})^{-1}\gtrsim
k\gtrsim\lambda_{\star}^{-1}$ to future work. We note that
$C_{\rho},C_{\alpha}$ decay exponentially in $\rho$ and $\alpha$ respectively,
and thus, the lower bounds remain non-vacuous as $k$ grows, provided
$\rho\lesssim\log(k)$ and $\alpha\lesssim\log(k)$.

###  2.4 Bounds for Individual Classes

In this section we present bounds for the class of estimators associated to
gradient descent and ridge regression. We denote the error for a class of
estimators $\mathcal{C}$ in terms of the gap from optimally tuned ridge
regression (contrast with (4))

$\displaystyle\mathcal{E}(\mathcal{C}):=\min_{\widehat{\beta}\in\mathcal{C}}\left\\{\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})]-\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]\right\\}.$

We define the spectral measure $\widehat{H}$ associated to the eigenvalues
$\\{s_{i}\\}_{i=1}^{r}$, to have a cumulative distribution function, also
denoted as $\widehat{H}$, for all $s\in\mathbb{R}$, given by
$\widehat{H}(s):=\frac{1}{d}\sum_{i=1}^{r}\mathbbm{1}(s_{i}\leq
s)+(1-\frac{r}{d})\mathbbm{1}(0\leq s)$ where $\mathbbm{1}(\cdot)$ is the
indicator function. The following results bound the sub-optimality for a given
class $\mathcal{E}(\mathcal{C})$ in terms of a function integrated against the
the spectral measure $\widehat{H}$. This approach is rather natural, as the
estimation error of optimally tuned ridge regression can be written

$\displaystyle\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\lambda_{\star}})]=\lambda_{\star}\int\frac{1}{s+\lambda_{\star}}d\widehat{H}(s).$
(16)

In our case bounds on $\mathcal{E}(\mathcal{C})$ take the form
$\lambda_{\star}\int G(s)d\widehat{H}(s)$ for an “error” function
$G:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ that describes “where” on the
spectrum the estimator is sub-optimal. Precisely, the function $G$ will depend
upon $\lambda_{\star}$ and encode properties of the class $\mathcal{C}$, e.g.,
the step size $\eta$ and number of iterations $t$ for gradient descent, or the
discretization length $\delta$ for ridge regression. Since $\widehat{H}(s)$ is
an atomic measure, we adopt the convention, for any $b>a$, that
$\int_{b}^{a}d\widehat{H}(s)=\int\mathbbm{1}(s)_{(a,b]}d\widehat{H}(s)$ i.e.,
the integration range is closed on the right and open on the left.

The remainder of this section is then structured as follows. Section 2.4.1
considers classes arising from ridge regression with a uniformly discretized
regularization parameter. Section 2.4.2 considers classes arising from the
iterations of gradient descent.

####  2.4.1 Ridge Regression

The following lemma provides upper and lower bounds on the class of estimators
arising from ridge regression in the case of a fine discretization, i.e.,
where $\delta=(1-\lambda_{\min})/(k-1)\leq\lambda_{\star}$.

######  Proposition 1 (Ridge Regression Estimator, Fine Discretization)

Let $\delta=(1-\lambda_{\min})/(k-1)$. Suppose
$0\leq\lambda_{\min}\leq\lambda_{\star}\leq 1$, $\lambda_{\star}\geq\delta>0$
and $\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for some
$j\in\\{0,1,\dots,k-2\\}$ and $\varepsilon\in[0,1]$. Then

$\displaystyle\frac{1}{2^{5}}\\!\min\\!\\{1\\!-\\!\varepsilon,\varepsilon\\}^{2}\lambda_{\star}\\!\\!\\!\int\\!\\!G^{\text{Ridge}}(s)d\widehat{H}(s)\\!\leq\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\leq\\!4\min\\{1\\!-\\!\varepsilon,\varepsilon\\}^{2}\lambda_{\star}\\!\\!\\!\int\\!\\!G^{\text{Ridge}}(s)d\widehat{H}(s)$

where

$\displaystyle
G^{\text{Ridge}}(s)=\delta^{2}\begin{cases}\frac{1}{\lambda_{\star}s^{2}}&\text{
if }s\in(\lambda_{\star},\infty)\\\ \frac{s}{\lambda_{\star}^{4}}&\text{ if
}s\in(0,\lambda_{\star}].\end{cases}$

Results for tuning ridge regression with either a coarse discretization
$\delta>\lambda_{\star}$ or logarithmic grid are presented within Proposition
5 and 6 in Section A.5.1.

Now, let us rewrite the sub-optimality of ridge regression in terms of a
multiplicative constant of optimally tuned ridge regression, so that for some
constant $C>0$, and $G^{\text{Ridge}}$ from Proposition 1,

$\displaystyle\min_{\widehat{\beta}\in\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)}\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta})]=\lambda_{\star}\int\Big{(}1+CG^{\text{Ridge}}(s)(s+\lambda_{\star})\Big{)}\frac{1}{s+\lambda_{\star}}d\widehat{H}(s).$

We can interpret $CG^{\text{Ridge}}(s)(s+\lambda_{\star})$ as a form of
spectral dependent _risk inflation_. Recalling the discretization length
$\delta=1/k$, and using Propositions 1, 5 and 6, we can take a uniform bound
to get the risk inflation of ridge regression with each discretization

$\displaystyle\max_{s\in(0,s_{1}]}G^{\text{Ridge}}(s)(s+\lambda_{\star})$
$\displaystyle=\frac{2}{k^{2}}\frac{1}{\lambda_{\star}^{2}},\qquad\max_{s\in(0,s_{1}]}G^{\text{Coarse
Ridge}}(s)(s+\lambda_{\star})=\frac{1}{k\lambda_{\star}}$
$\displaystyle\max_{s\in(0,s_{1}]}G^{\text{log-ridge}}(s)(s+\lambda_{\star})$
$\displaystyle=\frac{\log^{2}(1/\lambda_{\min})}{4(k-1)^{2}}.$ (17)

We make two observations. First, for the uniform discretizations, the risk
inflation initially decays at the “slow” rate of $(k\lambda_{\star})^{-1}$ for
$k\leq\lambda_{\star}^{-1}$, and then moves to the fast
$(k\lambda_{\star})^{-2}$ rate for $k\geq\lambda_{\star}^{-1}$. This phase
transition in the number of models $k$ also reflects what is observed in
Section 3.1 for ridge regression with an orthogonal design. Second, as the
log-grid relies on knowing a lower bound $\lambda_{\min}<\lambda_{\star}$ we
see trade-off as to when a log-grid is beneficial over a uniform grid.
Precisely, as the log-grid is favored approximately when
$\log(1/\lambda_{\min})\leq 1/\lambda_{\star}$ or $\lambda_{\min}\geq
e^{-1/\lambda_{\star}}$.

####  2.4.2 Gradient Descent

The following presents the upper and lower bounds for gradient descent. Recall
the definition of $\mathcal{C}^{\text{GD}}(\eta,t)$ provided at the beginning
of Section 2.

######  Proposition 2 (Gradient Descent Estimators, Fine Discretization)

Suppose $0<\lambda_{\star}\leq 1$ and $t\geq\lceil
1/(\eta\lambda_{\star})\rceil$ for a step size $0<\eta\leq
1/\max\\{s_{1},\lambda_{\star}\\}$. Then

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))\leq
18\lambda_{\star}\int G^{\text{GD}}(s)d\widehat{H}(s)$

where

$\displaystyle
G^{\text{GD}}(s)=\begin{cases}\frac{\lambda_{\star}}{s^{2}}&\text{ for
}s\in(\lambda_{\star},1/\eta]\\\ \frac{s^{3}}{\lambda_{\star}^{4}}&\text{ for
}s\in(\eta\lambda_{\star}^{2},\lambda_{\star}]\\\ \eta^{2}s&\text{ for
}s\in(0,\eta\lambda_{\star}^{2}].\end{cases}$ (18)

Furthermore, if $\frac{1}{\eta\lambda_{\star}}=\ell+\kappa$ for some integer
$\ell$ and $\kappa\in(0,1)$, then for any $t\geq 1$

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))\geq\frac{1}{16}\min\\{1-\kappa,\kappa\\}^{2}\lambda_{\star}\int_{0}^{\eta\lambda_{\star}^{2}\kappa/4}G^{\text{GD}}(s)d\widehat{H}(s).$

For ridge regression as studied in Proposition 1, the discretization length
tuning parameter $\delta$ simply scales the error function. In contrast, for
gradient descent, the stepsize $\eta$ does not simply scale the error function
$G^{\text{GD}}$. One interpretation is that ridge regression converges
_uniformly_ as the number of models increases. However, for gradient descent a
non-zero error remains regardless of how small the step size is (see Theorem 8
in Appendix B.8).

Following the discussion after Theorem 2 in Section 2.2, we can see how the
factor of $\lambda_{\star}^{4}/\lambda^{2}_{\min}$ arises within the upper
bound of the relative sub-optimality. Specifically, consider the step size
$\eta=1/(k\lambda_{\min})$ for gradient descent and discretization length
$\delta=1/k$ for ridge regression. Taking the ratio of error functions, we
then have for eigenvalues $s<\eta\lambda_{\star}^{2}$ that
$G^{\text{GD}}(s)/G^{\text{Ridge}}(s)=\lambda_{\star}^{4}/\lambda_{\min}^{2}$.
When considering relative sub-optimality, the corresponding ratio of
expectations $\int G^{\text{GD}}(s)d\widehat{H}(s)/\int
G^{\text{Ridge}}(s)d\widehat{H}(s)$ arises, and therefore, we need to take
into account where the spectrum $\widehat{H}(s)$ “places mass”.

The lower bound in Proposition 2 holds over “part of the spectrum”, in that
the integral is over the range up to $\eta\lambda_{\star}^{2}\kappa/4$. This
lower bound is sharp when there are many eigenvalues within the interval
$[0,\eta\lambda_{\star}^{2}\kappa/4]$, e.g., when the eigenvalues decay at a
slow power law rate. For lower bounds when there is a faster decay in the
eigenvalues, it is natural to focus on the range $(0,\lambda_{\star}]$. In
Theorem 8 in Appendix B.8, a similar lower bound is given for an integral over
the interval $(u_{\min}(\eta),s_{1}]$, for a certain function $u_{\min}$ of
the stepsize, depending on finer notions of the spectrum.

For completeness a bound for gradient descent in the coarse regime $t\lesssim
1/(\eta\lambda_{\star})$ is presented within Proposition 7 in Section A.5.2 of
the supplementary material.

##  3 Minimax Estimation under Orthogonal Designs

For orthogonal designs, we can obtain even more precise results. We find the
_exact minimax optimal_ classes of estimators over a range of signal-to-noise
ratios. Further, we can find the _exact_ sub-optimality of ridge regression
and gradient descent (Section 3.1).

To study the minimax optimal class of $k$ estimators, we consider a parameter
set $\Theta$ of design matrices $X$, signal strengths $\psi$, noise levels
$\sigma$, and a collection $E$ of classes
$T_{k}=\\{\Phi_{1},\ldots,\Phi_{k}\\}$ of $k$ spectral shrinkers
$\Phi_{j}:[0,\infty)\to[0,\infty)$, $j\in[k]$, each determining a
corresponding class of estimators
$\widehat{T_{k}}=\\{\widehat{\beta}_{\Phi_{1}},\ldots,\widehat{\beta}_{\Phi_{k}}\\}$.
171717We will sometimes also call $T_{k}$ a collection, a set, a $k$-tuple,
or—in the scalar case—a grid of estimators. Evaluating the _minimax optimal
excess risk_ over the class $T_{k}\in E$ amounts to finding, for
$[k]=\\{1,\ldots,k\\}$, the following _min-max-min_ problem:

$\inf_{T_{k}=\\{\Phi_{1},\ldots,\Phi_{k}\\}\in
E}\,\sup_{\theta\in\Theta}\,\min_{j\in[k]}\,\mathcal{E}(\widehat{\beta}_{\Phi_{j}}).$
(19)

Here we are minimizing over classes $T_{k}\in E$ the worst-case risk over the
unknown parameters $\theta\in\Theta$ of the _best estimator
$\widehat{\beta}_{\Phi_{j}}$ in the class $T_{k}$_. This is a generalization
of the usual notion of minimax excess risk in statistical decision theory and
learning, which corresponds to classes with size $k=1$, where the inner
minimization is vacuous [LC98, LR05, Ber13].

Since solving problem (19) could be very challenging in general, we consider
parameter spaces $\Theta$ such that all $s_{i}=s>0$ are fixed to some known
value, and $r=n$. This corresponds to an orthogonal design where
$X^{\top}X/n=sI_{d}$. We assume that the noise level is fixed, and without
loss of generality we consider $\sigma=1$. Thus, for some lower and upper
bounds $0\leq\psi_{-}\leq\psi_{+}$ on the signal strength $\psi$, we study the
parameter space

$\Theta=\\{\psi\in[\psi_{-},\psi_{+}],X^{\top}X/n=sI_{d},n=d\\}.$ (20)

We have the following result, proved in Section C.1.

######  Theorem 6 (Minimax Optimal Class for Orthogonal Designs)

Let the parameter set $\Theta$ be defined in (20) and let $\sigma=1$. Consider
the collection $E$ of all classes of $k$ estimators
$T_{k}=\\{\Phi_{1},\ldots,\Phi_{k}\\}$ determined by spectral shrinkers. There
is a minimax optimal class, solving the min-max-min problem (19), of the form

$\widehat{T_{k}}=\left\\{[1-\Phi_{j}(s)]/s\cdot
X^{\top}Y/n,j=1,\ldots,k\right\\},$

where $\Phi_{j}$ are constant functions defined, for all $s\geq 0$, by

$\displaystyle\Phi_{j}(s)=\left[\frac{1}{x_{+}}+\left(j-\frac{1}{2}\right)c\right]^{2}-\frac{c^{2}}{4},$

and $c=\frac{1}{k}(\frac{1}{{x_{-}}}-\frac{1}{{x_{+}}})$, with
$x_{\pm}=\sqrt{1+s\psi_{\pm}}$. The minimax optimal excess risk, i.e., the
optimal value of the objective in (19), is

$\displaystyle M(\psi_{-},\psi_{+},s,k)$
$\displaystyle=\frac{1}{k^{2}s}\left(\frac{1}{\sqrt{1+s\psi_{-}}}-\frac{1}{\sqrt{1+s\psi_{+}}}\right)^{2}.$

The proof is based on a combination of classical mathematical analysis and
explicit calculations, including an “infinite descent” argument to find the
minimizer. Specifically, after some calculations, we can reduce the problem to
evaluating the quantity given in equation (65) in the appendix. This is a
minimum over $k+1$ terms. We argue by contradiction that the solution is
achieved when the $k+1$ quantities in (65) are equal. To show this, we suppose
that at the minimum, the $k+1$ terms are not all equal, and choose the maximal
term. Then, by careful analysis, we verify that by changing one of the
optimization variables in that term, we can decrease the maximal term to equal
its larger neighbor, which is a contradiction to our assumption that we were
at the minimum. Surprisingly, the mini-max optimal grid aligns with gradient
descent with a decreasing learning rate. For details on this see the
discussion within Section A.6.

###  3.1 Sub-optimality compared to the Minimax Grid

It is of interest to characterize the sub-optimality of ridge regression and
gradient descent to the minimax optimal grid. The following result is proved
in Section C.2. Denote by $\\{x\\}$ the fractional part of the scalar $x$, and
by $\lfloor x\rfloor$ its floor, the largest integer less than or equal to
$x$. Denote by
$C_{\text{Ridge}}(\delta)=\\{\widehat{\beta}_{\lambda}\\}_{\lambda\in\\{\delta,2\delta,\dots,1\\}}$
the class of estimators equal to ridge regression with regularization over a
grid $\\{\delta,2\delta,\dots,1\\}$.

######  Proposition 3 (Max-Min Excess Risk of Ridge Regression)

Under the conditions of Theorem 6, let $\delta=1/k$, $\phi=k/\psi_{-}-(\lfloor
k/\psi_{+}\rfloor+1)$, and $\psi_{-}>k/(k+1)$. Then, the worst-case excess
risk of the best estimator in the class $C_{\text{Ridge}}(\delta)$ of ridge
regression estimators with regularization over the grid
$\\{\delta,2\delta,\dots,1\\}$ $=$ $\\{1/k,\ldots,1\\}$ equals

$\sup_{\psi\in[\psi_{-},\psi_{+}]}\min\limits_{\widehat{\beta}\in
C_{\text{Ridge}}(\delta)}\mathcal{E}(\widehat{\beta})=\frac{1}{s}\max\left\\{Q_{\star}(j,\tau^{\star}_{1})^{2},Q_{\star}(j+1,\tau^{\star}_{2})^{2}\right\\}$

where $j=\lfloor k/\psi_{+}\rfloor$, $a=ks$, and

$Q_{\star}(j,\tau)=\frac{a/[j+\tau]}{(1+a/[j+\tau])^{1/2}}\min\left(\frac{\tau}{j+a},\frac{1-\tau}{j+1+a}\right),$
$\displaystyle\tau^{\star}_{1}=\max\left(\left\\{\frac{k}{\psi_{+}}\right\\},\frac{\lfloor
k/\psi_{+}\rfloor+a}{2(\lfloor
k/\psi_{+}\rfloor+a)+1}\right)\\!\\!\quad\quad\\!\\!\text{and}\\!\\!\quad\quad\\!\\!\tau^{\star}_{2}=\min\left(\phi,\frac{\lfloor
k/\psi_{+}\rfloor+1+a}{2(\lfloor k/\psi_{+}\rfloor+1+a)+1}\right).$

The condition $\psi_{-}>k/(k+1)$ requires that $\psi_{-}$ is sufficiently
large, while $\lfloor k/\psi_{+}\rfloor+1\leq k/\psi_{-}$ requires that
$\psi_{+}$ is sufficiently large compared to $\psi_{-}$ and $k$.

If $s=1$, we can verify $\tau_{1}^{*}\in[1/3,1]$, and
$a/[j+\tau_{1}^{*}]=k/[\lfloor k/\psi_{+}\rfloor+\tau_{1}^{*}]=O(\psi_{+})$,
where $A=O(B)$ means that $A\leq CB$ for a constant $C$ not depending on $k$.
Also

$\frac{\tau_{1}^{*}}{j+a}=O\left(\frac{1}{\lfloor
k/\psi_{+}\rfloor+k}\right)=O\left(\frac{1}{k}\right).$

This shows that $Q_{\star}(j,\tau^{\star}_{1})=O(1/k)$. The same reasoning
also shows that $Q_{\star}(j+1,\tau^{\star}_{2})=O(1/k)$. Thus, the upper
bound on the excess risk of ridge is of order at most $O(1/k)$. As we will see
numerically, the rate decays linearly in $1/k$ in certain ranges of $k$, and
linearly in $1/k^{2}$ in other ranges. This is a subtle and perhaps unexpected
behavior that is uncovered by our analysis.

A similar approach allows us to characterize the sub-optimality of gradient
descent. We have the following result, proved in Section C.3. Let
$C_{\text{GD}}(\eta,k)=\\{\hat{\beta}_{\eta,i}\\}_{i=1,\dots,k}$ denote the
class of estimators associated to the first $k$ iterations of gradient descent
initialized at $\hat{\beta}_{\eta,0}=0$ zero, with step size $\eta>0$. We
denote $a\vee b=\max\\{a,b\\}$ as well as $a\wedge b=\min\\{a,b\\}$.

######  Proposition 4 (Max-Min Excess Risk of Gradient Descent)

Under the conditions of Theorem 6 and Proposition 3, consider gradient descent
with step size $0<\eta<1/s$. Let

$b=1-\eta s\in(0,1),\\!\quad
j=\lfloor\log_{1/b}(1+s\psi_{-})\rfloor,\\!\quad\tau^{\star}=\log_{1/b}(2/(b+1)),\\!\quad\tau_{-}=\\{\log_{1/b}(1+s\psi_{-})\\}$

and suppose that $(1-\eta s)^{k}<(1+s\psi_{+})^{-1}.$

Then, the worst-case excess risk of the best iterate of gradient descent out
of the first $k$ iterates equals

$\sup_{\psi\in[\psi_{-},\psi_{+}]}\min\limits_{\widehat{\beta}\in
C_{\text{GD}}(\eta,t)}\mathcal{E}(\widehat{\beta})=b^{j-\tau^{\star}}\max\big{\\{}Q_{\star}(\tau_{-}\vee\tau^{\star})^{2},b\cdot
Q_{\star}(\tau_{-}\wedge\tau^{\star})^{2}\big{\\}},$

where

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

The condition $(1-\eta s)^{k}<(1+s\psi_{+})^{-1}$ requires $\eta$ and $k$ to
be large enough. This assumption ensures that the gradient descent iterates
reach far enough so that the optimal stopping point is before the last
iteration. Relaxing this condition requires a more careful study of the
behavior of the last iteration, which we do not expect to lead to major new
insights. If $s=1$ and $\eta=C/k$ for some constant $C>0$, then $(1-\eta
s)^{k}\leq\exp(-C)$, and thus the aforementioned assumption is satisfied for
$C$ sufficiently large with respect to $\psi_{+}$. From Proposition 4 we then
find that the excess risk is $O(\eta^{2})=O(1/k^{2})$, since the maximum of
$Q_{\star}(\tau)$ is achieved at $\tau^{\star}$, and
$b^{\tau^{\star}}=(1+b)/2=1-\eta/2$.

###  3.2 Experiments

Numerical results are provided to support the results for orthogonal designs.
Figure 4 shows an agreement between the theoretical results and numerically
approximated minimax excess risks. The left plot of Figure 5 shows that
gradient descent decays at the same $O(k^{-2})$ rate as the optimal grid in
Theorem 6. In contrast, ridge regression’s excess risk decays at the rate
$O(k^{-1})$ for small $k$, and then, seemingly, switches between rates of
decay of $O(k^{-2})$ and $O(k^{-1})$. The right plot of Figure 5, shows how
different methods distribute their shrinkers (i.e., the values $\phi_{j}$) in
the interval $(0,1)$. Gradient descent and the optimal grid place more mass
towards the ordinary least squares (OLS) model than ridge regression tuned
over a uniform grid.

Figure 4: Plots of minimax excess risk versus discretization size
$k\in[10^{1.2},10^{4}]$ for different methods: Left: Optimal grids, Middle:
Ridge regression, Right: Gradient descent. Orange Line: Indicates estimate of
minimax excess risk by discretizing $[\psi_{-},\psi_{+}]$ into $10^{5}$ points
(to evaluate supremum in (19)), Blue Line: Theoretical quantity. Gradient
descent step size $\eta=8/k$.

Figure 5: Left: Lines indicate the theoretical minimax risk for each class
from Figure 4 plotted side-by-side, with points showing numerical estimates.
Right: Histogram of spectral shrinkers for the orthogonal design case with
various methods: gradient descent, Optimal: optimal design, and Ridge: ridge
regression with uniform discretization. OLS Model: Ordinary Least Squares
Model.

##  4 Conclusion

We have introduced a framework to compare the statistical performance of
_classes of estimators_. In linear regression with a random ground truth, we
have compared gradient descent and ridge regression. We have found that, if
the rank of the empirical covariance matrix is sufficiently large, the _rate_
at which the eigenvalues decays influences whether gradient descent or ridge
regression is better, with a _slower decay_ leading to more favorable behavior
for gradient descent over. This is surprising, as for the infinitely large set
of all regularization parameters, the situation is reversed. Our work lays
foundations to investigate how classes of estimators—e.g., those obtained by
implicit or explicit regularization—should be constructed and adapted to a
specific problem instance, instead of considering optimally tuned estimators.

## Acknowledgements

ED was supported in part by the NSF grants BIGDATA (1837992), CAREER
(2046874), and the NSF–Simons Foundation Award on the Mathematical and
Scientific Foundations of Deep Learning (2031895). PR was supported in part by
the Alan Turing Institute under the EPSRC grant EP/N510129/1.

##  Appendix A Additional Results and Discussion

In this section we present additional results and discussion to support the
main body of the manuscript. This section is structured as follows.

  * •

Section A.1 discusses additional related literature related to shrinkage
estimators for least squared regression (Section 1.1)

  * •

Section A.2 compares the performance of ridge regression tuned with a
logarithmic grid to gradient descent when the eigenvalues decay slowly
(Theorem 7).

  * •

Section A.3 includes discussion of the framework investigated within this work
as well as future research direction (Section 2).

  * •

Section A.4 presents a proof sketch of Theorem 1 which compares ridge
regression to gradient descent with eigenvalues that decay at different rates
(Section 2).

  * •

Section A.5 considers the performance of individual classes of ridge
regression and gradient descent models in the coarse regime, as well as ridge
regression tuned with a logarithmic grid (Section 2.4).

  * •

Section A.6 investigates the structure of spectral shrinkers in the orthogonal
design case, and shows that gradient descent with a polynomial decreasing step
size equals the minimax grid (Section 3).

###  A.1 Related Literature

Our work is related to the study of the asymptotic performance of ridge
regression in a high-dimensional setting where both the ambient dimension and
number of data points go to infinity in proportion to one another, e.g.,
[TV04, EKK11, EK18, Dic13, Dic16, DW18, HMRT19, AKT19, ADT20, RMR21, WX20,
LD19] etc. Assuming the data follows a linear model or certain nonlinear
models, the works [Dic16, DW18, HMRT19, AKT19, ADT20, RMR21, WX20, LD19] study
the estimation and prediction error of ridge regression in terms of integrals
against the eigenvalue distribution of the empirical covariance matrix. By
making assumptions on the covariate structure, they leverage the convergence
of the empirical eigenvalue distribution to variants of the Marchenko–Pastur
law [MP67, BS10] to obtain results in terms of population quantities. While
our results are in terms of the eigenvalue spectrum, we alternatively focus on
the fixed design setting with spectral distributions that are distinct from
those classically studied in random matrix theory, such as eigenvalues with a
power law or exponential decay. Such distributions have been observed
empirically in many different applications, including in finance, biology, and
signal processing. For examples, see Section 8 of the arXiv version of the
paper [Dob17].

Our focus differs from the literature on tuning regularization for least
squares via cross-validation [AC10, KKV11, MM18, XMR19, HMRT19, PWRT21], which
considers empirical model selection criteria and their consistency. Similarly,
the works [BM01, BGH09, AB09, AM09, BY20] investigate selection criteria
aiming to recover the performance of the best-in-class model (often referred
to as oracle within). In contrast, we focus on choosing the class of models
which arises from, for instance, a _finite grid of regularization parameters_.

For an orthogonal design matrix, the least squares problem reduces to mean
estimation. However, unlike the usual setting where the mean parameter is
fixed, here we consider a random-effects model where the mean parameter is
isotropically distributed, and are interested in the average-case behavior
over this prior. In this sense, our work has a Bayesian interpretation [LC98,
Ber13].

There is a great deal of other work studying statistical properties of
optimization methods. [SGB94] show that in linear models, early stopped
gradient flow on the ridge regression objective with a sufficiently small
positive regularization parameter can outperform ridge regression in
estimation error for _a fixed design and regression parameters_. In contrast,
for the random-effects models we consider, ridge regression is average-case
(i.e., Bayes) optimal under certain assumptions. Other connections between
algorithmic regularization and penalization have also been studied [QQ19].

The related work [DFKU13] shows that the estimation risk of ridge regression
and principal component regression are within a multiplicative factor of four.
Our approach is distinctly different, beyond just considering a different pair
of estimators (early stopped gradient descent in place of principal component
regression). First, [DFKU13] compares estimators with the _same_
hyperparameter choice (denoted $\lambda>0$), while we compare each estimator
with their _best_ hyperparameter choice from two given sets. This is motivated
from the best hyperparameter choice for principal component regression (or any
general estimator) potentially not aligning with that for ridge regression.
Second, our analysis also accounts for finding the best regularization
parameter (by searching over a grid, say). This depends upon the estimator’s
sensitivity with respect to its hyperparameter, specifically, the change due
to the grid resolution around the optimal hyperparameter choice, and can
result in estimators outperforming ridge regression (Theorem 1). As principal
component regression can be represented via a spectral shrinker, one future
research direction is to extend the results of [DFKU13] into the framework
developed within our work.

###  A.2 Ridge Regression with Logarithmic Grid versus Gradient Descent

If $\Gamma=\\{\lambda_{j}\\}_{j=1}^{k}$ is a grid of strictly positive values,
then we denote $\log(\Gamma)=\\{\log(\lambda_{j})\\}_{j=1}^{k}$. Additionally,
define for $k\geq 2$ and $\lambda_{\min}>0$ the collection of ridge regression
estimators tuned over a logarithmic grid as

$\mathcal{C}^{\text{log-
Ridge}}(\lambda_{\min},k):=\\{\widehat{\beta}_{\lambda_{j}}:\lambda_{j}=\exp\left(-(j-1)\log(1/\lambda_{\min})/(k-1)\right),\,j=1,\dots,k\\}.$

With this we have the following result.

###### Theorem 7

Suppose $0<\sigma_{\min}<\sigma/\sqrt{2}$ with
$\lambda_{\min}=d\sigma^{2}_{\min}/n$. For $k>1$ let
$\eta=1/(k\lambda_{\min})$ and assume $k\geq 3/\lambda_{\min}$ and
$(\eta\lambda_{\star})^{-1}\not\in\\{0,1,2,3,\dots,k-1\\}$. Let
$\delta=\log(1/\lambda_{\min})/(k-1)$ with
$\lambda_{j}=\exp\big{(}-(j-1)\delta\big{)}$ for $j\geq 1$ and
$\Gamma=\\{\lambda_{j}\\}_{j=1}^{k}$. Suppose $s_{i}=i^{-\alpha}$ for
$i=1,\dots,r$, $\alpha\in(0,1)$. Then there exists a threshold
$r_{\alpha,\lambda_{\star},k,\lambda_{\min}}>1$, such that if $r\geq
r_{\alpha,\lambda_{\star},k,\lambda_{\min}}$, then

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{$\log$-Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\simeq\frac{1}{\mathrm{Dist}_{\delta}(\log(\lambda_{\star}),\log(\Gamma))^{2}}\frac{1}{\log^{2}(n/(d\sigma_{\min}^{2}))}\frac{\sigma^{4}}{\sigma_{\min}^{4}}.$

The above theorem shows that the relative sub-optimality scales in this case
as $\Theta(\log^{-2}(1/\lambda_{\star}))$ when other parameters are fixed,
when $\sigma_{\min}=\Theta(\sigma)$ and the eigenvalues decay according to a
slow polynomial power $s_{i}=i^{-\alpha}$ for $1\geq\alpha>0$. This reflects
Theorem 1 above, in that the relative sub-optimality goes to zero when the
optimal regularization $\lambda_{\star}=d\sigma^{2}/n$ goes to zero, i.e.,
$d/n\rightarrow 0$ or $\sigma\rightarrow 0$. We note the change from a
polynomial decay in $\lambda_{\star}$ in Theorem 1 to a logarithmic decay in
Theorem 7. Thus we expect that the performance of ridge regression over a
logarithmic grid is closer to that of gradient descent, as
$\lambda_{\star}\rightarrow 0$ in this case.

###  A.3 Discussion of our framework: Gradient Descent versus Ridge Regression

Our framework aims to address the issue that hyperparameter tuning can
strongly affect the behavior of algorithms. Already in a very simple setting,
namely in random effects linear models, we show that this leads to a
sophisticated behavior of the relative performance of two truly fundamental
classes of regularization methods: ridge regression and gradient descent. This
discovery is only possible due to our framework of comparing best in class
algorithms; which in our view demonstrates the power of our perspective.

There are a number of important further considerations to discuss.

  1. 1.

In future work, certain key algorithmic considerations need to be taken into
account for a more thorough comparison between methods. For instance, as we
have shown, our framework can be extended to incorporate that some algorithms
are computationally more expensive than others, by simply changing the class
of algorithms to match the computational cost. In addition, it will be
important to apply it to study more sophisticated classes of algorithms, and
for more general data generating models.

  2. 2.

At the moment, our framework compares methods according to their true expected
performance on the test distribution. In practice, the methods would be
compared after having selected the best-in-class on a finite training dataset,
and according to their performance on a finite a test set. This will introduce
some amount of noise, and thus has to be taken into account in the analysis.
However we expect that with sufficiently large training and test sets, our
conclusions would largely be unchanged. The analysis of the noise due to the
finiteness of the training and test set remains an important future problem.

###  A.4 Proof Sketch for Theorem 1

We begin by following the proof of Lemma 1 which, if we denote
$M_{\Phi}(s)=1-\Phi(s)s$, expresses the excess estimation error of
$\widehat{\beta}_{\Phi}$ as

$\displaystyle\mathcal{E}(\widehat{\beta}_{\Phi})=\frac{\lambda_{\star}}{d}\sum_{i=1}^{r}\left(\frac{1}{\lambda_{\star}}+\frac{1}{s_{i}}\right)\left(M_{\Phi}(s_{i})-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}.$

We then consider the appropriate ridge regression classes
$\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)$
=$\\{\widehat{\beta}_{\Phi^{\text{Ridge}}_{i}}\\}_{i=1,\dots,k}$ where
$M_{\Phi_{i}^{\text{Ridge}}}(s)=(\lambda_{\min}+(i-1)\delta)/(s+(\lambda_{\min}+(i-1)\delta))$;
and gradient descent classes
$\mathcal{C}^{\text{GD}}(\eta,k)=\\{\widehat{\beta}_{\Phi^{\text{GD}}_{i}}\\}_{i=1,\dots,k}$
where $M_{\Phi_{i}^{\text{GD}}}(s)=(1-\eta s)^{i}$. We begin by bounding the
best-in-class error for each method, i.e., the performance of the best model
in each class $\min_{\widehat{\beta}\in\mathcal{C}}\mathcal{E}(\mathcal{C})$,
after which we take the ratio. Bounding the performance of the best-in-class
models is described in the following two paragraphs, with their ratio
considered in a third paragraph.

Best-in-Class for Ridge Regression. If we denote
$\lambda_{i}=\lambda_{\min}+(i-1)\delta$ for $i=1,\dots,k$, and recall that
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$, the best-in-class
error for ridge regression reduces to evaluating the following minimum

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
$\displaystyle=\lambda_{\star}\min_{t=1,\dots,k}\frac{1}{d}\sum_{i=1}^{r}\left(\frac{1}{\lambda_{\star}}+\frac{1}{s_{i}}\right)\left(\frac{\lambda_{t}}{\lambda_{t}+s}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}$
$\displaystyle=\lambda_{\star}\min_{\kappa=\\{-\varepsilon,1-\varepsilon\\}}\frac{1}{d}\sum_{i=1}^{r}\left(\frac{1}{\lambda_{\star}}+\frac{1}{s_{i}}\right)\frac{s_{i}^{2}\kappa^{2}\delta^{2}}{(\lambda_{\star}+\kappa\delta+s_{i})^{2}(\lambda_{\star}+s_{i})^{2}},$

where the second equality arises from monotonicity, allowing the minimum to be
reduced to the two regularization choices in $\\{\lambda_{i}\\}_{i=1,\dots,k}$
closest to $\lambda_{\star}$. When $\varepsilon=1/2$ and the discretization
length is smaller than the optimal regularization $\delta\leq\lambda_{\star}$,
each term in the series is then on the order
$\delta^{2}\frac{s}{\lambda_{\star}}\frac{1}{(s+\lambda_{\star})^{3}}$, with
the factor in-front of $\delta^{2}$ describing the sensitivity to the
discretization length. When $s>\lambda_{\star}$ this factor is roughly
$\frac{1}{\lambda_{\star}s^{2}}$, and for $s<\lambda_{\star}$ is roughly
$\frac{s_{i}}{\lambda_{\star}^{4}}$, allowing us to then write

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))$
$\displaystyle\simeq\lambda_{\star}\delta^{2}\frac{1}{d}\left(\sum_{s_{i}>\lambda_{\star}}\frac{1}{\lambda_{\star}s^{2}}+\sum_{s_{i}\leq\lambda_{\star}}\frac{s_{i}}{\lambda_{\star}^{4}}\right).$
(21)

Best-in-Class for Gradient Descent. The best-in-class error in this case
reduces to evaluating the following minimum

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,k))=\lambda_{\star}\min_{t=1,\dots,k}\frac{1}{d}\sum_{i=1}^{r}\left(\frac{1}{\lambda_{\star}}+\frac{1}{s_{i}}\right)\left((1-\eta
s_{i})^{t}-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2}.$

The first step is to switch from an iteration viewpoint, i.e., $t=1,\dots,k$,
to an eigenvalue perspective. We consider the optimal per-eigenvalue-iteration
$t^{\star}$ as the possibly non-integer-valued iteration number which matches
the optimally tuned ridge regression estimator for eigenvalue $s$, i.e., for
which $(1-\eta s)^{t^{\star}(s)}=\lambda_{\star}/(\lambda_{\star}+s)$. If we
choose
$t=\lceil(\eta\lambda_{\star})^{-1}\rceil\geq(\eta\lambda_{\star})^{-1}=\max_{s\in[0,1/\eta]}t^{\star}(s)$
we can then bound

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,k))\lesssim\lambda_{\star}\frac{1}{d}\left(\sum_{i:s_{i}>\lambda_{\star}}\frac{\lambda_{\star}}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}\frac{1}{s_{i}}\left(1-(1-\eta
s)^{\lceil(\eta\lambda_{\star})^{-1}\rceil-t^{\star}(s_{i})}\right)^{2}\right),$

where for $s>\lambda_{\star}$ we have
$0\leq\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}\leq\frac{\lambda_{\star}}{s}$ and for $s\leq\lambda_{\star}$ we bound
$\frac{\lambda_{\star}}{\lambda_{\star}+s}-(1-\eta
s)^{t}=\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}(1-(1-\eta
s)^{t-t^{\star}(s)})\leq(1-(1-\eta s)^{t-t^{\star}(s)})$. The second series
depends upon the smoothness of $t^{\star}(s)$ through the difference
$\lceil(\eta\lambda_{\star})^{-1}\rceil-t^{\star}(s)$. A technical result
(Proposition 8) then shows, when $\eta\lambda_{\star}\leq 1$, that for
$s\in[0,\lambda_{\star}]$

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

Using this, with $\lceil x\rceil\leq x+1$ alongside Bernouli’s inequality
$(1+x)^{r}\geq 1+xr$ for $r\geq 1$ and $x\geq-1$, then yields the upper bound
$1-(1-\eta
s)^{\lceil(\eta\lambda_{\star})^{-1}\rceil-t^{\star}(s_{i})}\lesssim\eta
s(1+\frac{s}{\eta\lambda_{\star}^{2}})$. Plugging this in we arrive at

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,k))\lesssim\frac{\lambda_{\star}}{d}\left(\sum_{i:s_{i}>\lambda_{\star}}\frac{\lambda_{\star}}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}\max\big{\\{}\eta^{2}s_{i},\frac{s_{i}^{3}}{\lambda_{\star}^{4}}\big{\\}}\right).$
(22)

Ratio of Best-in-Class Performances. Taking the ratio of (22) and (21) we find

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\lesssim\frac{1}{\delta^{2}}\frac{\sum_{i:s_{i}>\lambda_{\star}}\frac{\lambda_{\star}}{s_{i}^{2}}}{\sum_{s_{i}\leq\lambda_{\star}}\frac{s_{i}}{\lambda_{\star}^{4}}}+\frac{1}{\delta^{2}}\frac{\sum_{i:s_{i}\leq\lambda_{\star}}\max\big{\\{}\eta^{2}s_{i},\frac{s_{i}^{3}}{\lambda_{\star}^{4}}\big{\\}}}{\sum_{i:s_{i}\leq\lambda_{\star}}\frac{s_{i}}{\lambda_{\star}^{4}}}.$
(23)

When $\sum_{s_{i}\leq\lambda_{\star}}s_{i}$ is large, e.g.,
$s_{i}=i^{-\alpha}$ for $\alpha\in(0,1)$, and $r$ large, the second term will
then dominate. Since the maximum in the numerator is $\eta^{2}s_{i}$ for
$s_{i}\leq\eta\lambda_{\star}^{2}$, the second term is on the order of
$\frac{\eta^{2}}{\delta^{2}}\lambda_{\star}^{4}=\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}\frac{1}{(1-\lambda_{\min})^{2}}$,
where we recall that $\eta=(k\lambda_{\min})^{-1}$ and
$\delta=(1-\lambda_{\min})/(k-1)$. More generally, the bound for this
expression arises from the error of ridge regression with respect to
eigenvalues below the regularization level—$s_{i}\leq\lambda_{\star}$—scaling
as $\frac{\delta^{2}}{\lambda_{\star}^{4}}$, whereas the error of gradient
descent for $s_{i}\leq\eta\lambda_{\star}^{2}$ scales as $\eta^{2}$.

###  A.5 Bounds for Individual Classes

In this section present additional bounds for classes of estimators associated
to gradient descent and ridge regression, complimenting results contained
within Section 2.4. Section A.5.1 has results associated to ridge regression.
Section A.5.2 presents results associated to gradient descent.

####  A.5.1 Ridge Regression

We provide the bound for the case of a coarse discretization
$\delta=(1-\lambda_{\min})/(k-1)>\lambda_{\star}$.

######  Proposition 5 (Ridge Regression Estimator, Coarse Discretization)

Let $\lambda_{\min}=0$, $\delta=(1-\lambda_{\min})/(k-1)$ and suppose
$\lambda_{\star}=\delta-\delta^{\prime}$ for some
$\delta/2\geq\delta^{\prime}>0$. Then

$\displaystyle\frac{1}{4}\left(\frac{\delta^{\prime}}{\delta}\right)^{2}\lambda_{\star}\int
G^{\text{Coarse
Ridge}}(s)d\widehat{H}(s)\leq\mathcal{E}(\mathcal{C}^{\text{Ridge}}(0,k))\leq\left(\frac{\delta^{\prime}}{\delta}\right)^{2}\lambda_{\star}\int
G^{\text{Coarse Ridge}}(s)d\widehat{H}(s)$

where

$\displaystyle G^{\text{Coarse
Ridge}}(s)=\frac{s}{\lambda_{\star}(s+\lambda_{\star})}\min\left\\{\frac{\delta^{2}}{s^{2}},1\right\\}.$
(24)

We now provide the bound for a logarithmic grid.

######  Proposition 6 (Ridge Regression Estimator, Log-Grid Discretization)

Assume for some $k>j_{\star}>2$ and $\epsilon\in(0,1)$ that
$\lambda_{\star}=\exp\big{(}(j_{\star}-2+\epsilon)\log(\lambda_{\min})/(k-1)\big{)}$
as well as that $k\geq 1+3\log(1/\lambda_{\min})$. Then

$\displaystyle\frac{\min\\{\epsilon,\\!1\\!-\\!\epsilon\\}}{12}\lambda_{\star}\\!\\!\int\\!\\!G^{\text{$\log$-Ridge}}\\!(s)d\widehat{H}(s)\\!\leq\\!\mathcal{E}(\mathcal{C}^{\text{$\log$-Ridge}}\\!(\lambda_{\min},\\!k))\\!\leq\\!\min\\{\epsilon,\\!1\\!-\\!\epsilon\\}\lambda_{\star}\\!\\!\int\\!\\!G^{\text{$\log$-Ridge}}\\!(s)d\widehat{H}(s)$

where

$\displaystyle
G^{\text{$\log$-Ridge}}(s)=\frac{\log^{2}(1/\lambda_{\min})}{(k-1)^{2}}\frac{s\lambda_{\star}}{(\lambda_{\star}+s)^{3}}.$

####  A.5.2 Gradient Descent

We now provide an upper bound on the error of gradient descent in a coarse
discretization regime when $t\lesssim 1/(\eta\lambda_{\star})$.

######  Proposition 7 (Gradient Descent Estimators, Coarse Discretization)

Let $\lambda_{\min}=0$, $0<\eta<1/\max\\{s_{1},\lambda_{\star}\\}$ and
$t<\frac{1-\eta\lambda_{\star}}{2\eta\lambda_{\star}}$. Then

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))\leq
2\lambda_{\star}\int G^{\text{Coarse GD}}(s)d\widehat{H}(s)$

where

$\displaystyle G^{\text{Coarse
GD}}(s)=\begin{cases}\frac{\lambda_{\star}}{s^{2}}&\text{ for
}s\in\big{(}\frac{1}{\lambda_{\star}(\eta t)^{2}},\frac{1}{\eta}\big{]}\\\
\frac{1}{\lambda_{\star}(\eta ts)^{4}}&\text{ for }s\in\big{(}\frac{1}{\eta
t},\frac{1}{\lambda_{\star}(\eta t)^{2}}\big{]}\\\
\frac{1}{\lambda_{\star}}&\text{ for }s\in(\lambda_{\star},\frac{1}{\eta
t}]\\\ \frac{s}{\lambda_{\star}^{2}}&\text{ for
}s\in(0,\lambda_{\star}].\end{cases}$ (25)

###  A.6 Comparing Grids for Orthogonal Designs

We can compare other grids with the minimax optimal grid via their spectral
filters, defined as $\Phi_{j}$, for $j=1,\dots,k$. Since the design is
isotropic, any spectral shrinker is a constant over the spectrum. Thus, by
fixing $s$ from (20), we can view the filters as constants in $s$, and only a
function of $j$, denoting them as $\phi_{j}$:

$\phi_{j}=\Phi_{j}(s).$

We can express the spectral filters of several methods as follows.

  1. 1.

Ridge Regression: For a general design, the spectral filter is
$\Phi_{j}(s)=\lambda_{j}/(\lambda_{j}+s)$ for some $\lambda_{j}>0$. As a
function of $j$, for a uniform discretization we have $\lambda_{j}=j/k$. Thus,
the filter values are $\phi_{j}=a^{\prime}j/(a^{\prime}j+b^{\prime})$,
$j=1,\ldots,k$, for certain $a^{\prime},b^{\prime}>0$.

  2. 2.

Gradient Descent: For a general design, the spectral filter is
$\Phi_{j}(s)=(1-\eta s)^{j}$ as a function of the iteration $j$, for some
$0<\eta<1/s$. It is convenient to sort these values in increasing order in
$j$, consistent with the other methods, writing $\phi_{j}=b_{0}/b^{j}$ for
some $b_{0}>0$ and $b=1/(1-\eta s)>1$.

  3. 3.

Minimax Optimal: We have shown in Theorem 6 that the minimax optimal grid is
$\phi_{j}=(A+Bj)^{2}-C^{2}$, for certain $A,B,C>0$.

Thus as a function of $j$, the grids have the form:

$\displaystyle a^{\prime}j/(a^{\prime}j+b^{\prime}),\qquad
b_{0}/b^{j},\qquad(A+Bj)^{2}-C^{2}.$

They are normalized to take values in the range $[0,1]$. Most of the values of
the GD grid are concentrated around its minimum. This and the minimax optimal
grid ares _convex_ 181818We recall that a sequence $(a_{k})_{k\geq 1}$ is
convex if $a_{k+1}+a_{k-1}\geq 2a_{k}$ for all $k\geq 2$, see e.g., [WV73]. in
$j$. The ridge grid is _concave_ in $j$.

GD with Decreasing Learning Rate can be Minimax Optimal. It turns out that
taking an appropriately decreasing learning rate in GD leads to the minimax
optimal grid. One can verify that the minimax optimal grid values $\phi_{j}$
can be written as $\phi_{j}=a_{j-1}a_{j}$, where $a_{j}={x_{+}}^{-1}+jc$,
$j=0,\ldots,k$ is an arithmetic progression going from $x_{+}^{-1}$ to
$x_{-}^{-1}$. Since we sort the grids in increasing order, GD with learning
rate $\eta_{j}\in(0,1/s)$ at the $j$-th iteration obeys the recursion
$\phi_{j+1}=\phi_{j}/(1-\eta_{j}s)$. To match this with the minimax grid, we
need

$\displaystyle 1-\eta_{j}s$
$\displaystyle=\phi_{j}/\phi_{j+1}=[a_{j-1}a_{j}]/[a_{j}a_{j+1}]=a_{j-1}/a_{j+1}$
$\displaystyle=[{x_{+}}^{-1}+(j-1)c]/[{x_{+}}^{-1}+(j+1)c]=1-2c/[{x_{+}}^{-1}+(j+1)c].$

This shows that the matching learning rate schedule for GD has the form

$\displaystyle\eta_{j}$
$\displaystyle=\frac{2c}{s\cdot[{x_{+}}^{-1}+(j+1)c]}.$

Such learning rate schedules are well known in optimization [Nes13]. For
instance, for such a learning rate one can get an $O(1/j)$ convergence rate,
where $j$ is the number of iterations, for stochastic gradient descent on
strongly convex functions, see e.g., Theorems 5, 6 of [VBS18] for results in
this direction.

In contrast, representing the minimax optimal grid as ridge regression
estimators over a certain regularization grid does not appear to lead to a
cleanly expressed grid.

##  Appendix B Proofs for Gradient Descent and Ridge Regression with General
Designs

In this section we present the proofs associated to the estimation error of
gradient descent and ridge regression for general design matrices.

  * •

Section B.1 presents the proof of Lemma 1 which decomposes the estimation
error of any estimator $\widehat{\beta}_{\Phi}$ into the estimation error of
optimally tuned ridge regression plus a non-zero term.

  * •

Section B.2 summarizes the relative sub-optimality between ridge regression
and gradient descent with eigenvalues that decay at different rates (Theorem
1).

  * •

Section B.5 considers upper and lower bounds on the relative sub-optimality
between ridge regression and gradient descent with eigenvalues that decay at a
slow power law, in the low dimensional case (Corollary 1).

  * •

Section B.3 compares the performance of ridge regression and gradient descent
when the eigenvalues decay at a slow power law rate, in the general case
(Theorem 2 and 3).

  * •

Section B.4 considers formal results associated to the limits presents within
the contribution section (Corollary 2 and 3).

  * •

Section B.6 has estimation error bounds for classes of estimators constructed
from ridge regression with a discretized regularization parameter (Proposition
1 and 5).

  * •

Section B.7 has estimation error bounds for classes of estimators constructed
from gradient descent iterates (Proposition 2 and 7).

  * •

Section B.8 has results that compare the performance of ridge regression and
gradient descent when the eigenvalues decay either exponentially or with a
fast power law rate (Theorem 4 and 5).

  * •

Section B.9 summarizes the relative sub-optimality between ridge regression
tuned with a logarithmic grid and gradient descent when the eigenvalues decay
at a slow power law rate (Theorem 7).

###  B.1 Proof of Lemma 1

For simplicity of notation, we assume without loss of generality that
$\psi=1$. This can always be achieved by rescaling the problem. Performing a
standard bias and variance decomposition and using the independence of
$\epsilon$ and $\beta_{\star}$, recalling (3), gives

$\displaystyle\mathbf{E}_{\beta_{\star},\epsilon}[L_{\beta_{\star}}(\widehat{\beta}_{\Phi})]=\mathbf{E}_{\beta_{\star},\epsilon}[\|\widehat{\beta}_{\Phi}-\mathbf{E}_{\epsilon}[\widehat{\beta}_{\Phi}]\|_{2}^{2}]+\mathbf{E}_{\beta_{\star}}[\|\mathbf{E}_{\epsilon}[\widehat{\beta}_{\Phi}]-\beta_{\star}\|_{2}^{2}]$
$\displaystyle=\frac{\sigma^{2}}{n}\operatorname{Tr}\left(\Phi\left(\frac{X^{\top}X}{n}\right)\frac{X^{\top}X}{n}\Phi\left(\frac{X^{\top}X}{n}\right)\right)$
$\displaystyle\quad\quad+\frac{1}{d}\operatorname{Tr}\left(\left(I-\Phi\left(\frac{X^{\top}X}{n}\right)\frac{X^{\top}X}{n}\right)\left(I-\Phi\left(\frac{X^{\top}X}{n}\right)\frac{X^{\top}X}{n}\right)^{\top}\right)$
$\displaystyle=\frac{d-r}{d}+\frac{1}{d}\sum_{i=1}^{r}(1-\Phi(s_{i})s_{i})^{2}+\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\Phi(s_{i})^{2}s_{i}.$

Denoting $M_{\Phi}(s)=1-\Phi(s)s$ and
$\zeta=1/\lambda_{\star}=n/(d\sigma^{2})$, we then find

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

Since for $s>0$

$\displaystyle\zeta M_{\Phi}(s)^{2}+\frac{(1-M_{\Phi}(s))^{2}}{s}$
$\displaystyle=\frac{(1+\zeta s)}{s}\left(M_{\Phi}(s)-\frac{1}{1+\zeta
s}\right)^{2}+\frac{1}{1/\zeta+s},$

we find

$\displaystyle\mathbf{E}_{\epsilon,\beta_{\star}}[L_{\beta_{\star}}(\widehat{\beta}_{\Phi})]$
$\displaystyle=\frac{d-r}{d}+\sigma^{2}\frac{1}{n}\sum_{i=1}^{r}\frac{1}{1/\zeta+s_{i}}+\frac{\sigma^{2}}{n}\sum_{i=1}^{r}\frac{(1+\zeta
s_{i})}{s_{i}}\left(M_{\Phi}(s_{i})-\frac{1}{1+\zeta s_{i}}\right)^{2}$
$\displaystyle=\frac{d}{n}\sigma^{2}\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(M_{\Phi}(s_{i})-\frac{\lambda_{\star}}{\lambda_{\star}+s_{i}}\right)^{2},$

where we recall $\lambda_{\star}=1/\zeta$ and the probability measure
$\widehat{H}(s)$ associated to the eigenvalues $\\{s_{i}\\}_{i=1}^{r}$ with a
point mass of $(1-r/d)$ at zero. Thus Lemma 1 holds because the rightmost term
is non-negative, and zero when the estimator $\widehat{\beta}_{\Phi}$ equals
ridge regression with penalization $\lambda=\lambda_{\star}$, i.e.
$\Phi(s_{i})=\frac{s_{i}}{s_{i}+\lambda_{\star}}$ for $i=1,\dots,r$.

For a general $\psi$ possibly different from unity, we obtain with
$\zeta=(n\psi)/(d\sigma^{2})$ that

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

###  B.2 Proof of Theorem 1

The proof of Theorem 1 is split into two cases: Slow Power Law Decay, and Fast
Power Law or Exponential decay, which we present in turn.

Slow Power Law Decay. Since $s_{1}=1$, the condition
$k>\max\\{s_{1},2\\}/\lambda_{\min}$ from Theorem 2 holds, thus from that
result, if

$\displaystyle r\geq$ $\displaystyle
M:=\max\left\\{\left(\frac{\lambda_{\min}k}{\lambda_{\star}^{2}}\right)^{2/(1-\alpha)}\left(\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\right)^{1/(1-\alpha)},2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha})\right\\}$

then we have the upper bound

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\frac{2304}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}.$

Meanwhile from Theorem 3 we see that once

$\displaystyle
r\geq\left(\frac{4}{1-\alpha}\right)^{1/(1-\alpha)}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha}$

then we have the lower bound

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\geq\frac{1}{2\cdot
512}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\max\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}.$

It therefore suffices to take

$\displaystyle
L_{\alpha,\lambda_{\star},k,\lambda_{\min}}=\max\left\\{M,\left(\frac{4}{1-\alpha}\right)^{1/(1-\alpha)}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha}\right\\}$

to have matching upper and lower bounds up to constant factors with

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\simeq\frac{1}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}.$

From $\sigma_{\min}\leq\sigma/\sqrt{2}$ we have that
$\lambda_{\min}=d\sigma_{\min}^{2}/n\leq
d\sigma^{2}/(2n)=\lambda_{\star}/2\leq 1/2$ and therefore
$1\geq(1-\lambda_{\min})^{2}\geq 1/4$. Meanwhile, since
$\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$ for an integer $k-2\geq
j\geq 0$ and $\varepsilon\in(0,1)$, we have
$\text{Dist}(\lambda_{\star},\Gamma)=\delta\min\\{\varepsilon,1-\varepsilon\\}$
and as such
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)=\text{Dist}(\lambda_{\star},\Gamma)/\delta=\min\\{\varepsilon,1-\varepsilon\\}$.
This then gives us
$\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\simeq\text{Dist}_{\delta}(\lambda_{\star},\Gamma)^{-2}\lambda_{\star}^{4}/\lambda_{\min}^{2}$
as required.

Fast Power Law or Exponential Decay: We now consider the case when the
eigenvalues decay more quickly, beginning with the case of eigenvalues that
decay exponentially, so $s_{i}=\exp(-\rho(i-1))$ for some $\rho>0$ for
$i=1,\dots,r$. The condition on $k$ from (13) in Theorem 4 is satisfied by
assumption, whereas the upper bound on $\lambda_{\star}$ from (13) is on the
order of a constant. The condition $r\geq 1+\rho^{-1}\log(1/\lambda_{\star})$
in Theorem 4 holds due to the assumption $s_{r}\leq\lambda_{\star}$. Given
this we have from Theorem 4 the lower bound

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\geq\frac{C_{\rho}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2}$
(27)

for some constant $C_{\rho}>0$ depending exponentially $\rho$, i.e.,
$C_{\rho}=\Theta(\exp(-\rho))$, and independent of $n,p,k,\sigma$. Following
the previous case, going from $\min\\{1-\varepsilon,\varepsilon\\}$ to
$\text{Dist}_{\delta}(\lambda_{\star},\Gamma)$, we arrive at the lower bound
$\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\gtrsim\text{Dist}_{\delta}(\lambda_{\star},\Gamma)^{-2}(k\lambda_{\star})^{2}$
as $k$ grows, provided $\rho\lesssim\log(k)$.

Let us now consider eigenvalues that decay at a faster power law rate so
$s_{i}=i^{-\alpha}$ for $\alpha>1$ and $i=1,\dots,r$. From Theorem 5 we see
once again that the condition (14) on $k$ is implied by the assumption of the
theorem, and the upper bound (15) on $\lambda_{\star}$ is on the order of a
constant. Similarly, $r\geq\lambda_{\star}^{-1/\alpha}$ holds due to
$s_{r}\leq\lambda_{\star}$. Given this, the lower bound matches (27) for a
(different) constant $C_{\alpha}>0$ depending expoentially on $\alpha$ so
$C_{\alpha}=\Theta(\exp(-\alpha))$, and thus, we have the desired lower bound
provided $\alpha\lesssim\log(k)$.

###  B.3 Proofs for Relative Sub-optimality with Slow Power Law Decaying
Eigenvalues

In this section we present proofs for the results associated to bounding the
relative sub-optimality of gradient descent and ridge regression when the
eigenvalues decay at a slow power law rate. Section B.3.1 presents the proof
of Theorem 2 which gives an upper bound, meanwhile Section B.3.2 presents the
proof of Theorem 3 which gives the lower bound.

####  B.3.1 Proof of Theorem 2

Plugging the expression for $\delta$ in Proposition 1 from Section 2.4, with
$\delta=(1-\lambda_{\min})/(k-1)$ (where the condition
$\lambda_{\star}\geq\delta$ holds because
$\lambda_{\star}\geq\lambda_{\min}\geq(1-\lambda_{\min})/(k-1)=\delta$, as
$\lambda_{\min}>1/k$) immediately yields the lower bound for ridge regression

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\geq\frac{1}{2^{5}}\min\\{1-\varepsilon,\varepsilon\\}^{2}\lambda_{\star}\int
G^{\text{Ridge}}(s)d\widehat{H}(s),$

where

$\displaystyle\int G^{\text{Ridge}}(s)d\widehat{H}(s)$
$\displaystyle=\frac{(1-\lambda_{\min})^{2}}{(k-1)^{2}}\frac{1}{d}\left(\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{\lambda_{\star}s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}\frac{s_{i}}{\lambda_{\star}^{4}}\right)$
$\displaystyle\geq\frac{(1-\lambda_{\min})^{2}}{k^{2}}\frac{1}{d}\frac{1}{\lambda_{\star}^{4}}\left(\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\right).$
(28)

We now turn to gradient descent. Since $\eta=\frac{1}{k\lambda_{\min}}$, using
Proposition 2 with $t=k$, where the condition $t\geq\lceil
1/(\eta\lambda_{\star})\rceil$ holds because
$t=k=1/(\eta\lambda_{\min})\geq\lceil 1/(\eta\lambda_{\star})\rceil$, we find

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,t))\leq
18\lambda_{\star}\int G^{\text{GD}}(s)d\widehat{H}(s),$

where

$\displaystyle\int G^{\text{GD}}(s)d\widehat{H}(s)$
$\displaystyle=\frac{1}{d}\left(\sum_{i:s_{i}>\lambda_{\star}}\frac{\lambda_{\star}}{s_{i}^{2}}+\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}\frac{s_{i}^{3}}{\lambda_{\star}^{4}}+\frac{1}{k^{2}\lambda_{\min}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}^{2}/(k\lambda_{\min})}s_{i}\right)$
(29)
$\displaystyle=\frac{1}{d}\frac{1}{\lambda_{\star}^{4}}\left(\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}+\frac{\lambda_{\star}^{4}}{k^{2}\lambda_{\min}^{2}}\sum_{i:s_{i}\leq\lambda_{\star}^{2}/(k\lambda_{\min})}s_{i}\right).$

Dividing this by the bound in (28) gives, using
$\lambda_{\star}^{2}/(k\lambda_{\min})\leq\lambda_{\star}$

$\displaystyle\frac{\int G^{\text{GD}}(s)d\widehat{H}(s)}{\int
G^{\text{Ridge}}(s)d\widehat{H}(s)}$
$\displaystyle\leq\frac{1}{(1-\lambda_{\min})^{2}}\left[k^{2}\frac{\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}}{\left(\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\right)}\right.$
$\displaystyle\quad\quad\quad\quad\quad\quad\left.+k^{2}\frac{\sum_{i:\lambda_{\star}^{2}/(k\lambda_{\min})<s_{i}\leq\lambda_{\star}}s_{i}^{3}}{\left(\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\right)}+\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}\frac{\sum_{i:s_{i}\leq\lambda_{\star}^{2}/(k\lambda_{\min})}s_{i}}{\left(\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}+\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\right)}\right]$
$\displaystyle\leq\frac{1}{(1-\lambda_{\min})^{2}}\left[k^{2}\frac{\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}}{\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}}+k^{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}^{4}}{\lambda_{\min}^{2}}\right].$

Since $s_{i}=i^{-\alpha}$ for $i=1,\dots,r$, we have the following bounds:

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

where $\mathcal{J}_{\alpha,\lambda_{\star}}$ is defined in (10). Plugging in
we then find

$\displaystyle\frac{\int G^{\text{GD}}(s)d\widehat{H}(s)}{\int
G^{\text{Ridge}}(s)d\widehat{H}(s)}\leq\frac{2}{(1-\lambda_{\min})^{2}}\left[\frac{k^{2}}{r^{1-\alpha}}\left(\frac{1}{\lambda_{\star}^{1/\alpha-1}}+\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\right)+\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}\right]$

as required.

We now show the bounds (30), (31), (32). For (30) we have

$\displaystyle\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}=\sum_{i<\lambda_{\star}^{-1/\alpha}}i^{2\alpha}\leq\sum_{i=1}^{\lambda_{\star}^{-1/\alpha}}i^{2\alpha}\leq\lambda_{\star}^{-1/\alpha}\lambda_{\star}^{-2}=\lambda_{\star}^{-(2+1/\alpha)}.$

For (31) we have from $i^{-\alpha}\geq\int_{i}^{i+1}x^{-\alpha}dx$ that

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

for the last inequality we used the assumption that $r\geq
2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha})$.

Finally for (32) we have with $a=\lambda_{\star}^{2}/(k\lambda_{\min})$,
$b=\lambda_{\star}$ as well as with
$i^{-3\alpha}\leq\int_{i-1}^{i}x^{-3\alpha}dx$ that

$\displaystyle\sum_{i:a<s_{i}\leq b}s_{i}^{3}$ $\displaystyle=\sum_{i=\lceil
b^{-1/\alpha}\rceil}^{\lceil a^{-1/\alpha}\rceil-1}i^{-3\alpha}=\lceil
b^{-1/\alpha}\rceil^{-3\alpha}+\sum_{i=\lceil b^{-1/\alpha}\rceil+1}^{\lceil
a^{-1/\alpha}\rceil-1}i^{-3\alpha}$ $\displaystyle\leq\lceil
b^{-1/\alpha}\rceil^{-3\alpha}+\int_{\lceil b^{-1/\alpha}\rceil}^{\lceil
a^{-1/\alpha}\rceil-1}x^{-3\alpha}dx\leq\lceil
b^{-1/\alpha}\rceil^{-3\alpha}+\int_{b^{-1/\alpha}}^{a^{-1/\alpha}}x^{-3\alpha}dx$
$\displaystyle\leq
1+\begin{cases}3\log(k\lambda_{\min}/\lambda_{\star})&\text{ if }\alpha=1/3\\\
\frac{\lambda_{\star}^{3-1/\alpha}}{1-3\alpha}\left[\left(\frac{\lambda_{\star}}{k\lambda_{\min}}\right)^{3-1/\alpha}-1\right]&\text{
if }\alpha\not=1/3\end{cases}$
$\displaystyle\leq\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min}),$

where we used that
$\lceil\lambda_{\star}^{-1/\alpha}\rceil^{-3\alpha}\leq\lambda_{\star}^{3}\leq
1$. This yields the desired inequality.

####  B.3.2 Proof of Theorem 3

Following the steps in Theorem 2 but applying the upper bound for ridge
regression from Proposition 1 with $\delta=(1-\lambda_{\min})/(k-1)$ gives

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\leq
4\min\left\\{1-\varepsilon,\varepsilon\right\\}^{2}\lambda_{\star}\int
G^{\text{Ridge}}(s)d\widehat{H}(s).$ (33)

Moreover (30), (31) and the condition $r\geq
2^{1/(1-\alpha)}(1+\lambda_{\star}^{-1/\alpha})$ yield

$\displaystyle\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}\geq\frac{r^{1-\alpha}}{2}\geq\lambda_{\star}^{1-1/\alpha}=\lambda_{\star}^{3}\lambda_{\star}^{-(2+1/\alpha)}\geq\lambda_{\star}^{3}\sum_{i:s_{i}>\lambda_{\star}}\frac{1}{s_{i}^{2}}.$
(34)

Therefore

$\displaystyle\int
G^{\text{Ridge}}(s)d\widehat{H}(s)\leq\frac{(1-\lambda_{\min})^{2}}{(k-1)^{2}}\frac{1}{d}\frac{1}{\lambda_{\star}^{4}}2\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}.$

For gradient descent, Proposition 2 yields the lower bound

$\displaystyle\mathcal{E}(\mathcal{C}^{\text{GD}}(\eta,k))$
$\displaystyle\geq\frac{1}{16}\min\\{1-\kappa,\kappa\\}^{2}\lambda_{\star}\int_{0}^{\eta\lambda_{\star}^{2}\kappa/4}G^{\text{GD}}(s)d\widehat{H}(s).$
(35)

Plugging in that $\eta=\frac{1}{k\lambda_{\min}}$ as well as that
$G^{\text{GD}}(s)=\eta^{2}s$ for $s\leq\eta\lambda_{\star}^{2}$ by definition
(18) gives

$\displaystyle\int_{0}^{\eta\lambda_{\star}^{2}\kappa/4}G^{\text{GD}}(s)d\widehat{H}(s)=\frac{1}{d}\sum_{i:s_{i}\leq\eta\lambda_{\star}^{2}\kappa/4}\eta^{2}s_{i}=\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}.$
(36)

Taking the ratio with the ridge regression bound and plugging in the above
bounds yields

$\displaystyle\mathcal{S}(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k))\geq\frac{1}{64}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\frac{\int_{0}^{\eta\lambda_{\star}^{2}\kappa/4}G^{\text{GD}}(s)d\widehat{H}(s)}{\int
G^{\text{Ridge}}(s)d\widehat{H}(s)}$
$\displaystyle\geq\frac{1}{128}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(1-\frac{1}{k}\right)^{2}\frac{1}{(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\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{1}{512}\frac{\min\\{1-\kappa,\kappa\\}^{2}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\frac{1}{(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\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}}.$

We bound

$\displaystyle\sum_{i:s_{i}\leq\frac{\lambda_{\star}^{2}\kappa}{4k\lambda_{\min}}}s_{i}$
$\displaystyle=\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}-\sum_{i:\lambda_{\star}\geq
s_{i}>\frac{\lambda_{\star}^{2}\kappa}{4k\lambda_{\min}}}s_{i}\geq\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}-\sum_{i:s_{i}>\frac{\lambda_{\star}^{2}\kappa}{4k\lambda_{\min}}}s_{i}$
$\displaystyle\geq\sum_{i:s_{i}\leq\lambda_{\star}}s_{i}-\frac{1}{1-\alpha}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha-1},$

where we have used that $\sum_{i:s_{i}>b}s_{i}=\sum_{i=1}^{\lceil
b^{-1/\alpha}\rceil-1}i^{-\alpha}\leq
1+\int_{1}^{b^{-1/\alpha}}x^{-\alpha}dx\leq\frac{1}{1-\alpha}b^{1-1/\alpha}$.

Therefore, using (31) we find

$\displaystyle\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}}\geq
1-\frac{2}{1-\alpha}\left(\frac{4k\lambda_{\min}}{\lambda_{\star}^{2}\kappa}\right)^{1/\alpha-1}\frac{1}{r^{1-\alpha}}.$
(37)

This then leads to the required lower bound.

###  B.4 Limits of the Relative Sub-optimality

In this section we present and prove Corollary 2 and 3 which are summarized
within the main contributions. We begin by presenting both corollaries, with
their proofs given after. We begin with Corollary 2, for eigenvalues with a
slow power law decay.

###### Corollary 2

Consider the setting of Theorem 2. Let $r=\min(d,n)$ and
$d,n\rightarrow\infty$ so that $\gamma=d/n$ is fixed, and
$\lambda_{\min,k}=\lambda_{\star,k}/2$. There is a constant
$C_{\lambda_{\star,k}}$ depending on the discretization we have

$\displaystyle\limsup_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\big{(}\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\big{)}\lesssim
C_{\lambda_{\star,k}}\lambda_{\star,k}^{2}.$

When there is $\delta\in(0,1]$ and $\epsilon\in(0,1)$ such that for all $k$,
there is $j_{k}\in\\{0,1\dots,\lfloor(k-1)^{1-\delta}\rfloor\\}$ such that
$\lambda_{\star,k}=2(\varepsilon+j_{k})/(k-1+\varepsilon+j_{k})$, then
$\lim_{k\rightarrow\infty}C_{\lambda_{\star,k}}\lambda_{\star,k}^{2}=0$.

We now present Corollary 3, for eigenvalues that decay quickly, i.e.,
exponentially, or with a fast power law decay.

###### Corollary 3

Consider the setting of Theorem 4 (exponentially decaying eigenvalues) or
Theorem 5 (eigenvalues with a fast power law decay). Let $r=\min(d,n)$ and
$d,n\rightarrow\infty$ so that $\gamma:=d/n$ is fixed, and
$\lambda_{\min,k}=\lambda_{\star,k}/2$. There is a constant
$C_{\lambda_{\star,k}}$ depending on the discretization, such that we have

$\displaystyle\liminf_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\big{(}\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\big{)}\gtrsim
C_{\lambda_{\star,k}}\lambda_{\star,k}^{2}k^{2}.$

When there is $\delta^{\prime}\in(0,1/2)$,
$\delta^{\prime\prime}\in(0,1/2-\delta^{\prime})$ and $\epsilon\in(0,1)$ such
that for all $k$, there is
$j_{k}\in\\{\lceil(k-1)^{1/2+\delta^{\prime}}\rceil\dots,\lfloor(k-1)^{1-\delta^{\prime\prime}}\rfloor\\}$
such that $\lambda_{\star,k}=2(\varepsilon+j_{k})/(k-1+\varepsilon+j_{k})$,
then
$\lim_{k\rightarrow\infty}C_{\lambda_{\star,k}}\lambda_{\star,k}^{2}k^{2}=\infty$.

####  B.4.1 Proof of Corollary 2

In the case $r=\min(d,n)$ and $d,n\rightarrow\infty$, we immediately have
$r\rightarrow\infty$. The upper bound from Theorem 2 then simplifies to

$\displaystyle\limsup_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\frac{1152}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}},$

where we recall that $\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$,
with $\epsilon\in(0,1)$, $j\in\\{0,1\dots,k-2\\}$ and
$\delta=(1-\lambda_{\min})/(k-1)$. For $\epsilon\in(0,1)$ and $k\geq 2$,
consider the sequence for
$\lambda_{\star,k}=\lambda_{\min}+(j_{k}+\varepsilon)(1-\lambda_{\min})/(k-1)$
where $j_{k}\in\\{0,1,2,\dots,\lceil(k-1)^{1-\delta}\rceil\\}$ with
$\delta\in(0,1]$. When $\lambda_{\min,k}=\lambda_{\star,k}/2$, we have

$\displaystyle\lambda_{\star,k}$
$\displaystyle=\lambda_{\min}+(\varepsilon+j_{k})\frac{(1-\lambda_{\min})}{k-1}=\frac{\lambda_{\star,k}}{2}\Big{(}1-\frac{\varepsilon+j_{k}}{k-1}\Big{)}+\frac{\varepsilon+j_{k}}{(k-1)}$

and thus

$\displaystyle\lambda_{\star,k}=2\frac{\frac{\varepsilon+j_{k}}{k-1}}{1+\frac{\varepsilon+j_{k}}{k-1}}=2\frac{\varepsilon+j_{k}}{k-1+\varepsilon+j_{k}}.$

Plugging in this sequence we find since $1-\lambda_{\min}\geq 1/2$

$\displaystyle\limsup_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\leq\frac{73728}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\Big{(}\frac{\varepsilon+j_{k}}{k-1+\varepsilon+j_{k}}\Big{)}^{2}.$

Taking the limit as $k\rightarrow\infty$ we then see that
$j_{k}/(k-1)\leq(k-1)^{1-\delta}/(k-1)=(k-1)^{-\delta}\rightarrow 0$ as
required.

####  B.4.2 Proof of Corollary 3

Let us begin by considering Theorem 4, for eigenvalues that decay
exponentially. With $r=\min(d,n)$ and $n,d\rightarrow\infty$ we have

$\displaystyle\liminf_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\big{(}\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\big{)}\geq\frac{C_{\rho}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\left(\frac{\lambda_{\star}k}{1-\lambda_{\min}}\right)^{2},$
(38)

where we recall that $\lambda_{\star}=\lambda_{\min}+(j+\varepsilon)\delta$
with $\epsilon\in(0,1)$, $j\in\\{0,1\dots,k-2\\}$ and
$\delta=(1-\lambda_{\min})/(k-1)$. Recalling that
$\lambda_{\min}=\lambda_{\star}/2$, for condition (13) in Theorem 4 to be
satisfied it is sufficient that

$\displaystyle\lambda_{\star}\leq
C_{\rho}^{\prime}\quad\quad\text{and}\quad\quad
k\geq\frac{C^{\prime\prime}_{\rho}}{\lambda_{\star}^{2}},$ (39)

for some constants $C_{\rho}^{\prime},C_{\rho}^{\prime\prime}>0$.

Following the proof of Corollary 2, let us now consider the sequence
$\lambda_{\star,k}=\lambda_{\min}+(j_{k}+\varepsilon)\delta=2(\varepsilon+j_{k})/(k-1+\varepsilon+j_{k})$
for some $\epsilon\in(0,1)$ and
$j_{k}\in\\{\lceil(k-1)^{1/2+\delta^{\prime}}\rceil\dots,\lfloor(k-1)^{1-\delta^{\prime\prime}}\rfloor\\}$
with $\delta^{\prime}\in(0,1/2)$ and
$\delta^{\prime\prime}\in(0,1/2-\delta^{\prime})$. We need to show that the
conditions in (39) hold for this sequence once $k$ is sufficiently large, that
is,

$\displaystyle\lambda_{\star,k}=\frac{\varepsilon+j_{k}}{\varepsilon+k+j_{k}}\leq
C_{\rho}^{\prime}\quad\quad\text{and}\quad\quad
k\geq\frac{C_{\rho}^{\prime\prime}}{\lambda_{\star,k}^{2}}=\frac{C^{\prime\prime}_{\rho}}{4}\Big{(}\frac{k-1}{\varepsilon+j_{k}}+1\Big{)}^{2}.$

From $j_{k}\leq(k-1)^{1-\delta^{\prime\prime}}$ we see that
$\lambda_{\star,k}=(\varepsilon+j_{k})/(\varepsilon+j_{k}+k-1)\leq(\varepsilon+(k-1)^{1-\delta^{\prime\prime}})/(k-1)\leq
2(k-1)^{-\delta^{\prime\prime}}$, and thus the first condition is satisfied
for $k\geq 1+(2/C_{\rho}^{\prime})^{1/\delta^{\prime\prime}}$. Since
$j_{k}\geq(k-1)^{1/2+\delta^{\prime}}$ for $\delta^{\prime}\in(0,1/2)$, we
have for sufficiently large $k$ that

$\displaystyle\frac{k-1}{\varepsilon+j_{k}}+1\leq
2(k-1)^{1/2-\delta^{\prime}}.$

Thus, for $k\geq(C_{\rho}^{\prime\prime})^{1/(2\delta^{\prime})}$ we have

$\displaystyle\frac{C^{\prime\prime}_{\rho}}{4}\Big{(}\frac{k-1}{\varepsilon+j_{k}}+1\Big{)}^{2}\leq
C_{\rho}^{\prime\prime}(k-1)^{1-2\delta^{\prime}}\leq
C_{\rho}^{\prime\prime}k^{1-2\delta^{\prime}}\leq k$

as required for the second condition.

Using that $1-\lambda_{\min}\geq 1/2$ and taking the limit as $k\to\infty$ we
find

$\displaystyle\liminf_{k\rightarrow\infty}\lim_{\begin{subarray}{c}d,n\rightarrow\infty\\\
d/n=\gamma\end{subarray}}\mathcal{S}\big{(}\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\big{)}\geq
4\frac{C_{\rho}}{\min\\{1-\varepsilon,\varepsilon\\}^{2}}\lim_{k\rightarrow\infty}\big{(}\lambda_{\star,k},k\big{)}^{2}=\infty,$

where in the last step we used that, since $k-1\geq
j_{k}\geq(k-1)^{1/2+\delta^{\prime}}$ and $\varepsilon\in(0,1)$, we have

$\displaystyle\lambda_{\star,k}k=2k\frac{\varepsilon+j_{k}}{k-1+\varepsilon+j_{k}}\geq
k\frac{j_{k}}{k+j_{k}}\geq
k\frac{(k-1)^{1/2+\delta^{\prime}}}{k+k-1}\geq\frac{1}{2}(k-1)^{1/2+\delta^{\prime}}.$

We now consider Theorem 5, for eigenvalues with a fast power law decay. The
proof now follows the same set of steps as above, but with
$C_{\rho},C_{\rho}^{\prime},C_{\rho}^{\prime\prime}$ swapped for certain
$C_{\alpha},C_{\alpha}^{\prime},C_{\alpha}^{\prime\prime}$. Specifically, in
the limit as $d,n\rightarrow\infty$ with $d/n=\gamma$ we arrive at the same
limit (38) but with the constant $C_{\rho}$ swapped for $C_{\alpha}$.
Similarly, conditions (14) and (15) in Theorem 5 are satisfied when (39) holds
with appropriate constants $C_{\alpha}^{\prime},C_{\alpha}^{\prime\prime}>0$.

###  B.5 Proof of Corollary 1

Since $r=d=n^{q}$ for $q\in(0,1)$, $\lambda_{\star}=\sigma^{2}/n^{1-q}$.
Moreover, as $q>1/(1+\alpha)$, the condition $n^{q}=r\geq
2^{1/(1-\alpha}(1+\lambda_{\star}^{-1/\alpha})=2^{1/(1-\alpha)}(1+\sigma^{-2/\alpha}n^{(1-q)/\alpha})$
in Theorem 2 is then satisfied since
$n\geq\max\\{4^{1/(q(1-\alpha)},(4^{1/(1-\alpha)}\sigma^{-2/\alpha})^{\alpha/(q(1+\alpha)-1)}\\}$.
Applying Theorem 2 with $\alpha>1/3$ and upper bounding

$\displaystyle\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})=1+\frac{\lambda_{\star}^{3-1/\alpha}}{3\alpha-1}\leq
1+\frac{1}{3\alpha-1}=\frac{3\alpha}{3\alpha-1}\leq\frac{3}{3\alpha-1}$

yields, using $1/\lambda_{\star}^{1/\alpha-1}\geq 1$,

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq\max\left\\{1,\frac{3}{3\alpha-1}\right\\}$
$\displaystyle\quad\quad\quad\times\frac{2304}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\left[\frac{1}{r^{1-\alpha}}\frac{k^{2}}{\lambda_{\star}^{1/\alpha-1}}+\frac{\lambda_{\star}^{4}}{\lambda_{\min}^{2}}\right].$

The quantity in the square brackets can be written in terms of
$\sigma,\sigma_{\min},k,n$ as follows

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

In the case $\alpha=1/3$ we alternatively have
$\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\leq
5\log(k\lambda_{\min}/\lambda_{\star})$. Following an identical set of steps
to the above yields the upper bound

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$
$\displaystyle\leq
5\log(k\lambda_{\min}/\lambda_{\star})\frac{2304}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}$
$\displaystyle\quad\quad\cdot\left[\frac{k^{2}}{\sigma^{2(1/\alpha-1)}}\frac{1}{n^{q(1/\alpha-\alpha)-1/\alpha+1}}+\frac{1}{n^{2(1-q)}}\left(\frac{\sigma^{4}}{\sigma^{2}_{\min}}\right)^{2}\right].$

Combining these bounds yields the result for $\alpha\geq 1/3$. Let us now
consider the case $\alpha<1/3$, in which case we have
$\mathcal{J}_{\alpha,\lambda_{\star}}(k,\lambda_{\min})\leq
2\left(\frac{k\lambda_{\min}}{\lambda_{\star}^{2}}\right)^{1/\alpha-3}/(1-3\alpha)$.
Following the same steps as above, by applying Theorem 2, we find

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)\leq\frac{1152}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}$
$\displaystyle\quad\quad\cdot\left[\frac{k^{2}}{\sigma^{2(1/\alpha-1)}}\frac{1}{n^{q(1/\alpha-\alpha)-1/\alpha+1}}+\frac{2}{1-3\alpha}\frac{k^{2}(k\sigma_{\min}^{2}/\sigma^{4})^{1/\alpha-3}}{n^{q(1-\alpha)-(1-q)(1/\alpha-3)}}+\frac{1}{n^{2(1-q)}}\left(\frac{\sigma^{4}}{\sigma^{2}_{\min}}\right)^{2}\right]$
$\displaystyle=\frac{1152}{\min\\{1-\varepsilon,\varepsilon\\}^{2}(1-\lambda_{\min})^{2}}\Bigg{[}\frac{k^{2}}{n^{q(1/\alpha-\alpha)-1/\alpha+1}}\left(\frac{1}{\sigma^{2(1/\alpha-1)}}+\frac{2}{1-3\alpha}\frac{(k\sigma_{\min}^{2}/\sigma^{4})^{1/\alpha-3}}{n^{2(1-q)}}\right)$
$\displaystyle\qquad+\frac{1}{n^{2(1-q)}}\left(\frac{\sigma^{4}}{\sigma^{2}_{\min}}\right)^{2}\Bigg{]}.$

Following the proof of Theorem 1, we can use that
$\sigma_{\min}\leq\sigma/\sqrt{2}$ to say $1\geq(1-\lambda_{\min})^{2}\geq
1/4$ as well as rewrite
$\min\\{1-\varepsilon,\varepsilon\\}=\text{Dist}_{\delta}(\lambda_{\star},\Gamma)$.
Combining the two upper bounds thereafter leads to (11).

For the lower bound, from Theorem 3 with $r=n^{q}$ and
$\lambda_{\star}=\sigma^{2}/n^{1-q}$ we find

$\displaystyle\mathcal{S}\left(\mathcal{C}^{\text{GD}}(\eta,k),\mathcal{C}^{\text{Ridge}}(\lambda_{\min},k)\right)$