No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions
Authors: Benjamin Samuel Ruben
William Lingxiao Tong
Hamza Tahir Chaudhry
Cengiz Pehlevan
Venue: ICML 2025 poster (2025)
Keywords: Ensemble Learning
Regression
Scaling Laws
Primary area: theory->learning_theory
TL;DR: We show that ensembles of random feature models never outperform a single model of the same total size, and identify conditions where near-optimal performance by ensembles is possible in both the overparameterized and underparameterized regimes.

Abstract: Given a fixed budget for total model size, one must choose between training a single large model or combining the predictions of multiple smaller models. 
We investigate this trade-off for ensembles of random-feature ridge regression models in both the overparameterized and underparameterized regimes. 
Using deterministic equivalent risk estimates, we prove that when a fixed number of parameters is distributed among $K$ independently trained models, the ridge-optimized test risk increases with $K$.
Consequently, a single large model achieves optimal performance.  We then ask when ensembles can achieve *near*-optimal performance.
In the overparameterized regime, we show that, to leading order, the test error depends on ensemble size and model size only through the total feature count, so that overparameterized ensembles consistently achieve near-optimal performance.
To understand underparameterized ensembles, we derive scaling laws for the test risk as a function of total parameter count when the ensemble size and parameters per ensemble member are jointly scaled according to a ``growth exponent'' $\ell$. 
While the optimal error scaling is always achieved by increasing model size with a fixed ensemble size, our analysis identifies conditions on the kernel and task eigenstructure under which near-optimal scaling laws can be obtained by joint scaling of ensemble size and model size.

No Free Lunch From Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions
Benjamin S. Ruben William L. Tong 234
Hamza Tahir Chaudhry 23
Cengiz Pehlevan 234
Abstract
1. Introduction
Ensembling methods well-established tool in machine learning for reducing the variance of learned predictors. While traditional ensemble approaches like random forests (Breiman 2001) and XGBoost (Chen & Guestrin 2016) combine many weak predictors, the advent of deep neural networks has shifted the state of the art toward training a single large predictor (LeCun et al. 2015). However, deep neural networks still suffer from various sources of variance, such as finite datasets and random initialization (Atanasov
Given a fixed budget for total model size, one must choose between training single large model or combining the predictions of multiple smaller models. We investigate this trade-off for ensem- bles of random-feature ridge regression models in both the overparameterized and underparameter- ized regimes. Using deterministic equivalent risk estimates, we prove that when fixed number of parameters is distributed among K independently trained models, the ridge-optimized test risk in- creases with K. Consequently, a single large model achieves optimal performance. We then ask when ensembles can achieve near-optimal per- formance. In the overparameterized regime, we show that, to leading order, the test error depends on ensemble size and model size only through the total feature count, so that overparameterized ensembles consistently achieve near-optimal per- formance. To understand underparameterized en- sembles, we derive scaling laws for the test risk as a function of total parameter count when the en- semble size and parameters per ensemble member are jointly scaled according to a "growth expo- nent" l. While the optimal error scaling is always achieved by increasing model size with fixed ensemble size, our analysis identifies conditions on the kernel and task eigenstructure under which near-optimal scaling laws can be obtained by joint scaling of ensemble size and model size.
et al. 2022 Adlam & Pennington, 2020 Lin & Dobriban Atanasov et al., 2024). As result, deep ensem- bles ensembles of deep neural networks- -eiikkn a popu- lar method for variance reduction (Ganaie et al., 2022 Fort
2021
et 2020), and uncertainty estimation (Laakshminrrayanan ct 2017
A critical consideration in practice is the computational cost associated with ensemble methods. While increasing the number of predictors in an ensemble improves its accuracy (provided each ensemble member is "competent" (heisen ct al. 2023)), each additional model incurs significant com- putational overhead. Supposing a fixed memory capacity for learned parameters, a more pragmatic comparison is between an ensemble of neural networks and single large network with the same total parameter count. Indeed, recent studies have called into question the utility of deep ensem- bles relative to a single network of comparable total size (Abe et al., 2022: Vyas et al., 2023). However, because ensemble learning allows fully parallelized training and in- ference, it will likely remain an attractive option in practice. A robust understanding of when an ensemble of small neural networks might approach the performance of single large neural network is therefore needed.
'Biophysies PhD Program, Harvard University, Cambridge, MA 02138, USA "John A. Paulson School of Engineering and Ap- plied Science, Harvard University, Cambridge, MA 02138, USA Center for Brain Science. Harvard University, Cambridge, MA 02138, USA 'Kempner Institute, Harvard University. Cambridge, MA 02138, USA. Correspondence to: Benjamin S. Ruben <ben- ruben hddv..d.edu>.
Originally introduced as a fast approximation to Kernel Ridge Regression, random-feature ridge regression (RFRR) (Rahimi & Recht 2007) has emerged as a rich "toy model" for deep learning, capturing non-trivial effects of dataset size and network width (Canatar et al. 2021 Atanasov et al.] 2023 generalization error of deep networks and RFRR can vary non-monotonically with dataset size and feature count due to fitting effects known as "double-descen"" (D' A'Ascoli
Mei & Montanari 2022). In particular, the
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

No Free Lunch From Random Feature Ensembles
al.
2020 Nakkiran 2019: Nakkiran al.
2019:
Adlam
we will use upper indices k ,...,,, K to represent the ensemble index. K sets of random features (ar) R are constructed as [x))],
& Pennington, 2020: Lin & Dobriban 2021),
"multi-
ple descent" (D' Ascooli et al.
2020 Mel & Ganguli 2021
g x)) Here, for each n = ................................ N and k= I...., K, va is a random parameter vector sampled independently as oa My for measure Me R The function g R x IR + I is "featurization transformation," often taking the form g(u, a:) = yp(r' ax) for some nonlinear activation function (p(). The prediction of the 1hhh RERR model is then given by
Meng et al. [022]. However, these overfitting effects can be
mitigated with an optimally tuned ridge parameter (Nakki-
ran et al., 2020 Advani et al. 2020; Canatar et al., 2021
Simon et al. 2023). Specifically, Simon et al.) showed
that in RFRR, test risk decreases monotonically with model size and dataset size when the ridge parameter is optimally chosen.
(*())= = t. 2/4 (az)
In this present work, we study the tradeoff between the number of predictors and the size of each predictor in en- sembles of RERR models. We find that with a fixed budget on total model size (defined as the total number of ran- dom features), minimal error is achieved by single large model, provided the ridge is optimally tuned (theorem p.I). However, we identify multiple conditions under which en- sembles of smaller models can achieve near-optimal perfor- mance. In the overparameterized regime, we show that, to leading order, error depends on the ensemble size K and individual model size N only through the total ensemble size M KN (eq. 2 so that overparameterizee en- sembles consistently achieve near-optimal performance. In the underparameterizet regime, we derive scaling laws for the test risk as function of total ensemble size (eq. (6)) The scaling law depends on a newly introduced "growth exponent" which controls the relative growth rates of K and N with total model size M (eq. (5). While optimal error scaling is always achieved by scaling model size N with fixed K, identify conditions the kernel and task eigenstructure which permit near-optimal error scaling by joint scaling of ensemble size and model size.
(I)
VN
where vt is the weight vector learned via ridge regression:
tt arg min WERD
Σ U/
M(x))) +
Nll
(2)
(
1 N
q
up + AI)
(3)
VN
where T E NxP has columns [yb* (x1). and the vector E RR has [y]p - Vp. Finally, the ensem- bled predictor is constructed by averaging the predictions of each ensemble member h 1,...,K'* K:
2b (xr)
K
1 K
Jons (m)
(x)
(4)
The Kernel Limit Each of the learned functions f*( may equivalently be expressed as the kernel ridge regression predictor:
jr (xx = -hi,x (ixxx + AIN) y
2. Preliminaries
(5)
2.1. Random Features and the Kernel Figenspectrum
Where the matrix (Hxxlee Hap Rap') and the vec- tor [h |h= A (x,, pp), for the stochastic finite-feature kernels:
In this section, we describe ensembled RFRR, as well as the spectral decomposition of the kernel on which our results rely. This framework is described in (Simon et al. [2033 for the single-predictor case, and is reviewed in more rigor in Appendix [A] Here we will consider a supervised learning task, where the goal is to learn an estimator fx)) that maps input features x E IRD to a target value E R. given a train- ing set D pxp }p)p= The training labels are assigned as y0 = fx,,) + Ep for some ground truth function f., and where 6p N/(0 o?) is drawn i.i.d. for each sample.
N g slu x) x)g (h x²)
H'()xx))) N
Σ
(6)
The fluctuations in this stochastic kernel vary due to the random realization of the weights { across ensemble
members k = 1..... K. As N + xo, these stochastic kernels converge to a common deterministic limiting kernel:
H (x. x²) N-000 H x') = Euwap [g(v, ar 3)) (1, a²)]
Random-Feature Ridge Regression (RFRR) Ensembles. In Random-Feature Ridge Regression (RFRR) Ensemble of size K, the data is first transformed into K separate finite- dimensional reature-spaces Linear regression is performed on each of these spaces independently, and the resulting predictions are averaged at test time. Throughout this paper,
In this "kernel limit", the learned functions f* (x) will be independent of the ensemble index k. so that we can define soo (2r) = fens(w)) f*((x) k, with
f2) = -z,x (Hxx + AT) y, (N + 00). (7)
2

---

No Free Lunch From Random Feature Ensembles
where Hxx E RxP is the kernel matrix with entries [Hxxlp py
For binary classification problems, we might also consider the classification error rate held-out test examples under score-averaging majority vote (equations A.6 A.7
H (gps Fy'), and hz,x (H, (e,,zi).... æi)...., (x)) The limiting kernel H (x, can be decomposed into its eigenfunctions (x) and
corresponding eigenvalues {n:)er
2.2. Degrees of Freedom
Using notation similar to (Atanasov et al. 2024 and (Bach 2023), we will write expressions in terms of the "degrees of freedom" defined as follows:
(a,, 20) = Σ (o)(()))
(8)
In this formulation, (xx) is equivalent to the function learned by linear regression in the infiittedimeesional fea- tures with components given by (z)) = (z). We will assume that the target function can be decomposed in this basis as fx) Ee (z)). In the following sections, we will describe an error formula for RFRR en- sembles which depends on these limiting kernel eigenvalues [n:] and target weights {we K, NN, and P, which provide a complete statistical description of the learning problem.
Df, = Σ t
Vi (Te + K)
(x)
Wi 1
(1) + K)
(11)
where n E N. Intuitively, Df, can be understood as a measure of how many modes of the kernel eigenspectrum are above a threshold k, with the sharpness of the mea- surement increasing with n. tf, is similar measure with each mode weighted by the corresponding component of the target function.
Gaussian Universality Assumption. Following (Simon al., 2023), we assume that the random features can be replaced by Gaussian projection from the RKHS associ- ated with the limiting kernel. Specifically, population risk is well described by the error formula obtained when the random features are replaced by (xx) = Z 2²0 (x) where [0(=)] = 0z(z)) z E R xH is a random Gaussian ma- trix with entries z Lid. ((0,1), 1), and H the (infinite) dimensionality of the RKHS. Equivalently, we may approxi- mate the stochastic kernels & (xx æ²) as the inner products of linear random features:
3. Deterministic Equivalent Error for Random Feature Ensembles
The error EK of eq. 10 is random quantity, depending both on the particular realization of the dataset 'D and the realization of the random feature vectors {uh)- Many re- cent works have found, however, that for large values of P and N the error EKK will concentrate over these sources of randomness. The error EK can then be estimated by a deter- ministic equivalent error E. which depends on the dataset D and random features {v only through their sizes P and N. We will write &K = F.K with the symbol = meaning that the value on the right side is the deterministic quantity approximating the stochastic quantity on the left in the limit of large P and N. The exact slack in this approximation varies in the literature, and is discussed in Appendix B
H (x. x') = N (x) (x)TTb(<')) (x')= = N
Hx
0(x) ZhT
z (2x).
(9)
Under this Gaussian universality assumption, the RFRR setting is equivalent to the linear handom-feature setting studied in ref's. (Maloney et al. 2022; Atanasov et al. 2024
We first review the deterministic equivalent approximation to the error Eg of single RFRR model (superscript indi- cates K = 1). We do not derive this well-known result here, but rather direct the reader to a wealth of derivations, includ- ing references (Atanasov et al.) 2024 Canatar et al. 2021 Simon et al.
2022). with the limiting kernel eigenspectrum playing the role of the data covariance.
The Gaussian universality assumption has been justified rigorously in the case of a single ensemble member (K 1)
2023 Adlam & Pennington, 2020) Rocks &
by Defilippis et al.) who provide a multiplicative error bound on the resulting estimate for population risk (see section 3 and Appendix B).
Mchta 2021 Hastie et al. 2022 Zavatone- Veth et al. 2022
Defilippis et al. 2024). Translating the risk estimate into our selected notation, we have that Eg ~ E3g with:
Test Risk The test risk (also known as the generaliza- tion error or test error) quantifies the expected error of the learned function on unseen data. In this work, we define the test error as the mean squared error (MSE) between the predicted function fens(a) and the true target function fx)),, averaged over the data distribution Ma::
1
F
[- 1 + (1 p)s² uf (12) + o?]
71
(12)
where we have defined
N - (K2)
1 ((1 p) Dr +p Dí2)
p N Df2(K2)
71 p
ex = En-ua [Ven((r)- [.())))] +0
(10)
(13)
3

---

No Free Lunch From Random Feature Ensembles
and Ri is the solution to the following self-consistent equa-
4. More is Better in Random Feature Ensembles
tion:
AN
K6g
(14)
(P- Df (k2) (N (x22)
A ubiquitous observation in the modern practice of machine learning is that larger models and datasets lead to better per- formance. However, ensemble learning offers an additional complication that can break this trend. In the case of random forests, for example, subsampling of data dimensions leads to improved performance, despite reducing the expressiv- ity of each decision tree (Breiman 200T). Similarly, deep feature-learning ensembles have been empirically observed to violate the "bigger is better" principle (see fig. 8 from Vyas et al. (002)). Here, we show that no such violations can occur in RFRR ensembles.
We find that eq. finite N, P.
12 provides an accurate estimate of risk at
3.1. The Bias- Variance Decomposition of Eg
The error formula can further be decomposed using a bias- variance decomposition with respect to the particular real- ization& Z of random features:
F 9
Bias + Var=
(15)
[EE [f(x)] ((())){(((z)) -L((z)) 27
Theorem 4.1. (More is better for RF Ensembles) Let E E (P,N, denote E with P training samples, N ran- dom features per ensemble member, ensemble size K, and ridge parameter X and any task eigenstructure {ne his {we) where {m:)E= has infinite rank. Let K' 2 K, P 2 P and N' 2 N. Then
B = Egenetn
+
(16)
[ff(0)= - Ez [f(z)) )
27
Var.- = Banpa
(17)
While the learned function f in the equation above also depends on the particular realization of the dataset D, we do decomposition because
S min E (P, min Eg (P',N', X
(21)
not include this in the we are interested in the variance due to the realization of finite set of random features. Furthermore, the Bias and Variance written in equations 16 17 are expected to concen-
X with strict inequality as long (K', P') # P, and Σ, wn n) > O.
trate over D (Atanasov et al. 2024: Adlam & Pennington
Proof of this theorem follows from the omniscient risk es- timate 20 and is provided in Appendix C
2020 Lin & Dobriban 2021). j. The deterministic equivalent
We make the
formulas for the Bias and Variance are given explicitly in
following remarks:
(Simon et al. 2023). and may be written as:
Remark 4.2. In the special case K = ="===== =" 1, this reduces to the "more is better" theorem for single models proven in Simon et al. (2023), and thus extends the notion that larger models and datasets improve performance from single (19) models to RFRR ensembles.
B ~ - 22
o² 1 1 722
tf (12) +
(18)
1-72
Var, ~ E Bias?
Remark 4.3. Improved accuracy of the constituent models that form an ensemble does not necessarily lead to improved accuracy of the ensemble-averaged prediction, which sup- presses the variance of the individual predictors. Proof of theorem 4.] therefore requires separate treatment of the bias and variance terms, unlike the K = K" 1 case proven by Simon et al.
where 722 = 1, p (f2())).
3.2. Ensembling Reduces Variance of the Learned Estimator
Armed with bias-variance decomposition of a single esti- mator over the realization of Z, we can immediately write the risk estimate for an ensemble of K estimators, each with an associated set of random features encapsulated by an independently drawn random Gaussian projection matrix ž&, k: I,..., K. Because the realization Z of random features is the only parameter distinguishing the ensemble members, each ensemble member will have the same ex- pected predictor fxxxxx Furthermore, because the draws of z are independent for k- = 1...., K, the deviations from this mean predictor will be independent across ensem- ble members, so that ensembling over K predictors reduces the variance of the prediction by factor of K:
We demonstrate monotonicity with P and N in Fig. where we plot E as a function of both sample size P and the network size N in ensembles of ReLU random feature models applied to a binarized CIFAR- 10 image classifica- tion task (see Appendix E..). While error may increase with P or N at a particular ridge value X, error decreases monotonically provided that the ridge À is tuned to its opti- mal value. Theoretical learning curves are calculated using eq. 20 with eigenvalues n)s and target weights wi deter- mined by computing the NNGP kernel corresponding to the unfinite-feature limit of the ReLU RF model (see Appendix E.3 for details). Numerically, we verify that error mono- tonicity with P and N holds at the level of 0-1 loss on the
1
K = Bias? + K 9
Var;
(20)
4

---

Several remarks are in order: No Free Lunch From Random Feature Ensembles
predicted classes of held-out test examples for both score- averaging and majority-vote ensembling over the predictors (see fig. S3
Proof of theorem 5.1 follows similar strategy to the proof of theorem 4.1 and is provided in Appendix C We test this prediction by performing ensembled ReLU RFRR on the binarized CIFAR-10 10 classification task in figure 2 We find that increasing K while keeping the total number of features M fixed always degrades the optimal test risk. The strength of this effect, however, depends on the size of the training set. For larger training sets (P > N). the width of each ensemble member becomes the constraining factor in each predictor's 's ability to recover the target function. However, when P < N,, the optimal loss is primarily determined by P. so that optimal error only begins increasing appreciably with K once N = M/K S P (fig. 2 B). We again find similar behavior of the 0-1 loss under score-average and majority-vote ensembling (see fig. [56). While the ridge- optimized error always minimal for K = we notice in fig. 2C that near-optimal performance can be obtained with K > 1 over wider range of À values, suggesting that ensembling may offer improved robustness in situations where fine- mie-tuning of the ridge parameter is not possible. Further robustness benefits have been reported for regression
We compare rdde-optimized eπror across ensemble sizes K in fig. [ST finding that increasing sample size P and network size N are usually more effective than ensembling over multiple networks in reducing predictor error, indicat- ing that for the binarized CIFAR-10 RFRR classification task, bias is the dominant contribution to error. Similarly, ensembling over multiple networks gives meager improve- ments in performance relative to increasing network size in deep feature-learning ensembles (Vyas et al. 2023
5. No Free Lunch from Random Feature Ensembles
is immediate from eq. 20 that increasing the size of an ensemble reduces the error. However, training additional models incurs significant cost. With a fixed memory ca- pacity, the machine learning practitioner faced with the decision of whether to train a single large model, or to train an ensemble of smaller models. Here, we prove a "no free lunch" theorem which says that, given a fixed total number of features M divided evenly among K random feature mod- els, then the lowest possible risk will always be achieved by K = 1, provided that the ridge is tuned to its optimal value. Furthermore, this ridge-optimized error increases monotonically with K.
ensembles of heterogeneous size (Ruben & Pehlevan 2023).
Theorems 1 and 2 together guarantee that a larger ensemble of smaller RFRR ensembles can only outperform smaller ensemble of larger RFRR models when the total parameter count of the former exceeds that of the latter. We formalize this fact in the following corollary:
Corollary 5.5. Let E (N) be the test risk of an ensemble of K RFRR models each with N features given by eq. 20
Theorem 5.1. (No Free Lunch From Random Feature En- sembles) Let F.K N,,N,N) X) denote Foj with P training sam- ples, N random features per ensemble member, ridge param- eter X, ensemble size K, and task eigenstructure (m 1 {w, ) where (e has infinite rank. Let K' < K. Then
Suppose K' > K or N' < <N. It follows Theorems 4.1 that
and 5.1
min Pg (N') min F. (N) = K'N' 2 KN. (23)
Remark 5.6. We emphasize that this is a uni-directional statement. It is common for a single larger model to out- perform an ensemble of smaller models with greater total size, particularly in the underparamettrrized regime. See, for example, fig. B.
EinEK min EKK (P.M/K',A) min E (P,M/KK,) (22)
with strict inequality as long as Ee wfn
0.
We demonstrate this result on synthetic tasks with power- law structure and on the binarized CIFAR-10 classification task in fig. S2
Remark 5.2. In the limit where M- + xc, this result im- plies that no ensemble of RFRR models can outperform the limiting (infinite-feature) KRR model with optimal ridge. Remark 5.3. In section 7 we comment on the distinction between this result and known equivalences between infinite ensembles and single predictors of infinite size (Patil & LeJeune 2024 LeJeune et al. 2020 Dern et al. (0024)
6. Near-OOtinnllity Conditions for RFRR Ensembles
Our results indicate that ensembling is always a sub-optimal allocation of model parameters. Theorem 5.1 T guarantees that no ensemble of random-feature models can outperform single model with the same total size when the ridge pa- rameter is optimally tuned. Furthermore, corollary |t3]st that an ensemble of smaller models can only outperform an ensemble of larger models if the ensemble of smaller
Remark 5.4. While ensembling is the canonical strategy for reducing the variance of a predictor, the proof of theorem 5.1 on the fact that when the ridge parameter is scaled to keep bias constant, increasing model size decreases vari- ance of the learned predictor faster than adding additional predictors to the ensemble.
5

---

No Free Lunch From Random Feature Ensembles
A
K
2
K
8
10a
Theory
optims
100
Test Error
1
10 -
0.9
0.8
0.9
10
0.8
0.7
0.7
0.6
0.6
10
10
10a
10a
10
10
10
10a
10
10
10a
10a
10
10a
10a
10a
10*
P
B
K
2
K
K 8
10a
Experment Theory
Test Error
1
10
10-2
0.8
0.7
07
0.7
10-3
10a
N 10
10a
10a
102
102
N 10a
10a
102
102
10a
N
N
Figure 1. "More is better" in random feature ensembles. We perform ReLU RERR binarized CIFAR- 10 classification task and compare the empirical test risk to the omniscient risk estimate (eq. 20). (A) We fix N 256 and vary both P and K. Color corresponds the regularization A. Markers show numerical experiments and dotted lines theoretical predictions. Error is monotonically decreasing with P' provided that the regularization is tuned to its optimal value. (B) Same as (A) except that = 256 is fixed and K, N are varied. Markers and bars show mean and standard deviation over 50 trials.
models has greater total size. These results suggest that, with fixed memory capacity, it is always beneficial to scale a predictor by increasing the size of the network. However, ensembling remains an attractive option in practice because they allow fully parallelized training and inference. It is therefore important ask when ensembles
expand the deterministic equivalent error formula EK (eq.
20 as power series in 1 1/N Z 0 and s 0 in Appendix
D.2 finding:
PR tf' (K))
PRY tttf
EK
+ AF P)
P- Df2
KN
attain near- optimal performance. In section 6.1 we investigate RFRR ensembles in the overparameterized regime, finding that at leading order in À and I/N, eгror depends only on the total feature count M = KNN To study the underparameterized regime, we derive scaling laws for RFRR ensembles under joint scaling of ensemble size K and model size N. While the optimal scaling law always achieved by scaling model size with fixed ensemble size, analysis provides con- ditions on the data and task eigen-structure under which joint scaling of model size and ensemble size can achieve near-optimal scaling law for the error.
+ 0 A/N, 1/N,1//N 1/N2),
(24)
where No satisfies Df, We see that, at leading order A, and 1/N, risk depends on the ensemble size and model size N only through the total number of features KN. So, while Theorem 5.1 guarantees that there be benefit dividing features into an ensemble of smaller predictors, we don't 't expect this to appreciably harm performance as long as the ensemble remains in the overparameterized regime (N > P) and optimal or near-optimal performance can be achieved with small ridge parameter. While we not provide exact con- ditions under which near-optimal performance is achieved at small ridge parameter here, our numerical experiments verify that enror depends on N and K only through their product M = NK (see agreement between dotted lines and green lines in fig. S2 Furthermore, Simon et al. argue that in the overparameterized limit N - oc, optimal ridge approaches zero for tasks with power-law structure under realistic conditions.
P. and we have set a, = 0.
6.1. NNea--Optima Risk in Overparameterized RERR Ensembles
For ensembles in the overparameterizze regime (N >> P), the bound of corollary 5.3 appears to be tight, meaning that an ensemble of K models size N performs similarly to single model of size M N K. To understand why, we
6

---

No Free Lunch From Random Feature Ensembles
A
p 128
P = 1024
P = 8192
Experiment
Theory optimal
Test Error
0.8
10
0.9
8
0.5
10
10
10a
10"
109
101
10a
B
K
K
C
K
K=1
Optimal Test Error
K=2
8 10
10
K=4
Test Error
K-8
K-16
7 10
7 10
K=32
P-128
K=64
P=1024
P=8192
P 8192
109
10
102
10
10
10a
Figure 2. No Free Lunch from Random Feature Ensembles. We perform kernel RF regression on a binarized CIFAR 10 classification
task. (A) We vary K and N while keeping total parameter count M 1024 fixed. The sample size P is indicated above each plot. (B) Error E optimized over the ridge parameter À increases monotonically with K provided the total parameter count M is fixed. Dashed standard deviation of the risk measured numerical simulations across 10 trials. (C) We show error a function of X for each K value simulated and / = 8192. Dashed lines
lines show thcoretical prediction using eq. 20 and markers and error-bars show mean
theoretical prediction using eq. 20 and shaded regions show standard deviation of risk measured in numerical simulations across
trials.
6.2. Scaling Laws for Underparameterizzed RERR Ensembles
w7?, ~ 5 (1+42r)) we find:
EK M
(26)
now study the behavior of RFRR ensembles in the un- derparameterized regime where N
M/KK < P. Here, model size N is the "bottleneck" that dictates the scaling behavior of the risk (Bahri al. 2024 Maloney et al. 2022 Bordelon et al. 2024a Atanasov et al. 2024). In particular, we ask how E* scales with total model size M when K and N scale jointly with M according to a "growth exponent"
= min Din(r, 1), E 20d min
(.
1
(27)
with s = 2al min(r, 1) corresponding to the scaling of the bias and = 1- E 2ad min (r, 1/2) corresponding the scaling of the variance (reduced by factor of 1/K). A full derivation is provided in Appendix These results reify the "no free lunch" result, the optimal scaling law is always achieved when = 1. For difficult tasks, defined as having < 1/2. bias always dominates the error scaling and the scaling exponent increases linearly with f. However, when 1/2, there will a certain value E above which error scaling is dominated by the variance term. When r > 1/2. the scaling exponent of the variance increases from over the range é [0, 1]. If a Z this can approach flat line, and the dependence of the scaling exponent on can become weak, so that near-optimal scaling can be achieved for any E > E" When 1/2 < < 1, this transition occurs at = 1/(1 + a(2r 1)) and when r occurs at 8" = 1/(1 + a).
i E [0.1] K~ Mi-
N N~M
(25)
so that when 0 the ensemble grows with Af by adding additional ensemble members of fixed size, and when l = 1 the ensemble grows by adding parameters to a fixed number of networks. Under the standard "source" and "ca- pacity" constraints on the task cigenstructure (Cui et al. 2023 Caponnetto & De Vito 2006) Bordelon et al.] 2020 Defilippis et al., 2024) (the kernel eigenspectrum decays as 7). t-o with a and the target weights decay as

---

No Free Lunch From Random Feature Ensembles
A
Qr
1.5, r = 0.4
= 1.5, -
0.8
0
1.5, r = 1.2
1.0
Optimal Test Error
10-1
10a
10
0.8
10
10-2
10
10-3
10-3
0.6
10-3
10-4
10-4
Numerical
Theoretical
10a
10a
10a
M
M
M
B
Q
1.5, r = 0.4
0
1.5, 7 = 0.8
0 1.5, r 1.2
2.5
3
Empirical: Eg
1.00
Theory: Blas
Theory: Var
0.75
0.50
0.25
0.25
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0,50
1
Figure 3. width-bottleneeked scaling laws of kernel RF regression under source and capacity constraints. We fix P = 15, 000, 1.5. (0.4, 0.8, 1.2) and calculate E as function M with MM and (1 using both omniscient risk estimate (eq. 20 and numerical simulation of a linear Gaussian random-feature model (eq. A..12 (A) Plots of E vs. M different & values reveal that controls the scaling law of the error. (B) We plot the theoretical scaling exponents (eq. 26): Bias ~ 2al min(r, 1), Var 1 f +/2+24 2al min(r, 1) along with the scaling laws obtained by fitting the risks obtained by numerical simulation.
We plot these scaling laws with a = 1.5 in the regimes where r < 1/2, 1/2 < r < 1, and r > in fig. 3 along with the results of numerical simulations of linear RF re- gression synthetic Gaussian datasets. As anticipated, for difficult tasks, where 1/2, the scaling law improves linearly with f. However, for easier tasks (r > 1/2), we see that, a near-optimal scaling law can be achieved as long as >>< (fig. center and right columns).
model types may also a result of overfitting. Because deep networks reduce kernel methods in the lazy training limit (Chizat et al., 2019 Jacot et al. 2018), we may pin- point any violations of these principles in deep ensembles consequence specifically of feature learning. Future work should extend recent analytical treatments of feature- learning networks (Bordelon et al. 2024b) to the ensembled case.
We also determine the scaling behavior of the ReLU RFRR ensembles on the binarized CIFAR-10 and MNIST clas- sification tasks. For both tasks, calculate the statis- ties of the limiting kernel eigenspectrum {n and tar- get weights { and fit their spectral decays to the source and capacity constraints. We find that for CIFAR-10, a x 1.33, r R 0.038 and for MNIST a s 1.46, ~ 0.14, which places both tasks squarely the difficult regime with 1/2. In figure we show that the predicted scaling exponents of eq. 26 agree with empirical scaling laws for RFRR ensembles applied to the binarized CIFAR-10 10 and MNIST classification tasks.
Our results relate a line of work on "sketched" subsam- pled ridge ensembles, which prove that an infinite ensemble of regression models trained random projections of the data achieve equivalent test risk to single regression model trained on the full data, with an increased ridge parame- ter (Patil & LeJeune 2024, Atanasov et al.] 2024 LeJeune et al. 2020 Patil et al., 2023). Translated to the kernel eigenframework under Gaussian universality, these results imply that in the limit K + oc, RFRR ensembles converge the same test risk as the limiting (anfnite-ffature) kernel predictor. It follows that ensemble of RFRR models outperform the limiting kernel predictor at optimal ridge, corresponding to the M + oo limit of theorem 5.] with K' = Because it applies also at finite M and K" > 1, theorem 5.1 is a stronger statement.
7. Discussion
Our results show that in RFRR ensembles any violations of the "more is better" or "no free lunch from ensembles" principles are result of overfitting at non-optimal ridge. This suggests that violations of these principles in other
Our study also connects recent work on scaling laws in deep learning (Kaplan a et al. 2020 Hoffmann al. 2022
Bordelon et al. 2024a b). which observe that the test error of neural networks tends to improve predictably as power-law
8

---

No Free Lunch From Random Feature Ensembles
A
CIFAR 10
MNIST
functional specialization an objective for future work.
10
1.0
9
0.8
8. Conclusion
Optimal Test
8x
6 10
7x
x0-1
0.4
In this work, we analyzed a trade-off between ensemble size and deatures-pen-ensemble--e
3 x0-10
Namerica Throntical
in the tractable set- ting of RFRR. We prove a "no free lunch from ensembles" theorem which states that optimal performance is always achieved by allocating all features to a single, large RFRR model, provided that the ridge parameter is tuned to its op- timal value. A scaling-laws analysis reveals that the sharp- ness of this trade-off depends sensitively on the structure of the task. In particular, near-optimal scaling laws can be achieved by RFRR ensembles, provided the task is suffi- ciently aligned with the top modes of the limiting kernel eigenspectrum. Our results tell a story consistent with the general trend from massively ensembled predictors to large models trained by joint optimization of all parameters with respect to a single loss function. Our results have implica- tions for model design and resource allocation in practical settings, where model size is limited.
10
02
10a
10a
10
10a
M
B
CIFAR 10
MNIST
1.42
à 1.53
0.8
8 == .028
0.75
8
= 110
0.6
0.50
Empirical: E,
0.4
Theery: B
0.2
0.25
Theory: Yor
0.0
0.00
0.25
0.50
0.75
1:00
0.25
0.50
75
1.00
Figure 4. Scaling laws provide a good description of width- bottlenecked RFRR ensembles.(A) we plot error as function of M at optimal ridge value for ReLU random-feature models ap- plied to the binarized CIFAR-10 (left) and MNIST (right) classifi- cation tasks, (B) We plot theoretically predicted scaling exponents (eq. (6)) for the bias and variance contributions to risk, as well as empirical power-law fits to risk in numerical simulations of RFRR
Acknowledgements
models (see Appendix E.3 fig. S7
C.P. is supported by NSF grant DMS-2134155 NSF CA- REER Award IIS- 2239780, DARPA grant DIAL-FP-038, Sloan Research Fellowship, and The William F. Milton Fund from Harvard University. WLT is supported by a Kempner Graduate Fellowship. HC was supported by the GFSD Fellowship. Harvard GSAS Prize Fellowship, and Harvard James Mills Peirce Fellowship. This work has been made possible in part by gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence. BSR thanks Blake Bordelon, Alex Atanasov, Sabarish Sainathan, James B. Simon, and especially Jacob Zavatone- Veth for thought- ful discussion related to and comments on this manuscript.
with the number of parameters and the size of the dataset used during training. With our scaling-law llw analysis, we ex- tend the power-laws predicted using random-feature models
(Bahri et al. 2024 Maloney et al. 2022, Bordelon et al. 2020 2024a Defilippis et al. 2024) to the case where model size N and ensemble size K are scaled jointly according to a novel "growth exponent" e defined in eq. 25 While optimal scaling is always achieved by fixing K and scaling N, for sufficiently easy tasks (r > 1/2), near-optimal scaling laws can be achieved by growing both N and K, provided N grows quickly enough with total parameter count. Because feature-learning networks can dynamically align their rep- resentations to the target function (Bordelon et al.] (204b)). the scaling laws for deep ensembles may be dramatically improved by feature-learning effects.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
An important limitation of our work is the assumption of statistically homogeneous ensembles. We consider each en- semble member to be trained on the same dataset, and to per- form the same task. However, successes have been achieved using ensembles with functional specialization, where differ- ent sub-networks are trained on different datasets to perform different sub-tasks relevant to the overall goal of the ensem- ble. For example, mixture of experts (MoE) models (Jacobs ct al. 1991: Lepikhin et al. 22200] Fedus et al., (022) might offer a way to cleverly scale model size using ensembles that outperforms the scaling laws for single large networks. We leave a theory of ensembled regression which allows for
References
Abe, T., Buchanan, E. K., Pleiss, G., Zemel, R., and Cun- ningham, J. Deep ensembles work, but are they nec- essary?, 2022. URL https: httpp::/aaxivv.org/bba..
Adlam, B. and Pennington, J. Understanding double de- scent requires fine-grained bias bias-variance decomposi-

---

No Free Lunch From Random Feature Ensembles
tion, 2020. URL /
doi: 10.008441116--000111000--- URL http://dx
03321
del..cor//0000033//41144--------
Advani, M. S., Saxe, A. M., and Sompolinsky, H. High- dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428 446, December doi: 10.10166f.neuunet2202.
Caponnetto, A. and De Vito, E. Optimal rates for the regularized least-squares algorithm. Founda- tions of Computational Mathematics, 7(3):331-68,, August 2006. ISSN 1615-3383. doi: 10.1007/ s10208-006-0196-88 URL http://dw..d..orgg.... 10. 10.1007/s10206 006 0196-8
2020. ISSN 0893-6080.
08.022. URL
neunet 2020 08 022
Atanasov, A., Bordelon, B., Sainathan, S., and Pehlevan, C. The onset of variance-limited behavior for networks in the lazy and rich regimes. arXiv preprint arX1v:2212.12147. 2022.
Chen, T. and Guestrin, C. Xgboost: A scalable tree boost- ing system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 785-794, ACM, August 2016. doi: 10. 10.114457993967722937775 URL http:
Atanasov, A., Bordelon, B., Sainathan, S., and Pehle- van, C. The onset of variance-limited behavior for net- works in the lazy and rich regimes. In The Eleventh International Conference on Learning Representations, 2023.
Chizat, L., Oyallon, E., and Bach, F. On lazy training in diffcrentiable programming. Advances in neural informa- tion processing systems, 32, 2019.
Id=JI.NxPPVV
Cui, H., Loureiro, B.. Krzakala, F., and Zdeborová, L. Er- ror scaling laws for kernel classification under source and capacity conditions. Machine Learning: Science and Technology, 4(3):035033, August 2023. ISSN 2632- URL https 2153. doi: 10. //00://.....r0000011/2//2222222/ 2213///cf41/
Atanasov, A., Zavatone-Veth J. A., and Pehlevan, C. Scaling and renormalization in high-dimensional regres- sion, 2024. BoLLatttss//arxx1..r//////////
00592
Bach, F. High-dimensional analysis of double descent for
linear regression with random projections. 2023, URL
D' Asccolii S., Refinetti, M., Biroli, G., and Krzakala, F. Double trouble in double descent: Bias and variance(s) in the lazy regime. In Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119, pp. 2p80 22880-2290, 2020. /ttp::ts:////ooeeeeee m r. w...ppres/vill 1e11119dd-cccllooo 1200l.120000.m. .20
https://arxite org. abs / 01372
Bahri, Y., Dyer, E., Kaplan, J.. Lee, J., and Sharma, U. Explaining neural scaling laws. Proceedings of the Na- tional Academy of Sciences, 121(27), June 2024. ISSN 1091-6490. doi: 10. 10.1073/pmas 1878121. URL dodx.doi.ooo org /0 10. 1073 www...pp........a/..aaa...aa.... 2311878121
Defilippis, L., Loureiro, B., and Misiakiewicz, T. Dimension-fres deterministic equivalents and scaling laws for random feature regression, 2024. URL https
Bordelon, B., Canatar, A., and Pehlevan, C. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
15699
Dem, N., Cunningham, J. P., and Pleiss, G. Theoretical limitations of ensembles in the age of overparameteriza- tion, 2024. URL htt.ps::/arxiv..rr/////aa// 16201
Bordelon, B., Atanasov, A., and Pehlevan, C. dy- namical model of neural scaling laws. arXiv preprint arXiv:2402.01099, 2024a.
Fedus, W., Zoph, B., and Shazeer, N. Switch transformers: Scaling to trillion parameter models with simple and ef- ficient sparsity. Journal of Machine Learning Research, 23(120): 1-39, 2022.
Bordelon, B., Atanasov, A., and Pehlevan, C. How feature learning can improve neural scaling laws. arXiv preprint arXiv:2409. 178588 2024b.
Breiman, L. Random forests. Machine Learning, 45(1):5- 32, 2001. doi: 10. 10..102//A:111119344443323 https //doi. http:///00.1112/1111103033330000
Fort, S., Hu, H., and Lakshminarayanan, B. Deep ensembles: A loss landscape perspective, 2020. URL. https:
srxiv.org/abs/1112 02757
Canatar, A., Bordelon, B., and Pehlevan, C. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1), May 2021. ISSN 2041-1723.
Ganaie, M., Hu, M., Malik, A., Tanveer, M., and Suganthan, P. Ensemble deep learning: A review. Engineering Ap- plications of Artificial Intelligence, 115:105151, October 2022. ISSN 0952-1976. doi: 10. 10.10166j.engappai..
10

---

No Free Lunch From Random Feature Ensembles
105151. URL engappai
Lepikhin, D., Lee, H., Xu, Y., Chen, D., Firat, O., Huang, Y., Krikun, M., Shazeer, N., and Chen, Z. Gshard: Scaling giant models with conditional computation and automatic sharding, arXiv preprint arXiv:2006. 16668, 2020.
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2), April 2022. ISSN 0090-5364. doi: 10.1214/21- URL 10. 10..0.111421110 http: doi. 4ttp://........../////...2223133
Lin, L. and Dobriban, E. beyond bias-variance via anova. Journal of Machine
What causes the test error? going
Learning Research, 22(155): 2021. URL http
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E.,, Casas, D. d. L.. Hendricks, L. A., Welbl, J., Clark, A., et al. Training compute-optimal large language models. arXiv preprint arXiv:2003.15556, 2022.
htm
Loureiro, B., Gerbelot, C., Refinetti, M., Sicuro, G., and Krzakala, F. Fluctuations, bias, variance &; ensem- ble of learners: Exact asymptotics for convex losses in high-dimension. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari. C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 14283-14314. PMLR, 17-23 Jul 2022. URL/tttp:://oooeedinngg presss v r162/loureiro222..1
Jacobs, R. A., Jordan, M. I., Nowlan, S. J., and Hinton, G. E. Adaptive mixtures of local experts. Neural computation, 3(1):79-87, 1991.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent ker- nel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Maloney, A., Roberts, D. A., and Sully, J. A solvable model of neural scaling laws, 2022. URL htttss:////x/tt org abs/aabs...2e... 16859
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint 2rXiv:2001.08361 2020.
Mei, S. and Montanari, A. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
Kato, T. Perturbation theory for linear operators. Springer Berlin Heidelberg, 1966. ISBN 9783662126783. doi:
10. 00.10077998-3-6622-222 022--66---113833 URL http://xx.. brc/10.10077978-333
12678-3
Mel, G. and Ganguli, S. A theory of high dimensional regres- sion with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139, igs
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http::://prccee..ggg..o
pp. 7578-7587 2021. URL htt.::: mir. mir.press/ wtt.press//v13mmel....... html
cc pe/paper..o httpppperfffeeeeeeeeee wtw.ee/s/pppeee///////////////// 2a22244477c2225510477fraaa888833
Meng, X., Yao, J., and Cao, Y. Multiple descent in the multiple random feature model. arXiv [math.ST], August 2022.
Pape
pdf
LeCun, Y., Bengio. Y., and Hinton, G. Deep learning.
Nakkiran, P. More data can hurt for linear regres- sion: Sample-wise double descent. arXiv preprint 1rXiv:1912.07222.200
Nature, 521(7553):336444, May 2015. ISSN 1476- 4687. doi: 10. 10t.1088/nture455395 URL http://dx doi. Noi.org/10... 1038/100000 http//auuuure99999 101111011100///aaeee5533333
Lee, J., Bahri, Y., Novak, R., Schoenholz, S. S., Pennington, J., and Sohl-Dickstein,) J. Deep neural networks as gaus- sian processes, 2018 URL htttp:://arxiv.oot
Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, I. Deep double descent: Where big- ger models and more data hurt, 2019. URL https 7/arxiv. Tfarxiv.org/abs/// 912. 02292
abs/1711. 00165
LeJeune, D., Javadi, H., and Baraniuk, R. G. The implicit regularization of ordinary least squares ensembles, 2020.
Nakkiran, P., Venkat, P., Kakade, S., and Ma, T. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.0/897 2020.
URL http:ss//aarii..or//a//////1/11/ 04743

---

No Free Lunch From Random Feature Ensembles
Novak, R., Xiao, L.,, Hron, J., Lee, J., Alemi, A. A., Sohl- Dickstein, J., and Schoenholz, S. S. Neural tangents: Fast and easy infinite neural networks in python, 2019, URL https://arxiv.om org/ wttp://ggaaaoooo 32803
Lavatone-Veth, J. A., Tong, W. L., and Pehlevan, C. Con trasting random and learned features in deep bayesian linear regression. Physical Review E. 105(6), June 2022. ISSN 2470-0053, doi: 10.1103/physreee.100 064118. URL 1tt.tttt///.......rrr/1011.1111
32803
Patil, and LeJeune, D. Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning. 2024.
PhysRevE. 105. 064118
UKl.httpsss//arrttvorr/////////s 04357)
Patil, P., Du, J.-H., and Kuchibhotla, A. K. Bagging in over- parameterized learning: Risk characterization and risk monotonization. Journal of Machine Learning Research, 24(319)1--13,22 2023.
2023.
Rahimi, A. and Recht, B. Random features for large-scale scale kernel machines. Advances in neural information pro- cessing systems, 20, 2007.
Rocks, W. and Mehta, P. The geometry of over- parameterized regression and adversarial perturbations, 2021. URL
14108
Ruben, B. S. and Pehlevan, C. Learning curves for heteroge- neous feature-subsampled ridge ensembles, 2023, URL
pettss///arxii /30 03176
Simon, J. B., Karkada, D., Ghosh, N., and Belkin, M. More is better in modern machine learning: when infinite over- parameterization optimal and overfitting is obligatory. CoRR, abs/2311 I. 14646, 2023. doi: 10.48550/ARXIV.
2311.14646. URL htt.t:tpps........... /ttttts:://o... orrboo..rrr/oo. 485500
arXiv. 14646
Theisen, R., Kim, H., Yang, Y., Hodgkinson, L.,, and Ma-
honey, M. W. When ensembles really effective?, 2023. org. httggabs//2.. 200.e////....... 223111333311
URL
12313
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M.. Reddy, T., Cournapeau, D., Burovski, E., Peter- son, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., and et al. Scipy 1.0: fundamental algorithms for scientific computing python. Nature Methods, 17(3):6612773 Feb 2020. doi: 10. 10.10888441592-0019-6666----222 2. URL http: 0rc/10.1038/s41530
Vyas, N., Atanasov, A., Bordelon, B., Morwani, D., Sainathan, S., and Pehlevan, C. Feature-leaming net- works are consistent across widths at realistic scales, 2023.
URL /
18411
Wei, A., Hu, W., and Steinhardt, J. More than toy: Random matrix models predict how real-world neural representa- tions generalize, 2022. URL htt.tttts///xii.oott abs/ 0.203.06100
12

---

No Free Lunch From Random Feature Ensembles
A
B
N-10
0.9
P-62
N=30
Optimal Test Error
0.9
P=379
Optimal Test Error
N=89
P=2336
N=264
N=785
0.8
N
0.8
N=6952
0.7
1
2
4
8
2
K
K
Figure S1. by at optimal ridge as function of ensemble size K for binarized CIFAR-10 10 RFRR classification. (A) We fix N 256, values indicated in legend. (B) We fix / 256, N values indicated in legend. Error bars show standard deviation across 10 trials.
13

---

No Free Lunch From Random Feature Ensembles
A
a == 1.2, /= 1, P= 10
B a = 1.2, r= 1, P
1000
C
a= = r=
Optimal Test Error
N 16
10-
P=10
3x10-1
N 32
10a
1000
N 64
10
10000
N = 128
2x10-1
N 256
10a
K 10'
=
10a4
10-1
KN
M
10a
10
10"
101
10º
10a
100
10a
10²
101
10a
K
K
N
D
CIFAR 10
E
CIFAR P 1000
F
CIFAR
9.84 x 10
Optimal Test Error
10a
9.82 10
90
8 10
9.78
K 10a
x0-
x00
- 10
7 x 10
9.72 x 10-1
P 1000
9.7 10
10a
10000
10"
10a
10a
10a
10*
10a
10a
10a
10a
102
10a
K
K
N
Figure S2. (A, B, D, E) We plot theoretical values for E at optimal ridge function of ensemble size K for RFRR with power-law eigenstructure with source exponent = and capacity a = 1.2 (A, B) and for the NNGP kernel associated with the binarized CIFAR-10 classification task (D. E) Random features per ensemble member N shown in the legend. The dotted black line shows Ey for single RPRR model with N = M 2048 features. Sample size P is indicated in the title. (C, F) We plot the ensemble size K for which an ensemble of RFRR models with size N performs least well single RFRR model with M 2048 random features. P values indicated in legend. As predicted by corollary 5.5 all curves lic above the dotted line KNN M. This bound appears tight when P < N.
14

---

No Free Lunch From Random Feature Ensembles
A
K
K = 2
K = 4
K 8
10
Experiment Optimal
Test Error
0.4
0.4
0.4
10c
1001
0.3
10
10
10
10
10
10
10a
10
10
P
P
P
P
B
K
K =
K =
K = 8
101
Test Error
0.4
0.4
10
10
0.3
10
10-3
10a
102
10a
10a
10
102
10a
10a
10a
102
10a
104
10
102
10a
10a
P
P
P
P
C
K
K
K 4
K 8
101
0.38
0.4
0.4
0.36
0.34
10c
Test Error
0.34
0.32
0.3
10-1
0.3
0.28
10-2
0.26
10-3
10a
10a
103
104
10
102
103
104
10a
102
103
104
10a
10a
103
10a
D
K
K = 2
K = 4
K 8
0.30
10a
0.36
0.4
10c
Test Error
10-1
0.3
0.3
10-2
0.26
10-3
101
102
10a
10
102
10
102
10a
102
10a
N
N
N
N
Figure S3. 0-1 Loss for binarized CIFAR-10 RFRR task under score-averaging (A, C) and majority vote (B, D) ensembling schemes. As Fig. [ Errors shown (A, as function of for fixed 256 and (B) a function N for fixed P 256. K value indicated in title and À value in colorbar. Red line indicates optimal ridge determined by grid search. Markers and crror bars show mean and standard deviation over 50 trials.
15

---

No Free Lunch From Random Feature Ensembles
A
P 128
P 1024
8192
102
2
0.9
Experiment
Theory
0.7
Test Error
A optimal
0.6
100
0.5
1
079
0.9
0.8
0.4
10-2
0.7
0.8
0.6
0.5
0.3
0.6
0.4
10
100
10
102
100
10a
102
100
10
102
K
K
K
B
C
K=1
= 1024
Optimal Test Error
K=2
K=4
6 10
Test Error
K=8
K=16
100
K=32
10-1
P=
K=64
1024
K=128
x 10-1
8-92
10"
10a
102
10-3
10-1
10
K
A
Figure S4. No Free Lunch from Ensembles Random Feature Models. Eg for kernel RF regression on an MNIST classification task. (A) Warying K and N while keeping total parameter count M 1024 fixed. The sample size P is indicated above each plot. (B) Error Ex optimized over the ridge parameter À increases monotonically with K provided the total parameter count M is fixed. Dashed lines show theoretical prediction using eq. and markers and error-bars show
and standard deviation of the risk measured in numerical simulations across 10 trials. (C) We show error as function of À for each K value simulated and P = 8192. Dashed lines show thcoretical prediction using eq. 20 and shaded regions show standard deviation of risk measured in numerical simulations
trials.
16

---

No Free Lunch From Random Feature Ensembles
A
B
C
8x10
P-1024
10
Var; /
10"2
P=8192
Bias
Var,
1x
10
6 10-1
109
10
10a
10a
10'
102
10a
10a
10a
K
F
10a
P=128
P-1024
6 10-1
P=8192
Var; /K
Bias
Var=
10-2
40-1
10:3
3 10-1
10.2
2 10
10a
10a
10a
10"
10
10'
K
Figure S5. Bias-Variance decomposition of optimal ridge for binarized CIFAR-I0 (A, B. C) and MNIST (D, E, RFRR tasks. We vary K and N while keeping total parameter M = 1024 fixed. Bias, (A, D), single-predictor variance Var, (B, E), and ensemble-predietor variance Var, K (C, F) are calculated from theoretical expressions 19
17

---

No Free Lunch From Random Feature Ensembles
A
128
1024
P 8192
10a
0.3
04
0.4
Test Error
100
0.3
10
0.2
10-4
100
10a
10a
10a
10a
10a
109
10a
10a
B
128
P 1024
P = 8192
102
0.3
04
Test Error
100
10
02
10
10
10a
109
10
102
10
10
102
K
K
K
C
128
1024
P 8192
10a
0.3
0
0.2
Test Error
109
10
0.08
0.07
0.1
10-4
10a
10A
102
10a
10
102
109
10a
102
K
D
128
P 1024
P = 8192
10a
0.2
Test Error
100
0.2
033
0.1
10-2
02
0.1
100
10a
102
109
101
102
109
10a
102
K
K
K
Figure S6. 0-1 loss for binarized CIFAR- 10 (A, B) and MNIST (C, D) RFRR classification tasks under score-average (A, C) and majority vote (B, D) ensembling. We sweep K and N keeping M KN 1024 fixed. Sample size P indicated in titles. Colorbar indicates ridge parameter. Red indicates optimal ridge determined by grid search.
18

---

No Free Lunch From Random Feature Ensembles
A
CIFAR 10
B
CIFAR 10
10 -4
Fit d=1.42
Mean Squared Error
Fit 8=0.08
Trace Metric
MSE Test Set
x 10
Tr
10-5
7
103
P
104
10a
P
10a
C
MNIST
D
MNIST
c=1.53
Mean Squared Error
x.75
Fit B=0.31
Trace Metric
2.5x10
Test Set
x.25x10
10
2
1.75 x 10
1.5x 10
10-6
1.25 x 10
10-1
10a
104
103
10a
P
P
Figure S7. We measure the eigenspectrum of the NNGP kernel applied to the CIFAR-10 10 and MNIST datasets, as well as the target weights for the binarized classification tasks described in Appendix E2 Estimates for the source and capacity exponents obtained fitting the
"trace metric" [tr [H,]* --= and the MSE loss of kernel ridge regression with the limiting NNGP kernel to power laws (see Appendix
B.4 for details).
19

---

No Free Lunch From Random Feature Ensembles
A. Extending the Random-Feature Eigenframework to Ensembles
We consider the RFRR setting as described by (Simon et al. 2023), extended to ensembles predictors. A detailed description of this extended framework Let D ppps yp training of P examples, where zp RD are imput features and Up IR are target values generated by a noisy ground-truth function yp f=(pp) + ep and the label noise Cp lid. o.)
We consider ensemble of K random feature models, each with N features. The total number of features is thus M = K N. For each model & = I..... K. we sample N feature vectors {w) i..d. from measure j over R (we will use upper indices to represent the index of the ensemble member, and lower indices to represent indices of the training examples and features). An ensemble of featurization transformations are defined as vb x + (g(o, x) ) where g TR R R is square-integrable with respect to pa: and plg- The predictions of the ridge regression models are then given (z) w //xx//V where the weight vectors wh are determined by standard linear ridge regression with ridge parameter A:
úh ( D
& y v N
w AI
(A.1)
Where the matrices T NxP have columns (eb* (x1); 2/5 (a:p)] and the vector y E IR. has [y]p = yy- For each ensemble member, this is equivalent to the kernel ridge regression predictor:
fx(()) = h2.x +xxx+*l
(A.2)
Where the matrix [Hxxlpp] H (xp, xp) and the vector [hx = H (xx, xp) with the stochastic finite-feature kernel
H (x,
Σ N ==1
s( x ()g((, a²) k k= 1,...,, K
(A.3)
In the limit of infinite features, this stochastic kernel converges to a deterministic limit ( x²) + H(x x²). Because we consider the feature function to be shared across ensemble members, this limit is independent of The ensemble prediction the average of individual model predictions:
K
1
feus (x)
(x)
(A.4)
K
Finally, we measure the test error as the mean-squared error the ensemble as the mean- mean-squared error on a held out-test sample:
FKK Feees [[Jeus (m) S. (a:)) + 9
(A.5)
For binary classification problems, we may be more interested in the classification error rate for the learned predictor. Given an ensemble of scalar output "scores" f (.)...... f score-averaging and vajority-vote ensembling (Loureiro al. 2022):
2 x, two possible schemes to assign the class of the test example x are
SAA (x)
Sign
f*(x)
(z)
(Score-Average)
(A.6)
K
MV (x: =
Sign
Σ
Sign (F*
(Majority-Vooe
(A.7)
The classification error rate then given as the probability of mislabeling a held-out test example.
A.1. Spectral Decomposition of the Kernel
The feature function g permits spectral decomposition as follows:. Let T (pv)) + L?(Hz) be the linear operator defined by:
(Tr) /
(()))(1,
(A.8)
R
20

---

No Free Lunch From Random Feature Ensembles
The singular value decomposition of T (Kaoo 1966) yields orthonormal bases {6n of (T) C (2 and _ (dn of 1.2 (1m), where { are the eigenvalues (in decreasing order) and (Gr ] the corresponding eigenvectors integral operator E: : L² (ux) L (M²) given by
(Eu)(a)= = 1 u(x') x a))
(A.9)
We can write Σ 7 where 7 L2 (Um) + L (wo) denotes the adjoint of T. The feature function g can then be decomposed as g(v Ex= (T)
Under these conditions, we may write the stochastic finite-feature kernel functions as:
N
# (1, x²)
(A.10)
N 1= t.
Using the orthonormality of the bases, the deterministic limit of the kernel function can then be expanded as
H x²) = Σ (cdr())))sa')) = Σ (x'))
(A.11)
where we have defined 0+(x)= = (2)) We see that that the singular values {nc} of the operator double as the eigenvalues of the limiting kernel operator H. We will assume that the ground truth function fz) can then be decomposed as: f=) E. (x). Any component of f. which does not lie in the RKHS of the kernel could, in principle, be absorbed into the noise of Cannttar et al. 2021).
A.2. Gaussian Universality Ansatz and the connection to Linear Random Feature Ridge Regression
As in (Simon al. 2023 Atanasov et al. 2022), , we adopt the Gaussian universality ansatz, which states that the expected train and test errors are unchanged if we replace {St} } and { with random Gaussian functions {Ge) and { such that ((()) ~ (V0 1) and d. (x) ~ (0, 1) for v ~ Py and a ~ Max respectively.
The finite-feature stochastic kernels can then be written Hi (x,x') x') 0 (zx) (xx') where ('(x) (xx) and the entries of -* E N are drawn i.i.d. as (O, 1/N) and we have defined H to be the (possibly infinite) dimensionality of the reproducing kernel Hilbert space (RKHS) of H. The learned functions can then be written as
(xx = u (x+)
nh = t TZ + z²O
(A.12)
Where = (0(z)). 0(zp)), and the vectors 0(zp) ~ (O, with A a diagonal matrix with A = 7/. This is
precisely the setting of linear ranturefeature model with data covariance spectrum (m, ....... (Atanasov et al. 2024
Under the Gaussian universality ansatz, we can therefore re-cast RFRR as linear RFRR with the role of the spectrum of the "data" played by the spectrum { of the limiting deterministic kernel H.
B. Notions of Deterministic Equivalent Error
Here, we review the notions of deterministic equivalent error relating the "true" error &K of a RFRR ensemble to its deterministic approximation E While E is random quantity, depending on the particular realization of the dataset D as well the random-feature weights (w,) However, many works have found that the stochastic quantity EK concentrates about a deterministic equivalent error 9 which depends on the dataset and random features only through their sizes P. N, and K (see eq. 20). The exact relationship between g and EK however, varies in the literature. Here we describe two notions of deterministic equivalence, and discuss how and when they apply to the relationship EK ~ EK employed in this work.
To derive a deterministic equivalent error formula, many works examine an "asymptotic" regime, in which both N, P - do with a fixed ratio ratio P/N- ~ (1). This permits the use of tools from random matrix theory to analyze the learned predictor. This approach is reviewed in (Atanasov et al., 2024), and we defer the reader to the citations therein. Under the
21

---

No Free Lunch From Random Feature Ensembles
gaussian equivalence assumption which we employ, eq.
20 is straightforward application of the error formula for linear
random feature models (Atanasov et al. 2024 2022 Adlam & Pennington, 2020 Maloney al. 2022), with the role of the "data" played by the infinite-dimensional features of the RKHS of the limiting kernel H (x, x'). While asymptotic
equivalence holds only in the limit N, P > oc, the resulting formulas often serve as a good approximation at finite N and P
A stronger notion of deterministic equivalence between E/ and E was recently proven by Defilippis et al. without the assumption of Gaussian Equivalence, resolving the conjecture of (Simon et al. 2023) for single models (K = 1). Specifically, Defilippis et al. proved "dimension-free" deterministic equivalence which guarantees that
[g - - c
vP )
with high probability, for factor C' which is logarithmically small in N and P. Unlike asymptotic deterministic equivalence, dimension-free deterministic equivalence applies at fixed, finite P and N. While at the time of writing the dimension-fre free deterministic equivalence has not been proven the the case of ensembled RFRR (K > 1), we anticipate that the arguments of (Defilippis et al. 2024) could be extended to the ensembled case.
C. Proof of Theorems 4.1 and 5.1
In this section, we will refer to the condition that Σ. W >> 0 the task having "learnable component." It can be shown from eq. [4 that Df, S min(N, P). Because N and P are finite and rank((n ) is infinite, it follows that K2 > 0. The following inequalities then hold strictly:
Dig Df1
72
71
0 <<p<1
(C.1)
We verify all deterministic equivalent error formulas used here by comparing to numerical experiments.
Furthermore, the inequality (k) < (f, (x) holds, with strict inequality when the target has learnable component. In each of the proofs that follow, we aim to show that the error of aanom-ffeture ensemble decreases monotonically under certain transformations of the parameters (K, N, P) + (K', N", P') when the value of the ridge parameter À is set to it's optimal value. We will argue using the invariance- based method introduced by (Simon et al. 22023). .. Denote the errors before and after the transformation by F. (N, P, A) and F (N', P", X'). We allow here for the regularization À before the transformation to take an arbitrary value. Then, we will prove that there always exists a value X' such that E (N', P', X) I E (N, P.A). Proof follows by setting X equal to it's optimal value X and noting that min, EK (N', ,) & EK' (N' P', X' S FKK (N, P,) Below, we will prove the existence of X' under the desired transformations.
C.1. "Bigger is Better" Theorems
We begin with the setting of the 4.1 so that we must prove error decreases under any transformation (K, N, P) + (K', Nº, P') such that K < K", N < N', and P < Pr. We note that it suffices to prove that E&K decreases monotonically with K, N, and P separately, since any transformation P,) + (K', N', P') can be taken in steps K + N + N', P- P
Monotonicity with K The fact that when K' > K and all other variables are held fixed, EEK decreases is immediately evident from the form of eq. 20 because Bias; and Var, are independent of K. Furthermore, the inequality is strict as long as Var, > 0, which is valid as long as the task has learnable component.
Monotonicity with P Consider transformation P + P with P' P. Examining eq. 14 we see that it is always possible to increase the ridge À such that H2 remains fixed. We then rewrite E,K as:
1 K
1 K
Ex (1
2 + E Bias?
(C.2)
With K2 and N fixed, we see that only the fre-factor of I-72 in Fy will be affected, so that Fj decreases with P. Note also that " is decreasing function of P. With K2 and N fixed, it follows that Ed decreases with P. Finally, because K is fixed, EKK will decrease with P.
22

---

No Free Lunch From Random Feature Ensembles
Monotonicity with N Consider transformation N + N' with N' N. Examining eq. 14 we see that it is always possible to increase the ridge À so that 62 remains constant. With Kig, P fixed, Bias is fixed as well. From eq. C.2 then suffices to show that Eg decreases. To see this, recall that p is an increasing function of N, and is decreasing function of p. We then have that Yi is a decreasing function of so that the pre-factor of I- in eq. 12 is decreasing with N.
C.2. "No Free Lunch" from Ensembles Theorem
We now prove theorem 5.1 We first recall the form of the error to be:
E Bias (Eg 1P--Bic -Bias
(C.3)
We define the variable y/ K. By analytical continuation, it suffices to show that test risk decreases as v increases when M = KN is held fixed. Rewriting the self-consistent equation in terms of v, we have;
AN
K2 (P- - Df (f2 - Df
(C.4)
-f( (k2))
Consider a transformation v + v/ where // v. We se that it always possible to increase À so that K2 remains fixed. Note that Bias? depends only on K2 and P. so that as (and therefore N) vary, Bias, remains fixed. From eq. 20 it therefore suffices show that v(Ee Bias?) decreases with v. Rearranging terms, we have:
-nny (122) + (1 - p)mz (K22)
- -n3 ts' (K22
v (E g
Bias?)
=V
(C.5)
m1
1 72
+
6²
(C.6)
- n
1 1 72
We first show that
d
1
72 )
0,
(C.7)
dv
7
To see this, recall that p (vM (D Df2). Because Df, > Df2, this is monotonically increasing function of
v. We may write 71 = P [11 p) Df, +p Df2]. From this equation it is clear that 71 72. Differentiating with respect
v, get
dp M (Df, Df2)
(C.8)
dy (vM D22)2
d'2 1 (Dr, Dí2) dp
M (Df, Df2)
(C.9)
dv P
du
P (vM Df2)²
Using these, we have:
d
1
1
(C.10)
dv
1
-
71
- 72
1
1
v d'ys
+
dy
(C.11)
71
1 72
}
(DI, D22)²
1
Mv
(C.12)
(1
(MM Df2)
P(1 (22)
P(1
(vM -fz)
0
(C.13)
23

---

No Free Lunch From Random Feature Ensembles
where in the last line, have used the facts that 71 72 and Df2 S vM. To show that
d
(=pnn
pm3 tfy (12) + - p)= tfi (M2)
-nž tfi (K22)
]]
S 0,
(C.14)
dv
72
we first note that -pkn 2 tf (K2) (1 - p)l² tf (k2) can be equivalenty written as n₂ thi (K2) (1 p)le tf2 (x2). The
above derivative then be broken into parts:
d - Aig tfj
1 - 72 )1
v(1 p) dv 1
+ 12 tfz
(C.15)
dv
We have already shown that the derivative in the first term is negative. Furthermore, -n3 tfy 2 0, with strict equality holding when the task has a learnable component. To see that the derivative in the second term is negative, note that i an increasing function of y. Because 7/ is a decreasing function of p. is therefore a decreasing function of v. The denominator 1 --11 inside the derivative increases with v. Furthermore, the numerator v(1 p) can be written as - - vM-D1, With K2 fixed (so that Df - Dfz > 0 is fixed), this is a strictly decreasing function of v. follows that
d v(1 p) 71
Rig lf2
0.
(C.16)
du
with strict inequality holding as long as lf2 > O, which is true whenever the task has learnable component.
D. Derivation of Scaling Laws
using methods described in (Atanasov ct al. 2024). We assume that the kernel eigenspectrum decays as тe t-a and the power of the target function in the modes decays w.n. t- (1+22r)) and examine the regime where P > N, that the width of the ensemble members is the bottleneck to signal recovery. We begin by analyzing the self-consistent equation for K2, reproduced here for clarity:
In this section, we derive the bidth-botttenncked scaling laws given in section 6.2
AN
R2
(D.1)
(P DI, (M²) (M2)))
Because (N2) < min,N, P) and equation
P. it follows that P > Df, (N22) We can therefore approximate the fixed- seedt-point
A
Pw2 1- N (ri2)
(D.2)
We approximate Df, using an integral:
(f2 2 /
000 x-
dt
(D.3)
1-a + K2
Making the change of variables u = tx. 1/a
we get
-1/a 0 du
DF Re Kig
(D.4)
1/1
+
Plugging back into the fixed-point equation, we arrive at Next, we make the ansatz that K2 N The fixed point equation becomes
A
K2P P
~
(D.5)
du
1t
PN
(D.6)
1
N
-
du
1440
24

---

No Free Lunch From Random Feature Ensembles
The left size of this equation will be very large, due the separation of scales P > N. The only feasible way for the right side scale with P is for the denominator to become very small as N grows. This is only possible if N9/a N, that q We therefore have K2 N Na
With this scaling for we have Df Dfg N. is then clear that + 0 for P >> N. Furthermore, because p [0, 1]. and ?1 - for P > N. The pre-factors of T- I-m can therefore be ignored.
may then write
1+1 dt N 2ar ( u (1+2ar) /
000 t- (1+22r))
22 (f2
1/N 1 u du
(D.7)
where t/ and we have made the substitution N We get two contributions the integral: when is near 1/N, get contribution (including the pre-factor) which scales N When is away from 1/N, the integral contributes constant factor and we get contribution that scales as the pre-factor N-2or,
Similarly, we may write:
t- (1+2ar)
( u (1+2ar)
22 (K2)
(1+1-a /x2) dt N N-2ar 2ar
J/N (1 + a= du
(D.8)
The contributions from the component of the integral near 1/N will scale N-2o and the contribution away from I/N will remain N-2ar, Combining these results, we arrive at separate scaling laws for the bias and variance terms of the error:
Bias² N 20 min(r.1)
(D.9)
Var. ~ N 2a min(r.))
(D.10)
Finally, to obtain eq. 26 we put N M and K M and substitute into eq. and variance scale
20 We find that, in terms M. the bias
Bias? M- 2ta min(r.1)
(D.11)
Var, M (1 2ad 2nn
(D.12)
The scaling the total loss for an ensemble will be dominated by the more slowly-decaying of these terms.
D.1. Hample-Bottleneckeee Scaling
We next examine the case where P < N. Here, we find that Df, (K2), (12)))) & N so that p - 1, Var, + 0, so that the most significant contribution to the error comes from the bias: The only significant contribution to the error will come from Bias?, which will scale (Atanasov et al. 2024):
EK
20 min(r.1)
(A < Pl-a)
(D.13)
E
(2/P) 22ip)2min(s.)))
(A > pl-a)
(D.14)
We therefore see that the ensemble size K and network size N have no effect on the scaling law in provided P < N.
D.2. Overparameterizee Ensembles with Small Ridge
Here, we analyze the behavior of ensembles of RERR models in the overparameterized regime (N > P) and with small ridge A. We set the scale of the noise a, = 0 for simplicity. We write the "renormalized ridge" Ki and degrees of freedom as
25

---

No Free Lunch From Random Feature Ensembles
power series in the small parameters I/N and X, which assume be on the order of magnitude.
K2 ~ Kp 8/N ad
(D.15)
Dr (K2) R P + (r + aA)
(D.16)
(22( = (rz - Df2((2
+ aA);
(D.17)
for some parameters 6, a which are (11) in 1/N and X. Plugging these into the fixed-point equation (eq. 14 and expanding
about = 1/N = 0, we can solve for a, by matching coefficients at first order:
(D.18)
K2 Df (155)
XPr3
8 = 2x n2 Df (x:))
(D.19)
Finally, expanding equations 19 in power series in 1/N and X, obtain the following (for oe 0):
PRn tf (ne)
B
XF P) O(12, 1/N,1
(D.20)
P- ((2(())))
Pnž tf (Kz)
Var:
+ 1A2,,//N11/N
(D.21)
where
P P(PP-f tlz + K3 (Kz) tf (Kt)) Df, (xt)) - Df (n₂))²
[K2g, P)
(D.22)
This gives us that, to leading order in À and 1/N, the error of an ensemble of K RERR models, each with N features, can be written
Pxg tf (N:)) Ex P- D(2 + AF P) Pn
+ +O A/N.1//)N11/3)
(D.23)
KN
We note that, at leading order, this depends ensemble size K and model size N only through the total number of features KN.
E. RFRR on Real Datasets
E.1. Numerical Experiments with Synthetic Gaussian Data
For a given value of a and r, we fix a large value D >> P.M and generate cigenvalues ny x t- and target weights W t - -10oarr) The N) and wi are normalized so that E, n and Σ, w.n) We generate random features ② ΣX RDXP, where X,j ij No, 1) and Σ is the diagonal matrix with entry Σ., Me. Labels are assigned as = v w R... For each l 1, ...... K, we perform linear RFRR (eq. A.12 with independently drawn projection matrix ² with entries drawn from (0, 1/N). The prediction of the ensemble is then given as the mean over the K learned predictors. We use this procedure to generate numerical error curves in Figures and S2 A-C.
E.2. Numerical Experiments on Binarized MNIST and CIFAR-10 with ReLU Features
We perform RFRR CIFAR-10 and MNIST datasets. To construct the dataset, we sort the images into two classes. For 100,R-10, we assign a label +1 to images of "things one could ride" together (airplane, automobile, horse, ship, truck) and label = -1 for "things one ought not to ride" (bird, cat, deer, dog, frog) (Simon et al.) 2023). For MNIST, we assign a label y = +1 to digits 0 4, and a label -1 to digits 5-9. We construct K feature maps as ((*x) VN
1 ReLU (V x).
where V ~ D) Here, is the data dimensionality (D 3072 for CIFAR- 10 and 784 for MNIST). Then, for each ensemble member = 1,..., K, we train a linear regression model on the features S In the fefnite-featurr limit, the finite-ccature kernels will converge to the "NNGP kernel" for single-hidden layer Relu network (Lee et al. 2018). This
procedure was used to generate numerical error curves for figures
ST D-F
S6 and S7
26

---

No Free Lunch From Random Feature Ensembles
E.3. Theoretical Predictions
We evaluate the omniscient risk estimate 20 numerically using vectors storing the values of {m:}s= and (w) In the case of synthetic data, these vectors are readily available. For the MNIST and CIFAR-10 tasks, approximate these vectors by evaluating the infinite-width Neural Network Gaussian Process (NNGP) kernel using the neural tangents library (Novak et al. 2019). For 30,000 images from the training sets of both MNIST and CIFAR 10, we evaluate the kernel matrix [H] [Hpp H pp ). and diagonalize the kernel matrix to determine the eigenvectors and eigenvalues. To be precise, with P 30, 000, we calculate the cigenvalues (71, T2...... 7p} and eigenvectors { [u1 {u1..... up} of the cample-normalized kernel matrix + H. We then assign the weights the target function as W, PPn u, y, where y E R is the vector of labels associated to our P samples.
We then solved the self-consistent equation (eq. [4 using the Bisection method of the scipy library (Virtanen et al. 2020). and evaluate eq. 20 to determine the predicted risk.
E.4. Measuring Power Law Exponents of Kernel Ridge Regression Tasks
In fig. B.. we plot theoretical predictions for the scaling exponents of the bias and variance contributions to error for the binarized CIFAR-10 10 and MNIST classification tasks. To calculate these exponents, we need access the "ground truth" source and capacity exponents and characterizing the kernel eigenstructure of the dataset and the target function, such that the eigenvalues (m, "/,,,-,- } of the NNGP kernel decay 1/2 t~ and the weights of the target function [W, ......) decay as 15 ~ t (1+266), To estimate å, we calculate the "trace metric" [tr [[]
then obtained ~p= where H, E RPX is the empirical NNGP kernel for p randomly drawn
by fitting to the relationship fr H p 2022 SSion al. 2023) (figs. 57 A,C). To estimate the source exponent v, we use the samples from the dataset (Wei al. scaling law for Kernel Ridge Regression (with the limiting infinite-feature NNGP kernel) which dictates that for small ridge, Eg p 2a min(r:1) (see Appendix D.1). Following Simon et al.
we fit the MSE loss for Kernel Ridge Regression with the limiting NNGP kernel to power law decay Eg p (figs. S7 B.D), and assign f 3/2/a.
F. Code Availability
All code
used to generate http://ggttb..cmmmmmmmmmne////aa Feature "ratuure_Esemblesppo
the figures presented
in this work
publicly
available at
27


Reviews:
[{"review_id": "Urgv5v5yWu", "reviewer": "Reviewer_2SLL", "summary": "The paper investigates the performance of random feature ensembles, and discusss whether the ensemble models outperform the single model when the number of total parameter is fixed. The theoretical analysis is given based on the random feature ridge regression, while the empirical studies are performed on binarized CIFAR10 task. The paper provides two main results, the first one shows the RF ensemble models always benefit from the larger ensemble member and the more ensembles, while the second shows when there is a fixed total parameter count, increasing the number of ensemble size $K$ degrades the performance with an optimal ridge parameter. Moreover, the paper also derives a acaling law for the underparameterized ensembles.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Rebuttal to Reviewer 2SLL (Complete)\n\nThank you for your review and questions.  It appears that you are convinced of the correctness of our results, but have concerns about the significance of the contribution.  We will respond to your concerns and questions individually below:\n\n>1. The contribution of this paper is limited; the results are somewhat evident and can be derived from prior works.\n\n**Response:**  The error formulas for RFRR ensembles derived in previous works are not easily interpretable, and studying the implications of these deterministic equivalent errors is an important task unto itself.  We believe that our paper has addressed an important gap in our understanding of ensembled random feature models. We have used the (known) bias-variance decomposition of the test risk of RFRR to study the tradeoff between model size and ensemble size.  Specifically, we have shown that:\n- Ensembling is *never* optimal under a fixed parameter budget at optimal ridge.\n- Ensembling can achieve near-optimal performance in both the overparameterized and underparameterized regimes, with precise spectral conditions for near-optimal scaling in the underparameterized regime.\nIf accepted, we will clarify these contributions in the abstract and introduction.  We may also change the title of the paper to \"No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions\" to highlight our contributions beyond Theorem 4.1.\n\n>2. The results mainly pertain to the random feature ridge regression model; whether they apply to deep learning models remains unaddressed.  \n\n**Response:** While we are ultimately interested in understanding the utility of ensemble learning using state-of-the-art machine learning models, random-features regression provides an important \"ground-floor\" to investigate the utility of ensemble learning in a tractable setting.  Furthermore, because of the approximate correspondence between RFRR and deep networks trained in the lazy learning regime [3], our results already bear some relevance to deep ensembles.  Understanding the properties deep ensembles trained in the rich regime is a critical research direction for our future work, but will be better presented with reference to these baseline results in linear models, which have already saturated the page limit for this venue.\n\nOur results also add to a long history of research on random-feature models in analogy to deep networks. Another example of this fruitful correspondence is work on fine-grained bias-variance decompositions [2]\n\nWe have also performed numerical experiments for deep ensembles.  In these experiments, we train ensembles of deep convolutional neural networks on a computer vision task (CIFAR10 image classification) using $\\mu P$ parameterization, which keeps training dynamics consistent across widths [1].  In addition to the weight decay, there is a \"richness\" parameter $\\gamma$ which controls the amount of feature-learning in the network.  Our simulations show that a large network outperforms any ensemble of smaller networks with the same total size when both the weight decay and \"richness\" parameter are tuned to their optimal values.  If it will have a positive impact on your evaluation, we are willing to add these numerical results to the supplemental material.  This result is available at this anonymized github repo: https://anonymous.4open.science/r/NoFreeLunchRandomFeatureEnsembles/README.md\n\n>3. The layout of the figures is irregular, and the fonts in these figures could be improved.\n\n**Response:** Thank you for your feedback, we are open to any and all suggestions on how to improve the clarity and appearance of our figures for the final version of this paper if accepted!\n\n> \"Most of the experiments are based on the random feature (RF) model. Would the same results hold for larger ensemble models?\"\n\n**Response:** See our response to 2. above.\n\n\n[1] Nikhil Vyas, Alexander Atanasov, Blake Bordelon, Depen Morwani, Sabarish Sainathan, and Cengiz Pehlevan. Feature-learning networks are consistent across widths at realistic scales, 2023. URL https://arxiv.org/abs/2305.18411.\n\n[2] Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine-grained bias-variance decomposition, 2020. URL https://arxiv.org/abs/2011.03321.\n\n[3] Chizat, L., Oyallon, E., & Bach, F. (2020). On lazy training in differentiable programming (arXiv:1812.07956v5). Retrieved from https://arxiv.org/abs/1812.07956", "claims_and_evidence": "The paper provides the sufficient theoretical analysis to support the claims, and the experiments based on the random feature ridge regression on binarized CIFAR10 task also shows the convincing results.", "methods_and_evaluation_criteria": "The theorems and results provided in this paper are easy to understand, and there are several works referenced in this paper already give the similar analysis that decreasing the random features $N$ leads to a poor performance. The proposed results are clear and make sense for the emsemble RF models.", "theoretical_claims": "The paper presents the theoretical analysis to prove the theorems, and the claims is proved based on the prior works and some obvious inequations.", "experimental_designs_or_analyses": "The experimental studies are sufficient and verify the claims in this paper. The Figure 1 shows increasing the number of samples P and the ensemble member size N can reduce the predictor error, while the Figure 2 shows increasing the number of ensemble menbers K while fix the total number of random features M, the performance of ensemble model degrades.", "relation_to_broader_scientific_literature": "The results presented in this paper is clear and evident, the theoretical analysis is mainly based on the prior works, and the results are mainly focus on the random feature ridge regression model, whether the results are useful for the other machine learning models or deep neural networks are unclear.", "essential_references_not_discussed": "No additional references need to be discussed here. The authors have covered all the essential studies in the experiments or the related work.", "other_strengths_and_weaknesses": "Weaknesses:\n1. The contribution of this paper is limited, the results in this paper are evident, and can be easily derived based on the prior works.\n2. The results mainly based on the random feature ridge regression model, whether the results suit for the deep learning models are not discussed.\n3. The layout of the figures in this paper is irregular, as well as the fonts in these figures.", "other_comments_or_suggestions": "This is a paper with limited contributions, the author should provide more interesting findings, such as extending the results on deep learning area or other ensembel models.", "questions_for_authors": "Most of the experiments are based on the random feature RF model. Whether the same results shows in some larger ensemble models?", "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": "yntymkda1E", "reviewer": "Reviewer_6CpK", "summary": "In the context of random feature high-dimensional ridge regression, this paper investigates the problem of training an ensemble of independent models and the trade-off between ensemble size and model size for a fixed total number of features. The authors prove a 'no free lunch' theorem, showing that increasing the ensemble size while keeping the total number of features fixed leads to higher test risk, making a single large model the optimal choice, provided the ridge parameter is fine-tuned. However, in the overparameterized regime, small ensembles can achieve near-optimal performance over a wider range of ridge parameter values, making them more robust than single models. The authors derive scaling laws showing that while optimal error scaling is always achieved by increasing model size with a fixed ensemble size, near-optimal scaling can be achieved under certain conditions on the kernel and task eigenstructure. These findings are validated through numerical simulations on synthetic data and real-world datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!", "claims_and_evidence": "All claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods are well-suited for the problem considered.", "theoretical_claims": "I checked the correctness of the proofs and I have no issues to discuss.", "experimental_designs_or_analyses": "I have no issues to discuss.", "relation_to_broader_scientific_literature": "This paper builds on prior works showing that single large models can outperform ensembles when optimally tuned and extends the theoretical understanding of random feature generalization to the ensemble setting. The authors also contribute to the literature on scaling laws by deriving how test risk scales with ensemble and model size, providing insights into the trade-offs between the two quantities.", "essential_references_not_discussed": "I am not aware of any relevant references that have been omitted.", "other_strengths_and_weaknesses": "This work improves the current understanding of generalization and scaling laws for RFRR, extending previous findings by tackling the problem of ensemble learning, which is closely related to practical issues and applications. The presentation is clear and provides valuable insights that could apply to other settings, such as explaining the apparent violation of the \"no free lunch from ensembles\" principle. Moreover, all claims are supported by extensive numerical simulations. I have not identified any major weaknesses.", "other_comments_or_suggestions": "Typo on line 121, second column: \"et al.\" is repeated twice", "questions_for_authors": "I have no important questions.", "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": "Vyc5oiNrf8", "reviewer": "Reviewer_Ef22", "summary": "## Updates after author discussion\n\nThanks a lot for all the clear discussion. A lot of my issues/confusion with the paper have been addressed in the comments, and I'm convinced that the theory just needs some cleaning up to be fully clear. The paper then tells an interesting -- and, to my knowledge, novel -- story about ensembling. I've increased my score to a 4/5 to vote for an accept. I would just recommend to the authors to do a few careful scrubbing passes over the theoretical sections to make sure notation is being used consistently and all the asymptotics are carefully defined *and* explained (e.g., the fact that $\\lambda \\to 0$ is (1) done for analytical convenience, but (2) has some justification in the literature is helpful discussion that should definitely be in the paper!)\n\nBest,\nReviewer Ef22\n\n\n## Original review before author response\nThis is a theoretical paper studying kernel ridge regression with random features. Specifically, it asks whether ensembles of multiple models are effective when the optimal ridge parameter is used. The authors show that, in fact, when holding the total number of random features constant across all models (representing a fixed compute budget), the test risk is minimized by not ensembling. However, the authors note that ensembles can achieve *nearly* optimal performance in the overparameterized regime. The authors validate their theory in small-scale synthetic and real experiments, which point to some interesting future directions around when the ridge parameter is not optimally chosen.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. Below, we address your questions and concerns:\n\n> \"The one portion ... would be helpful.\"\n\n **Response**: Thank you for this suggestion. We will add more justification. While ensembles are never optimal, they allow parallelization and can be *near-optimal*, hence useful in practice. Section 5.1 addresses near-optimality in the overparameterized regime.  The scaling laws derived in section 6 address near-optimality in the under-parameterized regime -- necessary for a complete characterization.\n\n> 1. **Section D.1** states ... satisfiable?\n\n**Response:** We will clarify that both the $\\eta_t$ and $\\bar{w}_t$ are normalized to satisfy these constraints.\n\n> 2. In **Section D.2**, why ... clarify this.\n\n**Response:** Yes, we choose $\\mathbf{V}^k_{ij}\\sim \\mathcal{N}(0, 2/D)$ to converge to the NNGP kernel in Lee et. al. (2018).  We will clarify this in the text.\n\n>1. **\"consider the *featurization* transformation $g$\"**. I ... supposed to be.\n>2. **$\\mu_\\nu$** was ... for it.\n\n**Response**: We have revised the text:\n\n\"Define the random features $\\mathbf{\\psi}(\\mathbf{x}) \\in \\mathbb{R}^N$ by $\\left[ \\mathbf{\\psi}(\\mathbf{x})\\right]\\_n = g(\\mathbf{v}\\_n, \\mathbf{x})$, where the $\\mathbf{v}\\_n$ are random parameter vectors sampled independently from measure $ \\mu\\_{\\mathbf{v}}$ on $\\mathbb{R}^C$.  Here, the function  $g: \\mathbb{R}^C \\times R^{D} \\mapsto \\mathbb{R}$ is a \"featurization transformation,\" often taking the form $g(\\mathbf{v}\\_n, \\mathbf{x}) = \\varphi (\\mathbf{v\\_n}^\\top \\mathbf{x})$ for some nonlinear activation function $\\varphi(\\cdot)$... \"\n\n>3. **\"As $N \\to \\infty$, this... and $\\mu_\\nu$?\n\n**Response**:  A careful choice of $g$ and $\\mu\\_{\\mathbf{v}}$ is required to ensure convergence to *a particular* kernel (see point 2).  However, the stochastic kernel in general converges to *some* deterministic kernel given by $H(x, x') = \\mathbb{E}\\_{\\mathbf{v} \\sim \\mu\\_{\\mathbf{v}}} g(\\mathbf{v}, \\mathbf{x})g(\\mathbf{v}, \\mathbf{x'})$.  We will clarify.\n\n>6. **Equation (7)** seems to ... with one another.\n\n   **Response**: This is a standard bias-variance decomposition of the error (see, [2]).  An expectation over $\\mathbf{Z}$ is not necessary on the left side of eq. 12 because the test risk **concentrates** over $\\mathbf{Z}$.\n\n>7. In **Section 5.1**, *\"$\\lambda = 1/N = 0$\"*.... $1/N$ and 0.\n\n   **Response**: To clarify, we now say \"we expand the risk estimate $E_g^K$ (eq. 9) as power series in $1/N \\gtrsim 0$ and $\\lambda  \\approx 0$\".\n\n> Comments regarding the use of eq. 9, and the slack in this estimate (\"where $\\mathcal{E}\\_g^1$ is ... to be.\"; \"I think... should be stated.\"; \"In Appendix C ... result.\"; \"Also, the proof rigorous conclusions.\"):\n\n**Response**: Thank you, we agree that more thorough explanation would be helpful. We call the \"true\" risk $\\mathcal{E}\\_g$ the error for a particular realization of the random parameters $\\mathbf{v}\\_n$.  The key result of Defilippis *et al.* (2024) is to show that the *distribution* over $\\mathcal{E}\\_g$ values *concentrates* around a *deterministic‐equivalent* expression $E\\_g$ which depends on the feature count $N$. The difference between the *true* random‐features generalization error $\\mathcal{E}\\_g$ and its deterministic‐equivalent **$E\\_g$** is controlled by a **multiplicative concentration bound**:\n$$ |\\mathcal{E}\\_g - E\\_g| \\le C\\, \\bigl(\\tfrac{1}{\\sqrt{N}} + \\tfrac{1}{\\sqrt{P}}\\bigr)\\,E\\_g\n\\quad\\text{(with high probability)}, $$\nfor constant $C$. We will clarify the notion of \"deterministic\" equivalence between the random quantity $\\mathcal{E}\\_g$ and the deterministic quantity $E\\_g$ at large $P$ and $N$.\n\n>Eq 21 seems ... complete proof.\n\n **Response:** The approximate equalities in Eq's C.15 - C.17 indicate that we are neglecting higher order terms in $\\lambda$ and $1/N$. The result is a rigorous first-order approximation in these variables.  To clarify, we will replace $\\approx$ with $\\asymp$ (equal to leading order) in the derivation.\n\n> Appendix B.1... pointing out.\n\n**Response:** Thanks, we will clarify these steps in the SI. \n For increasing $N$ we could argue as follows: \nDenote by $E_g(N, \\lambda)$ the test with $N$ random features and ridge $\\lambda$.  Consider $N \\to N'$ for $N'>N$.  We show that there exists a ridge parameter $\\lambda'$ such that $E_g(N', \\lambda') \\leq E_g(N, \\lambda)$.  Next, we have that\n$$ \\min_\\lambda (E\\_g(N', \\lambda)) \\leq E\\_g(N', \\lambda') \\leq E\\_g(N, \\lambda)$$\nBecause this is true for any $\\lambda$, we may assign $\\lambda = \\operatorname{argmin}\\_{\\lambda} E\\_g (N, \\lambda)$, completing the proof.\n\nAnalogous steps can be applied when increasing $P$ or for the joint transformation of $N$ and $K$ with $KN=M$. \n\nReferences: \n\n[1] Defilippis et. al https://arxiv. org/abs/2405.15699.\n\n[2] Adlam et. al. https://arxiv.org/abs/2011.03321.", "claims_and_evidence": "I think that the theoretical results, as stated, back up the overall premise of the paper. And the empirical results also effectively illustrate the theoretical results. I do have some issues with the theoretical development, which are listed below.\n\nThe one portion of the paper that I didn't see as offering much evidence was Section 6. This felt a little tacked on, and I wasn't sure how it related to the main story of the paper, which is (to my reading) about ensembling not being effective. I think some more discussion of what the motivation / takeaways of this section are would be helpful.", "methods_and_evaluation_criteria": "Yes, the paper is mostly theoretical, so there isn't too much choice of methodology here.\n\nThe only comments I had were from reading Appendix D (details on experimental setups):\n1. Section D.1 states that that the $\\eta_t$ are normalized so that $\\sum_t \\eta_t = 1$ and $\\sum_t \\bar w_t^2 \\eta_t = 1$. Why is it that these are both simultaneously satisfiable?\n2. In Section D.2, why is the variance of $V_{ij}^k$ chosen to be $2/D$? Is this a result from Lee et al. (2018)? If so, some quick rewording might clarify this.", "theoretical_claims": "There were a few times where I thought the theoretical development was hard to follow because it seemed to be lacking definition, was not fully rigorous, or seemed to have skipped a few steps in proofs. I've bulleted out these issues below:\n\n**Lacking definition**\n1. \"consider the \"featurization\" transformation $g$\" -- I think this could really use a precise example to clarify what $g$ is supposed to be.\n2. $\\mu_v$ was used around the second column of line 62, but I didn't see a definition for it.\n3. ``As $N \\to \\infty$, this stochastic kernel converges to the deterministic kernel $H(x,x')$''. Does this not require a careful choice of $g$ and $\\mu_v$.\n4. ``$f(x)$ and the true target function $f(x)$'' -- I think this is just a typo\n5. \"where $\\mathcal{E}_g^1$ is the \"true'' risk\" -- How is the definition of $E^1_g$ in equation 9 not the `\"true\" risk? I didn't really understand what $\\mathcal{E}$ is supposed to be.\n6. Eq 7 seems to define $E_g$ for a fixed $f$. But then Eqs 12-14 decompose $E_g$ using expectations over $Z$ (i.e., over the random features making up $f$). These seem inconsistent with one another.\n7. In section 5.1, \"$\\lambda = 1/N = 0$\". It doesn't seem possible that $\\lambda$ could be both $1/N$ and 0.\n\n**Missing Rigor**\n\n1. I think it's fine to not show the derivation of Eq 9. But it's written as an approximate equality without ever saying what the slack in this approximation is. I think this should be stated.\n2. Eq 21 seems like a major point of the paper, given that it's the main result showing near optimality of ensembling in the overparameterized regime. But, it's proof in Appendix C.2 doesn't seem fully rigorous. First, in the proof $1/N$ and $\\lambda$ are stated to be \"[assumed] to be on the same order of magnitude\" without stating what this means. Second, the proof uses a number of approximate equalities (Eqs C.15-C.17) without specifying what the approximation is or how it affects the proof. Overall, I think this result should be wrapped into a lemma / theorem environment with carefully stated assumptions and a complete proof.\n3. In Appendix C (derivation of the scaling laws), there were a lot of approximations used. It's not clear how these affect the proof.\n\nOverall, my major issue with rigor is that I don't think it's appropriate to use approximate equalities in a formal proof without precisely defining what terms $\\approx$ sign is hiding and verifying that dropping those terms doesn't affect the result.\n\n**Missing Steps in Proofs**\n\nAppendix B.1 contains the proof of Theorem 4.1, which says that when minimizing the test risk over the ridge parameter $\\lambda$, the test risk decreases monotonically with the number of features, number of ensemble elements, and number of training datapoints. It's overall not clear to me how this proof accounts for the fact that we are minimizing over $\\lambda$. There's a reference to Eq 11 and the fact that its fixed point can be held constant by scaling up $\\lambda$. But we're optimizing over $\\lambda$. So I'm not totally sure what this is pointing out.\n\nAlso, the proof of monotonicity in $N$ (the number of model features) uses Eq. 9 to derive its result. But Eq 9 is an approximate equality, so I don't think that analyzing it can lead us to rigorous conclusions.", "experimental_designs_or_analyses": "Yes, the paper is mostly theoretical, so there isn't too much choice of experimental design here.", "relation_to_broader_scientific_literature": "Ensembling is an important idea in the machine learning literature; e.g. random forests are hugely successful in practice, and ensembles of deep models have been proposed recently for various purposes such as uncertainty estimation. As far as I know, most work on ensembling does not study the very important tradeoff in terms of number of parameters (representing compute) and statistical accuracy. I think this paper is an interesting step towards understanding that tradeoff.", "essential_references_not_discussed": "Nothing as far as I know!", "other_strengths_and_weaknesses": "I've listed everything in the sections above.", "other_comments_or_suggestions": "I would just point out that, while there's not a statistical gain in ensembling here (in fact it seems there may be a statistical loss!) there is a computational gain, as the compute required for $M$ features is $O(M^3)$ versus $M$ features spread over $K$ ensembles requires $O(M^3 / K^2)$. I think this would be good to bring up around the discussion of Theorem 5.1.", "questions_for_authors": "My main questions that influenced my review are:\n\n1. Are all the approximate equalitites really justified in the proofs / theoretical statements?\n2. Can the proof of theorem 5.1 be expanded on or my understanding of it corrected?\n3. What is the purpose of Section 6?", "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": "oPhdS7z8J1", "reviewer": "Reviewer_5sWk", "summary": "The paper investigates the random-feature ridge regression between using a single large model versus multiple smaller models (ensembles). The authors demonstrate that ensembles can achieve near-optimal performance when the total feature count remains high in the overparameterized regime, while in the underparameterized regime, error scaling laws depend on the relationship between ensemble size and model size.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.  We respond to your questions concerns as follows:\n\n> In Section D.1, D.2, the authors should clearly point out where are the experimental results.\n\n**Response:** Thank you for your suggestion.  We will update the text to point this out.  \n\nSection D.1 on synthetic tasks pertains to the numerical error points in Figures 3 and S2.A-C.\n\nSection D.2 on the numerical experiments for  binarized MNIST and CIFAR-10 with ReLU features pertains to figures 1, 2, 4, S1, S2.D-F, S3, S4, S5, S6, and S7.\n\n\n> The authors missed two important references ([1], [2])...compare the results.\n\nThank you for bringing these works to our attention.  We were aware of ref [1] and many other papers deriving the error... These papers focus on the over-fitting and double descent / multiple descent pheonomena in their analysis.  However, these effects vanish entirely when the ridge parameter is optimized at each sample size.  By studyiing the behavior of the test risk at optimal ridge, we obtain more practical results that will apply even in settings where the ridge parameter is set to its optimal value using cross-validation.\n\n> I have some concerns on the essential contribution ... these two references.\n> Can the authors rely on the results ...$ \\arg\\min_x f_2(x).\n$\n\nThank you for bringing these papers to our attention.  In short, no, we cannot rely on either of them to derive the test risk of ensembled RFRR.  \n\nAs for ref. [1], the data model considered here consists of samples drawn uniformly from the unit sphere, whereas the results we use apply to arbitrary (but nicely behaved) data distributions $\\mathbf{x} \\sim \\mu_{\\mathbf{x}}$.\n\nAs for ref. [2], the loss function considered there encodes \\textit{joint} training of the parameters $\\mathbf{a}\\_1 \\equiv [a\\_1, \\dots, a\\_{N\\_1}]^\\top $ and $\\mathbf{a}\\_2 \\equiv [a\\_{N\\_1 + 1}, \\dots, a\\_{N\\_2}]^\\top$.  This can be written as\n\n$$ \\frac{1}{n} \\sum_{i=1}^n \\left( y - f_1(\\mathbf{a}\\_1) \\right)^2 + \\frac{d}{n} \\lambda ||\\mathbf{a}\\_1||^2  + \\frac{1}{n} \\sum_{i=1}^n \\left( y - f_1( \\mathbf{a}\\_1) \\right)^2 + \\frac{d}{n} \\lambda  ||\\mathbf{a}\\_2||^2 $$\n\nThe square term here cannot be factored into a sum of contributions depending separately on $\\mathbf{a}\\_1$ and $\\mathbf{a}\\_2$, as you have assumed in your comment.  \n\nIn the notation of [2], the model we consider corresponds to a decoupled loss function which optimizes $\\mathbb{a}\\_1$ and $\\mathbf{a}\\_2$ separately:\n\n$$\\frac{1}{n} \\sum_{i=1}^n\\left( y - f_1(\\mathbf{a}\\_1) \\right)^2 + \\frac{d}{n} \\lambda ||\\mathbf{a}\\_1||^2+ \\frac{1}{n} \\sum\\_{i=1}^n\\left( y - f_1(\\mathbf{a}\\_1) \\right)^2 + \\frac{d}{n} \\lambda  ||\\mathbf{a}\\_2||^2 \\,,$$\n\nwith additional terms if $K>2$.\n\n\n> Additional response to reviewer comments:\n\nMany of your questions and concerns revolve around the derivation of the risk estimate for random feature ensembles, and its presence in prior literature.  There are many papers which derive the bias and variance terms for random-features regression using a variety of methods, which we have referenced (Atanasov e tal.,2024; Canatar et al. ,2021; Simon et al., 2023; Adlam & Pennington, 2020; Rocks & Mehta, 2021; Hastie etal., 2022; Zavatone-Vethetal., 2022) and we are happy to add discussions of [1] and [2].\n\nWe do not claim to have contributed the error formula for ensembles -- our contribution is a novel and informative analysis of test risk formula.\n\nThe error formulas for RFRR ensembles derived in previous works are not easily interpretable, and studying the implications of these error formulas is an important task unto itself.  We believe that our paper has addressed an important gap in our understanding of ensembled random feature models. We have used the (known) bias-variance decomposition of the test risk of RFRR to study the tradeoff between model size and ensemble size.  Specifically, we have shown that:\n- Ensembling is *never* optimal under a fixed parameter budget at optimal ridge.\n- Ensembling can achieve near-optimal performance in both the overparameterized and underparameterized regimes, with precise spectral conditions for near-optimal scaling in the underparameterized regime.\nIf accepted, we will clarify these contributions in the abstract and introduction.  We may also change the title of the paper to \"No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions\" to highlight all of our main contributions.\n\n\n[1] Mei S, Montanari A. The generalization error of random features regression: Precise asymptotics and the double descent curve J. Communications on Pure and Applied Mathematics, 2022, 75(4): 667-766.\n\n[2] Meng, X., Yao, J., & Cao, Y. (2024). Multiple descent in the multiple random feature model. Journal of Machine Learning Research, 25(44), 1-49.", "claims_and_evidence": "The claims are supported by clear evidence.", "methods_and_evaluation_criteria": "I appreciate the real data experiments via CIFAR10 and MNIST. The authors  performed fully numerical experiments first to support their theory first. Then they also conducted real data experiments.", "theoretical_claims": "I did not check how equation (9) comes. To my understanding, all the comparison below comes from equation (9), the authors should give clearer demonstration on Section 3.1, at least give clear resources where these equations come from.", "experimental_designs_or_analyses": "In Section D.1, D.2, the authors should clearly point out where are the experimental results.", "relation_to_broader_scientific_literature": "The authors missed two important references, which already rigorously gave the risks of single random feature model and ensembled random feature models. The authors should discuss these references adequately, and compare the results. \n\n[1] Mei S, Montanari A. The generalization error of random features regression: Precise asymptotics and the double descent curve[J]. Communications on Pure and Applied Mathematics, 2022, 75(4): 667-766.\n\n[2] Meng, X., Yao, J., & Cao, Y. (2024). Multiple descent in the multiple random feature model. Journal of Machine Learning Research, 25(44), 1-49.", "essential_references_not_discussed": "I have some concerns on the essential contribution of this paper. The rigorous excess risk curve has already been investigated by previous papers.  [1] gave the rigorous theoretical values of risks of random feature model,  and [2] extended the single random feature model to ensembled random feature model. With $y=f_0(x)+\\epsilon$, people can also easily get rigorous theoretical values of risks of ensembled random feature model based on the analysis of [1] and [2]. The authors should discuss more on these two references. \n\n\n[1] Mei S, Montanari A. The generalization error of random features regression: Precise asymptotics and the double descent curve[J]. Communications on Pure and Applied Mathematics, 2022, 75(4): 667-766.\n\n[2] Meng, X., Yao, J., & Cao, Y. (2024). Multiple descent in the multiple random feature model. Journal of Machine Learning Research, 25(44), 1-49.", "other_strengths_and_weaknesses": "The paper is generally well written. However, there are two main concerns.\n\n[1] Literature related issues given above. Please also see my questions below.\n[2] Clearer resources in Section 3.1.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "Can the authors rely on the results presented in [1] and [2]? In my understanding, the solution for random feature models in [2] directly corresponds to the solution of ensembled random feature models. This follows from the fact that for different vectors  $x_1, x_2$,\n\n\n$\\min_{x_1, x_2} \\left( f(x_1) + g(x_2) \\right) = \\min_{x_1} f(x_1) + \\min_{x_2} g(x_2)$,\n\n\nwhich implies that\n\n\n$x_1^* = \\arg\\min f(x_1), \\quad x_2^* = \\arg\\min g(x_2)$.", "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:

Meta-review: This work provides an asymptotic comparison of random feature ensembles versus a single large random feature regressor under a fixed feature budget. While the authors demonstrate that no ensemble will outperform a single regressor with an optimally tuned ridge parameter, they demonstrate conditions under which an ensemble is near optimal. This work is theoretically sounds and builds upon many recent derivations of the asymptotic risk of random feature regression. While some portions of the theoretical argument were not rigorously presented in the original submission, the authors have addressed these concerns during the discussion period. I urge the authors to incorporate these suggestions for clarity and rigour in the camera ready. Overall, this work tackles a relevant problem and adds to the knowledge of scaling laws, and therefore I recommend acceptance.
Decision: Accept (poster)