Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper calculates a bound on the generalization error of a committee machine (i.e., a two layer neural network with weights of the top layer fixed to all 1s). It shows O(1/sqrt(n)) generalization gap if the number of hidden neurons is m > (eta T)^3 where eta is the learning rate of gradient descent/stochastic gradient descent and T is the number of gradient updates. This improves a previous result (m > (eta T)^5) slightly. The analysis relies on using algorithmic stability and constructing a lower bound on the smallest eigenvalue of the Hessian.
strengths_and_weaknesses: + The analysis is sound as far as I could check.

+ The analysis of SGD follows along very similar lines of [46] and the analysis of GD, but I believe it is novel, in principle.

- I believe this work makes very minor improvements, both technical and methodological ones, on top of existing work, in particular [46]. I will give an example below.

The authors note on Line 182 the bound in [46] is m > (eta T)^3; this is very close to the bound in this paper of m > (eta T)^3 n^{-2 alpha/(1+alpha)}. This comment also applies to the comment on Line 189 where the bound on the eigenvalue of the Hessian is improved from O(sqrt(eta T)) to O(n^{-1} eta T). These are minor technical improvements and one wonders whether we are learning anything new about the problem that gives a unique insight. The proof of Lemma 3, the comments on Lines 196-200 and Remark 3 suggest that W^*_{1/eta T} or W^* are close to the initialization W_0 and thereby close to W_t as well. I have similar reservations about Theorem 5.
questions: 1. There is a typo on Line 120, the empirical risk should be divided by n.

2. The relevance of the results rests crucially on alpha. Can you give an intuitive explanation of what the parameter is?
limitations: N/A
review_title: null

final_score: 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.
review_content: summary: The paper improves algorithmic stability analysis of GD-trained shallow neural networks of [46]. In particular, [46] required overparameterization of order $\text{width} \geq (\text{step-size} \cdot \text{GD-steps})^3$ for the stability/generalization bound, whereas in the current paper this is improves till $\text{width} \geq (\text{step-size} \cdot \text{GD-steps})^2$ when the problem is 'easy'. Moreover [46] showed an excess risk bound which required overparameterization of order $\text{width} \geq (\text{step-size} \cdot \text{GD-steps})^5$, whereas in the current paper this is improved till exponent of 3. In this paper (as in [46]) the theory works for an early stopped GD (i.e. $\text{step-size} \cdot \text{GD-steps}$ is taken to be a sublinear function of the sample size), which makes sense since otherwise consistency is not achievable. The excess risk bound scales with the `niceness' exponent of the problem. The analysis is also extended to SGD.
strengths_and_weaknesses: Strengths:
* Improves overparameterization rates compared to [46] (see details below).
* Excess risk analysis avoid oracle-type arguments of [46] and makes bound more specialized (see details below).
* Extends analysis to SGD.

Weaknesses:
* Comparison to the literature is somewhat lacking, in particular in terms of rates (e.g. to [46] and/or to [1*]), or at least a discussion why it is challenging is missing.
* Sometimes the narrative is unclear, bits of the proof ideas are introduced here and there. Perhaps it would be beneficial to have a separate proof idea section.

Rate improvements achieved in this paper are rather technical. The key observation is that the smallest eigenvalue of the Hessian matrix of the empirical risk between two parameters $\mathbf{W}$ and $\mathbf{\tilde{W}}$ scales as $-\frac{1}{\sqrt{\text{width}}} (\|\mathbf{W} - \mathbf{\tilde{W}}\| + 1)$. When these parameters are taken to be iterates of GD with intact and perturbed training sample, [46] controlled $\|\mathbf{W} - \mathbf{\tilde{W}}\|$ in a pessimistic way through descent-lemma type argument. The current paper delves into a more elaborate argument and shows that both iterates converge to the regularized solution + some offset which is expected to be much smaller than in the pessimistic case.

The second contribution of the paper is control of the excess risk which is based on the certain regularity of a problem. [46] showed an oracle-type bound where the excess risk scales with the $\ell 2$-norm of a minimal-norm interpolating network (here norm is understood as relative to initialization, i.e. always involves $\cdot -\mathbf{W}_0$). In the current paper, instead, the control is done w.r.t. the minimizer of $\ell 2$-penalized risk and then the paper assumes that the approximation error of the true risk behaves nicely, i.e. as $\lambda^{\alpha}$ where $\lambda$ is a regularization parameter and where $\alpha$ is a niceness exponent. This is a common technique in analysis of the ridge regression. Finally $\alpha$ makes its way into the exponent of the excess risk rate (as in the ridge regression case).
At this point one would expect some comparison of rates: for instance [46] showed some rates where is on RKHS or GD in nonparametric setting [1*].

[1*] Hu, T., Wang, W., Lin, C., & Cheng, G. (2021, March). Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics (pp. 829-837). PMLR.
questions: How large the width should be in terms of the sample size when $\text{step-size} \cdot \text{GD-steps}$ is set w.r.t. sample size? Is overparameterization mild (i.e. subquadratic)?
Actually, Table 1 could also include the order of the width in terms of the sample size.
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the generalisation of shallow neural networks using algorithm stability. The work provides a tighter analysis of [1], obtaining a similar generalization for smaller width $ m \sim O ((\eta T) ^ {3}) $ in comparison to $ O ((\eta T) ^ {5}) $ in [1]. The paper also extends the results for SGD with a similar over-parameterization requirement. 
strengths_and_weaknesses: Strengths:

1) This work identifies crucial quantities in the analysis of analysis as [1] majorly, $ \| W_ {t} - W_{1/\eta T}^{*} \| $ or $R_{T}$. Using these quantities, the paper produces a finer analysis reducing the overparameterisation required to obtain similar generalisation guarantees. 

2) Also extend the stability analyses to SGD. 

Weakness:
1) The paper clearly extends the results of [1] and mostly follows a similar framework. Hence, it also suffers from the same limitations as the original paper where the number of parameters still depends on $T$ and early stopping is required even for the noiseless or low noise case. As these questions still remain, it is hard to evaluate the impact of reducing the scale of width from $O((\eta T)^5)$ to $O((\eta T)^3)$ . 


[1] Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, NeurIPS 2021. 
questions: One potential concern is Assumption 3, which is crucial to control $R_{T}$. The justification for Assumption 3 is not very convincing as $ \| W^* \|  = O(1) $ is a strong requirement as the $ \| W^{*} \| $ is a $ d \times m $-matrix. Can the authors provide more justification for this as this seems central to the analysis, e.g. Theorem 6?
limitations: The limitations are adequately addressed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study excess risk bounds for one hidden-layer neural networks where the last layer is fixed to the initialization and only the first layer is trained by gradient descent. The resulting bounds significantly improve the overparametrization requirements of previous work while preserving the same rates. They achieve this by splitting the excess risk into a generalization part, the optimization part and a left-over part, and controlling each with separate techniques. More precisely, the generalization part is analysed through the notion of on-average stability, and it is here where a more careful control over the smallest Hessian eigenvalue leads to improvements over previous works. The atuhors further show that the optimization can be similarly controlled with weaker overparametrization than previously, showing that under some assumptions they can recover the same results as [1] under smaller widths. The final part is largely controlled by a regularity assumption not made in previous works  Moreover, they extend their results also to the setting of stochastic gradient descent, something which was not possible in previous work. 

[1] *Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, D. Richards and I. Kuzborskij*
strengths_and_weaknesses: **Strengths:**
1. In my opinion the paper pushes several directions that are worth pursuing to improve over current state-of-the-art generalization bounds. First, this work aims to move away from the so-called NTK regime by not relying on the heavy overparametrization usually required in these works, similarly to [1]. This is important since in practice, neural networks have been observed to outperform their kernel counterparts in realistic settings. Second, analyzing stability bounds moves away from the paradigm of uniform convergence and the implied capacity bounds relying on notions such as Rademacher complexities and VC-dimensions. Not relying on uniform convergence may be crucial to achieve non-trivial progress in the field of generalization, as the work [2] has shown. I think it is worth to add that citation to the related works since uniform convergence-based bounds are already discussed.
2. The technical contributions seem highly non-trivial improvements over previous works and the width requirement is strongly reduced without incurring too much loss in terms of the achieved rates, both in noisy and noiseless settings. Moreover, the extension to SGD also seems technically very involved and is something that could not be achieved in [1].   

**Weaknesses:**
1. The role of assumption 3 is not clear to me on several levels. What does it encapsulate on an intuitive level? Mathematically, it is the difference between the optimal regularized the optimal non-regularised generalization loss. The assumption imposes a polynomial upper bound in the regularization parameter lambda. The authors show that this assumption is satisfied if the optimal weights W* have constant (i.e. not growing ) norm, something also not completely obvious. For instance if I think of some image classification task such as MNIST, is assumption 3 met? If yes, with what alpha? This seems tricky to check unfortunately since we need to know the optimal model W^*.  On the other hand, it’s also not obvious how the analysis in this paper profits from assumption 3 which is not present in previous works. Theorem 2 and Theorem 5 don’t seem to explictily need assumption 3 but I guess the optimization part analyzed in this paper is not the same as in [1] and assumption 3 hence implicitly shows up here too? I would find it very helpful if the authors could clarify the role and intuiton of assumption 3 and whether we can gain any numerical insights into it.
2. While the paper is well-written, I think its readibility would greatly benefit from reducing the number of Theorems, Lemmas and Corollaries in the main text (there are 14!). Restricting this to the main results (Generalization gap, Optimization error, excess bound, novel key lemma etc.) would already make the read more enjoyable, without losing too much of the content and story-line. While I appreciate that the main text is extremely precise about all constants, I also think that explicitly writing out the exact width requirements as well as other bounds, hinders readibility as well and makes statements rather cluttered. Listing the main dependencies in big-O fashion in the main text would make it simpler to get an understanding of the terms. The exact forms of the terms could for instance be listed in the appendix.

[1] *Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel, D. Richards and I. Kuzborskij*

[2] *Uniform Convergence May be Unable to Explan Generalization in Deep Learning, Vaishnavh Nagarajan, Zico Kolter*
questions: The NTK is mainly associated with large width but it also strongly relies on small learning rates. How do the learning rates in this work (\eta T \approx n in the noiseless case) compare to the minimal learning rates needed to be in the NTK regime (provided we have a wide enough network), i.e. Theorem 2.1 in [1]? Are we also operating outside of the NTK regime in terms of learning rate size? 

[1] *Wide Networks of Any Depth Evolve as Linear Models Under Gradient Descent, Jaehoon Lee et al.*
limitations: The authors discuss limitations, some more insight into Assumption 3 would be helpful to the reader however.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper focuses on deriving stability-based generalization bound for shallow neural networks. Specifically, the authors improve the previous bounds by relaxing the requirement for the width from (\etaT)^5 to (\eta T)^3, where \eta denotes the step size and T is the training iterate. The key technical difference from the previous works is a more fine-grained estimation of the smallest eigenvalue of the Hessian matrix. The authors also apply their methods to the SGD regimes. 

I think this paper has the potential to be accepted. However, there are still some questions to be answered. 
My major concern falls in comparing this paper's bound with the norm-based generalization bound (uniform convergence).
In Line 194-195, the authors show E\|W_t\| = O(1) in their analysis.
However, this case might be solved by norm-based bound trivially. 
For more details, see the question part. 

strengths_and_weaknesses: Contributions.
1. The authors improve the previous stability-based bound on the shallow neural networks. Specifically, the authors improve the requirements for the width from (\etaT)^5 to (\eta T)^3.
2. The authors also extend their analysis to SGD, which is more challenging. 
3. To reach the bound, the authors provide a more fine-grained analysis of the smallest eigenvalue of the Hessian matrix.
4. This paper is clearly written, and the authors provide many insights. 

Flaws:
As said before, in Line194-195, the authors show that if etaT = O(\sqrt n) and |W^* - W_0| =O(1), we can show that |W_t – W*| = O(1).
The first choice of etaT is used later, and the second condition of |W^* - W_0| is just the special case proposed in Assumption~3. 
Therefore, it seems that $|W_t| = O(1)$ easily holds in practice. 
However, with the bounded norm, one can apply norm-based bounds in uniform convergence without applying stability-based bound.
Therefore, could the authors provide a specific case where $|W_t|$ is not bounded? 

Not important:
The authors need to distinguish between the subscript W_T and W_{1/\eta T}.

questions: As said above, could the authors provide a specific case where we can apply the proposed bound when $|W_t|$ is not bounded?
This may also require another example for Assumption~3.
limitations: No potential negative societal impact.
review_title: null

Meta-review: metareview: The paper studies the generalization of a committee machine using algorithm stability. Compared to previous works, the authors obtain similar generalization error for smaller width for both GD and SGD. Reviewers had some conflicting opinions about this paper, with major concerns on the limited novelty compared to [46] and the small interpretability of the generalization bound beyond NTK results. However they valued the ability to control the bias term in a kernel free manner which was left open in [46] and found the stability analysis interesting and promising. I do therefore recommend acceptance of the paper. 

 

confidence: Less certain
Decision: Accept