No Free Lunch from Random Feature Ensembles

Authors: Benjamin Samuel Ruben, William Lingxiao Tong, Hamza Tahir Chaudhry, Cengiz Pehlevan
Primary area: learning theory
Keywords: Ensemble Learning, Deep Ensembles, Kernel Random Features Regression, Representation Learning

Abstract:
Given a budget on total model size, one must decide whether to train a single, large neural network or to combine the predictions of many smaller networks.  We study this trade-off for ensembles of random-feature ridge regression models. We prove that when a fixed number of trainable parameters are partitioned among $K$ independently trained models, $K=1$ achieves optimal performance, provided the ridge parameter is optimally tuned. We then derive scaling laws which describe how the test risk of an ensemble of regression models decays with its total size.  We identify conditions on the kernel and task eigenstructure under which ensembles can achieve near-optimal scaling laws.  Training ensembles of deep convolutional neural networks on CIFAR-10 and a transformer architecture on C4, we find that a single large network outperforms any ensemble of networks with the same total number of parameters, provided the weight decay and feature-learning strength are tuned to their optimal values.

Decision: reject
Reviewer scores: 8, 8, 6, 3, 3

Reviews and discussion:
<thread>
creation date:
1730244588326

thread_type:
official_review

<thread_object>
creator: reviewer_6nye

<content>
summary:
This paper analyzes the ensemble of K ridge regressions on random features size M/K and one right regression on random features size M. And concludes that the later one is always the optimal under the optimal L2 regularization. This work also use some toy experiments (e.g. two to three layers CNN) to compare the ensemble of K small models and one large models.

strengths:
- The writing is clear. The paper is easy to read.

weaknesses:
- In this paper, Text, Theory and Experiments are not consistent. 
In text, this paper assumes a fixed "computational budget" (line 256), which is resonable, then links this assumption to "a fixed total number of features"  (line 257).  However, a fixed computational budget is not necessary leads to a fixed total number of features. 

The theory discusses the ensemble case of regression on random features. Concludes that one right regression on random features size M is always the optimal under the **optimal L2 regularization**, compared with the ensemble of K ridge regressions on random features size M/K. However, that is trivial. Section 9.1 in [1] shows a dropout on regression equals to an ensemble of expensional number of small regressiors, equals to L2 regularization. Since **an ensemble of expensional number of small regressiors** is not worse that **M/K regressors** (same as the Eq 16 in this work), an "optimal L2 regularization" is of course not worse than "M/K regressors"

The cifar experiments in this work does not link to the theory, i.e. without neither regression nor random features. 



[1] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., & Salakhutdinov, R. (2014). Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1), 1929-1958.





typos:
line 141  f(x)

questions:
- The CNN experiment on CIFAR10 contains two CNN layers and one linear layer. That is already too small for CIFAR10 tasks. Reducing the size of this small network would further hurt the performance. Does the same phenomena in this paper hold on larger networks?  [2] shows the ensemble multiple small networks outperforms a large network. 


[2] Zhang, J., & Bottou, L. (2023, July). Learning useful representations for shifting tasks and distributions. In International Conference on Machine Learning (pp. 40830-40850). PMLR.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730725701137

thread_type:
official_review

<thread_object>
creator: reviewer_sshy

<content>
summary:
This paper investigates the trade-off between employing a single large model versus an ensemble of smaller models, focusing on random feature kernel ridge regression (RF-KRR). In particular, this work studies ensembles of size $K$ with $N$ random features per ensemble member with a fixed total parameter count $M=N\cdot K$. In this setting, the paper proves rigorously and shows empirically that optimal performance is achieved by $K=1$ for an optimally tuned ridge parameter while increasing $K$ degrades the optimal test risk. Additionally, this result – referred to as “_no free lunch from random feature ensembles_” – is shown for CNNs and transformers in experiments on image classification (CIFAR10) and language modelling (C4) in the regimes of lazy training and feature learning. Furthermore, scaling laws are derived, and conditions for achieving near-optimal scaling laws for these ensembles are identified.

strengths:
The main contribution of the paper is to add the ensemble perspective to established results on random feature kernel ridge regressions. It contributes theoretical insights and proofs for two theorems on “_more is better for RF Ensembles_” and “_No Free Lunch From Random Feature Ensembles_” (pages 4-5)  as well as scaling laws and empirical validation of adequate quality. Generally, the paper has a clear thread, with some minor adjustments required to the presentation (listed below in “weaknesses”).

weaknesses:
Even though extending the analysis of RF-KRR to ensembles is new, the presented results align with the expectations from prior work on single models. In my opinion, this limits the novelty and significance of the contribution, which I elaborate on in more detail below. 

__W1.__ _Novelty of Theorem 1 “More is better for RF Ensembles” and results in section 3_: For “non-ensemble” RF-KRR, the referenced papers by [Simon _et al_. (2023)](https://openreview.net/pdf?id=OdpIjS0vkO) and [Bordelon _et al_. (2024a)](https://arxiv.org/pdf/2402.01092) have established that decreasing the number of random features $N$ leads to a degraded optimal test risk. Could the authors elaborate on why examining ensembles adds new perspectives beyond what is already known for single models? I think a strong justification would be necessary. In particular, I view the statement of Theorem 1 and the results presented in Figure 1 of this submission as a natural consequence of (and essentially the same as) [Theorem 1 “More is better for RF regression” and Figure 1 in in Simon _et al_. (2023)](https://openreview.net/pdf?id=OdpIjS0vkO#page=6); see also point W2.1.

__W2.__ _Significance of Theorem 2 “No Free Lunch From Random Feature Ensembles” and results in section 4_: \
__W2.1.__ A main premise of the work is to have a fixed total parameter count $M$ and compare ensembles of $K$ members and $N$ random features such that $M=N\cdot K$ always holds. This is presented as a “pragmatic” approach to limit computational overhead associated with ensemble methods (lines 34-37). However, this leads to increasingly “weaker learners” when the ensemble size $K$ is increased. For this reason, it is less surprising and in line with the conclusions of [Simon _et al_. (2023)](https://openreview.net/pdf?id=OdpIjS0vkO) and [Bordelon _et al_. (2024a)](https://arxiv.org/pdf/2402.01092) that decreasing the number of random features $N$ (by increasing ensemble size $K$) leads to a degraded optimal test risk (at fixed total parameter count $M$). From this perspective, it is expected that $K=1$ leads to the optimal result. This limits the novelty and significance of theorem 2 on “No Free Lunch From Random Feature Ensembles” where specifically the number of random features are chosen as $N’=M/K’$ and $N=M/K$ with $K’<K$ leading to $N’>N$.  As this is a central result of the paper, it could strengthen the contribution to elaborate more on why ensembles provide new insights beyond what can be directly inferred from the existing work on single models. In my opinion, a more substantial justification would be required. \
__W2.2.__ In addition to the previous point, I believe that the interplay between the number of random features $N$, the size of the ensemble $K$ and the total parameter count $M$ make it difficult to compare the information provided in Figures 1 and 2. For instance, in Figure 2A the relationship between test error and ensemble size $K$ for different sample sizes $P$ at fixed total parameter count $M$ is considered, but with increasing $K$ the number of random features $N$ decreases. It appears that a more careful discussion would be required, which is intimately connected to the premise above.

Minor remarks:
- “RF KRR” and “RF-KRR” are both used in the manuscript and the authors might want to make the usage consistent.
- Line 101: Missing full stop “.” at the end of the sentence.
- Line 106: The computation of $g(v_n,x)$ is mentioned, but $g$ is not defined in the main text. From Appendix A, line 690, it seems that it is another notation for $\psi^k (x)$, but its use in the main text is not clear to me.
- Line 118-119: Missing citation.
- Line 142: Wrong formatting of “f_{*} (x)”.
- Line 176-177: Double parenthesis in citation.
- Line 187: I would not recommend writing “eq’s”.
- Line 248-249 and Figure 1: The “filled” lines are quite likely supposed to be dashed lines.

In summary, I view the points raised in W1 and W2 as the main challenges in the current version of the submission and believe a major revision of the paper is required. However, I invite the authors to address my objections and clarify potential misunderstandings.

questions:
My questions revolve around the core assumptions of the paper as outlined in W1 and W2 above. In particular, considering classical literature on RF-KRR like [Rahimi and Recht, “Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in learning” (2008)](https://people.eecs.berkeley.edu/~brecht/papers/08.rah.rec.nips.pdf) and the referenced works of [Simon _et al_. (2023)](https://openreview.net/pdf?id=OdpIjS0vkO) and [Bordelon _et al_. (2024a)](https://arxiv.org/pdf/2402.01092), my questions are as follows:

Q1. Is there any evidence that an ensemble of random features could provide a different result than is stated in [Theorem 1 of Simon _et al_. (2023)](https://openreview.net/pdf?id=OdpIjS0vkO#page=6) for RF regression?

Q2. In connection to Theorem 2 in the submission and in the context of RF-KRR, is there any reason to assume that a larger ensemble of weak learners can outperform a small ensemble of stronger learners?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730944634077

thread_type:
official_review

<thread_object>
creator: reviewer_u2xd

<content>
summary:
- This paper studies the tradeoff between ensemble size and total feature/parameter count for random feature ensembles
- In particular, they derive the following theorems (paraphrased informally):
- Theorem 1 - larger ensembles -> better performance (this contribution is minor)
- Theorem 2 - Given a fixed feature count, it is better to have a single large model than multiple smaller ones (this is the main contribution of the paper)
- Both theorems are verified experimentally binarized Cifar-10 datasets
- The paper then uses Thm 2 to derive scaling laws, assuming a standard model of the decay of kernel's eigenspectrum. They identify differing behaviour for "simple" and "difficult" datasets, and verify this experimentally
- Finally, the paper studies the performance of non-fixed feature classifiers using ensembles of CNNs trained on CIFAR-10. They control the feature learning by controlling the richness parameter

strengths:
- Presentation is clear and easy to follow
- Claims are verified experimentally and there is good agreement with the author's claims
- Section 5 (the section on scaling laws) I find particularly interesting as it shows how the fairly uninspiring theorems in the first two sections can be used to derive more non-trivial behaviours, such as the distinction between "easy" and "difficult" dataset scaling laws
- The use of the richness parameter to control the adherence to the assumptions in the theorems in section 6 in quite interesting, but I am unsure how applicable this work is necessarily to modern models (see weaknesses)

weaknesses:
- I think the authors should be very clear that the theorems do not directly "explain" the empirical results in section 6, except in the case of very small richness parameters, as their theorems do not cover feature learning. I think it would also be useful for the authors to discuss this limitation in the weaknesses section in concluding discussion

questions:
- Is it possible to plot the validation loss in figure 5b as opposed to the test loss?
- Could the authors discuss how for certain values for $\gamma$ in figure 5a, it seems the increasing the ensemble count improves performance, namely for larger values of $\gamma$? Is it possible that behaviour for models outside of the lazy regime do not follows the same "no free lunch" theorem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731400785833

thread_type:
official_review

<thread_object>
creator: reviewer_knrl

<content>
summary:
The present study aims to investigate the utility of training multilple shallower networks vs that of a larger network.  Theory shows that only 1 large network is appropriate and experiments validate this approach.

strengths:
The paper gives extensive theory and experimental proof that the theory works. 

Wide variety of experiments. 

Scaling laws are given for this class of models, which is always useful.

weaknesses:
I'd like to see experiments be ran on imagenet validating these results there. 

No results on conventional nerual network architectures.

questions:
Would it be possible to train random feature ResNet18s or VGGs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731427192151

thread_type:
official_review

<thread_object>
creator: reviewer_mdqv

<content>
summary:
The paper covers several theoretical and empirical analyses related to whether a parameter budget should be allocated to a single large classifier or an ensemble of smaller classifiers. 
The authors first analyse ridge regression using random-features where the ensemble prediction is the mean response of the member predictors, and the test risk is the mean squared error.  They prove that the expected test risk decreases when any of: data size, ensemble feature size, or ensemble size increases when the ridge parameter is chosen optimally for the given setting (with mild assumptions on the task eigenstructure) and show empirically the monotonicity in test error for a binarized CIFAR10 task using RELU random features. The authors then prove a “no free lunch” theorem for random feature ensembles showing that, for a fixed total parameter count, lower test risk is achieved with fewer ensemble members (with mild assumptions on the task eigen structure) and empirically show the monotonicity of test error with ensemble size fitting RELU random feature models to the binarized CIFAR10 task. 
Next the authors derive scaling laws for random feature ensembles in the width-bottlenecked regime (the number of features per ensemble member is much smaller than the data size). They show on synthetic data that for r (a parameter controlling the relative rate of decay of power in modes relative to the rate of eigenspectrum decay) greater than 0.5 (an “easy task”) then there is a growth exponent l* above which scaling laws are near optimal. Therefore ensembles with K>1 can be near optimal as long as the number of parameters per ensemble member grows quickly enough. 
Finally, the authors initialize CNNs in the maximal update parameterization and, using CIFAR10, empirically show for a fixed parameter budget, and task richness, that test accuracy typically decreases monotonically with increased ensemble size. They also show empirically that training loss increases monotonically with increased ensemble size when fitting transformers to C4 data.

strengths:
I think the paper is in general clear and well-written, the research question is useful and the paper is of interest to ICLR.
I have not checked the proofs, but the results looked sensible and were broadly consistent with the empirical results.

weaknesses:
In figure 5a, one of the highest performing richness parameters (although not the admittedly highest) does not show monotonic decrease with ensemble size. Given this does not fit with your other analysis, it would be useful to comment on it in the paper.



minor points:

Both CIFAR10/MNIST and a CIFAR10/MNIST-derived binary classification task are included in the paper. What is the papers convention for differentiating between the binarized version and the original version? In places the paper appears to call the binary classification task “a CIFAR classification task” or “Binarized CIFAR10” but in others it then refers to this binary task just as CIFAR (I think this happens for example in line 370). Could the binary tasks have a name (for which CIFAR10 is a prefix perhaps) and then be referred to by that name to improve readability?

The same notation of learning rate and task eigen structure, and for richness and the data-size-scaled degree of freedom parameters. Giving separate notation would be preferable.

118 – “(citations)” should instead be the actual citation

228 – Figure 1: Are the non-red lines supposed to be dashed in this plot? otherwise does the legend contain a dashed line? Since none appear in the actual plot.

340 – Figure 3 – could you draw the line for l* (= 1/(1+ alpha*(2*r – 1))) in red on the plots for figure 3 A?

397 – “a” is singular, but “tasks” is plural, should remove “a”?

452 – “that at the” -> “that the”

questions:
In Figure 2c, ensembles (K>1) appear to be relatively robust to ridge parameter, where as K=1 is highly sensitive to it. Could this correspond to it potentially being more practically expedient to train small ensembles when optimally tuning the regularising parameter is expensive?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732161591725

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updates to Rebuttal Version

comment:
We thank all the reviewers for their time and valuable feedback.  Since our initial submission, we have made a number of updates to our manuscript which we will summarize here.  We will also respond individually to each reviewer's comments.

- We have updated our discussion of the RFRR risk formula to include a reference to [1], which provides a rigorous backing for the risk estimate we use.  We have also updated our terminology to refer to "Random Feature Ridge Regression (RFRR)" uniformly throughout the paper.
- We have added supplemental figures S3 and S6 confirming that the monotonic decreases in error described in theorems 1 and 2 for the MSE loss also hold for the binarized MNIST and CIFAR10 RFRR classification tasks at the level of the 0-1 test loss under majority vote and score-averaging.
- We have updated the methods we use to determine the "source" and "capacity" exponents for the binarized MNIST and CIFAR10 NNGP kernel regression tasks to the more robust methods described in [2], leading to a better fit between theory and experiment in fig. 4B.
- We have updated section 3.3 to elaborate on potentially complicating effects of ensembling which make Theorem 1 an interesting result, distinct from the $K=1$ case proven in [2].
- We have added a corrolary to section 4 which combines theorems 1 and 2 to guarantee that an ensemble of $K$ RFRR models with $N$ features each can only outperform a single RFRR model with $M$ features at optimal ridge if $NK>M$.  We confirm this for tasks with power-law structure and the binarized CIFAR10 RFRR task in a new supplemental figure S2.  This bound is tight in the overparameterized regime where $N \gg P$.
- We have updated the text of section 6 ("No Free Lunch from Feature-Learning Ensembles") to emphasize the importance of using $\mu P$ parameterization, to clarify the relationship between our theory and deep ensembles, and to simplify the discussion of our results.  In particular, we propose three conditions under which the "no free lunch from ensembles" principle holds in networks trained with $\mu P$ parameterization:
  - In the lazy training regime ($\gamma \to 0$) when the weight decay is tuned to its optimal value.
  - When weight decay and richness $\gamma$ are jointly tuned to their optimal values.
  - When richness $\gamma$ is fixed and training is performed *online* (i.e. without repeating data).
- We have updated Figure 5.A to sweep over a larger range of richness values $\gamma$, confirming that accuracy is monotonically decreasing with $K$ when weight decay and richness are jointly tuned to their optimal values.
- We have added experiments analogous to figure 5.A for CIFAR-10 classification but using the ResNet18 architecture.  We find that for this larger architecture, the "no free lunch from ensembles" principle still holds.


[1] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free deterministic equivalents and scaling laws for random feature regression, 2024. URL https://arxiv. org/abs/2405.15699.

[2] James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better in modern machine learning: when infinite overparameterization is optimal and overfitting is obligatory. CoRR, abs/2311.14646, 2023. doi: 10.48550/ARXIV.2311.14646. URL https://doi.org/ 10.48550/arXiv.2311.14646.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The submission investigates whether ensembles can outperform single models when constrained to have the same total parameter count. This is undertaken from a theoretical point of view in the context of random feature ridge regression, and in the empirical context via neural networks. The results in both setting suggest that, when regularisation hyperparameters are optimal, the ensemble cannot outperform the single model. The reviewers generally agreed that the paper is easy to understand, even though the subject matter is quite complex. There were no concerns about the correctness of the theoretical contributions or the experimental setup. The main downsides that impacted my decision are the lack of theoretical novelty over several existing works, as pointed out by reviewer SSHY, and the mismatch between the experiments and theoretical analysis, as pointed out reviewer 6nYe.