Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents a bound on the expected risk of a two-layer neural network with smooth activation, where the first layer is trained by gradient descent. The bound is in terms of the smallest L2 distance of the weights to initialization among interpolating solutions. When choosing the total number of iterations to be $n^\alpha$ ($\alpha \in(0,1]$), and the width to be bigger than $n^{5\alpha}$, the bound essentially scales like $n^{-\alpha}$ times the squared L2 distance. The analysis is based on stability, and relies on controlling the smallest eigenvalue of the Hessian of the loss.
main_review: While much of the stability-based generalization analysis is for convex cases, the current paper is able to obtain a nontrivial result for two-layer neural networks, including the optimization part. I think the result is generally interesting, because there are few results that can guarantee optimization and generalization together. One representative set of such results are based on the NTK, but the current paper uses a different approach and might allow the network to escape the NTK regime.

That said, a few things are unclear to me:
1. How does the bound in this paper compare with the line of work that uses distance to initialization to bound the generalization gap, e.g. [1] below? (BTW, this line of papers are not cited in the current paper.) Admittedly, these papers typically don't have optimization guarantees, but it would still be good to have a careful comparison between the bounds.
2. In the theorem where the NTK bound is recovered from the result in this paper (Theorem 2), why can you assume $\lambda_{\min}(K) \gtrsim 1/n$? This is not assumed in the paper of Arora et al. Furthermore, the result in [Arora et al. 2019] does not require bounded or smooth activation.
3. It would be good to have some discussion about the tightness of the bound. For example, in Lemma 2 and Lemma 3, spectral norm is relaxed to Frobenius norm, which seems loose.
4. One main point the paper stresses is that the analysis is not based on the NTK. However, the result does require the width to grow polynomially with the number of iterations, and it's possible that the network still operates in or close to the NTK regime. Is there an explicit nontrivial theoretical example where the current paper gives an explicit nontrivial bound while NTK cannot? 

[1] The role of over-parametrization in generalization of neural networks. Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, Nathan Srebro. ICLR 2019.


The writing in this paper needs significant improvement. There are many small errors and typos throughout the paper. I'd suggest proofreading the entire paper carefully. Some examples I noticed:
- Inconsistency of conditioning: at some places, $(W_0, u)$ are conditioned on, while at other places only $W_0$ is conditioned on.
- Line 20: should be $|y_i| \le C_y$, not $=$.
- Theorem 2: what does $\tilde{O}_P$ mean? Also, $K$ is never defined.
- Assumption 2: you can't assume the loss is uniformly bounded since this is square loss. It seems that what you really need is that the initial loss $L_S(W_0)$ to be bounded by a constant $C_0$. Is this correct, or am i missing something?
- Assumption 1: there should be absolute values on the 0th, 1st, and 2nd derivatives.
- Line 450: the definition of $\ell$ here is for a linear model...
- Line 477, second step: it should be $\sqrt{L_S(W_s)}$, instead of ${L_S(W_s)}$.
- Line 120: "meaning theat"
- Line 160: "a random inputs"
- Line 161: "use our bounds to we show that"
- Line 164: "recall that that"
- Line 198: "$\phi(u)$ continuous" --> "$\phi(u)$ is continuous"
- ...
limitations_and_societal_impact: The discussion is mostly adequate. See main review for some additional questions to be addressed.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper derives bounds for generalization gap of two-layer neural networks using algorithmic stability. The bounds covers noisy and noiseless cases, and depend on the distance of the interpolation solution which is closest to the initialization. With properly chosen number of iterations and network width (with respect to the number of data n), the bounds decay as n increases. 

The bounds requires the width of the networks to be bigger than a polynomial of the number of iterations (specifically, number of iterations times the step size). Hence, it works out of the NTK regime. Through, the bounds can also yield reasonable results in the NTK regime. 
main_review: This paper derives generalization bounds which covers broader cases than the NTK. Though, the assumptions for the network seems to be stronger than NKT. For example, the output parameters u are fixed, and the activation function is smooth and bounded. Under these assumptions, bounding the Hessians of the loss function becomes easy, and thus bounding the stability of GD also becomes easy. However, with the assumptions no special structure or property of neural network models is employed in the analysis, and the same technique can hardly be extended to deep neural networks without producing exponential terms of the depth. 

Other major comments:
1. Although the bounds work out of the NTK regime, but since the width m should be greater than (\eta T)^5, it can easily fall into the NTK regime. As is mentioned in the paper, taking T=n^\alpha, then m>n^{5\alpha}. When \alpha>=0.5, the case is already in the NTK regime. So it seems the new bounds do not extend much from the NTK.

2. The deduction from equation 4 to the equation between line 106 and 107 looks confusing to me. Replacing E\Delta with equation 3 gives ||W-W_0||/(\eta*T), this cancels with the (\eta*T) on the denominator on the right hand side of equation 4, and leaves a 1/n. Why the result has 1/n^\alpha instead of 1/n?

3. It seems the proof part, Section 3, is written in a rush. There are many hard-to-read sentences and typos. For example, in line 198 "The activation \phi(u) continuous and twice differentiable ", and in line 205 "the main theorem a bound on for the gradient descent iterates", and line 211-213 "the generalisation gap can be controlled through both: the step size and number of iterations through the factor alongside the trajectory taken by gradient through the Empirical Risk". 
limitations_and_societal_impact: The authors have adequately addressed the limitations of the work. Since this is a pure theoretical work, there's no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a novel generalization guarantee for over-parameterized one-hidden-layer neural network by using oracle-based stability analysis instead of NTK. 
main_review: The paper provides a new type of non-vacuous generalization bound for over-parameterized shallow neural network. It's original and novel and may provide a new direction for generalization guarantees for over-parameterized models. 

Most parts of the paper is easy to follow. The organization of the paper could be improved, such as moving main results section earlier so that we can remove some equation/statement duplication in both Sec. 2 and Sec. 3, such as the duplication of Eq. (4) and Corollary 1. 

Line 154 mentioned that the oracle-based bound in this paper is tighter than NTK-based bounds because some relaxation of oracle-based bound is applied to achieve an equivalence to NTK-based bound. I am wondering if the authors can provide some examples showing the tighter-ness. For example, does there exist a target function such that oracle-based bound is non-vacuous while NTK-based bound is vacuous?

A few proof steps are not clear to me. For example, in footnote 3 in Page 3, why $L_S (W_T) \lesssim exp(\mu\sum_{j=1}^T 1/j)$ ? Also, I didn't find the proof of Corollary 1 and it's not straight forward to me that Corollary 1 can be derived directly from Theorem 1 and Lemma 1. 

Overall, I believe the paper and its techniques will be interesting to the deep learning theory community.
limitations_and_societal_impact: The limitations of the theorems are addressed in the paper. Since this is a theory paper, the societal impact can be negligible.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose to apply stability-based bound on the overparameterized neural networks and reach non-vacuous bound with early stopping. The authors show that the excess risk can be bounded by an interpolating network with the shortest GD path from initialization. The proof can be extended to NTK regimes and brings some interesting conclusions, e.g., GD with early stopping is consistent. Overall, I think this paper is interesting, and I tend to accept this paper.
main_review: 【contributions】

(a.) The authors propose to apply stability-based bound on the overparameterized neural networks and show that the excess risk can be bounded by an interpolating network with the shortest GD path from initialization (Theorem 1).

(b.) There are some interesting conclusions based on the analysis. For example, (1) GD with early stopping is consistent; (2) one can recover the NTK-form generalization gap via early stopping (Theorem 2). (The early-stopping requirements, in my opinion, are the intrinsic weakness of stability-based bound.)

(c.) The proof is clear and easy to follow. The authors provide some intuitions behind the proof and the theorems. I enjoy reading such a paper.


【questions】

(a)   Line 20, maybe I missed some details. Why do we need |y| = C a constant? 

(b)   Does the results of Arora et al. require \eta T = n? If not, I do not think the claim “our analysis is general enough to recover the results of Arora et al.” is fair.

【some typos】

(a.)  The formula between Line 244-245 lacks “+”

(b.) The motivation of the paper can be significantly improved. I am a little puzzled about whether the authors want to do optimization or generalization when reading the introduction. For example, Line 40-41, “thus, it is not clear whether GD can minimize it up to the desired precision,” makes me think the authors want to do optimization.

(c.)  Maybe I lose some details. Line 101, the condition is m>T^5, while in Theorem 1, the condition is T^3. Could the authors clarify this mismatching?
limitations_and_societal_impact: No potential negative societal impact.
review_title: null

Meta-review: This paper presents a bound on the expected risk of a two-layer neural network with smooth activation, where the first layer is trained by gradient descent. The bounds cover noisy and noiseless cases and depend on the distance of the interpolation solution which is closest to the initialization. 

The reviewers agree that the paper provides a theoretical analysis for the generalization gap of two-layer neural networks using algorithmic stability using a proof technique that is not based on the Neural Tangent Kernel, while obtaining results that have a similar generality of the ones of NTK for two layers networks. Moreover, as observed by some reviewers, the bounds require the width of the networks to be bigger than a polynomial of the number of iterations (specifically, number of iterations times the step size), observing that it also works out of the NTK regime. 

In any case, according to the reviewers, the paper provides a relatively novel proof strategy in the context of theoretical analysis of the generalization of deep learning that is conceptually simpler, and also able to shed light on the properties of the first non-trivial example of a dnn, i.e. a 2-layer nn. We think that this contribution is enough for publication.

However, we strongly encourage the authors to improve the writing of the paper, in particular Section 3, as observed by some reviewers. 
Decision: Accept (Poster)