Venue: NeurIPS 2022 Conference

Reviews:

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 presents various upper bounds (Rademacher complexity based) and lower bounds (fat shattering dimension based) on single hidden layer neural networks. These bounds shed light on the question whether the bounded spectral norm of the weight matrix is sufficient for having width independent uniform convergence guarantees. Moreover, there are similar discussions for Frobenius norms and input dimension dependence. The paper considers both generic and convolutional neural networks. 

Contributions of the paper are summarized in 8 theorems:

* Theorem 1 shows that the fat shattering dimension is scaled with the network width for nonsmooth activation function, if only the spectral norm is bounded. 
* Theorem 2 generalizes Golowich et al 2018 and Neyshabur et al 2015 to show that Frobenius norm bound is sufficient to bound the sample complexity for Lipschitz activation functions (width independent bound) using Rademachar complexity analysis.
* Theorem 3 shows that the fat shattering dimension for Frobenius norm bounded networks is input dimension dependent (for smaller input dimensions).  
* Theorem 4 shows that the spectral norm is sufficient to bound the sample complexity for polynomial activation functions. 
* Theorem 5 extends the result to the multilayer case for polynomial activation functions of type $z^k$. Lemma 4 and 5 are crucial for the proof of Theorem 4 and 5.
* Theorem 6 shows that the spectral norm is sufficient for convolutional networks with linear last layer.
* Theorem 7 shows that Rademacher complexity bound for convolutional networks with pooling  has logarithmic dependence on width.
* Theorem 8 shows, using fat shattering dimension, that the logarithmic width dependence is unavoidable. 

strengths_and_weaknesses: **Strengths:**

From technical perspective, the paper provides a valuable contribution by clear exposition of the role of spectral and Frobenius norm in uniform convergence results. 
The paper is well written. Given the sheer volume of works on explaining generalization error for neural networks, the authors do a good job connecting the results to the existing works for instance in Remark 2 on Bubeck et al 2021 or Remark 3 on implicit regularization. The paper contains many theoretical results of interest, combines many ideas from previous works and provide new proof techniques notably Theorem 4 and 5 (to the best of my knowledge). The proofs are well presented and are sound. Overall, this is a great paper and I enjoyed reading it.

**Weaknesses:**

* Although this might seem like a gratuitous comment and request, I think having numerical support, even a toy example, can be good to support the theory. 
* I have some concerns about O_\Phi term in Theorem 4 (see below).
* I feel that the authors do not adequately comment about implications of the current result for a general theory of generalization for deep learning. Covering all existing works are of course not possible, however, works like Nagarajan et al 2019, or Zhang et al ICLR 2017 are widely discussed. It is at least expected that the authors clarify in which regime their bounds are applicable and do not suffer from examples of those papers. 

questions: * Regarding Theorem 1: Anthony and Bartlett 1999 also provide an expression of fat shattering dimension although with slightly different assumptions (Theorem 14.18) and limitations. For example, the bound is input dimension dependent, the class of activation functions is different, etc. It would be good to add a discussion regarding this to the related works.
* Regarding Theorem 2: the proof, like Theorem 5 of Golowich et al, seems to be based on McDiarmid’s lemma and not relying on Dudley’s integral, which is also used to bound the Rademacher complexity using covering numbers. Is there any reason behind why Dudley’s integral is not used? Does it provide worse result if applied to this context with Lipschitz activation function? This can be an interesting theoretical insight and valuable to add.
* Theorem 4 and 5 prove that for polynomial activation functions, the spectral norm bound is sufficient for uniform convergence bound. However, the question remains if the lower bound, based on fat shattering dimension, can be further improved for these activation functions. A comment on this point can be a good add to the paper, if it is straightforward.
* The authors mention that they build on Ledent et al 2021 for Theorem 7. However, it is not currently clear, neither in the main paper nor in A.8,  what is the main difference between Ledent et al 2021. The difference in the respective proofs and bounds should be specified.
* If $[M]_{+}$ is the ReLU applied on $+/- 1/\sqrt{n}$, I cannot see why it “is just the constant matrix with value $1/\sqrt{n}$ at each entry” (page 5). It will be a combination of 0 and $1/\sqrt{n}$.
* I felt that Remark 4 is a bit confusing, although I got the point: namely, the presence of d in the lower bound does not contradict Theorem 2, since it assumes that “the above expression” is bigger than cd (according to the theorem) meaning that $(bBb_x/\epsilon)\sqrt{d}$ is bigger than $cd$, and therefore, d is smaller than $(bBb_x/\epsilon)^2$. I think this remark can be re-written. I suggest adding equation and theorem labels and refer to them explicitly instead of using demonstratives.
* The authors mention that “when the network employs weight-sharing”, it is possible to get width independent bound (actually logarithmic dependence for CNNs with pooling). This is not fully precise. The term $O_\Phi$ hides the dependence on kernel size. Consider a discrete circular convolution for which the matrix $W$ is a circulant matrix. In this case, $O_\Phi = n$. Even for a vanilla convolutional kernel, $O_\Phi$ is equal to the kernel size, which is a more intuitive notion of width for convolutional networks. This is clear at the end of A.7 right above A.8 where two summations range over m and n inside the square root.
* How do the current results change (or not) if one introduces a margin-based loss? For classification tasks, if one disregards the margin, it is possible to rescale the last layer without changing the classification accuracy, which would mean arbitrarily changing the product of spectral norm. Many previous works, e.g., Bartlett et al 2017, consider margin-based bounds. Why is this not considered in this work?

limitations: As mentioned by the authors themselves, there is a debate whether uniform convergence can explain generalization in neural networks mainly supported by some carefully designed experiments. It is not clear how one should understand the bounds of this paper in light of papers like Nagarajan et al 2019.
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: This paper studies the norm-based uniform convergence bounds for two-layer neural networks. Their results give a tight understanding of spectral-norm-based uniform convergence. In particular, they proved that spectral norm is not sufficient for general settings to get a uniform convergence result. However, for NNs with certain smoothness conditions or some convolution structures, the spectral norm is sufficient. 
strengths_and_weaknesses: Overall, this paper is well-written and clear. The authors show that, in general, bounding the spectral norm cannot lead to size-independent guarantees. This negative result is quite interesting and insightful. However, I have a concern about the significance of the results. Since the size of the parameters is known through the training, it seems unnecessary to get a size-independent guarantee. Moreover, the spectral-norm-based convergence result seems hard to apply both empirically and theoretically, which may limit the application of the convergence result. 
questions: The uniform convergence guarantees derived in Sections 4 and 5 are size-independent. I wonder whether they also work for infinite width neural networks such as mean-field settings?
limitations: The authors have addressed their work's limitations and potential negative social impact.
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: Based on bounded norms of the weight matrices, the authors investigated the upper and lower bound sample complexity for neural networks with one hidden layer in this research.  They demonstrated that in contrast to bounding the Frobenius norm, however, bounding the spectral norm generally cannot result in size-independent guarantees - although it is not surprising that the spectral norm is insufficient to get width-independent sample complexity bound -  the paper and its theoretical analysis are very important. 


The constructions did, however, highlight two situations in which the lower bounds can be avoided and a spectral norm control is sufficient to provide width-independent guarantees. The first scenario is when the activations are sufficiently smooth, and the second is in certain situations involving convolutional networks. 

In general, this is a very important paper as deep neural networks still lack a very basic understanding of their behavior.
strengths_and_weaknesses: Strengths:

1. A very solid theoretical paper - the theorems and proofs are exciting.
2. The paper deals with very important and required questions in the field of deep learning, not many papers focus on the theoretical side of deep learning - I find this paper a very important step towards better understanding DNNs. 

Weaknesses:
Although it is clear that the paper is a theoretical paper, however, I have the following minor comment. The writing could still be improved, giving some intuitive explanation and details as to what and why each theorem holds and what each theorem mean -- it took some time to understand the theorems and the details. 
questions: Some definitions are missing. What is the definition of a Lipschitz function in your work? Is it the standard definition, (intuitively) a continuous function that is limited in how fast it can change?

Can you give more examples of other used Lipschitz functions?

Is σ(0) = 0, necessary in all the theorems, or it can be avoided (used for simplicity)? 




limitations: some simple numerical experimentss would help justify the theory.
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: This paper studies the sample complexity of simple neural network model classes. The focus is on upper and lower bounds under various norm constraints on the network coefficients. It is shown that a spectral norm constraint is not sufficient to obtain bounds that are independent of the network width. To prove this, the authors estimate the fat shattering dimension of the considered hypothesis class. The surprising aspect of this result is that it does not hold if the activation is the identity but crucially depends on the nonlinearity. As a second contribution the authors show that a Frobenius norm constraint yields hypothesis classes whose sample complexity is independent of the network width. Finally, the authors identify two interesting settings where a spectral norm constraint is sufficient for getting bounds independent of the width. 
strengths_and_weaknesses: I think that this is an interesting paper, well written, and adding to the current body of knowledge on understanding the generalization behaviour of deep learning algorithms. 

In terms of originality I am not sure if the paper introduces new proof techniques; maybe they can elaborate the novelty of their technical and mathematical contributions a bit more? 
questions: I would like to ask the authors to comment more on the novelty of their proof techniques. 
limitations: This has been adequately addressed
review_title: null

Meta-review: metareview: The paper proves a novel, tighter bound norm-based bound for the generalization error of two-layer networks. All the reviewers agree that this is an important theoretical result and should be accepted.
confidence: Certain
Decision: Accept