Benign overfitting in leaky ReLU networks with moderate input dimension

We thank the reviewer for the overall positive feedback on our work. We are confident we have addressed each of the issues raised and hope the reviewer might consider raising their score in light of our responses.

Linearly separable data

Indeed, a linear classifier is sufficient to learn this problem: we also demonstrate that the max-margin linear classifier benignly overfits in our data setting. However, shallow neural networks are substantially more complex models and can express a rich class of functions. Without explicit regularization, previous conventional machine learning wisdom suggests neural networks will not learn a linear classifier. Results on benign overfitting in the linearly separable setting, including ours, demonstrate that the implicit bias of neural networks trained with gradient descent is favorable to learning linear problems.

No comparison with [1]

We thank the reviewer for bringing this to our attention and will more thoroughly compare our work with [1] in the future revisions. Here are the comparisons with [1]:

• The settings are very similar with regards to the data assumptions, network model, and training. The most significant differences is that [1] uses ReLU activations and requires $d = \Omega(n^2\log n)$ while we use leaky ReLU and $d = \Omega(n)$.

• The proof techniques for the two papers are very different. In [1], the authors analyze the activation patterns of the neurons during various phases of training. We do not consider the activation patterns and instead bound how much the neural network can diverge from a linear model. These different techniques are appropriate in different settings: for a ReLU network it is possible that the dynamics of different neurons are driven by different subsets of the data, but with leaky ReLU this effect is weaker and the network is closer to a linear model.

• Both papers prove the existence of multiple distinct "overfitting" regimes. However, [1] also shows a regime where the network fails to overfit. This regime does not occur for the leaky ReLU network model we use: Theorem 3.1 shows that networks always achieves zero loss in our setting.

More discussion on $\gamma$ and $k$ is needed

We highlight that in both Corollary 3.2.1 and Theorem 3.3 the classification error increases with $k$. The classification error bound uses the norm of the network weights, which by Theorem 3.1 is proportional to the norm of the max margin classifier. We bound this twice. In Lemma B.3 we get a dependence on $k$ by constructing an "ideal" linear classifier: one that uses the true signal vector for clean points and the noise only as minimally needed to fit the corrupted points. If $\gamma$ is small, then the classifier constructed in Lemma B.4 (which uses only noise) has smaller norm. In fact, if $\gamma$ is too small, this norm is so much smaller that the network can never learn the ``ideal'' classifier, which leads to Theorem 3.4 (non-benign overfitting).

Sample complexity is $\Omega(n^2)$ in Theorem 3.1

The number of iterations $T$ does not directly contribute to $|\mathcal{A}|$. In the proof of Theorem 3.1, we bound $|\mathcal{A}|$ by bounding the number of non-zero data point updates. The bound for the number of updates is also a (pessimistic) bound for $T$, which we do not use but record for completeness.

Larger $m$ leads to a larger misclassification probability

The misclassification probability can increase if $m|\mathcal{A}|^2$ increases. But in Theorem 3.1, $|\mathcal{A}_{GD}| \sim m^{-1/2}$. Thus our results specifically for neural networks (Corollary 3.2.1, Theorems 3.3 and 3.4) are independent of $m$.

In Corollary 3.2.1, I didn't see $\delta$ in the main result.

The parameter $\delta$ refers to the "failure probability" of the data generation process. It appears in Theorem 3.2 in lines 228--230.

Lemma B.1 can obtained from the high dimensional probability book

We thank the reviewer for drawing our attention to Theorem 4.6.1 in High Dimensional Probability by Vershynin. We emphasize that Lemma B.1 summarizes two results by Vershynin and co-authors that together are equivalent to 4.6.1. We have clearly cited both works and do not claim this lemma to be a novel or significant part of our contribution.

It would be possible to consider general data generation process?

Proving results for arbitrary data distributions might be intractable as benign overfitting does not always occur even experimentally. However, our results for benign overfitting (Theorem 3.2) can be proven in a slightly more general setting. If all coordinates of noise are i.i.d. sub-Gaussian, the same result will hold with an analogous proof. We chose to work with Gaussian noise to prove error lower bounds (Theorems 3.3 and 3.4). We emphasize that our data assumptions are standard for works in this space.

$d = \Omega(n)$ is still large, what is the limit for this? Maybe constant order is sufficient?

We believe that the regime $d = O(n)$ will lead to different results than the ones observed in our paper, is challenging, and will involve different techniques to study. In particular, if $md \leq n$, then the network is underparameterized and will likely not perfectly fit the data. When $d = 1$ and the network is sufficiently wide, there are partial results in the literature which suggest that the network will perfectly fit the data, but the overfitting is not benign [2]. To our knowledge, the general case $d = O(n)$ remains open.

In the proof, line 706...

Thank you for highlighting this. There was a missing factor of $\dot{\sigma}(\langle w\_j^{(t)}, x\_l\rangle)$. This does not affect the correctness and we will correct this in future revisions.

Typos

Thank you for drawing this to our attention. We will make another thorough proofreading to fix typos in revised versions.

[2] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in ReLU neural networks. Advances in Neural Information Processing Systems, 2023.

thanks for the authors' rebuttal.

It addressed some of my concerns but there are still some issues that prevent me to give higher score for very positive support. For example, the linear separable data assumption and the specific data generation process.

Besides, the comparison with [1] include different techniques but the setting is quite close.

Accordingly, I kept my score unchanged.

We thank the reviewer for their feedback and questions. It appears that the primary concern lies in the fact that our results only hold for shallow networks and linearly separable data. We emphasize that these are limitations also present in the existing literature on benign overfitting in non-linear models / networks in the rich feature learning regime (i.e., not leveraging the NTK framework). The primary contribution of our work is to relax the relationship between the input dimension and the number of points: in particular past works require a very large input dimension, $d = \Omega(n^2 \log(n))$ or worse. In contrast, our results are for $d = \Omega(n)$ which is far more realistic. Furthermore to achieve this required new and highly different techniques to those used in the existing literature. As a result we would respectfully ask the reviewer to reconsider their rating. We proceed to address in more detail the specific weaknesses highlighted.

This paper mainly studies a specific shallow leaky ReLU network. The applicability of the results is limited to deeper neural networks or other complex models such as CNN and transformer.

The results rely on a specific linearly separable data distribution assumption.

• Our setup involving a shallow ReLU network combined with the proposed data model is a) in-line with relevant and recent literature on the topic and b) represents perhaps the simplest and most natural setting involving a non-linear model in which one can study benign overfitting. Even in this simple setup many theoretical questions remain open: in particular, all past works require a near orthogonality condition on the data. As the emphasis of our work is to relax this technical condition we decided to work with this canonical setup. Deriving theory for more complicated settings, in particular deep networks and transformers, is clearly an important open problem. Such theory will almost certainly be built upon a solid understanding of the simple, shallow case.

The dependence of Theorem 3.2 and Theorem 3.3 on $n, d, k$ does not cover all cases. For other cases, what are the characteristics of overfitting?

• In Theorems 3.2 and 3.3, the assumption $k = O(n)$ is minimal, since we always have $k \leq n$. The relaxation $d = \Omega(n)$ from $d = \Omega(n^2 \log n)$ is a main improvement of our results from prior work. We believe that the regime $d = O(n)$ will lead to different results than the ones observed in our paper, and will involve different techniques to study. In particular, if $md \leq n$, then the network is underparameterized and it is likely impossible to perfectly fit the data. When $d = 1$ and the network is sufficiently wide, there are some partial results in the literature which suggest that the network will perfectly fit the data, but the overfitting is not benign [1]. To the best of our knowledge the case $d = O(n)$ remains open.

[1] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in ReLU neural networks. Advances in Neural Information Processing Systems, 2023.

We thank the reviewer for reading our paper and for raising their questions and comments. We are confident that we can clarify the issues raised and hope in light of our responses below that the reviewer will consider raising their score.

The paper may lack some experiments. The results are fully theoretical. If there are some empirical experiments, the conclusion will be more convincing.

We appreciate the suggestion of including experiments to better explain our results. We will update the paper to include experiments in future revisions. We've attached a file showcasing a couple of experiments along with explanations in the main rebuttal.

There are few explanations for theorems and assumptions. Some additional explanations may let readers understand the results better.

We are happy to provide more commentary in future revisions. To clarify here, in regards to the assumptions, Assumption 1 upper bounds both the step size and initialization scale. Both of these bounds are required for the proof of convergence to a global minimizer: we remark that although they are no more egregious than comparative theory works in this space, they are typically smaller than what is used in practice. Assumption 2 clarifies the model we consider and the assumptions on the data: in particular we consider data drawn from a mixture of Gaussians with a relatively small number of label corruptions. This is very standard in the literature. In terms of our results, we give an overview in Section 1.1 outlining the role of the different Theorems and Lemmas. In terms of explaining our proof techniques, we chose in Section 4 to present the key ideas using the simple case study of a linear model. In particular we highlight four key steps: first derive generalization bounds using the SNR of a classifier in terms of the size of its component in the noise versus signal subspace, second upper bound the max margin classifier, third and fourth use the bound on the max margin classifier as well as the zero loss property to to upper and lower bound the SNR.

Since hinge loss may not be so commonly used in the analysis of neural networks, maybe you can also try on other loss functions like cross-entropy loss or logistic loss.

We agree that different loss functions would be an interesting generalization of our results. We chose the hinge loss because it exhibits similar properties to other classification losses (such as de-emphasizing points which have already been correctly classified) while having favorable properties for theoretical analysis (such as convergence in finitely many iterations). We expect that our results could admit generalizations to the cross-entropy or logistic losses with an appropriate analogue of the convergence analysis in Theorem 3.1. Fundamentally, our generalization bounds depend on gradient descent converging to a solution which is approximately margin maximizing. For any other loss function satisfying this property, we immediately obtain a benign overfitting result by applying Theorem 3.2.

Since the proof techniques and ideas are closely related to [1], what is the main difference between the two papers?

The main result of [1] is that a leaky ReLU neural network trained with the hinge loss on linearly separable data will converge to a global minimizer. Moreover, the weights of this solution have norm bounded above by the norm of the max-margin linear classifier of the data. While this idea and proof technique are important to our paper, our main contributions are in describing how this margin maxmimization results in benign overfitting. That is, we are interested in the generalization of leaky ReLU networks on noisy data, and we use a similar convergence analysis as an intermediate result to this goal. While [1] does establish a generalization bound in Theorem 4, the bound assumes that population dataset is linearly separable rather than just the training dataset. Hence, it cannot be applied when the training dataset has label-flipping noise, which is the setting that we are interested in for benign overfitting. The bound also gets worse as the learning rate $\eta$ goes to 0, while our generalization bounds do not have any dependence on $\eta$. In order to make these adaptations, we perform an analysis which uses properties of our specific data model. In the process, we obtain a more detailed understanding of how generalization depends on the number of data points, the dimensionality of the data, and the amount of noise in the data.

We are glad the reviewer appreciates the contribution of our work and thank them for highlighting the two related works on linear models [1,2]. We are happy to cite these and discuss them in future revisions. We also thank the reviewer for spotting the two typos listed, we will do a further thorough proofread before uploading a revised version.

In regard to the question

What do the authors expect to change for multiclass classification with a more complicated mixture model?'

A multiclass classification setting is an interesting future direction to look into. It would involve looking at a different model / loss but the general form of argument, i.e., bounding the singular values of the noise matrix and comparing to the one hot class max-margin classifiers, seems possible to generalize to this new setting.