No Free Lunch from Random Feature Ensembles

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

Response: Thank you for this comment, which prompts a clarification. First, we note that because RFRR is still a commonly used algorithm, our theoretical contributions to understanding RFRR may be of independent interest. Our theory of RFRR ensembles does link directly to the Binarized CIFAR10 and MNIST RFRR experiments, which are overlaid with theoretical loss curves in figures 1, 2, and 4.

We do not claim that our theoretical results directly explain our empirical findings in deep neural networks (fig. 5). Rather, we view the RFRR model as a toy model from which we might gain intuition that guides our numerical experiments. This perspective has guided many papers (for one example, see [5]). In this case, we find that RFRR ensembles obey the "no free lunch from ensembles" principle when the hyperparameter $\lambda$ is tuned to its optimal value. In section 6, we find that deep ensembles trained with $\mu P$ parameterization also obey the ``no free lunch from ensembles'' principle, when network hyperparameters are tuned to their optimal values. The difference is that the hyperparameters which must be tuned in deep networks are both weight decay and richness $\gamma$. Please see our updated section 6, which makes the relationship between theory and deep feature-learning ensembles clearer than in our original submission. We agree that a theory of feature-learning ensembles is an important objective for future work, and have added a note on this to our discussion section.

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.

Response: Thank you for this comment and for bringing the results of [2] to our attention. We are currently working on repeating the experiment in fig. 4A using a larger ResNet architecture that performs better on the CIFAR10 classification task. We will hopefully be able to share these before the end of the discussion period. As for the results of [2], they do not appear to be inconsistent with our claims. This is because [2] does not use the $\mu P$ parameterization. Many of their results might be explained by the fact that in standard parameterization, a single wider network will be closer to the lazy learning regime than an ensemble of smaller networks. It is possible (and we suspect) that some of the benefits of ensembling that they report would be reversed if they used $\mu P$ parameterization and optimized network performance over the richness parameter $\gamma$ as well as weight decay in each experiment. We have updated section 6 to elaborate on the importance of disentangling network size and learning dynamics to make a proper comparison between networks of varying width.

[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.

[5] Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.01897, 2020.

Thank you for your review. We will respond in two parts due to character limits.

In this paper, Text, Theory and Experiments ... number of features.

Response: Thank you for this comment, which we agree with. We have now clarified in the main text that we consider constraints on total parameter count. The performance of a single large model and ensembles of smaller models are usually compared with reference to the total parameter count, including in [2]. Total parameter count determines the memory required to store a learned model, which is a significant constraint in practice.

The theory discusses ... not worse than "M/K regressors"

Response: We thank the reviewer for calling this result to our attention. However, we believe our result is stronger.

Before giving our reasons for why our result is stronger, we are also aware of results showing equivalence between a single ridge-regularized regressor with access to the full inputs and an infinite ensemble of unregularized, subsampling or "sketched" regressors [3, 4]. An analogous (and true!) statement in the setting we describe would read that an infinite ensemble of random-feature ridge regresssion models with zero ridge is equivalent to the limiting (i.e. infinite-feature) kernel ridge regression model. It would follow that even infinitely large ensembles of random feature models could never outperform the limiting kernel regression model with optimal ridge. This corresponds to the limit $M, K \to \infty$ in Theorem 2.

However, the result we present is stronger because it applies at finite $M$. Rather than comparing a single regressor with access to the full (infinite) set of kernel features to an ensemble of subsampling regressors, we compare a regressor with access to a single large random projection of the kernel features to an ensemble of regressors with access to smaller random projections of the kernel features. Because of this distinction, we find that ensembles with $K > M/N$ can actually outperform a single regressor of size $M$. To demonstrate this, we plot error as a function of $K$ ensembles of RFRR models with $N$ features each in a new supplemental fig. S2. We see that an ensemble of RFRR models with $N$ features each can outperform a single RFRR model of size $M>N$ only if $K>K^*$. Theorems 1 and 2 together guarantee that the value $K^*$ required to achieve better performanced with the ensemble is at least as large as $M/N$. Similarly, if we fix $K$ and allow $N$ to grow, the value $N^*$ above which the ensemble outperforms the single large model of size $N$ as at least $M/K$. This bound on appears to be tight in the overparameterized regime where $P \ll N$ (fig. S2.C, F). We state this result explicitly as the new "Corrolary 1" in the updated version of the manuscript.

One might hope to apply the result from section 9.1 of [1] or from [4] to prove our Theorem 2 by formally regarding the projection of $M$ random features as the full data, with correspondingly shifted ground-truth weights $\tilde{\bar{\mathbf{w}}} = \text{argmin}\_\{\mathbf{w}\} \left[ \mathbb{E}\_\{\mathbf{x} \sim \mu\_\{\mathbf{x}\}\} (f_*(\mathbf{x}) - \mathbf{w}^\top \mathbf{Z} \mathbf{\theta}(\mathbf{x}))^2 \right]$ and shifted label noise $\tilde{\sigma}\_\epsilon^2 = \sigma\_\epsilon^2 + \mathbb{E}\_\{\mathbf{x} \sim \mu\_\{\mathbf{x}\}\} \left[ \left( f\_\ast(\mathbf{x}) - \tilde{\bar{\mathbf{w}}}^\top \mathbf{Z} \mathbf{\theta}(\mathbf{x}) \right)^2 \right]$ With $NK = M$, the ensemble of $K$ RFRR models of size $N$ could formally be regarded regarded as sampling mutually exclusive subsets of $N$ features from the pool of $M$. However, this requires the regressors to sample non-overlapping subsets of the features, which is not accomodated by the random bernoulli masks in [9, 3] or the uncorrelated sketching matrices in [4]. For these reasons, we believe that our Theorem 2 is not a trivial result.

[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.

[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.

[3] Daniel LeJeune, Hamid Javadi, Richard Baraniuk Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3525-3535, 2020.

[4] Patil, Pratik, and Daniel LeJeune. "Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning." arXiv preprint arXiv:2310.04357 (2024). Available at: https://arxiv.org/abs/2310.04357.

Thank for authors responses. After reading the responses and other reviews comments, I find some key concerns are not well addressed. In summary:

1. The theorical result is trival (close to the first two weakness pointed by reviewer sshy). The main theorical result in this work is still "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.". This is trival because there is a L2 regularization to trade-off the model complexity.

2. Text, Theory and Experiments are not consistent, as author replied "We do not claim that our theoretical results directly explain our empirical findings in deep neural networks (fig. 5)."

3. The CNN experiment on Cifar is problematic, because the network of each ensemble member is highly constrained (too small).

Overall, I couldn't recommend for acception.

Weaknesses:

W1. Novelty of Theorem 1 “More is better for RF Ensembles” ... see also point W2.1.

Response: Thank you for this comment. While we agree that this result is in line with results from Simon et al. (2023) and Bordelon et al. (2024a) for single models, we believe that it might be surprising in the context of ensemble learning, where predictive variance has historically been viewed as beneficial. In random forests, for example, subsampling of data dimensions leads to improved performance even though it reduces the sizes of individual decision trees. In RFRR ensembles, each ensemble member is distinguished by the particular realization of its random features (i.e. the independently drawn $\mathbf{v}\_n\^k \sim \mu\_\{\mathbf{v}\}$). As $N \to \infty$, the function learned by each estimator will converge to the same limiting kernel predictor, destroying the diversity of the ensemble. One might therefore expect reducing the size $N$ of each ensemble member to improve ensemble performance by increasing the diversity of the ensemble's predictors. Other empirical findings have shown that deep feature-learning ensembles do not always conform to the ``wider is better'' intuition observed for single models (see fig. 8 from [1]). We have updated the text of section 3.3 to discuss these points.

W2. Significance ... section 4: W2.1. A main... would be required.

W2.2. In addition to ... premise above.

Response Thank you for your comments, which prompt an important clarification of the difference between figures 1 and 2. As you have correctly understood, in figure 1 we compare ensembles across widths $N$ while keeping ensemble size $K$ fixed. We have made a slight alteration to our numerics to make this clearer: the x-axes of figure 1B now correspond to the width $N$ of the ensemble members. In this case, the total parameter count $M = KN$ grows with $N$. In line with our expectations from Simon et al. (2023) and Bordelon et al. (2024a), we see that the optmial risk decreases with $N$. However, we argue that in the case of ensembles of predictors, this does not follow directly from their results for single models, and might be surprising given the common practice of feature-bagging (see our response to W1). In figure 2 we compare the ridge-optimized performance of RFRR models with fixed total parameter count $M=KN$ as the ensembe size $K$ is varied. You have correctly understood then that as $K$ increases, the size $N$ of each ensemble member decreases ($N = M/K$). We disagree, however, that we should necessarily expect error to increase as a result of this decrease in $N$ because $K$ is also increasing, which is beneficial to the error. Put plainly, the decrease in $N$ and increase in $K$ are competing effects. If variance is the main contribution to the error, one might expect to see a benefit to reducing model size if that means you can average over a larger number of predictors. Theorem 2 guarantees that this is never the case in RFRR, provided that the total parameter count is fixed and ridge is optimized. An ensemble of smaller models might do better than a single larger model, however, when the total parameter count of the ensemble is larger than the number of parameters in the single larger model. We have formalized this fact in the corollary added to section 4 and the surrounding discussion. Please also see the newly added figure S2.

Minor remarks:

“RF KRR” ... dashed lines.

Response: Thank you for pointing out these errors, which have been corrected in the new version of the manuscript. We have replaced "eq's" with "equations." The text of section 2 has been updated to clarify the relationship between $\mathbf{\psi}$\mathbf{x} and $g$\mathbf{v}\_n, \mathbf{x}.

Questions: Q1. Is there any evidence ... RF regression?

Response: We refer to our response to W.1 above.

Q2. In connection to Theorem 2 i... stronger learners?

Response: We refer to our response to W.2 above. In particular, we reiterate that a larger ensemble of weak learners can outperform a small ensemble of stronger learners. This is only possible, however, when the total parameter count of the larger ensemble of weak learners is greater than the total parameter count of the smaller ensemble of strong learners.

[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.

[2] 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.

• 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.

  Response We thank the reviewer for this suggestion, which we agree with. We have made significant updates to clarify that our theory does not cover feature learning in both section 6 and in the discussion section.

• Questions:

  • Is it possible to plot the validation loss in figure 5b as opposed to the test loss?

  Response: Thank you for this suggestion. We clarify that Figure 5b shows the training loss for the C4 language modeling task as a function of training steps in the online setting. In this setting, there is no distinction between train and test loss as each batch consists of previously unseen data. Calculating a validation loss on a larger held-out test set might reduce noise in this figure, but because the curves are already visually smooth, we do not believe this will make a significant difference in the resulting plot. We will add text clarifying the meaning of the loss in the online setting.

  • 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?

  Response: Thank you for pointing this out. After checking our experiments, we agree that models outside the lazy regime do not necessarily follow the "no free lunch" principle. However, we do find empirically that monotonicity is restored when both the weight decay and the richness parameter are jointly tuned to their optimal values. Please see the updated figure 5a and text of section 6.

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.

Response: Thank you for this comment, which we agree with. We have updated our discussion of the results of our deep ensemble simulations to discuss these exceptions to the "no free lunch" principle. We observe that monotonicity holds when error is jointly optimized over weight decay and richness. Please see the updated section 6.

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?

Thank you for catching this discrepancy. To clarify, all random-feature ridge regression experiments are performed on the binarized CIFAR10 and MNIST tasks. The deep ensemble experiment is on the standard CIFAR10 experiment. We do not do MNIST classification with the original labels in any of our experiments. We have updated the manuscript so that the binarized CIFAR10 and MNIST tasks are always referred to as such.

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”

Response: Thank you for pointing out these typos and the error in the legend of figre 1. We gave fixed them in our updated manuscript. We appreciate your careful reading! We will plan to add the lines for $\ell^*$ to the final version of figure 3A.

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?

Response: This is an excellent point! We have added a comment on the potential robustness of ensembleing methods in situations where fine-tuning hyperparameters is not feasible to our discussion of figure 3 in section 4.

Thank you for your review! To your question of using conventional neural network architectures, we have also validated these results for CIFAR10 calssification with ResNet18 ensembles (See Fig. 5.B in updated manuscript).