Summary
This paper considers the various settings of overfitting, including benign overfitting where an interpolating estimator is optimal in spite of perfectly fitting noisy labels, tempered overfitting where an interpolating estimator is inconsistent but error is a function of the label noise, and catastrophic overfitting where an interpolating estimator has no ability to generalize (random guessing in classification or infinite risk in regression). The authors follow-up prior works in benign overfitting by showing that a two layer neural network can benignly overfit so long as the input dimension of the data grows faster than the number of training samples, irrespective of the width of the network itself (assuming convergence to a max-margin solution, and additionally show another benign overfitting result that only requires convergence to a KKT point of a max-margin problem).
They also provide a theoretical justification for tempered overfitting in two-layer ReLU networks, a phenomena that was empirically studied in prior work. The authors precisely characterize the excess risk of an interpolating network trained to fit uniform data with labels samples as +1 and flipped to -1 with probability p. The authors show that for one-dimensional data, the excess risk of such a network interpolating this problem is tightly bounded by functions of the noise level (e.g. theta(poly(p)) and theta(p) in a more restrictive setting).
The authors then observe that catastrophic overfitting can occur when forcing networks, of width at least 2, without a bias to interpolate the training data (drawn as specified before) when there is at least one sample with -1 label. They also show that you cannot obtain benign overfitting from convergence to a KKT point of the max-margin problem unless the network has a bias term.
Finally, the authors provide an extended version of an experiment from prior work on tempered overfitting in which fully-connected ReLU networks are trained to interpolate data on the unit sphere with +1/-1 labels sampled with probability p, as defined before. They observe that there are regions between benign and tempered that are a function of the ratio of input data dimension to number of training samples, namely: as the input data dimension grows higher than the number of training samples, the excess risk of the model approaches 0. They additionally show experimental results on 3-layer networks to empirically assert that, while their theory holds for 2 layer networks practically the same behavior is seen for 3. Finally, they experimentally show in their setting that the width of the network is not as important as the input dimension when evaluating consistency of the estimator.
EDIT: Thank you for the rebuttal and engaging response, this is indeed a very thoughtful work. I opt to keep my positive score.
Strengths
This paper provides a clear theoretical analysis for tempered overfitting for two-layer ReLU networks that has not appeared in prior literature. There is some earlier theoretical work on tempered overfitting in kernel regression and for minimum description length settings, but as far as I know nothing for a standard finite-width neural network. The prior cited work (Mallinar et al. 2022) shows experimental evidence with neural networks that suggests tempered overfitting, and following their formalisms the authors of this work go a step further to give proofs of excess risk of one of the experiments in that paper (more on this in later section).
I really appreciate the authors providing proof outlines and intuitions in the main text, as well as citing references where they are using techniques and following proof styles introduced in prior works. The style of explanation is accessible and gives me, at a high level, the right amount of information to contextualize the theorem statement while deferring details to the appendix should I want to review them.
There are many intriguing results from this paper. For one, I am initially surprised by the one-dimensional tempered results and Theorem 4.1 on benign overfitting feature bounds that don’t depend on the width of the network. I’ve written more about this in the questions section, but I would have expected a more subtle interplay between width of the network and input dimension of the data. Notably, though, the width of the network has to be sufficiently large to interpolate the data (e.g. overparameterized) and since the authors study 2-layer networks this might imply a large width, though their experimental results show roughly similar behavior for width 3000 and width 50 networks) across varying input dimensionality.
I find the role of bias section illuminating as well. To the best of my knowledge, I haven’t seen a generic negative result like this, that any bias-less network will have a risk lower bounded by a function of the network width or the support of the negative training samples.
Weaknesses
The authors do acknowledge it and give a tighter bound subsequently under stronger assumptions, but Theorem 3.1 has an upper and lower bound gap that is growing with p. It’s not really a weakness of the paper, but it would be nice if the authors wrote a bit about when this bound can be very tight (as a function of p, m?).
Theorem 4.3 seems to indicate a dependence on p being smaller than some constant divided by the width of the network squared, which seems to indicate for very wide networks that this result holds for p shrinking -> 0. While interesting, I’m not sure if this is the most general result and the authors don’t discuss in too much detail the implications of this, and what settings of network width lead to various results apart from n=O(1). For instance, it could be useful to assert if p is meaningful for n >> m or n ~ m, etc. There are common settings of network width with relation to number of samples or input dimensionality and at first glance I don’t know whether this theorem will give me a useful result in many of those settings.
Additionally, this theorem trades off one assumption (convergence to a max-margin solution vs. KKT point of max-margin problem) for another (output weights are fixed as +- 1 and only the input weights are trained). They mention this theorem stems from attempting to drop the strong assumptions of the prior theorem (Theorem 4.1), but to me it seems perhaps to still include a new, strong assumption. Granted, I’m unfamiliar with the works cited in the footnote that study this setting in particular. Maybe the authors can provide a little exposition about why this setting is of particular interest and what motivates it in the grander study of neural networks?
Missing concluding thoughts, would like to see some final discussion on everything and where the authors see next steps going.
Other notes / fixes:
- Page 5, 3rd paragraph: double “we we” in the line “we we get that the total length of all…”
- Figures could use grid-lines as well as separate line-styles to differentiate the settings for accommodation to colorblind people and for printing in black and white
Questions
In the setting where all layers are trained the width does not seem to be so important. This definitely speaks to the intuition I have that the ambient dimension of the data is what matters. When studying a random feature model the ambient dimension is indicated by the width of the first layer, but when you train that layer too the ambient dimension would be the input dimension. These results make me want to understand more the interplay between intrinsic and ambient dimension, as well as bottleneck vs. non-bottleneck networks in overfitting. Do you have any further intuitions about these comparisons? Is this width-independence something you would expect to hold for deeper networks, or other architectures?
Does Proposition 4.5 subsume Proposition 4.4? Could you explain a bit more about the difference here. n=2 in Prop 4.5 would lead to a lower bound of ¼ but in Prop 4.4 the lower bound is ½. I haven’t read deeply the proofs on this section but it might help to give a little more exposition on what assumptions are made about width that differ between 4.4 and 4.5.
You prove tempered overfitting for one-dimensional data only, but practically it seems that it is more about certain settings where the ratio of input dimension to number of samples satisfies some criteria (at least, experimentally and based on prior works). Can you speak to the difference between the theorem you propose and practice? It appears that tempered overfitting could occur at any input dimension, depending on how much training data is used. Can your proof techniques be extended to explain this?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.