Benefits of Additive Noise in Composing Classes with Bounded Capacity
Authors: Alireza Fathollah Pour
Hassan Ashtiani
Venue: NeurIPS 2022 Accept (2022)
Keywords: Generalization Bound
Composition
Noise
Covering Number
Neural Networks

Abstract: We observe that given two (compatible) classes of functions $\mathcal{F}$ and $\mathcal{H}$ with small capacity as measured by their uniform covering numbers, the capacity of the composition class $\mathcal{H} \circ \mathcal{F}$ can become prohibitively large or even unbounded. We then show that adding a small amount of Gaussian noise to the output of $\mathcal{F}$ before composing it with $\mathcal{H}$ can effectively control the capacity of $\mathcal{H} \circ \mathcal{F}$, offering a general recipe for modular design. To prove our results, we define new notions of uniform covering number of random functions with respect to the total variation and Wasserstein distances. We instantiate our results for the case of multi-layer sigmoid neural networks. Preliminary empirical results on MNIST dataset indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible (i.e., element-wise i.i.d. Gaussian noise with standard deviation $10^{-240}$)

Benefits of Additive Noise in Composing Classes with Bounded Capacity
Alireza Fathollah Pour Department of Computing and Software
Hassan Ashtiani Department of Computing and Software McMaster University zokaei ammmmmastr..
McMaster University
fathola@mccmsseer..
Abstract
We observe that given two (compatible) classes of functions. F and H. with small capacity as measured by their uniform covering numbers, the capacity of the composition class 7 a F can become prohibitively large even unbounded. We then show that adding small amount Gaussian noise to the output of before composing it with H can effectively control the capacity of H. F, offering a general recipe for modular design. To prove our results, we define new notions uniform covering number of random functions with respect to the total variation and Wasserstein distances. We instantiate our results for the case of multi-layer sigmoid neural networks. Preliminary empirical results on MNIST dataset indicate that the amount of noise required to improve over existing uniform bounds can be numerically negligible (i.e., element-wise i.i.d. Gaussian noise with standard deviation 10 240
Introduction
Let F be class of functions from A' to y, and H. class of functions from y to Z. Assuming that F and H have bounded "capacity", can we bound the capacity of their composition, i.e., H F {h e f F, H.? Here, by capacity we mean learning-theoree as VC dimension, fat-shattering dimension, and (uniform) covering numbers associated with these classes (see Vapnik (1999); Anthony et al. (1999) (Shalev-Shwane and Ben-David 2014); Mohri et al. (008) for an introduction.. Being able to control the capacity composition of function classes useful, as it offers modular approach algorithms) out of simpler ones. To be concrete, we want to know the uniform covering number (as defined in the next section) of H F can be "effectively" bounded function of the uniform covering numbers of F and H.
quantities such
design sophisticated classes (and therefore learning
The answer to the above questions is true when F is set of binary valued functions (i.e., y {0. 1} the above). More generally, the capacity of the composition class (as measured by the uniform covering number) can be bounded long as | is relatively small (see Proposition 7. But what if ) an infinite set, such as the natural case of y = [o, 1]? Unfortunately. in this case the capacity of H F (as measured by the covering number) can become unbounded (or excessively large) even when both J and H have bounded (or small) capacities; see Propositions S and
Given the above observation, we ask whether there is a general and systematic way to control the capacity of the composition of bounded-capacity classes. More specifically, we are interested in the case where the domain sets are multi- nulti-dimmeniionl real-valued vectors (e.g., X' C Rd. C R", Z C RR). The canonical examples of such classes are those associated with neural networks.
For the full version of this paper see Pour and Ashtiani 2022).
"The source codes are available at
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A common approach to control the capacity of H. o F is assuming that H. and F have bounded capacity and H. consists of Lipschitz functions (with respect to appropriate metries). Then the capacity of H o FF can be bounded as long as H has small "global cover" (see Remark 13). This observation has been used to bound the capacity of neural networks in terms of the magnitude of their weights (Bartlett 1996). More generally, the capacity of neural networks that admit Lipschitz continuity can be bounded based on their group norms and spectral norms (Neyshabur et al. 2015 Bartlett et al. 2017 Golowich et al. 2018). One benefit of this approach is that the composition of Lipschitz classes is still Lipschitz (although with a larger Lipschitz constant).
While building classes of functions from composition of Lipschitz classes is useful, it does not necessarily work as a general recipe. In fact, some commonly used classes of functions do not admit a small Lipschitz constant. Consider the class of single-layer neural networks defined over bounded input domain | B, B] and with the sigmoid activation function. While the sigmoid activation function itself is Lipschitz, the Lipschitz constant of the network depends on the magnitude of the weights. Indeed, we empirically observe that this can turn Lipschitzness based bounds on the covering number of neural networks worse than classic VC-based bounds.
Another limitation of using Lipschitz classes is that they cannot be easily "mixed and matched" with other (bounded-capacity) classes. For example, suppose F is a class of L-Lipschitz functions (e.g.. multi-layer sigmoid neural networks with many weights but small magnitudes). Also, assume H is non-Lipschitz class with bounded uniform covering number (e.g., one layer sigmoid neural network with unbounded weights). Then although both F and H. have bounded capacity, H. F is not Lipschitz and its capacity cannot be generally controlled.
We take different approach for composing classes of functions. A key observation that make and utilize is that adding a little bit of noise while "gluing" two classes can help in controlling the capacity of their composition. In order prove such results, we define and study uniform covering numbers of random functions with respect to total variation and Wasserstein metrics. The bounds for composition then come naturally through the use of data processing inequality for the total variation distance metric.
Contributions and Organization.
Section provides the necessary notations and includes the observations that composing real-valued functions can be more challenging than binary valued functions (Propositions) 2nd
In Section 4 we define a new notion of covering number for random functions (Definition [0) with respect to total variation (TV) and Wasserstein distances.
The bulk of our technical results appear in Section 5 These include composition result for random classes with respect to the TV distance (Lemma [8] that is based on the data processing inequality. We also show how one can translate TV covering numbers to conventional ||-1|2 counterparts (Theorem 17) and vice versa (Corollary 21p. A useful tool Theorem 20 which exploits kernel density estimation techniques to translate Wasserstein
covers to covers when we add Gaussian noise to the output of functions.
Section provides a stronger type of covering number for classes of single-layer noisy neural networks with the sigmoid activation function (Theorem 25
In Section 7 on the ||-1|2 covering number of noisy deep neural networks (Theorem 26
the tools developed in the previous sections and prove novel bound
In Section g we define NVAC, a metric for comparing generalization bounds (Definition 28 based on the number of samples required to make the bound non-vacuous.
We offer some preliminary experiments, comparing various generalization bounds in Sec- tion 9 We observe that even negligible amount of Gaussian noise can improve NVAC over other approaches without affecting the accuracy of the model on train or test data.
2 Related work
Adding various types of noise have been empirically shown to be beneficial in training neural networks. In dropout noise (Srivastava et al., 2014) (and its variants such DropConnect (Wan et al.

---

2013)) the output of some of the activation functions (or weights) are randomly set to zero. These approaches are thought to act as regularizer. Another example is Denoising AutoEncoders (Vincent
et al. 2008) which adds noise to the input of the network while training stacked autoencoders.
There has been efforts on studying the theory behind the effects of noise in neural networks, Tim et al. (196) study the effects of different types of additive and multiplicative noise on convergence speed and generalization of recurrent neural networks (RNN) and suggest that noise can help to speed up the convergence on local minima surfaces. [im et al. (02TT) formalize the regularization effects of noise in RNNs and show that noisy RNNs are more stable and robust to input perturbations. Wang et al. (2019) and Gao and Zhou (016) analyze the networks with dropout noise and find bounds on Rademacher complexities that are dependent on the product of norms and dropout probability. It is noteworthy that our techniques and results are quite different, and require a negligible amount of additive noise to work, while existing bounds for dropout improve over conventional bounds only the amount of noise is substantial. Studying dropout noise with the tools developed in this paper is direction for future research.
Studying PAC learning and its sample complexity is by now a mature field; see Vapnik (1999);
;
Shalev-Shwartz and Ben-David (2014); Mohri al. (2018). In the case of neural networks, standard
Sennik-Chervonekii based complexity bounds have been established (Baum and Haussler] | 1988
Maass 1994, Goldberg and Jerrum 1995 Vidyasagar 1997 Sontag et al.] [9988 Koiran and Sontag
1998; Bartlett et al. [998] Bartlett and Maass| 2003] Bartlett et al.) 2019). These offer generalization
bounds that depend on the number of parameters of the neural network. There is also another line
of work that aims to prove a generalization bound that mainly depends on the norms of the weights and Lipschitz continuity properties of the network rather than the number of parameters (Bartlett
1996; Anthony et al. 1999; Zhang 2002; |Bartltti 1996 Neyshabur et al. 2015 Bartlett et al. 2017
Neyshabur et al. 20188 Golowich et al. 2018 Arora et al.] 2018]] Nagarajan jan and Kolter 2018: Long
and Sedghi 2020). We provide more detailed discussion of some of these results in Appendix H
Finally, we refer the reader to Anthony et al. (1999) for an introductory discussion on this subject.
The Above-mentioons Dziugaite and Roy (2017) (and later Zhou et al. (2119)) show how to achieve a non-vacuour bound using the PAC Bayesian framework. These approaches as well as compression- sepeeessioo-bbsedd methods (Arora et al. 2018) are, however, examples of "two-step" methods; see Appendix [o] more details. has been argued that uniform convergence theory may not fully explain the performance of neural networks (Zhang et al. 2021 Nagarajan and Kolter, 2019). One conjecture is that implicit bias of gradient descent (Gunasekar et al. 2017 Arora et al. 2019; Ji et al.
bounds are usually vacuous for commonly used data sets and architectures.
2020 Chizat and Bach, 2020 Ji
and Telgarsky| 202 can lead to benign overfitting (Belkin et al. 2018 2019 Bartlett et al. 2020); see Bartlett et al. (2021) for recent overview.
In a recent line of work, generalization has been studied from the perspective of information the- ory (Russo and Zou 2016; Xu and Raginsky 2017 Russo and Zou| 2019, Steinke and Zakynthinou 2020). showing that a learning algorithm will generalize if the (conditional) mutual information be- tween the training sample and the learned model is small. Utilizing these results, a number of generic generalization bounds have been proved for Stochastic Gradient Langevin Descent (SGLD) (Raginsky
et al. 2017] Haghifam et al. (020) as well as Stochastic Gradient Descent (SGD) Neu et al. (2021). Somewhat related to our "noise analysis", these approaches (virtually) add noise to the parameters to control the mutual information. In contrast, we add noise between modules for composition (e.g., in between layers of neural network). Furthermore, we prove uniform (covering number) bounds while these approaches are for generic SGD/SGLD and are mostly agnostic to the structure of the hypothesis class. Investigating the connections between our analysis and information-theoree techniques is direction for future research.
3 Notations and background
Notation. X' C Rdd and y C IR denote two (domain) sets. For x E X, let ||x||1,, |||||2 and || denote the é1, f2, and for norm of the vector z, respectively. We denote the cardinality of set by [S]. The set of natural numbers smaller or equal to m are denoted by [mm] A hypothesis is Borel function/ f Rdd + Rº, and a hypothesis class F is a set of hypotheses.
We also define the random counterparts of the above definitions and use an overline to distinguish them from the non non-random versions. X denotes the set of all random variables defined over X' that
3

---

admit a generalized density function We sometimes abuse the notation and write T E N' rather than I E X (e.g., J E IR is a random variable taking values in TR.). By π = f() we denote a random variable that is the result of mapping E using Borel function f R + RP. We use f IR + R to indicate that the mapping itself can be random. We use F to signal that the class can include random hypotheses. We conflate the notation for random hypotheses so that they can be applied to both random and non-random inputs (e.g.. f(z) and f(x))
Definition 1 (Composition of two hypothesis classes). We denote by h o f the function h(f(z))
(assuming the range of I and the domain of h are compatible). The composition of two hypothesis classes and H is defined by H F = (h o f h E H. E F). Composition of classes of random hypotheses defined similarly by H o = ( o J 1he H. Fe..
The following singleton class Go will be used to create noisy functions (e.g., using Go F). Definition 2 (The Gaussian Noise Class), The d-dimensional noise class with scale a is denoted by Ga.d = {. H Here, 9a,d Rd + R. is a random function defined by (o,a(r) = x + 2, where I ~ NO, o² Ia). When it is clear from the context we drop d and write Go {.r)
In the rest of this section, we define the standard notion of uniform covering numbers for hypothesis classes. Intuitively, classes with larger uniform covering numbers have more capacity/flexibiitty, and therefore require more samples to be learned.
Definition (Covering number). Let (X, p) be a metric space. We say that a set A C X e-covered by set C S A with respect to p. for all E A there exists E C such that pla. c) S c. The cardinality of the smallest set C that e-covers A is denoted by Níe, A, p) and it is referred to as the e-covering number of A with respect to metric p.
Definition (Extended metrics). Let (X.p) be metric space. Let u = (a.,..., "l)....,,m): (bi,..., bm) E xm for m E N. The co-extended and lz-extended metrics over x are defined by pos," (u, v) supisism p(oz, bi) and paa." (u,
am) V
/ th E b,)) respectively. We drop
m and use p p²² if it is clear from the context.
Remark 5. The extended metrics are used in Definition Soniitiioonnnna and capture the distance of two hypotheses on an imput sample of size m. A typical example of p is the Euclidean distance over R", for which the extended metrics are denoted by 11-112. and 11-112..m Unlike oc-extended metric, the le-extended metric is normalized by 1/vmm, and therefore we have p'2."
S p000. (u. v) for all U. E xm". Definition 6 (Uniform covering number). Let p)) be a metric space and F a hypothesis class of functions from X to Y. For a set of inputs S = {I1, I2...., C X. we define the restriction of F to S as Fis (((()), f(22)..... ((Im)))),......) numbers of hypothesis class F with respect to metrics ppe ppa are denoted by Nu ()) and (e, m. p²a) and are the maximum values of Fis. and N N(,, Fis, p'a.") over all S C X with SS = m, respectively.
=fe EEFF F} ymm The uniform e-covering
It is well-known that the Rademacher complexity and therefore the generalization gap of class can be bounded based on logarithm of the uniform covering number. For sake of brevity, we defer those results to Appendix [F] Therefore, our main object of interest is bounding (logarithm of) the uniform covering number. The following propositions show that there is a stark difference between classes of functions with finite range versus continuous valued functions when comes to bounding the uniform covering number of composite classes; the proofs can be found in Appendix B
Proposition 7. Let y be a finite domain (D) = k)) and ply, 9) 1[y + 9} be a metric over Y. For any class F of functions from X to y and any class H of functions from y to R. we have
(e H a F, m, (1-1(2) < Ni,Nur(e, H. mNN1 11-112)) where N = Nrr(0.5, (0,,,F,,,,,.. )²²) Proposition 8. Let F = (x) = wx | w E (0, 1), x E (0, be a class of functions and H (l(yy) 1/y 1 y E (0,1)} be a singleton class. Then, Ne, F,m, 11-12) S [2/e2] and (o, H. m. 11-1(-) = 1, but Nu (c. H o F, m. 11-11(2) is unbounded.
Proposition 9. For every 6 > 5' > 0, there exist hypothesis classes F and H. such that for every m we have Nu H. m, 11-112)) m + and (e, m. 11-1 = yet No HoJ, m, 11-1189) ' 2mm
'Both discrete (by using Dirac delta function) and absolutely continuous random variables admit generalized density function.
Technically, we consider 7(x) to be J(0z). where on is a random variable with Dirac delta measure on
4

---

Covering random hypotheses
We want establish the benefits adding little bit of) noise when composing hypothesis classes. Therefore, we need to analyze classes of random hypotheses. One way to do this is to replace each hypothesis with its expectation, creating a deterministic version of the hypothesis class, Unfortunately, this approach misses the whole point of having noisy hypotheses (and their benefits in composition). Instead, we extend the definition of uniform covering numbers to classes of random hypotheses F. The following basically the random counterpart of Definition 6
Definition 10 (Uniform covering number for classes of random hypotheses). Let (Y, p) be metric For a set of random variables S
space and F class of random hypotheses from X
P2.. Jmm) S X, define the restriction of F to S as F F(z)) ..... f(mm))
I FEFI CY" Let S X. The uniform e-covering numbers of F with respect I and metrics p and p²a are defined by
Nu(c,F, m. (n, ,r)= sup Sgr,|s|=m
N(c, F
[3 p..p)..))
Mu,e,F,m,p ,1,, sup sgr,|s|=m.
N(e,FF (.. m)..m)
Remark 11. Unlike in Definition 6 where is usually the I1-1l2 metric in the Euclidean space, here in Definition p is defined over random variables. More specifically, we will use the Total Variation and Wasserstein metrics concrete choices for p. Remark 12. The specific choices that we use for I are
T= X= the set of all random variables defined over Fd that admit generalized density function.
the set of all random variables defined over [-B, B)a that admit a generalized density function.
T A = 16 x E Rd and = (6g E B) where dn is the random variable associated with Dirac delta measure on
r T= XB. (z) x E XB,a): : all members of XB,d after being "smoothed" by adding (convolving with) Gaussian noise.
Remark 13. Some hypothesis classes that work with have "global" covers, in the sense that the uniform covering number does not depend on m. We therefore use the following notation
00, r)
lim (u, m. p=0; I).
m-+0c
We now define Total Variation (TV) and Wasserstein metrics over probability measures rather than random variables, but with slight abuse of notation will use them for random variables too.
Definition 14 (Total Variation Distance). Let and v denote two probability measures over X' and let Q be the Borel sigma- algebra over X. The TV distance between μ and v defined by
dTv(H,, = sup (n( v v(B).
Bell
Furthermore, if and v have densities f and g then
/ (((a)-g(z))daa) = x [f(x)) - ((x)و de -115- gll1-
drv(u.v) v) sup
BER
Definition 15 (Wasserstein Distance). Let μ and u denote two probability measures over X, and M(p v) be the set of all their couplings. The Wasserstein distance between μ and is defined by
dw v)
inf (TET((P))) xxxx
|| v112d7(2x,
The following proposition makes explicit that the conventional uniform covering number with respect to ||-1|2 (Definition 6 can be regarded as special case of Definition I0
5

---

Proposition 16. Let F. be a class of (deterministic) hypotheses from R to R.. Then
No(e, F, d m, Az). The proposition is the direct consequence of the D once we note that the Wasserstein distance between Dirac random variables is just their Eg distance, i.e., dw 5y) = || yl12.
(u,e,,F m, 11-11-) = (c, dw, m, Ad) and
5 Bounding the uniform covering number
This section provides tools that can be used in a general recipe for bounding the uniform covering number. The ultimate goal is to bound the (conventional) I1-112 and I1-112= uniform covering numbers for (noisy) compositions of hypothesis classes. In order to achieve this, we will show how one can turn TV covers into ||-1|2 covers (Theorem (7) and vice versa (Corollary 21). But what is the point of going back and forth between I1-I|2 and TV covers? Basically, the data processing inequality ensures an effective composition (Lemma [8) for TV covers. Our analysis goes through a number of steps, connecting covering numbers with respect to ||-1|2. Wasserstein, and TV distances. The missing
proof' of this section can be found in Appendix
The following theorem considers the deterministic class H. associated with expectations of random hypotheses from F, and shows that bounding the uniform covering number of JF with respect to TV distance is enough for bounding the uniform covering number of H with respect to l|-I12 distance.
Theorem 17 (From TV cover to a ll-I12 cover). Consider any class F of random hypotheses f:R IR B- BJ with bounded output. Define the (nonrandom) hypothesis class H {h: B - [-B, B|P h(x) = 7 [[x)]] . E F.. Then for every >> 0, m E N these two inequalities hold: (2 H, m, 11-111) S No, m. dvv Ad) S Ne F, m. dv, Xa); (u H, m. 11-112) S Nu,,,, m. di Aa) S Nu m, dec m, d.. X.).
But what is the point of working with the TV distance? An important ingredient of our analysis is the use of data processing inequality which holds for the TV distance (see Lemma 3T). The following lemma uses this fact, and shows how one can compose classes with bounded TV covers.
Lemma 18 (Composing classes with bounded TV covers). Let F be a class of random hypotheses from &&d to R2, and H be a class of random hypotheses from TRP to RV, For every e, e > 0, and every m E N these three inequalities hold:
Nu (c + é, H o F, m. div Xa) S Nu (c', H. MN1, dfy, .Ni,
Nu 6', H F, m. di Da) S Nu (e', H. mN2 xp) (p) .N2,
Nu (e+t', H o F, m d Aa) < Nu (é,,H, MN, diy. Xp) .N3.
where N1 = Nu (c, F. m, diy. Xd), N₂
NN (c,F F,F.m.ai dl.. Da) and Ng.
Nu (e,F,m, m, m,F.
Remark 19. In Lemma 18 for H. we required the stronger notion of cover with respect to Xa (i.e., the input to the hypotheses can be any random variable with a density function), whereas for F. cover with respect Da sufficed in some cases. As we will see below, finding cover with respect to Aa is easier since one can reuse conventional |1.1|2 covers. However, finding covers with respect to Xa is more challenging. In the next section we show how to do this for a class of neural networks.
The next step is bounding the uniform covering number with respect to the TV distance (TV covering number for short). It will be useful to be able to bound TV covering number with Wasserstein covering number. However, this is generally impossible since closeness in Wasserstein distance does not imply closeness in TV distance. Yet. the following theorem establishes that one can bound the TV covering number as long as some Gaussian noise is added to the output of the hypotheses.
Theorem 20 (From Wasserstein cover to TV cover). Let F be class of random hypotheses from Rdd to RP, and Gop be a Gaussian noise class. Then for every e > 0 and m E N we have
Nu
Gop o F, m, mF, dFy Xa) < Nulc,, F. d Xa),
20
No
Io. o F. m. d... Ad) s Nu, m. diy Da).
20

---

Intuitively, the Gaussian noise smooths out densities of random variables that are associated with applying transformation in F to random variables in X or Ag- As a result, the proof of Theorem 20 has step on relating the Wasserstein distance between two smoothed (by adding random Gaussian noise) densities to their total variation distance (see Lemma 35 in Appendix O Finally, we can use Proposition to relate the Wasserstein covering number with the ||-I12 covering number. The following corollary is the result of Proposition 16 and Theorem 20 that stated for both dii and diy extended metrics.
Corollary 21 (From a l1-112 cover to a TV cover). Let F be a class of hypotheses f RR + RP and go.g be Gaussian noise class. Then for every e > 0 and m E N we have
NU (5 2 Inp F, m, div, Da) S Nu F,m, 11:12)); 2n
Nul b. gop o m, dvv A S Nu m, 11-11-))
The following theorem shows that we can get a stronger notion of TV cover with respect to Xn, from |1-1|2 global cover, given that some Gaussian noise is added the output of hypotheses.
Theorem 22 (From a global [l-1|2 cover to a global TV cover). Let F be a class of hypotheses f: IR R2 and go be a Gaussian noise class. Then for every e and m N we have
Nu 20 Iap o F, 00, div. XB.) S NN, 00, 11-11
The proof involves finding a Wasserstein covering number and using Theorem 20 to obtain TV covering number.
6 Uniform TV covers for single-layer neural networks
In this section, we study the uniform covering number of single-layer neural networks with respect to the total variation distance. This will set the stage for the next section, where want the tools from Section to bound covering numbers of deeper networks. We start with the following definition for the class of single-layer neural networks.
Definition 23 (Single-Layer Sigmoid Neural Networks). Let RP - [0,1] be the element- wise sigmoid activation function defined by ((x(1),..., = ( ".ai))))..,,.0. ((x(())),, )), where <(x) = Ite-z is the sigmoid function. The class of single-layer neural networks with d inputs and p
outputs is defined by NET[d, p] [sw R - 1|2 fw(x)= = D(W x), W E Rdxp).
Remark 24. We choose sigmoid function for simplicity, but our analysis for finding uniform covering
numbers of neural networks (Theorem 25 is not specific the sigmoid activation function. We
present a stronger version of Theorem 25 in Appendix D which works for any activation function that Lipschitz, monotone, and bounded.
As mentioned in Remark 19 Lemma X₂ and TV distance. In fact, the size of this kind of cover is infinite for deterministic neural networks defined above. In contrast, Theorem 25 shows that one can bound this covering number as long as some Gaussian noise is added to the input and output of the network. The proof is quite technical, starting with estimating the smoothed input distribution (To (z)) with mixtures of Gaussians using kernel density estimation (see Lemma [58 in Appendix J) Then a cover for mixtures of Gaussians with respect to Wasserstein distance is found. Finally, Theorem hh to find the cover with respect to total variation distance. For a complete proof of theorem see Appendix [
18 requires stronger notion of covering numbers with respect to
Theorem 25 (A global total variation cover for noisy neural networks with unbounded weights). For every p, d E N.e > 0, a 5d/e we have
30 6/2 /In (1nd(cccc) co)/(eE))
5d
p(d+1)
(e Go NET xc, di Go XiA) S
In
22/002
co
Note that the dependence of the bound on 1/a polynomial. he assumption a < 5d/e holds for any reasonable application (we will use < 1 in the experiments). In contrast to the analyses that exploit Lipschitz continuity, the above theorem does not require any assumptions on the norms of weights. Theorem 25 is key tool in analyzing the uniform covering number of deeper networks.
7

---

7 Uniform covering numbers for deeper networks
In the following, we discuss how can use Theorem 25 and techniques provided in Section 5 to obtain bounds on covering number for deeper networks. For a T-layer neural network, it is useful to separate the first layer from the rest of the network. The following theorem offers bound the uniform covering number of (the expectation of) noisy network based on the usual 11-1 covering number of the first layer and the TV covering number of the subsequent layers.
Theorem 26. Let NETId, PI NET[PL pe2l...,,TT(ppT-uv Denote the T -layer noisy network by
be T classes of neural networks.
F= = Go NET(Pr-1,
Go NETIP1, p21 Go NETId, pıl.
and let H. {h Rd + [0, 1jrr h(x) By [fx)) ,3 Fj. Denote the uniform covering
numbers of compositions of neural network classes with the Gaussian noise class (with respect to dfFv) as
- N Nu
E In NET(p:: 00, dFv. Gn o X1.ss 1) 2 2SiST,
(I)
TVT
and the uniform covering number 9o NETid, p1/ with respect 11-112
20e NET[d, Pıl, m, 11-112
Ni = Nu
T TDT
Then we have
Nu (e; H, 11.11 S N,
The 11-1122 covering number of the first layer (i.c., N₁ in above) can be bounded using standard approaches in the literature. For instance, in Appendix we will use the bound of Lemma 14.7 in Anthony et al. (1999). Other Ns's can be bounded using Theorem [5) (See Corollary 28 in Pour and Ashtiani (2022) and Theorem i0 Ap) The above bound does not depend on the norm of weights and therefore we can use it for networks with large weights.
The proof of Theorem 26 involves applying Corollary to to the ||-I|2 cover of first layer into TVV cover. We then find a T'V cover for rest of the network by applying Lemma 18 recursively to compose all the other layers. We will compose the first layer with the rest of the network and bound the covering number by another application of Lemma 18 Finally, we turn the TV covering number
(of the entire network) back into ||-11/2 covering number using Theorem 17 The complete proof can be found in Appendix E
One can generalize the above analysis in the following way: instead of separating the first layer, one can basically "break" the network from any layer, existing ||-1|2 covering number bounds for the first few layers, and Theorem 25 for the rest. See Lemma 37 in Appendix for details.
8 NVAC: a metric for comparing generalization bounds
We want to provide tools to compare different approaches in finding covering numbers and their suggested generalization bounds. First, we define the notion of a generalization bound for clas- sification. Let y = [k] and F be a class of functions from X' to R Let A be an algorithm that receives a labeled sample S = ((x1,91),--- y.),..., (Fm: Umm) (X x 2) and outputs a func- tion E F. Note that the output of this function is a real vector so can capture margin- based classifiers too. Let 10-1, R x [ + {0, 1} be the "thresholded" 0-1 loss function defined by 10-1 (u. 3) 1 [argmaax (9) * y} where ((() is the i-th dimension of u. Definition 27 (Generalization Bound for Classification).
(valid) generalization bound for A with respect to 10-1 and another (surrogate) loss function I is a function GB : F x (X yym - B such that for every distribution D over x V. is D then with probability at least 0. 9.99 (over the randomness of S) we huve
Σ ((((z).)) E ( [0-1(h(2), $ SBhh,
m
(x.
8

---

For example, S)) 2 is a useless but valid generalization bound. Various generalization bounds that have been proposed in the literature are examples of GB. Note that GB can depend both on S (for instance on (S)) and on h (for example, on the norm of the weights of network).
It is not straightforward to empirically compare generalization bounds since they are often vacuous for commonly used applications. Diang et al. (2019) address this by looking at other metries, such as the correlation of each bound with the actual generalization gap. While these metrics are informative, it is also useful know how far off each bound is from producing a inon-vacuony bound (Dziugaite and Roy 2017). Therefore, we will take more direct approach and propose the following metric.
Definition 28 (NVAC). Let h be hypothesis, Se (X y a sample, and GB a generalization bound for algorithm A. Let S" denote sample of size mn which includes n copies of S. Let n² be the smallest integer such that the following holds:
GB(,, 5Th)
Σ (R.v)ES"
1(h(z),)) 1
15
We define NVAC to be |5t" = mnn..
Informally speaking, NVAC is an upper bound the minimum number of samples required to obtain a non-vacuors generalization bound. Approaches that get tighter upper bounds on covering number will generally result in smaller NVACs. In Appendix G we will show how one can calculate NVAC using the uniform covering number bounds.
Experiments
In this section, we empirically compare different approaches bounding the covering number using the NVAC metric. We compare the following approaches in bounding covering number: Theorem 26 Norm-based (Theorem 14.17 in Anthony et al. (1999), Lipschitzness--aase
(Theorem 14.5 in
Anthony et al. (1999). Pseudo-dim- (Theorem 14.2 in Anthony et al. (1999), and Spectral (Brtlett et al. (017)) More details about these bounds can be found in Appendix H
We train fully connected neural networks on MNIST dataset. We use a network with an input layer, an output layer, and three hidden layers each containing 250 hidden neurons as the baseline architecture. See Appendix [oor the details of the learning settings. The left two graphs in Figure [ depict NVACs as functions of the depth and width of the network. It can be observed that our approach achieves the smallest NVAC. The Norm-based bound is the worst and is removed from the graph (see Appendix [ Overall, bounds that are based on the norm of the weights (even the spectral norm) perform poorly compared to those that are based on the parameter count. This is an interesting observation since we have millions of parameters (As 10") in some of the wide networks and one would assume approaches based on norm of weights should be able explain generalization behaviour better. Aside from the fact that our bound does not have any dependence on the norms of weights, there are several reasons why it performs better. First, the NVAC in Spectral and Norm-based approaches have an extra polynomial dependence on 1 1/c, compared to all other approaches. Moreover, these bounds depend on product of norms and group norms which can get quite large. Finally, our method works naturally for multi-output layers, while the Pseudo-dia baaedd Lipschitzness-basee and Norm-based approaches work for valudd output (and therefore one needs bound the cover for each output separately).
The covering number bound of Theorem 26 has polynomial dependence on 1/a. Therefore, NVAC has a mild logarithmic dependence on 1 a (see Appendix G for details). The third graph in Figure ! corroborates that even negligible amount of noise (a x 10 10-240) is sufficient to get tighter bounds on NVAC compared to other approaches. Finally, the right graph in Figure I shows that even with a considerable amount of noise (c.g, 0.2), the train and test accuracy of the model remain almost unchanged. This is perhaps expected, as the dynamics of training neural networks with gradient descent is already noisy shows that small amount of noise does not affect the performance, yet it enables us to prove tighter generalization bounds.
without adding Gaussian noise. Overall, our preliminary experiment
Limitations and Future Work. Our analysis based on the assumption that the activation function is bounded. Therefore, extending the results to ReLU neural networks is not immediate, and is left for

---

XWAC (r-adi of Flbble Layes A80
XVAC Or siive O
2-1 Lote guaai (Q-444)
Thooee
307
Pondiidee Sperea
Lipttd
13
Spucted
01-
530 1000
Figure 1: The left two graphs depict NVAC of different generalization bounds as function of the number of hidden layers and width of the network. The Norm-based approach is excluded because of its excessively high NVAC (see Appendix D. The third graph plots NVAC against log (r) (a is standard deviation of noise) for the two best approaches. The rightmost graph plots the train/test 0-1 losses for different values of o. The gaps between the train and test losses are shown for 0, 0.3.
future work. Also, our empirical amalysis is preliminary and is mostly used as a sanity check. Further empirical evaluations can help better understand the role of noise in training neural networks.
References
Martin Anthony, Peter L Bartlett, Peter L Bartlett, et al. Neural network learning: Theoretical foundations, volume 9, cambridge university press Cambridge, 1999.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 264-263. PMLR, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Peter Bartlett. For valid generalization the size of the weights is more important than the size of the network. Advances in neural information processing systems, 9, 1996.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
Peter L Bartlett and Wolfgang Maass. Vapnik-chervonenkk dimension neural nets. The handbook of brain theory and neural networks, pages 1 1188-1192, 2003.
Peter L. Bartlett, Michael I Jordan, and Jon D McAuliffe.
Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155 2006.
Peter I. Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-noraall margin bounds for neural networks. Advances in neural information processing systems, 2017.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2288 ):2255-2301, 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(45):3003333007 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. Acta numerica, 30:87-201, 2021.
Eric Baum and David Haussler. What size net gives valid generalization? Advances neural information processing systems, 1, 1988.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances neural information processing systems. 31, 2018
10

---

Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
Minwoo Chae and Stephen G Walker. Wasserstein upper bounds of the total variation for smooth densities. Statistics & Probability Letters, 163:108771, 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory. pages 1305-1338. PMLR, 2020.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.
Robust estimators in high-dimensions without the computational intractability, SIAM Journal on Computing, 48(2):742-866 2019.
Richard M Dudley. Universal donsker classes and metric entropy. Selected Works of RM Dudley, pages 345-365. Springer, 2010.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty Artificial Intelligence (UAI), 2017.
Wei Gao and Zhi-Hua Zhou. Dropout rademacher complexity of deep neural networks. Science China Information Sciences, 59(7):1-12, 2016.
Paul W Goldberg and Mark R Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2):131-148, 1995.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299 PMLR, 2018.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli,, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Informtiinn Processing Systems, 30, 2017.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 33:9925-9935, 2020.
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theorry pages 772 804. PMLR, 2021.
Ziwei Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference Learning Theory, pages 2109-2136. PMLR, 2020.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic 2019.
generalization measures and where to find them. arXiv preprint
Kam-Chuen Jim, C Lee Giles, and Bill G Horne. An analysis of noise in recurrent neural networks:
convergence and generalization. IEEE Transactions on neural networks, 7(6):1424-144 1438, 1996.
Pascal Koiran and Eduardo D Sontag. Vapnik-chervonenkis dimension of recurrent neural networks.
Discrete Applied Mathematics, 86(1):63-79, 1998.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection.
Annals of Statistics, pages 1302-1338. 2000.
Soon Hoe Lim, N Benjamin Erichson, Liam Hodgkinson, and Michael Mahoney. Noisy recurrent neural networks. Advances in Neural Information Processing Systems, 34, 2021.

---

Philip M Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. In International Conference on Learning Representations, 2020.
Wolfgang Maass. Neural nets with superlinear vc-dimension. Neural Computation, 6(5):877-884, 1994.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep net- works via generalizing roise-resilience. In International Conference on Learning Representations. 2018.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information-thhorctiee generalization bounds for stochastic gradient descent. arXiv preprint arXiv:2102.00931, 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Repre- sentations, 2018.
Alireza Fathollah Pour and Hassan Ashtiani. Benefits of additive noise in composing classes with bounded capacity. arXiv preprint arXiv:2206.07199 2022.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference Learning Theory, pages 1703. PMLR, 2017.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1240. PMLR, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions Information Theory, 66(1):302-325, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Eduardo D Sontag et al. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96, 1998.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 15()::1929-1958 2014.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pages 3437-3452. PMLR, 2020.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Mathukumalli Vidyasagar. A theory of learning and generalization: with applications to neural networks and control systems. Springer-Vere Verlag, 1997.
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1 103, 2008
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In International conference on machine learning, pages 1058-1066. PMLR, 2013.
12

---

Haotian Wang, Wenjing Yang, Zhenyu Zhao, Tingjin Luo, Ji Wang. and Yuhua Tang. Rademacher dropout: An adaptive dropout for deep neural network via optimizing generalization gap. Neuro- computing, 357:177-187, 2019.
Aolin Xu and Maxim Raginsky. Information-theeun algorithms. Advances in Neural Information Processing Systems, 30, 2017.
analysis of generalization capability of learning
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550 2002.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: pac-bayesian compression approach. In International Conference on Learning Representations (ICLR), 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The main claims of the paper abstract and introduction stated as theorems, lemmas and propositions, which are proved in appendices due to space constraints.
(b) Did you describe the limitations of your work? [Yes] We discuss the limitations of our experiments and possible future work in "Limitations and Future Work".
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This mainly a theoretical paper and is unlikely to have any negative societal impacts.
(d) Have you read the ethies review guidelines and ensured that your paper conforms to them? (Yes)
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The theorems and lemmas proved in appendices due to space constraints.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material as a URL)? [Yes] The codes will be provided as supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix !
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix !
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We experiment on the publicly available MNIST dataset, which is mentioned in the main paper.
(b) Did you mention the license of the assets? [Yes] We provide our code as a supplemental material which does not require a license. We use MNIST dataset and discuss it in Appendix[[
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We provide our code in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use MNIST dataset which is publicly available.
13

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use MNIST dataset which a collection of handwritten digits and does not contain personal information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Vixl0MGR3jB", "reviewer": "Reviewer_yRWs", "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.", "questions": "\n- 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. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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:\n\n- It would have been nicer if the authors could also give an explicit example of non-Lipschitz activation functions. \n\n- 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.\n\n- 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). \n\nOverall, 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PP5xU4titW5", "reviewer": "Reviewer_Qj2x", "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. ", "questions": "Are there connections between the generalization bounds presented here and the certifiable adversarial robustness using randomized / gaussian smoothing [2]?\n\n[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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a novel approach to understand generalization when a small amount of noise is added while composing functions.\n2. 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.\n3. 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.\n4. 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.\n\n\nWeaknesses:\n1. 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.\n\n[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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NpI1JE9-T7X", "reviewer": "Reviewer_xHvU", "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. ", "questions": "1. In the definition of extended metrics, why does L2-extended metrics require a normalization?\n2. 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. \n3. 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. \n4. 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?\n5. 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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nOriginality: 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.\nQuality: I am not an expert in PAC learning theory but I briefly checked the proof, it looks sound to my best knowledge. \nClarity: As a math-heavy paper, this paper overall is very clear.\nSignificance: The generalized covering number analysis does help us understand the effect of noise in deep learning.\n\nWeakness: My major concern is the existing framework only works for bounded activation function. This limits the applicability  of the proposed theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept