Implicit Regularization Paths of Weighted Neural Representations
Authors: Jin-Hong Du
Pratik Patil
Venue: NeurIPS 2024 poster (2024)
Keywords: pretrained representations
implicit regularization
random features
kernel regression
neural tangent kernel
cross-validation
Primary area: learning_theory
TL;DR: We explore the implicit regularization induced by weighted and/or subsampled pretrained neural features, offering theory and practical methods to manage high-dimensional data for better model fitting.

Abstract: We study the implicit regularization effects induced by (observation) weighting of pretrained features.
For weight and feature matrices of bounded operator norms that are infinitesimally free with respect to (normalized) trace functionals, we derive equivalence paths connecting different weighting matrices and ridge regularization levels.
Specifically, we show that ridge estimators trained on weighted features along the same path are asymptotically equivalent when evaluated against test vectors of bounded norms.
These paths can be interpreted as matching the effective degrees of freedom of ridge estimators fitted with weighted features.
For the special case of subsampling without replacement, our results apply to independently sampled random features and kernel features and confirm recent conjectures (Conjectures 7 and 8) of the authors on the existence of such paths in Patil and Du (2023).
We also present an additive risk decomposition for ensembles of weighted estimators and show that the risks are equivalent along the paths when the ensemble size goes to infinity.
As a practical consequence of the path equivalences, we develop an efficient cross-validation method for tuning and apply it to subsampled pretrained representations across several models (e.g., ResNet-50) and datasets (e.g., CIFAR-100).

Implicit Regularization Paths of Weighted Neural Representations
Jin-Hong Du Carnegie Mellon University jinhongd@andrex. cmu.ed edu
Pratik Patil University of California Berkeley
pratikpatii@@erkelleyy edu
Abstract
We study the implicit regularization effects induced by (ohservation) weighting of pretrained features. For weight and feature matrices bounded operator norms that are infinitesimally free with respect (normalized) trace functionals, we derive equivalence paths connecting different weighting matrices and ridge regu- larization levels. Specifically, we show that ridge estimators trained weighted features along the same path are asymptotically equivalent when evaluated against vectors of bounded norms. These paths can be interpreted as matching the effective degrees of freedom of ridge estimators fitted with weighted features. For the special case of subsampling without replacement, our results apply to indepen- dently sampled random features and kernel features and confirm recent conjectures (Conjectures and 8) of the authors on the existence of such paths in [50]. We also present an additive risk decomposition for ensembles of weighted estimators and show that the risks are equivalent along the paths when the ensemble size goes to infinity. As practical consequence of the path equivalences, we develop an efficient cross-validation method for tuning and apply it to subsampled pre- trained representations across several models (e.g., ResNet-50) and datasets (e.g., CIFAR-100).
Introduction
In recent years, neural networks have become state-of-the-an models for tasks in computer vision and natural language processing by learning rich representations from large datasets. Pretrained neural networks, such as ResNet, which are trained on massive datasets like ImageNet, serve as valuable resources for new, smaller datasets [32]. These pretrained models reduce computational burden and generalize well in tasks such as image classification and object detection due to their rich feature space [32, 69]. Furthermore, pretrained features neural embeddings, such the neural tangent kernel, extracted from these models, serve as valuable representations of diverse data [33, 66).
However, despite their usefulness, fitting models based on pretrained features on large datasets can be challenging due to computational and memory constraints. When dealing with high-dimensional pretrained features and large sample sizes, direct application of even simple linear regression may be [23, 44]. To address this issue, subsampling has
computationally infeasible or memory-prohibiiee emerged a practical solution that reduces the dataset size, thereby alleviating the computational and memory burden. Subsampling involves creating smaller datasets by randomly selecting a subset the original data points. Beyond these computational and memory advantages, subagging can also greatly improve predictive performance in overparameterized regimes, especially near model interpolation thresholds [53]. Moreover, through distributed learning, models fitted multiple subsampled datasets can be aggregated as an ensemble to provide more stable predictions [20, 21, 51].
There has been growing interest in understanding the effects of subsampling (without replacement) [16, 25, 37, 50, 51]. These works relate subsampling to explicit ridge regularization, assuming either
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Overview of related work the equivalence of implicit regularization and explicit ridge regularization.
Main analysis
Feature structure
Weight structure
Reference
Gaussian
subsampling
[37]
Risk characterization
linear
subsampling
[51]
Gaussian
bootstrapping
[5, 16, 17]
linear
subsampling
[50]
general
general subsampling
Theorem
Estimator equivalence
general
Theorem 2
linear, random, kernel
subsampling
Propositions 3-5
linear
subsampling
[50]
Risk equivalence
general
general
Theorem 6
Gaussian features ~ (O,,, Σ) linearly decomposable features (referred as linear features in this paper) Φ = /1/2z, where E E: RPxP is the covariance matrix and E IR contains i.i.d. entries with zero means and bounded + 8 moments for some 5 > O. Specifically, [50] establish a connection between implicit regularization induced by subsampling and explicit ridge regularization through path defined by the tuple (k/n, A), where k and n are the subsample size and the full sample size, respectively, and the ridge regularization level. Along this path, any subsample estimator with the corresponding ridge regularization exhibits the same first-order (or estimator equivalence) and second-order (or risk equivalence) asymptotic limits. Moreover, the endpoints of all such paths along the two axes of k π. (no subsampling) and À = 0 (no regularization) span the same range. Although these results have been demonstrated for linear features, [50] also numerically observe similar equivalence behavior in features and kernel features based on heuristic "universality" " justifications. However, extending these results to encompass more general feature structures and other sampling schemes remains open question.
realistic contexts and propose conjectures for random
Towards answering this question, in this paper, we view subsampling a weighted regression problem [67]. This perspective allows us to study the equivalence in its most general form, considering arbitrary feature structures and weight structures. The general weight matrix approach used in this study encompasses various applications, including subsampling, bootstrapping, variance-adaptive weighting, survey, and importance weighting, among others. By interpreting subsampling weighted regression problem, we leverage recent tools from free probability theory, which have been developed analyze feature sketching [39, 42, 54]. Building on these theoretical tools, establish implicit regularization paths for general weighting and feature structures. We summarize our main results below and provide overview of our results in the context of recent related work in Table 1.
1.1 Summary of results and paper outline
We summarize our main results and provide an outline for the paper below.
Paths of weighted representations. In Section 3, we demonstrate that general weighted mod- els exhibit first-order equivalence along a path (Theorem 1) when the weight matrices are asymptotically independent of the data matrices. This path of equivalence can be computed directly from the data using the formula provided in Equation (2). Furthermore, we provide a novel interpretation of this path in terms of matching effective degrees of freedom of models along the path for general feature structures when the weights correspond to those arising from subsampling (Theorem 2).
Paths of subsampled representations. We further specialize our general result in Theorem 2 for the weights induced by subsampling without replacement to structured features in Section 3.2. These include results for linear random features, nonlinear random features, and kernel features, as shown in Propositions 3-5, respectively. The latter two results also resolve Conjectures 7 and 8 raised by [50] regarding subsampling regularization paths for random and kernel features, respectively.

---

Risk equivalences and tuming. In Section 4, we demonstrate that an ensemble of weighted models has general quadratic risk equivalence on the path, with an error term that decreases inversely as 1/ /M as the number of ensemble size M increases (Theorem 6). The risk equivalence holds for both in-distribution and out-of-distribution settings. For subsampling general features, we derive upper bound for the optimal subsample size (Proposition 7) and propose a cross-validation method to tune the subsample and ensemble sizes (Algorithm I), validated on real datasets in Section 4.3.
This level of generality is achievable because we do not analyze the risk of either the full model or the weighted models in isolation. Instead, we relate these two of models, allowing us maintain weak assumptions about the features. The key assumption underlying our results is the asymptotic freeness of weight matrices with respect to the data matrices. While directly testing this assumption is generally challenging, we verify its validity through its consequences on real datasets in Section 4.3.
1.2 Related literature
We provide a brief account of other related work below to place our work in a better context.
Linear features. Despite being overparameterized, neural networks generalize well in practice [70, 71]. Recent work has used high-ding nigh-dimensiona "linearized" networks to investigate the various phenomena that arise in deep learning, such as double descent [12, 46, 48], benign overfitting [10, 35, 45], and scaling laws [7, 19, 66). This literature analyzes linear regression using statistical physics [14, 60] and random matrix theory [22, 30]. Risk approximations hold under random matrix theory assumptions [6, 30, 66] in theory and apply empirically on a variety of natural data distributions [43, 60, 66).
Random and kernel features. Random feature regression, initially introduced in [56] as way to scale kernel methods, has recently been used for theoretical analysis of neural networks and trends of double descent in deep networks [1, 46]. The generalization of kernel ridge regression has been studied in [11, 40, 57]. The risks of kernel ridge regression are also analyzed in [9. 19, 29]. The neural representations we study work on ultra-wide neural networks and their relationships to NTKs [34, 68).
motivated by the neural tangent kernel (NTK) and related theoretical
Resampling analysis. Resampling and weighted models are popular in distributed learning to provide more stable predictions and handle large datasets [20, 21, 51]. Historically, for ridge ensembles, [36, 61] derived risk asymptoties under Gaussian features. Recently, there has been growing interest in analyzing the effect of subsampling high-dimensional settings. [37] considered least squares ensembles obtained by subsampling, where the final subsampled dataset has more observations than the number of features. For linear models the underparameterized regime, [59] also provide certain equivalences between subsampling and iterative least squares approaches. The asymptotic risk characterization for general data models has been derived by [51]. [25, 50] extended the scope of these results by characterizing risk equivalences for both optimal and suboptimal risks and for arbitrary feature covariance and signal structures. Very recently, different resampling strategies for high-dimensional supervised regression tasks have been analyzed by [17] under isotropic Gaussian features. Cross- validation methods for tuning the ensemble of ridge estimators and other penalized estimators are discussed in [13, 25, 26). Our work adds to this literature by considering ensembles of models with general weighting and feature structures.
2 Preliminaries
In this section, we formally define our weighted estimator and state the main assumption on the weight matrix. Let fmn: Rd IR" be a pretrained model. Let (0,, i 1....... in Id IR be the given dataset. Applying fm to the raw dataset, we obtain the pretrained features Φ; = fm; matrix notation, we denote the pretrained feature matrix by + ( 6.)" E Raxp, Let W E Raan be general weight matrix used for weighting the observations. The weight matrix W is allowed to be asymmetric, in general.
for i = 1,..., n as the resulting neural representations or neural embeddings.
3

---

We consider fitting ridge regression on the weighted dataset (W4, Wy). Given a ridge penalty A, the ridge estimator fitted on the weighted dataset is given by:
[yy 3 + (1S11 - ( W W + T
Bw.x == argmin BERP
Wy. (1)
In the definition above, we allow for À = O, in which case the corresponding ridgeless estimator is defined the limit À -> 0+. For À < O, we use the Moore-Penroon pseudoinverse. An important special case is where Win is a diagonal matrix, in which case the above estimator reduces to weighted ridge regression. This type of weight matrix encompasses various applications, such resampling, bootstrapping, and variance weighting. Our main application in this paper will be subsampling.
For our theoretical results, we assume that the weight matrix W preserves some spectral structure of the feature matrix + This assumption is captured by the condition of asymptotic freeness between W W and the feature Gram matrix Φ Asymptotie freeness is concept from free probability theory [64].
Assumption A (Weight structure). Let W W and 4 /n converge almost surely to bounded operators that are infinitesimally free with respect to (trl-),tr(C(( with ||Cl|tr uniformly bounded. Additionally, let W T W have limiting S-transform that analytic on the lower half of the complex plane.
tr tr(C()) for any C' independent of W
At a high level, Assumption A captures the notion of independence but adapted for non-commutative random variables of matrices. We provide background on free probability theory and asymptotic freeness in Appendix A.3. Here, we briefly list series of invertible transformations from free probability to help define the S-transform [47]. The Cauchy transform is given by G2(z) = tr[(21 - "1. The moment generating series is given by Ma(z) = 2 -A -. The
A (w). These are the Cauchy transform (negative of the Stieltjes transform), moment generating series, and S-transform of A, respectively. Here,
S-transform is given by SAw = (1 + w M (-1)
( denotes the inverse under the composition of MA. The notation tr[A] denotes the average trace tr[Al/p of A E Rexp.
The freeness of a pair of matrices A and B means that the eigenvectors of one are completely unaligned or incoherent with those of the other. For example, if A URU for uniformly random unitary matrix U drawn independently of the positive semidefinite B and R, then A and B are almost surely asymptotically infinitesimally free [15]. Other well-known examples include Wigner matrices, which are asymptotically free with respect to deterministic matrices [4, Theorem 5.4.5). Gaussian matrices, where the Gram matrix G Φ /n U(VV /n)UU and any deterministic S, are almost surely asymptotically free [47, Chapter 4, Theorem 9]. Although not proven in full generality, it is expected that diagonal matrices are asymptotically free from data Gram matrices constructed using i.i.d. data. In Section 3.2, we will provide additional examples of feature matrices, such as random and kernel features from machine learning, for which our results apply.
Our results involve the notion of degrees of freedom from statistical optimism theory [27, 28]. Degrees of freedom in statistics count the number of dimensions in which statistical model may vary, which is simply the number of variables for ordinary linear regression. To account for regularization, this notion has been extended to effective degrees of freedom (Chapter 3 of [31]). Under some regularity conditions, from Stein's 's relation [63], the degrees of freedom of a predictor f are measured by the trace of the operators y + (0/0y) fitted on ( @ y) with penalty p. the degrees of freedom is consequently the trace of its prediction operator y - & / + + pIp) ) + y, which is also referred as the ridge smoother matrix. That is,
f( f For the ridge estimator BI
df( = tr| ( 1 + HI,,) $1. We denote the normalized degrees of freedom by df = /n.
Note that df (3 I min(n, p) Inn. 1.
Finally, we express our asymptotic results using the asymptotic equivalence relation. Consider sequences {An I221 and (Br of (random or deterministic) matrices (which includes vectors and scalans). We say that A,, and B, are equivalent and write A,, > B, if limp- |t |r|C,, (A, B.)]l = 0 almost surely for any sequence C, of matrices with bounded trace norm such that lim sup || < oo as n - cc. Our forthcoming results apply to a sequence of problems indexed by n. For notational simplicity, we omit the explicit dependence in our statements.

---

3 Implicit regularization paths
We begin by characterizing the implicit regularization induced by weighted pretrained features. We will show that the degrees of freedom of the unweighted estimator Br,,, on the full data ( y. with regularization parameter μl are equal the degrees of freedom of the weighted estimator Bw,x A for some regularization parameter A. For estimator equivalence, our data-dependent set of weighted ridge estimators (W, A) that connect to the unweighted ridge estimator (I, (1) is defined in terms of "matching" effective degrees of freedom of component estimators in the set.
To state the upcoming result, denote the Gram matrix of the weighted data Gw W W /n and the Gram matrix of the unweighted data as G₁ - /nn. Furthermore, let A A (A) denote the minimum positive eigenvalue of a symmetric matrix A.
Theorem 1 (Implicit regularization of weighted representations). For G1 Rux", suppose that the weight matrix W E R=*x satisfies Assumption A and lim sup llyll//n < oo as n + co. For any a > - lim inf Anin (G1), let X -mmin (Gw) be given by the following equation:
== w//STTTTp w( (t/////wwd((B)). (-d((31,.)),
where Sw w is the S-transform of the operator W W. Then, as n - cc, it holds that:
df df(@w.x) = df(3r...) and Bw.x- Br.
In other words, to achieve a target regularization μ on the unweighted data, Theorem provides a method to compute the regularization penalty À with given weights W from the available data using (2). The weighted estimator then has asymptotically the same degrees of freedom as the unweighted estimator. This means that the level of effective regularization of the two estimators is the same. Moreover, the estimators themselves every constant vector e with bounded norm. The estimator equivalence in Theorem a "first-order" result, while we will also characterize the "second-order" effects in Section 4.
structurally equivalent; that is, c C(@w BI,aa) - 0 for
The notable aspect of Theorem is its generality. The equivalence results hold for a wide range of weight matrices and allow for negative values for the regularization levels. Furthermore, we have not made any direct assumptions about the feature matrix Φ, the weight matrix W, and the response vector y (other than mild bounded norms). The main underlying ingredient is the asymptotic freeness between W and &, which we then exploit using tools developed in [39] in the context of feature sketching. We discuss special cases of interest for W and T in the upcoming Sections 3.1 and 3.2.
3.1 Examples of weight matrices
There are two classes of weighting matrices that are of practical interest:
Non-diagonal weighting matrices. One can consider observation sketching, which involves some random linear combinations of the rows of the data matrix. Such observation sketching is beneficial for privacy, as it scrambles the rows of the data matrix, which may contain identifiable information about individuals. It also helps in reducing the effect of non-i.i.d. data that arise in time series spatial data, where one wants smooth away the impact of irregularities or non-stationarity.
Diagonal weighting matrices. When observations are individually weighted, W is diagonal matrix, which includes scenarios such as resampling, bootstrapping, and subsampling. Note that even with subsampling, one can have non-binary diagonal weighting matrix. For example, one can consider sampling with replacement or sampling with a particular distribution, which yields non-binary diagonal weighting matrices. Other examples of non-binary diagonal weighting matrices include inverse-variant variance weighting sampling to mitigate the effects of heterogeneous variations if the responses have different variances for different units.
In general, the set of equivalent weighted estimators depends on the corresponding S-transform as in (2), and it can be numerically evaluated. When focusing on subsampling without replacement, the data-dependent path for equivalent estimators with associated subsampling and regularization levels can be explicitly characterized in the following result by analyzing the S S-transform of subsampling operators.
5

---

Degrees of freedom
Gaussian
0.040
0.025
Ridge penalty
0.1
600
0.010
0.005
10
0.0
0.1
Subsample ratio k/n
Subsample ratio k/n
Figure 1: Equivalence under subsampling. The left panel shows the heatmap of degrees freedom, and right panel shows the random projection lšw ja 3w.., ..] where NN(O,, Lp/p) /p) In both heatmaps. lines indicate the predicted paths using Equation (4); and black dashed lines indicate empirical paths by matching empirical degrees of freedom. The data is generated according to Appendix F.1 with n = 10000 and p 1000, and the results averaged over M 100 random weight matrices W.
color
Theorem (Regularization paths due to subsampling). For a subsampling matrix W consisting of unit diagonal entries, the path (2) in terms of (ki, X) simplifies to:
(1-df/n) df/n). (1-A/p) (1- k1nk/n),
(4)
where we denote by df df df (3w..) for notational simplicity.
The relation (4) is remarkably simple, yet quite general! It provides an interplay between the normalized target complexity df/n, regularization inflation A/μ, and subsample fraction k/n:
(1 normalized complexity)
regularization inflation) = (1 -ubsample fraction).
(5)
Since the normalized target complexity and subsample fraction are no greater than one, (5) also implies that the regularization level for the subsample estimator always lower than the regularization level for the full estimator. In other words, subsampling induces (positive) implicit regularization, reducing the need for explicit ridge regularization. This is verified numerically in Figure 1.
For fixed target regularization amount μu, the degrees of freedom (f of the ridge estimator on full data is fixed. Thus, we can observe that the path in the (k/n, A)-plane is a line. There are two extreme cases: (1) when the subsample size is close to n. have y A; and (2) when the subsample size is near O, we have μ = co. When À = O, the effective regularization level À is such that dff (B (Brr,.. k. which find to be neat relation!
Beyond subsampling without replacement, one can also consider other subsample matrixs. For example, for bootstrapping & entries, we observe similar equivalent path in Figure 5. Additionally, for random sample reweighting, as shown Figure 6, we also observe certain equivalence behaviors of degrees of freedom. This indicates that Theorem also applies to more general weighting schemes.
3.2 Examples of feature matrices
As mentioned in Section 2, when the feature matrix & consists of i..d. Gaussian features, any deterministic matrix W satisfies the condition stated in Assumption A. However, our results are limited Gaussian features. In this section, we will consider more general families of features commonly analyzed in machine learning and demonstrate the applicability of our results to them.
(1) Linear features. As first example, we consider linear features composed of (multiplicatively) transformed i..dd entries with sufficiently bounded moments by a deterministic covariance matrix.
Proposition (Regularization paths with linear features). Suppose the feature & can be decomposed as Φ 11/22 where E TRP contains i.i.d. entries z, 1,..., . with mean 0, variance 1, and satisfies [||211+H My for some 0 and constant M,, and Σ e XPPP is deterministic

---

Kernel
Random features
409
-00
Ridge penalty
280
306
10
0.0
0.1
0.0
0.1
0.0
0.1
Subcample ratio kin
Subsample ratio kin
Subsample ratio km
Figure Equivalence of degrees freedom for various feature structures under subsampling. The three panels correspond to linear features, random features with ReLU activation function (2-layer), and kernel features (polynomial kernel with degree 3 and without intercept), respectively, In all heatmaps, the red color lines indicate the predicted paths using Equation (4), and the black dashed lines indicate the empirical paths by matching the empirical degrees freedom. The data generated according to Appendix F. with 5000 and p 500, and the results are averaged over M 100 random weight matrices W.
symmetric matrix with eigenvalues uniformly bounded between constants T'mn >> O and T'ax < 00. Then, as n, > Do such that p/n - 7 > 0, the equivalences in (3) hold along the path (4).
Features of this type are common in random matrix theory [8] and in a wide range of applications, including statistical physics [14, 60], high-dimensional statistics [22, 55, 58], machine learning [18], among others. The generalized path (2) in Theorem 2 recovers the path in Proposition 4 of [50]. Although the technique in this paper is quite different and more general than that [50].
(2) Kernel features. As the second example, Theorem 2 also applies to kernel features. Kernel features are a generalization linear features and lift the input feature space to a high- or infinite- dimensional feature space by applying a feature map + Φ(x). Kernel methods use the kernel function K (a,,, m35) = (<)) (xr,)) to compute the inner product in the lifted space.
Proposition 4 (Regularization paths with kernel features). Suppose the same conditions in Proposition 3 and the kernel function is of the form K K(v,, 2;;) (112> 11:2:11/p.pp (xt, xz)/p. where y C² around (T, T, r) and C around (r, 0, r) and limp- tr[D/d /d. Then, n oc. the equivalences in (3) hold in probability along the path (4).
The assumption Proposition is commonly used in the risk analysis of kernel ridge regression [9, 19, 29, 57], among others. Here, C denotes the class of functions that are k-times continuously differentiable. It includes neural tangent kernels (NTKs)
special case. Proposition 4 confirms
Conjecture 8 of [50] for these types of kernel functions.
(3) Random features. Finally, consider random features that were introduced by [56] way to scale kernel methods to large datasets. Linked closely to two-layer neural networks [46], the random feature model has fmn(x)
(Fæ), where F E Rx is some randomly initialized weight matrix, and a IR + R is a nonlinear activation function applied element-wise to Fx.
Proposition 5 (Regularization paths with random features). Suppose x; ~ (0, Σ) and the activa- tion function IR + R is differentiable almost everywhere and there are constants co and ej such that (x)], (z)) I coe whenever o d'(x) exists. Then, as n, p, d + oo such that p/n + > and d/n & > 0, the equivalences in (3) hold in probability along the path (4).
As mentioned in the related work, random feature models have recently been used as a standard model to study various generalization phenomena observed in neural networks theoretically [1, 46]. Proposition resolves Conjecture 7 of [50] under mild regularity conditions on the activation function.
It is worth noting that the prior works mentioned above, including [50], have focused on first characterizing the risk asymptotics above. In contrast, our work in this paper deviates from these approaches by not expressing the risk in population quantities but rather by directly relating the estimators at different regularization levels. In the next section, will explore the relationship between their squared prediction risks.
terms of various population quantities for each the cases
7

---

4 Prediction risk asymptotics and risk estimation
The results in the previous section provide first-order equivalences of the estimators, which are related to the bias of the estimators. In practice, we are also interested in the predictive performance of the estimators. ridge regularization through ensembling. Specifically, we show that aggregating estimators fitted on different weighted datasets also reduces the additional variance. Furthermore, the prediction risks of the full-ensemble weighted estimator and the unweighted estimator also match along the path.
this section, we investigate the second-order equivalence of weighting and
Before presenting our risk equivalence result, we first introduce some additional notation. Assume there are M i.idd weight matrices Wi...., WM E R=xx The M -enseblle estimator is defined as:
M
BWEMd M-
Bwm..r
(6)
m=1
and its performance is quantified by the conditional squared prediction risk, given by:
R R(Bw.s..)) Emo.. [[5o- - 2J 3w d2, y, (Wm) [Wm)ml)
where (æo, (o) is a test point sampled independently from some distribution Pa that may be different from the training distribution Pr.g. and Φn = (2ro) is the pretrained feature at the test point. The covariance matrix of the test features Φ is denoted by Eg. When Fa Pa.y refer to it as the in-distribution risk. On the other hand, when P20.3o differs from Pa we refer to it the out-of-distributiin risk. Note that the conditional risk RM is scalar random variable that depends on both the dataset (4,, y) and the weight matrix W.. for m E [M]. Our goal in this section is to analyze the prediction risk of the ensemble estimator (6) for any ensemble size M.
Theorem 6 (Risk equivalence along the path). Under the setting of Theorem 1, assume that the operator norm of Σo uniformly bounded in p and that each response variable ys for i 1...., has mean O and satisfies E| S M2 < 00 for some p. M, > 0. Then, along the path (4).
R(3w = R(3I,.) + M
+ (G1 + +Inn)',
(8)
where the constant C is given by:
C= -pp0p00 X S wwww( (- (T((Gr + + /n) +n))).
At a high level, Theorem 6 provides a bias-variance-like risk decomposition for both the squared risks of weighted ensembles. The risk of the weighted predictor is equal the risk of the unweighted equivalent implicit ridge regressor (bias) plus a term due to the randomness due to weighting (variance). The inflation factor C' controls the magnitude of this term, and it decreases at rate of 1/M as the ensemble size M increases (see Figure 7 for a numerical verification of this rate). Therefore, by using a resample ensemble with a sufficiently large size M, we can retain the statistical properties of the full ridge regression while reducing memory usage and increasing parallelization.
Theorem 6 extends the risk equivalence results in [50, 52]. Compared to previous results, Theorem 6 provides a broader risk equivalence that holds for general weight and feature matrices, as well as an arbitrary ensemble size M. It is important to note that Theorem 6 holds even when the test distribution differs from the training data, making it applicable to dist---iittiibttion risks. Furthermore, our results do not rely any specific distributional assumptions for the response vector, making them applicable in a model-free setting. The key idea behind this result is to exploit asymptotic freeness between the subsample and data matrices. Next, we will address the question of optimal tuning.
4.1 Optimal oracle tuning
As in Theorem 2, we next analyze various properties related to optimal subsampling weights and their implications for the risk of optimal ridge regression. Recall that the subsampling matrix (kk is diagonal matrix with & E {1. (1....,7) n nonzero diagonal entries, which is parameterized by the subsample size k. Note that the optimal regularization parameter jı" for the full data (W()) = I or A: = n) a function of the distribution of pretrained data and the test point. Based on the risk equivalence in Theorem 6, there exists an optimal path of (k, >) with the corresponding full fullmensemble
8

---

Degrees freedom
Predicti
0.00 0.00050
1200
0017
Ridge penally
1000
0.00045
0006
0.015
0.00040
0004
-0 0000003
0.033
400
0.122
0.00033
200
0.111
Subsample ratio kin Figure 3: Equivalence in pretrained features of pretrained ResNet-50 Flowers-102 datasets.
Subsample ratio k/n
Subsample ratio kin
estimator 3 Bwyes
1:00 A = M 3 w that achieves the optimal predictive performance at (n, jz") M.M.A
In particular, the ridgeless ensemble with X 0 happens to be the path. From previous work [25, 50], the optimal subsample size k" for A = O has the property that k* S under linear features. We show in the following that this property can be extended to include general features.
Proposition 7 (Optimal subsample ratio). Assume the subsampling matrix W as defined in Theo- rem 2. Let μ argmin,20 R(3
with 1:00.11
..). Then the corresponding subsample size satisfies:
k- = =
w/ ( _u-)
S rank(G,).
(10)
The optimal subsample size k* obtained from Proposition is asymptotically optimal. For linear features, the underparameterizeed regime where p. [25, 50] show that the optimal subsample size k* is asymptotically no larger than p. This result is covered by Proposition 7 by noting that ran S p under linear features. underparameterizzed regime (when n), we do not need more than observations to achieve the optimal risk. In this sense, the optimal subsampled dataset always overparameterized.
interesting and somewhat surprising to note that in the
When the limiting risk profiles R(7, 1b, (4) p/ R(B
W . exist for subsample
ensembles, the limiting risk of the optimal ridge predictor inf ( ()) is monotonically decreasing in the limiting sample aspect ratio 7 [50]. This also (provably) confirms the sample-wise monotonicity of opte risk for general features in asymptotic
[48]. Due to the risk
equivalence in Theorem 6, for any > 0, there exists v such that A(7, 7, 14) = A (r, 4 0). This implies that =00 R (r: 14) inf u2 ( 1h, 0). In other words, tuning subsample sizes with sufficiently large ensembles is equivalent to tuning over the ridge penalty on the full data.
4.2 Data-dependent tuning
As suggested by Proposition 7, the optimal subsample size is smaller than the rank of the Gram matrix. This result has important implications for real-world datasets where the number of observations (n) much larger than the number of features (p). In such cases, instead of using the entire dataset, can efficiently build small ensembles with a subsample size i S p. This approach is particularly beneficial when is significantly higher than p. for example, when with only M = 100 base predictors, we can potentially reduce the computational burden while still achieving optimal predictive performance. Furthermore, this technique be especially valuable in scenarios where computational resources are limited or when dealing with massive datasets that cannot be easily processed in their entirety.
1000p. By fitting ensembles
In the following, we propose a method to determine the optimal values of the regularization parameter 4² for the full ridge regression, well as the corresponding subsample size k- and the optimal ensemble size M². According to Theorem 6, the optimal value of M is theoretically infinite. However, in practice, the prediction risk of the Meensemble predictor decreases at rate of 1/M as M increases. Therefore, important to select a suitable value of M that achieves the desired level of performance while considering computational constraints and the specified error budget. By carefully choosing an appropriate M, we can strike a balance between model accuracy and efficiency, ensuring that the subsampled neural representations are effectively used in downstream tasks.
Consider grid of subsample size K., S (1...., n): for instance, K.,, = (0, ko 2ko...., ,n) where kg is subsample size unit. For prespecified subsample size k E K,, and ensemble size Mo

---

Algorithm 1 Meta-algorithm for tuning of ensemble sizes and subsample matrices.
Input: A dataset D, [( vi) E R x R: Si n), a regularization parameter X, a class of subsample matrix distribution Pn {Pa)kex,,> a ensemble size Ma 2 2 for risk estimation, and optimality tolerance parameter 8.
3 wwit) with My base estimators, where ((()) W (k) iid. Mu
1: Build ensembles
~ Pk. for each
Wi.d0o 1:240
k E Kr,
2: Estimate the prediction risk of 3 with 1.M. with Rm, by CV methods such as CGCV [13], for
k E Kr, and m = ,1...,,,, Mo-
3: Extrapolate the risk estimations Rmn, for >> Mo using (11) and (12).
4: Select a subsample size & E argmingex. Roo that minimizes the extrapolated estimates.
5: Select an ensemble size M argmin 1R m,,
R xe + 6) for the 6-optimal risk.
6: If M Mo. fit a M-ensemble estimator 3 w
Output: Return the tuned estimator e w((
and the risk estimators RAI for all M, k.
'
1:37
N. suppose we have multiple risk estimates Rm of Ryn for m I...., Mo- The squared risk
decomposition [51, Eq (7)] along with the equivalence path (8) implies that Rm m Ri (1 m Roc, for = 1, 1,..., My. Summing these equations yields Eme Rm > Mu Rı MM (1 - mm m) Rxo Thus, we can estimate Roo by:
Me
Ma
Rox0
Rm
R1
Σ
(1-m
(11)
m=
m=
Then, the extrapolated risk estimates Rm (with mn > Mo) are defined as:
R. = m -R + (1-m² 1) Roo for m Mo.
(12)
The meta- algorrtht that implements the above cross-validation procedure provided in Algorithm 1. To efficiently tune the parameters of ridge ensembles, we use and combine the corrected generalized cross-validation (CGCV) method [13] and the extrapolated cross-validation (ECV) method [26]. The
improved CV method is implemented in the Python library [24].
4.3 Validation on real-world datasets
In this section, we present numerical experiments to validate our theoretical results on real-world datasets. Figure 3 provides evidence supporting Assumption A on pretrained features extracted from commonly used neural networks applied to real-world datasets. The first panel of the figure demonstrates the equivalence of degrees of freedom for these pretrained features. Furthermore, we also observe consistent behavior across different neural network architectures and different datasets (see Figures 8 and 9). Remarkably, the path of equivalence can be accurately predicted, offering valuable insight into the underlying dynamics of these models. This observation suggests that the pretrained features from widely used neural networks exhibit similar properties when applied to real- world data, regardless of the specific architecture employed. The ability to predict the equivalence path opens up possibilities for optimizing the performance of these models in practical applications.
One implication of the equivalence results explored Theorems and 6 that instead of tuning for the full ridge penalty μa the large datasets, we can fix small value of the ridge penalty X, fit subsample ridge ensembles, and tune for an optimal subsample size k. To illustrate the validity of the tuning procedure described in Algorithm 1, we present both the actual prediction errors and their estimates by Algorithm Figure 4. We observe that the risk estimates closely match the prediction risks at different ensemble sizes across different datasets. Even with subsampling ratio k/n of 0.01 and a sufficiently large M, the risk estimate close to the optimal risk. A smaller subsample size could also yield even smaller prediction risk in certain datasets.
10

---

Prediction ritk
M=1
M=
M=5
10=10
Mt
100
Estimated risk
M=
Ml2
M=
M--10
M 100
Fashion-MNIST/ ResNet-18
CIFAR-10 Reshist-18
CIFAR-1 ResNat-SO
Food-101 Reshist-101
0416
000
0.0
6312
806
304
1.000
0410
20
10
2pm1
E0e
16"11
2pt
201 Subsample ratio
D
Subsample ratio
Subsample retio kin
Subsample rañio kin
Figure 4: Risk estimation by corrected and extrapolated generalized ross-validatiin. The risk estimates
computed based Mo 25 base estimators using A Algorithm with 10-3
5 Limitations and outlook
While our results are quite general in terms of applying to a wide variety of pretrained features, they are limited in that they only apply ridge regression fitted on the pretrained features. The key challenge for extending the analysis based on Assumption A to general estimators beyond ridge regression the characterization of the effect of subsampling general resolvents as additional ridge regularization. To extend to generalized linear models, one approach is to view the optimization as iteratively reweighted least squares [38] in combination with the current results. Another approach is to combine our results with the techniques in [41] to obtain deterministic equivalents for the Hessian, enabling an understanding of implicit regularization due to subsampling beyond linear models.
Beyond implicit regularization due to subsampling, there are other forms of implicit regularization, such as algorithmic regularization due early stopping in gradient descent [2, 3, 49), dropout regularization [62, 65], among others. In some applications, multiple forms of implicit regularization are present simultaneously. For instance, during mini-batch gradient step, implicit regularization arises from both iterative methods and mini-batch subsampling. The results presented in this paper may help make explicit the combined effect of various forms of implicit regularization.
Acknowledgments and Disclosure of Funding
thank Benson Au, Daniel LeJeune, Ryan Tibshirani, and Alex Wei for the helpful conversations surrounding this work. We also thank the anonymous reviewers for their valuable feedback and suggestions.
We acknowledge the computing support the ACCESS allocation MTH230020 provided for some of the experiments performed on the Bridges2 system at the Pittsburgh Supercomputing Center. The code for reproducing the results of this paper can be found at https: //jayul aawpa.ggihhubb...........p...u.e io/ overparames ter ized- ensembl wwwgg//gegeeedeeeeeeeeeeeee neural.
References
[1] Adlam, B., Levinson, A., and Pennington, (2022). A random matrix perspective mixtures nonlinearities high dimensions. In International Conference on Artificial Intelligence and Statistics.
[2] Ali, A., Dobriban, E., and Tibshirani, R. J. (2020). The implicit regularization of stochastic gradient flow for least squares. In International conference on machine learning.
[3] Ali, A., Kolter, J. Z., and Tibshirani, R. J. (2019). continuous-úmme view of early stopping for least squares regression. In International Conference on Artificial Intelligence and Statistics.
[4] Anderson, W., Guionnet, A., and Zeitouni, O. (2010). An Introduction to Random Matrices. Cambridge University Press.

---

[5] Ando, R. and Komaki, F. (2023). On high-dimensional asymptotic properties of model averaging estimators. arXiv preprint arXiv:2308.04477
[6] Bach, F. (2023). High-dimensional analysis of double descent for linear regression with random projections. arXiv:2303.01372.
[7] Bahri, Y., Dyer, E., Kaplan, J., Lee, J., and Sharma, U. (2021). Explaining neural scaling laws. arXiv:2102.06701.
[8] Bai, Z. and Silverstein, J. W. (2010). Spectral Analysis of Large Dimensional Random Matrices. Springer. Second edition.
[9] Barthelmé, S., Amblard, P.O.., Tremblay, N., and Usevich, K. (2023). Gaussian process regression in the flat limit. The Annals of Statistics, 51 11)::24775
[10] Bartlett, P. I.., Long, P. M., Lugosi, G., and Tsigler, A. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117448)30003-30070
[11] Bartlett, P. L., Montanari, A., and Rakhlin, A. (2021). Deep learning: A statistical viewpoint. Acta Numerica, 30:87-201.
[12] Belkin, M., Hsu, D., and Xu, J. (2020). Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 167):116
[13] Bellec, P., Du, J.-H., Koriyama, T., Patil, P., and Tan, K. (2023). Corrected generalized cross-validation for finite ensembles of penalized estimators. arXiv preprint 10.01:2310.01374.
[14] Bordelon, B., Canatar, A., and Pehlevan, C. (2020). Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning.
[15] Cébron, G., Dahlqvist, A., and Gabriel, F. (2022). Freeness of type B and conditional freeness for random matrices. arXiv preprint arXiv:2205.01926.
[16] Chen, X., Zeng, Y., Yang, S., and Sun. Q. (2023). Sketched ridgeless linear regression: The role of downsampling. In International Conference on Machine Learning.
[17] Clarté, L., Vandenbroucque. A., Dalle, G., Loureiro, B., Krzakala, F., and Zdeborová, L. (2024). Analysis of bootstrap and subsampling high-dimensional regularized regression. arXiv preprint 2xXv:22402133622
[18] Couillet, R. and Liao, (2022). Random Matrix Methods for Machine Learning. Cambridge University Press.
[19] Cui, H., Loureiro, B., Krzakala, F., and Zdeborová, L. (2021). Generalization error rates in kernel regression: The crossover from the noiseless noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143.
[20] Dobriban, E. and Sheng. Y. (2020). Wonder: Weighted one-shot distributed ridge regression in high dimensions. Journal of Machine Learning Research, 21(66):1-52.
[21] Dobriban, and Sheng, (2021). Distributed linear regression by averaging. The Annals of Statistics, 49(2))918-944
[22] Dobriban, E. and Wager, S. (2018). High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279.
[23] Drineas, P., Mahoney, M. W. and Muthukrishnan, (2006). Sampling algorithms for la regression and applications. Proceedings of the ACM-SIAM Symposium on Discrete Algorithm.
[24] Du, J.-H. and Patil, P. (2023). Python package Biream__nssemll_ccm cv v0.2.1. PyPI.
12

---

[25] Du, J.-H., Patil, P., and Kuchibhotla, A. K. (2023). Subsample ridge ensembles: Equivalences and generalized cross-validation, In International Conference on Machine Learning.
[26] Du, J.-H., Patil, P., Roeder, K., and Kuchibhotla, A. K. (2024). Extrapolated cross-validation for randomized ensembles. Journal of Computational and Graphical Statistics.
[27] Efron, (1983). Estimating the error rate of a prediction rule: improvement on cross-validation. Journal of the American Statistical Association, 78(382):316-311
[28] Efron, B. (1986). How biased is the apparent rate of prediction rule? Journal of the American Statistical Association, 81 (1(344):461-470
[29] Ghorbani, B., Mei, S., Misiakiewicz, T., and Montanari, A. (2020). When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems.
[30] Hastie, Montanari, A., Rosset, S., and Tibshirani, (2022). Surprises in nigh-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986.
[31] Hastie, T. and Tibshirani, R. (1990). Generalized Additive Models. Chapman & Hall.
[32] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR).
[33] Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization neural networks. Advances neural information processing systems.
[34] Jacot, A., Simsek, B.. Spadaro, F., Hongler, C., and Gabriel, F. (2020). Kernel alignment risk estimator: Risk prediction from training data. Advances in Neural Information Processing Systems.
[35] Koehler, F., Zhou, L.,, Sutherland, D. J., and Srebro, N. (2021). Uniform convergence of inter- polators: Gaussian width, norm bounds and benign overfitting. Advances in Neural Information Processing Systems.
[36] Krogh, A. and Sollich, P. (1997). Statistical mechanics of ensemble learning. Physical Review E, 55(6):811.
[37] LeJeune, D., Javadi, H., and Baraniuk, R. (2020). The implicit regularization of ordinary least squares ensembles. In International Conference Artificial Intelligence and Statistics.
[38] Leleune, D., Javadi, H., and Baraniuk, R. G. (2021). The flip side of the reweighted coin: Duality of adaptive dropout and regularization. Advances in Neural Information Processing Systems.
[39] LeJeune, D., Patil, P., Javadi, H., Baraniuk, R. G., and Tibshirani, R. (2024). Asymptotics of the sketched pseudoinverse. SIAM Journal on Mathematics of Data Science, 6(1):199-22 -255.
[40] Liang, T. and Rakhlin, A. (2020). Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics.
[41] Liao, Z. and Mahoney, M. W. (2021). Hessian eigenspectra of more realistic nonlinear models. In Advances in Neural Information Processing Systems, volume 34.
[42] Liu, S. and Dobriban, E. (2020). Ridge regression: Structure, cross-validation, and sketching. In International Conference on Learning Representations.
[43] Loureiro, B., Gerbelot, C., Cui, H., Goldt, S., Krzakala, F., Mezard, M., and Zdeborova, L. (2021). Learning curves of generic features maps for realistic datasets with teacher-student model. In Advances in Neural Information Processing Systems.
13

---

[44] Mahoney, M. W. (2011). Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning,
[45] Mallinar, N., Simon, J. B., Abedsoltan, A., Pandit, P., Belkin, M., and Nakkiran, P. (2022). Benign, tempered, or catastrophic: A taxonomy of overfitting. arXiv:2207.06566
[46] Mei, S. and Montanari, A. (2022). The generalization error of random features regression: Pre- cise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766.
[47] Mingo, J. A. and Speicher, R. (2017). Free Probability and Random Matrices, volume 35. Springer.
[48] Nakkiran, P., Venkat, P., Kakade, S. M., and Ma, T. (2021). Optimal regularization can mitigate double descent. In International Conference on Learning Representations.
[49] Neu, G. and Rosasco, L. (2018). Iterate averaging as regularization for stochastic gradient descent. In Conference On Learning Theory.
[50] Patil, P. and Du, J.HH. (2023). Generalized equivalences between subsampling and ridge regularization. Advances Neural Information Processing Systems.
[51] Patil, P., Du, J.-H., and Kuchibhotla, A. K. (2023). Bagging in overparameterrzed learning: Risk characterization and risk monotonization. Journal of Machine Learning Research, 24(319):1-113.
[52] Patil, P., Du, J.-H., and Tibshirani, J. (2024). Optimal ridge regularization for out-of- distribution prediction. arXiv preprint arXiv:2404.01233.
[53] Patil, P., Kuchibhotla, A. K., Wei, Y., and Rinaldo, A. (2022). Mitigating multiple descents: A model-agnostic framework for risk monotonization. arXiv preprint arXiv:2205.1290
[54] Patil, P. and LeJeune, D. (2024). Asymptotically free sketched ridge ensembles: Risks, cross- validation, and tuning. In International Conference Learning Representations.
[55] Paul, D. and Aue, A. (2014). Random matrix theory statistics: review. Journal of Statistical Planning and Inference, 150:1-29.
[56] Rahimi, A. and Recht, (2007). Random features for large-scale kernel machines. Advances in neural information processing systems, 20.
[57] Sahraee-Ardakan M., Emami, M., Pandit, P., Rangan, S., and Fletcher, A. K. (2022). Kernel methods and multi-layer perceptrons learn linear models in high dimensions. arXiv preprint arXiv:2201 220002200..
[58] Serdobolskii, I. (2007). Multiparametric Statistics. Elsevier.
[59] Slagel, T., Chung, J., Chung, M., Kozak, D., and Tenorio, (2019). Sampled tikhonov regularization for large linear inverse problems. Inverse Problems, 35(1 1):1 14008.
[60] Sollich, P. (2001). Gaussian process regression with mismatched models. Advances in Neural Information Processing Systems, 14.
[61] Sollich, P. and Krogh, A. (1995). Learning with ensembles: How overfitting can be useful. In Advances in Neural Information Processing Systems.
[62] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R. (2014). Dropout: simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1):1929 15()):1929-1958
14

---

[63] Stein, C. M. (1981). Estimation of the mean of multivariate normal distribution. The Annals of Statistics, pages 1135-1151.
[64] Voiculescu, D. V. (1997). Free Probability Theory. American Mathematical Society.
[65] Wager, S., Wang, S., and Liang, P. S. (2013). Dropout training adaptive regularization. In Advances Neural Information Processing Systems.
[66] Wei, A., Hu, W., and Steinhardt. J. (2022). More than a toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning.
[67] Weisberg, S. (2005). Applied Linear Regression. John Wiley & Sons.
[68] Yang, G. (2019). Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04700 04760..
[69] Yosinski, J., Clune, J., Bengio, Y., and Lipson, H. (2014). How transferable are features in deep neural networks? In Advances Neural Information Processing Systems.
[70] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, (2017). Understanding deep learn- ing requires rethinking generalization. In International Conference Learning Representations.
[71] Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115.
15

---

Appendix
This serves as an appendix to the paper "Implicit Regularization Paths of Weighted Neural Represen- tations." The beginning (unlabeled) section of the appendix provides organization for the appendix, followed by summary of the general notation used in both the paper and the appendix. Any other specific notation explained inline where it is first used.
Or Organization
In Appendix A, we provide brief technical background on free probability theory and various transforms that we need and collect known asymptotic ridge equivalents that we use in our proofs.
In Appendix B, we present proofs the theoretical results in Section 3 (Theorems and 2 and Propositions 3-5).
In Appendix C, we present proofs of the theoretical results in Section (Theorem and Proposition 7).
In Appendix D, we provide additional illustrations for the results in Section 3 (Figures and 6).
In Appendix E, we provide additional illustrations for the results in Section (Figures 7-9), including our meta-algorithm for tuning (Algorithm 1) that is not included in the main text due to space constraints.
In Appendix F, we provide additional details on the experiments in both Section and Section 4.
Notation
We use blackboard letters to denote some special sets: N denotes the set of natural numbers, IR denotes the set of real numbers, R.+ denotes the set of positive real numbers, denotes the set of complex numbers, C+ denotes the set of complex numbers with positive imaginary part, and C- denotes the set complex numbers with negative imaginary part. We use [n] to denote the index set .1......,.).
We denote scalars and vectors using lower-case letters and matrices using upper-case letters. For a vector B. 3 denotes its transpose, and ||A1|| denotes its la norm. For a pair of vectors and v, (u, v) denotes their inner product. For a matrix X E RXx,, X E RPx* denotes its transpose, and X 1 Rex= denotes its Monrr-e inverse. For a square matrix E Rexp, tr[A] denotes its trace, tr[A] denotes its average trace tr tr/p//p and A-1 denotes its inverse, provided that A is invertible. For symmetric matrix A, X (A) denotes its minimum nonzero eigenvalue. For positive semidefinite matrix G, G²/² denotes its principal square root. For matrix X, we denote by | olop its operator norm with respect to the lg vector norm. is also the spectral norm of X. For a matrix X, we denote by X [|r its trace norm. is given by tr((X X)22), and also the nuclear norm X. We denote p identity matrix by Ip. simply by I when it is clear from the context.
X
For symmetric matrices and B, we use A < to denote the Loewner ordering to mean that A - B is positive semidefinite matrix. For two sequences of matrices Ap and B,. we use Ap = B, to denote a certain asymptotic equivalence; see Appendix A.3 for a precise definition.
A Technical background
A.1 Basics of free probability theory
In this section, we briefly review definitions from free probability theory and its applications to random matrices. This review will help set the stage by introducing the various mathematical structures and spaces we are working with. It will also introduce some the notation used throughout the text.
Free probability is mathematical framework that deals with non-commutative random variables [19]. The use of free probability theory has appeared in various recent works in statistical machine learning, including [1, 2, 11, 12, 17]. Good references on free probability theory include [3, 13], from
16

---

which we borrow some basic definitions in the following. All the material in this section is standard free probability theory and mainly serves to keep the definitions self-contained.
Definition 8 (Non-commutative algebra). A set A is called (complex) algebra (over the field of complex numbers ()) if vector space (over C with addition +), equipped with bilinear multiplication such that for all r, y, 2 E AA and C,
(I) (y 2) (x y)
(2) (z + 2 = 2 2.
(3) x. (y+ = x + x.22
(4) a(x y) (axr) y = x (ay).
In addition, am algebra called unital a multiplicative identity element exists. We will use 1 to denote this identity element. We will drop the "." symbol denote multiplication
the algebra. Definition 9 -oonmommuutative probability space). Let A over C be a unital algebra with identity 1A- Let y A + C be linear functional which is unital (that is, (p(1a) 1). Then (A, (p) is called a commutattee probability space, and y is called a state. A state is said to be tracial (p(ry) - ((Y=) for all v,, A.
Definition 10 (Moments). Let (A: (p) be a non-commutative probability space. The numbers {}<<"))}== are called the moments of the variable x E A. Definition 11 (*-algebra). An algebra A is called a *-algebra if there exists a mapping r + x² from A such that, for all x, y E A and a E C.
(1) (x + y)" x² + y.
(2) (ax)" ā.""
(3) (xy))* yf"
(4) (x*)*
variable of x-algebra is called self-adjoint if x² A unital linear functional y on +-algebra is said to be positive if <p("x>) x) 2 0 for all x E A. Definition 12 (=-probability space). Let A be unital +-algebra with positive state p. Then (A, sp) called a x-probability space.
Example 1. Denote by MM(C) the collection of all p matrices with complex entries. Let the multiplication and addition operations be defined in the usual way. The --operation is the same as taking the conjugate transpose. Let tr (M) + C be the normalized trace defined by:
tr (A) = tr(A].
p
The state tr is tracial and positive.
Definition 13 (Free independence). Suppose (A, ()) is a s-probability space. Then, the s-sub- algebras {Ai)xer of A are said be +-freely independent (or simply *-free) if, for all 2 2 and all I1, T2, TIn from {A, hee. Kn, Ø2. 2n.) = 0 whenever at least two of the x, are from different A,, In particular, any collection of variables is said to be *-free if the sub-aluee sub-algebras generated by these variables are s-free.
Lemma 14. Suppose (A, :p) is s-probability space. If and y are free in (A,,p), then for all non-negative integers n and m,
"(x")") = ((("")(("")))))))))) = x()"""").
In other words, elements of the algebra are considered free if any alternating product of centered polynomials is also centered.
In this work, we will consider to be the normalized trace. The normalized trace is the generalization of 1 tr(A] for A CP elements of C* -algeeebra A. Specifically, for any self-adjoint A and p any polynomial p. we have
((p(a))
p(2) d[a(2)) d/=222
17

---

where Ha is the probability measure that characterizes the spectral distribution of a. Definition (Convergence spectral distribution). Let (A, ip) be a C* probbbiiiyyy space. We say that AI, ..,.... Am E CPxP converge in spectral distribution to elements di, ".,..., Um E A if, for all 1 S l < do and S ig S m 1 S j S E, we have
tr tr .. Aud + ((ai).....) ... .11)) p
Then, with slight abuse of notation, two matrices A, B E Rpxp are said to be free if
L II poly? (A)poly B 0,
1 tr
for all L 2 1 and all centered polynomials, that is, tr(poly& A (A)) O. This notation is an abuse of notation because finite matrices cannot satisfy this condition. However, they can satisfy asymptotically
- oo, and in this case, we say that A and B are asymptotically free.
Note: With some abuse of notation, will let matrices in boldface denote both the finite matrix and the limiting element in the free probability space. The limiting element can be understood, for example, bounded linear operator Hilbert space. We also remark that all notions need are well-defined in this limit as well, as long as they are appropriately normalized.
A.2 Useful transforms and their relationships
In this section, we review the key transforms used in free probability theory and their interrelation- ships.
Definition 16 (Cauchy transform). Let be an element of a x-probability space (A, Suppose there exists some C' > such that [p(a") & C" for all n E N. Then the Cauchy transform of is defined
(a")
Ga (a)=)= =
1
n=
for all = E C with |=| C.
Note that the Cauchy transform is the negative of the Stieltjes transform. In this paper, we will focus only on the Cauchy transform. Recall that for a probability measure v on R and for & & R, the Cauchy transform of is defined as:
g(=) - do(x). _dd((
1
The definition above is motivated by the following property of the Cauchy transform of measure. Suppose is a probability measure whose support is contained in [-C, C*) for some C' >> 0 and which has moments (ml (v)) Then the Cauchy transform of v is defined for with |a| C as:
(x
(x(2)
k=0
Definition 17 (Moment generating function). Let a be an element of a +-probability space (A, 4). The moment generating function of is defined as:
Ma(z) =1 Σ )(
Rm/
for 2 E C such that [2| < Ta- Here, ra is the radius of convergence of the series.
For probability measure the moment generating function is defined analogously. (Note: The definition above is not to be confused with the moment generating function of random variable in probability theory.) The Cauchy transform is related to the moment series via:
1 MM z
Gz(z)
(13)
18

---

In the other direction, we have:
Ma(z) Ga (
(14)
Definition (S tS-nrsoffrr) For
Ma(z) Σ p(aa"))²"
m==
define the S-transform of a by:
1 1 w ! (w), Sa (w)
M
(15)
w
where ( denotes the inverse under composition of M.
Finally, in terms of operator A. we summarize the series of invertible transformations between the various transforms introduced in this section.
Cauchy transform:
G^(z) = TT((ZT A)
Moment generating series:
MA(z) - (1)
2
S-transform:
1+ M 1 (w). S^(W)
w
Here:
-Ma())= - ( is the moment generating series.
.M denotes the inverse under composition of MM.-
Tr [|] denotes the average trace tr [AA/pp of matrix A RexP.
A.3 Asymptotic ridge resolvents
In this section, we provide a brief background on the language of asymptotic equivalents used the proofs throughout the paper. We will state the definition of asymptotic equivalents and point useful calculus rules. For more details, see [16, Appendix S.7J.
To concisely present results, we will use the framework of asymptotic equivalence [5, 6, 16], defined as follows. Let A, and B, be sequences matrices of arbitrary dimensions (including vectors and scalars). We say that Ap and Bp are asymptotically equivalent, denoted as A. B,,. limp-+ trp bounded trace norm that are independent of Ap and Bp. Note that for sequences of scalar random variables, the definition simply reduces to the typical almost sure convergence of sequences of random variables involved.
Bp)]l = O almost surely for any sequence of random matrices Cp with
The notion deterministic equivalents obeys various calculus rules such as sum, product, differenti- ation, conditioning, and substitution. We refer the reader to [16] for a comprehensive list of these calculus rules, their proofs, and other related details.
Next, we collect first- and second-order asymptotic equivalents for sketched ridge resolvents from [11, 17], which will be useful for our extensions weighted ridge resolvents.
Assumption B (Sketch structure). Let S RRxx be the feature sketching matrix and X E RRax be the data matrix. Let SST and 1 X X converge almost surely to bounded operators that π
are infinitesimally free with respect to (1 tr[:), (r))(.))) for any θ independent of S with | uniformly bounded. Additionally, let SS have a limiting S-transform that analytic on the lower half of the complex plane.
19

---

For the statement to follow, let define Σ = , X. Let X == : lim inf min (S' ES). Here, recall that X min (A) represents the minimum nonzero eigenvalue of symmetric matrix A.
Theorem 19 (Free sketching equivalence; [11], Theorem 7.2). Under Assumption B, for all X Xo.
S(S ES AT ~ (E+11p)
(16)
where v > -X (E) is increasing in À > do and satisfies:
== ASss (- (- ES ST)) = ASSS (-T + II)
(17)
Lemma 20 (Second-order equivalence for sketched ridge resolvents; [17], Lemma 15). Under the settings of Lemma 21, for any positive semidefinite T with uniformly bounded operator norm, for all Ao.
A
S(S' ES + ST) S SSS S1,''ST = + (++I)) 1 +V++) +up)'
(18)
where 1/2 2 0 is given by:
dv
1/4 ax
(- + (1)) / +
(19)
B Proofs in Section
B.1 Proof of Theorem 1
Our main ingredient in the proof is Lemma 21. We will first show estimator equivalence and then show degrees of freedom equivalence.
Estimator equivalence. Recall from (1) the ridge estimator on the weighted data
iw. = ① W W + AIP) s W Wy/n.
This is the "primal" form of the ridge estimator. Using the Woodbury matrix identity, we first write the estimator into its "dual" form.
Bw. T W W W /n AI.) 'yyn
= + T W (Gw + AI Wy/n.
Now, we can apply the first part of Lemma 21 to the matrix WT(Gr + W From (31), we then have the following equivalence:
Bw. ~ + T (G + μI,) /
$ ( + μIn)) y/n
=( 1 /n + μIر) + TTyyl y/n Br,,.
where μ satisfies the following equation:
tr Gr (
XSWTW
(-
Note that the simplification, we used the Woodbury identity again to go back from the dual form into the primal form for the ridge estimator based on the full data. Rearranging, obtain the desired estimator equivalence. We next move on to showing the degrees of freedom equivalence.
Degrees of freedom equivalence. For the subsampled estimator Bw.x. the effective degrees of freedom is given by: df(Bw.,) tr t $/n( +
4/n XI,) $]
= ( T TT/n XI g /n] ttr(( / / AI कΦ /n]
20

---

The second equality above follows from the push-through identity Φ 2 + 1 (# + XI,)) $ Recognizing the quantity inside the trace as the degrees of freedom of the full ridge estimator, we have
== ASWTWS (
We can equivalently write the equation above as
-S w
,r. or
p
Rearranging the display above provides the desired degrees of freedom equivalence and finishes the proof.
B.2 Proof of Theorem 2
We will apply Theorem the subsampling weight matrix W. The main ingredient that need is the S-transform of the spectrum of the matrix W W. As summarized in Appendix A.2, one approach compute the S-transform is go through the following chain of transforms. First, we apply the Cauchy transform, then the moment-gente generating series, and finally, take the inverse to obtain the S-transform. We will do this in the following steps.
Cauchy transform. Recall that the Cauchy transform from Definition 16 can be computed as:
GwTw(2) tr((zIn - W w)-
Moment generating series. We can then compute the moment series from Definition using (14) as follows:
MW (2) (2) 1 tr ( -
w W) -11
-
=Ti(In zW ( - [r(A,]
= =-F[[A, + (T - -w -WW-
= =ti(::W W I, + I,) 2W TWT w)
=t[[2W W(I, =w -WT
now note that the matrix W T W has & eigenvalues of and n eigenvalues of 0. Therefore, we have
Mwtw (2) = tr/2W W (In - -w TWTWw w)
zd2
- 2dg
2
(20)
1
S-transform.
The inverse of the moment generating series map + MwT werw(22 (2) from (20) is:
M (1-1) (w)
w
(21)
k/n
Therefore, from Definition 18 and using (21), we have
1
+
S(w)
(22)
w w
k/n
w + k/n
Now, we are ready to apply Theorem to the subsampling matrix W. Substituting (22) into (2), we get
- S( ((-dF(BI,.)) = -F.( + k/n
/
21

---

Rearranging, we obtain
(f (u- X) = p (k/n) X.
Thus, we get
df(Br,.) = d p (k/m)
p- X
In other words, we have
- df(
(1-=)
Multiplying (1 p/2) on both sides, we arrive at the desired relation. This completes the proof.
B.3 Proof of Proposition
We prove this by matching the path (4) with the one in [15]. Let p/n, 2b = p/k, Hp be the spectral distribution of Σ x X X/n. The path from Equation (5) [15] is given by the following equation:
/
= (46 1)
+ u(,, dHp(r),
(23)
where v(14,) 7) is the unique solution to the following fixed-point equation:
v(w,7) = + I+ u(, y)r dl) = +b/ I+v(u,)) dH,(r).
(24)
For given y and ns, we will show that s that solves (23) gives rise hs p/vb that also solves (4) with À = 0:
tr ( (xxXT= + +u 1
Rearranging the above equation yields:
k =1
+ pI,) = --o((,, 7),
n
where the second equality is from Lemma B.2 of [15]. This implies that
k
1
v(,,7)
k
vb ʃ
r
dH,(r)
n
1 v(u, 7)r
/
(tb - 7)
1 1 1+u(,,7) 7)r dHp(r),
where the second equality follows from (24). The above is the same as the path (23) in [15]. This finishes the proof.
Proof of Proposition B.4
We first describe the setup for the kernel ridge regression formulation and then show the desired equivalence.
Setup, Let K(.,) Rd d + R be kernel function. Let H. denote the reproducing kernel Hilbert space associated with kernel K. Kernel ridge regression with the subsampling matrix W solves the following problem with tuning parameter
0:
iw = argmin [Wy y - W + + JEH
where f(x) [(,)) expression:
Kernel ridge regression predictions have closed-form
fw.)(x) = K)x,X) W (WW((X,XWW + +
22

---

Here, ((x E R" with i-th entry ax,, and (XX R with the ij-th entry (x,,,))
The predicted values on the training data X are given by (x) = K(X, T W (WK(X, X)WT + +
Here, the matrix K(X, X) W (WK(X, X + + W is the smoothing matrix.
Define G2 = K ( x) and Gw = (X(X, X)WT. Leveraging the kernel trick, the preceding optimization problem translates into solving the following problem (in the dual domain):
Yw. argmin a (Gw + Xla) 20 Wy.
.ER"
where the dual solution given by xw,i (Gw + AI,) kyy The correspondence be- tween the dual and primal solutions is simply given by: Bw,y = T W /w where $ (é(x))..... ((xn)] is the feature matrix and Φ: Rd + H is the feature map of the Hilbert space H with kernel K. Thus, (w, W #/3 w W ā Gw (GWWw W and the degrees of freedom is given by df (f tr[Gw + !.
Next, we show that (3) holds. Alteraatvelyy one can also show that
Yw, = āT, and [wo) (wo):
which we omit due to similarity. Our proof strategy consists of two steps. We first show that it suffices establish the desired result for the linearized version. We then show that we can suitably adapt our result for the linearized version.
Linearization of kernels. In the below, we will show that for μ O.
WT A (G, nI,)* T[\(Gw + XI, +
where W and A 2 0 satisfy that
= ASw w (r AI) = ASW wwww(( w
w triG (Gw + II,, (25)
Using assumptions of Proposition and the assumption in Proposition 4, by [18, Proposition 5.1],
| Glinllp & 0,
where
= col, + ca 1. + XX
and (co, C1, 02) associated with function in Proposition 4 and = limp tr|E//p are defined as
- -(,,0,7)))) tr Σ
(26)
p
tr = 9(T,0,7) (T,
1
(27)
2p²
22 ==
(28)
Assume C, is sequence of random matrices with bounded trace norm. Note that
+ - (Glin + [Im)))]]
< + (Gli + Ill)) <
+ pJ,) llo G.
|lua ||op _>, 0.
Assumption Al of [18] requires finite 5 + 6-moments, which can be relaxed to only finite + 5 6-moments as in the assumption of Proposition 3, by truncation argument the proof of Theorem 6 of [7, Appendix A.4].
23

---

where in the last inequality, we use a matrix identity A - AB A)B -1 for two invertible matrices and B. Thus, we have
(Gr + plm) =p (G) + jum)
(29)
Hence, combining (29) and the transition property of asymptotic equivalence [15, Lemma S.7.4 (1)) suffices to show
W (GW AI,)) W (GT + ,
where G WG WT, and and y satisfy (25). Similarly, we can also show that the path (25)
asymptotically equivalent to
/ ==>STTW (- (- (G +1, ASw w tr G (GW )I,)
(30)
Equivalence for linearized kernels. We next show that the resolvent equivalence result holds for K This follows from additional manipulations building on Lemma 21.
B.5 Proof of Proposition
In the below, we will show that for μ 2 O.
WTW (W T /n + AI W = (44 pk,) )t tr(A D W / AI,) ) ( /n + nk,)
Under assumptions in Proposition 5, the linearized features take the form
S
PX
U
where the constants Ps and w, are given in Proposition 5 and U E Raxp has i.i.d. standard normal entries. From Claim A.13 of [10], the linear functionals of the estimators BD.A and BI,,, with random features o and o asymptotically equivalent. Now, following the proof of Proposition 4, apply Lemma on lin to yield the desired result.
B.6 Technical lemmas
In preparation for the forthcoming statement, define Àg = = lim inf, x (Gw). Recall the Gram matrices G = 4 /nn and Gw = W W W WT/n.
Lemma 21 (General first-order equivalence for freely subsampled ridge resolvents). For R suppose Assumption A holds for WW Then, for all À > Au.
w W (Gw + A ~ (G)+HI+:
(31)
G[\(Gw + AL,) = TT +..+) uI,)'),
(32)
where μ -X+ (G) solves the equation:
# XSwwr (- [TG + #V)")) ASww (- [r[ (Gw +V)))).
(33)
Proof of Lemma 21. The first result follows from using Theorem 19 by suitably changing the roles of and &. In particular, we to be X T and W be S and apply Theorem 19 to obtain
W ( W /n + ) W
(#4 T // =
(34)
Writing in terms of G and Gw, this proves the first part (31).
For the second part, we use the result (34) in the first part and multiply both sides by Φ T /n to get
( T //)n W (W W /n + AI,) A W ~ ( T /nn ($$ T /n "Im)
Using the trace property of asymptotic equivalence [15, Lemma S.7.4 (4)), we have
iz| ( T /n) W (Woe W /n AI w ~ ( ( ($0 /n + pIn)
24

---

Using the cyclic property of the trace operator yields
tr((W ④ /n) W W W /n + AI, = tr ($ /n) ($6 /n + pI,)"
In terms of G and Gw, this is the same as G + AI,'" | G
Adding and subtracting AI, and pln, on the left- and right-hand resolvents, arrive at the second part (32). This completes the proof.
C Proofs in Section 4
C.1 Proof of Theorem
The main ingredients of the proof are Lemmas 21 and 22. We begin by decomposing the unknown response yo into its linear predictor and residual. Specifically, let Bo be the optimal projection parameter given by Bo = En E[@usol, Then, we can express the response as the sum of its best linear predictor, Φ Bo, and the residual, yo - Φ Bo. Denote the variance of this residual by of = [Uo Φū }O) It is easy to see that the risk decomposes as follows:
R(Bw = [( - @0 (...))) L. y, ( [=
(Bw Bo) E(3 Bo) + o..
Here, we used the fact that (wo 10 (o) is uncorrelated with Φo. that is, E[ (T Op- note that [1,ol|2 < oc and Eg has uniformly bounded operator norm.
Observe that
R(Bw = (Bwi. - Bo)
-Bo) + a
1
Σ Bw
30)
En
1
Σ
Bw... (00 o
M
M
M
2
Σ
Bw.. EnBW...
30 DoBw... + +.30 En.3o + o
M2
M
k,t=1
1
Σ
(B Do.wi.A - 3n.3,r) + 11 Eo,3r,1
M
k,4=1
M
3o Eg Ee,Bw.. + B En.B + o6.
M
m=1
By Lemma 21, note that
Bwmid Br.
M
Thus, we have
R(Brarn))
Bw EoGWe.. BT,,, Ei,Br..)
M
k
2
+ B 3n
Σ M m=
Eo, + 33, Eo,3o og.
Now, by two applications of Lemma 21, we know that W Eo,3,,A EOBI,. " 0 when 1: + E since Wa and W₁ are independent. Hence, we have
M
R(Bwi.a.N)
1
Σ
(B
- 3T, 3o. + (Br,,. -Br,-~36)* 36) 7 - 3o) + o
~
M2
m==1
25

---

= M (ww,, Io - -3 Eo + (BI Bo) Bo) Eo(3I, -Bo) + +
M ( 3T 1o + R(3
(35)
where we used the fact that the M terms where k = l converge identically in the second to last line and risk decomposition similar to that for SW in the last line. Thus, it suffices to evaluate the difference 3 Σn,3 3/. E to finish the proof.
We have
B WW EI,
= =(y W n W W /
2 ④ W W AI,) W (Wy/n)
(y Φ/n) 0 μI En 4/n+ + y/n)
-r(WW
W W
W W + AIp)
+ W W/n (vv }
/n- (yy )]
= (1tp:/11___((1000000000001111111
pIm) (gy
"1 (yy
- 21
+ 4 1r [ μل yy ($ [
- tr]( /n + ul 4 /n)
/n + pdn) (yy (yy)) >]
= =1$S [ + pI yy
4 + ,I,)
(36)
where in the third line, we used the second-order equivalence for freely weighted ridge resolvents from Lemma 22; in the fourth line, we employed the push-through identity multiple times. Substituting for ur' from Lemma 22 in (36) and substituting this back into (35), we arrive at the desired decomposition. This completes the proof.
C.2 Proof of Proposition? 7
We the path (4) with h- and μ², and setting X" 0:
df(Brr,u))
1 k"
This suggests that
h- = df.
Note that rank( X T trank (G7). By the definition of degrees of freedom, it follows that
df(3r,,') = tr X
X(XTX X + / I )1
< rank G1).
+ μ
i=1
where s1,,.,,8 Sy are non-zero eigenvalues of X X. This finishes the proof.
C.3 Technical lemmas
Recall from Appendix B.6 that we define A = lim inf Xt (W WT/n).
Lemma 22 (General second-order equivalence for freely weighted ridge resolvents). Under the settings of Lemma 21, for any positive semidefinite Eo with uniformly bounded operator norm, for all Ao:
1 w 1
T
W E
W W (I,) Tw W
26

---

= ( ( + +,In)( " + + [,)( T + pun)), (37)
where ur: is given by:
Ou X SwW 1 fr n 01
ΦΦ T ( (=
T + )
Lr [ T + ( + ( + +..))
(38)
Proof. We use the Woodbury matrix identity to write
WW T ( WW & + AI,) Lo( + WW $ + AI,) $ WWT
W W 4Φ W + Amm) W & W W 44 W Am W
The equivalence in (37) and the inflation parameter in (38) now follow from the second-order result for feature sketch by substituting W for S, & for & T and 1 _ for Eo (18).
27

---

D
Additional illustrations for Section 3
D.1
Implicit regularization paths for bootstrapping
Degrees of freedom
Gaussian
0.0
0.040
800
0.035
Ridge penalty
0.1
0.030
0.025
0.020
-400
200
10
0.0
0.1
1
0.0
0.1
Subsample ratio k/n
Subsample ratio k/n
Figure 5: Equivalence under bootstrapping. The left panel shows the heatmap of degrees of freedom, and the right panel shows the random projection Ew (a [w.x] where a ~ (O,,, In/)). In both heatmaps, the red lines indicate the predicted paths using Equation (4), and the black dashed lines indicate the empirical paths obtained by matching empirical degrees of freedom. Despite the complexity of the theoretical path for bootstrapping. we observe that the empirical paths closely resemble Therefore, the theoretical path for sampling without replacement from (4) serves as good approximation.
D.2 Implicit regularization paths with non-uniform weights
Degrees of freedom
Gaussian
0.0
0.012
33
0.000
Ridge penalty
0.1
0.008
0.006
1
0.004
5
10
0.0
0.1
0.0
0.1
Subsample ratio k/n
Subsample ratio k/n
Figure 6: Equivalence under non-um -n-uumiform weighting. The left panel shows the heatmap degrees freedom. and the right panel shows the random projection Ew(a [a. (]. where (diag( W)) for observations are initially generated as (9/10)² for 0..... a - 1, subsample & entries from zero out the other n & entries, and then normalized to have norm &. The black dashed lines indicate the empirical paths obtained by matching the empirical degrees of freedom.
(N,...
The weights
n... (1.....)).
28

---

E Additional illustrations for Section 4
E.1 Rate illustration for ensemble risk against ensemble size
A 0.01v
A 0.1v
10
Prediction risk
Prediction risk
Prediction rik
1=
Mi
20
100
100
Figure 7: Risk cquivalence for random feature structures when sampling without replacement. The solid lines represent the prediction risks and their estimates of the subsample ridge ensemble, and the red dashed lines indicate the prediction error of the full ridge predictor. The data and random features with the ReLU activation function are generated according full ridge is set as μ = 1, and subsampled ridge ensemble is fitted with M 100 randomly sampled subsampling matrices. For each value of X, the subsample ratio determined by solving Equation (4).
Appendix F. with 5000 and p 500. The regularization level for
E,2
Real data illustrations for implicit regularization paths
Degrees freedom
Training error
Prediction error
0.0
E000
Ridge Aenalty
1000
0.1
200
1.012
0325
1.009
200
0375
0.001
0.1
0.001
0.01
0.001
0.01
Subsample ratio
Subsample
Subsample ratio
Figure 8: Equivalence in pretrained features of pretrained ResNet-18 on CIFAR-10 dataset.
Degrees of freedom
Training error
Prediction emrrr
234
Ridge penally
0.08
-0.00
-0.5
10
0.001
0.001
0.01
Subsample ratio kin
Subsample ratio k/o
Subsample ratio kin
Figure 9: Equivalence in features of randomly initialized ResNet- Fashion MNIST dataset.
Pashion-MNIST
F Details of experiments
F1
Simulation details
The simulation settings are as follows.
Covariance model. The covariance matrix of auto-regressive process of order (AR(1)) is given by Σnr E Rdxd where (Earl)ig = p for some parameter Part E (0, 1). For the simulations, we set Par1 0.25.
29

---

Signal model. Define 3o = = () where (() is the eigenvector of Eari associated with the top jth eigenvalue r(J).
Response model. We generated data (a Us) Rd x IR for i I,...,, from nonlinear model:
,
iid to 05
yi - x. 2. Bo + [11:112 tr Ar(Earl)) + + a; arl Ris
Zij
8:
55
(M-ARI)
where O3 /5/3 is the standard deviation of distribution.
The benefit of using the above nonlinear model is that clearly separate the linear and the nonlinear components and compute the quantities of interest because Bo happens to be the best linear projection.
The linear, random, and kernel features are generated as follows.
Linear features. For given feature dimension p, we use linear features.
features from (M-ARI) as
Random features. For generating random features, we use 2p raw features from (M-ARI) and sample randomly initialized weight matrix F E Igxd whose entries are i..dd samples from d) Then the transform feature is given by æ; (FFx:)) E RP, where y is nonlinear transformation and set be ReLU function in our experiment.
Kernel features. For kernel features, we use d kernel matrix.
features from (M-ARI) to construct the
In the simulations, the estimates averaged across 20 simulations with different random seeds.
F22 Experimental details in Section 4.3
Following the similar experimental setup in [20], we use residual networks to extract features on several computer vision datasets, both at random initialization and after pretraining. More specifically, we consider ResNet-(18, 18, 34, 50, 101) applied to the CIFAR- 10, 100] [9], Aushion-MNISY [21], Flowers- 102 [14], and Food-10 101 [4] datasets. All random initialization was done following [8]; pretrained networks (obtained from Py Torch) were pretrained on ImageNet, and the outputs of the used as the embedding feature b
last pretrained layer each dataset mentioned above
After obtaining the embedding features from the last layer of the neural network model, we further normalize each row of the pretrained feature to have a norm of p. and center the one-hot labels to have zero means. To reduce the computational burden, we only consider the first 10 one-hot labels of all datasets. For datasets with different data aspect ratios, stratify 10% of the training samples as the training set for the CIFAR- 100 dataset. The training and predicting errors are the mean square enrors the training and test sets, respectively, aggregated over all the labels.
References
[1] Adlam, B., Levinson, J. A., and Pennington, J. (2022). A random matrix perspective on mixtures of nonlinearities in high dimensions. International Conference on Artificial Intelligence and Statistics.
[2] Adlam, B. and Pennington, J. (2020). The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization. In International Conference on Machine Learning.
[3] Bose, A. (2021). Random Matrices and Non-Commutative Probability. CRC Press.
[4] Bossard, L., Guillaumin, M., and Van Gool, L. (2014). Food-101-mining discriminative com- ponents with random forests. In Computer Vision-ECCV 2014: 13th European Conference. Springer.
30

---

Table 2: Summary of pretrained features from different real datasets.
Number of pretrained features
Number of train samples
Number of test samples
Dataset
Model
ResNet-18
60000
10000
512
init.
ResNet-18
CIFAR-10
50000
10000
512
pretr.
ResNet-50
CIFAR-100 (subset)
5000
10000
2048
pretr.
ResNet-50
Flowers-102
2040
6149
2048
pretr.
ResNet-100
Food-101
75750
25250
2048
pretr.
[5] Dobriban, E. and Sheng. Y. (2020). Wonder: high dimensions. Journal of Machine Learning Research, 21(66):1-52.
Weighted one-shot distributed ridge regression in
[6] Dobriban, E. and Sheng, Y. (2021). Distributed linear regression by averaging. The Annals of Statistics, (9(2)91189443
[7] Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. (2022). Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986.
[8] He, K., Zhang, X., Ren, S., and Sun, (2015). Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In International Conference on Computer Vision.
[9] Krizhevsky, A. and Hinton, G. (2009). Learning multiple layers of features from tiny images.
[10] Lee, D., Moniri, B., Huang, X., Dobriban, E., and Hassani, H. (2023). Demystifying disagreement-on-tte--iiin high dimensions. In International Conference on Machine Learning.
[11] LeJeune, D., Patil, P., Javadi, H., Baraniuk, R. G., and Tibshirani, R. J. (2024). Asymptotics of the sketched pseudoinverse. SIAM Journal Mathematics of Data Science, 6(1):199-225
[12] Mel, G. and Pennington, J. (2021). Anisotropic random feature regression in high dimensions. In International Conference on Learning Representations.
[13] Mingo, J. A. and Speicher, R. (2017). Free Probability and Random Matrices, volume 35. Springer.
[14] Nilsback, M.-E, and Zisserman, A. (2008). Automated flower classification over a large number of classes. In Indian Conference Computer Vision, Graphics and Image Processing.
[15] Patil, P. and Du, J.-H. (2023). Generalized equivalences between subsampling and ridge regularization. Advances in Neural Information Processing Systems.
[16] Patil, P., J., and Kuchibhotla, A. K. (2023). Bagging in overparameterized learning: Risk characterization and risk monotonization. Journal of Machine Learning Research, 24(319):1-113.
[17] Patil, P. and LeJeune, (2024). Asymptotically free sketched ridge ensembles: Risks, cross- validation, and tuning. In International Conference on Learning Representations.
[18] Sahraee-Ardakan M., Emami, M., Pandit, P., Rangan, S., and Fletcher, A. K. (2022). Kernel methods and multi-layer perceptrons learn linear models in high dimensions. arXiv preprint 2201:2201.08088
31

---

[19] Voiculescu, D. V. (1997). Free Probability Theory. American Mathematical Society.
[20] Wei, A.. Hu, W., and Steinhardt, (2022). More than a toy: Random matrix models predict how real-world neural representations generalize. In International Conference on Machine Learning.
[21] Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.0777 077447.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the claims made the abstract are justified by both theoretical and experi- mental results in Sections 3 and and the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The assumptions are discussed and explained after their first mention (either in Section right after the thcoretical result that uses them). The main limitations of the paper are discussed in the last section (Section 5).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
33

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions for each of the results are included in the main text, and the complete proofs for each of the results are included in the appendix. The beginning of the appendix provides an organization for the proofs of all the results mentioned in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code and instructions for reproducing experimental results in this paper are included in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
34

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use publicly available data. The code and instructions for reproducing experimental results in this paper included in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
mublic/guide /ttgg//d/////uuubbneeeee /woo/oobbiiisionnonoooooo ollicy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. wwtppcccccccc/ccccc /ttdggddiC///oeuumiiiiiii
CodeSubmisse wwwssssssliioooeeeooooooississii for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The experimental details are included in the appendix, and the source code is provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Docs the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The standard errors across multiple random seeds are included for Figure Note that for the heatmaps, only report the mean statistics because of visual constraints. However, the standard errors for the heatmaps are small enough not to impact the regulariza- tion paths indicated.
35

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The compute resources are described in the README file of the submitted code in the supplementary materials.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https http:://eeuuuueeeeee httpp//.......ttttetttceeaaaeaee
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
36

---

Answer: [NA]
The paper provides a theoretical analysis and does not have immediate societal impacts.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose any risks that require safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The paper correctly cites papers of related assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
37

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi wwwrsssithhheeee thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects
Guidelines:
38

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "BSgzaQe4ry", "reviewer": "Reviewer_cp5Y", "summary": "This paper investigates the implicit regularization effects of weighted pretrained features. It establishes a path of equivalence between different weighting matrices and ridge regularization with matching effective degrees of freedom. The study extends results to structured features and ensembles, providing theoretical validation for random and kernel features, and proposes an efficient cross-validation method to finetune subsampled pretrained representations in practice.", "questions": "- In Definition A, what's the precise definition of $\\overline{tr}(\\cdot)$? What does it mean by saying \"$W^\\top W$ and $\\Phi \\Phi^\\top/n$ converge almost surely to bounded operators\"? If it refers to the convergence as $n \\to \\infty$, then does it mean the analysis is conducted in the asymptotic regime?\n- In line 196, if (5) implies $\\lambda < \\mu$, isn't the regularization level $\\lambda$ of the subsampled estimator lower (instead of higher) than that of the full estimator $\\mu$?\n- It's somehow counter-intuitive that the equivalence path results depend only on the subsample fraction $k/n$ under the \"general\" data assumption. Common analyses in the asymptotic regime reduce data properties to the subsample ratio $k/n$ usually based on strong assumptions on the data distribution like Gaussian, while data-agnostic subsampling on adversarial data should bring inevitable compromise compared to full data (e.g., with a direction that is only learnable through a single data point). It seems that the \"infinitesimally freeness\" in Assumption A implicitly circumvents this issue, but it's unclear in the current discussion. For example:\n    - Whether Assumption A enforces a \"nice\" data distribution, a \"good\" subsampling strategy, or both?\n    - If Assumption A implies a \"good\" subsampling strategy, can such subsampling matrix $W$ be efficiently constructed in practice?", "limitations": "Limitations are well-discussed in the Conclusion. Some further limitations are mentioned in Weaknesses and Questions.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- Table 1 provides a clear overview of the previous works, along with the contributions and organization of this paper.\n- The theoretical results are comprehensive and strong in terms of relaxed assumptions on the features and weights.\n- The theoretical results bring insights into designing a practical cross-validation algorithm, whose effectiveness is supported by experiments.", "weaknesses": "- While Table 1 and the summary of results provide a relatively clear view of the theoretical contributions, the abstract and the motivation part of the introduction read somewhat confusing. For example, the \"path of equivalence\" is repeatedly mentioned in the abstract and introduction as one of the main contributions, but without a clear explanation/intuition of what it means until later.\n- The problem setup and notations are not clearly stated before being used. For example, in terms of setup, in Assumption A, it's unclear what the convergence refers to in \"$W^\\top W$ and $\\Phi \\Phi^\\top/n$ converge almost surely to bounded operators\". In terms of notations, $\\|\\cdot\\|_{tr}$ and $\\overline{tr}(\\cdot)$ are used without clear definitions for reference.\n- Overall, the layout of the results is a little bit hard to follow, partially due to the lack of clear problem setup and notations mentioned before, and partially due to presuming prior knowledge of specific technical tools like free probability theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouragement and comments! While we appreciate all the feedback, we believe that the main concerns raised are related to the clarity of exposition and can be easily addressed easily. Below, we address all the weaknesses and questions on a point-by-point basis.\nWe respectfully request that the reviewer reconsider the scores based on the technical contributions of the paper, which we believe are significant.\n\n**Weaknesses**\n\n- **[W1] Explanation/intuition of main contributions.**\nPath of equivalence refers to data-dependent set of weighted ridge estimators $(\\mathbf{W} , \\lambda)$ that connect to the unweighted ridge estimator $(\\mathbf{I}, \\mu)$ is defined in terms of \"matching\" effective degrees of freedom of component estimators in the set (see lines 161-163). This path allows us to relate the performance and properties of models fitted on full datasets to those fitted on subsampled datasets.  \nIn the Abstract (lines 7-9), we refer to it as \"a path of equivalence connecting different weighting matrices and ridge regularization with matching effective degrees of freedom.\" This is to keep the abstract within the recommended 4-6 lines. In the introduction (lines 39-41), we explain mathematically what a path means. Based on your feedback, we will add a line in the Abstract to even more clearly state what a path of equivalence means.\n- **[W2] Problem setup.**\nIn terms of problem setup, we explain the meaning of ``converge almost surely to bounded operators'' below. In free probability theory and random matrix theory, matrices as linear transformations are viewed as operators. A bounded operator is a linear transformation on a vector space where the magnitude of the output vector is bounded by a constant multiple of the magnitude of the input vector. In matrix terms, this means that the eigenvalues of the matrix are bounded. For us, this means that the maximum eigenvalues of the matrices $\\mathbf{W}^\\top \\mathbf{W}$ and $\\mathbf{\\Phi} \\mathbf{\\Phi}^\\top / n$ are almost surely bounded in the limit as $n \\to \\infty$. This is a standard assumption in free probability theory and keeps the estimators and their risks bounded in the limit.  \n- **[W2] Notational clarity.**\nAll the important notation in the paper is well-defined and exhaustive. We have an entire subsection of the Appendix on this (lines 552-580). Not all of this notation is in the main paper because of the page limit of 9 pages due to the space limit, but note that the meaning of $\\overline{tr}(\\cdot)$ is explained in the main paper (130-131). The notation of $tr(\\cdot)$, $\\overline{tr}(\\cdot)$, and $\\|\\cdot\\|_{tr}$ is defined on lines 572-573, 577. This notation is standard in the fields of random matrix theory and free probability theory.\nWhile we understand that not all readers will be familiar with these fields, it is not feasible for us to include every notation and definition in the main paper due to page limits, and hence, we added this in the Appendix. Based on your feedback, we will include a paragraph on notation in the main paper in our revision.\n- **[W3] Layout and accessibility of results.**\nThe Summary of Results (line 55-77) outlines the paper's contents: Section 2 covers preliminaries, Section 3 discusses implicit regularization paths and examples of weight and feature matrices, and Section 4 addresses prediction risk asymptotics, risk estimation, optimal tuning, and validation on real-world datasets. Section 5 concludes with limitations and outlook. We will add a separate organization section in the revised version.  \nTo aid readers unfamiliar with random matrix and free probability theories, Appendix A provides a self-contained background, including:\n  - Appendix A.1: Basics of free probability theory.\n  - Appendix A.2: Useful transforms and their relationships.\n  - Appendix A.3: Asymptotic ridge resolvents.  \n  \nAdvanced tools are necessary for such general results, and we try to make them accessible with Appendix A. We welcome additional suggestions from reviewers but we consider the use of tools from other fields in machine learning as a strength rather than a weakness.\n\n**Questions**\n\n- **[Q1] Definitions.** The definition of $\\overline{tr}$ is given in the notation paragraph (line 577) of the Appendix. See also our response to [W2]. The analysis in the current paper is indeed conducted in the asymptotic regime, in which the sequence of random matrices (with possibly growing dimensions) is indexed by $n$ (see lines 151-156).\n- **[Q2] Comparing regularization strength of subsample and full estimators.**\nWe thank the reviewer for pointing out the typo in wording. Indeed, the regularization level $\\lambda$ of the subsampled estimator is lower than that of the full estimator $\\mu$. We will correct this in the revised version.\n- **[Q3] Equivalence path results.** Thanks, this is a great question! \nCommon analyses in the asymptotic regime often rely on strong assumptions like Gaussian distribution, while our approach is more general. A key result is that equivalence paths are characterized by degrees of freedom.\n  - Assumption A does not require a \"nice\" *marginal* data and weighting distribution. But it relies on the \"infinitesimal freeness\" of the (data, weight) pair. Intuitively, for subsampling, it means that the pair needs to be \"sufficiently\" independent (in the limit). In particular, adversarial subsampling may not be permitted as such.\n  -  Yes. *Independent* random subsampling is easy to construct. In Section 3.2, we construct various examples that satisfy Assumption A. In general, it is also empirically satisfied on real data (as in Figure 3 and Appendix 3.2).\n\nGiven the significant technical contributions and the ease of addressing the reviewer's concerns, we kindly request the reviewer to reconsider the score. We will improve the presentation of the paper based on the feedback. We believe the technical contributions and practical relevance of our work merit a more favorable evaluation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FuwAO0l60B", "reviewer": "Reviewer_nM8u", "summary": "This paper studies the weighted linear regression problem where the feature matrix is left-multiplied with a random matrix $\\mathbf{W}$ denoting the sample weighting. Under the assumption of the asymptotic freeness between this weighting matrix and the feature matrix, the paper shows that the weighted ridge regression estimator is equivalent to a simple ridge regression estimator in the limit of infinite samples by establishing a connection between the regularization strengths of the weighted and the simple ridge regression. Based on this regularization path, the paper gives illustrative examples of concrete weighting matrix and feature matrix. Moreover, the paper also shows a equivalence between the risk of ensemble weighted and simple ridge regression under the same regularization path. Based on this result, the paper derives an optimal sub-sample size for the ensemble training. Theoretical results of this paper is accompanied by experimental verification.", "questions": "1. Are there any example in real-world applications where the weighting matrix is not a diagonal matrix?\n2. Based on the theoretical results in the paper, what would be the benefit of using a sub-sampling matrix with non-binary diagonal entries?", "limitations": "The paper has a good discussion of its limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper considers a general scheme where $\\mathbf{W}$ can be any random weighting matrix, which can generalize beyond the sub-sampling scenario. The assumption on the asymptotic freeness between the weighting matrix and the feature matrix is quite relaxed.\n2. The paper derives an exact relationship between the regularization of the weighted ridge regression and that of the simple ridge regression in the limit of $n\\rightarrow\\infty$. This relationship is verified by the experiments presented in the paper.\n3. The paper also derives the equivalence between risks of the ensemble weighted ridge regression and the simple ridge regression. The equivalence demonstrates a bias-variance trade-off and also validate the benefit of using a larger ensemble size.\n4. Although the results is based on sophisticated mathematical notions, the paper uses intuitive explanation to make the results more comprehensible by a broader audience.", "weaknesses": "1. The results derived in the paper has limited applicability. In particular, although it would be interesting to know the equivalence between the weighted ridge regression and the simple ridge regression, the regularization path does not tell much about how should we choose a weighting matrix, even assuming the optimal ridge regression regularization is known. Moreover, the optimal sub-sample size in Proposition 7 involves computing $\\mu^*$ which cannot be done easily. Although the paper discussed a way to measure $\\mu^*$, it is still computationally heavy, and even in the case where $\\mu^*$ is known, one might not be able to measure the degree of freedom easily.\n2. The paper considers an asymptotic regime where the sample size goes to infinity. The results in the paper will have better implications if a dependency on $n$ is given.\n3. The paper's result is derived under the ridge regression setting. Although one can always choose $\\Phi$ to be the output of some pre-trained neural network, the results barely connect to any property of neural network training.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and providing valuable suggestions!\nThank you also for the nice questions!\nWe appreciate all the feedback and have addressed the weaknesses and questions below.\n\n**Weaknesses**\n\n- **[W1] Practical applicability.** Both Theorems 1 and 2 provide \"data-dependent\" paths through path (2) and path (4), respectively. By fixing target regularization $\\mu$, one can compute the degrees of freedom of the full ridge estimator using training data (see line 149). This allows us to numerically solve for the path since the degrees of freedom of the weighted ridge estimator can also be computed using the same formula.  \nStatisticians have two hyperparameter choices: the type of weighting and the regularization level. We offer a method to tune these in Section 4.2, specifically for subsampling-based weighting, which can be generalized to other parameterized weighting schemes. The oracle optimal subsample size in Proposition 7 may include unknown parameters like $\\mu^*$, but for practical purposes, knowing these parameters is unnecessary.  \nThe equivalence implies one can fix a small regularization level and adjust the subsample size. The method in Section 4.2 leverages this, providing a data-driven way to tune the optimal subsample size. Although it requires fitting multiple models, these can be computed independently and distributed, reducing computational time. In Section 4.3, we apply this approach to real-world datasets (e.g., Figure 4) to predict explicit regularization matching the implicit regularization from subsampling.  \nWhen $\\mu^*$ is known, the situation simplifies. We can compute the degrees of freedom of the full ridge estimator at $\\mu^*$ and use the data-dependent path to find various weights and regularization levels that yield the optimal estimator.\n\n- **[W2] Asymptotic analysis.** We examine proportional asymptotic regimes where the sample size $n$, feature dimension $p$, and subsample size $k$ all tend to infinity, but their ratios $p/n$ and $p/k$ converge to constants. In this analysis, both data and weighting matrices are indexed by $n$, a common approach in random matrix theory. This asymptotic method simplifies proofs and highlights essential problem characteristics under minimal assumptions.  \nExtending our results to finite samples is possible but requires additional assumptions, as precise error bounds depend on the specifics of feature and response distributions. For subsampling weights, techniques from [KY17], [L22], [CM22], and [HX23] may yield non-asymptotic versions of some statements in our paper. However, for general weights satisfying the asymptotic freeness assumption, obtaining non-asymptotic results is challenging. This remains an active area of research in free probability theory.\n\n- **[W3] Relation to neural network training.** Our results are indifferent to the type of neural network training that proves advantageous. Other theoretical analyses link the generalization error of trained models to network properties and data distribution parameters (e.g., [JGH18], [AP20], [BMR21], [MM22]). For example, in random features regression, similar to a two-layer network with random first-layer weights, the generalization error depends on the distributional properties of the weights and the activation function. Although these analyses offer insights into how network properties affect generalization error, the risk expressions become complicated with additional layers.  \nOur work is different in style from these works. In particular, we do not analyze the risk of either the full model or the subsampled models in isolation. Instead, we relate these two sets of models, allowing us to maintain weak assumptions about the features. Note that it is possible to combine our equivalence results with the aforementioned line of work and this gives a way to port the insights from one model to other equivalent models.\n\n**Questions**\n\nSincere thanks for the great questions!\n\n- **[Q1] Non-diagonal weighting matrix.**  Observation sketching involves taking random linear combinations of the rows of the data matrix, resulting in a non-diagonal weighting matrix. This technique can be useful for privacy, scrambling identifiable information, or mitigating the effects of non-i.i.d. data in time series or spatial data. We will discuss the non-diagonal weighting matrix in our revision.\n    \n- **[Q2] Non-binary diagonal weighting matrix.** Even with subsampling, a non-binary diagonal weighting matrix is possible. For instance, sampling with replacement or a specific distribution results in non-binary diagonal weighting matrices, as illustrated in Figures 6 and 7 of the supplement. Other examples include inverse-variance weighting to address heterogeneous variations when responses have different variances for different units.\n\n**References**\n\n- [KY17] Antti Knowles and Jun Yin. Anisotropic local laws for random matrices. Probability Theory and Related Fields, 169:257–352, 2017  \n- [JGH18] Jacot, A., Gabriel, F., and Hongler, C. Neural tanget kernel: Convergence and generalization in neural networks. In NeurIPS, 2018.  \n- [AP20] Adlam, B.~ and Pennington, J. The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization. In ICML, 2020.\n- [BMR21] Bartlett, P., Montanari, A., and Rakhlin, A. Deep learning: A statistical viewpoint. Acta Numerica, 2021.  \n- [L22] Cosme Louart. Sharp bounds for the concentration of the resolvent in convex concentration settings. arXiv:2201.00284, 2022  \n- [CM22] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv:2210.08571, 2022.  \n- [MM22] Mei, S. and Montanari, A. The generalization error of random features regression: Precise asymptotics and the double descent curve. In Communications on Pure and Applied Mathematics, 2022.\n- [HX23] Han, Qiyang, and Xiaocong Xu. The distribution of Ridgeless least squares interpolators. arXiv preprint arXiv:2307.02044, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Iu167ClAAj", "reviewer": "Reviewer_HnNV", "summary": "Neural networks are a powerful tool for extracting features from data, but these features can be very high-dimensional. This high dimensionality can be a bottleneck for training machine learning models, requiring computational power and memory. This manuscript investigates implicit regularization through subsampling and draws a connection to weighted regression problems. The authors provide theoretical results for the claimed connection between implicit regularization via subsampling and regression. The authors provide numerical evidence of their investigations.", "questions": "see weaknesses.", "limitations": "yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The manuscript is well-written and provides an interesting insight into the connection between subsampling approaches and explicit regularization.", "weaknesses": "Some works have provided between subsampling and iterative least squares approaches, see Slagel et al., Sampled Tikhonov Regularization for Large Linear Inverse Problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their time and valuable feedback and acknowledging the strengths of our paper!\nThanks also for a nice reference pointer!\nBelow, we expand more on this reference and connections to our work.\n\n**Weakness** and **Question**\n\n- **[W1] and [Q1] Related work on iterative least squares.**\nWe thank the reviewer for pointing out this great relevant reference about the relationship between subsampling and iterative least squares approaches. We will definitely add the missing reference to the related work in our revision.  \nCompared to the work by [SCC+19], there are several differences (and some improvements) that our work offers:\n  - *Problem setup.* [SCC+19] show the equivalence between the iterates along the (randomly) subsampled iterative methods and full Tikhonov regularized estimator (also known as generalized ridge regression estimator). On the other hand, we show equivalence between the subsampled (and ensemble) weighted ridge estimators and ridge(less) estimators on full data (at a different regularization). It is definitely related but these are somewhat complementary directions.\n  - *Regime of interest.* [SCC+19] implicitly only analyze an underparameterized regime (where the sample size $n$ is required to be larger than the feature dimension $p$). This is because the data matrix is required to have full column rank, which will only happen in the underparameterized regime. Moreover, they only consider the target ridge estimator with $\\lambda > 0$. In comparison, our paper considers both underparameterized and overparameterized regimes (allowing for both $n > p$ and $n < p$). Furthermore, we also allow the target ridge with $\\lambda = 0$ (also known as ridgeless) and potentially negative $\\lambda$ as well.\n  - *Sampling strategies.* [SCC+19] only consider random subsampling matrices, which are akin to orthogonal matrices (in expectation). In comparison, our work allows for general weighting matrices that we assume to be asymptotically free from the data matrices.\n  - *Data model.* [SCC+19] assume a well-specified linear model. Our work does not assume any specific model for the response and only require finite average response energy (in the limit).\n  - *Types of equivalences.* [SCC+19] show the equivalence of the estimators in expectation (over the randomness in subsampling). On the other hand, we show asymptotic equivalences for both the estimators and quadratic risks that hold almost surely (over the randomness in weight and data matrices). In addition, we also establish entire (data-dependent) paths of equivalences for the weighted ensembled ridge estimators. \n\n**Reference**\n- [SCC+19] Slagel J. T., Chung, J., Chung M., Kozak D., and Tenorio L. Sampled Tikhonov regularization for large linear inverse problems. Inverse Problems, 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for taking the time to review our paper. We appreciate the constructive comments and valuable feedback.

All three reviewers have acknowledged several key strengths of our paper.

- Reviewer **cp5Y** liked the clear overview of previous works provided in Table 1, the comprehensive and strong theoretical results with relaxed assumptions, and the practical insights from our theory that lead to an effective cross-validation algorithm.
- Reviewer **nM8u** highlighted the generality of our results, the relaxed assumptions on asymptotic freeness that our results require, the exact relationship established between the implicit regularization effects, and the comprehensible presentation despite sophisticated mathematical theory.
- Reviewer **HnNV** appreciated the well-written manuscript, the interesting insights into the connection between subsampling approaches and explicit regularization, and the theoretical (for a variety of standard feature models) and numerical (on a variety of datasets) evidence supporting our investigations.

The reviewers have also pointed out potential weaknesses and places for improvements in the paper.

- Reviewer **cp5Y** mentioned some confusion regarding the notation, terminology, and layout of the paper.
- Reviewer **nM8u** noted the focus on the asymptotic regime.
- Reviewer **HnNV** suggested additional related work on subsampling and iterative least squares approaches.

We have carefully addressed each reviewer's questions and points of weakness in a point-by-point manner below. To improve readability and for space reasons, we have divided our responses into different posts. We apologize for the length of our response, but we provide thorough and comprehensive answers to all the reviewer's questions and concerns.

In particular, we have tried to clear some misunderstandings of Reviewer **cp5Y** with regard to notation, terminology, and organization. We briefly describe this below for reviewers' convenience.

- **Notation**: The reviewer may have missed this but we actually have a dedicated notation section in the Appendix (lines 552-580) that summarizes all the key notations used in the paper. Some of the important notation (such as average trace) is also mentioned in the main paper where it is used (lines 130-131). We understand that the paper is notation-heavy, and the notation may seem foreign for readers not familiar with random matrix theory and free probability theory, but the notation we use is standard in these fields.

- **Terminology**: We understand that some of the terminology in the paper may be specific to the literature in this area. But note that we define the term "paths of equivalence" in the Introduction (lines 38-41) and intuitively explain this in the Abstract (lines 7-9). We will try to explain this in even more detail in our revision.

- **Organization**: With regards to the layout, we have a section-wise summary of results in the paper in the Summary of Results paragraph (lines 55-77). We will add an explicit organization section in our revision (with the additional page provided in the final version). 

We have kindly asked Reviewer **cp5Y** to reconsider the score given after clearing these misunderstandings.

We believe that our response comprehensively addresses the concerns raised by the reviewers. We are open to any further feedback and look forward to subsequent comments from the reviewers.

Meta-review: After the rebuttal, all reviewers gave positive scores. The AC recommends acceptance based on the following merits:

* The submission presents strong theoretical results based on relaxed assumptions on both the weighting matrix and the feature matrix. It demonstrates the precise relationship between the regularization of weighted ridge regression and simple ridge regression.

* The proposed theory introduces a novel approach to tuning regularization strengths through subsampling. The experiments in Figure 4 confirm the theoretical relationship between risks and validate the effectiveness of the tuning procedure.

The authors are encouraged to improve the organization of the paper following the advice of reviewer cp5Y in the final version.
Decision: Accept (poster)