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 provides bounds on capacity of composition of noisy function classes. The paper is motivated by the fact that even when two function classes are nicely behaved and have bounded capacity, their composition might not have a bounded capacity. The paper shows that the covering number of the composition of two functions (with bounded range) is well bounded when a small amount of noise is added to the functions. 
strengths_and_weaknesses: Strengths:
1. The paper provides a novel approach to understand generalization when a small amount of noise is added while composing functions.
2. The paper provides multiple results for relating the covering numbers of noisy functions under various distance metrics like TV distance and Wasserstein distance, with those of their 'expected' non-noisy functions.
3. The idea seems intuitive to understand: adding noise will smoothen the output of the first function, thus even if it has sudden changes in its output, that gets smoothed out. This is helpful because function classes with high Lipschitz constant will also have large capacity and consequently bad generalization guarantees.
4. The paper also provides experiments that show that only a small amount of noise is needed for their bounds to be better than existing bounds.


Weaknesses:
1. The biggest problems with most existing bounds seem to be their bad (usually exponential) dependence on the depth of networks. Unfortunately, the result in this paper for deep networks (Theorem 26) also has an exponential dependence. Further, the dependence on width is also exponential here (Theorem 25). In contrast, [1] achieves a polynomial dependence in depth, although their assumptions are different.

[1]: Arora, S., Ge, R., Neyshabur, B. and Zhang, Y., 2018, July. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning (pp. 254-263). PMLR.
questions: Are there connections between the generalization bounds presented here and the certifiable adversarial robustness using randomized / gaussian smoothing [2]?

[2]: Cohen, J., Rosenfeld, E. and Kolter, Z., 2019, May. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning (pp. 1310-1320). PMLR.
limitations: See the weakness section.
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: This submission proposes a new measure of the capacity (i.e., uniform covering number) of composite classes. The motivation starts from examples where each function class has bounded capacity but the composition does not (Proposition 8,9). Due to some ill-defined capacity measures for the composition class, this paper proposes a new capacity measure defined on randomized function classes. Due to imposed randomness in the function class, TV or Wasserstein distance metrics are used to measure the distance between functions. This uniform covering number on randomized function classes has a nice property that the capacity of composite class is bounded by the covering numbers of two sub classes. Authors demonstrate the boundedness of the proposed measure for neural network function classes, and connect it to the generalization bound of deep neural networks.
strengths_and_weaknesses: This paper seems to propose a new and important concept for measuring a capacity of composite class. This could be useful for giving a generalization bound for neural-network function classes with e.g., bounded activations. I have a few concerns:

- It would have been nicer if the authors could also give an explicit example of non-Lipschitz activation functions. 

- Proposition 8 is a nice example for motivating the study.  But is this a right example to use? since I wondered if this example could be addressed with the newly proposed measure to show how we can benefit from it.

- Theorem 17 seems to convert the bound on a randomized class to the original function class, but requires boundedness of the output. I wonder if there are functions of interest with bounded capacity and bounded output values, but their composition does not have bounded capacity (in the example used in Proposition 8, h is unbounded). 

Overall, I think the paper is well-written with clear messages. Most of research questions that can arise from the proposed concepts seem to be addressed. 
questions: 
- As mentioned in the paper, the proposed measure cannot work with ReLU since it is not bounded. Could you clarify if there are other works that does not have an issue with ReLU activation / and if so, in which scenario does the proposed measure work better than such benchmarks? 
limitations: I am happy that authors are upfront with their limitations. I do not see any negative societal impact.
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 analyzes the uniform covering number of Gaussian Noisy Neural network. It provide a generalized framework to calculate the covering number and also a metric to compare difference generalization metric. 
strengths_and_weaknesses: Strengths: 
Originality: The originality of this paper mostly comes from the new generalized mathematical framework of covering number.  Adding noise to neural nets has been studied in existing literature, but its covering number result is original.
Quality: I am not an expert in PAC learning theory but I briefly checked the proof, it looks sound to my best knowledge. 
Clarity: As a math-heavy paper, this paper overall is very clear.
Significance: The generalized covering number analysis does help us understand the effect of noise in deep learning.

Weakness: My major concern is the existing framework only works for bounded activation function. This limits the applicability  of the proposed theory.
questions: 1. In the definition of extended metrics, why does L2-extended metrics require a normalization?
2. Adding noise leads to a bounded covering number, but at the same time a small capacity? Does that heart the performance of Noisy neural networks. 
3. In section 7, what is the intuition of separate the first layer from others? What is the difference of analyzing the first layer and analyzing a single layer neural networks. 
4. The paper can talk more on the insight from the bounded covering number. For example, can it explain why adding noise to neural nets can help reduce overfitting?
5. There are some more related literature on noisy neural networks and noisy activation function, e.g., Gulcehre et al., 2016. 
limitations: 1. The current analysis can only be applied on bounded activation function, such as sigmoid, softmax, tanh.
review_title: null

Meta-review: metareview: The paper present a neat idea how to use noise in order to control the capacity of composite classes
confidence: Certain
Decision: Accept