Benign overfitting in leaky ReLU networks with moderate input dimension

Summary

This paper stuides the benign overiftting of two-layer neural networks (only training the first layer) with leaky ReLU for binary classification, which relaxes the dimension condition on the dimension from $d = \Omega(n^2 log n)$ to $d = \Omega(n)$. The considered problem setting is - data generation process: the label is generated by Gaussian data corrupted by flipped noise under a linear function after sign. The parameter $\gamma$ controls the component of signal and noise. The more $\gamma$, the more signal. - the used loss is hinge loss, and the involved with optimization algorithm is sub-gradient descent. The obtained results include that - implicit bias: the obtained solution (neural network parameter) will converge to a max-margin linear classifier. - condition of benign overfitting: $d = \Omega(n)$, signal strength $\gamma = \Omega(1/k)$ - non-benign overfitting: $d = \Omega(n)$, $\gamma = O(1/d)$

Strengths

- relax the dimension dependence from $n^2$ to $n$ - provide the condition for benign overfitting (or not) - demonstrate the implicit bias: converge to a max-margin linear classifier

Weaknesses

- this paper requires linear separable data, more strictly speaking, the optimal Bayes classifier is linearly separable, that means linear classifier is sufficient to learn this problem. I don't see the strong motivation of using two-layer neural networks, though this is a common issue in the benign overfitting community. - One major issue is, no comparison with [1]. I think this comparison should be included in terms of problem setting, proof techniques, the obtained findings. - About the main result, intuitively, classification rate is proportional to $k$, the number of corrupt points. More discussion on $\gamma$ and $k$ is needed. - Regarding theorem 3.2, it's unclear to me in several points: i) the sample complexity is $\Omega(n^2)$ in Theorem 3.1. How does this contribute to $|A|$? iI) a larger $m$ leads to a larger missclassification probability. Intuitively, a larger size of neural network is better for performance. - In Corollary 3.2.1, I didn't see $\delta$ in the main result. - Lemma B.1 can be directly obtained from the high dimensional probability book, Chapter 5. --- [1] George etal. Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign? NeurIPS 2023.

Questions

- The key idea is to bound the weight norm and its alignment with any linear separator of the data during each update by the distribution of sigular values of the noise. In this case, the obtained results heavily depend on the data-generation process. It would be possible to consider general data generation process? Besides, $d = \Omega(n)$ is still large, what is the limit for this? Maybe constant order is sufficient? - In the proof, line 706, in the last inequality, regarding the summation $\sum_{i,l} \in F(t)$, there is one term missing about $\langle w_j^{(t)}, x_j \rangle$? - There are some typos: line 707: $\sigma(s)$ -> $\sigma(z)$

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

n/a

Summary

The paper studies benign overfitting in leaky ReLU networks trained with hinge loss on a binary classification task. The paper gives the conditions on the signal-to-noise ratio under which benign or harmful overfitting occurs for leaky ReLU networks. Unlike the previous related works, this paper does not require the training data to be nearly orthogonal and reduces the input dimension required from $\Omega(n^2\log n)$ to $\Omega(n)$.

Strengths

1. The paper demonstrates that leaky ReLU networks trained on hinge loss with gradient descent satisfy an approximate margin maximization property. 2. Prior works usually supposed nearly orthogonal data setting and dimension $d=\Omega(n^2\log n)$. However, this paper needs linearly separable data and dimension $d=\Omega(n)$, which weakens the requirement.

Weaknesses

1. The paper may lack some experiments. The results are fully theoretical. If there are some empirical experiments, the conclusion will be more convincing. 2. There are few explanations for theorems and assumptions. Some additional explanations may let readers understand the results better.

Questions

1. 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. 2. Since the proof techniques and ideas are closely related to [1], what is the main difference between the two papers? [1] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over-parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have shown the limitations as the future directions in the paper.

Summary

This paper studies the benign overfitting of two-layer leaky ReLU network for binary classification with only mild overparameterization under a simple Gaussian mixture model assumption. First, the paper proves that for sufficiently small initialization, gradient descent with hinge loss converges in a polynomial number of iterations to an approximate max-margin solution. Then, the paper establishes that any approximate margin maximizer achieves benign overfitting, or low test error, in an (essentially tight parameter) regime where $d = \Omega(n)$. These results are matched by lower bounds in certain parameter regimes (low SNR and high label noise).

Strengths

1. This paper is well-written, clear, and technically interesting. I especially appreciated the technical overview, where the main proof ideas are explained. 2. Previous works required $d = \Omega(n^2 \log n)$ to obtain benign overfitting due to using near-orthogonality of the input data, but this work only requires $d = \Omega(n)$, which is tight (for the overparameterized regime). Hence extending benign overfitting to this setting requires using subgaussian bounds on the extreme singular values of Gaussian matrices. I do want to note that this idea has also been used to prove benign overfitting for binary and multiclass classification $d = \omega(n)$ (see e.g. [1, 2]) 3. Many prior works studied linear models, whereas this paper studies ReLU activation (although with only one trainable linear layer). 4. It is of particular note that the proof techniques do not rely on exact margin maximization, as the results then apply to parameters found by GD in polynomial time (as opposed to the infinite time limit). Many (though not all) previous works have explicitly studied the limiting parameters (e.g. min $\ell_2$-norm interpolation), which is not reached in practice. 5. As I described in the summary, the upper bounds have matching lower bounds in some parameter regimes. Theorem 3.3 is a matching lower bound for the misclassification probability in the regime where the label noise rate $k/n = \Omega(1)$, which is fairly realistic. [1] Wang, Ke, and Christos Thrampoulidis. "Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization." SIAM Journal on Mathematics of Data Science 4.1 (2022): 260-284. [2] Wu, David, and Anant Sahai. "Precise asymptotic generalization for multiclass classification with overparameterized linear models." Advances in Neural Information Processing Systems 36 (2024).

Weaknesses

No major weaknesses to report.

Questions

1. What do the authors expect to change for multiclass classification with a more complicated mixture model? 2. Line 278, there is a typo; it should be $X \sim N(\sqrt{\gamma}a_v, \frac{1-\gamma}{d}\| z\|^2)$. 3. Line 325, “of” is missing in “The proof Theorem 3.3,...”

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes

Summary

This paper studies benign overfitting in a two-layer leaky ReLU network trained with hinge loss for a binary classification task. This paper proves that in a finite iteration, the leaky ReLU network can reach zero training loss through gradient descent, and the network weight matrix after convergence will approximate the max-margin. And this paper provides the conditions for benign overfitting and non-benign overfitting of the leaky ReLU network.

Strengths

This paper improves the previous work's requirements for almost orthogonal training data and input dimension $d= \Omega(n² \log n)$, and only requires $d = \Omega(n)$.

Weaknesses

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.

Questions

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?

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See Weaknesses