Generalized equivalences between subsampling and ridge regularization
Authors: Pratik Patil
Jin-Hong Du
Venue: NeurIPS 2023 poster (2023)
Keywords: subsampling
ridge regularization
asymptotic equivalences
proportional asymptotics
TL;DR: We establish an array of precise equivalences between the implicit regularization due to subsampling and explicit ridge regularization with mild data assumptions.

Abstract: We establish precise structural and risk equivalences between subsampling and ridge regularization for ensemble ridge estimators. Specifically, we prove that linear and quadratic functionals of subsample ridge estimators, when fitted with different ridge regularization levels $\lambda$ and subsample aspect ratios $\psi$, are asymptotically equivalent along specific paths in the $(\lambda,\psi)$-plane (where $\psi$ is the ratio of the feature dimension to the subsample size). Our results only require bounded moment assumptions on feature and response distributions and allow for arbitrary joint distributions. Furthermore, we provide a data-dependent method to determine the equivalent paths of $(\lambda,\psi)$. An indirect implication of our equivalences is that optimally tuned ridge regression exhibits a monotonic prediction risk in the data aspect ratio. This resolves a recent open problem raised by Nakkiran et al. for general data distributions under proportional asymptotics, assuming a mild regularity condition that maintains regression hardness through linearized signal-to-noise ratios.

Generalized equivalences between subsampling and ridge regularization
Pratik Patil
Jin-Hong Du
Department of Statistics and Data Science & Machine Learning Department Carnegie Mellon University
Department of Statistics
University of California Berkeley, CA 94720, USA
Pittsburgh, PA 15213, USA
pratikpatti0derrkeeee.cem
jinhongd@andrev. cmu cmu. edu
Abstract
We establish precise structural and risk equivalences between subsampling and ridge regularization for ensemble ridge estimators. Specifically, we prove that linear and quadratic functionals of subsample ridge estimators, when fitted with different ridge regularization levels À and subsample aspect ratios v/, are asymptotically equivalent along specific paths in the (A, - (where vó is the ratio the feature dimension the subsample size). Our results only require bounded moment assumptions on feature and response distributions and allow for arbitrary joint distributions. Furthermore,
provide data-dependent method to determine the equivalent paths of (A, v)). An indirect implication of our equivalences is that optimally tuned ridge regression exhibits monotonic prediction risk in the data aspect ratio. This resolves a recent open problem raised by Nakkiran et al. [ for general data distributions under proportional asymptotics, assuming a mild regularity condition that maintains regression hardness through linearized signal- to-noise ratios.
Introduction
Ensemble methods, such as bagging 2 3. are powerful tools that combine weak predictors to improve predictive stability and accuracy. This paper focuses sampling- basedd ensembles, which exhibit an implicit regularization effect 6 Specifically, we investigate subsample ridge ensembles, where the ridge predictors are fitted on independently subsampled datasets [7. Recent work has demonstrated that full ensemble (that is fitted on all possible subsampled datasets) of ridgeless [10
predictors achieves the same squared prediction risk ridge predictor fitted on full data 11
To be precise, let & be the limiting dataset aspect ratio p/n, where p is the feature dimension, and is the number of observations. For a given o, the limiting prediction risk of subsample ridge ensembles is parameterized by (A, v). where À 2 0 is the ridge regularization parameter and v 2 ó is the limiting subsample aspect ratio p/k; with is being the subsample size [2] Under isotropic features and a well-specified linear model, [1] show that the squared prediction risk at (0, 1²) (the optimal ridgeless ensemble) is the same as the risk (X*,)) (the optimal ridge), where e)* and X" are the optimal subsample aspect ratio and ridge penalty, respectively. Furthermore, this equivalence of prediction risk between subsampling and ridge regularization is extended in [13 to anisotropic linear models. As an application, for ridge regression be naturally transferred subsample ridge ensembles. In essence, these results suggest that subsampling smaller number of observations has the same effect adding an appropriately larger level of ridge penalty. These findings prompt two important open questions:
[ also demonstrates how generalized cross-validation
(a) The extent of equivalences. The previous works all focus on equivalences of the squared prediction risk when the test distribution matches the train distribution. In real-world scenarios,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison with related work. The marker "v"" indicates partial equivalence result
connecting the optimal prediction risk of the ridge predictor and the full ridgeless ensemble predictor.
Type of equivalence results
Type of data assumptions
pred. risk gen. risk
estimator response
feature
lim. spectrum
isotropic
LeJeune et al.
linear
Gaussian
exists
isotropic
Patil et al.
linear
exists
RMT
anisotropic
Du et al.
linear
exists
RMT
anisotropic
This work
arbitrary
need not exist RMT
however, there are often covariate and label shifts, making it crucial to consider prediction risks under such shifts. In addition. other risk measures, such as training error, estimation risk, coefficient errors, and more, are also of interest in various inferential tasks. A natural question is then whether similar equivalences hold for such "generalized" risk measures. At a basic level, the question boils down to whether any equivalences exist at the "estimator level". Answering this question would establish a connection between the ensemble and the ridge estimators, facilitating the exchange of various downstream inferential statements between the two sets of estimators.
(b) The role of linear model. All previous works assume well-specified linear model between the responses and the features, which rarely holds in practical applications. A natural question is whether the equivalences hold for arbitrary joint distributions of the response and the features or whether they are merely an artifact of the linear model. Addressing this question broadens the applicability of such equivalences beyond simplistic models to real-world scenarios, where the relationship between the response and the features typically intricate and unknown.
We provide answers to questions raised in both directions. We demonstrate that the equivalences hold for the generalized squared risks in the full ensemble. Further, these equivalences fundamentally occur the estimator level for any arbitrary ensemble size. Importantly, these results are not limited to linear models of the gatt-geenratiig process. Below we provide summary of our main results.
1.1 Summary contributions
(1) Risk equivalences. We establish asymptotic equivalences of the full-ensemble ridge estimators at different ridge penalties and subsample ratios & along specific paths the (A, )-planee for variety of generalized risk functionals. This class of functionals includes commonly used risk measures (see Table 2) and our results hold for both independent and dependent coefficient matrices that define these risk functionals (see Theorem and Proposition 2). In addition, demonstrate that the equivalence path remains unchanged across all the functionals examined.
(2) Structural equivalences. We establish structural equivalences the form of linear functionals of the ensemble ridge estimators, which hold for arbitrary ensemble sizes (see Theorem 3.. Our proofs for both structural and risk equivalences exploit properties of certain fixed equations that arise in analysis, enabling to explicitly characterize paths that yield equivalent estimators in the (A, -pl-aaee (see Equation (5). In addition, we provide an entirely data-driven construction of this path using certain companion Stieltjes transform relations of random matrices (see Proposition 4
(3) Equivalence implications. As an implication of our equivalences, we show that the prediction risk an optimally-tuned ridge estimator is monotonically increasing in the data aspect ratio under mild regularity conditions (see Theorem 6). This is an indirect consequence of our general equivalence results that leverages the provable monotonicity of the subsample-optimizze Under proportional asymptotics, our result settles recent open question raised by Nakkiran et al. [I] Conjecture 1] concerning the monotonicity of optimal ridge regression under anisotropic features and general data models while maintaining regularity condition that preserves the lincarized signal-to-note noise ratios across regression problems.
estimator.
(4) Generality of equivalences. Our main results apply to arbitrary responses with bounded Jr moments for some μ 0, as well as features with similar bounded moments and general

---

covariance structures, We demonstrate the practical implications of our findings on real- datasets (see Section ( On the technical side, we extend the tools developed in [1] to handle the dependency between the linear and the non-linear components and obtain model-free equivalences. Furthermore, we extend our analysis to include generalized ridge regression (see Corollary [5). Through experiments, we demonstrate the universality of the equívalences for random and kernel features and conjecture the associated data-driven prediction risk equivalence paths (see Section 6).
1.2 Related work
Ensemble learning. Ensemble methods yield strong predictors by combining weak predictors [5]
The most common strategy for building ensembles is based on subsampling observations, which
includes bagging 23. random forests [16), neural network ensembles 17/19). among the others.
The effect of sampling-basel ensembles has been studied in the statistical physics literature [20 22]
as well as statistical learning literature (2)3). Recent works have attempted to explain the success of ensemble learning by suggesting that subsampling induces a regularizing effect 4 6 Under proportional asymptotics, the effect of ensemble random feature models has been investigated in 25] There has been growing interest in connecting the effect of ensemble learning to explicit regularization: see (26) for related experimental evidence under the umbrella of "mini-patch" learning. Towards making these connections precise, some work has been done in the context of the ridge and ridgeless ensembles: [1 investigate the relationship between subsampling and regularization for ridge ensembles in the overparameterized regime. We will delve into these works in detail next.
Ensembles and ridge equivalences. In the study of ridge ensembles, LeJeune et al. (11) show that the optimal ridge predictor has the same prediction risk the ridgeless ensemble under the Gaussian isotropic design, which has been extended in [12] for RMT features (see Assumption for definition). Specifically, these works establish the prediction risk equivalences for a specific pair of (X*, .) and (0, )²*) The results are then extended to the entire range of (A, e)) using deterministic asymptotic risk formulas [13, assuming a well-specified linear model, RMT features, and the existence of a fixed limiting spectral distribution of the covariance matrix. Our work significantly broadens the scope of results connecting subsampling and ridge regularization. joint distributions of the data, anisotropic features with only bounded moments, and do not assume the convergence of the spectrum of the population covariance matrix. Furthermore, we expand the applicability of equivalences to encompass both the estimators and various generalized squared risk functionals. See Table I for an explicit comparison and Section S for additional related comparisons.
particular, we allow for arbitrary
Other ridge connections. Beyond the connection connections between implicit regularization induced by subsampling and explicit ridge regularization examined in this paper, ridge regression shares ties with various other forms of regularization. For example, ridge regression has been linked to dropout regularization 27 28) variable splitting in random forests (2), noisy training 29 30), random sketched regression [ 33,33, various forms of data augmentation [34), feature augmentation 9 35). early stopping in gradient descent and its variants (36,39], among others. These connections highlight the pervasiveness and the significance of understanding various "facets" of ridge regularization. In that direction, our work contributes to expand the equivalences between subsampling and ridge regularization.
2 Notation and preliminaries
Ensemble estimators. Let D., [(2,, ua) E [ni]} be a dataset containing i.i.d. samples in R2 x R. Let X E R and y E Rn be the feature matrix and response vector with az. and y; in i-th rows. For an index set C [n] of size k, let D, = (( M1) i E l} be the associated subsampled dataset. Let L, E RRax be a diagonal matrix such that its i-th diagonal entry is 1 if E I and 0 otherwise. Note that the feature matrix and response vector associated with Dj respectively are X and Lry. Given ridge penalty À > O, the ridge estimator fitted D) consisting of k samples is given by:
I(u - 3T + +11l112 = ()-
"XTLIU k
BA = argmin
(1)
BERF
k
iE1
The ridgeless estimator
(D(D) (x))))=(TTL))) (XT,)/)>X L,y/ lk is obtained by sending A - 0+, inverse of matrix M. To define the ensemble estimator, denote
where M denotes the
3

---

Table 2: Summary of various generalized risks and their corresponding statistical learning problems. The asymptotic equivalences between subsampling and ridge regularization are analyzed in Theorem | and Proposition for generalized risks 3 defined through functionals LA,b
& for various A and b.
Statistical learning problem
1.,,((3 Bo)
A
b
nrow (A)
vector coefficient estimation
3 3o
p
projected coefficient estimation
a (13 3b)
a T
0
1
training error estimation
XB
X
fNN.
in-sample prediction
((3 Bb)
X
n
out-of-sample prediction
2 3 y/
-60
1
the set of all k distinct elements from [n] by I = {fi,,2,,... be,...,,,,,,,...... 4 15 < < <... < S n).
For 2 0, the M-ensemble and the full-ensemble estimators are respectively defined as follows:
(Dn: (Te)
Σ (DDr)) and Blo (Dn) (I)) [D) RE[M]
Here {I 3%,00 (Dn)) is the average of predictors fitted all possible subsampled datasets, is shown in Lemma A. of 13 that 3 (D,,) is also asymptotically equivalent to the limit of 3 M (Dn; { [1r) {1e) as the ensemble size M - oc (conditioning on the full dataset D..). This also justifies using co the subscript to denote the full- full-ensemble estimator. For brevity, we simply write the estimators as 3 3/ and drop the dependency on D,,, {1e) We will show certain structural equivalences in terms of linear projections in the family of estimators 3r, vr along certain paths in the (A, p/ 1 -pllane for arbitrary ensemble size M E N U {oo} (in Theorem (3. Apart from connecting the estimators, we will also show equivalences of various notions of risks (in Theorem D.. which we describe next.
t= and are simple random samples from Ig. In 2 the full-ensemble ridge estimator
Generalized risks. Since the ensemble ridge estimators are linear estimators, we evaluate their performance relative to the oracle parameter: Bg = E f ]="E[ which is the best (population) linear projection of y onto x and minimizes the linear regression error (see, e.g., 42) Note that we can decompose any response y into: y = faa(2)) + (ar), where far(2) = 30 ar is the oracle linear predictor, and fNL = y - fu(()) the nonlinear component that is not explained by fu(()). The best linear projection has the useful property that fu) is (linearly) uncorrelated with fN,(#) although they are generally dependent. It worth mentioning that this does not imply that y and follow a linear regression model. Indeed, our framework allows any nonlinear dependence structure between them and is model-free for the joint distribution of (x. y). Relative to Go. we measure the performance of an estimator 33 via the generalized mean squared risk defined compactly as follows:
1 R(0; A, b, Bo) nrow (A) || Bb)
where LA,( AB + is a linear functional. Note that A and can potentially depend on the data, and their dimensions can vary depending on the statistical learning problem at hand. This framework includes various important statistical learning problems, as summarized in Table 2 Observe that the framework also includes various notions of prediction risks. One can use the test error formulation in Table 2 to obtain the prediction risk at any test point (æo, yo), where yo = 2 Bu + Ep. and Eo may depend on and have non-zero mean. This also permits the test point to be drawn from distribution that differs from the training distribution. Specifically, when Eg = SNI. (wx) but 2ng has a distribution different from æ, we obtain the prediction error under covariate shift. Similarly, when Eo # fNL (wo) but Hy and æ have the same distribution, we get the prediction error under label shift.
Asymptotic equivalence. For our theoretical analysis, we consider the proportional asymptotics regime, where the ratio of the feature size p to the sample size n tends aspect ratio & (0, oo). To concisely present our results, we will use the elegant framework of asymptotic equivalence 12 43
fixed limiting data
Let Ap and B, be sequences of (additively) conformable matrices of arbitrary dimensions (including vectors and scalars). We say that A, and B, are asymp- totically equivalent, denoted as A, ~ Bp. if limp (A, - B,)]] = 0 almost surely for any sequence of random matrices Cp with bounded trace norm that are (multiplicatively) conformable and independent of A, and B,. Note that for sequences of scalar random variables, the definition simply reduces to the typical almost sure convergence of sequences of random variables involved.

---

Estimation risk
Training error
Prediction risk
Prediction risk (OOD)
Ridge penalty A
40
5300
923
-36
531
10
Subsample aspect ratio
Figure 1: Heat map of the various generalized risks (estimation risk, training error, prediction risk, out-of-distribution (OOD) prediction risk) of full-ensemble ridge estimators (approximated with M 100), for varying ridge penalties À and subsample aspect ratios = p/ík on the log-log scale. The data model is described in Appendix F22 with p = 500, n = 5000, and é p/n = 0.1. Observe that along the same path the values match well for all risks, in line with Theorem Tanedmaannnd and Proposition
3 Generalized risk equivalences of ensemble estimators
We begin by examining the risk equivalences among different ensemble ridge estimators for various generalized risks defined in (3). To prepare for our upcoming results, impose two structural and moment assumptions on the distributions of the response variable and the feature vector.
Assumption 1 (Response variable distribution). Each response variable yt for E [ni] has mean and satisfies [[] I Mμ < 0o for some μ > 0 and a constant Mp-
Assumption 2 (Feature vector distribution). Each feature vector æ; for E [n]] can be decomposed as 2; = Σ 2,. where 2; E I" contains i.i.d. entries 2sj for j E [p] with mean 0, variance 1, and satisfy E| |+|= I M, < po for some v > O and a constant M,, and Σ E RRXP is a deterministic and symmetric matrix with eigenvalues uniformly bounded between constants Tmin >> and Tmax < co.
Note that we do not impose any specific model assumptions on the response variable in relation to the feature vector We only assume bounded moments as stated in Assumption [ making all of our subsequent results model-free. The zero-mere meno assumption for y is for simplicity since, in practice, centering can always be done by subtracting the sample mean. The bounded moment condition can also be satisfied one imposes a stronger distributional assumption (e.g.. sub-Guusee Gaussianity) Assumption 2 on the feature vector is common in the study of random matrix theory [45] 46] and the
analysis of ridge and ridgeless regression 10 47H49,, which we refer to as RMT features for brevity,
Given limiting data aspect ratio & E (0, oo) and limiting subsample aspect ratio ip E [0) oo]. our statement of equivalences between different ensemble estimators defined through certain paths char- acterized by two endpoints (0, ) and (A, 6). These endpoints correspond to the subsample ridgeless ensemble and the (non-ensemble) ridge predictor, respectively, with À being the ridge penalty to be de- fined next. For that, let Hp be the empirical spectral distribution of E: Hp(r) p " (rvSr)) where r.'s s are the eigenvalues of E. Consider the following system of equations in À and w:
- + dHp(r), and -
r
r
dr,(r)-
(4)
+
Existence and uniqueness of the solution (X. v) E [0, o0 to the above equations are guaranteed by Corollary E.4 Now, define a path Paxx Φ. 15) that passes through the endpoints (0, t)) and (ī, Ø): O)) {(1-0) 0) (7,
(0, T) 0 e [o,
(5)
We are ready state our results. We consider two cases for the generalized risk (3) depending on the relationships between (A, b) and X. In the first case, when both A and are independent of the data, Theorem shows that the generalized risks are equivalent along the path (5).
Theorem 1 (Risk equivalences when (A. b) IL (X, 4)). Suppose Assumptions 72 hold. Let (A. b) be independent of (X, 3) such that nrow(A) -1/2||1 ||/ llop and ||bll2 are almost surely bounded. Ler n.P P- - oo such that p/n - de E (0, oo). For any ve E (é. (2)) let X be as defined in (4). Then, for any pair of (A1, w1) and (A2, 222) on the path P(); o. +) as defined in (5), the generalized risk functionals B3) of the full- full-ensemble estimator are asymptotically equivalent:
R( 11/011..00 A,,,3) R(3 (0/v2)..c A. b, Bb).
(6)
In other words, Theorem establishes the equivalences of subsampling and ridge regularization in terms of generalized risk for many statistical learning problems, encompassing coefficient estimation.
5

---

coefficient confidence interval, and test error estimation. All of these problems fall in the category when (A. b) are independent of X. However, there are other statistical learning problems not covered
in Theorem 1 such as the in-sample prediction risk and the training error, which correspond to the case when
X. Fortunately, the equivalences also apply to them, as summarized in Proposition 2
Proposition 2 (Risk equivalences when A = xX). Under Assumptions 2 when A = X. the conclusion in Theorem continue to hold for the cases of -ampl prediction risk (b 0) and
training error (b = -
Both Theorem T and Proposition 2 provide specific second-order equivalences for the full-ensemble ridge estimators, in the sense that the quadratic functionals of the estimators associated with (A. b) asymptotically the same. See Figure [ for visual illustrations of both equivalences. These statements are presented separately because their proofs differ, with the proof for the dependent case being more intricate. We note that by combining the risk functionals in Table 2 it is possible to further extend the equivalences to other types of functionals not directly covered by statements above, using composition and continuous mapping. For example, it is not difficult to show that similar equivalences hold for the generalized cross-validation the full ensembles [3]. This follows by combining the result for training error from Proposition 2 and for denominator concentration proved in Lemma 3.4 of [1]
Theorem D generalizes the existing equivalence results for the prediction risk 11-33 to include general risk functionals under milder assumptions. As summarized in Table [ we allow for a general response model and feature covariance without assuming convergence of the spectral distributions Hp to fixed distribution H. This flexibility is achieved by showing equivalences of the underlying resolvents in the estimators rather than deriving the limiting functionals done in previous works. To extend results allowing for a general response, we generalize certain concentration results by leveraging tools from 14 to handle the dependency between the linear and non-linear components.
As alluded to earlier, it is worth noting that the generalized risk equivalences only hold in the full ensemble. However, by using the risk decomposition obtained from Lemma S.1.1 of [12] for finite ensembles, one can obtain the following relationship along the path in Theorem 3 ( I A, 3o) - R(@ (p/0bs).M b, Bo) = A/M, for some A (independent of M) that is eventually almost surely bounded. In other words, the difference between any two estimators
on the same path scales as 1/M when n is sufficiently large, as numerically verified in Figure F5
4 Structural equivalences of ensemble estimators
The equivalences established in the previous section only hold for the full-ensemble estimators in a second-order sense. We can go a step further and ask if there exist any equivalences for the finite ensemble and if there are any equivalences at the estimator coordinate level between the estimators. Specifically, we aim inspect whether each coordinate of the p-dimensional estimated coefficients asymptotically equals. This section establishes structural relationships between the estimators in first-order sense that any bounded linear functionals of them are asymptotically the same.
Theorem (Structural equivalences). Suppose Assumptions 7 hold. Let n, P + co with p/ - & E (0, o.). For any Vb E (d) +o0), let be as in (4) Then, for any M N and any pair of (X1, 1 and (Az, 1/22) the path (5), the M-ensemble estimators are asymptotically equivalent:
B P//TIM 2
3/// Le/val.M
Put another way, Theorem immples that for any fixed ensemble size M, the Meensmbble ridgeless estimator at the limiting aspect ratio 17 is equivalent to ridge regression at the regularization level This equivalence is visually illustrated in Figure where the data is simulated from anisotropic and nonlinear model (see Appendix F.2 for more details). Furthermore, the contour path P(x: 6. v)) connecting the endpoints (0, Φ) and (A, d) is straight line, although it may have varying slopes. Along any path, all Mennemble estimators at the limiting aspect ratio & and ridge penalty are equivalent for all (X, v) E P(x; Φ, v)). The equivalences here are for any arbitrary linear combinations of the estimators. In particular, this implies that the predicted values (or even any continuous function applied to them due to the continuous mapping theorem) of any test point will eventually be the same, almost surely, with respect to the training data. Finally, remark that in the statement of Thhorem the equivalence is defined on extended reals in order to incorporate the ridgeless case when e 1.

---

(a)
Uniform, M =
Uniform, M
Uniform, M 50
Ridge penalty
4
coo
(b)
Uniform, M 100
Gaussian, M 100
Student's M.M 100
Ridge penalty
cor
Subsample aspect ratio
Figure 2: Heat map of the values of various linear functionals of ensemble ridge estimators B M for varying ridge penalties X, subsample aspect ratios v p/k: and ensemble size M on the log-log scale. The data model is described Appendix F.2with with p = 1000. n 10000, and (a) The values of the uniformly weighted projection for varying ensemble sizes (M = 1, 5, and 50). (b) The values of M 100 for varying projection vectors (uniformly weighted, random Gaussian, and random student's 's t). The black dashed line is estimated based on Proposition g with e 2. Observe that the values along the data-dependent paths are indeed very similar, in line with Proposition
p/n 0.1.
The paths (5 in Theorem 3 are defined via the spectral distribution Hp, which requires knowledge of E. This is often difficult obtain practice from the observed data. Fortunately, we can provide an alternative characterization for the path 5 solely through the data, summarized in Proposition 4
Proposition 4 "Dataddependen equivalence path characterization). Suppose Assumptions
2 hold.
Define On = p/n. Let S n be the subsample size and denote by ih = -p/k. For any M (o) let Xn be the value that satisfies the following equation in ensemble ridgeless and ridge gram matrices:
( L.. ) = ( (=XX* + Nn
Define the data-dependent path P,, P(Tni Onr Dn). Then, the conclusion Theorem continues to hold if we replace the (population) path P by the (data-dependent) path P,,.
The term "data-dependent path" signifies that we can estimate the level of implicit regularization induced by subsampling solely based on the observed data by solving (8). We remark that (8) always has at least one solution for a given triplet of (n, k. p). This is because the right-hand side of (8) is monotonically decreasing in X, and the heft-hand side always lies within the range of the right-hand side. The powerful implication of the characterization in Proposition i that enables practical computation of the path using real-world data. In Section 6, we will demonstrate this approach on various real-world datasets, allowing us to predict an equivalent amount of explicit regularization matching the implicit regularization due to subsampling.
One natural extension of the results is to consider the generalized ridge as a base estimator 1
3r (G)(DD = argmin
E(u - x xT² A||
(9)
BER
K
iE!
where G E TRXP is positive definite matrix. The equivalences still hold, albeit on different paths:
Corollary (Equivalences for generalized ridge regression). Suppose Assumptions 1 hold. Let G E Rpxp be deterministic and symmetric matrix with eigenvalues uniformly bounded between Jtnin > and Jmnx < Go. Let n.P + OC such that p/n. - & E (0, c0). For any J E (6 +00), let X be as defined in 4 with Hp replaced H p the empirical spectral distribution of Then, the conclusions in Theorems 7 and continue hold for the generalized ridge ensemble predictors.
constants
G E-1/2G--111
Another extension of our results to incorporate subquadratic risk functionals in Theorem to derive equivalences of the cumulative distribution functions of the predictive error distributions associated
7

---

with the estimators along the equivalence paths. One can use such equivalences for downstream inference questions. Finally, while our statements are asymptotic in nature, we expect similar analysis as done in (50 can yield finite-sample statements. We leave these extensions for the future.
5 Implications of equivalences
The generalized risk equivalences establish connection between the risks of different ridge ensem- bles, including the ridge predictors on full data and the full-ensemble ridgeless predictors. These connections enable us to transfer properties from one estimator to the other. For example, by exam- ining the impact of subsampling on the estimator's 's performance, we can better understand how to optimize the ridge penalty. We will next provide an example of this. Many common methods, such as ridgeless or lassoless predictors, have been recently shown to exhibit non-monotonic behavior in the sample size or the limiting aspect ratio. An open problem raised by Nakkiran et al. [] Conjecture 1] asks whether the prediction risk of the ridge regression with optimal ridge penalty X is monotonically increasing in the data aspect ratio @ = p/ n. The non- monotonicity risk behavior implies that more data can hurt performance, and it's important to investigate whether optimal ridge regression also suffers from this issue. Our equivalence results provide a surprising (even to us) indirect way to answer this question affirmatively under proportional asymptotics.
To analyze the monotonicity of the risk, we will need to impose two additional regularity assumptions to guarantee the convergence of the prediction risk. Let Σ = - ,,,,; denote the eigenvalue decomposition, where (T) W,y's are pairs of associated eigenvalue and normalized eigenvector. The following assumptions ensure that the hardness of the underlying regression problems across different limiting data aspect ratios is comparable.
Assumption (Spectral convergence). We assume there exists a deterministic distribution H such that the empirical spectral distribution of Σ, Hp(r) = p-1 Σ 1 (rigr), weakly converges to H, almost surely (with respect to æ)).
Assumption 4 (Limiting signal and noise energies). We assume there exists deterministic distribu- tion G such that the empirical distribution of Bo 's (squared) projection onto E's eigenspace, Gp(r) = ||300122 Ei= (3, w,)2 1 (ry.r), weakly converges to G. As n. p + oo and p/n + o E (0, oo), the limiting linearized energy 1 = lim ||,r 1|2 and the limiting nonlinearized energy o² lim f 1. are finite.
Assumption is commonly used in random matrix theory and overparameterizeed learning 10
and ensures that the limiting spectral distribution of the sample covariance matrix converges to a fixed distribution. Under these assumptions, we show in Appendix Chatt there exists deterministic function (x; Φ v) such that R( A, b, Bo) = (); Φ. v). Notably, the deterministic profile on the right-hand side is a monotonically increasing and a continuous function in the first parameter é when limiting values of ||3o and [l. are fixed (i.e., when Assumption 4 holds). Moreover, the deterministic risk equivalent of the optimal ridge predictor matches that of the optimal full- ensemble ridgeless predictor; in other words, min120 ((; A Φ) = min (0; d, v²). The same monotonicity property of the two optimized functions leads to the following result.
Theorem 6 (Monotonicity of prediction risk with optimal ridge regularization), Suppose the con- hold. Let ki n.P - Do such that p/n - E (0, x)) and b = O. the optimal risk of the ridgeless ensemble, ming26 (0; d. ))), is monotonically increasing in d. Consequently, the optimal risk of the ridge predictor, minx A ()x d). is also monotonically increasing in 6.
ditions of Theorem 7 and Assumptions
and p/k + v [o, oc]. Then, for A
Under Assumptions 3 and 4 the linearized conal-to-noisse ratio (SNR) is maintained at the same level changes. The key message of Theorem 6 is then that, for sequence
across varying distributions of problems with the same SNR (indicating the same level of regression hardness), the asymptotic prediction risk of optimized ridge risk gets monotonically worse the aspect ratio of the problem increases. This is intuitive because a smaller & corresponds to more samples than features. In this sense, Theorem non-monotonicity. Moreover, as the null risk is finite, this also shows that the optimal ridge estimator mitigates the "double or multiple descents" behaviors in the generalization error
D certifies that optimal ridge uses the available data effectively, avoiding sample-wise
51).
Attempting to prove Theorem dirrectly is challenging due to the lack of closed- form expression for the optimal risk of ridge regression in general. Moreover, the risk profile of ridge regression,
8

---

Paths through (Ag. M0 for varyling Ag:
Ap
Ap 0.05
Ap
1.00
Relative valio
0.75
0.50
0.25
0.00
H
I
I
-0.25
Unifom
Gaussian
Studorts:
Estimation rot
Prodiction
Presition
Linear functionals
Genearlized risk functionals
Figure 3: Comparison of various linear functionals (Theorem and generalized risk functionals (Theorem I on different paths evaluated on CIFAR-10. The aspect ratios Φ = p/n and i = 46 are estimated from the dataset and fixed. For different values of \ (different colors), we estimate À from Proposition which gives a path between (>7, v and (7, Φ). For each path, we uniformly sample points and compute the functionals of the ridge ensemble using M 100. The values of different paths are then normalized by subtracting the mean value in the first path and dividing by the mean difference of values on the last and first paths.
((A: o, d), does not exhibit any particular structure function of A. On the other hand, the risk profile of the full-ensemble ridgeless, L ((; Φ, vi), has a very nice structure in terms of tb This, coupled with our equivalence result, allows one to prove quite non-trivial behavior of optimal ridge. See Figure F6 for illustrations.
Discussion
Motivated by the recent subsampling and ridge equivalences for the prediction risk 11:13 this paper establishes generalized risk equivalences (Section B and structural equivalences (Section within the family of ensemble ridge estimators. Our results precisely link the implicit regularization of subsampling to explicit ridge penalization via a path P defined in (5). which connects two endpoints (0, )) and (X. Φ) regardless of the risk functionals. Furthermore, we provide data-dependent method (Proposition
4 to estimate this path. Our results do not assume any specific relationship between the response variable y and the feature vector æ. We next explore some extensions of these equivalences.
Real data. While our theoretical results assume RMT features (Assumption) 2), we anticipate that the equivalences will very likely hold under more general features [50]. To verify this, we examine the equivalences in Proposition 4 with M = 100 on real-world datasets. Figure 3 depicts both the linear functionals in Theorem and the generalized quadratic functionals in Theorem I computed along four paths, shown in different colors. We observe that the variation within each path is small, while different paths have different functional values. This suggests that the theoretical finding in the previous sections also hold quite well on real-world datasets. We investigate this further by varying vi on the three image datasets, CIFAR- 10. MNIST, and USPS. Figure F7suows the two points. These experiments demonstrate that the amount of explicit regularization induced by subsampling can indeed be accurately predicted based on the observed data using Proposition 4
shows similar values and trends
Random features. Closely related to two-layer neural networks [52] we can consider the random feature model, (x: B, F)- = ,3 (Fx),, where F E Rddxp is some randomly initialized weight matrix, and مي R - IR is a nonlinear activation function applied element-wine to Fz. As from "universalitylivvrrineee"" certain random feature models are asymptotically equivalent to a surrogate linear Gaussian model with a matching covariance matrix [53] we expect the theoretical results in Theorems 3 to likely hold, although the relationship
will now depend on the non-linear activation functions. Empirically, we indeed observe similar equivalence phenomena of the prediction risks with random features ridge regression using sigmoid, ReLU, and tanh activation functions, as shown in Figure 4 Analogous to Proposition we conjecture similar data-driven relationship between (Xn, o..) and (0, vn,) for random features X = xx FT):
Conjecture 7 (Data-dependent equivalences for random features (informal)). Suppose Assumptions ! 2 hold. Define Φ., p/n. Let k S n be the subsample size and denote by tha = p/k. Suppose ip satisfies certain regularity conditions. For any M E NU (oo). let Nn be the value that satisfies
M
n (
1 tr )x(FF (=((XF")(XFF)
M tr
9

---

Sigmoid
RuLU
Tanh
Ridge penalty A
0.0
0.1
137
100
133
10
1.
Subsample aspect ratio
Figure 4: Heat map of prediction risks of full-ensemble ridge estimators (approximated with M 100) using random features, for varying ridge penalties A, subsample aspect ratios v = p/ on the log-log scale. We consider random features şo (F;;;;; E IR where yp an activation function (sigmoid, ReLU, or tanh). The data model is described in Appendix [16 with p 250, d 500, 5000, and = d/n 0.1. As Theorem [ we see clear risk equivalence paths across activations.
Define the data-dependent path Pn, P(An: On bn). Then, the conclusions in Theorem Proposi- tion 2
and Theorem continue to hold on (vp(X ), y) with P replaced by P..
Kernel features. We can also consider kernel ridge regression. For a given feature map a RR + Rdd the kernel ridge estimator (in the primal form) is defined as:
k 11 p
-argmin (A(D))
Ek- - x11/22 T3 + 1I Σ (y: - (v::((r;;) 3) + SE1
BERF
Leveraging the kernel trick, the preceding optimization problem translates to solving the follow- ing problem (in the dual domain): at = ar argmingert a (K, + kAIg) a + a yı, where K; Φ R is the kernel matrix and Φ (Φ(x,)) (x))) E Rndd is the feature matrix. The correspondence between the dual and primal solutions is simply given by: (D)) = 2 (Dr).
Figure illustrae results for kernel ridge regression using the same data data-generating process as in the previous subsection. The figure shows the prediction risk of kernel ridge ensembles for polynomial, Gaussian, and Laplace kernels exhibit similar equivalence patterns, leading us to formulate an analogous conjecture for kernel ridge regression (which when & (x) = x gives back Proposition with appropriate rescaling of features):
equivalences for kernel features (informal)). Suppose Assumptions 7 2 hold. Define on = p/n. n. Suppose the kernel satisfies certain regularity conditions. Let S n be the subsample size and denote by in = p/l For any M E (oo), let X, be a solution to
Conjecture 8
(
Σ
[
K
(Kim
n1 "
Define the data-dependent path Pn, = P(Xni dn B.). Then, the conclusions in Theorem Proposi- tion 2 and Theorem 3 continue to hold for kernel ridge ensembles with P replaced by Pa.
The empirical evidence here strongly suggests that the relationship between subsampling and ridge regression, which we have proved for ridge regression, holds true at least when the gram matrix "linearizes" in the sense of asymptotic equivalence [14 54 (5). This intriguing observation opens up whole host of avenues towards fully understanding the universality of this relationship and We hope to share
establishing precise connections for a broader range of models [17 18 20 21.
more on these compelling directions in the near future.
Tying other implicit regularizations. Finally, as noted in related work, the equivalences between ridge regularization and subsampling established in this paper naturally offer opportunities to interpret and understand the other implicit regularization effects such as dropout regularization 27 28 early stopping in gradient descent variants [36] 38 39). Furthermore, these equivalences provide avenues to understand the combined effects of these forms of implicit regularization, such as the effects of both subsample aggregating and gradient descent in mini-batch gradient descent, and contrast them to explicit regularization. Whether the explicit regularization can always be cleanly expressed as ridge-like regularization or takes a more generic form an intriguing question. Exploring this exciting, and we hope readers also share this excitement!
10

---

Acknowledgments and Disclosure of Funding
We are indebted to Ryan Tibshirani, Alessandro Rinaldo, Arun Kuchibhotla, Yuting Wei, Matey Neykov, Edgar Dobriban, Daniel LeJeune, Shamindra Shrotriya, Yuchen Wu for many insightful conversations. We are also grateful to anonymous reviewers of the precursor [3] for encouraging us to work several follow-up directions that make up parts of this successor. On more personal note: The lack of proof of risk monotonicity of optimally -tuned ridge in general had been "monotone bugging" (in good way) the first author, ever since plotting Figure 8 (and other similar plots) in [5T]. The resolution in Theorem 6 of great personal significance to him and he is heartily appreciative of related threads, especially the second author, for being dedicated climbing
all the collaborators partner on this technical "ascent". At the risk of over analogizing, the metaphor of letting a nut soak in water instead of forcibly cracking open with hammer, from Grothendieck may perhaps describe the proof of Theorem 6 Establishing subsampling and ridge equivalences first and using it demonstrate ridge monotonicity, in retrospect, seems much less arduous route than direct brute-force attempt (with calculus, say). But we will let the readers decide!
This work used the Bridges2 system at the Pittsburgh Supercomputing Center (PSC) through allo- cations MTH230020 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program. The code for reproducing the results of this paper can be found at https://faydul..iitte io/ ttoovvrrpaaaeterriizeee wwweeennnenegeeeeeeeeee hngg
References
[1] Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. International Conference on Learning Representations, 2021.
[2] Leo Breiman. Bagging predictors. Machine Learning, 24(2):123-14)) 1996.
[3] Peter Bühlmann and Bin Yu. Analyzing bagging. The Annals of Statistics, 30(4):927-961, 2002.
[4] Abraham J. Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of adaboost and random forests as interpolating classifiers. The Journal of Machine Learning Research, 18(1):1558-1553 2017.
[5] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variane variance trade-off. Proceedings of the National Academy of Sciences, 116632):15449-1588
2019.
[6] Lucas Mentch and Siyu Zhou. Randomization regularization: A degrees of freedom explana- tion for random forest success. The Journal of Machine Learning Research, ((1):6918-695))) 2020.
[7] Arthur E. Hoerl and Robert W. Kennard. Ridge regression: Biased estimation for nonorthogonal problems. Technometrics, 12(1):55-67, 1970.
[8] Arthur E. Hoerl and Robert W. Kennard. Ridge regression: Applications to nonorthogonal problems. Technometrics, 12(1):69-8)) 82, 1970.
[9] Trevor Hastie. Ridge regularization: An essential concept in data science. Technometrics, 62 (4):4264433, 2020.
[10] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986, 2022.
[11] Daniel LeJeune, Hamid Javadi, and Richard Baraniuk. The implicit regularization of ordinary least squares ensembles. In International Conference on Artificial Intelligence and Statistics, 2020.
page

---

[12] Pratik Patil, Jin-Hong Du, and Arun Kumar Kuchibhotla. Bagging in overparameterrized learning: Risk characterization and risk monotonization. arXiv preprint arXiv:2210.11445, 2022.
[13] Jin-Hong Du, Pratik Patil, and Arun Kumar Kuchibhotla. Subsample ridge ensembles: Equiv- alences and generalized cross-validation, In International Conference on Machine Learning, 2023.
[14] Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: A statistical viewpoint. Acta numerica, 30:87-201, 2021.
[15] Trevor Hastie, Robert Tibshirani, and Jerome H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2009. Second edition.
[16] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[17] L.K. Hansen and P. Salamon. Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence 12(10):993-1011 1990.
[18) Anders Krogh and Jesper Vedelsby. Neural network ensembles, cross validation, and active learning. Advances neural information processing systems, 1994.
[19] Balaji Lakshminarayannan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, 2017.
[20] Michael Perrone. Putting it all together: Methods for combining neural networks. In Advances in Neural Information Processing Systems, 1993.
[21] Anders Krogh and Peter Sollich. Learning with ensembles: How overfitting can be useful. In Advances in Neural Information Processing Systems, 1995.
[22] Anders Krogh and Peter Sollich. Statistical mechanics of ensemble learning. Physical Review E, 55(6):811, 1997.
[23] Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning, pages 2280-2290 PMLR, 2020.
[24] Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine- fine-grained bias-variance decomposition. In Advances in Neural Information Processing Systems, 2020.
[25] Bruno Loureiro, Cedric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala. Fluctuations, bias, variance & ensemble of learners: Exact asymptotics for convex losses in high-dimension. In International Conference on Machine Learning. 2022.
[26] Tianyi Yao, Daniel LeJeune, Hamid Javadi, Richard G. Baraniuk, and Genevera I. Allen. Minipatch learning as implicit ridge-like regularization. In International Conference on Big Data and Smart Computing, 2021.
[27] Stefan Wager, Sida Wang, and Percy S. Liang. Dropout training as adaptive regularization. In Advances Neural Information Processing Systems, 2013.
[28] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1):1929-1958 2014.
[29] Andrew R. Webb. Functional approximation by feed-forward networks: A least-squares approach to generalization. IEFE Transactions on Neural Networks, 5(3):363-371, 1994.
[30] Chris M. Bishop. Training with noise equivalent to Tikhonov regularization. Neural computation, 7(1):108-116, 1995.
12

---

[31] Gian-Andres Andrea Thanei, Christina Heinze, and Nicolai Meinshausen. Random projections for large-scale regression. Big and Complex Data Analysis: Methodologies and Applications, pages 51-68, 2017.
[32] Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nyström com- putational regularization. Advances in Neural Information Processing Systems, volume 28, 2015.
[33] Daniel LeJeune, Pratik Patil, Hamid Javadi, Richard G Baraniuk, and Ryan J. Tibshirani. Asymptotics of the sketched pseudoinverse. arXiv preprint arXiv:2211.03751, 2022.
[34] Chi-Heng Lin, Chiraag Kaushik, Eva I.. Dyer, and Vidya Muthukumar. The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective. arXiv preprint arXiv:2210.05002, 2022.
[35] Marina Skurichina and Robert W. Duin. Regularization by adding redundant features. In Advances in Patlern Recognition: Joint IAPR International Workshops SSPR '98 and SPR Sydney, Australia, August 11-13, 1998 Proceedings, pages 564-572. Springer, 1998.
[36] Gergely Neu and Lorenzo Rosasco, Iterate averaging as regularization for stochastic gradient descent. In Conference On Learning Theory, pages 3222-3242. PMLR, 2018.
[37] Arun Suggala, Adarsh Prasad, and Pradeep K. Ravikumar. Connecting optimization and regularization paths. In Advances Neural Information Processing Systems, 2018
[38] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International conference on machine learning, 2020.
[39] Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous-ting time view of early stopping for least squares regression. International Conference on Artificial Intelligence and Statistics, 2019.
[40] A. Buja, R. Berk, L. Brown, E. George, E. Pitkin, M. Traskin, K. Zhang, and L. Zhao. A conspiracy of random predictors and model violations against classical inference in regression. arXiv preprint arXiv: 1578, 2014.
[41] Andreas Buja, Lawrence Brown, Richard Berk, Edward George, Emil Pitkin, Mikhail Traskin, Kai Zhang, and Linda Zhao. Models as approximations I. Statistical Science, (234)5423-544 2019.
[42] Andreas Buja, Lawrence Brown, Arun Kumar Kuchibhotla, Richard Berk, Edward George, and Linda Zhao. Models as approximations Statistical Science, 34(4):545-565, 2019.
[43] Edgar Dobriban and Yue Sheng. Wonder: Weighted one-shot distributed ridge regression in high dimensions. Journal of Machine Learning Reseurch, 21(66): 2020.
[44] Edgar Dobriban and Yue Sheng. Distributed linear regression by averaging. The Annals of Statistics, 49(2)-918-943, 2021.
[45] Zhidong Bai and Jack W. Silverstein. Spectral Analysis of Large Dimensional Random Matrices. Springer, 2010. Second edition.
[46] Noureddine El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38 (1):1-50, 2010.
[47] Noureddine El Karoui and Holger Kösters. Geometric sensitivity of random matrix results: Consequences for shrinkage estimators of covariance and related statistical methods. arXiv preprint arXiv: 105. 1404, 2011.
[48] Noureddine Karoui. Asymptotic behavior of unregularized and ridge-regularized high- dimensional robust regression estimators: rigorous results. arXiv preprint 11X1v:1311.2445, 2013.
[49] Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regres- sion and classification. The Annals of Statistics, 46(1):247-279, 2018.
13

---

[50] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571, 2022.
[51] Pratik Patil, Arun Kumar Kuchibhotla, Yuting Wei, and Alessandro Rinaldo. Mitigating multiple descents: A model-agnostic framework for risk monotonization. arXiv preprint arXiv:2205.129377 2022.
[52] Song Mei and Andrea Montanari. The generalization error random features regression: Precise asymptoties and the double descent curve. Communications on Pure and Applied Mathematics, 75(4)6667-766 2022.
[53] Hong Hu and Yue M. Lu. Universality laws for high-dimensions learning with random features. IEEE Transactions on Information Theory, 69(3):1932-1964, 2023.
[54] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 2020.
[55] Mojtaba Sahraec-Ardaken Melikasadat Emami, Parthe Pandit, Sundeep Rangan, and Alyson K Fletcher. Kernel methods and multi- layer perceptrons learn linear models high dimensions. arXiv preprint arXiv:220..08088 2022.
[56] Antti Knowles and Jun Yin. Anisotropic local laws for random matrices. Probability Theory and Related Fields, 169:257-352, 2017.
[57] László Erdös and Horng- Tzer Yau. A Dynamical Approach to Random Matrix Theory. American Mathematical Society, 2017.
[58] Francisco Rubio and Xavier Mestre. Spectral convergence for general class of random matrices. Statistics & probability letters, 81(5):592-602, 2011.
[59] Voschnision. Torchvision: PyTorch's computer vision library.
https://github. com/
pytorch/vision 2016.
[60] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28300 2011.
14

---

Supplementary material for " "Generalized equivalences between subsampling and ridge regularization"
This document serves supplement to the paper "Generalized equivalences betweensubsampling and ridge regularization." " The initial (unnumbered) section of the supplement provides a summary of the notation used in both the paper and supplement, followed by an organization for the supplement.
Notation. Below we provide an overview of the notation used throughout.
General notation:
Notation
Description
Non-bold
Denotes univariates (scalars, functions, distributions, etc.) (e.g., X, H).
Bold lower case
Denotes vectors (e.g.. &. (3).
Bold upper case
Denotes matrices (c.g.. ()).
Calligraphic font
Denotes sets (e.g.. D).
Script font
Denotes certain limiting functions (c.g., in (27
N
Set of positive integers.
R.
RR+
Set of real numbers and positive real numbers.
C, C+
Set of complex numbers and complex numbers with positive imaginary part. Set (1,...,n)
[n]
n) for natural number n.
(x)
The positive part of real number The floor and ceiling of real number x. The L2 norm function f. [l = E. (x)
x) [x]]
|,81|2
The & norm vector G. The inner product of vectors and The transpose and Moore-Penrose inverse of matrix X E Rexp,
(v, w)
X X
tr(A), A
The trace and inverse (if invertible) of square matrix A E Rexp. The principal square root of positive semi-definite matrix Σ. The p p identity matrix.
E 1/2
I I
X llop
The operator norm (spectral norm) of real matrix X.
1tr
The trace norm (nuclear norm) tr((X X x)2/3 of real matrix X.
The matrix V ( where A V RV-1 is eigenvalue decomposition, and (R) is I applied (elementwise) to the diagonals of Rt
f(A)
A
B
The Loewner ordering for symmetric matrices A and
Almost sure convergence, convergence probability, and weak convergence.
Specific notation:
Notation
Description
(x, 9)
The population random vector in IR x
Dr
A dataset containing i.i.d. samples of (æ,y): D, {(,, v.) : [n])-
X, y
The feature matrix in R and the response vector in IR"
Di
subsampled dataset D, = {(x,, y: : 1}.
(Dr))
ridge estimator fitted on DD, with || = observations and ridge penalty An Mensemble ridge estimator fitted on (D,, M with subsample size k
Bi (P (M)M
and ridge penalty X.
The best (population) linear projection coefficient of onto x:
Bo
Elarx: " (ry).
fa)(
The best (population) linear projection of y onto x: 3p. The component of that is not explained by æ: x Bo. fu X X fx. [fvu. (xx, (l)))n)
(x))
fur fx
15

---

A note on indexing of sequences:
In the subsequent sections, we will prove the results for n, k. being a sequence of integers {Tim m== {km im {pm m= Alternatively, one can also view and p as sequences kn and pn. that are indexed by n. For notational brevity, we drop the subscript when it is clear from the context.
Organization. Below outline the structure of the rest of the supplement. The technical lemmas refer to the main ingredients that we use to prove results in the corresponding sections.
Table 3: Outline of the supplement.
Section
Description
Technical lemmas
Lemma
A.1
Lemma A.2
Appendix
Proof of Theorem
Proposition
(from Section
Lemma
A.3
Proof of Theorem
Proposition
Corollary
(from
Appendix
Lemma
Lemma B.2
Section
Appendix
Proof of Theorem 6 (from Section
Lemma C.1
New asymptotic equivalents, concentration results and other useful lemmas (used in Appendices A
Lemma D.I
Lemma D.2
Appendix D
A
Lemma
D.3
Lemma
D.5
Asymptotic equivalents: background and known results (used in Appendices A
Appendix E
Appendix
Additional details for all the experiments
A Proofs of results in Section 3
A.1 Proof of Theorem
Given an observation (x, y), recall the decomposition y = + explained in Section 2 For n i.ddd samples from the same distribution as (æx, y). we define analogously the vector decomposition:
y fu fNL,
(10)
where fu = X,3, and fvL. = [fNL Mieem)) Let n n = nrow (A). Note that
R( A, Bo) RB3, A, 0, 2m A Bo) + n 1
By Theorem 3 the cross term vanishes, i..., n b A( BD) - 0. We then have
R kc b, - R 02 Bo) as. | 00 A, 0, 0,) - R(B A, 0, Bo))
suffices to analyze R( 0,)
For simplicity, we treat A as the normalized matrix n 1/2 A to avoid the notation of nrow nrow(A). Note that y X 30 + fNI. e, where 3o is the best linear projection of y on X, fN. is the nonlinear residual and E is the independent noise. Let A
( L2X X /k +
L,/k) and
B Ip A X EI~I, [X(X L /k + AIp) We begin by decomposing the generalized
risk for arbitrary (X, k) into different terms:
R( A, Bb) |A Bb)
|AAA)y Bo)
||AA + fNi.) ABb
(A 1,) AT A(A 1,) fm. T(A)) A AA
+2 T(A A A - 1,)
= 3 A AB + frL. (AA)T (AA)TAA AAAA 2fsx TAA)T A AB.
16

---

A When À > O. from Lemma A.3 we know that the cross terms 2 ((A)) ( 3o vanishes as p tends to infinity. Further, by Lemma A.1 and Lemma A.2 follows that when A TT (X, as p/n + and p/k tb
R 0.00 A, Rp(A;d,))) = 0,
where the function Rp is defined
Rp(A: = = =;(:); A A'A) + [f I2 (- A.
(1I)
and the nonnegative constants (-) v. A and ;p(->: A ATA) are as defined in Lemma[A.I
When X = O, as in the proof of Theorem we again show that PA,A - Qn, is equivcontinuous over A [0, Amax] for any Amax E (0, 00) fixed, where we define
15). PAAA R(3 A, Bu),, and Qn,
When v A 1. it can be verified that |Pr,al. / Qn,ah. 18Qn,1/0M are bounded almost surely. Thus, by the Moore-Osgood theorem, follows that, with probability one,
lim |R(@R 3o) (0:00 -0000
lim lim |R(O, A,0, (p ()) - = 0. x-0+ n-000
AT) are functions the fixed-point solution v)) By Lemma C.1 we have that for き (Ø. ool there exists a segment P such that for all (Åi, 1h)), (A2, (b2) E P. it holds that u(-Ai; (2= 2/22 as p/k/ + 11i and p/k2 + 122. This
Note that o. a/, A A) and
implies that
Rp w/1 = Rp(22; 1b, v/2)
Thus, by triangle inequality, we have
|R33 A. R( k2 A, A,0,Bb - 0,
which completes the proof.
A.2 Proof of Proposition 2
When A = X and = fNL. the generalized risk reduces to
R(Br.oo A,b,3) = X x - BB) - -fxll1
X x3. - (X + f2
11
|X (X.0 fN.) (8,30 fNu)l1
3 ΣB + fxy T (Ip - X (I, XA
- + 2 Sm. -I,- x XB
The proof then follows analogously as in Theorem by involving Lemma A.1 and Lemma A.2 with A X.
When A X and O. we have
R( A, b, BTT BBBB + SSL TEL 2fsu T( EB
Invoking Lemma A.2 for fNi. TEA instead of fs. T(I, - (AA) X XAA))fs the proof follows analogously.
17

---

A.3 Technical lemmas
Lemma A.1 (Bias of generalized risk). Suppose the same assumptions in Theorem | hold with Let g = Ip A EiwI, [XX L /k + XIp) "1. For any A with limsup || lop bounded almost surely, the following statements hold:
(1) If A 11 y), then
3 A 3 - (. - 0.
(2) 1f A n2 1 X, then
Bo B AB (1-0/ /
v,E) Σ) as 0. 1+ dHp(r) ) Ep( ?p(->: ,,,
up(->:00r
Here the nonnegative constants up( ():))) Tp( x, A through the following equations:
ATA) A) and (ppc v, AT A) are defined
r
x vb
1+ Upp -->; dHp(T),
Φ tr A AE (Up(
A 1) E I,) 331p
o- v/ A A)
(1+ (1+1((-x;)))) dHp(r)
;(-A;o, v5 AT AT) = (vx( Ip) (Tp( A AJA + A ()(,,(->:;))>> + 330
Proof. Note that Bo is independent of
B AB X2E1, [M A AM2),
where Linz = X LI X/I n22 and M, = (XT Lr, X X/k + XIp) for j = 1,2. We analyze
the deterministic equivalents of the latter for the two cases.
(1) A JL v).
From Lemma D.1 (2)
we know that when is independent to (X, y), it follows that
X E J2 Ta IM, A
AM2]
(op(->x; E Ip)
(i,(->; A ATEEE + A
Then, by the trace property of deterministic equivalents in Lemma E.3 (4) we have
3J A A AB
a. 36 (Up( (up(->;;)) / Σ + Ip) (7 b, AT AJE ATA) (xp(--;;)))))) X; + Ip) 300
(-): 16 A A).
(2) A = n X.
From Lemma D.I (4) it follows that
(p(-):0)r dHp(r) 1 1 / 1+,)(~>;))r X 2 E Iw, [M EMM
(1 1x+ ()) (-x;)) -
Then, by the trace property of deterministic equivalents in Lemma E.3 (4) have
(1-0/ δ ep( ep(->:p)r d(p(()) (1+ (-x,, v))-
B BB
a.s.
I+
BIT (up( (o;--;;0)) I,) Σ (1p(->:3)) + Ip) -,))'1 Bo
a.s. (1 (1-0 / cp(->; w)r dH,(r)) 50(-1;0, E).
2
1+ -- x))
18

---

Lemma A.2 (Variance term of generalized risk). Suppose the same assumptions in Theorem
hold with X > O. Let & EI [(X L, X /k + XIp) Lı/k] and B I A
BI-IyA(X L k + 1IIp)=1 For any A with lim ||A lop bounded almost surely, the follow-
ing statements hold:
(1) If 11 (X, y). then
fm. (AA) A fM 11 (p( 01 E)) " 0.
(2) 1f n 1/2 x, then
f (AA) A AAAEN..
2.. 11 (1 1 (1- Φ
up(- "p(->: (Ha)r) (1 11 (; E))
1p b)r
| l 2 /
upl up(->;t5)r dH -1)
1+ (p(->>
1 fNL (XA I (X - IN)FNL
n2
(1-0) /
up( up(->:00r aHF,()) 2 o0 + mp(-;; th E)), + x-(x:
w)r -
Here the nonnegative constants (-);) and üip (-p(-> (~ A A) are defined through the following equations:
+ 1/
1+ 1p-p-->;pp (r) dHp(r),
Up( 1p<->; vb)
ò tr A AE(ep( (x::--1):000 E + I,)
$1pp
(- 1/ T A)
7
-p((~x;))² Φ
(1 (1+ ())r= dHp(r)
Proof.
The two cases are treated separately below.
(1) A IL y).
We split the proof into three different parts.
Part (1) Intersection concentration. Let fxL LIniffu LIiN Liart fsL
fo + fi + f2. Note that
X fs. AATT A AA fu. EI, (fo + fi) MMA
X
T k (fo + f2)
k
where M, = (XT T L1, X/k + (Pp) -1 By conditional independence and Lemma S.8.5 of [51. the cross terms vanish
X M,A AM, k
X X L2
L as 0, and fxL MAA
X
fsL
AM2
f2 as 0.
(12)
It remains to analyze the quadratic term of fo:
LinixX X
X T Linta fo-
fo
k M,
AM,
k
By conditioning on L X. from Lemma S.7.10 (1) of 12], we have
M, M = ( NI, + -C
19

---

where Eo = X Xo/iu, Xo = Lin,, X. C = (k io)/io ;, + Ip).
C₁ io(A(k: io)) (Eo + >1p) and in
[11 12/.
Then we have
X M AM2 k
Xo
k² Xo
M A AM X k
k
l/ k
k² X
A'M' X
M'
(13)
10
2
k
where X Xu + C) 1/2 A' = (I, + 13 A A(I, + C)-1/2 and M' = ((Ip C)-1/2 + C) A
+
Part (2) Diagonal concentration. We next use a similar strategy as in the proof of Lemma A.16
in [4 by showing that the off diagonal summation vanishes. Let E' = (I, + -I-
C) 1122, Since Xo 1/2 we have X = ZoZn/ Then, the quadratic form becomes:
bZ Jo X
M
A'M fo
io 1.2 So
Zo
+ AIn
-1 Zo
A'E
Z Vio
ZU i0
+
MIn) x1h)))
) fo
10 BBB
Via
10 B
fo
fo-
(14)
12
Note that from Lemma D.4
we have for any 0.
(B, (Bi + (B2) tB, B2(Bi BB
B B,BT'
B
+1B2) B,B
Let U E R nx with Ui ffoli 1 + f}. We then have
Σ [ BBB B.BT'luifoll [oolol//fols
ISişišn
= | B UU
s k U\ - (BB)) + |2 B2 (B, ~Bop)=lppp11 "lopp U/lrr
(15)
For the first two terms, Lemma D.3 implies that
( UU O, and K [(B + (B2) ,U} -3, 0.
For the last term, note that |B op || Eollop where || llop is almost surely bounded
as assumed, and || Eooloa S mmax + 6 /0)² almost surely as ks, n, + and p/n + Φ e (0, oc). p/k & e (6, 20| (see, c.g., the strong law of large numbers, Lemma D.5 and B |lop I -- Thus, the last term is almost surely bounded. It then follows that k- B B
45 Also. |U|| S 21] "*, 2 fll Ill, < from
U O. Therefore,
i 5 B BB fo
L BBB [no]]
O.
Part (3) Trace concentration. From the results in [56] it holds that
BB. "B,',BBT' 11 tr B,B a.s. O.
max ISiS
Further, -1 Ei f we have
11 11, by strong law large number and Lemma D.5 Therefore,
B.B 111 12 uN O.
(16)
20

---

Combining 12
13 and 16 yields that
S )AA) A AAAS (r((AA) A AA I1.vr.l2aa -
By the trace property tr((At) AAN = (A(A)(AA))
it remains derive the A], ATA],
A
deterministic equivalents of 4/
AA' A. Note that
[4 1n
( A A
E, B2,
M E 122 M2 A A
22
where Σine L / n Ig] and M, (X" L1, x (1p) \z,) for
1. The
above quantity is well-defined almost surely because [11 converges to some positive quantity almost surely. Next, we analyze the trace term for the two cases.
From Lemma
D.1
(3)
we know that when is independent to (X, y). follows that A.
E1 II [M Mn
5 (-): -x)
We have
p 1
fM A AA
1
- tr 1
II- [M M A]
k
Φ 1
a.a. 1 1,,
7p(-
( A A
v6
111xal1i2 X: X; v, A AT
where the second convergence is from Lemma S.8.3 of and the trace property in Lemma E.3 (4)
(2) A = n 1/
Instead of working on 13 we use the following decomposition:
M MM M, Σ, M2 Σ2M2 - M 1n + Mi E (1uu)- M2
2
Σ M, 2AM M2 M, M E (102)
Then, repeating Part (2) and (3) above, it suffices derive the deterministic equivalents of (AA) TAA We decompose this term into:
1 [XA I.) (AA I.) -
(A T A A4
I,- (17)
n
n
For the last two terms of the right hand side, following the similar argument as in Part (I), holds that
2 I - 2Φ / (p(-): 1+;p(->:0)> dHp(r) 2 0, and n
1 tr = (18)
n
For the first term of the right hand side, notice that it is the variance of the mean squared error computed on all samples, which the variance term of the numerator the generalized cross-validation (GCV) estimator in [13). It has been shown Proposition 3.6 of [13] that in the full ensemble, the GCV estimator is consistent with the prediction risk, which is also true for the variance term:
tr A
TXX I.))
(19)
B.S.
(p(->:
dH,(r)) ( E)).,
(20)
up(->:
Finally, combining
[4 16) with the above finishes the proof for the first convergence result of
A = -1/2
X.
21

---

Analogously, from 20 we also have
1
fn T (A
In (XA 1n)
n
- f 1 (1-0/
ʃ "p(-A: (Hg))) 7pp11pp(-);0) e; E)),
1 1x-x v)r
which finishes the proof for the second convergence result of = 112
Lemma A.3 (Cross terms of generalized risk). Suppose the same assumptions in Theorem 7 holdd
with > 0. Let A = EI [(X L //k + XI,) -p) Lı/k] and B Ip A EI (XX L L1 For any A with lim sup | dlop bounded almost surely, holds that
fML (At) A A B as. 0.
Proof. Note that
(l)())) A AB
Bul22
k hn
A
| op
B 1
op
$ I
11
18p | L X k (I 1lpp]
| 11 11 11.11
k
S h
[ |3pp 12 || ol 31..
Let sg be the singular value of Σz. From the results in 45 we have lim supp || Eollop s lim sup maxisisp 83 I Tmax + /vb)² almost surely k,p and p/k - vb E (0, co]. On the other hand, n/kk "*, w/0 and || is uniformly bounded as assumed. Thus, we have A AB Goll bounded almost surely.
lim sumsupri ral( A
Similar to the proof of Theorem we decompose fxi. as fvi. = Linntf + LIyafm + Ligh So
f2. We then have
L
X LLInIXX
fv.
M, T AM,
Bo
b
Lnnt,
X
X LLnnn
X
a.s.
fo
Mi
A AM2
Go
k
k
222 X
as. fo
Lignaa
M' A'M'S
t0 fo Li,nia k
122
X
1.2 X M' A'M' Bo. 10 fo L o k
M'
A'3,
o k
k
where the first convergence is from Lemma S.8.5 of [51 and the second convergence from with X = Xo(4, CC A' (I, + C)-1/ A(I, + C)-1/² and M' (E% + XI,) and Σ/ = (T, 112 I, C)-1/2 From Lemma D.2 the first term in the above display vanishes. Analogous to (5), the second term also vanishes by splitting and applying Lemma D.2 Thus, we have for 1,, 12 It.
LIOLX M, AM,
X KL,
X
fv
Bo - 0.
k
k
Finally, by Lemma G.5 (2) of 13 the conclusion follows.
B Proofs of results in Section
B.1 Proof of Theorem 3
We consider two cases.
22

---

(I) \1. > O.
We begin to prove for the full ensemble when M = For j 1,2 and 1ú Iky, define
Σ, = X L X nn and M, = (X X/ + Az Recall that = X + fvL and
(
x
x L
k,,000 = Riindt
x LI
+ 15
kj
-Ii MM + m M Li, / fxL-
Then, for IR with bounded le norm, we have
a (Bx 3/ 300%
a (IES,TT [M MiEi] 1n MM 12
TI + a T (EIjnIN, X Ln,1/K - EianIe, [M2X] Lil/ha))
(21)
Next, we analyze the three terms separately. For the first term, from Lemma D. we have for Xg 0.
Bi Big [M E, = Ip Bri M2 = I, (p (w(--);
I,)
where v( - 1hy) is as defined in 440) By Lemma C.I we have that for & E (o), x)] there exists
segment P such that for all (A1, 11). (A2, 1/22 E P. it holds that u v(- t/ = v { 22 as p/ki + 1 and p/k2 + t2. By the definition of deterministic equivalents (Definition E. E.I. follows that
Ti tr(B0a EA,sT, E tr tr/S EIg [M
a.s. lim tr(B0aa (Ip (u(->r;:))E++1 80000
triB (Ip (u(-)2:
For the second term, notice that by Lemma
D.2
1 a
-aMMX
Mj
Lrn a kj
ZZEZ"
kj >,4p)
SN.. "i,
ki
From Lemma G.5 (2) of 13 it follows that
E, Tr [MjX] Lr,1/kzfm.
ax 0,
= 1,2,
and T2 - 0.
Combining the above results and applying triangle inequality
2 yields that
la (Bh) 3/ S [Ti [Tg
a.S. O,
which completes the proof when M oc. When M e N, replacing the above expectation by the average over M simple random samples I1, In Iş completes the proof.
(2) d1 = 0.
When 0 = 22 = 0, is trivially true as k = kg- Otherwise, without loss of generality, we assume \ 0 and A O. We use the same decomposition (2) and first analyze Ti. From part one we have that for 0, PA,A- Un. nsN, where
PAL = triBua En Ie, [(X L1 /k1 + XI,) E1I. +
Qa,A = =
triB T (I, (u(- -x: U4 E + Ip) }].
We next show that
lim lim PAA lim lim PA, 0,
(22)
00 X-0 2 n-+00
23

---

by proving that the function PA,x is equicontinuous family in X over A = [0, Amax] for any Xmax (0, oo) fixed. Note that for all A,
A S Bri 11(x Lr, X X/ki + M1) A Eillop]1Bsa 1ltr S 1|,3012
and its derivative
0 0x
BlinIs, [tr[(X Lt, X /k1 - E |1|
PA.A
BliNIe, [ll(X T L,, X X/ki k1 + A " 1Ilopp1] 1|+
- 11
are uniformly bounded in A almost surely. In the above inequalities, the operator norm is
bounded because 1I Lr, X /ki X1)--11 lopp S 8//(s: + A) and [| Lr
X
//i
XIp) -2 "Eillop llpp S s;/(8; + 2)2 I 1/(s; + A) Σ 1, by noting that lim sup [> 1lap
lim sup maxisisp 57 S Tmax (1 + v1) and lim inf |
limint min Sisp S
Tmin (1 - v11) almost surely KI,P
and p/k1
th E (0, (0, \ {1) 45
On
the other hand, since Qn,a is continuous function of v( - v1), we have
1n.a1 1 |100-11; 12 (E( -1500-111)))111 pp) 11lpp 11 l1e S 113 ||
θ 0x
² dul - 111
tr (o(-A;o11)0 1 1p)
n.N
ax
θv( @v((>;011) ax
- ||Bba 1lop
(1 u1+ dHp(r)).
When v/ > 1, (b; 1/Ox is bounded over 10Qu,2001 /ax is also bounded almost surely. When wh from Lemma E. of [ have
13 Lemma E. 10 and Lemma 11] and thus
Ov( foo(-x;3h) x1)
/
r
-v(-A; x; e))
r (1+ (r)r)) dHl(r)
(1+0(-Ari)))) dHp(r)
0X
OX
(1+ A; d: dHp(r)
4/1
(1- (H,(r)
01 A; 41)3
1/11
since r(- p(->; 1h1 < v00; vh))= +00. Therefore, |aQn,>/80 is uniformly bounded over for d (0, \ (1}. Thus, by the Moore-Osgood theorem, the convergence is uniform in À and 22 follows. Finally, since T2 bounded analogously as in Part (1), the equivalence holds when
O.
B.2
Proof of Proposition
From Lemma
B.2
it follows that
- -r (1xXT + X1 xx, )
1
v(->; Φn)
(23)
n
By the continuity of function o + v(->: x) from Lemma F.10 and E.11 of 13, we have v( (n) = vf x)) as on = p/n n - の. From Lemma C.1 there exists In such that
v.. v( u Φn),
as th - t and oin Φ. Involving 23 on the both sides yields that
1 ir x + Antp)
[ (HXX,, xT)
"
MK Σ
n
where {41...., Iar) is a simple random sample from Ig.
24

---

B.3 Proof of Corollary 5
We will use a structural equivalence (much more direct than the first-order equivalence considered in the paper) between generalized ridge predictor and the isotropic ridge predictor to prove the result. The generalized ridge predictor
(9), trained the subsampled dataset D,, can be expressed as:
(D)) (000)=(xx'')) x X Liy
k
Observe that we can equivalently manipulate the generalized ridge estimator into:
(D)) G- 1/2 X L, L,X + ~I,) G G-1/2 X Lry
Recalling from Assumption 2 that X 1/ where Z E RuXP contains 2, in the i-th row for i E [n], obtain
3 G (Di) G-1/2 ( 1/-1/2211 1/2 z L, 2 22
G-1/251/227 Lry (24)
We now define EG G G /G 1/2 and consider transformed feature matrix XG 2
Denote the transformed dataset corresponding to the new feature matrix by DC (where we keep the response vector as is). Using (24), we can write relate the generalized ridge estimator fitted on the dataset D to the standard ridge estimator fitted on the data DG (both at the same scalar regularization level A) by:
= -G'"
Observe that the transformed dataset DG satisfies Assumption as the eigenvalues of G are bounded away from 0 and co. Further, note that both Theorem [T and Theorem transformations of the estimator. Thus, we conclude that the results of both the theorems continue to hold. The equivalence path now use the modified Eg. which in turn changes the spectral distribution Hp to that of Eg, in defining the end points via (4 given by:
invariant linear
H, Σ (65h)
where F; for i E [p] are eigenvalues of Eg. This completes the proof.
B.4 Technical lemmas
Lemma B.1 (Relationship between m and 1). For X Roxp and on p/n, define
(1; )n) tr (
| )
1
- - =1p )
p x -0-1/
and 0(z;6n)
n
It holds that
2n Φn) + On - = =0(2; 2x).
(25)
Proof. Let r be the rank of the matrix X. Denote by 8;, 1,..., 7, the non-zero eigenvalues of the matrix X X. Note that these are the same non-zero eigenvalues of the matrix XX function S such that for # 0,
Define
5(2)
i=1
For * 0, write out ē and m in terms of S(z) as:
r
n
((2;)n)
S(z)
T1
11.
11
71
i=1
25

---

m(2; )n))
Σ
1
1p-r -r
-S(2)
1
1 1p-r -
p
8:
P
P
p
1=1
We now expand the left-hand side of
25
2m 0n) + On -
-
P
-
(2)
1p-r 1
+
P
71
-=((;)
p
P
n
n
11
1
=2((2)
r
r
11
11
71
n
11
P
P
=20(2; on)
+
+
n
20(2; on):
which finishes the proof.
Lemma B.2 (Equivalence of 1 and v). Suppose Assumptions 72 hold. Then it holds that
1 tr (+xx* +1pp)
v on) ~
Proof. From Lemma B.I we have
20(2 (1- (lo)) 2n Øn).
Substituting À yields that
- tr (=xx + +2lp)
-17
+ (Øn - 1) = s ( xx,x) -17
(26)
From Corollary E.4 we have
X - 11/0
v(->;
n (2xTX+M1,) + No, -
1 Atr
p
p
This implies
Xe((->; >x (hm) + t tr|u xx
1p)
= -vv(-A >x )n) + on on tr((u(( - >1 on) 12+ + 11)=1)//
1 _ x + N1p
-17
Xu(- X5 chn. + on Andir
/1
12
1 Atr ( +N
=1 x=(-->;;)))
n
where the last equality follows from 26 This concludes the proof.
C Proof of results in Section
C.1 Proof of Theorem
6
By Assumptions 3 for A = 1/22 and 0. R2 v) defined in converges to
R,(1; 1)) ب -= - =: 20()
(27)
26

---

where the nonnegative constants o( and o0 0(->; 2b) are defined through the following equations:
Φ f
y²
(1 + v( - x; b))) dH
8(-1:0,0)-
/
v(->; 15) -2 -
(1+ ((>;; ( dr
0(-1; 10) = (0( -0:0--;;000 d; 18) +1)
1+u(->;w) dG(r),
1 = + / x(-;;a)r dH(r).
v( A: 1))
From the proof of Theorem we also have that 8 o v) = Rp (p(A) = R(3) E, 0.)).
Since (0; Φ, 1b) is a continuous function of & and v(0; v/) and is increasing in & for any fixed v/, follows that for 0 Φ1 62 < 00,
min { 01 +)) #2Φ1
min L0 01 1p) 02
min A (0; 22, #2
where the first inequality follows because {v: 2 Φ1) 2 {+: v N Φ2). and the second inequality
follows because (0; Φ, 1)) is increasing in for a fixed v. Thus, min Al (0; Φ, v/) is a continuous and monotonically increasing function in ø.
Finally, note that from Lemma C.1 for any A, there exists & such that v0; 0, v) v(-); This implies that L Φ, +)- = (,; Φ). Then we have ming20 (0; Φb 1h) S minx2o ((; Φ).
Conversely, since for any ti there exists such that v(0: Φ, v) = =(->; d. Φ). we also have ming2a (0; o vb) 2 minAzo 2 (); o, Φ). Combining the two inequalities yields the conclusion.
C.2 Technical lemmas
In this section, we gather results on certain analytic properties of the fixed-point solution vi( v(-A; s) defined in (40).
Lemma C.1 (Contour of fixed-point solutions). As n.p - oc such that p/n + & E (0, co), for any T E (0. too], there exists a unique value X ' 0 (or conversely for E [0, oo), there exists a unique value & E [o V. v,)o)) sol) such that for all (x, xb) on the path
0 E [0. p {[1 0) (A, Φ) + (0,
it holds that
-(- x) v(-0;))
where up( ->)-- 1b) is as defined in (40)
Proof. Since when o < 1, v00; = +oo for all & (ob 1]. we can restrict ourselves to te E (e V 1, +oo]. From Lemma E.11 (1) of [3), the function vp + v(0; vb) is strictly decreasing over s E ( V 1, oa] with range
[0(0; Φ).
E (1, oc) @ E (0,
v0 / v 1) =
u(0; +00;+))==0 = lim +oo
v(O; v)) = 0.
lim (b) = t00,
From Lemma E.12 (3) of [13 the function A - v(->: Φ) is strictly decreasing over À E [0, oo] with range
Su(0; Φ))
E (1, oo) e (0, 1]
v(0; Φ)
x(-00;)) = lim v(->; x) = 0. x++
[lims-so+ o(->; x) t00,
Note that v00; C =(; Ø). For v E (6 v 1, x3. by the intermediate value theorem, there exists unique À [0, oc] such that v Ø) v00 () Furthermore, when & < 1, A = is also the unique
27

---

value such that v00; = v v(-x: Conversely, for Ā E [0, oo], there also exists के E 1 V 1, oo] such that u( u(-x; の) = v10; v)).
Based the definition of fixed-point solutions, it follows that
1 =X+ 0// o
dHp(r) = 1
1+0(-x; Ø)r dH,(r) = /0/ 1+ v(0; vrr
(-):
v(0; v)
Then, for any (A, 1/) = - (A, 6) + +(00, 3) on the path P, we have
1
1
v( o(-1;)) = -0) 0)
((-x;0) v(0: w))
= (1 0)X + (1 -1-0) 0)
1 1+o(->;0)r dHp(r) + -0
1 (0; d
=x+ /
+ Ø)- (H,
Because up(->: 16) is the unique solution to the fixed-point equation:
:p(->: = - x / (+ dHp(r))
r
then follows that 0p(- u(-x; v(0: ().
D Asymptotic equivalents, concentration results, and other useful lemmas
D.1 Full-ensemble resolvents
Lemma D.1 (Full-ensemble resolvents). Let -
where I ~ Ik- and C IRPxP with bounded operator norm almost surely. As
Let Eir = X L,, n. n.p,k 0c, p/n + Φ. p/k 4, the following asymptotic equivalences hold:
(1) Basic ridge resolvent:
XE II [ A1p) -1
1,)
(2) Bias resolvent with C 11 X:
En (12 + x1p) - 11
= (ca(->;v)E= + (G6-AAA
(3) Variance resolvent with C X:
(E) + A(,) ' Eine EB +1,) C
BIgbsI
~ (b)
EE
(4) Bias resolvent with C = Σ:
EI 1² - -5,
~()-> (() I,)) -
Here v(->; Φ) is defined in and we let (-x: -x;0, dh E)
lim e tr tr((CE
E + I,) 9110
op(->;0,,h C)
k,n
<p(->; {; -2 $ /
1²
(1 up (- - w))) dH,(r)
28

---

5.( b-(-;:
upl op(->;;0)= -2 20/ /
p
dHp(r)
(1 -p(->: w)rr
d(->: 0, (1-0
upl up(-1;16rr (+ dH
The empirical distribution H, eigenvalues can be replaced by the limiting distribution H whenever it exists.
Proof. The proofs for different parts is separated below.
(1) Basic ridge resolvent.
From Definition E.2
we know that A(E, p = x=)(>:))=+I)>) By the definition
of deterministic equivalents in Definition E.1 for any A E RPxp that has bounded trace norm and independent to X, we have
tr (A(E +XI)) 1::0111-ppp-000000000-- (1p((>;;))))
[)) - 0.
From Lemma G.5 (2) of it follows that
tr (r|A(AE; I [E, + -1p)
1p)
R, [tr[[tr|[| (A((E) + - A; +5) + [1)] - 0,
(28)
which implies that
XE ([i + x1p) - +1)
(2) Bias resolvent with C 1T X.
Denote M, = =EE + Ahp) for j = 1,2. From Part (c) of the proof for Lemma S.2.4 [12.
it follows that for /1, 12 Ip.
M2, = (vp(- x;; Σ Ip)
(7p(-> db v, C) + (v, (
By the same argument as in
28 the conclusion follows.
(3) Variance resolvent with C |l X.
From Lemma E.8 (3) of 13, it follows that for I, I2 Ik.
Mi M2 ~ u, o,
By the same argument as in 28 the conclusion follows.
(4) Bias resolvent with C' Σ.
We begin by decomposing the object inside expectation into two terms:
[1 U T2l X² &,,
U 12
X ÊMM
2 (122)-
(29)
n
where SS Siuz= X L,, X/ U T2] and E (1122= Next, we analyze each of them.
T (I Lnuiss T2)).
For the first term, from Lemma D.6 (3) of 13 have
Mi Siue M2 = uppp
(->; + 7n (->--,,,,)))
2( ②)
1 (30)
2 2サ )
2 Au (-p X; 1))
where d)) (-x th E)
For the second term, from Lemma E,8 (1) of 13 and the product rule of calculus in Lemma we have
X 2M E (102)- M2 ~ AMEMM
29

---

From Part (2) and Lemma E.3 it follows that
X² M, E (102) M2 X M, MM2 (1 + up( 1)) (Up (->: + I2)
(31)
Finally, for the coefficients of the two terms, from Lemma S.8.3 of 12]. we have that
I 1
[1
[2
I, 1
( Φ)
12
1 x)2
(32)
n
222
n
2/2
Combining
29
32
yields that
2 M, EM₂
- 6)
(oxu x; + 1 ) (1 (1477
212
= -11-0/
1+ dH2 ((
upl -
where the last equality follows by substituting
= =ー>(\>>))~--- 1b r -
based the fixed-point equation.
D.2 Convergence of random linear and quadratic forms
Lemma D.2 (Concentration of linear form with independent components and varying coefficients). Let z; E TRP for = 1,..., n be a sequence of random vectors with i.i.d. entries Zij. j = 1, ,, such that for each i, j. B[[a,] = 0, = = 1, B[] [4+a] S Mo for some a > and constant RExp be the random matrix formed by concatenating 0 and E[z,g(z,)) Let Op E R be a sequence of random vectors independent of zp such that lim supp ||ap|12/p S Mo almost surely for a constant Mo < co. Let D be a positive semidefinite matrix such that lim Dilopp S. Mo almost surely as p + oo for some constant Mo < co. Then, as n. p- co such that p/n Φ (0, oo), we have
Ma < Dc. Let Z = [z ...]
z; 'ss. Let g Rp
be any measurable function such that [[g(z:)]
for i I,...,
D z ZD + XI,
-1
T
z
g(2,)
u.s.
0.
(33)
Proof. We will use the standard leave-one-out trick to break the dependence between the i-th component multiplier in the summation (33) and g(2;) for each i 1...., To that end, using the Woodbury matrix identity, first observe that
D ZD! + +AI
11
D ZT.
Di D
+ MIp
Zl 2 D
+ AIp
30

---

D D
D 2iz; D
D = Z_
+ +1pp
+ Alp
(34)
D D 2I,I,_.DD
2 D
+ +XIp)
D
+
Plugging 34
back into
33
we expand the desired sum into:
D z
ZD
a
T
+ 21
D TT
g(zi)
Dà ZT ZD
-1
a
+ +Mpp
D)zi((z))
11
1 Σ
Da Z-;
a
+ tXp
D (2g((()))
11
D Z T, 1111Z_11 D
Dizzz D
D -,, +XI
+ +hpp
Dåzg((z))
D 2 2 2D D
im
z; D
+ XIp
Diz:
1 +
1
b dizig(z))
6 (zg(
(35)
1 + di
1=1
1
(1 d.)b! (;);
(36)
n
where in step
35 we denote by:
D ZT. 2,,
b, = D
+ +1Ip
D Z D' + +Ap
-1
2: D d:
D
n
π
and step (36 follows since d, 2 0. It is easy to check that lim sup, 11b.1//p S C < oo, and
d, C2 < co for some constants C1 and Cz. Appealing Lemma S.8.5 of [1] (36 almost
surely converges to O. This finishes the proof.
Lemma D.3 (Concentration of sum of quadratic forms with independent components and independent varying inner matrices). Let Zp IRP be a sequence of random vector with i.i.d. entries Zyo
1. 1...., P such that for each i, EE 2pd] O, [E = [B( S Mafor some 0 and constant Ma < oc. Lei Z [21,.... Zn T nux be the design matrix. Let g TRP - R be any measurable function such that [2);g(2,)] = O and [[g():)) 1. Let D be positive semidefinite matrix such that lim sup Dilop I My almost surely as p > oo for some constant Mo < oc. Then, as n. - oo
such that p/n + & E (0, oo).
1
Σ ISESJS
ZDZ
+ AIn
a(zi)g(z;)
2s, O.
(37)
Proof. The strategy in the proof is express each the ij-the entry of the resolvent in such that the dependence on (zi, 2z)) and the rest of (#t : # i, is separated. One is then able use the
31

---

uncorrelatedness of = and g(²) along with standard concentration of a quadratic form with respect to an independent matrix. Similar strategy has been used in [14] when analyzing kernel ridge regression under proportional asymptotics.
Denote Y (ZDZ*/ /n+ ) -1 For each pair of E [n] and i * J. we let Z- (1j) E (2xxp))xp be the matrix comprising the n 2 rows of Z excluding the ith and jth rows, and U E R be the matrix with columns Uije; = Zi, Uej = Zj. We finally define the matrices R. R2) RPxP as follows:
Rw) = 1D 1/2 zI
D (0) Z- (1))
DV2////////// (1)) AI,) > D1/2,
and let Yo = [Ym.tmm.ett...... mm. be the submatrix Y. Then, using the block matrix inversion formula (see, e.g., Appendix A.1.4 of (45) and the Woodbury matrix identity, one can show that
Y (U.j R (1)) U2/ + AI))
Yu = (zs. (1)) (1) /n
dij
where di is given by:
dy= = (A (2 R (1))2)) /n) (A+ (2,, (()))))) /n) - (2 R (1))))))) " /n².
Since 2is Zj. and R-())) are mutually independent, by Lemma S.8.5 of [51] we have
(zi, R)))))))) /n - 0 and the denominator concentrates on X², By Lemma G.5 (1) of [3]
it follows that max dij is, X² Thus, there exists No N such that for all n 2 No. maxigişján dij= 2 X² /2 almost surely. Then, it follows that for n 2 No.
Σ
Yyg(Z))9(z)
S
2 1
Σ
1z, R R(w))))) ((2))((2))
X2 n²
p ISiSiSn
19tiSn
Σ (zig(zi))
R (1))
X n²
igitinn
0,
where the last convergence is from Lemma S.8.5 of 51 and Lemma G.5 (2) of [3. Lemma D.4. For any two conforming matrices A and B and any + 0, we have
A BA- 1A-1-(AA
- (A+ 1A+tBi tB) 1/t + tA B A + tB) 'A
Proof. We recall the Woodbury matrix identity:
(A+UCV) UCVV-V-- A-1 A-- VA -VA')------
This holds for any conforming matrices A, U, C, and V. We will need to apply the Woodbury matrix identity twice below.
1. Applying the Woodbury identity for the first time with A A,U = 1, B, and V 1, we get
(A+ = A 1
1A 1 B
1- A-
Rearranging, this yields
(A-1-(AA /)/t A B tA -1---------
1 A 1 '(A 1 ---1 (38)
2. Applying the Woodbury identity the second time with A UB, A, and V 1 we get
- -
Multiplying by tB from the left yields
+B(A+tB)* = - - B - 1 B-
Now, multiplying by B on the right, notice that
tB (A++BB)* B B (tA 1 + B
(39)
32

---

From
38
observe that
A BA -A-1
11 A-
=A-
Using 39
we then have
BA
(A+1B) (B
LA
BA
BA-
Rearranging, we arrive at the desired equality:
A A (A (A
BA- BA-
D.3
Concentration of energy of linear and nonlinear components
Lemma D.5. Under Assumptions 7 2 the best linear estimator 3o and the nonlinear component fxt as defined (10) satisfies that |30 2 and [l Lets are bounded almost surely.
| we have Ely? S B S C2/((+66) for
Proof. By Jensen's inequality and Assumption some constant Co > O.
which implies that E[ [1 and Il 112,2 is bounded. Since by Assumption 2 the cigenvalues of Σ is lower bounded by Tmin 0.
By the orthogonality, we have that E E x Ba) + fl 11
we have that (xx Bb) Bo 3 2 Ymin || l1 and thus |1/3o||2 is bounded.
Since fuL- = y - x G.. by triangle inequality we have that
JNalleats S Ilvllza- + || Bollceto
Elyllla-, C11Bool12)
for some constant C' > 0. The second inequality of the above display is from Lemma 7.8 of 57 Since llyll and |/1l bounded, it follows that [| is also bounded.
E
Asymptotic equivalents: background and known results
Preliminary background. several proofs, we employ the concept of asymptotic equivalence of sequences of random matrices; 112
44 49 51). This section provides brief overview of the
associated terminology and calculus principles.
Definition E.1 (Asymptotic equivalence). Consider sequences { {Ap)p21 and (Bplp21 of (random or deterministic) matrices of growing dimensions. We say that A, and B, are equivalent and write A, Bp if limp- Ar(C,(A, Bp)ll = 0 almost surely for every sequence of random matrices C independent to A, and p. with bounded trace norm such that lim linsupp--s ||Cpller < almost surely.
The notion of asymptotic equivalence of two sequences of random matrices above can be further extended to incorporate conditioning on another sequence of random matrices; see [12] for more details.
Definition E.2 (Conditional asymptotic equivalence). Consider sequences {Aplp2ı (Bp1p21 and (Dp)p21 of (random or deterministic) matrices of growing dimensions. We say that A, and B, are equivalent given D, and write Ap ~ B, D, if lomppoo tr(C -B)]] = 0 almost surely conditional D Dplp21, Le.,
P lim (A, B,)]l = (Dph22)) =1
=1,
for any sequence of random matrices Cp independent to Ap and B, conditional on Dp, with bounded trace norm such that lim sup ||Cpller <
Below we summarize the calculus rules for conditional asymptotic equivalence in Definition These are adapted from Lemma S.7.4 and S.7.6 of [1].
33

---

Lemma E.3 (Calculus of asymptotic equivalents), Let Ap. Bp. Cp and Dy be sequences of random matrices. The calculus of asymptotic equivalents satisfies the following properties:
(1) Equivalence: The relation = is an equivalence relation.
(2) Sum If Ap = Bp Eg and Cp = Dp Eg. then Ap cp Dp Exp
(3) Product: If Ap has bounded operator norms such that lim sup || < 00, Ap is conditional independent to Bp and Cp given Ep for p 2 1, and B, = Cp Eg, then B, Cp pp Ey
(4) Trace: If Ap ~ Bp Ep. then tr tr(Ap//p tr tr/Bpl/p + almost surely when conditioning on Ep.
(5) Differentiation: Suppose f(z, Ap) Bp), Ep where the entries of f and g are analytic functions in = E S and S is an open connected subset of C. Suppose for any sequence C of deterministic matrices with bounded trace norm we have tr]C,([(z, Ap) 9(z, BB))]] M for every p and E S. Then, we have fl Ap) g' Bp) Ep every 2 E S, where the derivatives are taken entrywise with respect to
(6) Unconditioning: If Ap Bp Ep. then Ap Bp.
(7) Substitution: Let v R + R and f(u(C), C): RPxp R2 be matrix function for matrix E RPxP and p E N, that continuous in the first augment with respect to operator norm. If eCC) vDD) such that C is independent to D, then f(u(C), = f(v(D), C) C.
Standard ridge resolvents and various extensions. In this section, collect various asymptotic equivalents. The following corollary is a simple consequence of Theorem in [58] It provides deterministic equivalent for the scaled ridge resolvent.
Corollary E.4 (Deterministic equivalent for scaled ridge resolvent). Suppose æ, ER,,
are i..dd random vectors such that each x;; = z; 11/2 where z; is a random vector consisting of i.i.d. entries Zij, 1 S j S p, satisfying E[ 0. E E[ and Ma oc, and Σ E PR is a positive semidefinite matrix satisfying 3 3 Tmaxx for some constant Tmax < 30 (independent of p). Let X E Raxp the concatenated matrix with x! 1 I i S n. as rows, and let E E RPXP denote the random matrix X X/nn Let = p/n. Then, for such that 0 < lim inf llim 7 < cc, and X > 0, we have
1, and [E|[= (8t]88 S Ma for some constants
E C+ n.
X + XI,)~ (o(->xn)) + I 1,)
where u->x;7) > 0 is the unique solution to the fxxed-point equation
(--):)) - / 1+x(->;7) dH,(r).
(40)
Here Hy is the empirical distribution (supported on RRz0) of the eigenvalues of
Side remark: The parameter 7(-);7) in Corollary E.4 is also the companion Stieltjes transform of the spectral distribution of the sample covariance matrix Σ. is also the Stieltjes transform of the spectral distribution of the gram matrix XX /n. This is essentially the characterization we use in proving Proposition
The following lemma uses Corollary E.4 along with calculus of deterministic equivalents (from Lemma
3.3 and provides deterministic equivalents for resolvents needed obtain asymptotic bias and variance of standard ridge regression. is adapted from Lemma S.6. 10 of [51]
Lemma E.5 (Deterministic equivalents for ridge resolvents associated with generalized bias and variance). Suppose a; E TR?,, < i < are i.i.d. random vectors with each a; z; 1/2 where 2; E TRP is a random vector that contains i...d. random variables Zij, 1 j S p. each with R[ E[2 I, and [E[ [++]] < Ma for some constants a and Ma 00, and Σ Px is positive semidefinite matrix with T Tmin Ip I Σ 3 Tmaxx f for some constants Tmin > 0 and r max < co (independent of p). Let X E RRx be the concatenated random matrix with D; S i S n, as
x/nnn RRxxY Let 7 = p/n. Then, for X > 0, as n. p - oc with 0 < lim inf r lim supsup y the following statements hold:
its rows, and define E X
34

---

(1) Bias of ridge regression:
A1p)
E. 11) (10 AAE + A)(o(-Ai E)E 1p)
(2) Variance of ridge regression:
(1,) 'EA i. E)(((-X ,)) ΣAA
Here v0 ( E) is the unique solution to the fxxedpooie equation
7/
w 7 A
dH,(r; E),
(41)
u E)r
and 76(-6 b, ) and T. (-x;7 ) are defined through vi - Σ) by the following equations:
7 7tr AEr[AAE( (u( ->; Σ)Σ + 1,) 3/p
To(->; A)
(42)
v(->;77 Σ)
71 + 1 (->;7 E)r) -2 (H, E)
(- - Σ) /n221 + -->;7, D)r) d (r: Σ);
(43)
where H; Σ) is the empirical distribution (supported on Tmin: mmax) of the eigenvalues of Σ.
Though Lemma E.5 states the dependency explicitly, we will simply write Hr(r), o(->; X; -x;7) 7- A), and Un - 7) to denote (r; D), u E) 7 Σ, A), and (->; E). respectively, for simplifying various notations when clear from the context. When A Σ, simply write 7) u6(->;
F
Experiment details
F.1
Reproducibility and compute details
The source code for generating all of our figures is included with the supplementary material. The source code also includes details about the computational resources used to run the code and other timing details.
F22 Simulation details
The covariance matrix of an auto-regressive process of order 1 (AR(1)) given by Eari. where (Ean)) ); = Par ドーン! for some parameter Part E (0, 1). Define fo := ΣS j== W() where W() is the eigenvector of Ear associated with the top jth eigenvalue r()). We generated data (æ,, Vi) for i I...., from a nonlinear model:
sid ts Zij
ta 05
x. Bo + (1|= tr(Eari)) + Eii 2;
Σ
Ari
El
(M-ARI)
05
5/3 the standard deviation of is distribution. The benefit of using the above nonlinear model is that we can clearly separate the linear and the nonlinear components and compute the quantities of interest because B0 happens to be the best linear projection.
where o5
For the simulations, we set Parl = 0.5. For finite ensembles, the risks are averaged across 50 simulations.
35

---

F.3 Risk comparisons along equivalence paths for finite ensembles
Figure F5 verifies the following linear (in M) relationship along the path in Theorem 3 for finite ensembles: R of M), which is eventually almost surely bounded.
Ip/é: I.Mi A, b, (90) - R 1p/v/ L.Mi A, (,) = A/M, for some A (independent
Estimation risk
Training error
Prediction risk
Prediction risk (OOD)
10c
100
10a
Range
10
10-1
10 -1
10-1
10
100
1
100 1 10 100
10 100
Ensemble size M
Figure F5: The range (the difference between the maximum and the maximum along the path) of the finite-sample generalized risk of Mennemble ridge estimators on the path through (X, 1) = (0, 2). for varying ensemble size M under the same setting in Figure [ The generalized risks include the estimation risk, the training error, the prediction risk, and the out-of-distribution (OOD) prediction
risk.
F44 Illustration risk monotonicity of optimal ridge
0.1
Incrcasing
aspect ratio
1.5
1.4
1.3
1.2
-.2
1.1
10
1 Subsample aspect ratio y
10
0.3
10
Ridge penalty A
Figure F6: Illustration of risk monotonicity of optimal subsampled ridgeless regression versus optimal regularized ridge regression. The underlying model has a non-isotropic covariance as described in Appendix F22 with linearized signal-to-noise ratio of 0.6 and [ I 1. This results in null risk 1.6, which is kept the same across all regression problems. The left panel shows the limiting risk of the full-ensemble ridgeless regression various data and subsample aspect ratios (ő, v). The right panel shows the limiting risk the ridge predictor (on the full data) at various data aspect ratios and regularization penalties (Φ, A). Optimal risks for each data aspect ratio highlighted using slender red lines in both panels. Observe that the optimal risk in both cases is increasing as a function of éb In the left panel, in addition, for every subsample aspect ratio vú, the risk of subsampled ridgeless is increasing in the data aspect ratio σ. This turn implies the risk monotonicity claim for the optimal ridge regression in Theorem Ghthough slick triangle inequality argument (see the proof in Appendix C for more details).
F.5 Real-world datasets
We conduct experiments on real-world datasets to examine the equivalence in more general setting. We utilized three image datasets for our experimental analysis: CIFAR 10, MNIST, and USPS [59]. For the CIFAR 10 dataset, we subset the images labeled as "dog" and "cat". For other datasets, we subset the images labeled "3" and "8". Then we treat them as binary labels y E (0, 1} and use flattened image as our feature vector æ. The training sample sizes, the feature dimensions, and the test sample sizes (n, p, Nhe) are (10000, 3072, 2000), (12873, 784, 2145), and (22358, 3072, 7981) for the three datasets, respectively.
36

---

For the first experiment in Figure we fix Φ p/n and きे- 4 using the training set of CIFAR- 10. For A3 E {0.01, 0.05, 0.1,1}, 1), we compute the data-dependent value of Ī based on Proposition Each value of > gives path between (Ag (b) and (A. Φ).
For the second experiment in Figure F7 by varying the values of subsample aspect ratios v, we compare the random Gaussian linear projection of the estimators and the prediction risk at the two endpoints (A, Φ) and (0, 1) on CIFAR-I0, MNIST, and USPS datasets.
Dataset
CIFAR10 Random line ar projection
MNIST
USPS
Model
(A,
(0.
Prediction
0.02
1.0
Value
0.8
0.00
2
10
2
8 10
Subsample aspect ratio
Subsample aspect w
Figure F7: The functional equivalences of subsampling and ridge regularization on different datasets. For each dataset with aspect ratio 6 = p/n and each value of 3. the corresponding ridge penalty estimated by Proposition 4 The two models with ridge penalty and subsample aspect ratio (A, o) and (0, ( are compared. Note that the model corresponding (7, Φ) ridge regression ridge penalty without subsampling, and the model corresponding to (0, v)) is full-ensemble ridgeless at subsample aspect ratio T.
F.6 Random features model
The data (z,,y) is generate from the nonlinear model
1 - (1<2a112 p) + Ess
y: = x. Bo + p
where Zig sid (O, 1), and E, ~ NO 1). The prediction risk of the ridge ensemble (M 100) computed based on the random feature (FFx;) and the response ys. where F Ø is the random weight matrix with Fej sid V(0,p-1). Here, yp is nonlinear activation function (sigmoid, ReLU, or tanh) that is applied entry-wise to Fæ, For the experiment, we set p 250, d = 500, and d/n- 0.1.
E.7 Kernel ridge regression
For a given feature map +b :R + Rd, the kernel ridge estimator is defined as:
+ k =11l112.
(D1) argmin Σ (k-1//y 11/2 Tx) + A|s Σ (3: - (xx,)
BERP
p
By using the kernel trick, the above optimization problem equivalent to solving:
(Dr) = argmin a T (Ki + kAIx) a TTy. yr.
RER
where K, / 1xk is the kernel matrix and 4; (I(æ;))ier Ruxd is the feature matrix. Simple calculation shows that (A = + (Dr).
Using the same data-gener dattaggenrrttig process as in the previous subsection, the results on kernel ridge regression are illustrated in Figure F8
37

---

Polynomial
Gaussian
Laplacian
0.0
Ridge penalty
10
114
Subsample aspect ratio
Figure F8: Heat map of the empirical distribution prediction risk of full-ensemble kernel ridge estimators, for varying ridge penalties À and subsample aspect ratio &े = p/d on the log-log scale. The prediction risk of the ridge ensemble (M 100) is computed using polynomial, Gaussian, and Laplacian kernel, using the default parameters as in Python package scikit-lean v1.2.2 [60] without the intercept terms. We scale À by k/p that obtain non-null estimators for the polynomial inner- meer-product kernel (of degree 3).
38


Reviews:
[{"review_id": "LB2kECzGbw", "reviewer": "Reviewer_DNS5", "summary": "This work compares the ridgeless ensemble and the ridge estimators in the proportional limit setting (i.e., $d/n\\to \\phi$). Prior works [11,12,13] show that these two estimators achieve the same out-of-sample risk. The main contribution of this paper has been to (1) weaken the assumptions and (2) broaden the equivalence from out-of-sample risk to other risks such as empirical risk, in-sample risk, and transfer learning risk. Based on this theory, this work also shows that the out-of-sample risk achieved by the optimal ridge estimator monotonically increases as a function of the data aspect ratio (i.e., $\\phi$).\n\n", "questions": "Upto my quick glance, it seems the proof methods are largely built upon existing works such as [12] and [13]. I understand that this work has derived broader equivalence results under weaker assumptions compared to [11,12,13]. Would you please clarify what are the new ingredients in this work that allow so?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ Excellent presentation. I have enjoyed going through the paper. \n+ Compared to [11,12,13], this work has shown equivalence between ridgeless ensemble and ridge estimators in a broader sense and under weaker assumptions. Notably, in this work, the data is allowed to be misspecified and the limiting covariance spectrum needs not to exist, and the proved equivalence holds for transfer learning risk, in-sample risk, empirical risk beside out-of-sample risk.\n+ Section 5 is a neat addition to the main results, showing that the optimal ridge induces an out-of-sample risk increasing with respect to the data aspect ratio. \n\n", "weaknesses": "- The Conjecture 1 in [1] is stated for every finite $n$ and $p$. Section 5 in this work only applies to the proportional limit setting, where $p/n\\to \\phi, n,p\\to\\infty$ for a finite $\\phi$. While I think Section 5 is very interesting, I am not sure it is proper to claim that \"This resolves a recent open problem raised by Nakkiran et al. [1] under general data distributions and mild regularity conditions.\"\n\n\n- The theory is limited to the proportional limit regime. To what extent the theory holds in the finite sample regime is unclear. \n\n\n- The technique novelty could be further clarified. \n\n- I tried to read the proof and believe they are mostly correct. However, there are a number of typos that confuse me (and prevent me from spending more time checking the proof). For an incomplete list:\n\n1. The equation after Line 514. Missing a factor of 2 in the cross-term. \n2. Line 520. $B = AX - I$, missing $-I$.\n3. Line 534. $v(- \\lambda_1; \\psi_1) = v(- \\lambda_2; \\psi_2)$. $\\lambda_2$ instead of $\\lambda_1$. \n4. The first inequality after Line 622. Left hand side of the inequality, $R(0; \\phi, \\psi)$ should be $R(0; \\phi_1, \\psi)$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Sincere thanks for the positive feedback, insightful comments, and the list of typos. \nWe are happy that you enjoyed reading our paper and appreciated the presentation (that we paid special attention to while writing the paper). \nTo echo your sentiment, results in Section 5 are also our favorite!\n\nBelow we will first provide our responses to the weaknesses raised (abbreviated by **[W]**).\n\n- **[Response to W1]** _(Finite-sample monotonicity of optimal ridge)_:\n    Thanks for the comment.\n    We agree that our claim regarding the resolution of the open problem (Conjecture 1) raised by Nakkiran et al. in [NVKM21] is perhaps overly broad. \n    Our results in Section 5 indeed apply in the proportional limit setting, where $p/n \\rightarrow \\phi$ for $\\phi \\in (0, \\infty)$ as $n, p \\rightarrow \\infty$.\n    We acknowledge that this does not cover every finite $n$ and $p$. \n    We will add the qualifier that the results in Section 5 resolves the conjecture in the proportional asymptotic sense. \nHowever, we expect that all the asymptotic statements in the paper can be converted to non-asymptotic statements with distributional assumptions on the feature and response distributions.\n    Please see our response to **[W2]** for more details.\n    In that sense, we expect that our Theorem 6 largely covers the meat of general monotonicity claim, though of course the finite-sample analogues are important also.\nWe will make sure to point it out.\n\n- **[Response to W2]** _(Non-asymptotic analogues of equivalences)_:\n    Thanks for the feedback.\n    Indeed, our current theoretical framework is primarily developed under the proportional limit regime.\n    This approach simplifies the proofs and allows us to focus on the essential characteristics of the problem.\n    Our empirical results, as shown in the Figures 3 in the paper, suggest that our results hold even for finite $n$ and $p$. \nThese empirical findings provide practical validation of our theoretical results beyond the proportional limit regime.\n    The extension of our results to the finite sample regime is possible, but requires additional assumptions.\n    The precise error bounds in the finite sample regime would depend on the specific nature of the distribution of features and response.\n    We expect techniques of [KY17], [CM22], [WHS22], among others, to provide non-asymptotic versions of the main statements in our paper.\n\n- **[Response to W3]** _(Clarification of novelties)_: We will briefly recall our novelties below, compared to previous related works:\n\n    - Generalized risk framework: \n    We consider a generalized risk framework that allows us to evaluate the performance of ensemble ridge estimators relative to the oracle parameter.\n    This is a significant departure from previous works that only focus on specific risk functionals.\n\n    - Structural equivalences: \n    We show structural equivalences in the form of linear functionals of the ensemble ridge estimators. This aspect is not explored in any of the previous papers.\n\n    - Data-dependent method for equivalent paths: \n    We provide a data-dependent method to determine the equivalent paths of $(\\lambda, \\phi)$. \n    We believe this is an important contribution as it allows us to apply our theoretical findings in practice. \n    \n    - Technical novelties: The new technical tools we develop allow us to relax the assumptions on features and responses.\n    See also response to **[Q1]** below for more details on technical novelties.\n\n- **[Response to W4]** _(Typos)_\n    Thanks so much for the list.\n    We have corrected these in our revision.\n\nNext we address the question (abbreviated by **[Q]**).\n\n- **[Response to Q1]** _(Clarification of technical novelties)_: While it is true that our work builds upon the foundations laid by previous studies, including [12] and [13], it is important to note that our contributions are not merely extensions of these works and requires several technical novelties. We elaborate below. \n\n   To derive the equivalence result under minimal assumption on the feature distribution and feature covariance, we use the notion of asymptotic equivalence to compare sequences of matrices of arbitrary dimensions. Using asymptotic equivalences and associated calculus (instead of computing the actual risks) lets us bypass the assumptions on features.\n\n   To accommodate any nonlinear dependence structure between $y$ and $\\mathbf{x}$, we generalize the linear and quadratic concentration results to allow for arbitrary models. In contrast, in all previous works, a well-specified linear model $y=\\mathbf{x}^{\\top}\\beta_0 + \\epsilon$ is assumed. At a high level, the proof of these results requires rank-2 perturbations of the ridge resolvents to separate out the dependent and independent parts, and exploiting the property of uncorrelation between the features and the nonlinear residuals (after projecting out the linear part). Please see Appendix D of the submitted paper for more details.\n\n**References**\n\n[NVKM21] Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. In International Conference on Learning Representations, 2021.\n\n[KY17] Antti Knowles and Jun Yin. Anisotropic local laws for random matrices. Probability Theory and Related Fields, 2017.\n\n[CM22] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv:2210.08571, 2022.\n\n[WHS22] Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning, 2022."}, {"review_id": "Z3HFwNQlUa", "reviewer": "Reviewer_wEHo", "summary": "This submission establishes equivalences between ridge regression (i.e. $\\ell_2$-penalized\nlinear regression) and ensembles of linear models trained on sub-sampled datasets.\nIn particular, the authors prove that for a fixed feature/sub-sample-size $d/k$, ratio, there \nexists a ridge-regression model with risk asymptotically equivalent to the full\nensemble, i.e. the average of all $k$ models trained on sub-samples of size $k$. \nMoreover, this equivalence holds for all convex combinations of the \nridge-regression and full sub-sampled model.\nNote that the asymptotics assume $d$, $k$, $n$ approach infinity such that\nthe ratios $d/k$ and $d/n$ are held constant.\nThis equivalence result is then extended to other metrics, such as training error\nand the weight estimation error, and to \"structural\" results which\nshow asymptotic equivalence of the weights of the models.\nThe authors leverage these equivalences to show that the prediction\nrisk of the best ridge regression model is monotone increasing in $d/n$. ", "questions": "Line 93: Is this supposed to mean that Assumption 2 defines RMT features? \n    It's not obvious because the acronym RMT is not defined anywhere and \n    not used in Assumption 2.\n\nLine 176: I suggest Changing the name of Assumption 2 from \"Feature Vector Distribution\" \n    to \"RMT\" features as well as including a definition for the initialism/acronym, since\n    it isn't stated anywhere.\n\nLine 156 and Definition E.1: Does $C_p$ need to be bounded away from zero? \n    Otherwise the asymptotic\n    equivalence definition will be meaningless when $C_p = 0$ almost surely \n    for every $p$. Or perhaps when you say \"any sequence $C_p$\" you mean\n    \"every sequence\"?\n\nLine 183: Shouldn't this solution be $(\\\\lambda, \\\\bar{\\\\psi})$?\n\nFigures 1/2: The paths between equivalent models don't appear to be linear \n    in these figures, although Equation 5 seems to indicate that they are always\n    linear combinations. Is this because the figures are in log-log scale?\n\nTheorem 3: I don't understand what is \"structural\" or \"first-order\" in this\n    theorem compared to Theorem 1. Is this because the estimators themselves\n    are equivalent, rather than a risk functional of the estimators?\n    While is equivalence of risk functionals \"second order\"?\n    \nTheorem 3: \"this implies that the predicted values (or even any continuous function\napplied to them due to the continuous mapping theorem) of any test point will eventually be the same,\nalmost surely, with respect to the training data.\"\n\nThe asymptotic equivalence of parameters in Theorem 3 and this \nstatement seem to imply that Theorem 3 covers both Theorem 1 and Proposition 2 \nby taking $M = \\\\infty$ --- is this correct?\nIf yes, what is the novelty of these two previous results given Theorem 3?\n\nProposition 4: Is Equation 8 always guaranteed to admit a solution?\n    Moreover, what is the utility of this result when the equivalence only\n    holds asymptotically? That is, when $n \\rightarrow \\infty$ and the\n    root-finding problem defined by Equation (8) is impractical to solve.", "limitations": "As mentioned in the \"Weaknesses\" section, I think the main limitation of this \nsubmission is the impracticality of the main theoretical results.\nSince they extend and generalize a previous result showing asymptotic equivalence\nof the risk, I do not see the theoretical derivations having an impact on practice.\nFurthermore, the connections to high-interest topics in ML like early stopping\nand dropout seem tenuous at best. \n\nSince I am not actively involved in learning theory research, I cannot\ncomment on the importance of this work for other members of this community.\nIt would be nice if the authors could provide additional context for their\nwork, including some comments on the novelty of their proof techniques and so\non. That way I can better understand the impact on this specific research community.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The main strength of this work is the theoretical contributions. In \nparticular:\n\n- The authors extend exist results on equivalent risk of ridge regression\n    models and sub-sampled ensembles to new metrics and to the model weights\n    themselves (\"structural results\").\n\n- The theorems are proved under relaxed conditions compared to previous work.\n    In particular, general data distributions are allowed provided a fairly\n    weak assumption on the moments holds.\n\n- The authors answer an open problem on the behavior of risk for ridge regression\n    models with the optimal regularization constant.\n\nThe paper is also well written, with very few typos. I congratulate the authors\non their polished manuscript. \nRelated work appears to be correctly cited, although this is not my research\narea so it is hard for me to check.\nNote that I did not check the theoretical derivations in the appendix so I\ncannot comment on their correctness.", "weaknesses": "The greatest weakness of this paper is that the theoretical results are\nsomewhat incremental and unlikely to have an impact outside of learning theory.\nIn particular,\n\n- The connection between ridge regression and sub-sampled ensembles was\n    previously established, so that the main contributions of this work \n    are weakened conditions and new types of equivalences.\n\n- It's not clear how interesting it is to answer the conjecture from \n    Nakkiran et al. While the authors prove that the risk for the ridge\n    regression model with optimal regularization constant is monotone\n    increasing in the ratio $d/n$, this only applies to the asymptotic\n    regime and so its practical importance may be limited.\n\n- While the authors motivate their work by highlighting connections between\n    ridge regularization and dropout, noisy training, data augmentation,\n    and early stopping. However, these connections are not developed any further\n    and I am skeptical the asymptotic equivalences in this submission will\n    impact those areas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the detailed constructive feedback! We appreciate the careful reading and questions.\n\nBelow we comment on the weaknesses within the allowed space.\n\n- **[W1]** While it is true that the connection between ridge regression and sub-sampled ensembles has been previously established, our work significantly extends this connection. Apart from generalizing results to hold general functionals, a key aspect of our results compared to prior work is that we do not assume any model for the response for any of these equivalences. We also establish structural equivalences, which were not studied in the prior works. This allows our theoretical results to be applicable to practical data analysis. Furthermore, our data-dependent method for determining equivalent paths is also another novel contribution, which we believe has practical implications as it allows one to determine the level of ``induced'' ridge regularization based on the available data. Please also see our response to **[Q1]** of reviewer **DNS5** for technical novelties and to **[W1]** of reviewer **nskG** for practical impact.\n- **[W2a]** Many common methods, such as ridgeless or lassoless regression, have been recently shown to exhibit non-monotonic behavior in the sample size or the limiting aspect ratio. In this regard, the conjecture from Nakkiran et al. is interesting because the non-monotonicity risk behavior implies that more data can hurt the performance, and it's important to investigate whether optimal ridge regression also suffers from this risk.\n- **[W2b]** The conjecture on the monotonicity of optimal ridge regression is of interest, even in the asymptotic regime. This is because the monotonicity/non-monotonicity is largely governed by the structure and relationship between the bias and variance at various regularization levels. Understanding the bias-variance tradeoff at the optimal regularization is not as affected by the finite-sample effects. Furthermore, as can seen empirically verified, even for $n$ and $p$ in the order of 100, one starts to observe the asymptotic behavior. The asymptotic approach simplifies the proofs and allows us to focus on the essential characteristics of the problem, under minimal assumptions. The extension of our results to the finite sample regime is possible but requires additional assumptions and depends on the specific nature of the distribution of features and response. See also response to **[W2]** of reviewer **DNS5** for more details.\n- **[W3]** Our mention of connections to dropout, noisy training, data augmentation, and early stopping was to highlight the broad relevance of our focus on ridge regularization and subsampling. While the direct application of our asymptotic equivalences to these areas is not immediately clear, we believe our work provides insights that could indirectly inform these areas and inspire future work. For instance, understanding the trade-offs between subsampling and ridge regularization could potentially inform more effective strategies for dropout or data augmentation.\n\nBelow we address the questions.\n\n- **[Q1]** We define these precisely in the discussion after Assumption 2. We will clarify this in the revision.\n- **[Q2]** We will make the names of the assumptions \"Moment-bounded response\" and \"RMT features\". We will also mention the acronyms explicitly when they first appear.\n- **[Q3]** The definition requires the convergence \"for every sequence $C_p$ that is uniformly bounde\".\n- **[Q4]** For (4), we fix $\\bar{\\psi}$ and try to determine the values of $\\bar{\\lambda}$ and $v$.\n    Here the tuple $(\\bar{\\lambda},v)$ is a solution to (4) when $\\bar{\\psi}$ is fixed.\n- **[Q5]** Yes, the figures are in the log-log scale, only for better illustration purposes. We mention this in both captions of the submitted paper.\n- **[Q6]** Yes, \"structural equivalence\" means that estimators themselves are equivalent, rather than a risk functional of the estimators. Theorem 3 states that ${\\mathbf c}^{\\top}(\\hat{\\mathbf{\\beta}}\\_1 - \\hat{\\mathbf\\beta}\\_2) \\xrightarrow{a.s.} 0$ for every constant vector ${\\mathbf c}$ with bounded norm. This is a linear functional of the difference, so we view this equivalence as a \"first-order\" result. On the contrary, Theorem 1 and Proposition 2 compare the distance between two estimators to the ground truth ${\\mathbf\\beta_0}$, i.e., $\\|\\|\\hat{\\mathbf\\beta}\\_1 - {\\mathbf\\beta_0}\\|\\|\\_{\\mathbf A}^2 - \\|\\|\\hat{\\mathbf\\beta}\\_2 - {\\mathbf\\beta_0}\\|\\|\\_{\\mathbf A}^2 \\xrightarrow{a.s.} 0$ where $\\mathbf A$ is a weight matrix. Hence the latter is in the \"second-order\" sense.\n- **[Q7]** Theorem 3 does not imply Theorem 1 and Proposition 2. When ${\\mathbf A} = {\\mathbf c}{\\mathbf c}^{\\top}$, the latter reduces to $({\\mathbf c}^{\\top}\\hat{\\mathbf\\beta}_1)^2 - ({\\mathbf c}^{\\top}\\hat{\\mathbf\\beta}_2)^2 \\xrightarrow{a.s.} 0$. But for general $\\mathbf A$, there is no direct relationship between the two. For instance, when $\\mathbf A=\\mathbf I_p$, each coordinate of $\\hat{\\mathbf\\beta}_1 - {\\mathbf\\beta_2}$ converges to zero almost surely, does not imply $\\|\\|\\hat{\\mathbf\\beta}_1 - {\\mathbf\\beta_0}\\|\\|_2^2 \\|\\|\\hat{\\mathbf\\beta}_2 - {\\mathbf\\beta_0}\\|\\|_2^2 = \\|\\|\\hat{\\mathbf\\beta}_1\\|\\|_2^2 - \\|\\|\\hat{\\mathbf\\beta}_2\\|\\|_2^2 +2{\\mathbf\\beta_0}^{\\top}(\\hat{\\mathbf\\beta}_1 - \\hat{\\mathbf\\beta_2})$ also converges to zero almost surely.\n- **[Q8]** Yes, (8) always has at least one solution. This is because the RHS of (8) is monotonically decreasing in $\\bar{\\lambda}_n$, and the LHS always lies within the range of the RHS. One can solve (8) for a given set of $n$ and $p$. Since for sufficiently large $n$ and $p$, the equivalence holds, we can solve (8) in finite samples. While it is true, the theorem statement at the moment does not say anything non-asymptotically, we expect that one can derive a high-probability statement that explicitly characterizes a high probability bound on the difference between the two asymptotically equivalent quantities."}, {"review_id": "rFjbz4IAst", "reviewer": "Reviewer_nskG", "summary": "The authors study the relationship between  ridgeless ensembles constructed from subsampled data and a ridge estimator in a setting with mild assumptions on the joint distribution $(Y,X)$.  They establish equivalences for a generalized class of risk functionals, which include quantities related to coefficient estimation and both in and out of sample errors. These equivalences are proven in the case where the ensemble includes estimators trained on all possible subsamples of a given size; the authors extend these results to equivalences between two finite ensembles. The authors use these equivalence results to settle a conjecture in a previous paper about risk monotonicity of ridge regression as a function of $p/n$.       \n", "questions": "- In Theorem 3, is the ensemble size $M$ fixed?\n- While the paper is well-written overall, some additional exposition/clarification in certain parts may be helpful to readers.  For example, the authors could elaborate more on what they mean by first-order and second-order.  In addition, the coefficient confidence interval case can be explained more.  Also, before theorem 3, it is stated that \"We can go a step further and ask if there exist any equivalences for the finite ensemble and if there are any equivalences at the estimator coordinate level between the estimators.\"  Do you mean that the conditions in this theorem have been previously shown to imply equivalences at the coordinate level and these conditions also imply equivalences with finite ensembles or do you mean something else?   \n", "limitations": "The authors are quite forthcoming about various limitations of their work and possible future extensions. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors substantially relax the distributional assumptions considered by previous work in the literature. This is conceptually important since it was not known how critical the linearity assumption is for these types of equivalences to hold. \n- The theoretical analysis is both novel and technical, invoking various concepts from random matrix theory.\n- Overall, the paper is well-written and well-organized.\n\n\n", "weaknesses": "While equivalences between ridge regression and subsampling are conceptually interesting, at this stage it appears that consequences for data analysis are a bit limited.  However, the authors generously discuss several potential extensions for which some of the tools developed in the paper may be helpful.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the encouraging comments and feedback!\nWe are glad to hear that you liked the relaxing of distributional assumptions, the novelty of theoretical analysis, and the clarity of presentation. In the sequel, we will first comment on the weaknesses raised and then address the questions.\n\nComments on weaknesses follow:\n\n- **[Response to W1]** _(Consequences for practical data analysis)_:  Thank you for the comment!\n    We acknowledge that the immediate practical application of our results may not be readily apparent, but the insights gained can inform practical data analysis.\n    Even though our paper primarily considers ridge regression, which may seem limited for real-world data analysis, it is good to note the close connections between ridge regularization and other forms of regularization methods, such as dropout regularization, noisy training, random sketched regression, among others, as mentioned in the related work. \nUnderstanding the relationship between subsampling and ridge may provide valuable insights into the behavior of subsampling and other implicit/explicit regularization methods. \nMoreover, our data-dependent characterization of this effect, as presented in Proposition 4, could potentially guide model selection involving other types of regularization for ensemble learning. This understanding could also potentially guide the selection of appropriate subsample sizes in practice.\n\n    Now it is true that the equivalence results are derived under certain assumptions on the features (RMT, in particular), we expect it to be true more generally.\n    For example, we really only need the concentration of the ridge resolvents.\n    Beyond RMT features, for the Marchenko-Pasture law to hold, which forms the backbone of of work, it is recently been shown (see [L22], [CM22], for example) that convex concentration suffices.\n    Thus we expect that the equivalences we establish in the paper to hold for a range of real data distributions.\n    For instance, as illustrated in Figure 3 of the paper, our equivalences seem to hold very well for real image datasets.\n   Formalizing precisely the extend to which these equivalences hold true is indeed on our list of future work! \n    \n\n- **[Response to Q1]** _(Ensemble size for structural equivalences)_: Yes, Theorem 3 on structural equivalence works for any ensemble size $M$.\n    We will stress this in the revised version.\n\n- **[Response to Q2]** _(Clarifications on the terminology)_: Thanks for the suggestions!\n    We appreciate the comment and agree that the paper will benefit from additional clarifications on the terminology.\n    \n    When we refer to first-order and second-order, we are referring to the order of the functional of the estimators. \n    First-order refers to the equivalence of linear functionals of the estimators.\n    Second-order, on the other hand, refers to the equivalence of quadratic functionals of the estimators. \n  \n    Regarding your question about the commentary before Theorem 3, we will clarify it better. \n    When we mention equivalences at the estimator ``coordinate'' level, we mean that each coordinate (of the $p$-dimensional vector of the estimators) asymptotically equals.\n    Such a type of equivalence on finite ensembles has not been studied in the previous works.\n    As summarized in Table 1, the previous related papers only show certain risk equivalences under restricted assumptions.\n\n**References**\n\n[L22] Cosme Louart. Sharp bounds for the concentration of the resolvent in convex concentration settings. arXiv:2201.00284, 2022.\n\n[CM22] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv:2210.08571, 2022."}, {"review_id": "CCYfZzmqM4", "reviewer": "Reviewer_MtFr", "summary": "This paper shows an asymptotic equivalence between an ensembled+subsampled (E+S) version of ridge regression and the standard version, in the proportional asymptotic regime. The equivalence result shows that there exists a linear path in the space (ridge-parameter, aspect-ratio) along which all estimators yield essentially the same solution.\n\nThis equivalence also resolves an important open question regarding the behavior of optimally tuned ridge regularization. Specifically, the generalization error monotonically decreases with overparameterization (assuming the same level of SNR).", "questions": "In Section 2, does M have to grow at a certain rate wrt n ?\n\nIt appears that the Conjecture regarding Kernel Ridge Regression may already be within the reach of this paper, following the equivalence result from Sahraee-Ardakan et al. https://arxiv.org/pdf/2201.08082.pdf", "limitations": "No negative impact envisioned.", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper was delightful to read.\n\nThe problem considered is of very broad interest. The contribution is fundamental and is potentially path-breaking. At the very least, it yields a very satisfactory understanding of the effect of ridge regularization under both important settings.\n- optimal tuning\n- interpolation (lambda = 0)", "weaknesses": "The paper can do with a round of proof-reading. There are some minor issues.\n\nPerhaps the title should read \"ensembled subsampling\" instead of just \"subsampling\".\n\nA sketch of the proof is missing. It would be good to highlight in a couple of paragraphs the core ideas behind the proof of the main result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the excellent concise summary, encouraging comments, and kind words!\nWe are delighted to hear that you found our paper enjoyable to read. \nPaper aside, we also find the structural and risk equivalences quite neat, in understating the effects of ridge regularization, and particularly in the context of optimal ridge tuning and corresponding risk monotonicity.\n\nBelow we comment on the general weaknesses raised (abbreviated by **[W]**).\n\n- **[Response to W1]** _(Paper proofreading)_: Thanks, we are revising the manuscript, taking into account typos from other reviewers as well.\n\n- **[Response to W2]** _(Paper title)_: That is a good suggestion!\n    The reason why we opted for simply subsampling is that the structural equivalence result (Theorem 3) holds for any ensemble size $M$, including $M=1$ when there is no ensemble.\n    The generalized risk equivalence (Theorem 1) holds for the \"infinite'' ensemble $M \\to \\infty$.\n    This is why we simply use `\"subsampling,'' though we fully agree with the sentiment of the comment.\n\n- **[Response to W3]** _(Proof sketches)_:   Thanks for the suggestion!\n    We agree that proof sketches (at least for Theorems 1 and 3) would be beneficial to the readers.\n    However, due to space constraints, we were not able to include more in the main text of the submitted paper.\n    We will try to squeeze in key ideas in the additional space for the paper revision.\n    The core ideas behind the proof involve: 1) using asymptotic equivalences and calculus (instead of computing the actual risks), which lets us bypass the assumptions on features; and 2) generalizing certain linear and non-linear concentration results using rank-2 perturbations of the ridge resolvent, which lets us handle the uncorrelated non-linear component without assuming independence.\n\nBelow we address the two questions raised (abbreviated by **[Q]**). \n\n- **[Response to Q1]** _(Growth rate of ensemble size)_: Good question!\n    We note that we do not actually need an ``infinite'' ensemble when definite the estimator in Section 2.\n    It suffices to consider an ensemble of all possible subsets $\\binom{n}{k}$ of size $k$ out of a dataset of observations $n$, which we call a \"full'' ensemble. One can show that for any fixed dataset $\\mathcal{D}_n$, the ridge estimators fitted on the \"full ensemble'' match that with the \"infinite ensemble'' almost surely conditioned on $\\mathcal{D}_n$, as mentioned in the paragraph after Equation (2) of the submitted paper.\n    For this result, we do not need asymptotics in $n$ or $p$ when defining the full-ensemble estimators in Section 2.\n\n    Now when we consider the equivalence results in Sections 3 and 4, they hold under proportional asymptotics.\n    The result for structural equivalence (in Section 4) holds for any ensemble size $M\\in\\mathbb{N}$.\n    Thus for this result, one does not need to consider varying $M$.\n    The result for risk equivalence (in Section 3) holds for the infinite ensemble as $M \\to \\infty$ or equivalently for a full ensemble.\n    Thus for this result, $M$ changes with $n$ as $M(n) = \\binom{n}{k}$.\n    When $n=k$, this does not grow to infinity.\n    In other words, one may not have \"growing'' number of distinct subsets of size $k$.\n\n- **[Response to Q2]** _(Subsampling equivalences for kernel ridge regression)_: Thanks for the reference!\n    It indeed looks very relevant, and we are working on the kernel extension, and we will add the reference [SAEPRF22] to the list.\n    Because under proportional asymptotics, the behavior of the kernel ridge resolvent is similar to the \"linearized'' kernel, the conjecture indeed looks within reach, as you suggested. We are also looking into a similar conjecture (Conjecture I.1 in the submitted paper) for random features regression using universality ideas (e.g., from [HL22], among others).\n\n**References**\n\n[SAEPRF22] Sahraee-Ardakan, Mojtaba, Melikasadat Emami, Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher. Kernel methods and multi-layer perceptrons learn linear models in high dimensions. arXiv preprint arXiv:2201.08082, 2022.\n\n[HL22] Hu, Hong, and Yue M. Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, 2022."}, {"review_id": "oibWqppm3z", "reviewer": "Reviewer_96Gw", "summary": "The authors investigate the problem of ridge regression, and prove equivalence results between ridge regularisation and ensambling of weak learners trained on subsamples of the original dataset.\nThe equivalences hold under very mild assumptions, and notably there is no requirement on the data model.\nTwo kind of equivalence are proven: i) equivalence at the level of a quite generic class of risks ii) equivalence at the level of the ridge estimator itself.\nThe equivalence basically say that one can trade a bit of subsampling for a bit of ridge regression without altering the performance of the estimator.\n\nThe equivalences hold on paths in the plane defined by the ridge regulariser and the subsampling ratio. \nThe authors provide both a \"theoretical\" characterisation of such paths, which requires knowledge of the population covariance of the features, and a \"data-driven\" characterisation, which requires only access to the sample covariance of the features.\n\nFinally, the authors discuss possible extensions of their results to real-data scenarios and random features regression.\n", "questions": "I do not have any question of the authors. \nI only suggest the authors to improve Figure 3: the caption could additionally describe the difference in x-axis between left and right panel.", "limitations": "The authors do not discuss explicitly limitations. I find that this is not strongly necessary, as the assumptions under which the results hold are clearly presented.\nThe only improvement I could suggest is for the authors to discuss whether they expect the equivalences they prove to break in some specified setting.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The works seems sound, relevant (answering open questions in the literature), well-motivated and well-presented.\nCode is available for reproducibility.\n\nI would like to highlight that the authors need basically no structural assumptions on the data model to prove the equivalence.\n", "weaknesses": "I did not identify any substantial weakness in the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks the nice summary, positive feedback, and the thought-provoking comment about plausible variations of the equivalence paths or even non-equivalences! We are glad that you found the paper interesting and appreciate the kind words.\n\nBelow we address the question and limitation raised. \n\n- **[Response to question]** _(Clarification of Figure 3 caption)_: Thanks for the suggestions!\nWe have now updated the caption of Figure 3 with additional clarifications on the linear functionals in the left panel and the risk functionals in the right panel and added pointers to the corresponding theorems.\n\n- **[Response to limitation]** _(Plausibility and conditions for different equivalence paths or non-equivalences)_: This is very interesting and thought-provoking comment! With i.i.d. samples, we expect the results to hold more generally, even beyond RMT features; see the discussions in Section 6 of the submitted paper.\nHowever, we acknowledge that the equivalences could potentially break, particularly if the observations are not sampled in an i.i.d. manner.\nFor instance, if the observations follow a specific dependence structure, such as in a time-series setting, then the equivalence paths could be influenced by this dependence structure.\nFurthermore, we expect different variations of the equivalence paths under different sampling strategies, such as sampling with (or without) replacement within each subsampled dataset (and across all subsampled datasets).\nA precise characterization of these variants is an interesting direction for future work.\nThanks again for this instigating this thought!"}]

Author rebuttal:

Meta-review: Overall, this is a solid and well-written paper on a core topic in statistical learning -- establishing a variety of equivalences between ridge regularization to subsampling in ensemble (ridge) estimators. It extends and improves prior literature by weakening assumption and by covering several kinds of learning/risk equivalences (e.g. empirical risk, out-of-sample risk, and transfer learning). It is well-written and synthesizes its results among existing ones in a way that ought to also be useful to readers outside of its sub-field.

One reviewer was especially enthusiastic about the paper overall. Their recommendation is balanced by others (e.g. reviewers DNS5, wEHo) who maintained reservations that the assumptions (asymptotics, the proportional limit regime, and so on) limit the scope of the result somewhat. Either way, I believe that the discussion with these reviewers led to some useful clarifications on the statement of contributions. For example, the discussion with reviewers DNS5 and wEHo stressed that the conjecture from Nakkiran et al is broader than what this paper resolves (since it is stated for finite dimensions, whereas this paper again focuses on proportional asymptotics). Meanwhile, the discussion with reviewer MtFr pointed out a new reference and conjecture to look into -- whether or not it turns out indeed within reach, it may be worth at least a remark.
Decision: Accept (poster)