Optimal Regularization Can Mitigate Double Descent

Introduction

Recent works have demonstrated a ubiquitous “double descent” phenomenon present in a range of machine learning models, including decision trees, random features, linear regression, and deep neural networks Opper (1995, 2001); Advani & Saxe (2017); Spigler et al. (2018); Belkin et al. (2018); Geiger et al. (2019b); Nakkiran et al. (2020); Belkin et al. (2019); Hastie et al. (2019); Bartlett et al. (2019); Muthukumar et al. (2019); Bibas et al. (2019); Mitra (2019); Mei & Montanari (2019); Liang & Rakhlin (2018); Liang et al. (2019); Xu & Hsu (2019); Dereziński et al. (2019); Lampinen & Ganguli (2018); Deng et al. (2019); Nakkiran (2019). The phenomenon is that models exhibit a peak of high test risk when they are just barely able to fit the train set, that is, to interpolate. For example, as we increase the size of models, test risk first decreases, then increases to a peak around when effective model size is close to the training data size, and then decreases again in the overparameterized regime. Also surprising is that Nakkiran et al. (2020) observe a double descent as we increase sample size, i.e. for a fixed model, training the model with more data can hurt test performance.

These striking observations highlight a potential gap in our understanding of generalization and an opportunity for improved methods. Ideally, we seek to use learning algorithms which robustly improve performance as the data or model size grow and do not exhibit such unexpected non-monotonic behaviors. In other words, we aim to improve the test performance in situations which would otherwise exhibit high test risk due to double descent. Here, a natural strategy would be to use a regularizer and tune its strength on a validation set.

This motivates the central question of this work:

When does optimally tuned regularization mitigate or remove the double-descent phenomenon?

Another motivation to start this line of inquiry is the observation that the double descent phenomenon is largely observed for unregularized or under-regularized models in practice. As an example, Figure 1 shows a simple linear ridge regression setting in which the unregularized estimator exhibits double descent, but an optimally-tuned regularizer has monotonic test performance.

We study this question from both a theoretical and empirical perspective. Theoretically, we start with the setting of high-dimensional linear regression. Linear regression is a sensible starting point to study these questions, since it already exhibits many of the qualitative features of double descent in more complex models (e.g. Belkin et al. (2019); Hastie et al. (2019) and further related works in Section 1.1).

This work shows that optimally-tuned ridge regression can achieve both sample-wise monotonicity and model-size-wise monotonicity under certain assumptions. Concretely, we show

Sample-wise monotonicity: In the setting of well-specified linear regression with isotropic features/covariates (Figure 1), we prove that optimally-tuned ridge regression yields monotonic test performance with increasing samples. That is, more data never hurts for optimally-tuned ridge regression (see Theorem 1).

Model-wise monotonicity: We consider a setting where the input/covariate lives in a high-dimensional ambient space with isotropic covariance. Given a fixed model size $d$ (which might be much smaller than ambient dimension), we consider the family of models which first project the input to a random $d$-dimensional subspace, and then compute a linear function in this projected “feature space.” (This is nearly identical to models of double-descent considered in Hastie et al. (2019, Section 5.1)). We prove that in this setting, as we grow the model-size, optimally-tuned ridge regression over the projected features has monotone test performance. That is, with optimal regularization, bigger models are always better or the same. (See Theorem 3).

Problem-specific vs Minimax and Bayesian. It is worth noting that our results hold for all linear ground-truths, rather than holding for only the worst-case ground-truth or a random ground-truth. Indeed, the minimax optimal estimator or the Bayes optimal estimator are both trivially sample-wise and model-wise monotonic with respect to the minimax risk or the Bayes risk. However, they do not guarantee monotonicity of the risk itself for a given fixed problem.

Universal vs Asymptotic. We also remark that our analysis is not only non-asymptotic but also works for all possible input dimensions, model sizes, and sample sizes. Prior works on double descent mostly rely on asymptotic assumptions that send the sample size or the model size to infinity in a specific manner. To our knowledge, the results herein are the first non-asymptotic sample-wise and model-wise monotonicity results for linear regression. (See discussion of related works Hastie et al. (2019); Mei & Montanari (2019) for related results in the asymptotic setting).

Finally, we note that our claims are about monotonicity of the actual test risk, instead of the monotonicity of the generalization bounds (e.g., results in Wei et al. (2019)).

Towards a more general characterization. Our theoretical results crucially rely on the covariance of the data being isotropic. A natural next question is if and when the same results can hold more generally. A full answer to this question is beyond the scope of this paper, though we give the following results:

Optimally-tuned ridge regression is not always sample-monotonic: we show a counterexample for a certain non-Gaussian data distribution and heteroscedastic noise. We are not aware of prior work pointing out this fact. (See Section 4.1 for the counterexample and intuitions.)

For non-isotropic Gaussian covariates, we can achieve sample-wise monotonicity with a regularizer that depends on the population covariance matrix of data. This suggests unlabeled data might also help mitigate double descent in some settings, because the population covariance can be estimated from unlabeled data. (See Section 6).

The last two results above highlight the importance of the form of the regularizer, which leads to the open question: “How do we design good regularizers which mitigate or remove double descent?” We hope that our results can motivate future work on mitigating the double descent phenomenon, and allow us to train high performance models which do not exhibit nonmonotonic behaviors.

1 Related Works

The study of nonmonotonicity in learning algorithms existed prior to double descent and has a long history going back to (at least) Trunk (1979) and LeCun et al. (1991); Le Cun et al. (1991), where the former was largely empirical observations and the latter studied the sample non-nonmonotonicity of unregularized linear regression in terms of the eigenspectrum of the covariance matrix; the difference to our works is that we study this in the context of optimal regularization. In fact, Duin (1995, 2000); Opper (2001); Loog & Duin (2012). Loog et al. (2019) introduces the same notion of risk monotonicity which we consider, and studies several examples of monotonic and non-monotonic procedures.

Double descent of test risk as a function of model size was considered recently in more generality by Belkin et al. (2018). Similar behavior was observed empirically in earlier work in somewhat more restricted settings Trunk (1979); Opper (1995, 2001); Skurichina & Duin (2002); Le Cun et al. (1991); LeCun et al. (1991) and more recently in Advani & Saxe (2017); Geiger et al. (2019a); Spigler et al. (2018); Neal et al. (2018). Recently Nakkiran et al. (2020) demonstrated a generalized double descent phenomenon on modern deep networks, and highlighted “sample non-monotonicity” as an aspect of double descent.

A recent stream of theoretical works consider model-wise double descent in simplified settings— often via linear models for regression or classification. This also connects to works on high-dimentional regression in the statistics literature. A partial list of works in these areas include Belkin et al. (2019); Hastie et al. (2019); Bartlett et al. (2019); Muthukumar et al. (2019); Bibas et al. (2019); Mitra (2019); Mei & Montanari (2019); Liang & Rakhlin (2018); Liang et al. (2019); Xu & Hsu (2019); Dereziński et al. (2019); Lampinen & Ganguli (2018); Deng et al. (2019); Nakkiran (2019); Mahdaviyeh & Naulet (2019); Dobriban et al. (2018); Dobriban & Sheng (2019); Kobak et al. (2018). Of these, most closely related to our work are Hastie et al. (2019); Dobriban et al. (2018); Mei & Montanari (2019). Specifically, Hastie et al. (2019) considers the risk of unregularized and regularized linear regression in an asymptotic regime, where dimension $d$ and number of samples $n$ scale to infinity together, at a constant ratio $d/n$. In contrast, we show non-asymptotic results, and are able to consider increasing the number of samples for a fixed model, without scaling both together. Mei & Montanari (2019) derive similar results for unregularized and regularized random features, also in an asymptotic limit. The non-asymptotic versions of the settings considered in Hastie et al. (2019) are almost identical to ours— for example, our projection model in Section 3 is nearly identical to the model in Hastie et al. (2019, Section 5.1). Finally, subsequent to our work, d’Ascoli et al. (2020) identified triple descent in an asymptotic setting.

Sample Monotonicity in Ridge Ridgression

In this section, we prove that optimally-regularized ridge regression has test risk that is monotonic in samples, for isotropic gaussian covariates and linear response. This confirms the behavior empirically observed in Figure 1. We also show that this monotonicity is not “fragile”, and using larger than larger regularization is still sample-monotonic (consistent with Figure 1).

We consider the regularized least-squares estimator, also known as the ridge regression estimator. For a given $\lambda>0$, define

Here $I_{d}$ denotes the $d$ dimensional identity matrix. Let $\lambda^{\textup{opt}}_{n}$ be the optimal ridge parameter (that achieves the minimum expected risk) given $n$ samples:

Let $\hat{\beta}^{\textup{opt}}_{n}$ be the estimator that corresponds to the $\lambda^{\textup{opt}}_{n}$

Our main theorem in this section shows that the expected risk of $\hat{\beta}^{\textup{opt}}_{n}$ monotonically decreases as $n$ increases.

From Lemma 1, the below lemma follows directly by taking derivatives to find the optimal $\lambda$.

In the setting of Theorem 1, the optimal ridge parameter is constant for all $n$: $\lambda^{\textup{opt}}_{n}=\frac{d\sigma^{2}}{||\beta^{*}||_{2}^{2}}.$ Moreover, the optimal expected test risk can be written as

Lemma 2’s proof is deferred to the Appendix, Section A.1. We now prove Lemma 1.

For isotropic $x$, the test risk is related to the parameter error as:

Plugging in the form of $\hat{\beta}_{n,\lambda}$ and expanding:

In Line (8) follows because by symmetry, the distribution of $V$ is a uniformly random orthonormal matrix, and $\Sigma$ is independent of $V$. Thus, $z:=V^{T}\beta^{*}$ is distributed as a uniformly random point on the unit sphere of radius $||\beta^{*}||_{2}$.

If we couple $\widetilde{X}$ and $X$, it will induce a coupling $\Pi$ between the distributions $\Gamma_{n+1}$ and $\Gamma_{n}$, of the singular values of the data matrix for $n+1$ and $n$ samples. This coupling satisfies that $\widetilde{\gamma}_{i}\geq\gamma_{i}$ with probability 1 for $(\{\widetilde{\gamma}_{i}\},\{\gamma_{i}\})\sim\Pi$.

Now, expand the test risk using Lemma 2, and observe that each term in the sum of Equation (11) below is monotone decreasing with $\gamma_{i}$. Thus:

By similar techniques, we can also prove that overregularization —that is, using ridge parameters $\lambda$ larger than the optimal value— is still monotonic. This proves the behavior empirically observed in Figure 1.

where $\lambda^{*}=\frac{d\sigma^{2}}{||\beta^{*}||_{2}^{2}}$.

Model-wise Monotonicity in Ridge Regression

In this section, we show that for a certain family of linear models, optimal regularization prevents model-wise double descent. That is, for a fixed number of samples, larger models are not worse than smaller models.

We consider the following learning problem. Informally, covariates live in a $p$-dimensional ambient space, and we consider models which first linearly project down to a random $d$-dimensional subspace, then perform ridge regression in that subspace for some $d\leq p$.

We consider the regularized least-squares estimator. For a given $\lambda>0$, define

Let $\lambda^{\textup{opt}}_{d}$ be the optimal ridge parameter (that achieves the minimum expected risk) for a model of size $d$, with $n$ samples:

Let $\hat{\beta}^{\textup{opt}}_{d}$ be the estimator that corresponds to the $\lambda^{\textup{opt}}_{d}$

In the setting above, the expected test risk of the optimally-regularized model is monotonic in the model size $d$.

This proof follows closely the proof of Theorem 1, making crucial use of Lemma 3 below.

Then, the optimal ridge parameter is constant for all $d$:

Moreover, the optimal expected test risk can be written as

This proof follows exactly analogously as the proof of Lemma 2 from Lemma 1, in Section A.1. ∎

Counterexamples to Monotonicity

In this section, we show that optimally-regularized ridge regression is not always monotonic in samples. We give a numeric counterexample in $d=2$ dimensions, with non-gaussian covariates and heteroscedastic noise. This does not contradict our main theorem in Section 2, since this distribution is not jointly Gaussian with isotropic marginals.

Here we give an example of a distribution $(x,y)$ for which the expected error of optimally-regularized ridge regression with $n=2$ samples is worse than with $n=1$ samples.

This counterexample is most intuitive to understand when the ridge parameter $\lambda$ is allowed to depend on the specific sample instance $(X,\vec{y})$ as well as $n$ Recall, our model of optimal ridge regularization from Section 2 only allows $\lambda$ to depend on $n$ (not on $X,\vec{y}$).. We sketch the intuition for this below.

Consider the following distribution on $(x,y)$ in $d=2$ dimensions. This distribution has one “clean” coordinate and one “noisy” coordinate. The distribution is:

For $n=1$ samples, the estimator can decide whether to use small $\lambda$ or large $\lambda$ depending on if the sampled coordinate is the “clean” or “noisy” one. Specifically, for the sample $(x,y)$: If $x=\vec{e}_{1}$, then the optimal ridge parameter is $\lambda=0$. If $x=\vec{e}_{2}$, then the optimal parameter is $\lambda=\infty$.

For $n=2$ samples, with probability $1/2$ the two samples will hit both coordinates. In this case, the estimator must chose a single value of $\lambda$ uniformly for both coordinates. This yields to a suboptimal tradeoff, since the “noisy” coordinate demands large regularization, but this hurts estimation on the “clean” coordinate.

It turns out that a slight modification to the above also serves as a counterexample to monotonicity when the regularization parameter $\lambda$ is chosen only depending on $n$ (and not on the instance $X,y$).

Let $\hat{\beta}^{\textup{opt}}_{n}$ be the optimally-regularized ridge regression solution for $n$ samples $(X,\vec{y})$ from $\mathcal{D}$. Then:

The expected test risk increases as a function of $n$, between $n=1$ and $n=2$. Specifically

For $n=1$ samples, it can be confirmed analytically that the expected risk $\overline{R}(\hat{\beta}^{\textup{opt}}_{n=1})<8.157$. This is achieved with $\lambda=400/2401\approx 0.166597$.

For $n=2$ samples, it can be confirmed numerically (via Mathematica) that the expected risk $\overline{R}(\hat{\beta}^{\textup{opt}}_{n=2})>8.179$. This is achieved with $\lambda=0.642525$. ∎

Experiments

We consider the same ridge regression estimator,

Figure 2 shows one instance of this, for a particular choice of $\Sigma$ and $\beta^{*}$. The covariance $\Sigma$ is diagonal, with $\Sigma_{i,i}=10$ for $i\leq 15$ and $\Sigma_{i,i}=1$ for $i>15$. That is, the covariance has one “large” eigenspace and one “small” eigenspace. The ground-truth $\beta^{*}=0.1\vec{e_{1}}+\vec{e_{30}}$, which lies almost entirely within the “small” eigenspace of $\Sigma$. The noise parameter is $\sigma=0.5$.

We see that unregularized regression ($\lambda=0$) actually undergoes “triple descent”See also the “multiple descent” behavior of kernel interpolants in Liang et al. (2020). in this setting, with the first peak around $n=15$ samples due to the 15-dimensional large eigenspace, and the second peak at $n=d$.

In this setting, optimally-regularized ridge regression is empirically monotonic in samples (Figure 2). Unlike the isotropic setting of Section 2, the optimal ridge parameter $\lambda_{n}$ is no longer a constant, but varies with number of samples $n$.

2 Model-size Monotonicity

We consider the same experimental setup as in Section 5.1, but now fix the number of samples $n$, and vary the number of random features $D$. This corresponds to varying the width of the corresponding 2-layer neural network.

Figure 4 shows the test error of these models on CIFAR-100. Although unregularized and under-reguarized models exhibit double descent, the test error of optimally-regularized models is largely monotonic. Note that the optimal regularization $\lambda$ varies with the model size — no single regularization value is optimal for all models.

Towards Monotonicity with General Covariates

Here we investigate whether monotonicity provably holds in more general models, inspired by the experimental results. As a first step, we consider Gaussian (but not isotropic) covariances and homeostatic noise. That is, we consider ridge regression in the setting of Section 2, but with $x\sim\mathcal{N}(0,\Sigma)$, and $y\sim\langle x,\beta^{*}\rangle+N(0,\sigma^{2})$. In this section, we observe that ridge regression can be made sample-monotonic with a modified regularizer. We also conjecture that ridge regression is sample-monotonic without modifying the regularizer, and we outline a potential proof strategy along with numerical evidence.

The results on isotropic regression in Section 2 imply that ridge regression can be made sample-monotonic even for non-isotropic covariates, if an appropriate regularizer is applied. Specifically, the appropriate regularizer depends on the covariance of the inputs: for $x\sim\mathcal{N}(0,\Sigma)$, the following estimator is sample-monotonic for optimally-tuned $\lambda$:

This follows directly from Theorem 1 by applying a change-of-variable; full details of this equivalence are in Section A.3. Note that if the population covariance $\Sigma$ is not known, it can potentially be estimated from unlabeled data.

2 Towards Proving Monotonicity

We conjecture that optimally-regularized ridge regression is sample-monotonic for non-isotropic covariates, even without modifying the regularizer (as suggested by the experiment in Figure 2). We derive a sufficient condition for monotonicity, which we have numerically verified in a variety of instances.

Specifically, we conjecture the following.

where we define $\hat{\beta}_{n,0}:=\lim_{\lambda\rightarrow 0+}\hat{\beta}_{n,\lambda}=X^{\dagger}y$.

In order to establish Conjecture 1, it is sufficient to prove the following technical conjecture.

The expected test risk for $n$ samples can be expressed as:

Then, we conjecture that the following two conditions hold.

Proving Conjecture 2 presents a number of technical challenges, but we have numerically verified it in a variety of cases. (One can numerically verify the conjecture for a fixed $Q$, $n$ and $d$. Here $Q$ can be assumed to be diagonal w.l.o.g. because $X$ is isotropic. The matrices and scalars in equation (25) can be evaluated by sampling the random matrix $X$. The derivatives w.r.t $\lambda$ can be done by auto-differentiation).

It can also be shown that Conjecture 2 is true when $Q=I$, corresponding to isotropic covariates. We show that Conjecture 2 implies Conjecture 1 in in Section A.3.1 of the Appendix.

Discussion and Conclusion

In this work, we study the double descent phenomenon in the context of optimal regularization. We show that, while unregularized or under-regularized models often have non-monotonic behavior, appropriate regularization can eliminate this effect.

Our work suggests a number of natural open questions. First, it is open to prove (or disprove) that optimal ridge regression is sample-monotonic for non-isotropic Gaussian covariates (Conjecture 1). We conjecture that it is, and outline a potential route to proving this (via Conjecture 2). The non-isotropic setting presents a number of differences from the isotropic one (e.g. the optimal regularizer $\lambda$ depends on number of samples $n$), and thus a proof of this may yield further insight into mechanisms of monotonicity.

Second, more broadly, it is open to prove sample-wise or model-wise monotonicity for more general (non-linear) models with appropriate regularizers. Addressing the monotonicity of non-linear models may require us to design new regularizers which improve the generalization when the model size is close to the sample size. It is possible that data-dependent regularizers (which depend on certain statistics of the labeled or unlabeled data) can be used to induce sample monotonicity, analogous to the approach in Section 6.1 for linear models. Recent work has introduced data-dependent regularizers for deep models with improved generalization upper bounds Wei & Ma (2019a, b), however a precise characterization of the test risk remain elusive.

Finally, it is open to understand why large neural networks in practice are often sample-monotonic in realistic regimes of sample sizes, even without careful choice of regularization.

Acknowledgements

Work supported in part by the Simons Investigator Awards of Boaz Barak and Madhu Sudan, and NSF Awards under grants CCF 1715187, CCF 1565264 and CNS 1618026. Sham Kakade acknowledges funding from the Washington Research Foundation for Innovation in Data-intensive Discovery, and the NSF Awards CCF-1703574, and CCF-1740551.

The numerical experiments were supported in part by Google Cloud research credits, and a gift form Oracle. The work is also partially supported by SDSI and SAIL at Stanford.

References

Appendix A Appendix

In Section A.1 and A.2 we provide the proofs for sample-monotonicity and model-size monotonicity. In Section A.4 we include additional and omitted plots.

First, we determine the optimal ridge parameter. Using Lemma 1, we have

Thus, $\frac{\partial}{\partial\lambda}\overline{R}(\hat{\beta}_{n,\lambda})=0\implies\lambda=\frac{d\sigma^{2}}{||\beta^{*}||_{2}^{2}}$ and we conclude that $\lambda^{\textup{opt}}_{n}=\frac{d\sigma^{2}}{||\beta^{*}||_{2}^{2}}$.

For this optimal parameter, the test risk follows from Lemma 1 as

We follow a similar proof strategy as in Theorem 1: we invoke singular value interlacing ($\widetilde{\gamma}_{i}\geq\gamma_{i}$) for the data matrix when adding a single sample. We then apply Lemma 1 to argue that the test risk varies monotonically with the singular values.

and we compute how each term in the sum varies with $\gamma_{i}$:

By the coupling argument in Theorem 1, this implies that the test risk is monotonic:

where $\Pi$ is the coupling. Line (30) follows from Equation (28), and the fact that the coupling obeys $\widetilde{\gamma}_{i}\geq\gamma_{i}$. ∎

A.2 Projection Model Proofs

We first define the parameter that minimizes the population risk. It follows directly that:

The cross terms in Line (35) vanish because the first-order optimality condition for $\beta^{*}$ implies that $\beta^{*}$ satisfies $P(\theta^{*}-P^{T}\beta^{*})=0$. We now simplify each of the two remaining terms.

since $P^{T}P$ is an orthogonal projection onto a random $d$-dimensional subspace.

Now, recall we have $\vec{y}=X\theta+\eta$ where $\eta\sim\mathcal{N}(0,\sigma^{2}I_{n})$. Expand this as:

where $\varepsilon:=X(1-P^{T}P)\theta$. Note that conditioned on $P$, the three terms $\widetilde{X},\varepsilon$ and $\eta$ are conditionally independent, since $P^{T}P$ and $(I-P^{T}P)$ project $X$ onto orthogonal subspaces. And further, $\varepsilon\sim\mathcal{N}(0,||(1-P^{T}P)\theta||^{2}I_{n})$.

Now, since $\widetilde{X}$ is conditionally independent of $\varepsilon$ conditioned on $P$,

where Line (50) holds because the marginal distribution of $\widetilde{X}$ does not depend on $P$.

Finally, continuing from Line (46), we can use Lines (51), (53), and (60) to write:

Now, we can continue from Line (37), and apply lines (38), to conclude:

This follows analogously to the proof of Theorem 1, Let $\widetilde{X}_{d}$ and $\widetilde{X}_{d+1}$ be the observed data matrices for $d$ and $d+1$ model size. As in Theorem 1, there exists a coupling $\Pi$ between the distributions $\Gamma_{d}$ and $\Gamma_{d+1}$ of the singular values of $\widetilde{X}_{d}$ and $\widetilde{X}_{d+1}$ such that these singular values are interlaced.

A.3 Nonisotropic Reduction

Here we observe that results on isotropic regression in Section 2 also imply that ridge regression can be made sample-monotonic even for non-isotropic covariates, if an appropriate regularzier is applied. Specifically, the regularizer depends on the covariance on the inputs. This follows from a general equivalence between the non-isotropic and isotropic problems.

Regularized regression with covariance $\Sigma$, and an $(\Sigma^{1/2}M\Sigma^{1/2})$-regularizer. That is, suppose $n$ samples $(\widetilde{x},y)$ are drawn with covariates $\widetilde{x}\sim\mathcal{N}(0,\Sigma)$ and response $y=\langle z^{*},\widetilde{x}\rangle+\mathcal{N}(0,\sigma^{2})$, for

Then, the expected test risks of the above two problems are identical:

The distribution of $\widetilde{X}$ in the Problem 2 is equivalent to $X\Sigma^{1/2}$, where $X$ is as in Problem 1. Thus, the two settings are equivalent by the change-of-variable $\beta=\Sigma^{1/2}z$. Specifically,

Further, the response $\langle z^{*},\widetilde{x}\rangle=\langle\beta,x\rangle$, and the test risk transforms identically:

This implies that if the covariance $\Sigma$ is known, then ridge regression with a $\Sigma^{-1}$ regularizer is sample-monotonic.

And let $\hat{\beta}^{\textup{opt}}_{n}$ be the estimator that corresponds to the $\lambda^{\textup{opt}}_{n}$. Then, the expected test risk of optimally-regularized linear regression is monotonic in samples:

This follows directly by applying the reduction in Lemma 5 for $M=I_{d}$ to reduce to the isotropic case, and then applying the monotonicity of isotropic regression from Theorem 1. ∎

By the reduction in Section A.3, showing monotonicity for non-isotropic regression with an isotropic regularizer is equivalent to showing monotonicity for isotropic regression with a non-isotropic regularizer. Thus, we consider the latter. Specifically, Conjecture 1 is equivalent to showing monotonicity for the estimator

where $x\sim\mathcal{N}(0,I)$ is isotropic, and $y\sim\langle x,\beta^{*}\rangle+\mathcal{N}(0,\sigma^{2})$.

Now, letting $Q:=\Sigma^{-1}$, the expected test risk of this estimator for $n$ samples is:

Case (1). Suppose the infimum in Equation 80 is achieved in the limit $\lambda\to+\infty$. In this case, monotonicity trivially holds, since

Case (2). Suppose the infimum in Equation 80 is achieved by some $\lambda=\lambda^{\textup{opt}}_{n}$ in the interior of the set $(0,\infty)$.

Because $\overline{R}(\hat{\beta}_{n,\lambda})$ is continuous and differentiable in $\lambda$ for all $\lambda\in(0,\infty)$, we have that $\lambda^{\textup{opt}}_{n}$ must satisfy the following first-order optimality condition:

We will later use this condition to show monotonicity.

Case (3). Suppose the infimum in Equation 80 is achieved at $\lambda^{\textup{opt}}_{n}=0$. Recall, we define $\hat{\beta}_{n,0}:=\lim_{\lambda\rightarrow 0+}\hat{\beta}_{n,\lambda}$. This means that,

Note that since $\frac{dH_{\lambda}^{n}}{d\lambda}\leq 0$, both Equations (82) and (83) in Case (2) and Case (3) respectively imply that

Now, assuming Conjecture 2, we will show that the choice of $\lambda^{\textup{opt}}_{n}$ in Cases (2) and (3) has non-increasing test risk for $(n+1)$ samples. That is,

This implies the desired monotonicity, since $\overline{R}(\hat{\beta}_{n+1,\lambda^{\textup{opt}}_{n}})\geq\overline{R}(\hat{\beta}_{n+1,\lambda^{\textup{opt}}_{n+1}})$.

We first consider the case when $H_{\lambda}^{n}-H_{\lambda}^{n+1}|_{\lambda=\lambda^{\textup{opt}}_{n}}\geq 0$. In this case, because $G_{\lambda}^{n}-G_{\lambda}^{n+1}\succeq 0$ by assumption, we have

Otherwise, assume. $H_{\lambda}^{n}-H_{\lambda}^{n+1}|_{\lambda=\lambda^{\textup{opt}}_{n}}\leq 0$. Then we have:

A.4 Additional Plots