Stronger generalization bounds for deep nets via a compression approach

Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang

Introduction

A mystery about deep nets is that they generalize (i.e., predict well on unseen data) despite having far more parameters than the number of training samples. One commonly voiced explanation is that regularization during training –whether implicit via use of SGD Neyshabur et al. (2015c); Hardt et al. (2016) or explicit via weight decay, dropout Srivastava et al. (2014), batch normalization Ioffe and Szegedy (2015), etc. –reduces the effective capacity of the net. But Zhang et al. (2017) questioned this received wisdom and fueled research in this area by showing experimentally that standard architectures using SGD and regularization can still reach low training error on randomly labeled examples (which clearly won’t generalize).

Clearly, deep nets trained on real-life data have some properties that reduce effective capacity, but identifying them has proved difficult —at least in a quantitative way that yields sample size upper bounds similar to classical analyses in simpler models such as SVMs Bartlett and Mendelson (2002); Evgeniou et al. (2000); Smola et al. (1998) or matrix factorization Fazel et al. (2001); Srebro et al. (2005).

Qualitatively Hochreiter and Schmidhuber (1997); Hinton and Van Camp (1993) suggested that nets that generalize well are flat minima in the optimization landscape of the training loss and Hinton and Van Camp (1993) further discusses the connections to Minimum Description Length principle for generalization. Recently Keskar et al. (2016) show using experiments with different batch-sizes that sharp minima do correlate with higher generalization error. A quantitative version of “flatness” was suggested in (Langford and Caruana, 2001): the net’s output is stable to noise added to the net’s trainable parameters. Using PAC-Bayes bound (McAllester, 1998, 1999) this noise stability yielded generalization bounds for fully connected nets of depth $2$ . The theory has been extended to multilayer fully connected nets (Neyshabur et al., 2017b), although thus far yields sample complexity bounds much worse than naive parameter counting. (Same holds for the earlier Bartlett and Mendelson (2002); Neyshabur et al. (2015b); Bartlett et al. (2017); Neyshabur et al. (2017a); Golowich et al. (2017); see Figure 4). Another notion of noise stability —closely related to dropout and batch normalization—is stability of the output with respect to the noise injected at the nodes of the network, which was recently shown experimentally (Morcos et al., 2018) to improve in tandem with generalization ability during training, and to be absent in nets trained on random data. Chaudhari et al Chaudhari et al. (2016) suggest adding noise to gradient descent to bias it towards finding flat minima.

While study of generalization may appear a bit academic — held-out data easily establishes generalization in practice— the ultimate hope is that it will help identify simple, measurable and intuitive properties of well-trained deep nets, which in turn may fuel superior architectures and faster training. We hope the detailed study —theoretical and empirical—in the current paper advances this goal.

A simple compression framework (Section 2) for proving generalization bounds, perhaps a more explicit and intuitive form of the PAC-Bayes work. It also yields elementary short proofs of recent generalization results (Section 2.2).

Identifying new form of noise-stability for deep nets: the stability of each layer’s computation to noise injected at lower layers. (Earlier papers worked only with stability of the output layer.) Figure 1 visualizes the stability of network w.r.t. Gaussian injected noise. Formal statements require a string of other properties (Section 3). All are empirically studied, including their correlation with generalization (Section 6).

Using the above properties to derive efficient and provably correct algorithms that reduce the effective number of parameters in the nets, yielding generalization bounds that: (a) are better than naive parameter counting (Section 6) (b) depend on simple, intuitive and measurable properties of the network (Section 4) (c) apply also to convolutional nets (Section 5) (d) empirically correlate with generalization (Section 6).

The main idea is to show that noise stability allows individual layers to be compressed via a linear-algebraic procedure Algorithm 1. This results in new error in the output of the layer. This added error is “gaussian-like” and tends to get attenuated as it propagates to higher layers.

Other related works. Dziugaite and Roy (2017) use non-convex optimization to optimize the PAC-Bayes bound get a non-vacuous sample bound on MNIST. While very creative, this provides little insight into favorable properties of networks. Liang et al. (2017) have suggested Fisher-Rao metric, a regularization based on the Fisher matrix and showed that this metric correlate with generalization. Unfortunately, they could only apply their method to linear networks. Recently Kawaguchi et al. (2017) connects Path-Norm Neyshabur et al. (2015a) to generalization. However, the proved generalization bound depends on the distribution and measuring it requires vector operations on exponentially high dimensional vectors. Other works have designed experiments to empirically evaluate potential properties of the network that helps generalizationArpit et al. (2017); Neyshabur et al. (2017b); Dinh et al. (2017). The idea of compressing trained deep nets is very popular for low-power applications; for a survey see (Cheng et al., 2018).

Finally, note that the terms compression and stability are traditionally used in a different sense in generalization theory Littlestone and Warmuth (1986); Kearns and Ron (1999); Shalev-Shwartz et al. (2010). Our framework is compared to other notions in the remarks after Theorem 2.1.

(Notice, the classification loss corresponds to $\gamma=0$ .) Let $\hat{L}_{\gamma}$ denote empirical estimate of the margin loss. Generalization error is the difference between the two.

For most of the paper we assume that deep nets have fully connected layers, and use ReLU activations. We treat convolutional nets in Section 5. If the net has $d$ layers, we label the vector before activation at these layers by $x^{0}$ , $x^{1}$ , … $x^{d}$ for the $d$ layers where $x^{0}$ is the input to the net, also denoted simply $x$ . So $x^{i}=A^{i}\phi(x^{i-1})$ where $A^{i}$ is the weight matrix of the $i$ th layer. (Here $\phi(x)$ if $x$ is a vector applies the ReLU component-wise. The ReLU is allowed a trainable bias parameter, which is omitted from the notation because it has no effect on any calculations below.) We denote the number of hidden units in layer $i$ by $h^{i}$ and set $h=\max_{i=1}^{d}h^{i}$ . Let $f_{A}(x)$ be the function calculated by the above network.

Stable rank of a matrix $B$ is $\|B\|_{F}^{2}/\|B\|_{2}^{2}$ , where $\|\cdot\|_{F}$ denotes Frobenius norm and $\|\cdot\|_{2}$ denotes spectral norm. Note that stable rank is at most (linear algebraic) rank.

For any two layer $i\leq j$ , denote by $M^{i,j}$ the operator for composition of these layers and $J^{i,j}_{x}$ be the Jacobian of this operator at input $x$ (a matrix whose $p,q$ is the partial derivative of the $p$ th output coordinate with respect to the $q$ ’th input input). Therefore, we have $x^{j}=M^{i,j}(x^{i})$ . Furthermore, since the activation functions are ReLU, we have $M^{i,j}(x^{i})=J^{i,j}_{x^{i}}x^{i}$ .

Compression and Generalization

Our compression framework rests on the following obvious fact. Suppose the training data contains $m$ samples, and $f$ is a classifier from a complicated class (e.g., deep nets with much more than $m$ parameters) that incurs very low empirical loss. We are trying to understand if it will generalize. Now suppose we can compute a classifier $g$ with discrete trainable parameters much less than $m$ and which incurs similar loss on the training data as $f$ . Then $g$ must incur low classification error on the full distribution. This framework has the advantage of staying with intuitive parameter counting and to avoid explicitly dealing with the hypothesis class that includes $f$ (see note after Theorem 2.1). Notice, the mapping from $f$ to $g$ merely needs to exist, not to be efficiently computable. But in all our examples the mapping will be explicit and fairly efficient. Now we formalize the notions. The proofs are elementary via concentration bounds and appear in the appendix.

Let $f$ be a classifier and $G_{\mathcal{A}}=\{g_{A}|A\in\mathcal{A}\}$ be a class of classifiers. We say $f$ is ( $\gamma,S$ )-compressible via $G_{\mathcal{A}}$ if there exists $A\in\mathcal{A}$ such that for any $x\in S$ , we have for all $y$

We also consider a different setting where the compression algorithm is allowed a“helper string” $s$ , which is arbitrary but fixed before looking at the training samples. Often $s$ will contain random numbers. A simple example is to let $s$ be the random initialization used for training the deep net. Then compress the difference between the final weights and $s$ ; this can give better generalization bounds, similar to Dziugaite and Roy (2017). Other nontrivial examples appear later.

Suppose $G_{\mathcal{A},s}=\{g_{A,s}|A\in\mathcal{A}\}$ is a class of classifiers indexed by trainable parameters $A$ and fixed strings $s$ . A classifier $f$ is ( $\gamma,S$ )-compressible with respect to $G_{\mathcal{A},s}$ using helper string $s$ if there exists $A\in\mathcal{A}$ such that for any $x\in S$ , we have for all $y$

Suppose $G_{\mathcal{A},s}=\{g_{A,s}|A\in\mathcal{A}\}$ where $A$ is a set of $q$ parameters each of which can have at most $r$ discrete values and $s$ is a helper string. Let $S$ be a training set with $m$ samples. If the trained classifier $f$ is $(\gamma,S)$ -compressible via $G_{\mathcal{A},s}$ with helper string $s$ , then there exists $A\in\mathcal{A}$ with high probability over the training set,

Remarks: (1) The framework proves the generalization not of $f$ but of its compression $g_{A}$ . (An exception is if the two are shown to have similar loss at every point in the domain, not just the training set. This is the case in Theorem 2.2.) (2) The previous item highlights how our framework steps away away from uniform convergence framework, e.g., covering number arguments Dudley (2010); Anthony and Bartlett (2009). There, one needs to fix a hypothesis class independent of the training set. By contrast we have no hypothesis class, only a single neural net that has some specific properties (described in Section 3) on a single finite training set. But if we can compress this specific neural net to a simpler neural nets with fewer parameters then we can use covering number argument on this simpler class to get the generalization of the compressed net. (3) Issue (1) exists also in standard PAC-Bayes framework for deep nets (see tongue-in-cheek title of (Langford and Caruana, 2001)). They yield generalization bounds not for $f$ but for a noised version of $f$ (i.e., net given by $W+\eta$ , where $W$ is parameter vector of $f$ and $\eta$ is a noise vector). For us issue (1) could be fixed by showing that if $f$ satisfies the properties of Section 3 on training data then it satisfies them on the entire domain. This is left for future work.

A classifier with margin $\gamma$ can be compressed to one that has only $O(1/\gamma^{2})$ non-zero entries. For each coordinate $i$ , toss a coin with $\Pr[heads]=8c_{i}^{2}/\gamma^{2}$ and if it comes up heads set the coordinate to equal to $\gamma^{2}/8c_{i}$ (see Algorithm 2 in supplementary material). This yields a vector $\hat{c}$ with only $O(1/\gamma^{2})$ nonzero entries such that for any vector $u$ , with reasonable probability $|\hat{c}^{\top}u-c^{\top}u|\leq\gamma$ , so $\hat{c}$ and $c$ will make the same prediction. We can then apply Theorem 2.1 on a discretized version of $\hat{c}$ to show that the sparsified classifier has good generalization with $O(\log d/\gamma^{2})$ samples.

This compressed classifier works correctly for a fixed input $x$ with good probability but not high probability. To fix this, one can recourse to the “compression with fixed string” model. The fixed string is a random linear transformation. When applied to unit vector $x$ , it tends to equalize all coordinates and the guarantee $|\hat{c}^{\top}u-c^{\top}u|\leq\gamma$ can hold with high probability. This random linear transformation can be fixed before seeing the training data. Similar approach was discussed by Blum (2006) for linear classifiers. See Section A.2 in supplementary material for more details.

2 Example 2: Existing generalization bounds

Our compression framework gives easy and short proof of the generalization bounds of a recent paper; see appendix for slightly stronger result of Bartlett et al. (2017).

(Neyshabur et al. (2017a)) For a deep net with layers $A^{1},A^{2},\ldots A^{d}$ and output margin $\gamma$ on a training set $S$ , the generalization error can be bounded by

The second part of this expression ( $\sum_{i=1}^{d}\frac{\|A^{i}\|_{F}^{2}}{\|A^{i}\|_{2}^{2}}$ ) is sum of stable ranks of the layers, a natural measure of their true parameter count. The first part ( $\prod_{i=1}^{d}\|A^{i}\|_{2}^{2}$ ) is related to the Lipschitz constant of the network, namely, the maximum norm of the vector it can produce if the input is a unit vector. The Lipschitz constant of a matrix operator $B$ is just its spectral norm $\|B\|_{2}$ . Since the network applies a sequence of matrix operations interspersed with ReLU, and ReLU is $1$ -Lipschitz we conclude that the Lipschitz constant of the full network is at most $\prod_{i=1}^{d}\|A^{i}\|_{2}.$

To prove Theorem 2.2 we use the following lemma to compress the matrix at each layer to a matrix of smaller rank. Since a matrix of rank $r$ can be expressed as the product of two matrices of inner dimension $r$ , it has $2hr$ parameters (instead of the trivial $h^{2}$ ). (Furthermore, the parameters can be discretized via trivial rounding to get a compression with discrete parameters as needed by Definition 1.)

Let $r$ be the rank of $\hat{A}$ . By construction, the maximum singular value of $\hat{A}-A$ is at most $\delta\|A\|_{2}$ . Since the remaining singular values are at least $\delta\|A\|_{2}$ , we have $\|A\|_{F}\geq\|\hat{A}\|_{F}\geq\sqrt{r}\delta\|A\|_{2}$ .∎

For each $i$ replace layer $i$ by its compression using the above lemma, with $\delta=\gamma(3\|x\|d\prod_{i=1}^{d}\|A^{i}\|_{2})^{-1}$ . How much error does this introduce at each layer and how much does it affect the output after passing through the intermediate layers (and getting magnified by their Lipschitz constants)? Since $A-\hat{A^{i}}$ has spectral norm (i.e., Lipschitz constant) at most $\delta$ , the error at the output due to changing layer $i$ in isolation is at most $\delta\|x^{i}\|\prod_{j=1}^{d}\|A^{j}\|_{2}\leq\gamma/3d$ .

A simple induction (see Neyshabur et al. (2017a) if needed) can now show the total error incurred in all layers is bounded by $\gamma$ . The generalization bound follows immediately from Theorem 2.1.

Noise stability properties of deep nets

This section introduces noise stability properties of deep nets that imply better compression (and hence generalization). They help overcome the pessimistic error analysis of our proof of Theorem 2.2: when a layer was compressed, the resulting error was assumed to blow up in a worst-case manner according to the Lipschitz constant (namely, product of spectral norms of layers). This hurt the amount of compression achievable. The new noise stability properties roughly amount to saying that noise injected at a layer has very little effect on the higher layers. Our formalization starts with noise sensitivity, which captures how an operator transmits noise vs signal.

If $M$ is a mapping from real-valued vectors to real-valued vectors, and ${\mathcal{N}}$ is some noise distribution then noise sensitivity of $M$ at $x$ with respect to ${\mathcal{N}}$ , is

The noise sensitivity of $M$ with respect to ${\mathcal{N}}$ on a set of inputs $S$ , denoted $\psi_{{\mathcal{N}},S}(M)$ , is the maximum of $\psi_{{\mathcal{N}}}(M,x)$ over all inputs $x$ in $S$ .

To illustrate, we examine noise sensitivity of a matrix (i.e., linear mapping) with respect to Gaussian distribution. Low sensitivity turns out to imply that the matrix has some large singular values (i.e., low stable rank), which give directions that can preferentially carry the “signal” $x$ whereas noise $\eta$ attenuates because it distributes uniformly across directions.

The noise sensitivity of a matrix $M$ at any vector $x\neq 0$ with respect to Gaussian distribution ${\mathcal{N}}(0,I)$ is exactly $\|M\|_{F}^{2}\|x\|^{2}/\|Mx\|^{2}$ , and at least its stable rank.

Thus noise sensitivity $\psi$ at $x$ is $\|M\|_{F}^{2}\|x\|^{2}/\|Mx\|^{2}$ , which is at least the stable rank $\|M\|_{F}^{2}/\|M\|_{2}^{2}$ since $\|Mx\|\leq\|M\|_{2}\|x\|$ . ∎

The above proposition suggests that if a vector $x$ is aligned to a matrix $M$ (i.e. correlated with high singular directions of $M$ ), then matrix $M$ becomes less sensitive to noise at $x$ . This intuition will be helpful in understanding the properties we define later to formalize noise stability.

The above discussion motivates the following approach. We compress each layer $i$ by an appropriate randomized compression algorithm, such that the noise/error in its output is “Gaussian-like”. If layers $i+1$ and higher have low sensitivity to this new noise, then the compression can be more extreme producing much higher noise. We formalize this idea using Jacobian $J^{i,j}$ , which describes instantaneous change of $M^{i,j}(x)$ under infinitesimal perturbation of $x$ .

Now we formalize the error-resilience properties. Section 6 reports empirical findings about these properties. The first is cushion, to be thought of roughly as reciprocal of noise sensitivity. We first formalize it for single layer.

The layer cushion of layer $i$ is similarly defined to be the largest number $\mu_{i}$ such that for any $x\in S$ , $\mu_{i}\|A^{i}\|_{F}\|\phi(x^{i-1})\|\leq\|A^{i}\phi(x^{i-1})\|$ .

Intuitively, cushion considers how much smaller the output $A^{i}\phi(x^{i-1})$ is compared to the upper bound $\|A^{i}\|_{F}\|\phi(x^{i-1})\|$ . Using argument similar to Proposition 3.1, we can see that $1/\mu_{i}^{2}$ is equal to the noise sensitivity of matrix $A^{i}$ at input $\phi(x^{i-1})$ with respect to Gaussian noise $\eta\sim{\mathcal{N}}(0,I)$ .

For any two layers $i\leq j$ , we define the interlayer cushion $\mu_{i,j}$ as the largest number such that for any $x\in S$ :

Furthermore, for any layer $i$ we define the minimal interlayer cushion as $\mu_{i\rightarrow}=\min_{i\leq j\leq d}\mu_{i,j}=\min\{1/\sqrt{h^{i}},\min_{i<j\leq d}\mu_{i,j}\}$ Note that $J_{x^{i}}^{i,i}=I$ and $\mu_{i,i}=1/\sqrt{h^{i}}$ .

Since $J^{i,j}_{x}$ is a linear transformation, a calculation similar to Proposition 3.1 shows that its noise sensitivity at $x^{i}$ with respect to Gaussian distribution $\mathcal{N}(0,I)$ is at most $\frac{1}{\mu_{ij}^{2}}$ .

The next property quantifies the intuitive observation on the learned networks that for any training data, almost half of the ReLU activations at each layer are active. If the input to the activations is well-distributed and the activations do not correlate with the magnitude of the input, then one would expect that on average, the effect of applying activations at any layer is to decrease the norm of the pre-activation vector by at most some small constant factor.

The activation contraction $c$ is defined as the smallest number such that for any layer $i$ and any $x\in S$ ,

We discussed how the interlayer cushion captures noise-resilience of the network if it behaves linearly, namely, when the set of activated ReLU gates does not change upon injecting noise. In general the activations do change, but the deviation from linear behavior is bounded for small noise vectors, as quantified next.

Let $\eta$ be the noise generated as a result of substituting weights in some of the layers before layer $i$ using Algorithm 1. We define interlayer smoothness $\rho_{\delta}$ to be the smallest number such that with probability $1-\delta$ over noise $\eta$ for any two layers $i<j$ any $x\in S$ :

In order to understand the above condition, we can look at a single layer case where $j=i+1$ :

where $\odot$ is the entry-wise product operator and $\nu=(\phi^{\prime}(x^{i}+\eta)-\phi^{\prime}(x^{i}))\odot(x^{i}+\eta)$ . Since the activation function is ReLU, $\phi^{\prime}(x^{i}+\eta)$ and $\phi^{\prime}(x^{i}))$ disagree whenever the perturbation has the opposite sign and higher absolute value compared to the input and hence $\|\nu\|\leq\|\eta\|$ .

Let us first see what happens if the perturbation $\nu$ is adversarially aligned to the weights:

where $r_{i+1}$ is the stable rank of layer $i+1$ . Therefore the interlayer smoothness from layer $i$ to layer $i+1$ is at least $\rho_{\delta}=\mu_{i+1}r_{i+1}/c$ . However, the noise generated from Algorithm 1 has similar properties to Gaussian noise (see Lemma 2). If $\nu$ behaves similar to Gaussian noise, then $\|A^{i+1}\nu\|\approx\|A^{i+1}\|_{F}\|\nu\|/\sqrt{h^{i}}$ and therefore $\rho_{\delta}$ is as high as $\sqrt{h^{i}\mu_{i+1}/c}$ . Since the layer cushion of networks trained on real data is much more than that of networks with random weights, $\rho_{\delta}$ is greater than one in this case. Another observation is that in practice, the noise is well-distributed and only a small portion of activations change from active to inactive and vice versa. Therefore, we can expect $\|\nu\|$ to be smaller than $\|\eta\|$ which further improves the interlayer smoothness. This appeared in Neyshabur et al. (2017b) that showed for one layer we can even use $\frac{\|\eta\|^{1.5}\|x^{j}\|}{\rho_{\delta}\|x^{i}\|}$ as the RHS of interlayer smoothness. Our current proof requires $1/\rho_{\delta}$ to be of order $1/d$ , this requirement can be removed (with $\rho_{\delta}$ appear in sample complexity) if we make the stronger assumption that the RHS is a lower order term in $\|\eta\|$ .

In general, for a single layer, $\rho_{\delta}$ captures the ratio of input/weight alignment to noise/weight alignment. Since the noise behaves similar to Gaussian, one expects this number to be greater than one for a single layer. When $j>i+1$ , the weights and activations create more dependencies. However, since these dependences are applied on both noise and input, we again expect that if the input is more aligned to the weights than noise, this should not change in higher layers. In Section 6, we show that the interlayer smoothness is indeed good: $1/\rho_{\delta}$ is a small constant.

Fully Connected Networks

We prove generalization bounds using for fully connected multilayer nets. Details appear in Appendix Section B.

where $\mu_{i}$ , $\mu_{i\rightarrow}$ , $c$ and $\rho_{\delta}$ are layer cushion, interlayer cushion, activation contraction and interlayer smoothness defined in Definitions 4,5,6 and 7 respectively.

To prove this we describe a compression of the net with respect to a fixed (random) string. In contrast to the deterministic compression of Lemma 1, this randomized compression ensures that the resulting error in the output behaves like a Gaussian. The proofs are similar to standard JL dimension reduction.

Note that the helper string of random matrices $M_{i}$ ’s were chosen and fixed before training set $S$ was picked. Each weight matrix is thus represented as only $k$ real numbers $\langle A,M_{i}\rangle$ for $i=1,2,...,k$ .

Lemma 2 can be used to upper bound the change in the network output after compressing a single layer if the activation patterns remain the same. For any layer, in the lemma statement take $x$ to be the input to the layer, $A$ to be the layer weight matrix, and $U$ to be the Jacobian of the network output with respect to the layer output. Network output before and after compression can then be calculated by the matrix products $UAx$ and $U\hat{A}x$ respectively. Hence, the lemma bounds the distance between network output before and after compression.

Next Lemma bounds the number of parameters of the compressed network resulting from applying Algorithm 1 to all the layer matrices of the net. The proof does induction on the layers and bounds the effect of the error on the output of the network using properties defined in Section 3.1.

(i) Empirically it has been observed that deep net training introduces fairly small changes to parameters as compared to the (random) initial weights Dziugaite and Roy (2017). We can exploit this by incorporating the random initial weights into the helper string and do the entire proof above not with the layer matrices $A^{i}$ but only the difference from the initial starting point. Experiments in Section 6 show this improves the bounds. (ii) Cushions and other quantities defined earlier are data-dependent, and required to hold for the entire training set. However, the proofs go through if we remove say $\zeta$ fraction of outliers that violate the definitions; this allows us to use more favorable values for cushion etc. and lose an additive factor $\zeta$ in the generalization error.

Convolutional Neural Networks

Now we sketch how to provably compress convolutional nets. (Details appear in Section C of supplementary.) Intuitively, this feels harder because the weights are already compressed— they’re shared across patches!

where $\mu_{i}$ , $\mu_{i\rightarrow}$ , $c$ , $\rho_{\delta}$ and $\beta$ are layer cushion, interlayer cushion, activation contraction, interlayer smoothness and well-distributed Jacobian defined in Definitions 4,8,6, 7 and 9 respectively. Furthermore, $s_{i}$ and $\kappa_{i}$ are stride and filter width in layer $i$ .

Let’s realize that obvious extensions of earlier sections fail. Suppose layer $i$ of the neural network is an image of dimension $n^{i}_{1}\times n^{i}_{2}$ and each pixel has $h^{i}$ channels, the size of the filter at layer $i$ is $\kappa_{i}\times\kappa_{i}$ with stride $s_{i}$ . The convolutional filter has dimension $h^{i-1}\times h^{i}\times\kappa_{i}\times\kappa_{i}$ . Applying matrix compression (Algorithm 1) independently to each copy of a convolutional filter makes number of new parameters proportional to $n^{i}_{1}n^{i}_{2}$ , a big blowup.

Compressing a convolutional filter once and reusing it in all patches doesn’t work because the interlayer analysis implicitly requires the noise generated by the compression to behave similar to a spherical Gaussian, but the shared filters introduce correlations. Quantitatively, using the fully connected analysis would require the error to be less than interlayer cushion value $\mu_{i\to}$ (Definition 5) which is at most $1/\sqrt{h^{i}n^{i}_{1}n^{i}_{2}}$ , and this can never be achieved from compressing matrices that are far smaller than $n^{i}_{1}\times n^{i}_{2}$ to begin with.

We end up with a solution in between fully independent and fully dependent: p-wise independence. The algorithm generates $p$ -wise independent compressed filters $\hat{A}_{(a,b)}$ for each convolution location $(a,b)\in[n^{i}_{1}]\times[n^{i}_{2}]$ . It results in $p$ times more parameters than a single compression. If $p$ grows logarithmically with relevant parameters, the filters behave like fully independent filters. Using this idea we can generalize the definition of interlayer margin to the convolution setting:

For any two layers $i\leq j$ , we define the interlayer cushion $\mu_{i,j}$ as the largest number such that for any $x\in S$ :

Recall that interlayer cushion is related to the noise sensitivity of $J^{i,j}_{x^{i}}$ at $x^{i}$ with respect to Gaussian distribution $\mathcal{N}(0,I)$ . When we consider $J^{i,j}_{x^{i}}$ applied to a noise $\eta$ , if different pixels in $\eta$ are independent Gaussians, then we can indeed expect $\|J^{i,j}_{x^{i}}\eta\|\approx\frac{1}{\sqrt{h^{i}n^{i}_{1}n^{i}_{2}}}\|J^{i,j}_{x^{i}}\|\|\eta\|$ , which explains the extra $\frac{1}{\sqrt{n^{i}_{1}n^{i}_{2}}}$ factor in Definition 8 compared to Definition 5. The proof also needs to assume —in line with intuition behind convolution architecture— that information from the entire image field is incorporated somewhat uniformly across pixels. It is formalized using the Jacobian which gives the partial derivative of the output with respect to pixels at previous layer.

Empirical Evaluation

We study noise stability properties (defined in Section 3) of an actual trained deep net, and compute a generalization bound from Theorem 5.1. Experiments were performed by training a VGG-19 architecture Simonyan and Zisserman (2014) and a AlexNet Krizhevsky et al. (2012) for multi-class classification task on CIFAR-10 dataset. Optimization used SGD with mini-batch size 128, weight decay 5e-4, momentum $0.9$ and initial learning rate $0.05$ , but decayed by factor 2 every 30 epochs. Drop-out was used in fully-connected layers. We trained both networks for 299 epochs and the final VGG-19 network achieved $100\%$ training and $92.45\%$ validation accuracy while the AlexNet achieved $100\%$ training and $77.22\%$ validation accuracy. To investigate the effect of corrupted label, we trained another AlexNet, with $100\%$ training and $9.86\%$ validation accuracy, on CIFAR-10 dataset with randomly shuffled labels.

Our estimate of the sample complexity bound used exact computation of norms of weight matrices (or tensors) in all bounds( $||A||_{1,\infty},||A||_{1,2},||A||_{2},||A||_{F}$ ). Like previous bounds in generalization theory, ours also depend upon nuisance parameters like depth $d$ , logarithm of $h$ , etc. which probably are an artifact of the proof. These are ignored in the computation (also in computing earlier bounds) for simplicity. Even the generalization based on parameter counting arguments does have an extra dependence on depth Bartlett et al. (2017). A recent work, Golowich et al. (2017) showed that many such depth dependencies can be improved.

Section 3 identifies four properties in the networks that contribute to noise-stability: layer cushion, interlayer cushion, contraction, interlayer smoothness. Figure 2 plots the distribution of over different data points in the training set and compares to a Gaussian random network and then scaled properly. The layer cushion, which quantifies its noise stability, is drastically improved during the training, especially for the higher layers ( $8$ and higher) where most parameters live. Moreover, we observe that interlayer cushion, activation contraction and interlayer smoothness behave nicely even after training. These plots suggest that the driver of the generalization phenomenon is layer cushion. The other properties are being maintained in the network and prevent the network from falling prey to pessimistic assumptions that causes the other older generalization bounds to be very high. The assumptions made in section 3 (also in B.1) are verified on the VGG-19 net in appendix D.1 by histogramming the distribution of layer cushion, interlayer cushion, contraction, interlayer smoothness, and well-distributedness of the Jacobians of each layer of the net on each data point in the training set. Some examples are shown in Figure 2.

2 Correlation to generalization error

We evaluate our generalization bound during the training, see Figure 4, Right. After 120 epochs, the training error is almost zero but the test error continues to improve in later epochs. Our generalization bound continues to improve, though not to the same level. Thus our generalization bound captures part of generalization phenomenon, not all. Still, this suggests that SGD somehow improves our generalization measure implicitly. Making this rigorous is a good topic for further research.

Furthermore, we investigate effect of training with normal data and corrupted data by training two AlexNets respectively on original and corrupted CIFAR-10 with randomly shuffled labels. We identify two key properties that differ significantly between the two networks: layer cushion and activation contraction, see 4. Since our bound predicts larger cushion and lower contraction indicates better generalization, our bound is consistent w with the fact that the net trained on normal data generalizes ( $77.22\%$ validation accuracy).

3 Comparison to other generalization bounds

Table 1 shows the compressibility of various layers according to the bounds given by our theorem. Again, this is a qualitative due to ignoring nuisance factors, but it gives an idea of which layers are important in the calculation.

Conclusions

With a new compression-based approach, the paper has made progress on several open issues regarding generalization properties of deep nets. The approach also adapts specially to convolutional nets. The empirical verification of the theory in Section 6 shows a rich set of new properties satisfied by deep nets trained on realistic data, which we hope will fuel further theory work on deep learning, including how these properties play into optimization and expressivity. Another possibility is a more rigorous understanding of deep net compression, which sees copious empirical work motivated by low-power applications. Perhaps our p-wise independence idea used for compressing convnets (Section 5) has practical implications.

Acknowledgements

This research was done with support from NSF, ONR, Simons Foundation, Mozilla Research, and Schmidt Foundation.

References

Appendix A Complete proofs for Section 2

In this section we give proofs of the various statements.

We will first prove Theorem 2.1, which gives generalization guarantees for the compressed function.

(Theorem 2.1) The proof is a basic application of concentration bounds and union bound and appears in the appendix.

For each $A\in\mathcal{A}$ , the training loss $\hat{L}_{0}(g_{A})$ is just the average of $n$ i.i.d. Bernoulli random variables with expectation equal to $L_{0}(g_{A})$ . Therefore by Chernoff bound we have

Therefore, suppose we choose $\tau=\left(\sqrt{\frac{m\log q}{n}}\right)$ , with probability at least $1-\exp(-2m\log q)$ we have $L_{0}(g_{A})\leq\hat{L}_{0}(g_{A})+\tau$ . There are only $q^{m}$ different $A\in\mathcal{A}$ , hence by union bound, with probability at least $1-\exp(-m\log q)$ , for all $A\in\mathcal{A}$ we have

Next, since $f$ is $(\gamma,S)$ -compressible with respect to $g$ , there exists $A\in\mathcal{A}$ such that for $x\in S$ and any $y$ we have

For these training examples, as long as the original function $f$ has margin at least $\gamma$ , the new function $g_{A}$ classifies the example correctly. Therefore

Combining these two steps, we immediately get the result. ∎

Using the same approach, we can also prove the following Corollaries that allow the compression to fail with some probability

In the setting of Theorem 2.1, if the compression works for $1-\zeta$ fraction of the training sample, then with high probability

The proof is using the same approach, except in this case we have

A.2 Example 1: Compress a Vector

This section gives detailed calculations supporting the first example in Section 2.

Algorithm 2 Vector-Compress( $\gamma$ , $c$ ) returns a vector $\hat{c}$ such that for any fixed $u$ (independent of choice of $\hat{c}$ ), with probability at least $1-\eta$ , $|\hat{c}^{\top}u-c^{\top}u|\leq\gamma$ . The vector $\hat{c}$ has at most $O((\log h)/\eta\gamma^{2})$ non-zero entries with high probability.

On the other hand, the expected number of non-zero entries in $\hat{c}$ is $\sum_{i=1}^{d}p_{i}=2/\eta\gamma^{2}$ . By Chernoff bound we know with high probability the number of non-zero entries is at most $O((\log h)/\eta\gamma^{2})$ . ∎

Combining the above two lemmas, we know there is a compression algorithm with $O((\log h)/\eta\gamma^{2})$ discrete parameters that works with probability at least $1-\eta$ . Applying Corollary A.1 we get

For any number of sample $m$ , there is an efficient algorithm to generate a compressed vector $\hat{c}$ , such that

Note that the rate we have here is not optimal as it depends on $m^{1/3}$ instead of $\sqrt{m}$ . This is mostly due to Lemma 4 cannot give a high probability bound (indeed if we consider all the basis vectors as the test vectors $u$ , Vector-Compress is always going to fail on some of them).

To fix this problem we use a different algorithm that uses a helper string, see Algorithm 3

Note that in Algorithm 3, the parameters for the output are the $z_{i}$ ’s. The vectors $v_{i}$ ’s are sampled independently, and hence can be considered to be in the helper string.

For any fixed vector $u$ , Algorithm 3 $\mbox{Vector-Project}(c,\gamma)$ produces a vector $\hat{c}$ such that with probability at least $1-\eta$ , we have $|\hat{c}^{\top}u-c^{\top}u|\leq\gamma$ .

This is in fact a well-known corollary of Johnson-Lindenstrauss Lemma. Observe that

The discretization is easy to check as with high probability the matrix $V$ with columns $v_{i}$ ’s have spectral norm at most $2\sqrt{h}$ , so the vector before and after discretization can only change by $\gamma/2$ . ∎

For any number of sample $m$ , there is an efficient algorithm with helper string to generate a compressed vector $\hat{c}$ , such that

We will choose $\eta=1/m$ . By Lemma 7, we know there is a compression algorithm that works with probability $1-\eta$ , and has at most $O((\log 1/\eta)/\gamma^{2})$ parameters. By Corollary A.1, we know

A.3 Proof for Generalization Bound in Neyshabur et al. [2017a]

We gave a compression in Lemma 1, the discretization in this case is trivial just by rounding the weights to nearest multiples of $\|A\|_{F}/h^{2}$ . The following lemma from Neyshabur et al. [2017a] (based on a simple induction of the noise) shows how the noises from different layers add up.

Let $f_{A}$ be a $d$ -layer network with weights $A=\{A^{1},\dots,A^{d}\}$ . Then for any input $x$ , weights $A$ and $\hat{A}$ , if for any layer $i$ , $\|A^{i}-\hat{A}^{i}\|\leq\frac{1}{d}\|A^{i}\|$ , then we have:

Compressing each layer $i$ with $\delta=\delta=\gamma(e\|x\|d\prod_{i=1}^{d}\|A^{i}\|_{2})^{-1}$ ensures $|f_{A}(x)-f_{\hat{A}}(x)|\leq\gamma$ . Since each $\hat{A}^{i}$ has rank $\frac{\|A^{i}\|_{F}^{2}}{\delta^{2}\|A^{i}\|_{2}^{2}}$ , the total number of parameters of the compressed network will be $2e^{2}d^{2}h\|x\|^{2}\prod_{i=1}^{d}\|A^{i}\|_{2}^{2}\sum_{i=1}^{d}\frac{\|A^{i}\|_{F}^{2}}{\|A^{i}\|_{2}^{2}}$ . Therefore we can apply Theorem 2.1 to get the generalization bound.

Appendix B Complete Proofs for Section 4

We discussed and verified several conditions in Section 3. Here, we formally state these conditions:

Layer cushion ( $\mu_{i}$ ): For any layer $i$ , we define the layer cushion $\mu_{i}$ as the largest number such that for any $x\in S$ :

Interlayer cushion ( $\mu_{i,j}$ ): For any two layers $i\leq j$ , we define interlayer cushion $\mu_{i,j}$ as the largest number such that for any $x\in S$ :

Furthermore, we define minimal interlayer cushion $\mu_{i\rightarrow}=\min_{i\leq j\leq d}\mu_{i,j}=\min\{1/\sqrt{h^{i}},\min_{i<j\leq d}\mu_{i,j}\}$ .

Activation contraction ( $c$ ): The activation contraction $c$ is defined as the smallest number such that for any layer $i$ and any $x\in S$ ,

Interlayer smoothness ( $\rho_{\delta}$ ): Interlayer smoothness is defined the smallest number such that with probability $1-\delta$ over noise $\eta$ for any two layers $i<j$ any $x\in S$ :

B.2 Proofs

(of Lemma 2) For any fixed vectors $u,v$ , we have

This is exactly the same as the case of Johnson-Lindenstrauss transformation. By standard concentration inequalities we know

Now for any pair of matrix/vector $(U,x)\in G$ , let $u_{i}$ be the $i$ -th row of $U$ , by union bound we know with probability at least $1-\delta$ for all $u_{i}$ we have $|u_{i}^{\top}(\hat{A}-A)v\|\leq\varepsilon\|A\|_{F}\|u_{i}\|\|v\|$ . Since $\|U(\hat{A}-A)x\|^{2}=\sum_{i=1}^{n}(u_{i}^{\top}(\hat{A}-A)x)^{2}$ and $\|U\|_{F}^{2}=\sum_{i=1}^{n}\|u_{i}\|^{2}$ , we immediately get $\|U(\hat{A}-A)x\|\geq\varepsilon\|A\|_{F}\|U\|_{F}\|x\|$ . ∎

For the base case $i=0$ , since we are not perturbing the input, the inequality is trivial. Now assuming that the induction hypothesis is true for $i-1$ , we consider what happens at layer $i$ . Let $\hat{A}^{i}$ be the result of Algorithm 1 on $A^{i}$ with $\varepsilon_{i}=\frac{\varepsilon\mu_{i}\mu_{i\rightarrow}}{4cd}$ and $\eta=\frac{\delta}{6d^{2}h^{2}m}$ . We can now apply Lemma 2 on the set $G=\{(J^{i,j}_{x^{i}},x^{i})|x\in S,j\geq i\}$ which has size at most $dm$ . Let $\Delta^{i}=\hat{A}^{i}-A^{i}$ , for any $j\geq i$ we have

The second term can be bounded by $(i-1)\varepsilon\|x^{j}\|/d$ by induction hypothesis. Therefore, in order to prove the induction, it is enough to show that the first term is bounded by $\varepsilon/d$ . We decompose the error into two error terms one of which corresponds to the error propagation through the network if activation were fixed and the other one is the error caused by change in the activations:

The first term can be bounded as follows:

Both terms can be bounded using interlayer smoothness condition of the network. First, notice that $A^{i}\phi(\hat{x}^{i-1})=\hat{x}^{i}_{i-1}$ . Therefore by induction hypothesis $\|A^{i}\phi(\hat{x}^{i-1})-x^{i}\|\leq(a-1)\varepsilon\|x^{i}\|/d\leq\varepsilon\|x^{i}\|$ . Now by interlayer smoothness property, $\|(M^{i,j}-J^{i,j}_{x^{i}})(A^{i}\phi(\hat{x}^{i-1})\|\leq\frac{\|x^{b}\|\varepsilon}{\rho_{\delta}}\leq(\varepsilon/3d)\|x^{j}\|$ . On the other hand, we also know $\hat{A}^{i}\phi(\hat{x}^{i-1})=\hat{x}^{i}_{i-1}+\Delta^{i}\phi(\hat{x}^{i-1})$ , therefore $\|\hat{A}^{i}\phi(\hat{x}^{i-1})-x^{i}\|\leq\|A^{i}\phi(\hat{x}^{i-1})-x^{i}\|+\|\Delta^{i}\phi(\hat{x}^{i-1})\|\leq(i-1)\varepsilon/d+\varepsilon/3d\leq\varepsilon$ , so again we have $\|(M^{i,j}-J^{i,j}_{x^{i}})(\hat{A}^{i}\phi(\hat{x}^{i-1}))\|\leq(\varepsilon/3d)\|x^{j}\|$ . Putting everything together completes the induction. ∎

Because of positive homogeneity of ReLU activations, we can assume without loss of generality that the network is balanced, i.e for any $i\neq j$ , $\|A_{i}\|_{F}=\|A_{j}\|_{F}=\beta$ (otherwise, one could rebalance the network before approximation and cushion in invariant to this rebalancing). Therefore, for any $x\in S$ we have:

where the last inequality is because by Lemma 10, $\frac{e^{2}d\|f_{A}(x)\|}{\gamma\beta\prod_{i=1}^{d}\mu_{i}}<\sqrt{q}$ . Since the absolute value of each parameter in layer $i$ is at most $\beta h$ , the logarithm of number of choices for each parameter in order to get $\varepsilon$ -cover is $\log(qh^{2}/\varepsilon)\leq 2\log(qh/\varepsilon)$ which results in the covering number $2q\log(kh/\varepsilon)$ . Bounding the Rademacher complexity by Dudley entropy integral completes the proof. ∎

Appendix C Convolutional Neural Networks

In this section we give a compression algorithm for convolutional neural networks, and prove Theorem 5.1.

We start by developing some notations to work with convolutions and product of tensors. For simplicity of notation, for any $k^{\prime}\leq k$ , we define a product operator $\times_{k^{\prime}}$ that given a $k$ th-order tensor $Y$ and a $k^{\prime}$ order tensor $Z$ with a matching dimensionality to the last $k^{\prime}$ -dimensions of $Y$ , vectorizes the last $k^{\prime}$ dimensions of each tensor and returns a $k-k^{\prime}$ th order tensor as follows:

The $\hat{A}_{(i,j)}$ ’s will be generated by Algorithm 4 and are $p$ -wise independent.

Let $\kappa_{i}$ be the filter size and $s_{i}$ be the stride in layer $i$ of the convolutional network. Then for any $i>1$ , $x^{i+1}=\phi(A^{i}*_{s_{i}}x^{i})$ . Furthermore, since the activation functions are ReLU, we have $x^{j}=M^{ij}(x^{i})=J^{ij}_{x^{i}}\times_{3}x^{i}$ .

In the rest of this section, we will first describe the compression algorithm Matrix-Project-Conv (Algorithm 4) and show that the output of this algorithm behaves similar to Gaussian noise (similar to Lemma 2). Then we will follow the same strategy as the feed-forward case and give the full proof.

The weights in convolutional neural networks have inherent correlation due to the architecture, as the weights are shared across different locations. However, in order to randomly compress the weight tensors, we need to break this correlation and try to introduce independent perturbations at every location. The procedure is described as Algorithm 4.

The goal of Algorithm 4 is to generate different compressed filters $\hat{A}_{i,j}$ such that the total number of parameters is small, and at the same time $\hat{A}_{i,j}$ ’s behave very similarly to applying Algorithm 1 $A$ for each location independently. We formalize these two properties in the following two lemmas:

Given a helper string that contains all of the $M^{\prime}$ matrices used in Algorithm 4, then it is possible to compute all of $\hat{A}_{(i,j)}$ ’s based on $\mbox{Proj}_{\mathcal{S}}(A)$ . Since $\mathcal{S}$ is a $kp$ dimensional subspace $\mbox{Proj}_{\mathcal{S}}(A)$ has $kp$ parameters.

By Algorithm 4 we know $\hat{A}_{(i,j)}$ ’s are average of the $Z$ matrices, and $Z_{k^{\prime}}=\langle A,M^{\prime}_{k^{\prime}}\rangle M^{\prime}_{k^{\prime}}$ . Since $M^{\prime}_{k^{\prime}}\in\mathcal{S}$ , we know $\langle A,M^{\prime}_{k^{\prime}}\rangle=\langle\mbox{Proj}_{\mathcal{S}}(A),M^{\prime}_{k^{\prime}}\rangle$ . Hence $Z_{k^{\prime}}=\langle\mbox{Proj}_{\mathcal{S}}(A),M^{\prime}_{k^{\prime}}\rangle M^{\prime}_{k^{\prime}}$ only depends on $\mbox{Proj}_{\mathcal{S}}(A)$ and $M^{\prime}_{k^{\prime}}$ . ∎

The random matrices $\hat{A}_{(i,j)}$ ’s generated by Algorithm 4 are $p$ -wise independent. Moreover, for any $\hat{A}_{(i,j)}$ , the marginal distribution of the $M^{\prime}$ matrices are i.i.d. Gaussian with variance 1 in every direction.

Take any subset of $p$ random matrices $\hat{A}_{(i_{1},j_{1})},...,\hat{A}_{(i_{p},j_{p})}$ generated by Algorithm 4. We are going to consider the joint distribution of all the $M^{\prime}$ matrices used in generating these $\hat{A}$ ’s ( $k\times p$ of them) and the subspace $\mathcal{S}$ .

Consider the following procedure: generate $k\times p$ random matrices $M^{\prime}_{1},M^{\prime}_{2}...,M^{\prime}_{kp}$ from $N(0,1)^{h^{\prime}\times h\times\kappa\times\kappa}$ , and let $\mathcal{S}$ be the span of these $kp$ vectors. By symmetry of Gaussian vectors, we know $\mathcal{S}$ is a uniform random subspace of dimension $kp$ .

Now we sample from the same distribution in a different order: first sample a uniform random subspace $\mathcal{S}$ of dimension $kp$ , then sample $kp$ random Gaussian matrices within this subspace (which can be done by sample a Gaussian in the entire space and then project to this subspace). This is exactly the procedure described in Algorithm 4.

Therefore, the $M^{\prime}$ matrices used in generating these $\hat{A}$ ’s are independent, as a result the $\hat{A}_{(i,j)}$ ’s are also independent. The equivalence also shows that the marginal distributions of $M^{\prime}$ are i.i.d. spherical Gaussians. (Note that the reason this is limited to $p$ -wise independence is that if we look at more than $kp$ random matrices from the subspace $\mathcal{S}$ , they do not have the same distribution as Gaussian random matrices; the latter would span a subspace of dimension higher than $kp$ .) ∎

Although the $\hat{A}_{(i,j)}$ ’s are only $p$ -wise independent, when $p=\log 1/\eta$ we can show that they behave similarly to fully independent random filters. We defer the technical concentration bounds to the end of this section (Section C.3).

Using this compression, we will prove that the noise generated at each layer behaves similar to a random vector. In particular it does not correlate with any fixed tensor, as long as the norms of the tensor is well-distributed:

Intuitively, $U$ is well-distributed if no spacial location of $U$ has a norm that is significantly larger than the average. Now we are ready to show the noise generated by this procedure behaves very similar to a random Gaussian (this is a generalization of Lemma 2):

We will first expand out $U\times_{3}(\Delta*_{s}V)$ :

In this expression, $(U_{:,i,j,:}\otimes V_{(s(i-1)+1,s(j-1)+1),\kappa})$ generates a 5-th order tensor (2 from $U$ and 3 from $V$ ), the order of dimensions is that $V$ takes coordinates number 3,4,5 (with dimensions $h\times\kappa\times\kappa$ ), the first dimension of $U$ takes the 2nd coordinate and the 4-th dimension of $U$ takes the 1st coordinate. The result of $(U_{:,i,j,:}\otimes V_{(s(i-1)+1,s(j-1)+1),\kappa})\times_{4}(\hat{A}_{(i,j)}-A)$ is a vector of dimension $n_{u}$ (because the first 4 dimensions are removed in the inner-product).

Now let us look at the terms in this sum, let $X_{i,j}=(U_{:,i,j,:}\otimes V_{(s(i-1)+1,s(j-1)+1),\kappa})\times_{4}\hat{A}_{(i,j)}$ . Let $M^{\prime}_{1},...,M^{\prime}_{k}$ be the random matrices used when computing $\hat{A}_{(i,j)}$ (for simplicity we omit the indices for $i,j$ ), then we have

By Lemma 12 we know $X_{i,j}$ ’s are $p$ -wise independent. Now we can apply Corollary C.2 to the sum of $X_{i,j}$ ’s. Let $\sigma=\sqrt{\sum_{i=1}^{n^{\prime}_{1}}\sum_{j=1}^{n^{\prime}_{2}}\sigma_{i,j}^{2}}$ , then we know

Union bound over all $(U,V)$ pairs, we know with probability at least $1-\delta$ , we have $\|U\times_{3}(\Delta*_{s}V)\|\leq 12\sigma p$ for all $(U,V)$ .

Finally, we will try to relate $12\sigma p$ with $\frac{\varepsilon\beta}{\sqrt{n^{\prime}_{1}n^{\prime}_{2}}}\|A\|_{F}\|U\|_{F}\|V\|_{F}$ .

Here the first inequality is by the assumption that all $U$ ’s are $\beta$ -well-distributed. The second inequality is true because each entry in $V$ appears in at most $\lceil\kappa/s\rceil^{2}$ entries of $V_{(s(i-1)+1,s(j-1)+1),\kappa}$ . Therefore, when $k$ is set to $144(Q^{\prime})^{2}\lceil\kappa/s\rceil^{2}p^{2}/\epsilon^{2}=O(\frac{\lceil\kappa/s\rceil^{2}\log^{2}1/\eta}{\epsilon^{2}})$ , we have $12\sigma p\leq\frac{\varepsilon\beta}{\sqrt{n^{\prime}_{1}n^{\prime}_{2}}}\|A\|_{F}\|U\|_{F}\|V\|_{F}$ as desired. ∎

C.2 Generalization Bounds for Convolutional Neural Networks

Next we will use Algorithm 4 to compress the neural network and prove generalization bounds. Similar to the feed-forward case, our first step is to show bound the perturbation of the output based on the noise introduced at each layer. This is captured by the following lemma (generalization of Lemma 3)

where $\mu_{i}$ , $\mu_{i\rightarrow}$ , $c$ , $\rho_{\delta}$ and $\beta$ are layer cushion, interlayer cushion, activation contraction, interlayer smoothness and well-distributedness of Jacobian defined in Definitions 4,8,6, 7 and 9 respectively.

(Note that although $x$ is now a 3-tensor, we still use $\|x\|$ to denote $\|x\|_{F}$ as we never use any other norm of $x$ .)

The first term can be bounded as follows:

Because of positive homogeneity of ReLU activations, we can assume without loss of generality that the network is balanced, i.e for any $i\neq j$ , $\|A_{i}\|_{F}=\|A_{j}\|_{F}=\tau$ (otherwise, one could rebalance the network before approximation and cushion in invariant to this rebalancing). Therefore, for any $x\in S$ we have:

where the last inequality is because by Lemma 10, $\frac{e^{2}d\|f_{A}(x)\|}{\gamma\tau\prod_{i=1}^{d}\mu_{i}}<\sqrt{q}$ . Since the absolute value of each parameter in layer $i$ is at most $\tau h$ , the logarithm of number of choices for each parameter in order to get $\varepsilon$ -cover is $\log(qh^{2}/\varepsilon)\leq 2\log(qh/\varepsilon)$ which results in the covering number $2q\log(kh/\varepsilon)$ . Bounding the Rademacher complexity by Dudley entropy integral completes the proof. ∎

Similar to the discussions at the end of Section 4, we can use distance to initialization and remove outliers. More concretely, we can get the following corollary

C.3 Concentration Inequalities for Sum of p𝑝p-wise Independent Variables

In this section we prove a technical lemma that shows the sum of $p$ -wise independent subexponential random variables have strong concentration properties. Previously similar results were known for Bernoulli random variables Pelekis and Ramon , the approach we take here is very similar.

The following lemma will imply concentration

Let $X_{1},X_{2},...,X_{n}$ be random variables where $X_{i}$ is $\sigma_{i}$ -subexponential. Let $\sigma^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}$ , $X=\sum_{i=1}^{n}X_{i}$ . If $X_{i}$ ’s are $p$ -wise independent

By Claim 1 below, we know this expectation is bounded by $p^{p}(3\sigma)^{p}$ . The second part of the lemma follows immediately from Markov’s inequality. ∎

We do induction on $n$ . When $n\leq 1$ this is clearly correct. Let $F(n,p)=\sum_{a\in\mathcal{A}_{n,p}}\prod_{i=1}^{n}\sigma_{i}^{a_{i}}$ , then we have

Suppose the claim is true for all $n<z$ , let $\sigma^{\prime}=\sqrt{\sum_{i=1}^{z-1}\sigma_{i}^{2}}$ , when $n=z$ we have

When $\sigma_{n}\leq 2\sigma^{\prime}$ , we know $\sum_{a=2}^{p}(3\sigma^{\prime})^{p-a}\sigma_{n}^{a}\leq 3(3\sigma^{\prime})^{p-2}\sigma_{n}^{2}$ , hence by Binomial expansion we have

On the other hand, if $\sigma_{n}\geq 2\sigma^{\prime}$ , then we know all the terms in the summation $\sum_{a=2}^{p}(3\sigma^{\prime})^{p-a}\sigma_{n}^{a}$ and $(3\sigma^{\prime})^{p}$ are bounded by $(1.5\sigma_{n})^{p}$ , therefore

In both cases we prove $F(z,p)\leq(9\sum_{i=1}^{n}\sigma_{i}^{2})^{p/2}$ , which finishes the induction. ∎

We also remark that Lemma 15 can be generalized to vectors

Let $X_{1},X_{2},...,X_{n}$ be random vectors where $\|X_{i}\|$ is $\sigma_{i}$ -subexponential. Let $\sigma^{2}=\sum_{i=1}^{n}\sigma_{i}^{2}$ , $X=\sum_{i=1}^{n}X_{i}$ . If $X_{i}$ ’s are $p$ -wise independent, for any even $p$

The proof is exactly the same as the proof of Lemma 15. When $X_{i}$ ’s are vectors we get exactly the same terms, except the terms have pair-wise inner-products. However, the inner-products $\langle X_{i},X_{j}\rangle\leq\|X_{i}\|\|X_{j}\|$ so we only need to argue about the same inequality for $\|X_{i}\|$ ’s. ∎