How many classifiers do we need?

Thank you for reviewing this paper and we really appreciate your comments and questions.

[Weakness 1] Agreed. That was the reason why we narrowed down the scope to interpolating models in Conjecture 1 although Theorem 1 holds for any ensemble. We think it would be an interesting direction to see how $\eta$ differs in non-interpolating models in different fields (e.g. language models).

[Weakness 2] Thank you for catching this. We will fix this in the final version.

[Weakness 3] The long underscore is due to the footnote below the formula.

[Weakness 4, Question 1] Please see the general response: "interpolator" is a model that is trained to perfectly fit the train data. In Conjecture 1, we wanted to draw a statement analogous to so-called 'neural scaling laws', which states that the out-of-sample performance of an interpolating neural network scales with the width of the neural net. We will add a paragraph about this on the final version.

[Weakness 5, Question 2] In Theorem 5, we prove that the disagreement for $N$ classifiers has a representation as $(1-1/N)(D_\infty + N^{-1/2}Z_N)$, and through Donsker's invariance principle, it can be approximated through the disagreement of a smaller number of classifiers (say $M$) as $(1-1/N) / (1-1/M) * (\text{Disg. of }M\text{ classifiers})$. The justification for this argument is that the disagreement is a $V$-statistic, and so its bias can be accounted for. The same is true for the numerator of $\delta$ (the denominator is unbiased): it is also a $V$-statistic, and should behave similarly to the disagreement, as its form is the same with only one less label. We will add this clarification in the final version.

I would like to thank the authors for their detailed response. To acknowledge that my concerns have been addressed, I will update my score.

Thank you for reviewing this paper; we really appreciate your comments and questions.

[Weakness 1] We agree that further empirical evidence would strengthen our claim. It is difficult to obtain an ensemble of well-trained interpolating models in practice, so we are limited in our selection of models and datasets. For now, we provide further evidence of the universality of $\eta<4/3$ on two additional datasets in the figure document: KMNIST and Fashion-MNIST. Please refer to Figure A on the figure document attached to the rebuttal for all reviewers above.

On KMNIST, which is an easier task than CIFAR-10, ResNet18 with various width (48, 64) were trained with various batch size (32,64,128) to interpolate the train data. On Fashion-MNIST, ResNet18 with width 48 was trained with batch size 128 to interpolate the train data.

[Weakness 2, Question 3] The main role of Theorem 5 is to justify our approximation of the entire disagreement curve by neglecting $N^{-1/2}Z_N$. If we used a ordinary central limit theorem, we could only justify approximations of $D_n$ for large $n$. Appealing to Donsker's invariance principle, we can justify our procedure of extrapolating the disagreement as $D_n = D_3 * (1-1/n)/(1-1/3)$.

In this case, $\sigma^2$ is equal to $Var_{h\sim\rho}(L(h))$. We will update this in the final version along with the typo on the $U_N$ Hoeffding decomposition in Line 214 where $E_{\rho_N^2}$ should be $E_{\rho^2}$ instead.

[Question 1] We rephrased the theorem and conjecture and posted as a rebuttal for all reviewers above. We hope this clarifies the statement.

[Question 2] Perhaps it is only at an intuitive level, but we see neural collapse and reduced entropy on the probabilities as symptoms of the same general phenomenon. If the representations within each class are reduced to a single point, then a classifier ensemble is going to become increasingly confident within each class, as there is less variability in the outputs.

[Question 3] Answered with Weakness 2 above.

[Question 4] Thank you for pointing this out. We will update this to $\mathcal{L}(h)=\mathbb{E}\_{h'\sim\rho}\mathbb{P}\_{\mathcal{D}}(h(X)\neq h'(X))-\mathbb{E}\_{(h',h'')\sim\rho^2}\mathbb{P}\_{\mathcal{D}}(h'(X)\neq h''(X))$ in the final version.

Thank you for your positive appraisal of our work!

[Weakness 1] Please see the general response. Interpolators are models that are trained to perfectly fit the train data, and appear prominently in the double descent literature, as well as prior explorations into the benefits of ensembling.

[Weakness 2, Question 1] Thank you for pointing this out. It is true that the empirical approximation converges to $\eta$ itself. Here the bound becomes trivial with large $m$, as $\eta$ is clearly bounded by the maximum of $4/3$ and itself.

We rephrased the theorem and conjecture and posted as a rebuttal for all reviewers above. We hope this clarifies the statement. Our conjecture follows from the observation that $P/S$ is less than $4/3$ (and hence $\max\{4/3, P/S\}$) for interpolators. To prove this in the theory is a fascinating open problem for us.

[Weakness 3, Question 2] We will add more implementation details to Appendix C in the final version. The constituent classifiers differ in weight initialization and vary due to the randomized batches used during training. We see that the number of classifiers we used (mostly 5) is specified in Appendix C.1, but please kindly let us know if you feel we missed something.

[Question 3] Thank you for pointing this out. We will correct this in the final version.

Thank you for your positive review of our paper; we greatly appreciate your comments and questions.

[Weakness 1] Please see the general response: we hope that the newly presented form of Theorem 1 addresses your concerns. In the original wording, we state that an $\eta$ greater than the stated lower bound is guaranteed. This is true, but one should pick the best possible $\eta$ for the task, which is what the newly worded theorem now states. $4/3$ in the theorem mainly arises from Lemma 1, equation (9). The notable point is that the value $4/3$ aligns well with the empirical result as shown in Figure 1.

[Weakness 2] Thank you for your comments. Please refer to Figure C on the figure document attached to the rebuttal for all reviewers above. On KMNIST, which is an easier task than CIFAR-10, ResNet18 with various width (48, 64) were trained with batch size (32,64,128) to interpolate the train data. On Fashion-MNIST, ResNet18 with width 48 was trained with batch size 128 to interpolate the train data.

[Question 1] Lemma 2 states that the majority vote error rate is smaller than $P(W_\rho > 1/2)$, the numerator term in the definition of polarity. If the error W_\rho(X) is smaller than 0.5 for all datapoints in the test set, the equality holds and the majority vote error rate $= P(W_\rho > 1/2) = 0$. This ensemble is $0$-polarized and thus $4/3$-polarized. We may have misunderstood your question. Could you explain a bit more about what you meant by 'small or large error regime (e.g. $\epsilon$ or $0.5-\epsilon$)'?

[Question 2] We avoided overlaying those bounds (described in Section 2.2) as they are so far above the current set of axes that one cannot deduce the accuracy of our novel bounds. Please refer to Figure B in the figure document attached to the rebuttal for all reviewers above

[Question 3] We used # as an indicator function 'f(A)=1 if A is true, otherwise 0'. For clarity, we will change this in the final version to a more common notation $1_A$.

Our current theory doesn’t suggest a general positive correlation. This is reflected in our experiments: when comparing the CIFAR10 and CIFAR10-1 examples in Figure A (figure_document), the polarity of the interpolators hasn’t changed significantly, even though the majority vote error rate has increased by ~0.1 on average.

However, we do not reject the possibility that a correlation might exist on a case-by-case basis. Our listed examples, Example 1 and Example 2 on page 4, highlight two extreme cases where this correlation is present. We are interested in conducting further investigations in future work.

Regarding polarity, as both Figure 1 and Figure A (figure_document) suggest, and based on our efforts to make Lemma 1 reasonably sharp, we conjecture that 4/3 is not purely an artifact of the proof.