summaries: The fact that a number of current generalization bounds for (deep) neural networks are not expressed on the deterministic predictor at stake is arguably an issue. This is notably the case of many recent PAC-Bayesian studies of neural networks stochastic surrogates (typically, a Gaussian noise is applied to the network weight parameters). The paper proposes to make these PAC-Bayesian bounds deterministic by studying their "noise-resilience" properties. The proposed generalization result bounds the margin of a (ReLU) neural network classifier from the empirical margin and a complexity term relying on conditions on the values of each layer (e.g., via layer Jacobian norm, the layer output norm, and the smallest pre-activation value).  This paper presents a PAC-Bayesian framework that bounds the generalization error of the learned model. While PAC-Bayesian bounds have been studied before, the focus of this paper is to study how different conditions in the network (e.g. behavior of activations) generalize from training set to the distribution. This is important since prior work have not been able to handle this issue properly and as a consequence, previous bounds are either on the networks with perturbed weights or with unrealistic assumptions on the behavior of the network for any input in the domain.
abstractText: The ability of overparameterized deep networks to generalize well has been linked to the fact that stochastic gradient descent (SGD) finds solutions that lie in flat, wide minima in the training loss – minima where the output of the network is resilient to small random noise added to its parameters. So far this observation has been used to provide generalization guarantees only for neural networks whose parameters are either stochastic or compressed. In this work, we present a general PAC-Bayesian framework that leverages this observation to provide a bound on the original network learned – a network that is deterministic and uncompressed. What enables us to do this is a key novelty in our approach: our framework allows us to show that if on training data, the interactions between the weight matrices satisfy certain conditions that imply a wide training loss minimum, these conditions themselves generalize to the interactions between the matrices on test data, thereby implying a wide test loss minimum. We then apply our general framework in a setup where we assume that the pre-activation values of the network are not too small (although we assume this only on the training data). In this setup, we provide a generalization guarantee for the original (deterministic, uncompressed) network, that does not scale with product of the spectral norms of the weight matrices – a guarantee that would not have been possible with prior approaches.
authors.name: Vaishnavh Nagarajan
references.authors: Sanjeev Arora Rong Ge Behnam Neyshabur Yi Zhang
references.title: Stronger generalization bounds for deep nets via a compression approach
references.venue: In The 35th International Conference on Machine Learning,
references.authors: Peter L. Bartlett Dylan J. Foster Matus J. Telgarsky
references.title: Spectrally-normalized margin bounds for neural networks
references.venue: In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems
references.authors: Alon Brutzkus Amir Globerson Eran Malach Shai Shalev-Shwartz
references.title: SGD learns overparameterized networks that provably generalize on linearly separable data
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Gintare Karolina Dziugaite Daniel M. Roy
references.title: Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
references.venue: In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence,
references.authors: Noah Golowich Alexander Rakhlin Ohad Shamir
references.title: Size-independent sample complexity of neural networks
references.venue: Computational Learning Theory,
references.authors: Ralf Herbrich Thore Graepel
references.title: A pac-bayesian margin bound for linear classifiers: Why svms work. In Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems
references.authors: Geoffrey E. Hinton Drew van Camp
references.title: Keeping the neural networks simple by minimizing the description length of the weights
references.venue: In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, COLT,
references.authors: Nitish Shirish Keskar Dheevatsa Mudigere Jorge Nocedal Mikhail Smelyanskiy Ping Tak Peter Tang
references.title: On large-batch training for deep learning: Generalization gap and sharp minima
references.venue: International Conference on Learning Representations (ICLR),
references.authors: John Langford Rich Caruana
references.title: not) bounding the true error. In Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic
references.authors: John Langford John Shawe-Taylor
references.title: Pac-bayes & margins
references.venue: In Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems,
references.authors: Yuanzhi Li Yingyu Liang
references.title: Learning overparameterized neural networks via stochastic gradient descent on structured data
references.venue: In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018,
references.authors: Ben London Bert Huang Lise Getoor
references.title: Stability and generalization in structured prediction
references.venue: Journal of Machine Learning Research,
references.authors: David McAllester
references.title: Simplified pac-bayesian margin bounds. In Learning Theory and Kernel Machines
references.authors: David A. McAllester
references.title: Some pac-bayesian theorems
references.venue: Machine Learning,
references.authors: David A. McAllester
references.title: Pac-bayesian model averaging
references.venue: In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT 1999,
references.authors: Vaishnavh Nagarajan J. Zico Kolter
references.title: Generalization in deep networks: The role of distance from initialization. Deep Learning: Bridging Theory and Practice Workshop in Advances in Neural Information Processing Systems
references.venue: Annual Conference on Neural Information Processing Systems
references.authors: Behnam Neyshabur Ryota Tomioka Nathan Srebro
references.title: In search of the real inductive bias: On the role of implicit regularization in deep learning
references.venue: International Conference on Learning Representations Workshop Track,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nathan Srebro
references.title: Exploring generalization in deep learning
references.venue: Advances in Neural Information Processing Systems to appear,
references.authors: Behnam Neyshabur Srinadh Bhojanapalli David McAllester Nathan Srebro
references.title: A pac-bayesian approach to spectrally-normalized margin bounds for neural networks
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Roman Novak Yasaman Bahri Daniel A. Abolafia Jeffrey Pennington Jascha Sohl-Dickstein
references.title: Sensitivity and generalization in neural networks: an empirical study
references.venue: In International Conference on Learning Representations,
references.authors: Daniel Soudry Elad Hoffer Nathan Srebro
references.title: The implicit bias of gradient descent on separable data
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Joel A. Tropp
references.title: User-friendly tail bounds for sums of random matrices
references.venue: Foundations of Computational Mathematics,
references.authors: Chiyuan Zhang Samy Bengio Moritz Hardt Benjamin Recht Oriol Vinyals
references.title: Understanding deep learning requires rethinking generalization
references.venue: International Conference on Learning Representations (ICLR),
sections.heading: 1 INTRODUCTION
sections.text: Modern deep neural networks contain millions of parameters and are trained on relatively few samples. Conventional wisdom in machine learning suggests that such models should massively overfit on the training data, as these models have the capacity to memorize even a randomly labeled dataset of similar size (Zhang et al., 2017; Neyshabur et al., 2015). Yet these models have achieved state-ofthe-art generalization error on many real-world tasks. This observation has spurred an active line of research (Soudry et al., 2018; Brutzkus et al., 2018; Li & Liang, 2018) that has tried to understand what properties are possessed by stochastic gradient descent (SGD) training of deep networks that allows these networks to generalize well.
  One particularly promising line of work in this area (Neyshabur et al., 2017; Arora et al., 2018) has been bounds that utilize the noise-resilience of deep networks on training data i.e., how much the training loss of the network changes with noise injected into the parameters, or roughly, how wide is the training loss minimum. While these have yielded generalization bounds that do not have a severe exponential dependence on depth (unlike other bounds that grow with the product of spectral norms of the weight matrices), these bounds are quite limited: they either apply to a stochastic version of the classifier (where the parameters are drawn from a distribution) or a compressed version of the classifier (where the parameters are modified and represented using fewer bits).
  In this paper, we revisit the PAC-Bayesian analysis of deep networks in Neyshabur et al. (2017; 2018) and provide a general framework that allows one to use noise-resilience of the deep network
  on training data to provide a bound on the original deterministic and uncompressed network. We achieve this by arguing that if on the training data, the interaction between the ‘activated weight matrices’ (weight matrices where the weights incoming from/outgoing to inactive units are zeroed out) satisfy certain conditions which results in a wide training loss minimum, these conditions themselves generalize to the weight matrix interactions on the test data.
  After presenting this general PAC-Bayesian framework, we specialize it to the case of deep ReLU networks, showing that we can provide a generalization bound that accomplishes two goals simultaneously: i) it applies to the original network and ii) it does not scale exponentially with depth in terms of the products of the spectral norms of the weight matrices; instead our bound scales with more meaningful terms that capture the interactions between the weight matrices and do not have such a severe dependence on depth in practice. We note that all but one of these terms are indeed quite small on networks in practice. However, one particularly (empirically) large term that we use is the reciprocal of the magnitude of the network pre-activations on the training data (and so our bound would be small only in the scenario where the pre-activations are not too small). We emphasize that this drawback is more of a limitation in how we characterize noise-resilience through the specific conditions we chose for the ReLU network, rather than a drawback in our PAC-Bayesian framework itself. Our hope is that, since our technique is quite general and flexible, by carefully identifying the right set of conditions, in the future, one might be able to derive a similar generalization guarantee that is smaller in practice.
  To the best of our knowledge, our approach of generalizing noise-resilience of deep networks from training data to test data in order to derive a bound on the original network that does not scale with products of spectral norms, has neither been considered nor accomplished so far, even in limited situations.
sections.heading: 2 BACKGROUND AND RELATED WORK
sections.text: One of the most important aspects of the generalization puzzle that has been studied is that of the flatness/width of the training loss at the minimum found by SGD. The general understanding is that flatter minima are correlated with better generalization behavior, and this should somehow help explain the generalization behavior (Hochreiter & Schmidhuber, 1997; Hinton & van Camp, 1993; Keskar et al., 2017). Flatness of the training loss minimum is also correlated with the observation that on training data, adding noise to the parameters of the network results only in little change in the output of the network – or in other words, the network is noise-resilient. Deep networks are known to be similarly resilient to noise injected into the inputs (Novak et al., 2018); but note that our theoretical analysis relies on resilience to parameter perturbations.
  While some progress has been made in understanding the convergence and generalization behavior of SGD training of simple models like two-layered hidden neural networks under simple data distributions (Neyshabur et al., 2015; Soudry et al., 2018; Brutzkus et al., 2018; Li & Liang, 2018), all known generalization guarantees for SGD on deeper networks – through analyses that do not use noise-resilience properties of the networks – have strong exponential dependence on depth. In particular, these bounds scale either with the product of the spectral norms of the weight matrices (Neyshabur et al., 2018; Bartlett et al., 2017) or their Frobenius norms (Golowich et al., 2018). In practice, the weight matrices have a spectral norm that is as large as 2 or 3, and an even larger Frobenius norm that scales with √ H where H is the width of the network i.e., maximum number of hidden units per layer. 1 Thus, the generalization bound scales as say, 2D or HD/2, where D is the depth of the network.
  At a high level, the reason these bounds suffer from such an exponential dependence on depth is that they effectively perform a worst case approximation of how the weight matrices interact with each other. For example, the product of the spectral norms arises from a naive approximation of the Lipschitz constant of the neural network, which would hold only when the singular values of the
  1To understand why these values are of this order in magnitude, consider the initial matrix that is randomly initialized with independent entries with variance 1/ √ H . It can be shown that the spectral norm of this matrix, with high probability, lies near its expected value, near 2 and the Frobenius norm near its expected value which is √ H . Since SGD is observed not to move too far away from the initialization regardless of H (Nagarajan & Kolter, 2017), these values are more or less preserved for the final weight matrices.
  weight matrices all align with each other. However, in practice, for most inputs to the network, the interactions between the activated weight matrices are not as adverse.
  By using noise-resilience of the networks, prior approaches (Arora et al., 2018; Neyshabur et al., 2017) have been able to derive bounds that replace the above worst-case approximation with smaller terms that realistically capture these interactions. However, these works are limited in critical ways. Arora et al. (2018) use noise-resilience of the network to modify and “compress” the parameter representation of the network, and derive a generalization bound on the compressed network. While this bound enjoys a better dependence on depth because its applies to a compressed network, the main drawback of this bound is that it does not apply on the original network. On the other hand, Neyshabur et al. (2017) take advantage of noise-resilience on training data by incorporating it within a PAC-Bayesian generalization bound (McAllester, 1999a). However, their final guarantee is only a bound on the expected test loss of a stochastic network.
  In this work, we revisit the idea in Neyshabur et al. (2017), by pursuing the PAC-Bayesian framework (McAllester, 1999a) to answer this question. The standard PAC-Bayesian framework provides generalization bounds for the expected loss of a stochastic classifier, where the stochasticity typically corresponds to Gaussian noise injected into the parameters output by the learning algorithm. However, if the classifier is noise-resilient on both training and test data, one could extend the PAC-Bayesian bound to a standard generalization guarantee on the deterministic classifier.
  Other works have used PAC-Bayesian bounds in different ways in the context of neural networks. Langford & Caruana (2001); Dziugaite & Roy (2017) optimize the stochasticity and/or the weights of the network in order to numerically compute good (i.e., non-vacuous) generalization bounds on the stochastic network. Neyshabur et al. (2018) derive generalization bounds on the original, deterministic network by working from the PAC-Bayesian bound on the stochastic network. However, as stated earlier, their work does not make use of noise resilience in the networks learned by SGD.
  OUR CONTRIBUTIONS The key contribution in our work is a general PAC-Bayesian framework for deriving generalization bounds while leveraging the noise resilience of a deep network. While our approach is applied to deep networks, we note that it is general enough to be applied to other classifiers.
  In our framework, we consider a set of conditions that when satisfied by the network, makes the output of the network noise-resilient at a particular input datapoint. For example, these conditions could characterize the interactions between the activated weight matrices at a particular input. To provide a generalization guarantee, we assume that the learning algorithm has found weights such that these conditions hold for the weight interactions in the network on training data (which effectively implies a wide training loss minimum). Then, as a key step, we generalize these conditions over to the weight interactions on test data (which effectively implies a wide test loss minimum) 2. Thus, with the guarantee that the classifier is noise-resilient both on training and test data, we derive a generalization bound on the test loss of the original network.
  Finally, we apply our framework to a specific set up of ReLU based feedforward networks. In particular, we first instantiate the above abstract framework with a set of specific conditions, and then use the above framework to derive a bound on the original network. While very similar conditions have already been identified in prior work (Arora et al., 2018; Neyshabur et al., 2017) (see Appendix G for an extensive discussion of this), our contribution here is in showing how these conditions generalize from training to test data. Crucially, like these works, our bound does not have severe exponential dependence on depth in terms of products of spectral norms.
  We note that in reality, all but one of our conditions on the network do hold on training data as necessitated by the framework. The strong, non-realistic condition we make is that the pre-activation values of the network are sufficiently large, although only on training data; however, in practice a small proportion of the pre-activation values can be arbitrarily small. Our generalization bound scales inversely with the smallest absolute value of the pre-activations on the training data, and hence in practice, our bound would be large.
  2Note that we can not directly assume these conditions to hold on test data, as that would be ‘cheating’ from the perspective of a generalization guarantee.
  Intuitively, we make this assumption to ensure that under sufficiently small parameter perturbations, the activation states of the units are guaranteed not to flip. It is worth noting that Arora et al. (2018); Neyshabur et al. (2017) too require similar, but more realistic assumptions about pre-activation values that effectively assume only a small proportion of units flip under noise. However, even under our stronger condition that no such units exist, it is not apparent how these approaches would yield a similar bound on the deterministic, uncompressed network without generalizing their conditions to test data. We hope that in the future our work could be developed further to accommodate the more realistic conditions from Arora et al. (2018); Neyshabur et al. (2017).
sections.heading: 3 A GENERAL PAC-BAYESIAN FRAMEWORK
sections.text: In this section, we present our general PAC-Bayesian framework that uses noise-resilience of the network to convert a PAC-Bayesian generalization bound on the stochastic classifier to a generalization bound on the deterministic classifier.
  NOTATION. Let KL(⋅∥⋅) denote the KL-divergence. Let ∥⋅∥ , ∥⋅∥∞ denote the `2 norm and the `∞ norms of a vector, respectively. Let ∥⋅∥2 , ∥⋅∥F , ∥⋅∥2,∞ denote the spectral norm, Frobenius norm and maximum row `2 norm of a matrix, respectively. Consider a K-class learning task where the labeled datapoints (x, y) are drawn from an underlying distribution D over X × {1,2,⋯,K} where X ∈ RN . We consider a classifier parametrized by weightsW . For a given input x and class k, we denote the output of the classifier by f (x;W) [k]. In our PAC-Bayesian analysis, we will use U ∼ N (0, σ2) to denote parameters whose entries are sampled independently from a Gaussian, andW + U to denote the entrywise addition of the two sets of parameters. We use ∥W∥2F to denote ∑ D d=1 ∥Wd∥ 2 F . Given a training set S of m samples, we let (x, y) ∼ S to denote uniform sampling from the set. Finally, for any γ > 0, let Lγ(f (x;W) , y) denote a margin-based loss such that the loss is 0 only when f (x;W) [y] ≥ maxj≠y f (x;W) [j]+γ, and 1 otherwise. Note that L0 corresponds to 0-1 error. See Appendix A for more notations.
  TRADITIONAL PAC-BAYESIAN BOUNDS. The PAC-Bayesian framework (McAllester, 1999a;b) allows us to derive generalization bounds for a stochastic classifier. Specifically, let W̃ be a random variable in the parameter space whose distribution is learned based on training data S. Let P be a prior distribution in the parameter space chosen independent of the training data. The PAC-Bayesian framework yields the following generalization bound on the 0-1 error of the stochastic classifier that holds with probability 1 − δ over the draw of the training set S of m samples3:
  EW̃[E(x,y)∼D[L0(f (x;W̃) , y)]] ≤ EW̃[E(x,y)∼S[L0(f (x;W̃) , y)]] + Õ ( √ KL(W̃∥P )/m)
  Typically, and in the rest of this discussion, W̃ is a Gaussian with covariance σ2I for some σ > 0 centered at the weightsW learned based on the training data. Furthermore, we will set P to be a Gaussian with covariance σ2I centered at the random initialization of the network like in Dziugaite & Roy (2017), instead of at the origin, like in Neyshabur et al. (2018). This is because the resulting KL-divergence – which depends on the distance between the means of the prior and the posterior – is known to be smaller, and to save a √ H factor in the bound (Nagarajan & Kolter, 2017).
sections.heading: 3.1 OUR FRAMEWORK
sections.text: To extend the above PAC-Bayesian bound to a standard generalization bound on a deterministic classifierW , we need to replace the training and the test loss of the stochastic classifier with that of the original, deterministic classifier. However, in doing so, we will have to introduce extra terms in the upper bound to account for the perturbation suffered by the train and test loss under the Gaussian perturbation of the parameters. To tightly bound these two terms, we need that the network is noise-resilient on training and test data respectively. Our hope is that if the learning algorithm has found weights such that the network is noise-resilient on the training data, we can then generalize this noise-resilience over to test data as well, allowing us to better bound the excess terms.
  3We use Õ(⋅) to hide logarithmic factors.
  We now discuss how noise-resilience is formalized in our framework through certain conditions on the weight matrices. Much of our discussion below is dedicated to how these conditions must be designed, as these details carry the key ideas behind how noise-resilience can be generalized from training to test data. We then present our main generalization bound and some intuition about our proof technique.
  INPUT-DEPENDENT PROPERTIES OF WEIGHTS Recall that, at a high level, the noise-resilience of a network corresponds to how little the network reacts to random parameter perturbations. Naturally, this would vary depending on the input. Hence, in our framework, we will analyze the noise-resilience of the network as a function of a given input. Specifically, we will characterize noise-resilience through conditions on how the weights of the model interact with each other for a given input. For example, in the next section, we will consider conditions of the form “the preactivation values of the hidden units in layer d, have magnitude larger than some small positive constant”. The idea is that when these conditions involving the weights and the input are satisfied, if we add noise to the weights, the output of the classifier for that input will provably suffer only little perturbation. We will more generally refer to each scalar quantity involved in these conditions, such as each of the pre-activation values, as an input-dependent property of the weights.
  We will now formulate these input-dependent properties and the conditions on them, for a generic classifier, and in the next section, we will see how they can be instantiated in the case of deep networks. Consider a classifier for which we can define R different conditions, which when satisfied on a given input, will help us guarantee the classifier’s noise-resilience at that input i.e., bound the output perturbation under random parameter perturbations (to get an idea of what R corresponds to, in the case of deep networks, we will have a condition for each layer, and so R will scale with depth). In particular, let the rth condition be a bound involving a particular set of input-dependent properties of the weights denoted by {ρr,1(W,x, y), ρr,2(W,x, y),⋯,} – here, each element ρr,l(W,x, y) is a scalar value that depends on the weights and the input, just like pre-activation values4. Note that here the first subscript l is the index of the element in the set, and the second subscript r is the index of the set itself. Now for each of these properties, we will define a corresponding set of positive constants (that are independent ofW,x and y), denoted by {∆⋆r,1,∆ ⋆ r,2,⋯}, which we will use to specify our conditions. In particular, we say that the weightsW satisfy the rth condition on the input (x, y) if5:
  ∀l, ρr,l(W,x, y) > ∆ ⋆ r,l (1)
  For convenience, we also define an additional R+1th set to be the singleton set containing the margin of the classifier on the input: f (x;W) [y] −maxj≠y f (x;W) [j]. Note that if this term is positive (negative) then the classification is (in)correct. We will also denote the constant ∆⋆R+1,1 as γclass.
  ORDERING OF THE SETS OF PROPERTIES We now impose a crucial constraint on how these sets of properties depend on each other. Roughly speaking, we want that for a given input, if the first r − 1 sets of properties approximately satisfy the condition in Equation 1, then the properties in the rth set are noise-resilient i.e., under random parameter perturbations, these properties do not suffer much perturbation. This kind of constraint would naturally hold for deep networks if we have chosen the properties carefully e.g., we will show that, for any given input, the perturbation in the pre-activation values of the dth layer is small as long as the absolute pre-activation values in the layers below d − 1 are large, and a few other norm-bounds on the lower layer weights are satisfied.
  We formalize the above requirement by defining expressions ∆r,l(σ) that bound the perturbation in the properties ρr,l, in terms of the variance σ2 of the parameter perturbations. For any r ≤ R + 1 and for any (x, y), our framework requires the following to hold:
  4As we will see in the next section, most of these properties depend on only the unlabeled input x and not on y. But for the sake of convenience, we include y in the formulation of the input-dependent property, and use the word input to refer to x or (x, y) depending on the context
  5When we say ∀l below, we refer to the set of all possible indices l in the rth set, noting that different sets may have different cardinality.
  if ∀q < r,∀l, ρq,l(W,x, y) > 0 then
  PrU∼N (0,σ2I)[∀l ∣ρr,l(W + U ,x, y) − ρr,l(W,x, y)∣ > ∆r,l(σ)
  2 and
  ∀q<r,∀l ∣ρq,l(W + U ,x, y) − ρq,l(W,x, y)∣< ∆q,l(σ)
  2 ] ≤
  1
  (R + 1) √ m . (2)
  Let us unpack the above constraint. First, although the above constraint must hold for all inputs (x, y), it effectively applies only to those inputs that satisfy the pre-condition of the if-then statement: namely, it applies only to inputs (x, y) that approximately satisfy the first r − 1 conditions in Equation 1 in that ρq,l(W,x, y) > 0 (instead of ρq,l(W,x, y) > ∆⋆q,l). Next, we discuss the second part of the above if-then statement which specifies a probability term that is required to be small for all such inputs. In words, the first event within the probability term above is the event that for a given random perturbation U , the properties involved in the rth condition suffer a large perturbation. The second is the event that the properties involved in the first r − 1 conditions do not suffer much perturbation; but, given that these r − 1 conditions already hold approximately, this second event implies that these conditions are still preserved approximately under perturbation. In summary, our constraint requires the following: for any input on which the first r − 1 conditions hold, there should be very few parameter perturbations that significantly perturb the rth set of properties while preserving the first r − 1 conditions. When we instantiate the framework, we have to derive closed form expressions for the perturbation bounds ∆r,l(σ) (in terms of only σ and the constants ∆⋆r,l). As we will see, for ReLU networks, we will choose the properties in a way that this constraint naturally falls into place in a way that the perturbation bounds ∆r,l(σ) do not grow with the product of spectral norms (Lemma E.1).
  THEOREM STATEMENT In this setup, we have the following ‘margin-based’ generalization guarantee on the original network. That is, we bound the 0-1 test error of the network by a margin-based error on the training data. Our generalization guarantee, which scales linearly with the number of conditions R, holds under the setting that the training algorithm always finds weights such that on the training data, the conditions in Equation 1 is satisfied for all r = 1,⋯,R.
  Theorem 3.1. Let σ∗ be the maximum standard deviation of the Gaussian parameter perturbation such that the constraint in Equation 2 holds with ∆r,l(σ⋆) ≤ ∆⋆r,l ∀r ≤ R + 1 and ∀l. Then, for any δ > 0, with probability 1 − δ over the draw of samples S from Dm, for anyW we have that, ifW satisfies the conditions in Equation 1 for all r ≤ R and for all training examples (x, y) ∈ S, then
  Pr(x,y)∼D [L0(f (x;W) , y)] ≤Pr(x,y)∼S [Lγclass(f (x;W) , y)]
  + Õ ⎛ ⎜ ⎝ R
  ¿ Á ÁÀ2KL(N (W, (σ⋆)2I)∥P ) + ln 2mR δ
  m − 1
  ⎞ ⎟ ⎠
  The crux of our proof (in Appendix D) lies in generalizing the conditions of Equation 1 satisfied on the training data to test data one after the other, by proving that they are noise-resilient on both training and test data. Crucially, after we generalize the first r − 1 conditions from training data to test data (i.e., on most test and training data, the r − 1 conditions are satisfied), we will have from Equation 2 that the rth set of properties are noise-resilient on both training and test data. Using the noise-resilience of the rth set of properties on test/train data, we can generalize even the rth condition to test data.
  We emphasize a key, fundamental tool that we present in Theorem C.1 to convert a generic PACBayesian bound on a stochastic classifier, to a generalization bound on the deterministic classifier. Our technique is at a high level similar to approaches in London et al. (2016); McAllester (2003). In Section C.1, we argue how this technique is more powerful than other approaches in Neyshabur et al. (2018); Langford & Shawe-Taylor (2002); Herbrich & Graepel (2000) in leveraging the noiseresilience of a classifier. The high level argument is that, to convert the PAC-Bayesian bound, these latter works relied on a looser output perturbation bound, one that holds on all possible inputs, with high probability over all perturbations i.e., a bound on maxx ∥f (x;W) − f (x;W + U)∥∞ w.h.p over draws of U . In contrast, our technique relies on a subtly different but significantly tighter bound: a bound on the output perturbation that holds with high probability given an input i.e., a bound
  on ∥f (x;W) − f (x;W + U)∥∞ w.h.p over draws of U for each x. When we do instantiate our framework as in the next section, this subtle difference is critical in being able to bound the output perturbation without suffering from a factor proportional to the product of the spectral norms of the weight matrices (which is the case in Neyshabur et al. (2018)).
sections.heading: 4 APPLICATION OF OUR FRAMEWORK TO RELU NETWORKS
sections.text: NOTATION. In this section, we apply our framework to feedforward fully connected ReLU networks of depth D (we care about D > 2) and width H (which we will assume is larger than the input dimensionality N , to simplify our proofs) and derive a generalization bound on the original network that does not scale with the product of spectral norms of the weight matrices. Let φ (⋅) denote the ReLU activation. We consider a network parameterized byW = (W1,W2,⋯,WD) such that the output of the network is computed as f (x;W) = WDφ (WD−1⋯φ (W1x)). We denote the value of the hth hidden unit on the dth layer before and after the activation by gd (x;W) [h] and fd (x;W) [h] respectively. We define Jd/d ′ (x;W) ∶= ∂gd (x;W)/∂gd ′ (x;W) to be the Jacobian of the pre-activations of layer d with respect to the pre-activations of layer d′ for d′ ≤ d (each row in this Jacobian corresponds to a unit in layer d). In short, we will call this, Jacobian d/d′. Let Z denote the random initialization of the network.
  Informally, we consider a setting where the learning algorithm satisfies the following conditions on the training data that make it noise-resilient on training data: a) the `2 norm of the hidden layers are all small, b) the pre-activation values are all sufficiently large in magnitude, c) the Jacobian of any layer with respect to a lower layer, has rows with a small `2 norm, and has a small spectral norm. We cast these conditions in the form of Equation 1 by appropriately defining the properties ρ’s and the margins ∆⋆’s in the general framework. We note that these properties are quite similar to those already explored in Arora et al. (2018); Neyshabur et al. (2017); we provide more intuition about these properties, and how we cast them in our framework in Appendix E.1.
  Having defined these properties, we first prove in Lemma E.1 in Appendix E a guarantee equivalent to the abstract inequality in Equation 2. Essentially, we show that under random perturbations of the parameters, the perturbation in the output of the network and the perturbation in the input-dependent properties involved in (a), (b), (c) themselves can all be bounded in terms of each other. Crucially, these perturbation bounds do not grow with the spectral norms of the network.
  Having instantiated the framework as above, we then instantiate the bound provided by the framework. Our generalization bound scales with the bounds on the properties in (a) and (c) above as satisfied on the training data, and with the reciprocal of the property in (b) i.e., the smallest absolute value of the pre-activations on the training data. Additionally, our bound has an explicit dependence on the depth of the network, which arises from the fact that we generalize R = O(D) conditions. Most importantly, our bound does not have a dependence on the product of the spectral norms of the weight matrices.
  Theorem 4.1. (shorter version; see Appendix F for the complete statement) For any margin γclass > 0, and any δ > 0, with probability 1 − δ over the draw of samples from Dm, for anyW , we have that:
  Pr(x,y)∼D [L0(f (x;W) , y)] ≤Pr(x,y)∼S [Lγclass(f (x;W) , y)] + Õ (D √ ∥W −Z∥2F /((σ ⋆)2m))
  Here 1/σ⋆ equals Õ( √ Hmax{Blayer-`2 ,Bpreact,Boutput,Bjac-row-`2 ,Bjac-spec}), where
  Blayer-`2 ∶= O ⎛
  ⎝ max 1≤d<D
  ∑ d d′=1 ζ ⋆ d/d′α ⋆ d′−1
  α⋆d
  ⎞ ⎠ ,Bpreact ∶= O ⎛ ⎝ max 1≤d<D
  ∑ d d′=1 ζ ⋆ d/d′α ⋆ d′−1
  √ Hγ⋆d
  ⎞
  ⎠
  Boutput ∶= O ⎛
  ⎝
  ∑ D d=1 ζ ⋆ D/dα ⋆ d−1
  √ Hγclass
  ⎞ ⎠ ,Bjac-row-`2 ∶= O ⎛ ⎝ max 1≤d′<d<D
  ζ⋆d−1/d′ + ∥Wd∥2,∞∑ d−1 d′′=d′+1 ψ ⋆ d−1/d′′ζ ⋆ d′′−1/d′
  ζ⋆ d/d′
  ⎞
  ⎠
  Bjac-spec ∶= O ⎛
  ⎝ max 1≤d′<d<D
  ψ⋆d′′−1/d′ + ∥Wd∥2∑ d−1 d′′=d′+1 ψ ⋆ d−1/d′′ζ ⋆ d′′−1/d′
  ψ⋆ d/d′
  ⎞
  ⎠
  where, the terms α⋆d, γ ⋆ d etc., are norm-bounds that hold on all training data (x, y) ∈ S as follows: α⋆d ≥ ∥f d (x;W)∥ (an upper bound on the `2 norm of each hidden layer output), γ⋆d ≤ minh ∣f d (x;W) [h]∣ (a lower bound on the absolute values of the pre-activations for each layer), ζ⋆d/d′ ≥ ∥J d/d′(x;W)∥
  2,∞ (an upper bound on the row `2 norms of the Jacobian for each
  layer), ψ⋆d/d′ ≥ ∥J d/d′(x;W)∥
  2 (an upper bound on the spectral norm of the Jacobian for each
  layer).
  In Figure 1, we show how the terms in the bound vary for networks of varying depth with a small width of H = 40 on the MNIST dataset. We observe that Blayer-`2 ,Boutput,Bjac-row-`2 ,Bjac-spec typically lie in the range of [100,102] and scale with depth as ∝ 1.57D. In contrast, the equivalent term from Neyshabur et al. (2018) consisting of the product of spectral norms can be as large as 103 or 105 and scale with D more severely as 2.15D.
  The bottleneck in our bound is Bpreact, which scales inversely with the magnitude of the smallest absolute pre-activation value of the network. In practice, this term can be arbitrarily large, even though it does not depend on the product of spectral norms/depth. This is because some hidden units can have arbitrarily small absolute pre-activation values – although this is true only for a small proportion of these units.
  To give an idea of the typical, non-pathological magnitude of the pre-activation values, we plot two other variations of Bpreact: a) 5%-Bpreact which is calculated by ignoring 5% of the training datapoints with the smallest absolute pre-activation values and b) median-Bpreact which is calculated by ignoring half the hidden units in each layer with the smallest absolute pre-activation values for each input. We observe that median-Bpreact is quite small (of the order of 102), while 5%-Bpreact, while large (of the order of 104), is still orders of magnitude smaller than Bpreact.
  In Figure 2 we show how our overall bound and existing product-of-spectral-norm-based bounds (Bartlett et al., 2017; Neyshabur et al., 2018) vary with depth. While our bound is orders of magnitude larger than prior bounds, the key point here is that our bound grows with depth as 1.57D while prior bounds grow with depth as 2.15D indicating that our bound should perform asymptotically better with respect to depth. Indeed, we verify that our bound obtains better values than the other existing bounds when D = 28 (see Figure 2 b). We also plot hypothetical variations of our bound replacing Bpreact with 5%-Bpreact (see “Ours-5%”) and median-Bpreact (see “Ours-Median”) both of which perform orders of magnitude better than our actual bound (note that these two hypothetical bounds do not actually hold good). In fact for larger depth, the bound with 5%-Bpreact performs better than all other bounds (including existing bounds). This indicates that the only bottleneck in our bound comes from the dependence on the smallest pre-activation magnitudes, and if this particular
  dependence is addressed, our bound has the potential to achieve tighter guarantees for even smaller D such as D = 8.
  (2018) maxx ∥x∥2D √ H∏Dd=1 ∥Wd∥2
  γclass ⋅
  √
  ∑ D d=1 ∥Wd−Zd∥2F ∥Wd∥22 and Bartlett et al. (2017) maxx ∥x∥2∏ D d=1 ∥Wd∥2 γclass ⋅
  (∑ D d=1 ( ∥Wd−Zd∥2,1 ∥Wd∥ )
  2/3 ) 3/2 both of which have been modified to include distance from initialization
  instead of distance from origin for a fair comparison. Observe the last two bounds have a plot with a larger slope than the other bounds indicating that they might potentially do worse for a sufficiently large D. Indeed, this can be observed from the plots on the right where we report the distribution of the logarithm of these bounds for D = 28 across 12 runs (although under training settings different from the experiments on the left; see Appendix F.3 for the exact details).
  We refer the reader to Appendix F.3 for added discussion where we demonstrate how all the quantities in our bound vary with depth for H = 1280 (Figure 3, 4) and with width for D = 8,14 (Figures 5 and 6).
  Finally, as noted before, we emphasize that the dependence of our bound on the pre-activation values is a limitation in how we characterize noise-resilience through our conditions rather than a drawback in our general PAC-Bayesian framework itself. Specifically, using the assumed lower bound on the pre-activation magnitudes we can ensure that, under noise, the activation states of the units do not flip; then the noise propagates through the network in a tractable, “linear” manner. Improving this analysis is an important direction for future work. For example, one could modify our analysis to allow perturbations large enough to flip a small proportion of the activation states; one could potentially formulate such realistic conditions by drawing inspiration from the conditions in Neyshabur et al. (2017); Arora et al. (2018).
  However, we note that even though these prior approaches made more realistic assumptions about the magnitudes of the pre-activation values, the key limitation in these approaches is that even under our non-realistic assumption, their approaches would yield bounds only on stochastic/compressed networks. Generalizing noise-resilience from training data to test data is crucial to extending these bounds to the original network, which we accomplish.
sections.heading: 5 SUMMARY AND FUTURE WORK
sections.text: In this work, we introduced a novel PAC-Bayesian framework for leveraging the noise-resilience of deep neural networks on training data, to derive a generalization bound on the original uncompressed, deterministic network. The main philosophy of our approach is to first generalize the noise-resilience from training data to test data using which we convert a PAC-Bayesian bound on a stochastic network to a standard margin-based generalization bound. We apply our approach to ReLU based networks and derive a bound that scales with terms that capture the interactions between the weight matrices better than the product of spectral norms.
  For future work, the most important direction is that of removing the dependence on our strong assumption that the magnitude of the pre-activation values of the network are not too small on training data. More generally, a better understanding of the source of noise-resilience in deep ReLU networks would help in applying our framework more carefully in these settings, leading to tighter guarantees on the original network.
  ACKNOWLEDGEMENTS. Vaishnavh Nagarajan was partially supported by a grant from the Bosch Center for AI.
sections.heading: APPENDIX
sections.heading: A NOTATIONS (CONTINUED)
sections.text: We will use upper-case symbols to denote matrices, and lower-case bold-face symbols to denote vectors. In order to make the mathematical statements/derivations easier to read, if we want to emphasize a term, say x, we write, x.
  Recall that we consider a neural netork of depth D (i.e., D − 1 hidden layers and one output layer) mapping from RN → RK , where K is the number of class labels in the learning task. The layers are fully connected with H units in each hidden layer, and with ReLU activations φ (⋅) on all the hidden units and linear activations on the output units. We denote the parameters of the network using the symbolW , which in turn denotes a set of weight matrices W1,W2,⋯,WD. Here, W1 ∈ RH×N , and WD ∈ RK×H and for all other layers d ≠ 1,D, Wd ∈ RH×H . We will use the notationWd to denote the first d weight matrices. We denote the vector of weights input to the hth unit on the dth layer (which corresponds to the hth row in Wd) as wdh.
  For any input x ∈ RN , we denote the function computed by the network on that input as f (x;W) = WDφ (WD−1⋯φ (W1x)). For any d = 1,⋯,D−1, we denote the output of the dth hidden layer after the activation by fd (x;W). We denote the corresponding pre-activation values for that layer by gd (x;W). We denote the value of the hth hidden unit on the dth layer after and before the activation by fd (x;W) [h] and gd (x;W) [h] respectively. Note that for the output layer d = D, these two values are equal as we assume only a linear activation. For d = 0, we define f0 (x;W) = x. As a result, we have the following recursions:
  fd (x;W) = φ (gd (x;W)) , d = 1,2,⋯,D − 1
  fD (x;W) = gD (x;W) = f (x;W) ,
  gd (x;W) =Wdf d−1 (x;W) ,∀d = 1,2,⋯,D
  gd (x;W) [h] =wdh ⋅ f d−1 (x;W) [h],∀d = 1,2,⋯,D
  For layers d′, d such that d′ ≤ d, let us define Jd/d ′ (x;W) to be the Jacobian corresponding to the pre-activation values of layer d with respect to the pre-activation values of layer d′ on an input x. That is,
  Jd/d ′ (x;W) =
  ∂gd (x;W)
  ∂gd′ (x;W)
  In other words, this corresponds to the product of the ‘activated’ portion of the matrices Wd′+1,Wd′+2,⋯,Wd, where the weights corresponding to inactive inputs are zeroed out. In short, we will call this ‘Jacobian d/d′’. Note that each row in this Jacobian corresponds to a unit on the dth layer, and each column corresponds to a unit on the d′th layer.
  We will denote the parameters of a random initialization of the network by Z = (Z1, Z2,⋯, Zd). Let D be an underlying distribution over RN × {1,2,⋯,K} from which the data is drawn.
  In our PAC-Bayesian analysis, we will use U to denote a set of D weight matrices U1, U2,⋯, UD whose entries are sampled independently from a Gaussian. Furthermore, we will use Ud to denote only the first d of the randomly sampled weight matrices, andW + Ud to denote a network where the d random matrices are added to the first d weight matrices inW . Note thatW + U0 =W . Thus, f (x;W + Ud) is the output of a network where the first d weight matrices have been perturbed. In our analysis, we will also need to study a perturbed network where the hidden units are frozen to be at the activation state they were at before the perturbation; we will use the notationW[+Ud] to denote the weights of such a network.
  For our statements regarding probability of events, we will use ∧, ∨, and ¬ to denote the intersection, union and complement of events (to disambiguate from the set operators).
sections.heading: B USEFUL LEMMAS
sections.text: In this section, we present some standard results. The first two results below will be useful for our noise resilience analysis.
sections.heading: HOEFFDING BOUND
sections.text: Lemma B.1. For i = 1,2,⋯, n, let Xi be independent random variables sampled from a Gaussian with mean µi and variance σ2i . Then for all t ≥ 0, we have:
  Pr [ n
  ∑ i=1
  (Xi − µi) ≥ t] ≤ exp(− t2
  2∑ n i=1 σ 2 i
  ) .
  Or alternatively, for δ ∈ (0,1]
  Pr ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ n ∑ i=1 (Xi − µi) ≥ ¿ Á ÁÀ2 n ∑ i=1 σ2i ln 1 δ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ δ
  Note that an identical inequality holds good symmetrically for the event ∑ni=1Xi − µi ≤ −t, and so the probability that the event ∣∑ni=1Xi − µi∣ > t holds, is at most twice the failure probability in the above inequalities.
sections.heading: PRODUCT OF AN ENTRYWISE GAUSSIAN MATRIX AND A VECTOR
sections.text: Lemma B.2. Let U be a H1 ×H2 matrix where each entry is sampled from N (0, σ2). Let x be an arbitrary vector in RH2 . Then, Ux ∼ N (0, ∥x∥22σ2I).
  Proof. Ux is a random vector sampled from a multivariate Gaussian with mean E[Ux] = 0 and co-variance E[UxxTUT ]. The (i, j)th entry in this covariance matrix is E[(uTi x)(uTj x)] where ui and uj are the ith and jth row in U . When i = j, E[(uTi x)(uTj x)] = E[∥uTi x∥2] = ∑ H2 h=1 E[u 2 ih]x 2 h = σ
  2∥x∥22. When i ≠ j, since ui and uj are independent random variables, we will have E[(uTi x)(uTj x)] = ∑ H2 h=1 E[uihxh]∑ H2 h=1 E[ujhxh] = 0.
  SPECTRAL NORM OF ENTRY-WISE GAUSSIAN MATRIX The following result (Tropp, 2012) bounds the spectral norm of a matrix with Gaussian entries, with high probability:
  Lemma B.3. Let U be a H ×H matrix. Then,
  PrU∼N (0,σ2I) [∥U∥2 > t] ≤ 2H exp(−t 2 /2Hσ2)
  or alternatively, for any δ > 0,
  PrU∼N (0,σ2I) ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ∥U∥2 > σ
  √
  2H ln 2H
  δ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≤ 2H exp(−t2/2Hσ2)
  KL DIVERGENCE OF GAUSSIANS. We will use the following KL divergence equality to bound the generalization error in our PAC-Bayesian analyses.
  Lemma B.4. Let P be the spherical Gaussian N (µ1, σ2I) and Q be the spherical Gaussian N (µ2, σ 2I). Then, the KL-divergence between Q and P is:
  KL(Q∥P ) = ∥µ2 −µ1∥
  2
  2σ2
sections.heading: C PAC-BAYESIAN THEOREM
sections.text: In this section, we will present our main PAC-Bayesian theorem that will guide our analysis of generalization in our framework. Concretely, our result extends the generalization bound provided by conventional PAC-Bayesian analysis (McAllester, 2003) – which is a generalization bound on the expected loss of a distribution of classifiers i.e., a stochastic classifier – to a generalization bound on a deterministic classifier. The way we reduce the PAC-Bayesian bound to a standard generalization bound, is different from the one pursued in previous works (Neyshabur et al., 2018; Langford & Shawe-Taylor, 2002).
  The generalization bound that we state below is a bit more general than standard generalization bounds on deterministic networks. Typically, generalization bounds are on the classification error; however, as discussed in the main paper we will be dealing with generalizing multiple different conditions on the interactions between the weights of the network from the training data to test data. So to state a bound that is general enough, we consider a set of generic functions ρr(W,x,y) for r = 1,2,⋯R′ (we use R′ to distinguish it from R, the number of conditions in the abstract classifier of Section 3.1). Each of these functions compute a scalar value that corresponds to some input-dependent property of the network with parametersW for the datapoint (x, y). As an example, this property could simply be the margin of the function on the yth class i.e., f (x;W) [y] −maxj≠y f (x;W) [j]. Theorem C.1. Let P be a prior distribution over the parameter space that is chosen independent of the training dataset. Let U be a random variable sampled entrywise fromN (0, σ2). Let ρr(⋅, ⋅, ⋅) and ∆r > 0 for r = 1,2,⋯R′, be a set of input-dependent properties and their corresponding margins. We define the networkW to be noise-resilient with respect to all these functions, at a given data point (x, y) if:
  PrU∼N (0,σ2) [∃r ∶ ∣ρr(W,x, y) − ρr(W + U ,x, y)∣ > ∆r 2 ] ≤ 1 √ m . (3)
  Let µD({(ρr,∆r)}R ′
  r=1,W) denote the probability over the random draw of a point (x, y) drawn from D, that the network with weightsW is not noise-resilient at (x, y) according to Equation 3. That is, let µD({(ρr,∆r)}R ′ r=1,W) ∶=
  Pr(x,y)∼D [PrU∼N (0,σ2) [∃r ∶ ∣ρr(W,x, y) − ρr(W + U ,x, y)∣ > ∆r 2 ] > 1 √ m ]
  Similarly, let µ̂S({(ρr,∆r)}R ′
  r=1,W) denote the fraction of data points (x, y) in a dataset S for which the network is not noise-resilient according to Equation 3. Then for any δ, with probability 1 − δ over the draws of a sample set S = {(xi, yi) ∼ D ∣i = 1,2,⋯,m}, for anyW we have:
  Pr(x,y)∼D [∃r ∶ ρr(W,x, y) < 0] ≤ 1
  m ∑ (x,y)∈S 1 [∃r ∶ ρr(W,x, y) < ∆r] + µ̂S({(ρr,∆r)}
  R′ r=1,W)
  +µD({(ρr,∆r)} R′ r=1,W) + 2
  √ 2KL(N (W, σ2I)∥P ) + ln 2m
  δ
  m − 1 + 2 √ m − 1 .
  The reader maybe curious about how one would bound the term µD in the above bound, as this term corresponds to noise-resilience with respect to test data. This is precisely what we bound later when we generalize the noise-resilience-related conditions satisfied on train data over to test data.
sections.heading: C.1 KEY ADVANTAGE OF OUR BOUND.
sections.text: The above approach differs from previous approaches used by Neyshabur et al. (2018); Langford & Shawe-Taylor (2002) in how strong a noise-resilience we require of the classifier to provide the generalization guarantee. The stronger the noise-resilience requirement, the more price we have to pay when we jump from the PAC-Bayesian guarantee on the stochastic classifier to a guarantee on the deterministic classifier. We argue that our noise-resilience requirement is a much milder condition and therefore promises tighter guarantees. Our requirement is in fact philosophically similar to London et al. (2016); McAllester (2003), although technically different.
  More concretely, to arrive at a reasonable generalization guarantee in our setup, we would need that µD and µ̂S are both only as large as O(1/ √ m). In other words, we would want the following for (x, y) ∼ D and for (x, y) ∼ S:
  Pr(x,y) [PrU∼N (0,σ2) [∃r ∶ ∣ρr(W,x, y) − ρr(W + U ,x, y)∣ > ∆r 2 ] > 1 √ m ] = O(1/ √ m).
  Previous works require a noise resilience condition of the form that with high probability a particular perturbation does not perturb the classifier output on any input. For example, the noise-resilience condition used in Neyshabur et al. (2018) written in terms of our notations, would be:
  PrU∼N (0,σ2) [∃x ∶ ∃r ∶ ∣ρr(W,x, y) − ρr(W + U ,x, y)∣ > ∆r 2 ] ≤ 1 2 .
  The main difference between the above two formulations is in what makes a particular perturbation (un)favorable for the classifier. In our case, we deem a perturbation unfavorable only after fixing the datapoint. However, in the earlier works, a perturbation is deemed unfavorable if it perturbs the classifier output sufficiently on some datapoint from the domain of the distribution. While this difference is subtle, the earlier approach would lead to a much more pessimistic analysis of these perturbations. In our analysis, this weakened noise resilience condition will be critical in analyzing the Gaussian perturbations more carefully than in Neyshabur et al. (2018) i.e., we can bound the perturbation in the classifier output more tightly by analyzing the Gaussian perturbation for a fixed input point.
  Note that one way our noise resilience condition would seem stronger in that on a given datapoint we want less than 1/ √ m mass of the perturbations to be unfavorable for us, while in previous bounds, there can be as much as 1/2 probability mass of perturbations that are unfavorable. In our analysis, this will only weaken our generalization bound by a ln √ m factor in comparison to previous bounds (while we save other significant factors).
sections.heading: C.2 PROOF FOR THEOREM C.1
sections.text: Proof. The starting point of our proof is a standard PAC-Bayesian theorem McAllester (2003) which bounds the generalization error of a stochastic classifier. Let P be a data-independent prior over the parameter space. Let L(W,x, y) be any loss function that takes as input the network parameter, and a datapoint x and its true label y and outputs a value in [0,1]. Then, we have that, with probability 1 − δ over the draw of S ∼ Dm, for every distribution Q over the parameter space, the following holds:
  EW̃∼Q [E(x,y)∼D [L(W̃,x, y)]] ≤ EW̃∼Q ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 m ∑ (x,y)∈S L(W̃,x, y) ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ + 2
  √ 2KL(Q∥P ) + ln 2m
  δ
  m − 1 (4)
  In other words, the statement tells us that except for a δ proportion of bad draws of m samples, the test loss of the stochastic classifier W̃ ∼ Q would be close to its train loss. This holds for every possible distribution Q, which allows us to cleverly choose Q based on S. As is the convention, we choose Q to be the distribution of the stochastic classifier picked from N (W, σ2I) i.e., a Gaussian perturbation of the deterministic classifierW .
  RELATING TEST LOSS OF STOCHASTIC CLASSIFIER TO DETERMINISTIC CLASSIFIER. Now our task is to bound the loss for the deterministic classifierW , Pr(x,y)∼D [∃r ∣ ρr(W,x, y) < 0]. To this end, let us define the following margin-based variation of this loss for some c ≥ 0:
  Lc(W,x, y) = { 1 ∃r ∶ ρr(W,x, y) < c∆r 0 otherwise,
  and so we have Pr(x,y)∼D [∃r ∣ ρr(W,x, y) < 0] = E(x,y)∼D [L0(W,x, y)]. First, we will bound the expected L0 of a deterministic classifier by the expected L1/2 of the stochastic classifier; then we will bound the test L1/2 of the stochastic classifier using the PAC-Bayesian bound.
  We will split the expected loss of the deterministic classifier into an expectation over datapoints for which it is noise-resilient with respect to Gaussian noise and an expectation over the rest. To write this out, we define, for a datapoint (x, y), N(W,x, y) to be the event thatW is noise-resilient at (x, y) as defined in Equation 3 in the theorem statement:
  E(x,y)∼D [L0(W,x, y)] = E(x,y)∼D [L0(W,x, y)∣ N(W,x, y)]Pr(x,y)∼D [N(W,x, y)] +E(x,y)∼D [L0(W,x, y)∣ ¬N(W,x, y)] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  ≤1
  Pr(x,y)∼D [¬N(W,x, y)] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  µD({(ρr,∆r)}R′r=1,W)
  ≤ E(x,y)∼D [L0(W,x, y)∣ N(W,x, y)]Pr(x,y)∼D [N(W,x, y)] + µD({(ρr,∆r)} R′ r=1,W) (5)
  To further continue the upper bound on the left hand side, we turn our attention to the stochastic classifier’s loss on the noise-resilient part of the distribution D (we will lower bound this term in terms of the first term on the right hand side above). For simplicity of notations, we will write D′ to denote the distribution D conditioned on N(W,x, y). Also, let U(W̃,x, y) be the favorable event that for a given data point (x, y) and a draw of the stochastic classifier, W̃ , it is the case that for every r, ∣ρr(W,x, y) − ρr(W̃,x, y)∣ ≤ ∆r/2. Then, the stochastic classifier’s loss L1/2 on D′ is:
  EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]] = E(x,y)∼D′ [EW̃∼Q [L1/2(W̃,x, y)]]
  splitting the inner expectation over the favorable and unfavorable perturbations, and using linearity of expectations,
  = E(x,y)∼D′ [EW̃∼Q [L1/2(W̃,x, y)∣ U(W̃,x, y)]PrW̃∼Q [U(W̃,x, y)]]
  +E(x,y)∼D′ [EW̃∼Q [L1/2(W̃,x, y)∣ ¬U(W̃,x, y)]PrW̃∼Q [¬U(W̃,x, y)]]
  to lower bound this, we simply ignore the second term (which is positive)
  ≥ E(x,y)∼D′ [EW̃∼Q [L1/2(W̃,x, y)∣ U(W̃,x, y)]PrW̃∼Q [U(W̃,x, y)]] .
  Next, we use the following fact: if L1/2(W̃,x, y) = 0, then for all r, ρr(W̃, x, y) ≥ ∆r/2 and if W̃ is a favorable perturbation of W , then for all r, ρr(W, x, y) ≥ ρr(W̃,x, y) − ∆r/2 > 0 i.e., L1/2(W̃,x, y) = 0 implies L0(W,x, y) = 0. Hence if W̃ is a favorable perturbation then, L1/2(W̃,x, y) ≥ L0(W,x, y). Therefore, we can lower bound the above expression by replacing the stochastic classifier with the deterministic classifier (and thus ridding ourselves of the expectation over Q):
  ≥ E(x,y)∼D′ [L0(W,x, y)PrW̃∼Q [U(W̃,x, y)]] .
  Since the favorable perturbations for a fixed datapoint drawn fromD′ have sufficiently high probability (that is, PrW̃∼Q [U(W̃,x, y)] ≥ 1 − 1/ √ m), we have:
  ≥ (1 − 1
  √ m
  )E(x,y)∼D′ [L0(W,x, y)] .
  Thus, we have a lower bound on the stochastic classifier’s loss that is in terms of the deterministic classifier’s loss on the noise-resilient datapoints. Rearranging it, we get an upper bound on the latter:
  E(x,y)∼D′ [L0(W,x, y)] ≤ 1
  (1 − 1√ m ) EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]]
  ≤ (1 + 1
  √ m − 1
  )EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]]
  ≤ EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]]
  + 1
  √ m − 1 EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  ≤1
  ≤ EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]] + 1
  √ m − 1
  Thus, we have an upper bound on the expected loss of the deterministic classifierW on the noiseresilient part of the distribution. Plugging this back in the first term of the upper bound on the deterministic classifier’s loss on the whole distribution D in Equation 5 we get :
  E(x,y)∼D [L0(W,x, y)] ≤(EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]] + 1
  √ m − 1
  )Pr(x,y)∼D [N(W,x, y)]+
  µD({(ρr,∆r)} R′ r=1,W)
  rearranging, we get:
  ≤ (EW̃∼Q [E(x,y)∼D′ [L1/2(W̃,x, y)]])Pr(x,y)∼D [N(W,x, y)]+
  µD({(ρr,∆r)} R′ r=1,W) + 1
  √ m − 1 Pr(x,y)∼D [N(W,x, y)] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  ≤1
  rewriting the expectation over D′ explicitly as an expectation over D conditioned on N(W,x, y), we get:
  ≤ (EW̃∼Q [E(x,y)∼D [L1/2(W̃,x, y)∣ N(W,x, y)]Pr(x,y)∼D [N(W,x, y)]])+
  µD({(ρr,∆r)} R′ r=1,W) + 1
  √ m − 1
  the first term above is essentially an expectation of a loss over the distribution D with the loss set to be zero over the non-noise-resilient datapoints and set to be L1/2 over the noise-resilient datapoints; thus we can upper bound it with the expectation of the L1/2 loss over the whole distribution D:
  ≤EW̃∼Q [E(x,y)∼D [L1/2(W̃,x, y)]] + ⋅µD({(ρr,∆r)} R′ r=1,W) + 1
  √ m − 1
  (6)
  Now observe that we can upper bound the first term here using the PAC-Bayesian bound by plugging in L1/2 for the generic L in Equation 4; however, the bound would still be in terms of the stochastic classifier’s train error. To get the generalization bound we seek, which involves the deterministic classifier’s train error, we need to take one final step mirroring these tricks on the train loss.
sections.heading: RELATING THE STOCHASTIC CLASSIFIER’S TRAIN LOSS TO DETERMINISTIC CLASSIFIER’S TRAIN
sections.text: LOSS. Our analysis here is almost identical to the previous analysis. Instead of working with the distribution D and D′ we will work with the training data set S and a subset of it S′ for which noise resilience property is satisfied byW . Below, to make the presentation neater, we use (x, y) ∼ S to denote uniform sampling from S.
  First, we upper bound the stochastic classifier’s train loss (L1/2) as follows:
  EW̃∼Q [E(x,y)∼S [L1/2(W̃,x, y)]] = E(x,y)∼S [EW̃∼Q [L1/2(W̃,x, y)]]
  splitting over the noise-resilient points S′ ((x, y) ∈ S for which N(W,x, y) holds) like in Equation 5, we can upper bound as:
  ≤ E(x,y)∼S′ [EW̃∼Q [L1/2(W̃,x, y)]]Pr(x,y)∼S [(x, y) ∈ S ′ ] + µ̂S({(ρr,∆r)} R′ r=1,W) (7)
  We can upper bound the first term by first splitting it over the favorable and unfavorable perturbations like we did before:
  E(x,y)∼S′ [EW̃∼Q [L1/2(W̃,x, y)]]
  = E(x,y)∼S′ [EW̃∼Q [L1/2(W̃,x, y)∣ U(W̃,x, y)]PrW̃∼Q [U(W̃,x, y)]]
  +E(x,y)∼S′ [EW̃∼Q [L1/2(W̃,x, y)∣ ¬U(W̃,x, y)]PrW̃∼Q [¬U(W̃,x, y)]]
  To upper bound this, we apply a similar argument. First, if L1/2(W̃,x, y) = 1, then ∃r such that ρr(W̃, x, y) < ∆r/2 and if W̃ is a favorable perturbation then for that value of r, ρr(W, x, y) < ρr(W̃,x, y) + ∆r/2 < ∆r. Thus if W̃ is a favorable perturbation then, L1(W,x, y) = 1 whenever L1/2(W̃,x, y) = 1 i.e., L1/2(W̃,x, y) ≤ L1(W,x, y). Next, we use the fact that the unfavorable perturbations for a fixed datapoint drawn from S′ have sufficiently low probability i.e., PrW̃∼Q [¬U(W̃,x, y)] ≤ 1/ √ m. Then, we get the following upper bound on the above equations, by replacing the stochastic classifier with the deterministic classifier (and thus ignoring the expectation over Q):
  ≤ E(x,y)∼S′ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ EW̃∼Q [L1(W,x, y)∣ U(W̃,x, y)]PrW̃∼Q [U(W̃,x, y)] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ≤1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
  +E(x,y)∼S′ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ EW̃∼Q [L1/2(W̃,x, y)∣ ¬U(W̃,x, y)] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ≤1 1 √ m ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦
  ≤ E(x,y)∼S′ [L1(W,x, y)] + 1
  √ m
  Plugging this back in the first term of Equation 7, we get:
  EW̃∼Q [E(x,y)∼S [L1/2(W̃,x, y)]] ≤(E(x,y)∼S′ [L1(W,x, y)] + 1
  √ m
  )Pr(x,y)∼S [(x, y) ∈ S ′ ]
  + µ̂S({(ρr,∆r)} R′ r=1,W)
  ≤E(x,y)∼S′ [L1(W,x, y)]Pr(x,y)∼S [(x, y) ∈ S′]
  + µ̂S({(ρr,∆r)} R′ r=1,W) + 1
  √ m
  Pr(x,y)∼S [(x, y) ∈ S ′ ]
  ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ≤1
  ≤E(x,y)∼S′ [L1(W,x, y)]Pr(x,y)∼S [(x, y) ∈ S′] + 1
  √ m
  + µ̂S({(ρr,∆r)} R′ r=1,W)
  since the first term is effectively the expectation of a loss over the whole distribution with the loss set to be zero on the non-noise-resilient points and set to L1 over the rest, we can upper bound it by setting the loss to be L1 over the whole distribution:
  ≤ E(x,y)∼S [L1(W,x, y)] + µ̂S({(ρr,∆r)}R ′ r=1,W) + 1
  √ m
  Applying the above upper bound and the bound in Equation 6 into the PAC-Bayesian result of Equation 4 yields our result (Note that combining these equations would produce the term 1√
  m + 1√
  m−1 which is at most 2√
  m−1 , which we reflect in the final bound. ).
sections.heading: D PROOF FOR THEOREM 3.1
sections.text: In this section, we present the proof for the abstract generalization guarantee presented in Section 3. Our proof is based on the following recursive inequality that we demonstrate for all r ≤ R (we will prove a similar, but slightly different inequality for r = R + 1):
  Pr(x,y)∼D [∃q≤r,∃l ρq,l(W,x, y) < 0] ≤ Pr(x,y)∼D [∃q<r,∃l ρq,l(W,x, y) < 0]
  + Õ ⎛
  ⎝
  √ 2KL(N (W, σ2I)∥P )
  m − 1
  ⎞
  ⎠
  ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ generalization error for condition r
  (8)
  Recall that the rth condition in Equation 1 is that ∀l, ρr,l > ∆⋆r,l. Above, we bound the probability mass of test points such that any one of the first r conditions in Equation 1 is not even approximately satisfied, in terms of the probability mass of points where one of the first r − 1 conditions is not even approximately satisfied, and a term that corresponds to how much error there can be in generalizing the rth condition from the training data.
  Our proof crucially relies on Theorem C.1. This theorem provides an upper bound on the proportion of test data that fail to satisfy a set of conditions, in terms of four quantities. The first quantity is the proportion of training data that do not satisfy the conditions; the second and third quantities, which we will in short refer to as µ̂S and µ̂D, correspond to the proportion of training and test data on which the properties involved in the conditions are not noise-resilient. The fourth quantity is the generalization error.
  First, we consider the base case when r = 1, and apply the PAC-Bayes-based guarantee from Theorem C.1 on the first set of properties {ρ1,1, ρ1,2,⋯} and their corresponding constants
  {∆⋆1,1,∆ ⋆ 1,2,⋯}. First we have from our assumption (in the main theorem statement) that on all the training data, the condition ρ1,l(W,x, y) > ∆⋆1,l is satisfied for all possible l. Thus, the first term in the upper bound in Theorem C.1 is zero. Next, we can show that the terms µ̂S and µ̂D would be zero too. This follows from the fact that the constraint in Equation 2 holds in this framework. Specifically, applying this equation for r = 1, for σ = σ⋆, we get that for all possible (x, y) the following inequality holds:
  PrU∼N (0,(σ⋆)2I) [∀l ∣ρ1,l(W + U ,x, y) − ρl,1(W,x, y)∣ > ∆1,l(σ
  ⋆)
  2 ] ≤
  1
  R √ m .
  Since, σ⋆ was chosen such that ∆1(σ⋆) ≤ ∆⋆1 , we have:
  PrU [∀l ∣ρ1,l(W + U ,x, y) − ρl,1(W,x, y)∣ > ∆⋆1 2 ] ≤ 1 R √ m .
  Effectively this establishes that the noise-resilience requirement of Equation 3 in Theorem C.1 holds on all possible inputs, thus proving our claim that the terms µ̂S and µ̂D would be zero. Thus, we will get that
  Pr(x,y)∼D [∃l ρ1,l(W,x, y) < 0] ≤ Õ ⎛
  ⎝
  √ 2KL(N (W, σ2I)∥P )
  m − 1
  ⎞
  ⎠
  which proves the recursion statement for the base case.
  To prove the recursion for some arbitrary r ≤ R, we again apply the PAC-Bayes-based guarantee from Theorem C.1, but on the union of the first r sets of properties. Again, we will have that the first term in the guarantee would be zero, since the corresponding conditions are satisfied on the training data. Now, to bound the proportion of bad points µ̂S and µ̂D, we make the following claim:
  the network is noise-resilient as per Equation 3 in Theorem C.1 for any input that satisfies the r−1 conditions approximately i.e., ∀q ≤ r−1 and ∀l, ρq,l(W,x, y) > 0.
  The above claim can be used to prove Equation 8 as follows. Since all the conditions are assumed to be satisfied by a margin on the training data, this claim immediately implies that µ̂S is zero. Similarly, this claim implies that for the test data, we can bound µD in terms of Pr(x,y)∼D [∃q<r ∃l ρq,l(W,x, y) < 0], thus giving rise to the recursion in Equation 8.
  Now, to prove our claim, consider an input (x, y) such that ρq,l(W,x, y) > 0 for q = 1,2,⋯, r − 1 and for all possible l. First from the assumption in our theorem statement that ∆q,l(σ⋆) ≤ ∆⋆q,l, we have the following upper bound on the proportion of parameter perturbations under which any of the properties in the first r sets suffer a large perturbation:
  PrU [∃q ≤ r ∃l ∶ ∣ρq,l(W,x, y) − ρq,l(W + U ,x, y)∣ > ∆∗q,l
  2 ]
  ≤ PrU [∃q ≤ r ∃l ∶ ∣ρq,l(W,x, y) − ρq,l(W + U ,x, y)∣ > ∆q,l(σ
  ⋆)
  2 ]
  Now, this can be expanded as a summation over q = 1,2,⋯, r as:
  ≤ r
  ∑ q=1
  Pr[∃l ∣ρq,l(W + U ,x, y) − ρq,l(W,x, y)∣ > ∆q(σ
  ⋆)
  2 ∧
  ∀q′ < q, ∃l ∣ρq′,l(W,x, y) − ρq′,l(W + U ,x, y)∣< ∆q′(σ
  ⋆)
  2 ]
  and because (x, y) satisfies ρq,l(W,x, y) > 0 for q = 1,2,⋯, r − 1 and for all possible l, by the constraint assumed in Equation 2, we have:
  ≤ r
  ∑ q=1
  1
  (R + 1) √ m
  ≤ 1
  √ m
  Thus, we have that (x, y) satisfies the noise-resilience condition from Equation 3 in Theorem C.1 if it also satisfies ρq,l(W,x, y) > 0 for q = 1,2,⋯, r − 1 and for all possible l. This proves our claim, and hence in turn proves the recursion in Equation 8.
  Finally, we can apply a similar argument for the R + 1th set of input-dependent properties (which is a singleton set consisting of the margin of the network) with a small change since the first term in the guarantee from Theorem C.1 is not explicitly assumed to be zero; we will get an inequality in terms of the number of training points that are not classified correctly by a margin, giving rise to the margin-based bound:
  Pr(x,y)∼D [∃q≤R+1 ∃l, ρq,l(W,x, y) < 0] ≤ 1
  m ∑ (x,y)∈S 1[ρR+1,1(W,x, y) < ∆R,1]
  + Pr(x,y)∼D [∃q ≤ R ∃l ρq,l(W,x, y) < 0]
  + Õ ⎛
  ⎝
  √ 2KL(N (W, σ2I)∥P )
  m − 1
  ⎞
  ⎠
  Note that in the first term on the right hand side, ρR+1,1(W,x, y) corresponds to the margin of the classifier on (x, y). Now, by using the fact that the test error is upper bounded by the left hand side in the above equation, applying the recursion on the right hand side R + 1 times, we get our final result.
sections.heading: E PERTURBATION BOUNDS
sections.heading: E.1 OVERVIEW OF THE BOUNDS.
sections.text: In this section, we will quantify the noise resilience of a network in different aspects. Each of our bounds has the following structure: we fix an input point (x, y), and then say that with high probability over a Gaussian perturbation of the network’s parameters, a particular input-dependent property of the network (say the output of the network, or the pre-activation value of a particular unit h at a particular layer d, or say the Frobenius norm sof its active weight matrices), changes only by a small magnitude proportional to the variance σ2 of the Gaussian perturbation of the parameters.
  A key feature of our bounds is that they do not involve the product of the spectral norm of the weight matrices and hence save us an exponential factor in the final generalization bound. Instead, the bound in the perturbation of a particular property will be in terms of i) the magnitude of the some ‘preceding’ properties (typically, these are properties of the lower layers) of the network, and ii) how those preceding properties themselves respond to perturbations. For example, an upper bound in the perturbation of the dth layer’s output would involve the `2 norm of the lower layers d′ < d, and how much they would blow up under these perturbations.
sections.heading: E.2 SOME NOTATIONS.
sections.text: To formulate our lemma statement succinctly, we design a notation wherein we define a set of ‘tolerance parameters’ which we will use to denote the extent of perturbation suffered by a particular property of the network.
  Let Ĉ denote a ‘set’ (more on what we mean by a set below) of positive tolerance values, consisting of the following elements:
  1. α̂d, for each layer d = 1,⋯,D − 1 (a tolerance value for the `2 norm of the output of layer d)
  2. γ̂d for each layer d = 1,⋯,D. (a tolerance value for the magnitude of the pre-activations of layer d)
  3. ζ̂d/d′ for each layer d = 1,2,⋯,D, and d′ = 1,⋯, d (a tolerance value for the `2 norm of each row of the Jacobians at layer d)
  4. ψ̂d/d′ for each layer d = 1,2,⋯,D, and d′ = 1,⋯, d (a tolerance value for the spectral norm of the Jacobians at layer d)
sections.heading: Notes about (abuse of) notation:
sections.text: • We call Ĉ a ‘set’ to denote a group of related constants into a single symbol. Each element in this set has a particular semantic associated with it, unlike the standard notation of a set, and so when we refer to, say ζ̂d/d′ ∈ Ĉ , we are indexing into the set to pick a particular element.
  • We will use the subscript Ĉd to index into a subset of only those tolerance values corresponding to layers from 1 until d.
  Next we define two events. The first event formulates the scenario that for a given input, a particular perturbation of the weights until layer d brought about very little change in the properties of these layers (within some tolerance levels). The second event formulates the scenario that the perturbation did not flip the activation states of the network.
  Definition E.1. Given an input x, and an arbitrary set of constants Ĉ ′, for any perturbation U ofW , we denote by PERT-BOUND(W+U , Ĉ ′,x) the event that:
  • for each α̂′d ∈ Ĉ ′, the perturbation in the `2 norm of layer d activations is bounded as
  ∣∥fd (x;W)∥ − ∥fd (x;W+U)∥∣ ≤ α̂′d.
  • for each γ̂′d ∈ Ĉ ′, the maximum perturbation in the preactivation of hidden units on layer d
  is bounded as maxh ∣fd (x;W) [h] − fd (x;W+U) [h]∣ ≤ γ̂′d.
  • for each ζ̂ ′d/d′ ∈ Ĉ ′, the maximum perturbation in the `2 norm of a row of the Jacobian d/d′
  is bounded as maxh ∣∥Jd/d ′ (x;W)[h]∥ − ∥Jd/d ′ (x;W+U)[h]∥∣ ≤ ζ̂ ′d/d′ .
  • for each ψ̂′d/d′ ∈ Ĉ ′, the perturbation in the spectral norm of the Jacobian d/d′ is bounded
  as ∣∥Jd/d ′ (x;W)∥ 2 − ∥Jd/d ′ (x;W+U)∥ 2 ∣ ≤ ψ̂′d/d′ .
  NOTE: If we supply only a subset of Ĉ (say Ĉd instead of the whole of Ĉ ) to the above event, PERT-BOUND(W + U , ⋅,x), then it would denote the event that the perturbations suffered by only that subset of properties is within the respective tolerance values.
  Next, we define the event that the perturbations do not affect the activation states of the network.
  Definition E.2. For any perturbation U of the matricesW , let UNCHANGED-ACTSd(W + U ,x) denote the event that none of the activation states of the first d layers change on perturbation.
sections.heading: E.3 MAIN LEMMA.
sections.text: Our results here are styled similar to the equations required by Equation 2 presented in the main paper. For a given input point and for a particular property of the network, roughly, we bound the the probability that a perturbation affects the value of the property while none of the preceding preceding properties themselves are perturbed beyond a certain tolerance level.
  Lemma E.1. Let Ĉ be a set of constants (that denote the amount of perturbation in the properties preceding a considered property). For any δ̂ > 0, define Ĉ ′ (which is a bound on the perturbation of
  a considered property) in terms of Ĉ and the perturbation parameter σ, for all d = 1,2,⋯,D and for all d′ = d − 1,⋯,1 as follows:
  α̂′d ∶= σ d
  ∑ d′=1
  ∥Jd/d ′ (x;W)∥
  F (∥fd
  ′−1 (x;W)∥ + α̂d′−1)
  √
  2 ln 2DH
  δ̂
  γ̂′d ∶= σ d
  ∑ d′=1
  ∥Jd/d ′ (x;W)∥
  2,∞ (∥fd
  ′−1 (x;W)∥ + α̂d′−1)
  √
  2 ln 2DH
  δ̂
  ζ̂ ′d/d′ ∶= σ (∥J d−1/d′
  (x;W)∥ F + ζ̂d−1/d′
  √ H)
  √
  4 ln DH
  δ̂
  + σ d−1 ∑
  d′′=d′+1 ∥Wd∥2,∞ ∥J
  d−1/d′′ (x;W)∥
  2 (∥Jd
  ′′−1/d′ (x;W)∥
  F + ζ̂d′′−1/d′
  √ H)
  √
  4 ln DH
  δ̂
  ψ̂′d/d′ ∶= σ √ H (∥Jd−1/d ′ (x;W)∥
  2 + ψ̂d−1/d′)
  √
  2 ln 2DH
  δ̂
  + σ √ H d−1 ∑
  d′′=d′+1 ∥Wd∥2 ∥J
  d−1/d′′ (x;W)∥
  2 (∥Jd
  ′′−1/d′ (x;W)∥
  2 + ψ̂d′′−1/d′)
  √
  2 ln 2DH
  δ̂
  α̂′0 = 0
  ζ̂ ′d/d ∶= 0
  ψ̂′d/d ∶= 0
  Let Ud be sampled entrywise from N (0, σ2) for any d. Then, the following statements hold good:
  1. Bound on perturbation of of `2 norm of the output of layer d. For all d = 1,2,⋯,D,
  PrU[¬PERT-BOUND(W + U ,{α̂′d},x) ∧
  PERT-BOUND(W + U , Ĉd−1⋃{ζ̂d/d′}dd′=1,x) ∧ UNCHANGED-ACTSd−1(W + U ,x)] ≤ δ̂
  2. Bound on perturbation of pre-activations at layer d. For all d = 1,2,⋯,D,
  PrU[¬PERT-BOUND(W + U ,{γ̂′d},x) ∧
  PERT-BOUND(W + U , Ĉd−1⋃{ζ̂d/d′}dd′=1⋃{α̂d},x) ∧ UNCHANGED-ACTSd−1(W + U ,x)] ≤ δ̂
sections.heading: 3. Bound on perturbation of `2 norm on the rows of the Jacobians d/d′.
sections.text: PrU[¬PERT-BOUND(W + U ,{ζ̂ ′d/d′} d d′=1,x) ∧
  PERT-BOUND(W + U , Ĉd−1,x) ∧ UNCHANGED-ACTSd−1(W + U ,x)] ≤ δ̂
sections.heading: 4. Bound on perturbation of spectral norm of the Jacobians d/d′.
sections.text: PrU[¬PERT-BOUND(W + U ,{ψ̂′d/d′} d d′=1,x) ∧
  PERT-BOUND(W + U , Ĉd−1,x) ∧ UNCHANGED-ACTSd−1(W + U ,x)] ≤ δ̂
  Proof. For the most part of this discussion, we will consider a perturbed network where all the hidden units are frozen to be at the same activation state as they were at, before the perturbation. We will denote the weights of such a network byW[+U] and its output at the dth layer by fd (x;W[+U]). By having the activations states frozen, the Gaussian perturbations propagate linearly through the activations, effectively remaining as Gaussian perturbations; then, we can enjoy the well-established properties of the Gaussian even after they propagate.
  PERTURBATION BOUND ON THE `2 NORM OF LAYER d. We bound the change in the `2 norm of the dth layer’s output by applying a triangle inequality6 after splitting it into a sum of vectors. Each summand here (which we define as vd′ for each d′ ≤ d) is the difference in the dth layer output on introducing noise in weight matrix d′ after having introduced noise into all the first d′ − 1 weight matrices.
  ∣∥fd (x;W[+Ud])∥ − ∥f d (x;W)∥∣ ≤ ∥fd (x;W[+Ud]) − f d (x;W)∥
  because the activations are ReLU, we can replace this with the perturbation of the pre-activation
  ≤ ∥gd (x;W[+Ud]) − g d (x;W)∥
  ≤ XXXXXXXXXXXXXXXXXXX d ∑ d′=1 ⎛ ⎜ ⎜ ⎜ ⎝ gd (x;W[+Ud′]) − g d (x;W[+Ud′−1]) ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ∶=vd′ ⎞ ⎟ ⎟ ⎟ ⎠ XXXXXXXXXXXXXXXXXXX
  ≤ d
  ∑ d′=1
  ∥vd′∥ = d
  ∑ d′=1
  √
  ∑ h
  v2d′,h (9)
  Here, vd′,h is the perturbation in the preactivation of hidden unit h on layer d′, brought about by perturbation of the d′th weight matrix in a network where only the first d′ − 1 weight matrices have already been perturbed.
  Now, for each h, we bound vd′,h in Equation 9. Since the activations have been frozen we can rewrite each vd′,h as the product of the hth row of the unperturbed network’s Jacobian d/d′ , followed by only the perturbation matrix Ud′ , and then the output of the layer d′ − 1. Concretely, we have7 8:
  vd′,h =
  1×Hd′ ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ Jd/d ′ (x;W)[h] Hd′×Hd′−1 ³·µ Ud′ Hd′−1×1 ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ fd ′−1
  (x;W[+Ud′−1]) ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  spherical Gaussian
  What do these random variables vd′,h look like? Conditioned on Ud′−1, the second part of our expansion of vd′,h, namely, Ud′fd
  ′−1 (x;W[+Ud′−1]) is a multivariate spherical Gaussian (see Lemma B.2) of the form N (0, σ2∥fd ′−1 (x;W[+Ud′−1]) ∥ 2I). As a result, conditioned on Ud′−1, vd′,h is a univariate Gaussian N (0, σ2∥Jd/d ′ (x;W)[h]∥2∥fd ′−1 (x;W[+Ud′−1])∥ 2).
  Then, we can apply a standard Gaussian tail bound (see Lemma B.1) to conclude that with probability 1 − δ̂/DH over the draws of Ud′ (conditioned on any Ud′−1), vd′,h is bounded as:
  ∣vd′,h∣ ≤ σ ∥J d/d′ (x;W)[h]∥ ∥fd ′−1 (x;W[+Ud′−1])∥
  √
  2 ln 2DH
  δ̂ . (10)
  Then, by a union bound over all the hidden units on layer d, and for each d′, we have that with probability 1 − δ̂, Equation 9 is upper bounded as:
  6Specifically, for two vectors a,b, we have from triangle inequality that ∥b∥ ≤ ∥a∥ + ∥b − a∥ and ∥a∥ ≤ ∥b∥ + ∥a − b∥. As a result of this, we have: − ∥a − b∥ ≤ ∥a∥ − ∥b∥ ≤ ∥a − b∥. We use this inequality in our proof.
  7Below, we have used Hd to denote the number of units on the dth layer (and this equals H for the hidden units and K for the output layer).
  8Note that the succinct formula below holds good even for the corner case d′ = d, where the first Jacobian-row term becomes a vector with zeros on all but the hth entry and therefore only the hth row of the perturbation matrix Ud′ will participate in the expression of vd′,h.
  ∑ d′
  √
  ∑ h
  v2d′,h ≤ d
  ∑ d′=1
  σ ∥Jd/d ′ (x;W)∥
  F ∥fd
  ′−1 (x;W[+Ud′−1])∥
  √
  2 ln 2DH
  δ̂ . (11)
  Using this we prove the probability bound in the lemma statement. To simplify notations, let us denote Ĉd−1⋃{ζ̂d/d′}dd′=1 by Ĉprev. Furthermore, we will drop redundant symbols in the arguments of the events we have defined. Then, recall that we want to upper bound the following probability (we ignore the argumentsW + U and x for brevity):
  Pr [(¬PERT-BOUND ({α̂′d})) ∧ PERT-BOUND(Ĉprev) ∧ UNCHANGED-ACTSd−1]
  Recall that Equation 11 is a bound on the perturbation of the `2 norm of the dth layer’s output when the activation states are explicitly frozen. If the perturbation we randomly draw happens to satisfy UNCHANGED-ACTSd−1 then the bound in Equation 11 holds good even in the case where the activation states are not explicitly frozen. Furthermore, when PERT-BOUND(Ĉprev) holds, the bound in Equation 11 can be upper-bounded by α̂′d as defined in the lemma statement, because under PERT-BOUND(Ĉprev), the middle term in Equation 11 can be upper bounded using triangle inequality as ∥fd ′−1 (x;W[+Ud′−1])∥ ≤ ∥f d′−1 (x;W)∥ + α̂d′−1. Hence, the event above happens only for the perturbations for which Equation 11 fails and hence we have that the above probability term is upper bounded by δ̂.
  PERTURBATION BOUND ON THE PREACTIVATION VALUES OF LAYER d. Following the same analysis as above, the bound we are seeking here is essentially maxh∑dd′=1 ∣vd′,h∣. The bound follows similarly from Equation 10.
  PERTURBATION BOUND ON THE `2 NORM OF THE ROWS OF THE JACOBIAN d/d′. We split this term like we did in the previous subsection, and apply triangle equality as follows:
  max h
  ∣∥Jd/d ′ (x;W)[h]∥ − ∥Jd/d ′ (x;W[+Ud])[h]∥∣
  ≤ max h
  ∥Jd/d ′ (x;W)[h] − Jd/d ′ (x;W[+Ud])[h]∥
  ≤ XXXXXXXXXXXXXXXXXXXXX d ∑ d′′=1 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Jd/d ′ (x;W[+Ud′′])[h] − J d/d′ (x;W[+Ud′′−1])[h] ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ∶=yd′′ h ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ XXXXXXXXXXXXXXXXXXXXX
  ≤ max h
  d
  ∑ d′′=1
  ∥yd ′′
  h ∥ = max h
  d
  ∑ d′′=1
  √
  ∑ h′
  (yd′′,h,h′) 2 (12)
  Here, we have defined yd ′′
  h to be the vector that corresponds to the difference in the hth row of the Jacobian d/d′ brought about by perturbing the d′′th weight matrix, given that the first d′′ − 1 matrices have already been perturbed. We use h to iterate over the units in the dth layer and h′ to iterate over the units in the d′th layer.
  Now, under the frozen activation states, when we perturb the weight matrices from 1 uptil d′, since these matrices are not involved in the Jacobian d/d′, fortunately, the Jacobian d/d′ is not perturbed (as the set of active weights in d/d′ are the same when we perturbW asW[+Ud′]). So, we will only need to bound yd′′,h,h′ for d′′ > d′.
  What does the distribution of yd′′,h,h′ look like for d′′ > d′? We can expand9 yd′′,h,h′ as the product of i) the hth row of the Jacobian d/d′′ ii) the perturbation matrix Ud′′ and iii) the h′th column of the Jacobian d′/d′′ − 1 for the perturbed network:
  9Again, note that the below succinct formula works even for corner cases like d′′ = d′ or d′′ = d.
  yd′′,h,h′ =
  1×Hd′′ ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ Jd/d ′′ (x;W)[h] Hd′′×Hd′′−1 ³·µ Ud′′ Hd′′−1×1 ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ Jd ′′−1/d′ (x;W[+Ud′′−1])[∶, h ′ ]
  ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ spherical Gaussian
  Conditioned on Ud′′−1, the second part of this expansion, namely, Ud′′Jd ′′−1/d′(x;W[+Ud′′−1])[∶ , h′] is a multivariate spherical Gaussian (see Lemma B.2) of the form N (0, σ2∥Jd ′′−1/d′(x;W[+Ud′′−1])[∶, h ′]∥2I). As a result, conditioned on Ud′′−1, yd′′,h,h′ is a univariate Gaussian N (0, σ2∥Jd/d ′′ (x;W)[h]∥2∥Jd ′′−1/d′(x;W[+Ud′′−1])[∶, h ′]∥2).
  Then, by applying a standard Gaussian tail bound we have that with probability 1 − δ̂ D2H2 over the draws of Ud′′ conditioned on Ud′′−1, each of these quantities is bounded as:
  ∣yd′′,h,h′ ∣ ≤ σ∥J d/d′′ (x;W)[h]∥∥Jd ′′−1/d′ (x;W[+Ud′′−1])[∶, h ′ ]∥
  √
  2 ln D2H2
  δ̂ (13)
  We simplify the bound on the right hand side a bit further so that it does not involve any Jacobian of layer d. Specifically, when d′′ < d, ∥Jd/d ′′ (x;W)[h]∥ can be written as the product of the spectral norm of the Jacobian d′ − 1/d′′ and the `2 norm of the hth row of Jacobian d − 1/d. Here, the latter can be upper bounded by the `2 norm of the hth row of Wd since the Jacobian (for a ReLU network) is essentially Wd but with some columns zerod out. When d = d′′, ∥Jd/d ′ (x;W)[h]∥ is essentially 1
  as the Jacobian is merely the identity matrix. Thus, we have:
  ∣yd′′,h,h′ ∣ ≤ ⎧⎪⎪⎪ ⎨ ⎪⎪⎪⎩ σ ∥wdh∥ ∥J d−1/d′′(x;W)∥ 2 ∥Jd ′′−1/d′(x;W[+Ud′′−1])[∶, h ′]∥
  √ 4 ln DH
  δ̂ d′′ < d
  σ∥Jd ′′−1/d′(x;W[+Ud′′−1])[∶, h ′]∥ √
  4 ln DH δ̂
  d′′ = d
  By a union bound on all d′′, we then get that with probability 1 − δ̂ D
  over the draws of Ud, we can upper bound Equation 12 as:
  max h
  d
  ∑ d′′=1
  √
  ∑ h′
  (yd′′,h,h′) 2 ≤ σ ∥Jd−1/d ′ (x;W[+Ud′′−1])∥
  F
  √
  4 ln DH
  δ̂ +
  d−1 ∑
  d′′=d′+1 σmax h ∥wdh∥ ∥J
  d−1/d′′ (x;W)∥
  2 ∥Jd
  ′′−1/d′ (x;W[+Ud′′−1])∥
  F
  √
  4 ln DH
  δ̂
  By again applying a union bound for all d′, we get the above bound to hold simultaneously for all d′
  with probability at least 1 − δ̂. Then, by a similar argument as in the case of the perturbation bound on the output of each layer, we get the result of the lemma.
  PERTURBATION BOUND ON THE SPECTRAL NORM OF THE JACOBIAN d/d′ . Again, we split this term and apply triangle equality as follows:
  ∣∥Jd/d ′ (x;W)∥ 2 − ∥Jd/d ′ (x;W[+Ud])∥ 2 ∣ ≤ ∥Jd/d ′ (x;W) − Jd/d ′ (x;W[+Ud])∥
  2
  ≤ XXXXXXXXXXXXXXXXXXX d ∑ d′′=1 ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ Jd/d ′ (x;W[+Ud′′]) − J d/d′ (x;W[+Ud′′−1]) ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶ ∶=Yd′′ ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ XXXXXXXXXXXXXXXXXXX2
  ≤ d
  ∑ d′′=1
  ∥Yd′′∥2 (14)
  Here, we have defined Yd′′ to be the matrix that corresponds to the difference in the Jacobian d/d′ brought about by perturbaing the the d′′th weight matrix, given that the first d′′ − 1 matrices have already been perturbed.
  As argued before, under the frozen activation states, when we perturb the weight matrices from 1 uptil d′, since these matrices are not involved in the Jacobian d/d′, fortunately, the Jacobian d/d′ is not perturbed (as the set of active weights in d/d′ are the same when we perturbW asW[+Ud′]). So, we will only need to bound Yd′′ for d′′ > d′.
  Recall that we can exapnd Yd′′ for d′′ > d′, yd′′,h,h′ as the product of i) Jacobian d/d′′ ii) the perturbation matrix Ud′′ and iii) the Jacobian d′/d′′ − 1 for the perturbed network10:
  Yd′′ =
  Hd×Hd′′ ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ Jd/d ′′ (x;W) Hd′′×Hd′′−1 ³·µ Ud′′ Hd′′−1×Hd′ ³¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹·¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹µ Jd ′′−1/d′
  (x;W[+Ud′′−1]) ´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶
  spherical Gaussian
  Now, the spectral norm of Yd′′ is at most the products of the spectral norms of each of these three matrices. Using Lemma B.3, the spectral norm of the middle term Ud′′ can be bounded by σ √
  2H ln 2DH δ̂ with high probability 1 − δ̂ D over the draws of Ud′′ . 11
  We will also decompose the spectral norm of the first term so that our final bound does not involve any Jacobian of the dth layer. When d′′ = d, this term has spectral norm 1 because the Jacobian d/d is essentially the identity matrix. When d′′ < d, we have that ∥Jd/d ′′ (x;W)∥
  2 ≤
  ∥Jd/d−1(x;W)∥ 2 ∥Jd−1/d ′′ (x;W)∥ 2 . Furthermore, since, for a ReLU network, Jd/d−1(x;W) is effectively Wd with some columns zerod out, the spectral norm of the Jacobian is upper bounded by the spectral norm Wd.
  Putting all these together, we have that with probability 1 − δ̂ D over the draws of Ud′′ , the following holds good:
  ∥Yd′′∥2 ≤ ⎧⎪⎪⎪ ⎨ ⎪⎪⎪⎩ σ ∥Wd∥2 ∥J d−1/d′′(x;W)∥ 2 ∥Jd ′′−1/d′(x;W[+Ud′′−1])∥ 2
  √ 2H ln 2DH
  δ̂ d′′ < d
  σ ∥Jd ′′−1/d′(x;W[+Ud′′−1])∥
  2
  √ 2H ln 2DH
  δ̂ d′′ = d
  By a union bound, we then get that with probability 1 − δ̂ over the draws of Ud, we can upper bound Equation 14 as:
  d
  ∑ d′′=1
  ∥Yd′∥2 ≤σ ∥J d′′−1/d′
  (x;W[+Ud′′−1])∥ 2
  √
  2H ln 2DH
  δ̂
  + σ d−1 ∑
  d′′=d′+1 ∥Wd∥2 ∥J
  d−1/d′′ (x;W)∥
  2 ∥Jd
  ′′−1/d′ (x;W[+Ud′′−1])∥
  2
  √
  2H ln 2DH
  δ̂
  Note that the above bound simultaneously holds over all d′ (without the application of a union bound). Finally we get the result of the lemma by a similar argument as in the case of the perturbation bound on the output of each layer.
  10Again, note that the below succinct formula works even for corner cases like d′′ = d′ or d′′ = d. 11Although Lemma B.3 applies only to the case where Ud′′ is a H ×H matrix, it can be easily extended to the corner cases when d′′ = 1 or d′′ =D. When d′′ = 1, Ud′′ would be a H ×N matrix, where H > N ; one could imagine adding more random columns to this matrix, and applying Lemma B.3. Since adding columns does not reduce the spectral norm, the bound on the larger matrix would apply on the original matrix too. A similar argument would apply to d′′ =D, where the matrix would be K ×H .
sections.heading: F PROOF FOR THEOREM 4.1
sections.text: Below, we present our main result for this section, a generalization bound on a class of networks that is based on certain norm bounds on the training data. We provide a more intuitive presentation of these bounds after the proof in Appendix F.3. Theorem. 4.1 For any δ > 0, with probability 1 − δ over the draw of samples S ∼ Dm, for anyW , we have that:
  Pr(x,y)∼D [L0(f (x;W) , y)] ≤Pr(x,y)∼S [Lγclass(f (x;W) , y)]+
  +O ⎛ ⎜ ⎝ D ⋅
  ¿ Á ÁÀ 1
  m − 1 ⋅ (2
  D
  ∑ d=1
  ∥Wd −Zd∥ 2 1
  (σ⋆)2 + ln
  Dm δ ) ⎞ ⎟ ⎠
  where 1 σ⋆
  is O ( √ H ⋅
  √
  ln (DH √ m) ×max{Blayer-`2 ,Bpreact,Bjac-row-`2 ,Bjac-spec,Boutput}), where:
  Blayer-`2 ∶= O ⎛
  ⎝ max 1≤d<D
  ∑ d d′=1 ζ ⋆ d/d′α ⋆ d′−1
  α⋆d
  ⎞
  ⎠
  Bpreact ∶= O ⎛
  ⎝ max 1≤d<D
  ∑ d d′=1 ζ ⋆ d/d′α ⋆ d′−1
  √ Hγ⋆d
  ⎞
  ⎠
  Bjac-row-`2 ∶= O ⎛
  ⎝ max 1≤d<D max 1≤d′<d≤D
  ζ⋆d−1/d′ + ∥Wd∥2,∞∑ d−1 d′′=d′+1 ψ ⋆ d−1/d′′ζ ⋆ d′′−1/d′
  ζ⋆ d/d′
  ⎞
  ⎠
  Bjac-spec ∶= O ⎛
  ⎝ max 1≤d<D max 1≤d′<d≤D
  ψ⋆d−1/d′ + ∥Wd∥2∑ d−1 d′′=d′+1 ψ ⋆ d−1/d′′ψ ⋆ d′′−1/d′
  ψ⋆ d/d′
  ⎞
  ⎠
  Boutput ∶= O ⎛
  ⎝
  ∑ D d=1 ζ ⋆ D/dα ⋆ d−1
  √ Hγclass
  ⎞
  ⎠
  where, α⋆d ∶= max (max(x,y)∈S ∥f
  d (x;W)∥ ,1) is an upper bound on the `2 norm of the output of each hidden layer d = 0,1,⋯,D − 1 on the training data. Note that for layer 0, this would correspond to the `2 norm of the input.
  γ⋆d ∶= min(x,y)∈S minh ∣f d (x;W) [h]∣ is a lower bound on the absolute values of the pre-activations for each layer d = 1,⋯,D on the training data.
  ζ⋆d/d′ ∶= max(max(x,y)∈S ∥J d/d′(x;W)∥
  2,∞ ,1) is an upper bound on the row `2 norms of the
  Jacobian for each layer d = 1,2,⋯,D, and d′ = 1,⋯, d on the training data.
  ψ⋆d/d′ ∶= max (max(x,y)∈S ∥J d/d′(x;W)∥
  2 ,1) is an upper bound on the spectral norm of the Jaco-
  bian for each layer d = 1,2,⋯,D, and d′ = 1,⋯, d on the training data.
sections.heading: F.1 NOTATIONS.
sections.text: To make the presentation of our proof cleaner, we will set up some notations. First, we use C ⋆ to denote the ‘set’ of constants related to the norm bounds on training set defined in the Theorem above. (Here we use the term set loosely, like we noted in the previous section.) Based on these
  training set related constants, we also define C † to be the following constants corresponding to weaker norm-bounds related to the test data:
  1. α†d ∶= 2α ⋆ d, for each hidden layer d = 0,1,⋯,D − 1, (we will use this to bound `2 norms of
  the outputs of the layers of the network on a test input)
  2. γ†d ∶= γ ⋆ d/2 for each layer d = 1,⋯,D, (we will use this to bound magnitudes of the
  preactivations values of the network on a test input).
  3. ζ† d/d′ ∶= 2ζ ⋆ d/d′ for each layer d = 1,2,⋯,D, and d ′ = 1,⋯, d (we will use this to bound `2 norms of rows in the Jacobians of the network for a test input)
  4. ψ† d/d′ ∶= 2ψ ⋆ d/d′ for each layer d = 1,2,⋯,D, and d ′ = 1,⋯, d (we will use this to bound spectral norms of the Jacobians of the network for a test input)
  Note about (abuse of) notation: We reiterate a point about our notation which we also made in Appendix E. We call C ⋆ and C † a ‘set’ to denote a group of related constants by a single symbol. Each element in this set has a particular semantic associated with it, unlike the standard notation of a set.
  Now, for any given set of constants C , for a particular weight configurationW , and for a given input x, we define the following event which holds when the network satisfies certain norm-bounds defined by the constants C (that are favorable for noise-resilience). Definition F.1. For a set of constants C , for network parametersW and for any input x, we define NORM-BOUND(W,C ,x) to be the event that all the following hold good:
  1. for all αd ∈ C , ∥fd (x;W)∥ < αd (Output of the layer does not have too large an `2 norm).
  2. for all γd ∈ C , minh ∣fd (x;W) [h]∣ > γd. (Pre-activation values are not too small).
  3. for all ζd/d′ ∈ C , maxh ∥Jd/d ′ (x;W)[h]∥ < ζd/d′ (Rows of Jacobian do not have too large
  an `2 norm).
  4. for all ψd/d′ ∈ C , ∥Jd/d ′ (x;W)∥
  2 < ψd/d′ (Jacobian does not have too large a spectral
  norm).
  NOTE: (Similar to a note under Definition E.1) A subtle point in the above definition (which we will make use of, to state our theorems) is that if we supply only a subset of C to the above event, NORM-BOUND(W, ⋅,x) then it would denote the event that only those subset of properties satsify the respective norm bounds.
sections.heading: F.2 PROOF FOR THEOREM 4.1
sections.text: Proof. To apply the framework, we will have to first define and order the input-dependent properties ρ and the corresponding margins ∆⋆ used in Theorem 3.1. We will define these properties in terms of the following functions: ∥fd (x;W)∥, fd (x;W) [h], ∥Jd/d ′ (x;W)[h]∥ and ∥Jd/d ′ (x;W)∥
  2 .
  Following this definition, we will create an ordered grouping of these properties.
  Definition F.2. For ReLU networks, we enumerate the input-dependent properties (on the left below) and their corresponding margins (on the right below) denoted with a superscript ∆:
  2α⋆d − ∥f d (x;W)∥ α▵d ∶= α ⋆ d for d = 0,1,2,⋯,D − 1
  ∣fd (x;W) [h]∣ − γ⋆d 2
  γ▵d ∶= γ⋆d 2
  for d = 1,2,⋯,D − 1 for all possible h 2ζ⋆d/d′ − ∥J d/d′(x;W)[h]∥ ζ▵d/d′ ∶= ζ ⋆ d/d′ for d = 1,⋯,D d ′ = 1,⋯, d − 1 for all possible h
  2ψ⋆d/d′ − ∥J d/d′(x;W)∥ 2 ψ▵d/d′ ∶= ψ ⋆ d/d′ for d = 1,⋯,D d ′ = 1,⋯, d − 1
  and for the output layer D: f (x;W)[y] −max
  j≠y f (x;W)[j] γ▵D ∶= γclass
  We will use the notation C ▵ to denote the sets of all margin terms defined on the right side above, and C ▵/2 to denote the values in that set divided by 2.
  ON THE CHOICE OF THE ABOVE FUNCTIONS AND MARGIN VALUES. Recall that for a specific input-dependent property ρ and its margin ∆⋆, the condition in Equation 1 requires that ρ(W,x, y) > ∆⋆. When we generalize these conditions in Theorem C.1, we will assume that these are satisfied on the training data, and we show that on the test data the approximate version of these conditions, namely ρ(W,x, y) > 0 hold. Below, we show what these conditions and their approximate versions translate to, in terms of norm-bounds on ∥fd (x;W)∥, fd (x;W) [h], ∥Jd/d ′ (x;W)[h]∥ and ∥Jd/d ′ (x;W)∥
  2 ;
  we encapsulate our statements in the following fact for easy reference later in our proof.
  Fact F.1. When ρ,∆⋆ correspond to 2α⋆d − ∥f d (x;W)∥ and α▵d, the conditions translate to upper bounds on the `2 norm of the layer as:
  ρ(W,x, y) > ∆⋆ ≡∥fd (x;W)∥ < α⋆d
  ρ(W,x, y) > 0 ≡ ∥fd (x;W)∥ < 2α⋆d = α † d
  When ρ,∆⋆ correspond to ∣fd (x;W) [h]∣ − γ ⋆ d
  2 and γ▵d ∶= γ⋆d 2
  , then the conditions translate to lower bounds on the pre-activation values as:
  ρ(W,x, y) > ∆⋆ ≡∣fd (x;W) [h]∣ > γ⋆d
  ρ(W,x, y) > 0 ≡ ∣fd (x;W) [h]∣ > γ⋆d/2 = γ † d
sections.heading: When ρ,∆⋆ correspond to 2ζ⋆d/d′ − ∥J
sections.text: d/d′(x;W)[h]∥ and ζ▵d/d′ , the conditions translate to upper bounds on the row `2 norm of the Jacobian as:
  ρ(W,x, y) > ∆⋆ ≡∥Jd/d ′ (x;W)[h]∥ < ζ⋆d/d′
  ρ(W,x, y) > 0 ≡∥Jd/d ′ (x;W)[h]∥ < 2ζ⋆d/d′ = ζ † d/d′
  When ρ,∆⋆ correspond to 2ψ⋆d/d′ − ∥J d/d′(x;W)∥ 2 and ψ▵d/d′ , the conditions translate to upper bounds on the spectral norms of the Jacobian as:
  ρ(W,x, y) > ∆⋆ ≡ ∥Jd/d ′ (x;W)∥ 2 < ψ⋆d/d′
  ρ(W,x, y) > 0 ≡ ∥Jd/d ′ (x;W)∥ 2 > 2ψ⋆d/d′ = ψ † d/d′
  When ρ,∆⋆ correspond to f (x;W)[y] −maxj≠y f (x;W)[j] and γ▵D, the conditions translate to lower bounds on the margin:
  ρ(W,x, y) > ∆⋆ ≡f (x;W)[y] −max j≠y f (x;W)[j] > 0
  ρ(W,x, y) > 0 ≡f (x;W)[y] −max j≠y f (x;W)[j] > γclass
  GROUPING AND ORDERING THE PROPERTIES. Now to apply the abstract generalization bound in Theorem 3.1, recall that we need to come up with an ordered grouping of the functions above such that we can realize the constraint given in Equation 2. Specifically, this constraint effectively required that, for a given input, the perturbation in the properties grouped in a particular set be small, given that all the properties in the preceding sets satisfy the corresponding conditions on them. To this end, we make use of Lemma E.1 where we have proven perturbation bounds relevant to the properties we have defined above. Our lemma also naturally induces dependencies between these properties in a way that they can be ordered as required by our framework.
  The order in which we traverse the properties is as follows, as dictated by Lemma E.1. We will go from layer 0 uptil D. For a particular layer d, we will first group the properties corresponding to the
  spectral norms of the Jacobians of that layer whose corresponding margins are {ψ▵d/d′} d d′=1. Next, we will group the row `2 norms of the Jacobians of layer d, whose corresponding margins are {ζ▵d/d′} d d′=1. Followed by this, we will have a singleton set of the layer output’s `2 norm whose corresponding margin is α▵d. We then will group the pre-activations of layer d, each of which has the corresponding margin γ▵d . For the output layer, instead of the pre-activations or the output `2 norm, we will consider the margin-based property we have defined above. 12 13 Observe that the number of sets R that we have created in this manner, is at most 4D since there are at most 4 sets of properties in each layer.
  PROVING CONSTRAINT IN EQUATION 2. Recall the constraint in Equation 2 that is required by our framework. For any r, the rth set of properties need to satisfy the following statement:
  if ∀q < r,∀l, ρq,l(W,x, y) > 0 then
  PrU∼N (0,σ2I)[∀l ∣ρr,l(W + U ,x, y) − ρr,l(W,x, y)∣ > ∆r,l(σ)
  2 and
  ∀q<r,∀l ∣ρq,l(W + U ,x, y) − ρq,l(W,x, y)∣< ∆q,l(σ)
  2 ] ≤
  1
  (R + 1) √ m . (2)
  Furthermore, we want the perturbation bounds ∆r,l(σ) to satisfy ∆r,l(σ⋆) ≤ ∆⋆r,l, where σ ⋆ is the standard deviation of the parameter perturbation chosen in the PAC-Bayesian analysis.
  The next step in our proof is to show that our choice of σ⋆, and the input-dependent properties, all satisfy the above requirements. To do this, we instantiate Lemma E.1 with σ = σ⋆ as in Theorem 4.1 (choosing appropriate constants), δ̂ = 1
  4D √ m
  and Ĉ = C ▵/2. Then, it can be verified that the values
  of the perturbation bounds in Ĉ ′ in Lemma E.1 can be upper bounded by the corresponding value in C ▵/2. In other words, we have that for our chosen value of σ, the perturbations in all the properties and the output of the network can be bounded by the constants specified in C ▵/2. Succinctly, let us say:
  Ĉ ′ ≤ C ▵/2 (15)
  Given that these perturbation bounds hold for our chosen value of σ, we will focus on showing that a constraint of the form Equation 2 holds for the row `2 norms of the Jacobians d/d′ for all d′ < d. A similar approach would apply for the other properties.
  First, we note that the sets of properties preceding the ones corresponding to the row `2 norms of Jacobian d/d′, consists of all the properties upto layer d − 1. Therefore, the precondition for Equation 2 which is of the form ρ(W,x, y) > 0 for all the previous properties ρ, translates to norm bound on these properties involving the constants C †d−1 as discussed in Fact F.1. Succinctly, these norm bounds can be expressed as NORM-BOUND(W + U ,C †d−1,x).
  Given that these norm bounds hold for a particular x, our goal is to argue that the rest of the constraint in Equation 2 holds. To do this, we first argue that given these norm bounds, if PERT-BOUND(W + U ,C ▵d−1/2,x) holds, then so does UNCHANGED-ACTSd−1(W + U ,x). This is because, the event PERT-BOUND(W + U ,C ▵d−1/2,x) implies that the pre-activation values of layer d − 1 suffer a perturbation of at most γ▵d−1/2 = γ ⋆ d−1/4 i.e., maxh ∣f
  d−1 (x;W + U) [h]−fd−1 (x;W) [h]∣ ≤ γ⋆d−1/4. However, since NORM-BOUND(W,C †d−1,x) holds, we have that the preactivation values of this layer have a magnitude of at least γ†d−1 = γ ⋆ d−1/2 before perturbation i.e., minh ∣f
  d−1 (x;W) [h]∣ ≥ γ⋆d−1/2. From these two equations, we have that the hidden units even at layer d−1 of the network do not change their activation state (i.e., the sign of the pre-activation does not change) under this perturbation. We can similarly argue for the layers below d − 1, thus proving that UNCHANGED-ACTSd−1(W + U ,x) holds under PERT-BOUND(W + U ,C ▵d−1/2,x).
  Then, from the above discussion on the activation states, and from Equation 15, we have that Lemma E.1 boils down to the following inequality, when we plug σ = σ⋆:
  12For layer 0, the only property that we have defined is the `2 norm of the input. 13Note that the Jacobian for d/d is nothing but an identity matrix regardless of the input datapoint; thus we do not need any generalization analysis to bound its value on a test datapoint. Hence, we ignore it in our analysis, as can be seen from the list of properties that we have defined.
  PrU[¬PERT-BOUND(W + U ,{ζ▵d/d′/2} d−1 d′=1,x) ∧ PERT-BOUND(W + U ,C ▵ d−1/2,x)] ≤
  1
  4D √ m
  First note that this inequality has the same form as the constraint required by Equation 2 in our framework. Specifically, in place of the generic perturbation bound ∆(σ⋆), we have ζ▵d/d′ . Furthermore, recall that our abstract generalization theorem in Theorem 3.1 required that the perturbation bound ∆r,l(σ ⋆) be smaller than the corresponding margin ∆⋆r,l. Since the margin here is ζ ▵ d/d′ , this is indeed the case. Through identical arguments for the other sets of input-dependent properties that we have defined, we can similarly show how the constraint in Equation 2 holds.
  Thus, the input-dependent properties we have devised satisfy all the requirements of our framework, allowing us to apply Theorem 3.1, with R ≤ 4D. Here, we use a prior centered at the random initialization Z; Lemma B.4 helps simplify the KL-divergence term between the posterior centered at W and the prior at the random initialization Z .
  COVERING ARGUMENT. To complete our proof, we need to take one more final step. First note that the guarantee in Theorem 3.1 requires that both σ⋆ and the margin constants ∆⋆r,l in Equation 1 are all chosen before drawing the training dataset. Thus, to apply this bound in practice, one would have to train the network on multiple independent draws of the training dataset (roughly O(1/δ) many draws), and then compute norm-bounds on the input-dependent properties across all these runs, and then choose the largest σ⋆ based on all these norm-bounds. We emphasize that theoretically speaking, this sort of a bound is still a valid generalization bound that essentially applies to a restricted, normbounded class of neural networks. Indeed, the hope is that the implicit bias of stochastic gradient descent ensures that the networks it learns do satisfy these norm-bounds on the input-dependent properties across most draws of the training dataset.
  But for practical purposes, one may not be able to empirically determine norm-bounds that hold on 1 − δ of the training set draws, and one might want to get a generalization bound based on norm-bounds that hold on just a single draw. We take this final step in our proof in order to derive such a generalization bound. We do this via the standard theoretical trick of ‘covering’ the space of all possible norm-bounds. That is, consider the set of ≤ 4D2 different constants in C ⋆ (that bound the different norms), based on which we choose σ⋆. We will create a ‘grid’ of constants (independent of the training data) such that for any particular run of the algorithm, we can find a point on this grid (that corresponds to a configuration of the constants) for which the norm-bounds still hold for that run. These bounds will be looser, but only by a constant multiplicative factor. This will ensure that the bound resulting from choosing σ⋆ based on this point on the grid, is only a constant factor looser than choosing σ⋆ based on the actual norm-bounds for that training set. Then, we will instantiate Theorem 3.1 for all the points on the grid, and apply a union bound over all of these to get our final bound.
  We create the grid based as follows. Observe that the bound we get from Boutput is at least as large as α⋆d−1/( √ Hγclass). Then, for any value of α⋆d−1 = Ω ( √ Hγclass √ m), we will choose a value of 1/σ⋆ that is Ω ( √ m), rendering the final bound vacuous. Also note that α⋆d−1 ≥ 1. Thus, we will focus on the interval [1,O ( √ Hγclass √ m)], and grid it based on the points 1,2,4,8,⋯,O ( √ Hγclass √ m). Observe that any value of α⋆d−1 can be approximated by one of these points within a multiplicative factor of 2. Furthermore, this gives rise to at most O (log2 √ Hγclass √ m) many points on this grid. Next, for a given point on this grid, by examining Blayer-`2 and Boutput, we can similarly argue how the range of values of ζ⋆d/d′ is limited between 1 and a polynomial in terms of H and γclass; this range of values can similarly be split into a grid. Then, by examining Bpreact, we can arrive at a similar grid for the quantity 1/γ⋆d ; by examining Bjac-row-`2 , we can get a grid for ψ ⋆ d/d′ too. In this manner, we can grid the space of all possible configurations of the constants into at most (poly(H,D,m,γclass))4D 2 many points (since there are not more than 4D2 different constants).
  For any given run, we can pick a point from this grid such that the norm-bounds are loose only by a constant multiplicative factor. Finally, we apply Theorem 3.1 for each of these grids by setting the failure probability to be δ/(poly(H,D,m,γclass))4D 2 , and then combine them via a union bound.
  Note, that the resulting bound would have a √ log (poly(H,D,m,γclass)) 4D2
  δ / √ m term, that would only
  result in a √
  D2 log poly(H,D,m,γclass) m term that does not affect our bound in an asymptotic sense.
sections.heading: F.3 ADDITIONAL EXPERIMENTS.
sections.text: In this section, we provide more detailed demonstration of the dependence of the terms in our bound on the depth/width of the network. In all the experiments, including the ones in the main paper (except the one in Figure 2 (b)) we use SGD with learning rate 0.1 and mini-batch size 64. We train the network on a subset of 4096 random training examples from the MNIST dataset to minimize cross entropy loss. We stop training when we classify at least 0.99 of the data perfectly, with a margin of γclass = 10. In Figure 2 (b) where we train networks of depth D = 28, the above training algorithm is quite unstable. Instead, we use Adam with a learning rate of 10−5 until the network achieves an accuracy of 0.95 on the training dataset. Finally, we note that all logarithmic transformations in our plots are to the base 10.
  In Figure 3 we show how the norm-bounds on the input-dependent properties of the network do not scale as large as the product of spectral norms.
  ∏ 10 d′=d ∥Wd∥2 = 2
  10−d. Right: Each black point corresponds to a particular training example x, and has y-value equal to the `2 norm of the output of layer d for that datapoint. A naive upper bound on this value would be ∥x∥∏dd′=1 ∥Wd∥2 ≈ 10 ⋅ 2
  d, which would be at least 100 times larger than the observed value for d = 10.
  For the remaining experiments in this section, we will present a slightly looser bound than the one presented in our main result, motivated by the fact that computing our actual bound is expensive as it involves computing spectral norms of Θ(D2) Jacobians on m training datapoints. We note that even this looser bound does not have a dependence on the product of spectral norms, and has similar overall dependence on the depth.
  Specifically, we will consider a bound that is based on a slightly modified noise-resilience analysis. Recall that in Lemma E.1, when we considered the perturbation in the row `2 norm Jacobian d/d′, we bounded Equation 13 in terms of the spectral norms of the Jacobians. Instead of taking this route, if we retained the bound in Equation 13, we will get a slightly different upper bound on the perturbation of the Jacobian row `2 norm as:
  ζ̂ ′d/d′ ∶= σ d
  ∑ d′′=d′+1
  ∥Jd/d ′′ (x;W)∥
  F (∥Jd
  ′′−1/d′ (x;W)∥
  F + ζ̂d′′−1/d′
  √ H)
  √
  2 ln D2H2
  δ̂
  By using this bound in our analysis, we can ignore the spectral norm terms ψ⋆d/d′ and derive a generalization bound that does not involve these terms. However, we would now have O(D2) conditions instead of O(D). This is because, the perturbation bound for the row norms of Jacobian d/d′ now depends on the row norms of Jacobian d/d′′, for all d′′ > d′. Thus, the row `2 norms of these Jacobians must be split into separate sets of properties, and the bound on them generalized one after the other (instead of grouped into one set and generalized all at one go as before). This would
  give us a similar generalization bound that is looser by a factor of D, does not involve Bjac-spec, and where Bjac-row-`2 is redefined as:
  Bjac-row-`2 ∶= O ⎛
  ⎝ max 1≤d<D max 1≤d′<d≤D
  ∑ d d′′=d′+1 ζ ⋆ d−1/d′′ζ ⋆ d′′−1/d′
  ζ⋆ d/d′
  ⎞
  ⎠
  All other terms remain the same. In the rest of the discussion, we plot this generalization bound that is looser by a D factor, but still does not depend on the product of the spectral norms. In Figure 4 we show how the quantities in this bound and the bound itself varies with depth, for a network of H = 1280, wider than what we considered in Figure 1.
  In Figure 5 and Figure 6 we show log-log (note that here even the x-axis has been transformed logarithmically) plots of all the quantities for networks of varying width and D = 8 and D = 14 respectively. Here, we observe that Bjac-row-`2 is width-independent. On the other hand Blayer-`2 and the product-of-spectral-norm term mildly decrease with width; Boutput decreases with width at the rate of 1/ √ H .
  As far as the term Bpreact is concerned, recall from our discussion in the main paper that the minimum pre-activation value γ⋆d of the network tends to be quite small in practice (and can be rounded to zero due to precision issues). Therefore the term Bpreact can be arbitrarily large and exhibit considerable variance across different widths/depths and different training runs. On the other hand, interestingly, the hypothetical variation median-Bpreact decreases with width at the rate of 1/ √ H , while 5%-Bpreact increases with a √ H dependence on width.
  Theoretically speaking, as far as the width-dependence is concerned, the best-case scenario for Bpreact can be realized when the preactivation values of each layer (which has a total `2 norm that is width-independent in practice) are equally spread out across the hidden units. Then we will have that the smallest pre-activation value to be as large as Ω(1/ √ H).
sections.heading: G COMPARISON OF OUR NOISE-RESILIENCE CONDITIONS WITH RELATED WORK
sections.text: Recall from the discussion in the introduction in the main paper that, prior works (Neyshabur et al., 2017; Arora et al., 2018) have also characterized noise resilience in terms of conditions on the interactions between the activated weight matrices. Below, we discuss the conditions assumed by these works, which parallel the conditions we have studied in our paper (such as the bounded `2 norm in each layer).
  There are two main high level similarities between the conditions studied across these works. First, these conditions – all of which characterize the interactions between the activated weights matrices in the network – are assumed only for the training inputs; such an assumption implies noise-resilience of the network on training inputs. Second, there are two kinds of conditions assumed. The first kind allows one to bound the propagation of noise through the network under the assumption that the activation states do not flip; the second kind allows one to bound the extent to which the activation states do flip.
  CONDITIONS IN NEYSHABUR ET AL. (2017) Using noise-resilience conditions assumed about the network on the training data, Neyshabur et al. (2017) derive a PAC-Bayes based generalization bound on a stochastic network. The first condition in Neyshabur et al. (2017) characterizes how the Jacobians of different parts of the network interact with each other. Specifically, consider layers d, d′ and d′′ such that d′′ ≤ d′ ≤ d. Then, consider the Jacobian of layer d′ with respect to layer d′′ and the
  Jacobian of layer d with respect to d′. Then, they require that ∥Jd/d ′ (x;W)∥
  F ∥Jd ′−1/d′′(x;W)∥ F =
  O(∥Jd/d ′′ (x;W)∥
  F ). This specific condition allows one to bound how the noise injected into the
  parameters propagate through the network under the assumption that the activation states do not flip. In our paper, we pick an orthogonal approach by assuming an upper bound on the Jacobian `2 norms and the layer output norms, which allows us to bound the propagation of noise under unchanged activation states.
  The second condition in Neyshabur et al. (2017) is that under a noise of variance σ2, the number of units that flip their activation state in a particular layer must be bounded as O(Hσ) i.e., smaller the noise, the smaller the proportion of units that flip their activation state. This condition is similar to (although milder than) our lower bounds on the magnitudes of the pre-activation values (which allow us to pick a sufficiently large noise that does not flip the activation states).
  Note that a bound on the Jacobian norms corresponds to a bound on the weights input to the active units in the network. However, since Neyshabur et al. (2017) allow a few units to flip activation states, they additionally require a bound on the weights input to the inactive units too. Specifically, for every layer, the maximum row `2 norm of the weight matrix Wi is upper bounded in terms of the Frobenius norm of the Jacobian Jd/d−1(x;W).
  CONDITIONS IN ARORA ET AL. (2018) In contrast to our work and Neyshabur et al. (2017), Arora et al. (2018) use their assumed noise-resilience conditions to derive a bound on a compressed network. Another small technical difference here is that, the kind of noise analysed here is Gaussian noise injected into the activations of each layer of the network (and not exactly the weights).
  The first condition here characterizes the interaction between the Jacobian of layer d with respect to d′ and the output of layer d′. Specifically, this is a lower bound on the so-called ‘interlayer cushion’, which is evaluated as
  ∥Jd/d ′ (x;W)fd ′ (x;W)∥
  ∥Jd/d′(x;W)∥ F ∥fd′ (x;W)∥
  Essentially when the interlayer cushion is sufficiently large, it means that the output of layer d′ is well-aligned with the larger singular directions of the Jacobian matrix above it; as a result it can be shown that noise injected at/below layer d′ diminishes as it propagates through the weights above layer d′, assuming the activation states do not flip. Again, our analysis is technically orthogonal to this style of analysis as we bound the propogation of the noise under unchanged activation states assuming that the norms of the Jacobians and the layer outputs are bounded.
  Another important condition in Arora et al. (2018) is that of “interlayer smoothness” which effectively captures how far the set of activation states between two layers, say d′ and d, flip under noise. Roughly speaking, the assumption made here is that when noise is injected into layer d′, there is not much difference between a) the output of the dth layer with the activation states of the units in layers d′ until d frozen at their original state and b) the output of the dth layer with the activation states of the units in layers d′ to d allowed to flip under the noise. As stated before, this condition is a relaxed version of our condition that essentially implies that none of the activation states flip.
title: DETERMINISTIC PAC-BAYESIAN GENERALIZATION BOUNDS FOR DEEP NETWORKS VIA GENERALIZING NOISE-RESILIENCE