Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
Authors: Taiji Suzuki
Hiroshi Abe
Tomoaki Nishimura
Venue:  (2020)
Keywords: Generalization error
compression based bound
local Rademacher complexity

Abstract: One of the biggest issues in deep learning theory is the generalization ability of networks with huge model size. 
The classical learning theory suggests that overparameterized models cause overfitting.
However, practically used large deep models avoid overfitting, which is not well explained by the classical approaches.
To resolve this issue, several attempts have been made. 
Among them, the compression based bound is one of the promising approaches. 
However, the compression based bound can be applied only to a compressed network, and it is not applicable to the non-compressed original network. 
In this paper, we give a unified frame-work that can convert compression based bounds to those for non-compressed original networks.
The bound gives even better rate than the one for the compressed network by improving the bias term.
By establishing the unified frame-work, we can obtain a data dependent generalization error bound which gives a tighter evaluation than the data independent ones.


Published as a conference paper at ICLR 2020
COMPRESSION BASED BOUND FOR NON-COMPRESSED NETWORK: UNIFIED GENERALIZATION ERROR ANAL- YSIS OF LARGE COMPRESSIBLE DEEP NEURAL NET- WORK
Taiji Suzuki
Graduate School of Information Science and Technology. The University of Tokyo, Japan Center for Advanced Intelligence Project, RIKEN, Japan Japan Digital Design tai miji@miist:. w.w.ko..cc....... jp
Hiroshi Abe
Tomoaki Nishimura
iPride Co., Ltd., Japan, abe0 opridir co. ip,
NTT Data Corporation, Japan, Tomoaki. Wishhimmraantttttaaccc
ABSTRACT
One of the biggest issues in deep learning theory is the generalization ability of networks with huge model size. The classical learning theory suggests that overparameterized models cause overfitting. However, practically used large deep models avoid overfitting, which is not well explained by the classical approaches. To resolve this issue, several attempts have been made. Among them, the compres- sion based bound is one of the promising approaches. However, the compression based bound can be applied only to compressed network, and it is not applicable to the non-compressed original network. In this paper, give unified frame- work that can convert compression based bounds to those for non-compressed original networks. The bound gives even better rate than the one for the pressed network by improving the bias term. By establishing the unified frame- work, obtain data dependent generalization tighter evaluation than the data independent ones.
bound which gives
INTRODUCTION
Deep learning has shown quite successful results in wide range of machine learning applications. such as image recognition (Krizhevsky et al. (012),, natural language processing (Devlin al. 2018) and image synthesis tasks (Radford et 2015). The success of deep learning methods mainly due to its flexibility, expression power and computational efficiency for large dataset training. Due to its significant importance in wide range of application areas. theoretical analysis is also getting much important. For example, it has been known that the deep neural network has universal approximation capability (Cybenko 1989. Horii 1991, Sonoda & Murata 2013) and its expressive power grows up in an exponential order against the number of layers (Montufar et al. 2014 Bianchini & Scarselli, 2014 Cohen al.) 2016 Cohen & Shashua 2016 Poole et al. 2016)] Suzuki 2019). However, theoretical understandings are still lacking in several important issues.
Among several topics of deep learning theories, generalization error analysis one of the biggest issues in the machine learning literature. An important property of deep learning that it general- izes well even though its parameter size is quite large compared with the sample size (Neyshabur et al. 2019). This not be well explained by classical VC-dimension type theory (Harvey et al. 2017) which suggests that overparameterized models cause overfitting and thus result in poor generalization ability.
For this purpose, norm based bounds have been extensively studied so far (Neyshabur et al., 2015 Bartlett al. 2017b Neyshabur et al. 2017: Golowich al. 2018). These bounds are beneficial

---

Published as a conference paper at ICLR 2020
because the bounds are not explicitly dependent on the number of parameters and thus useful to explain the generalization error of overparameterized network (Bartlett) 1998| Neyshabur et al.
the number of layers and thus tends to be loose for deep network situations (Dziugaite & Roy 2017 7 Arora et al. 2018 Nagarajan & Kolter 2019). As result, Arooa et al. (2018) reported that a simple VC-dimension bound (Li et al. 2018 Harvey et al. (017)) can still give sharper evaluations than these norm based bounds in some practically used deep networks. |Wii & Ma (2019) improved this issue by involving a data dependent Lipschitz constant as performed in Arora et al. (2018); Nagarajan & Kolter (2019)
2013 2019). However, these bounds
typically exponentially dependent
On the other hand, compression based bound is another promising upproach for tight generalization error evaluation which can avoid the exponential dependence on the depth. The complexity of deep neural network model is regulated from several aspects. For example, we usually impose explicit
regularization such as weight decay (Krogh & Hertz 1992). dropout (Srivastava et al., 2014
Wager
et al. 2013), anch-normalizztion (Toffe & Szegedy 2015), and mix-up (Zhang et al.
2018 Verma
et al. 2018). Zhang et al. (2116) reported that such explicit regularization does not have much
eilect but implicit regularization induced by SGD (Hardt et al. 2016 Gunasekar et al. 2018 Ji &
Telgarsky 2019) is important. Through these explicit and implicit regularizations, deep learning tends to produce a simpler model than its full expression ability (Valle Perez et al., 2019 Verma eet al. 2018). To measure how "simple" the trained model is, one of the most promising approaches currently investigated is the compression bounds (Arora et al.] 2018: [Baykal et al., [019 Suzuki cct al.] 2018). These bounds measure how much the network can be compressed and characterize the size of the compressed network as the implicit effective dimensionality. |Arora et al. (2018) characterized the implicit dimensionality based on so called layer-cushion quantity and suggested to perform random projection to obtain a compressed network. Along with a similar direction, Baykal et al. (2019) proposed a pruning scheme called Corenet and derived bound of the size of the compressed network. (Suzuki et al. (2018) has developed spectrum based bound for their compression scheme. Unfortunately, all of these bounds guarantee the generalization error of only the compressed network, not the original network. Hence, it does not give precise explanations about why large network can avoid overfitting.
In this paper, we derive a unified framework to obtain a compression based bound for non- compressed network. Unlike the existing researches, our bound is valid to evaluate the original network before compression, and thus gives a direct explanation about why deep learning general- izes despite its large network size. The difficulty to apply the compression bound to the original network lies in evaluation of the population L2-bound between the compression network and the original network. A naive evaluation results in the VC-bound which is not preferable. This difficulty overcome by developing novel data dependent capacity control technique using local Rademacher
complexity bounds (Mendelson) 2002 Bartlett et al. 2005); Koltchinski 2006 Giné & Koltchinskil 2006). Then, the bound is applied to some typical situations where the network is well compressed. Our analysis stands on the implicit bias hypothesis (Gunasekar et al.) 2018 Ji & Telgarsky, 2019) that claims deep learning tends to produce rather simple models. Actually, Gunasekar et al. 2018); Ji & Telgarsky (2019) showed gradient descent results in (near) low rank parameter matrices each layer in linear network settings. Martin & Mahoney (2018) evaluated the eigenvalue decays of the weight matrix through random matrix theories and several numerical experiments. These observa- tions are also supported by the flat minimum analysis (Hochreiter & Schmidhuber) 1997] Wu et al.) 2017 Langford & Caruana 2002), that is, the product of the eigenvalues of the Hessian around the SGD solution tends to be small, which means SGD converges to a flat minimum and possess sta- bility against small perturbations leading to good generalization. Based on these observations, we make use of the eigenvalue decay of the weight matrix and the covariance matrix among the nodes in each layer (this assumption is actually verified by numerical experiments in Appendix D). The eigenvalue decay speed characterizes the redundancy in each layer and thus is directly relevant to compressio compression ability. Our contributions in this paper are summarized as follows:
We give unified framework to obtain compression based bound for non-compressed net- work which properly explains that a compressible network can generalizes well. The bound can convert several existing compression based bounds to that for non-compressed one in a unifying manner. The bound is applied to near low rank models as concrete examples.
We develop a data dependent capacity control technique to bound the discrepancy between the original network and compressed network. As result, we obtain a sharp generalization
2

---

Published as a conference paper at ICLR 2020
Table 1: Comparison of each generalization error our bound. Rp is the Frobenius norm of the weight matrix, R2 is the operator norm of the weight matrix, Re-rq is the (p,g) matrix norm, L is the depth, is the maximum of the width, is the sample size. Rn and R, represent the Rademacher complexity and local Rademacher complexity respectively. K is Lipschitz constant between layers. represents the eigenvalue drop rate of the weight matrix, and represents that of the covariance matrix among the nodes each internal layer. A is the bias induced by compression. "Original" indicates whether the bound about the original network not.
Authors
Rate
Bound type
Original
Neyshabur et al. 2015
2" RE
Norm base
Yes
v/B
3/2
R
22/3
Bartlett 2211
Norm base
Yes
R2/3
[1+ 22/3 Lr.
R
3/2
Wei & Ma (209
Norm base
Yes
Neyshabur et al.
2017
L
Norm base
Yes
Golowich et al. 2018
Re min
Norm base
Yes
m.74:
Liet al. 2018)
VC-dim.
Yes
Harvey et al.
2017
V/n
La max 15:5
lf(z,))
EL. 1
Arora al.
(0188)
++
Compression
No
++ -== m mi
Suzuki et
20188
Compression
No
Ours (Thm.
i / n + R ( 9) + (9)
General
Yes
Ours (Cor.
L(LK3) 3) f/x Lm
Low rank weight
Yes
Ours (Thm.
(Lm)
Low rank weight
Yes
Low rank cov.
error bound which is even better than that of the compressed network. All derived bounds are characterized by data dependent quantities.
Other related work Recently, the role of over over-parame wer-paraaeeeerization for two layer networks has been extensively studied (Neyshabur et al. 2019)) Arora et al. (2019). These are for the shallow network and the generalization error is essentially given by the norm based bounds. It is not obvious that these bounds also give sharp bounds for deep models.
PAC-Bayes bound also applied to obtain non-vacuous compression based bound ZZoou et al., 2019). However, the bound is still for the compressed (quantized) models and it is not obvious that that bound can be converted to that for the original network.
Relation between compression and learnability was traditionally studied in different framework as Littllteee & Warmuth ( 1986) and minimum description code length (Hinton Van Camp) 1993). Our bound would share the same spirits with these studies but give new analysis by incorporating recent observations in deep learning researches.
PRELIMINARIES PROBLEM FORMULATION AND NOTATIONS
In this section, we give the problem setting and notations that will be used in the thcoretical analysis. We consider the standard supervised leaning formulation where data consists of input E IR and output (or label) y E R. We consider a single output setting, i.e., the output is a 1-dimensional real value, but it is straight forward to generalize the result to multiple output case. Suppose that are given n i.i.d. observations D, (Ix, y distributed from probability distribution P. To measure the performance of trained function f. use loss function R R R and define
3

---

Published as a conference paper at ICLR 2020
training error and its expected one as
n (() = 72 Σ
f(i)),
v(f) E(())
where the expectation is taken with respect (x, Y) P. Basically, we are interested in the generalization error V (f) - (f) for an estimator f. We denote the empirical Lo-norm by Il. ==
V f(,)2// for an empirical observation 23 = (I,, Mi) (i = I,..., n). The population L2-
norm is denoted by [lf == (Ez=P(f(Z)).
This paper deals with deep neural networks as a model. The activation function is denoted by which will be assumed to be I-Lipschitz satisfied by ReLU (Assumption D Let the depth of the network be L. and the width of the f-th internal layer be me (L = 1...., L + 1) where we set my = d (dimension of imput) and mL+1 1 (dimension of output) for convention. Then, the set of networks having depth and width m = (m.....,my, m,.) with norm constraint as
NN(m, R2 R(p) = { ((x)) = Go (w(D n(-)) o (w(l-1 o ................................ (w
w E memex || 12 = R2 (| S R
where ||W||2 == sup,: W Wills [| is the operator norm (the maximum singular value),
[[W]| |F = Eig W7, is the Frobenius norm, and G is the "clipping" operator that is defined by G(x) max(-aa M, minf2, Sonfx..MM 3M} for constant M. The reason why we put the clipping operator G on top of the last layer is because the clipping operator restricts the L -norm by a constant M and then
avoid unrealistically loose generalization error. Note that the clipping operator does not change the classificatton error for binary classification. We express F to represent the "full model": F NN(m, R2, Rp) for a given R2, Rr O. Here, we implicitly suppose that R₂ is close so that the norm of the output from internal layers is not too much amplified, while Rp could be moderately large.
The Rademacher complexity is the typical tool to evaluate the generalization error on a function class F. which is denoted by (F') := E, [sup ye. J. (z())) Dx] where D, (z))i= = (I,, )= and & (i = I, .n....n) is an i.i.d. Rademacher sequence (P(E, = 1) = P(e: = =1) 1/2). This is also called conditional Rademacher complexity because the expectation is taken con- ditioned on fixed D,.- Its expectation with respect to D, is denoted by (F') := Ep,, [ Roughly speaking the Rademacher complexity measures the size of the model and it gives upper bound of the generalization error (Vapnik] 1998 Mohri et al. 2012).
The main difficulty in generalization error analysis of deep learning is that the Rademacher com- plexity of the full model F is quite large. One of the successful approaches to avoid this difficulty is the compression based bound (Arora et al., 2018 Baykal et al. 2019: Suzuki et al. 2018) which measures how much the trained network if can be compressed. If the network can be compressed to much smaller one, then its intrinsic dimensionality can be regarded small. To describe it more precisely, suppose that the trained network f is included in subset of the neural network model: fe C F. For example, ff can be a set of networks with weight matrices that have bounded norms and are near low rank (Sec. 3.1 or Sec. 3.2). We do not assume a specific type of training procedure, but we give uniform bound valid for any estimator f that falls into fo and satisfies the following compressibility condition. We suppose that the network f is easy to compress, that is, submodel: ğ E G. For example,
can be compressed to smaller network ğ which is included I can be a set of networks with a smaller size than f. How small the trained network f can be compressed has been characterized by several notions such as "layer-cushion" (Arora et al.) 2018). Typical compression based bounds give generalization errors of the compressed model g, not the original network f. Our approach converts an error bound of ğ to that of f and eventually obtains a tighter evaluation.
In this paper, ||- denotes the Fuclidean norm: ||M|||
VI, u.
4

---

Published as a conference paper at ICLR 2020
The biggest difficulty for transforming the compression bound to that of f lies in evaluation of the population L2-norm between f and g. Basically, the compression based bounds are given as
9 S 3 + Ilf Il (9),
(1)
for a constant C > O under some assumptions (Table 1. The term 115 1 I11 appears to adapt the empirical error of f to that of g. that is called "compression error" which can be seen bias term. We see that, in the right hand side, there appears the complexity of I which is assumed be much smaller than that of the full model F. However, the left hand side is not the expected error of but
that of 3. One way to transfer this bound to that of ff is that we have (V(]) - v (f) I |l@ fl by assuming Lipschitz continuity of the loss function and then convert the bound to
v S ( (1I Ill + 11 21122 + (9).
However, to bound the term Ilf T1e + I1f - I2 there typically appears the complexity of the model F which is larger than the compressed model 9 like |1 - S / /lf Tll,, + (R((() which results in slow convergence rate. To overcome this difficulty, we need carefully control the difference between the training and test error of f and ğ by utilizing the local Rademacher com- plexity technique (Mendelson) 2002; Bartlett et al. 20055 Koltchinskii (2006] Giné & Koltchinskii 2006). The local Rademacher complexity of a model J" with radius r is defined as
R,"F")= == R,f IIll,, Sr)).
The main difference from the standard Rademacher complexity is that the model is localized to set of functions satisfying LI S r. As a result, we obtain tighter error bound.
Throughout this paper, we always assume the following assumptions. Let Px and Py denote the marginal distribution of and that of y respectively.
Assumption 1 (Lipschitz continuity of loss and activation functions). The loss fanction vo is 1- Lipschitz continuous with respect to the function output:
(y, u) bly v')l s Iu u'1 (Vy E supp(Py), u' R).
The activation function yi is also 1-Lipschitz continuous: Iln(u) v(('(ll I l w'll (Vu E Rdd)) where d' any positive integer.
Assumption 2. The norm of imput is bounded by BN 0: ||l||| S BN (Ver su))(
Assumption 3. The -orms of all elements in F and G are bounded by M 2 1: [| Igllos S M for all E F and g E G.
This assumption can be ensured by applying the clipping operator G to the output of the functions. In this paper, all the variables L, me, R2, Rp, M, B2 supposed to be o(n). What we will derive in the following is a bound which has mild dependency on the depth L and depends on the width (m=)/1 in sub-linear order by using the compression based approach.
Existing bounds for no-compressed network Here we give a brief review of the generaliza- tion error bound for non-compressed models. (i) VC-bound: The Rademacher complexity of the full model If' can be bounded by naive VC-dimension bound (Harvey et al. 2017) which is
mime+1 log(n)) In this bound, there appears the number of parame- (F) = 0 1ا
ters Σx- 7 in the numerator. However, the number of parameters is often larger than the sample size n in practical use. Hence, this bound is not appropriate to evaluate generaliza- tion ability of overparameterized networks. (ii) Norm- based bound: Golowich et al. (2018) showed
(V L.R% n
the norm based bound which is given as RR, =0
However, this is exponentially
dependent on the depth as R% resulting in quite loose bound. Neyshabur et al. 2017) showed
based bound of (F) 0 [ma my mm))rt// which avoids the exponential de- n
pendency. However, there is still dependency on the width, Ee me R2. which is larger than the
5

---

Published as a conference paper at ICLR 2020
linear order of the width since Ry could be moderately large.
Bartlett et al. (2017b) showed
3/2
(F) o R2
R2/3 R
The norm constraint on R2-11 implicitly assumes sparsity on
the weight matrix and R2-+1 typically depends on the width linearly. Wei & Ma 2019) improved
the exponential dependency R2 appearing in this bound (Bartlett et al. 701 to obtained a bound
o ( 1+
L (1+
+ -
3/2)
where x. is the Lipschitz continuity between layers.
We can see that R3-,1 and Ri can depend on the width linearly and quadratically respectively even though R2 is bounded.
3 COMPRESSION BOUND FOR NONCOMPRESSED NETWORK
Here, we give a general theoretical tool that converts a compression based bound to that for the original network f. We suppose the model classes F and & are fixed independently each data
[bservation 2 For sets of functions, J' and G', we denote the Minkowski difference of them by
F' G' = (f f F' E G³). We assume that the local Rademacher complexity of F G has a concave shape with respect to > 0: Suppose that there exists a function Φ [0, 20) - 00) such that
RF 9 < <(r) and ((r) - 2Φ(r) (v)>)).
>
This condition is not restrictive, and usual bounds for the local Rademacher complexity satisfy this condition (Mendelson 2002 Bartlett et al. 2005). Using this notation, we define r, = r. (t) as
r. (t) inf {
(r)
4t 12
21 22n
{
8
M
+ M
2
This is roughly given by the fixed point of a function x² - (r), and it is useful bound the ratio of the empirical Ln-norm and the population Lz-norm of element in F-G: G: | /[Il + +r?) S 1/2 with high probability. Finally, we denote (iF' == {v f()) f E F3) for set F of functions. Then, we obtain the following theorem that gives the compression based bound for non- compressed networks.
Theorem 1. Suppose that the empirical Læ-distance between ff and 9 is bounded by for fixed i > O almost surely. Let i := 22 + v2), then, under Assumptions
f Illn S #2
2
1
there exists
a universal constant > O such that
28 +C R.((()) (()) + +
1 1 tM
v S (f) + 2R
n
71
7
main Lerm
biux term
with probability at least 1 1 -t for all t 2 1.
The proof is given in Appendix A The bound consists of two terms: "main term" and "bias term." The main term represents the complexity of the compressed model & which could be much smaller than F. The bias term represents a sample complexity to bridge the original model and the com- pressed model. Typically we have r = o(1/vn), and if we set = (1). then the bias term can be faster than the main term which is D(1/v)) The term (*) (()) can be refined a little bit and the refined term can be evaluated by using the covering number of the model. The refnedd version is given in Appendix (Theorem 5). This bound is general, and can be combined with the compression bounds derived so far such as Arora et al. 2018); Baykal et al. (019)): Suzuki et al. 2018) where the complexity of & and the bias i are analyzed for their generalization error bounds.
The main difference from the compression bound T for z is that the bias term F = |1/ Il is replaced by J. f Øllm which is v times smaller. Since 7 is typically o(1/ Vn) and R2 (F)
can extend the result to data dependent models f and @ by taking uniform bound for all possible choice of the pair F and g. However, omit explicit presentation of this uniform bound for simplicity.

---

Published as a conference paper at ICLR 2020
(G)) can be made in the same order as the main term even faster by setting appropriately, may neglect these terms. Then, the bound is informally written as
( = ( + Op (Rn(O) + J -glln V1/n).
This allows us to obtain tighter bound than the compression bound for ğ because the bias term f/ /n is much smaller than f and eventually we can let the variance term R2 (9) much smaller by taking small compressed model ② when we balance the bias and variance trade-off. This an advantageous point of directly bounding the generalization error of I instead of g.
Finally, we note that some existing bounds such as Arora et al. (2018); Bartlett et al. (2017b); Wei & Ma (2019) assumes a constant margin so that the bias term can be sufficiently small constant (which does not need to converge to 0). On the other hand, our bound does not assume it and the bias term should converge to so that the bias balanced with the variance term, which a more difficult problem setting.
Example 1. In practice, trained network can be usually compressed to one with sparse weight matrix via pruning techniques (Denil et al.) 2013) Denton et al. 2014). Based on this observation, Baykal et al. (2019) derived a compression based bound based
pruning procedure. In this situation, we may suppose that 9 is the set of networks with S non-zero parameters where S is much smaller than the total number parameters: G = { E NN(m, R2, Rp) Ei= (l Ilo S S} where |[ oo the number of nonzero parameters of the weight matrix W(0), In this situ- ation, its Rademacher complexity bounded by R(G) & CMML L log(n) (see Appendix B.2
for the proof). This is much smaller than the VC-dimension bound LE mime+1 log(n) if < Ei= m
Although our bound can be adopted to several compression based bounds, we are going demon- strate how small the obtained bound can be through some typical situations in the following.
3.1 COMPRESSION BOUND WITH NEAR LOW RANK WEIGHT MATRIX
Here, we analyze the situation where the trained network has near low rank weight matrices (W It has been reported that the trained network tends to have near low rank weight matri- experimentally (Gunasekar et al. 200 8 Ji & Telgarsky 2019) (sce Appendix[]fon for the empirical verification). This situation has been analyzed in AAroa et al. (2018) where the low rank property characterized by their original quantities such layer cushion. However, we employ much simpler and intuitive condition to highlight how the low rank property affects the generalization.
Assumption 4. Assume that each of weight matrices ((!) (E I....,L) of any f E F is near low rank, that is, there exists a > 1/2 and Vo > such that
o, o,(W(9) S Voj
where (W) is the j-th largest singular value of matrix W (ai(W)
0).
In this situation, we can see that for any 1 S s S min(me, m we can approxi-
mate W(O by a rank matrix W as |[((e) - W/ Vos Let the set of networks with exactly low rank weight matrices be NN(m, s, R2, RF) == (s E NN(m, R2, Rp)
the weight matrix (4) of f has rank se} for s (8), (s1....,51) sL). If we set G NN(m, s, R2, Ry) ) then we have the following theorem.
Theorem 2. The compressed model 9 NN(m, s, R2, Rx) has the following complexity:
I. E se(me + me+1)
( SCM
log(n).
n
If F satisfies Assumption 4 can set f
VoRk-1 Bz E/= 8 " for any f F. there
ists ğ E 9 such that IIf Gle I F. Then, letting A 1, 122 se(metmeg 1) log(n) and
a
7

---

Published as a conference paper at ICLR 2020
2 12 m. (2LVOR) 1 "Ba
the overall generalization error is bounded by
1 + LM
V (f) - (() + MA + M A2 2i
+ (
with probability 1 - 3
" for any t where C > 0 is a constant depending on
See Appendix B.3 for the proof. This indicates that, if a 1/2 is large (in other words, each weight matrix is close to rank 1), then we have a better generalization error bound. Note that the rank 8ę be arbitrary chosen and f and A₁ are in trade-off relation. Hence, by selecting the rank appropriately so that this trade-off is balanced, then we obtain the optimal upper bound as in the following corollary.
Corollary 1. Under Assumption using the same notation as Theorem it holds that
( ( + M M1-1/20 EE m.)(2VV.R) Bz)"/" log(n) M A
2
20
1 1 tM
n
1
with probability 3 for any t where C is a constant depending on a.
n An important point here that the bound is Oly I "h= which has linear dependency on OLVI, the width mg in the square root, but the naive VC-dimension bound has quadratic dependency
L m) ). In other words, the term in the square root has linear dependency to the number of nodes instead of the number of parameters. This is huge gap because the width can be quite large in practice. This result implies that compressible model achieves much better generalization than the naive VC-bound.
In the generalization error bound, there appears Rd. Even though Rg can be much smaller than Rr, the exponential dependency Rý can give loose bound pointed out in Arora et al. (2018). This due to a rough evaluation of the Lipschitz continuity between layers, but the practically observed Lipschitz constant is usually much smaller. To fix this issue, we give a refined version of Corollary [ in Appendix B.4 by using data dependent Lipschitz constants such as interlayer cushion and interlayer smoothness introduced by Arora al. (2018). The refined bound does not involve the exponential term Ry but instead n: (xc: Lipschitz continuity) appears.
3.2 COMPRESSION BOUND WITH NEAR LOW RANK COVARIANCE MATRIX
Strictly speaking, the near low rank condition the weight matrix in the previous section can be dealt with a standard Rademacher complexity argument. Here, we consider more data dependent bound: We assume the near low rank property of the covariance matrix among the nodes in an internal layer (see Appendix D for the empirical verification). A compression based bound for using the low rank property of the covariance has been studied by [Suzuki al. (2018), but their analysis requires a bit strong condition on the weight matrix. In this paper, we employ weaker assumption.
Let See = = Σ. (x.)) T the covariance matrix of the nodes in the 8-th layer where (x(x) = 17 (wie-1) m))) o...o (W())).
Assumption 5. Suppose that the trained network f satisfies the following conditions: (6) 0, o,(E(s) S 2 =: Uoj-8
for a fixed B 1 and Up O.
If J satisfies this assumption, then we can show that f can be compressed to a smaller one f that has width (mf)=2 with compression error roughly evaluated Il f+ll < (m More
precisely, for given Fz > 0 (E = 1.... L) which corresponds to the compression error in the l-
th layer, let my max j m j4
(2) 22/4). Then, define N,(F) 3+ 3 +
8 (Et n(e-1-") for F (f1 . FL). Correspondingly set
F
m = ( (og(80N(
Then, obtain the following theorem.
8

---

we omit L and log(n) terms for simplicity of presentation, then the bound can be written as Published as a conference paper at ICLR 2020
Theorem 3. Let f = Ek=r Mi RFčk- Then, under Assumption
there exists I with width
m² (m1, m2...., ..., mi) that satisfies 9 NN(m², v 20 max; my Rny 3 max meRp) and
If Olln S.
In particular, may set & NN(m², R (9) S COVVE m log(n) for a constant C C>0 0.
V max; mrB2i V
20
max, mpRp), and then it holds that
See Appendix B.5 for the proof. Here, we again observe that there appears trade-off between i and m because as Fe becomes small, then the becomes large and thus my becomes large. The evaluation given in Theorem can be substituted to the general bound (Theorem D). If F is the full model F. then there appears the number Σí Mggl1111 of parameters which could be larger than n, which is unavoidable. This dependency on the number of parameters becomes much milder if
both of Assumptions 4 and are satisfied.
Theorem 4. Under Assumptions and
it holds that
4/0 47012(1 172a]
VLLV
v(f) s +())+ +C M,
me
log(n)
20c
M 20+1
(LPL 2i ves log(n)
M
RE L2 R2
[og(n)s
L+M! 70
12
2/8
for PL (2LVo Bu) and QL
with probability 1
(0.25]
3 (t> 1), where C. is constant depending B.
δ
Ei=1 me) 17843(1-1720)
4/2
Ele 71
me
ZO
2a
where the Õ()) symbol hides the poly-log order. This tighter than that of Corollary We can see that as B and get large, the bound becomes tighter. Actually, by taking the limit of a, B + co, then
the bound goes to I log(n)
Di= me Moreover, the term dependent the width is 0(1/n) + I
T
with respect to the sample size n which is faster than the rate O(v E/s mz which was presented in Corollary Hence, the low rank property of both the covariance matrix and the weight matrix helps to obtain better generalization. Although the bound contains the exponential term Rí we can give a refined version that does not contain the exponential term by assuming interlayer cushion (Arora al. 2018). See Appendix for the refined version.
There appears exp() (2VL (2VL 1)) which is exponentially dependent L. However, this term is moderately small for realistic settings of the depth L. Actually, it is 7.27 for = 20 and 26.7 for L). The bound is
L 50 (we replace this term in exchange for larger polynomial dependency optimized with respect to the dependency on the depth L. In particular, the term L 2 Vlog(n)/n could be artifact of the proof technique and the I term would be improved.
3/2
nt Vn
n2/3
Finally, we compare our bound with the following norm based bounds; O
by Bartlett et al. (2017b) and o (+ (
3/2
+ +
by Wei & Ma 2019
Since our bound and their bounds are derived from different conditions, we cannot tell which better. Here, we consider a special case where = m (VE) and ((() 1 11 T E I m which extreme case of low rank settings (note that ( has rank 1). Then, Ra Rr 1,
9

---

Published as a conference paper at ICLR 2020
R2-11 Vm and R1-1 m, and thus their bounds are O O(ym/n) and Oly(m + m²) m²)/n)
4/3 respectively, However, 3 and a in our bound V m 478420 1/207 /n V m 14at 11/2077 /n can be arbitrary large in this situation, that our bound has much milder dependency the width On the other hand, the weight matrix has small norm and has no spectral decay (corresponding to small and 3), then our bound can be looser than theirs. Combining compression based bounds and norm based bounds would be interesting future work.
CONCLUSION
In this paper, we derived compression based enror bound for non-compressed network. The bound is general and can be adopted to several compression based bound derived so far. The main dif- ficulty lies in evaluating the population Z2-norm between the original network and the compressed network, but it can be overcome by utilizing the data dependent bound by the local Rademacher complexity technique. We have applied the derived bound to a situation where low rank properties of the weight matrices and the covariance matrices are assumed. The obtained bound gives much better dependency on the parameter size than ever obtained compression based ones.
We thank the anonymous reviewers for their valuable comments, TS was par- tially supported by MEXT Kakenhi (15H05707, 18K19793 and 18H03201), Japan Digital Design, and JST-CREST, Japan.
Acknowledgment
5 PROOF OUTLINE OF THEOREM
Remember that for trained network f. 9 is its compressed version that is included in submodel G. First, we decompose the generalization gap as
f (f) [(V( T (Q) ( ( + (V (
The second block in the right hand side is easy to bound, i..., by applying the standard Rademacher complexity bound (Theorem 3.1 of Mohri et al. (012) with the contraction inequality (Theorem 11.6 of Boucheron et al. (2013) or Theorem 4. 4.12 of Ledoux & Talagrand (1991)), it holds that
( (3) s (9) + VM2
with probability 1 1-c e- Since & a small model, this bound could be much smaller than a naive VC-dimension bound. The first block "bridges" the generalization gap of 9 to that of S. but bounding the first block more involved. We make use of the local Rademacher complexity bound the term. Suppose that the event in which -fー I i holds has high probability (which should be proven later), then it is also expected that (yy, f) sy 9) has small L2-norm. This is true because of the Lipschitz continuity assumption (Assumption D. Actually, the Talagrand's concentration inequality yields that
1 - - v - (i()) - (i) s S ((F) + F 1+M
for (r) = Rr, (1 ( | E f.ge E G. Eعlو < +)) with probability 1 - e Since (F)) requires the restriction |f - gعlا, S f, this quantity is much smaller than the standard Rademacher complexity R,, (v(F) (()), which yields fast convergence rate.
Finally, we should bound the probability of || Ellz. r. This can be bounded by utilizing the ratio type empirical process. Actually, we can show that
(P-Px)(h')
P sup
Set
P12 + +
hEF-9
for r. defined in Eq. 2 where Paf := Σ f(z) and Pf = E[f(Z)] This yields that
Il 9 i,, -11f -1f--0ll I| < (1I 0 +r?) with probability 1-e e and equivalently Il Ell? < 201f 01I2 + +2)) Since |l gll2: f2 a.s., we have Ilf Ill,,, 2(p² r?) 12.
We can show that (f)) < (w(F) (g)) by using the Lipschitz continuity assumption (As-
sumption []. Then, we obtain the assertion.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via compression approach. Dy and A. Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp- 254-263, Stockholmsmassan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. arXiv e-prints, art. arXiv:1901 1911::991,,0884,, Jan 2019.
F. Bach. On the equivalence between kernel quadrature rules and random feature expansions. Jour- nal of Machine Learning Research, 18(21):1-38, 2017.
P. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The Annals of Statis- tics, 33: 13:1447-1537, 2005.
P. L.. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-536, March 1998.
Bartlett, D. J. Foster, and M. Telgarsky. -pectrally-normmaizedd margin bounds for neural networks. arXiv preprint arXiv: 17Xiv:7706008999000 2017a.
L. Bartletr, D. Foster, and M. J. Telgarsky. Spectrally-normaaizze margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6241-6250, 2017b.
C. Baykal, L. Liebenwein, I. Gilitschenski, D. Feldman, and D. Rus. Data-dependent coresets for compressing neural networks with applications to generalization bounds. In International Conference Learning Representations, 2019.
M. Bianchini and F. Scarselli. On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE transactions neural networks and learning systems, 2553):1553-1555, 2014.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013.
O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical process. C. R. Acad. Sci. Paris Ser. Math., 334:495-500, 2002.
N. Cohen and A. Shashua. Convolutional rectifier networks as generalized tensor decompositions. In Proceedings the 33th International Conference on Machine Learning, volume 48 of JMLR Workshop and Conference Proceedings, pp. 955-963, 2016.
N. Cohen, O. Sharir, and A. Shashua. On the expressive power of deep learning: A tensor analysis. In The 29th Annual Conference on Learning Theory, pp. 698-728, 2016.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303-314, 1989.
M. Denil, B. Shakibi, L. Dinh, M. A. Ranzato, and N. de Freitas. Predicting parameters in deep learning. In J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26, pp. 2148-2156 Curran Associates, Inc., 2013.
E. L. Denton, W. Zaremba, J. Bruna, Y. LeCun, and R. Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Z. Ghahramani, M. Welling. C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 1269-1277. Curran Associates, Inc., 2014.
Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv e-prints, art. 18 1110004055 Oct 2018.
11

---

Published as a conference paper at ICLR 2020
G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Thirty-Thib Conference on Uncertainty in Artificial Intelligence, 2017.
E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for ratio type empir- ical processes. The Annals of Probability, 34(3): 143-1216, 2006.
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In S. Bubeck, V. Perchet, and Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 297-2997 PMLR, 06-09 2018.
S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9482-94899999 -991,, 2018.
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In M. F. Balean and K. Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1225 1234, New York, New York, USA, 20 22 Jun 2016. PMLR.
N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight VC-dimension bounds for piecewise linear neu- ral networks. In S. Kale and O. Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 Proceedings of Machine Learning Research, pp. 1064-1068, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR.
G. Hinton and D. Van Camp. Keeping neural networks simple by minimizing the description length of the weights. In in Proc. of the 6th Ann. ACM Conf. on Computational Learning Theory. Citeseer, 1993.
Hochreiter and J. Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
K. Homikk Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251-257, 1991.
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Bach and D. Blei (eds.), Proceedings of the 32nd International Conference Machine Learning. volume 37 of Proceedings of Machine Learning Research, pp- 448 456, Lille, France, 07-09 Jul 2015. PMLR.
Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34:2593-2656 2006.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
A. Krogh and A. Hertz. A simple weight decay can improve generalization. In Advances in neural information processing systems, pp. 950-9550 1992.
Langford and R. Caruana. (not) bounding the true error. In T. G. Dietterich, S. Becker, and Z. Ghahramani (eds.), Advances in Neural Information Processing Systems 14, pp. 809-816. MIT Press. 2002.
M. Ledoux and M. Talagrand. Probability Banach Spaces. Isoperimetry and Processes. Springer, New York, 1991. MR 102015.
X. Li, J. Lu, Z. Wang, J. Haupt, and T. Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint 180600806 2018.
N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Technical report, University of Californa,, Santa Cruz, 1986.
12

---

Published as a conference paper at ICLR 2020
C. H. Martin and M. W. Mahoney. Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning. arXiv preprint 1810001810. 2018.
S. Mendelson. Improving the sample complexity using global data. IEEE Transactions on Informa- lion Theory, 19:199711191, 2002.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. 2012.
G. F. Montufar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural networks. In Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger (eds.), Advances in Neural Information Processing Systems 27, pp. 2924 2932. 2014.
Curran Associates, Inc.,
V. Nagarajan and Z. Kolter. Deterministic PAC-Bayesian generalization bounds for deep net- works via generalizing noise-resilience. International Conference on Learning Representations (ICLR2019), 2019.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference on Learning Theory, pp. 1376-1401, Montreal Quebec, 2015.
B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. A PAC-Bayesian approach to spertrally-normalized margin bounds for neural networks. arXiv preprint urXiv:1707.09564 2017.
B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, and N. Srebro. The role of aver-parametrizattoo in generalization neural networks. In International Conference on Learning Representations, 2019.
B. Poole, Lahiri, M. Raghu, J. Sohl-Dickstein, and Ganguli. Exponential expressivity in deep neural networks through transient chaos. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 3360-3368. Curran Associates, Inc., 2016.
A. Radford, L. Metz, and Chintala. Unsupervised Representation Learning with Deep Convolu- tional Generative Adversarial Networks. arXiv e-prints, art. 1.Xiv:1511.06434 Nov 2015.
J. Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, pp. to appear, 2019.
S. Sonoda and N. Murata. Neural network with unbounded activation functions is universal approx- imator. Applied and Computational Harmonic Analysis, 2015.
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1): 1929 1958, 2014.
I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008
Suzuki. Adaptivity of deep ReLU network learning Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference Learning Representa- tions (ICLR2019), 2019.
T. Suzuki, H. Abe, T. Murata, S. Horiuchi, K. Ito, T. Wachi, S. Hirai, M. Yukishima, and T. Nishimura. Spectral-Pruning: Compressing deep neural network via spectral analysis. arXiv e-prints, art. arXiv: 1808188888800 00558885 Aug 2018.
M. Talagrand. New concentration inequalities in product spaces. Inventiones Mathematicue, 126: 505-563, 1996.
G. Peree, C. Q. Camargo, and A. A. Louis. Deep learning generalizes because the parameter- function map is biased towards simple functions. In International Conference on Learning Rep- resentations, 2019.
13

---

Published as a conference paper at ICLR 2020
A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applica- tions to Statistics. Springer, New York, 1996.
V. N. Vapnik. Statistical Learning Theory. Wiley, New York, 1998.
V. Verma, Lamb, C. Beckham, A. Najafi, I. Mitliagkas, A. Courville, D. Lopez-Paz, and Y. Ben- gio. Manifold mixup: Better representations by interpolating hidden states. arXiv preprint 1rXiv:1806.05266. 2018.
S. Wager, S. Wang. and P. S. Liang. Dropout training adaptive regularization. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Infor- mation Processing Systems 26, pp. 351-359. Curran Associates, Inc., 2013.
M. Wainwright. High- Digee-Dimesional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
C. Wei and T. Ma. date-depnndent sample complexity of deep neural networks via lipschitz aug- mentation. In Advances in neural information processing systems, pp. to appear, 2019.
L. Wu, Z. Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: FrxXiv11700 1706. 10239, 2017.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 2016.
H. Zhang, M. Cisse, Y. N. Dauphin, and Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018.
W. Zhou, V. Veitch, M. Austern, R. P. Adams, and P. Orbanz. Non-vacuous generalization bounds at the imagenet scale: PAC-Bayesian compression approach. In International Conference on Learning Representations (ICLR2019), 2019.
NOTATION LISTS
Since we use plenty of notations, we give the notation list in Table 2
APPENDIX
In the appendix, we give the proofs of the main text. We use the following notation throughout the appendix:
Paf = 1 n ni - f(z)) Pf=EEf(2
To evaluate it, the covering number is useful (van der Vaart & Wellner 1996).
Definition 1 (Covering number). For metric space f equipped with a metric d, the e-covering number NFF, d, é) is defined as the minimum number of balls with radius (measured by the metric d) to cover the metric space F.
Hereafter, C denotes a constant which will be dependent on the context. We let A min(a, 6} and V b = max(a, b} for a, b E IR
A PROOF OF THEOREM
Denote the local Rademacher complexity of (v(f) - - f.ge - $ r) by (r) == RR,((v(()) (() f.g ğ. ll -عاوe sr)
Here, restate Theorem in the following in more complete form. Remember that f E f and g E 9 are the trained original network and the compressed network respectively.
14

---

Published as a conference paper at ICLR 2020
Table 2: Notation list
notation
definition
sample size
2; (z y6)
i-th observation (z,; input, y:: output)
Dn - (zi 1
training data
(y, (x))
loss function
M
-orm bound of models
norm bound of input
|| ll
empirical no-morm (Ifflln == VE f(2))2/n)
1. 1lza
population L2-norm (I1/|lz, == V / (2))
training error (empirical risk)
generalization error (expected risk)
(6)
Rademacher random variable
Rm(F))
conditional Rademacher complexity Rademacher complexity
(x(F))
(F(F))
local Rademacher complexity
f.
upper bound of I| Il,m
r.
fixed point the local Rademacher complexity (Eq. 2
i
/2(F2 +
T.
depth of networks
W(O)
weight matrix of the f-th layer covariance matrix of the ε-th layer
S(0)
R2
operator norm bound of W(E)
RF
Frobenius bound of W(( list of widths of networks
m = (m1. ml)
m (m1, my m
list of widths of compressed networks
S (51...., SL)
list ranks of the weight matrices of compressed networks
F NN(m, R2, Ry)
the whole set of networks with width
$
of trained networks set of compressed networks trained network
PEB F
ØEG و
compressed network an upper bound of the j-th largest eigenvalue of the covariance ma- trix in the ε-th layer of ʃ decreasing rate of the eigenvalues of W(()
(0)
decreasing rate of the eigenvalues of Σ
Theorem 5. Suppose that the empirical Læ-distance between f and ğ is bounded by f Ul S for fixed f >> 0 almost surely. Let i == 2f2 + r?), then, under Assumptions 2 a universal constant > O such that
there exists
2Mt
1 tM
V ( < 1 ( + (9) +
+C ((F) + +
with probability at least 1 -t for all
Note that R(v(F) (G)) in the statement of Theorem of the main body replaced by refined quantity (FF) (we can show (r)) < ()(+(F)= - (()) from the Lipschitz continuity of v)).
Proof of Theorems 7 and 5
First, by the standard Rademacher complexity analysis, we have that
V V
(
(1, )(x;) E ((y(Z.((X)))
n
15

---

Published as a conference paper at ICLR 2020
sup g
(((z))((a))) Flbb(,.
2....
sup LoEg
Σ (
2t V MM= S 2R
(9)
2t M
M
(5)
with probability --e- where we used the Rademacher concentration inequality (Theorem 3.1 of Mohri et al. (2012)) in the third line and the contraction inequality (Theorem 11.6 of Boucheron et al. (2013) Theorem 4.12 of Ledoux & Talagrand (1991) and its proof) in the last line. We let this event be (t).
Next, we observe that
w(f) #() -V(() - -
i()
-V - - V() (
[ V - (v v 2R, (9) + M 2t
(6)
where we used Eq. ( in the last line. Here, it should be noticed that it is not good strategy to
bound the first term v (f) ( (f) (G) by bounding (T( (f) and v ( (
independently, Instead, we should bound them simultaneously to obtain tighter bound. This can be
accomplished by using the local Rademacher complexity technique.
Note that f and are date dependent and them. On the other hand, the local Rademacher complexity is characterized by the population L2- norm. To bridge this gap, we need to bound the population L2-distance | r. between ʃ and g in terms of the empirical L2- Lo-norm bound || -l I F. To do so, also bound the local Rademacher complexity of f - ;: (F 9) Suppose that there exists a function [0. oo) ~ [0, oo) such that the the following conditions are satisfied:
only bound the empirical Læ-distance between
RF - S (lr)
and
6(2r) < 2Φ(r).
Note that Eq. gives one example Φ(r). Then, by the so-called peeling device, we can show that for any 0.
(P- (h))
((r) p2
4t +
2t r2n
P sup heF-C
Mv
.
Se-
Ph2 +
p2n
for all > (Theorem 7.7 and Eq. (7.17) of Steinwart & Christmann
2008 Hence, if we choose
r. (t) that
(r.))
41
21
1
8
+ M
+
M
< r
r2
r2n
2'
then holds that
P(h2) < 2h2 + 2r
uniformly over all h F- - with probability greater than e We let this event (t). In
this event, I| TlI < 22, then it holds that
[|
Tl 2 < 2(p2
Next, we bound ( (
1 ( To bound this term, we apply the Talagrand's con-
centration inequality (Proposition 2 and Talagrand (1996); Bousquet (2002) (2002) ). To apply it, we should
bound the variance and Loc -norm of syy f(x) (v g(x)) (E (Y, f(X)] - Efg (ep((Y(()))) (()))) for any f E F.g E I with |lf glle, I r (where will be set 2( r2)) Due the Lipschitz continuity of v. we have that
(ar(w)(. *(V,g(X)) Varls(X)- o(x)) < || -gl?2 5²²
16

---

Published as a conference paper at ICLR 2020
Similarly, it holds that
(y, (0
I (v f(x)) - - f(x)) (V - gX - 2.M
Hence, by the Talagrand's concentration inequalit (Proposition ))02)), holds that
and Talagrand (1996); Bousquet
sup falllf 90
(P- P.)(o(Y - v(Y,(())))
2F
4tM
2E
(P - P,)(o())((X)) -
+
ffa:ls-- Soillfsllue
with probability at least e- for any The first term the right hand side can be bounded
as
E
sup
(P - (T)-P(o(Y,(())) - -0
f.g:lf- log Sr
< <2E,,...
sup
Σ alv(v f(x:)) (aaa))))-((ma
faalls-alleg Sr
(n),,
where we used the standard symmetrization argument (see Lemma 11.4 of Boucheron et al. (0013 for example). Combining these incqualities, it holds that
Mt
sup f
(P P.) ((X) -(X))) s C ( + trV n
for a universal constant C > 0 with probability at least 1 - e- for all t > 0. We denote by this
event as rt,
We define an event Et( & (t) n (t, Then P(Es(t)) 2 1 - 2e for all t > 0. In this event, Ilf All2, 12 and thus it holds that
t 1 +
v V (6 ( s
((F)
+
n
n
for a universal constant C > Combining this and Eq. (6) we obtain the assertion on the event (t) n (t). This gives the proof of Theorem
To show Theorem [ note that [[x(() (g)lla I If allea by the Lipschitz continuity of
and this yields (f(() - x(g) f e F.ge E I. f - عala, I r c (v(f) (gg) f E F.g e
G. (l+()) ro)lla, r). Therefore, we have
((r) < (*) v()).
Hereafter, we derive some upper bounds of the (local) Rademacher complexities under some cover- ing number conditions.
Lemma 1. For given Then, it holds that
O, let in = (D.) == sup alln Ilf 9lle, S g. E 9).
max (r)), Rr -
1 + En,
log(N((F1) -111 101111//22 e/2)) de
('n
log(N((G, 1l e/2)) de
1/
1/n
17

---

Published as a conference paper at ICLR 2020
and
((r) S - (V)) (og(2n))),
where C, C" are universal constants.
Proof. The conditional Rademacher complexity of the set {e(y, f(x)( by g(x))()))))))))))))) I F,g g. [lf -gll,, S r) can be bounded by constant times the following Dudley integral (see Theorem 5.22 of Wainwright (2019) or Lemma A.5 of Bartlett et al. (2017)) for example):
log(N((bb(f)) (()) I F, G. 15 2l1ee S sr). 11 llx. de
inf a>0
a +
n
9m
1og(N((W(D)- - F, e θ, |/s معاوو S sr), 11 11, (l) de
(9)
71
1/n
(o II, e/2)) + (V Il e/ e/2)) de
71
1/n
n
An
log(N(FF 11 mm,, e/2)) + log(N((, 1.l...ll./2 de
1/n
Am
log(N(F 1.1lnn e/2))
+ f
log(N(E,11 (lns de.
(10)
1/
n
1/n
n
n
S e for f. E and 9,9' E θ with f'l, I e/2 and ||g - gl e/2 in the third line, and I-Lipschitz continuity of the loss function 1b in the fourth line (i.e., jb(y, f(x)) v' (()))())) = ff(x) g(x)
where we used [lv(f)) -v)))(((()) (gg')) n - -((()) (1v())))
which yields [f - (())ln I Ilf ,lln),
In the same way,
that R, (F 9) is bounded by the Dudley integral as
(F 9
C
F.g G.
Tlle. sr), I1 ()) de
$
+ CED.
n
n
C fr
(og(A((F11)
1l,, e/2))
log(N(
|| ll e/2))
+ CED..
de
de
(11)
n
n
1/n
where we used the same argument as Eq. Eq. 77.
and C > 0 is a universal constant. Then, we conclude 10
p can be evaluated by using the local Rademacher complexity of (F) ( Note that [}x(() د ||/ 9Tاوو by the Lipschitz continuity of 1/r and
Next, we show Eq.
8 The term Eq.
this yields (v( ((g) 1 f F.g G. مااو S r) C (v(() w(gg) f E F.g
G. [f)((f) - 2l(g)) (L, < r). Then, the Sudakov's minoration (Corollary 4.14 of Ledoux Talagrand (199T) gives an upper bound of the right hand side of Eq. 9
AM
log(N(HW(f) - (()) f E F. .g E G. Ilf Allee I rr)1l Im e)) de
1og(N((V())- ~() F. g (.1(()) Ge)llea S <rb.ll []n de
J1m
n
( Rn.(((1F) Vlog(n) - s (
$
log(n))))))
e
18

---

Published as a conference paper at ICLR 2020
where (x))((())) == E. (ups Ei= (I f(x))) - ((.. If f ف. (v(() ( sri].
Since In S 2M, the expectation of the right hand side with respect Dn is R. (I) (()) (og(n) (2g(2nM)) This gives an upper bound of the right hand side of
Eq. (9) and yields Eq.
Lemma 2.
E Supp(Pntt E h F- 1/ile sri s + + +M)(r)
Proof. By the contraction inequality of the Rademacher complexity (Theorem 4.12 Ledoux & Talagrand (191)) and its proof), we have
sup Phhh T t Ø: |Alll, sr] < E (upp((p - P)h² h E - - :llllles s sr]] +
E
S 2E sup Σ (h(a:)? h E E - 3 | rr} +
(symmetrization; Lemma 1 11.4 of Boucheron et al. (013))
2ME supl
1 -
Σ (((()))) | 1 f |1 sr) +
(:. contraction inequality)
1=1
S 2M > 2Mx(r) +22.
Lemma 3. Suppose that
suplog(N ll,, c/2)) + sup sup log(N( | (ln, < 81 + S2 Sogo/(//)) + S3c -2g Dn
Da
for < 1. Then, for a universal constant C' > 0 and a constant holds that
C. > 0 which depends on < 1, it
+ M S1
S2 log(n)
S
S2 log(n)
((r)= S max
+ +r/
n
n
n2
1
MM--9S3
1-1
S3
C₁
+
+ r 1-g
In particular,
S1 + S2 log(n)
( MM--9Sa
T#a
1 + MI
r C M
n
n
n
Proof. Remember that in == sup - glla Il - =ll6, <r,f E F.g E 9) for a given > 0.
Under the assumption, we may take Φ(r) (defined below) an upper bound of (r) by Lemmal
(1
1 vn
((r) c +++
VS S2 log(c=)) + Syc Syc-
n
1/a
where C > O is a universal constant. The right hand side can be evaluated as
An J
E
VS, +
Sz log(1/e) + Sze 22de
S in / + Sy log(n)
+ 1 -
Ey
1/n
$ EiPphh
h -- [ille, S Srl//s + log(n)
VSa
| Chllk s "1
+
1-q
19

---

Published as a conference paper at ICLR 2020
& V12 2M + log(n) + vSa
1- (1² 2M
(12)
where we used Lemma]
2 Hence, if the first term is larger than the second term, we have that
1
Si + S2 log(n)
((r) 50
+
Vr² 2M
C +
Si + S2 (og(n)
S1 + S2 log(n)
x(rr
C²
M
+ +Crv
+ 2
Therefore, obtain that
2C + 20 S + Solog(n)
S + S2 log(n)
<(r) S
2CrV
(13)
n
On the other hand, if the second term in Eq. gives that
is larger than the first one, then Young's inequality
o(r) IC
1 n
+
V n(1 (01-g)2 2)2(1² +2M
S3
c 1=20 nil ( q)²²
T47 + (1 9) 2M0
2M
S3
W
+
+
2((1-9)
d'
n(1
q)²
where d' > 0 is any positive real. Thus taking e' sufficiently large (which depends on M, q), we conclude that
1 + (()) S C.
M MM--53
S3
2(1 gg)
(14)
n
72
n
where Cy a constant depending only on g < 1. These two inequalities (Eq. (3) and Eq. (14) give the first assertion. By noticing the assumption M 2 1, r, can be derived from simple calculation.
B DERIVATION OF COMPRESSION BASED BOUND FOR NON-COMPRESSED NETWORKS
B. FULL MODEL BOUND
Here, we assume that the model F of the trained network is the full model f F NN(m, Re, Rp) and ğ is included in NN(m, Rg, Rp). Then, their covering entropy is bounded by
log(N(F;11 lll, c)) mogge))
L
(ome))))og([(() V ()maxmm 1)).
lo,(NV(,,11 (1lbo,)))))) <
1) logle 1) + L
mcms+1) Log(L V 1) + 1)).
2=1
Hence, the condition in Lemma holds for S Ele
m.m2411 S2 = LS log( V Rs V
(Inxx me + 1)) and Sy = In this case, we can set
2 c (M + 1)(Si 1 + S2 log(n)) + Mt.
for constant C 0.
20

---

Published as a conference paper at ICLR 2020
B.2 COMPLEXITY OF SPARSE MODEL (PROOF OF EXAMPLE
Suppose that 9 is the model with sparse weight matrices given in Example and = R2, then we can see that
Let m max; mg
ğ C (L,, m. S,
where the definition of (T,,, m, S, B) is given in Appendix C.1 Therefore, its covering number is bounded by
log(NV(, (l,lo,)) S Sloog(e - LS log( L(2 V () + 1)) & O(SLlog(n) + (S (log((
by Lemma
Hence, the Rademacher complexity is bounded as
S g s CMM L (Rg V 1) + 1)) O M L- log(m))
s
by the Dudley integral, R(9) S lo V log( -1xx ()) de, where C is a universal constant.
B.3 NEAR LOW RANK CONDITION ON THE WEIGHT MATRIX (PROOF OF THEOREM 2 AND COROLLARY )
Here, give proofs of Theorem and Corollary [ which give generalization error bound when the trained network has near low rank weight matrices (W())/ (Assumption 4
Under Assumption 4 we see that for any by a rank s matrix W as
min minn(mm, mc+1), approximate W(O
[ W S Vos | S || 1|
(15)
|| w'
Vo(s (22-2/22
(16)
22a
This can be checked by discarding the singular vectors corresponding to the singular values smaller than the s-th largest one. This ensures that, for any f E F. there exists f E F such that has width s (81....,81) weight matrix WH()) with ||Wa(())|2 S R2, || S Rr and
Ilf f'
Σ VoRk-1 5, BB.
(17)
This can be proved as follows. Let ('(x) G (Wi(L) n(-)) ... o (Wi()))) where Wi(())
a rank 82 matrix that satisfies Eqs. 15) and (6 for W wz((). Let fe(x) G
(()))))())).................)))) ((le))))....(((())))))) ())((((+))())))))))))))) (W())))(()))))p))))))))
(W()))))
(W())) and fu(x) = Then, 1ffff'll S
Eta fee We can see that [[W (W( S II [| |z||| S R²B, B.
(W(1x) - (W(On()) o (w(+-)) m()) .... (W())) < ( - W200 (ell (()) o (W())) x)ll s Vos, R
l(wt(mm()) o m())
B,. This gives I] fell S
The [| Vos, p B, < R R Vos, Bz. Finally, by summing up this from 1 to L= we obtain Eq. (77
In particular, for any > O, by setting 8/ = (e() = min(((e((VVRR) -,)) me A m
for all É, then Il fo I This indicates that, by Lemma 5 the covering entropy of F is bounded by
log(A((F.1) -.l.e,) ())
Σ (me + met1)s((c/2) [log(c-)) + log(2 1) + +1)]
(18)
L
< 2
V me) (2LV, "hc + 2L ( + 1))]
21

---

Published as a conference paper at ICLR 2020
As the compressed network G. we may choose 9 = NN s, R2, Rp) for ($1,..., .L) that, for all f E F, there exists g E Ô satisfying
gl (ViR22 B₂)
$t"
Hence, we may set f2 = [(V6R22-1 BB) "7 In this case, the covering number of G
bounded as (88) by replacing 5% with sg-
Therefore, Lemma 3 gives that
2 S C
(M + 1)(1 + + S2 (o)((()) + Mt
2a V M 20+1
S3
2a
where
S Σ
(m me+1);
E-1
S₂ LS, log (R2g V () 1)),
1
S: (2LVol - B,,) + 2L log(2 V () me + 1))]
where 9 1/2a was used. This indicates that, if a 1/2 is large (in other words, each weight matrix is close to rank 1), then the local Rademacher complexity can be small. Actually, the bound smaller than Σee memell because each rank 88 must satisfy 8g S min m
Finally, observe that
El selme + me41)
(9) SCMV
log(nL(Rg V 1)(max m. + 1)),
n
by Lemma 5 for = NN s, Rs, Rp) and the Dudley integral (van der Vaart & Wellner 1996 R(G)
- M (I de. This gives Theorem
n
Corollary can be obtained by substituting s; min(me, me+1. [VVol Ba 1/a3.
B.4 IMPROVED BOUND WITH LIPSCHITZ CONTINUITY CONSTRAINT
In the generalization emoor bound of Theorem 2 and Corollary [ there appears R2. Even though Ra can be much smaller than Rp, the exponential dependency 125 could give lose bound as pointed out in Arora et al. (0018). We improve this exponential dependency by assuming the following condition.
Assumption 6 (Lipschitz continuity between layers: Interlayer cushion, interlayer smoothness (W(L) o.... (W)))), let de(x) no (W(t-1) ())))))) (oo.....(())) be the input to the l-th layer and Me,e (w(e") ()) oWW be the transformation from the t-th layer -' layer. Then, assume that there exists such that t < 1/(2x² L) and for any é,C E [L].
Arora et al. 2018)). For the trained network - Go
(Mer +c(1)) - Mer((b((1s) + x² +
for all ((L) (5(2) (..,),..(11))) (1 R and g(2) (5(2)
En
(2)
T
E R
22

---

Published as a conference paper at ICLR 2020
This assumption is simplified version of the interlayer cushion and the interlayer smoothness in- troduced in Arora et al. (2018). Although a trivial bound of A is K I R2 the practically observed Lipschitz constant is usually much smaller. Assumption [ captures this point and gives better de- pendency on the depth L. Actually, we can remove the exponential dependency on R2 as in the following corollary.
Corollary 2. Under Assumptions and 6 it holds that
( = ( +
M M111//2
m2)(2 B2)1/ log(n) M 204
2n+1
+ LM
for A/2 L Eie me) B.y" with probability 1 3e for any > where C is a constant
depending a.
n
This is almost same as Corollary but the exponential dependency on B2 is replaced by the Lips- chitz continuity x².
Proof of Corollary
2
Suppose that
8t min me, me+1, [(4xVo))
(19)
then we show that Eq. 17 can be replaced by
Ilf P'ln S
Von ss
Bz,
(20)
where if 8g = minfme, me+1] ). then 8, term can be replaced by (which means no-compression in the layer f). Once we obtain this evaluations, then the following argument is same as the proof of Theorem 2 and Corollary (Sec. B.3).
Let (x(x)) = (W(0n(-) o (w(x) and of(x) = n (w)(Om(-)) o ... (W2()x) for t 1, I,.... L- 1, and let Φ1(x) Go (()))(())) o.... (W())) and of, (x) Go (W
....o (w) Let Cp 2kB.. We will show that
& 5
1 oilla S 2RVOCB
Σsg
llofln I CB.
for all h = 1...., L. We show this by inductive reasoning. To do so, we assume that, for A: I,..., l 1, this is satisfied, and then we show this for k L. Note that, for all & with < holds that, for any L' > k.
|| M o of Ma- Ma-1. S <(ll - ((W(1)) 1i 1l + (1) ob -
S <<Vos " 110t_1ll + TK| - ox-1 llm))
SK Vo Cn
+ TR2KKCC
Σ 8j
(by induction)
jSk-1
A-1
$ RVVC
$
+
L
Σ
9
(by the assumption of 7).
j=l
Note that the term 8% can be replaced by if sy = min(mm m6+1 which corresponds to the full rank setting (Wi(k) = W(k), Therefore, we have that
l1 - of
|M o M1-1, 01-1.003-111 03
S 24VOCB
Σ s
Under the setting [19 this gives that
11 0illz S Cn/2.
23

---

Published as a conference paper at ICLR 2020
Finally, noting that || I CB/2, we have
100 S CB.
This concludes the inductive reasoning.
Finally, noting that f f= Ø and f" oi we have Eq.
20
B.5
NEAR LOW RANK CONDITION ON THE COVARIANCE MATRIX (PROOF OF THEOREM 3 AND THEOREM
Under Assumption 5 f can be compressed as follows. Suppose that the network is compressed to smaller one upto the & - 1-th layer and the weight matrix of the compressed one is denoted by (W where each W has size m X m (here, m I my is assumed), and, in the é - 1-th layer, W has size my x m²_1. The input to the é-th layer of the compressed networkis denoted by (b((x)= = (WHRe-1) Wi()))).. ...). Let rā IIll - dilll and Et =
1
For a given matrix E and a precision 2² > 0, the degrees of freedom are defined as
my
Σ)
Ne(r* Σ)
(21)
Σ +
Since the degrees of freedom are monotonically increasing with respect each oI(E), we that Ne(r2, Σ) 2 Ne(1 E') if Σ > E'. Le
m (5 (0)) (og(80N)(r?,211))))
then Proposition tells that there exits matrix A E me x m and Je c {l...., m such that
I Too T Aevi,, f, 11 S 4r (Fio + - s 1//11
(22)
for any E I 5 and the norm of A, is bounded as
20 3 me.
Ae S V
Next, evaluate the degrees of freedom of 2 We bound this by using the degrees of freedom
of Eee-- First note that r |llle dill Let m. For any matrix U E Rmmess such that U. = 1,. Tr 20 = Po UU of s UUP oi] + Pa - TUU (Ø:
bi) by the Cauchy-Schward inequality. Here, let U be the matrix that gives PT TUT Di=me-s41 (S()) = infu:uTu=,, Pa 69)l < Pullor - 0212= s r2. we obtain that Pu UU Φb S m (E()) + +2]
UU od =
Po UUT TTeeee. then by noticing Pa - TUT
Finally, by minimizing the left hand side with respect to U, we obtain that
m2
2
Σ
+
j=m -+t
j=m
By setting s = my
m + for S m I mg, this indicates that
mc
mi
Σ jm
o ( (1)
2 2
Σ o (5))) + + j=m
2
Σ j=m
+ r
"The definition is not dependent on f, but to make clear that we are dealing with the f-th layer, we use the
notation Ne.
+ [x]] is the smallest integer that not less than J: E IR. For vector Rm and index set J E (1....,m]) m), is the vector corresponding to the index set J. that is, Φソ (z,) (r)))
24

---

Published as a conference paper at ICLR 2020
Now, let mi min(j m.) l S r2) (if pmm
(0)
r², then we me me). Then,
my
No(r2, =100)
Σ
S sig +
Σ
j=1 Jj (2) + ,²
(x(2(0))
+
soriee
I ms +
(0)
I
me
+ p²
2 + Σ o, (E())
72
J2m
2
1-8
2
merr
< mn +
2 + 00
S r1
+
r( +
p2
B
,2
3
2
mpr
+ 1
2
< mr +
2 +
m4
+
2
y²
B 1
B - 1
p2
Now, let
1 22
= x²
4
then
8 +
Ne(r², Σd
(0) -
me +
3 -
We define the right hand side as m
8 +
my + 8 1
m =
8 -
1/
We have, by Eq. 22
m4+1
Σ In(w ( (3) - -/(W A A.de
54
Σ
|| Jj:
1|2,2
1 22
<
AR
X
R
By the induction assumption, we also have that (1 0 l = (1 ot) ( < | S RR57..
Combining these incqualities, if we define
oin = 54==7(W() Aco (x)),
and set WF(() ((E)) Ae and reset W + wi((-1) then it holds that
Illde-1 o Illm S re41
where we let
re+1 = Rere + Rpft.
Letting ro 0, by an induction argument, we obtain
R (L-)) k) Rpin-
r++1 S
Finally, we obtain
1f- S <
Σ p ((L-K) ki ReTe
k=1
for a compressed network fz that has width m = mú,) with parameters Wt(()
(( Ae. Note that Jeiin
20 || S ([ Ilellllll S Ray 3 m,,
20 | < (| Je [ |llll S RF v m,.
25

---

Published as a conference paper at ICLR 2020
Therefore, if we set = NN(m", v 20 max, mell,, / max; meRf), then there exists 9 E g such that
|5 Fl1n 5
where
,² r
Moreover, applying Lemma to 9 and the Dudley integral yields
R S CMV Ei m4mi+1
log(nL(Re V 1)max + 1)2).
This gives the assertion of Theorem 3
Here, we consider situation where 12
for some constant co > 0. Then it holds that t
Té+1 = R2 1+
Tt
R
II
1
S RS exp (o(2vé-1)) ri.
l
k=1
Therefore, by setting Cz == (1 R₂) exp (c((2VL-1)) 11). holds that rt S Clri for
1,..., L. in particular, we have
Curi
In this situation, the degrees of freedom are bounded by
Ne(r², ve(r2,=(()) - m = 3 + me + 8e
Next, we bound rhg To do so, we should bound ÿz from below. Note that
R2
R2 R2
8-1
R3 1 f-1
Fz
R
Vi
Tt- =
Rg
1
k
ni
R
Vl
1+
k
k=
kml
Rg
ri Ro2y 1
(1 200 2c0((8 1)) 1i Rr Vl
1+
R Vi
k=1
Ro
| ri.
+
200(1
Rp
/l
Hence,
-2/8
col22
mh S (F2/(4U6)) 1/8
< (1U))
+ 2c0
Ve r1
Rp
Ve
Rp
2/8
(1
-2/3
1/0
< (4U))
Co
2
Aco
T1
2/8
<
(0.5 ^ co) 222
228
r1
2/8
By Lemma we can evaluate r for f satisfying Assumption
as
2 C (M + 1)(S + + S2 log(n)) + Mt
2a
Sa
142a
V M
n
where
S Σ mmm
L
S, = LS, (L(22 V 1)(mxxm; +
= 1)3)=
L Σ
mmmiun log(m)
26

---

Published as a conference paper at ICLR 2020
S3 = E mz) (2LV - "/ ([og(())) + 2L log(2 () my + 1)
E=1
mz) (2)VoR - 1/a log(())
0
Then, the overall generalization error is upper bounded by
S3 (2(1-1/20) + (M3 F2)L Dé-1 mfmb log(n) + Mt C r +
( & $
with probability -e for all t 2 1. By letting LL,,, LL (2LVoR) i < the second and third terms in C[+) is bounded by
R -1 Ba) Ba) log(n) and assuming
[ine + ERG (c} -/=1
1
C'M
log(n)3
n
L
4Ug
2/8
11 +
-4/3
L3
13R4/E3 R
$ O' Inan (e) + 20'M
(0.5/00) ) (
log(n)3.
Y1
Hence, by setting CLUi (با me
4/P+2t1-1/20
which balances the first and the second terms,
then f Crri $ 1 and the right hand side is bounded by
418
2(-11/20)
Vn
mp)
1784211111 1/20
4/24211
1/201
375 17203
2(1-1/20
EE m²)
4/8 7,
1750 (Cz)//3
RUR
2/3
+
CM
L
log(n)3
RC
La
+ CM
log(n)3.
R
n
Finally, by setting cp = 1/4, we obtain the assertion for
R2 V R2) exp (o(22/T-11) 11)
2/3
4U6 R3 v R2) exp (1(2VT.- -
2/0
QL
<
(o) (2)
(0.25) 12)22
This gives Theorem
B.6 IMPROVED BOUND OF THEOREM 4 WITH LIPSCHITZ CONTINUITY CONSTRAINT
Here, we again note that there appears R/ in Pt and QL in the bound of Theorem This is due to rough evaluation of the interlayer Lipschitz continuity. We can reduce this exponential dependency under Assumption 6
Corollary 3. Assume Assumption 6 in addition Assumptions
then the bound in Theorem
4 holds for the following redefined PL and QL:
2/3
RG exp (xp 12VT 1))
Pr = (2LVon Ba Qr
(0.25)
except that the term M R3 n2
log(n)) n
replaced by Mx² R% 122
log(n)
v V M
[P V Q
Σ m
log(n)3
n
27

---

Published as a conference paper at ICLR 2020
2a
M 20-1
[PP,
بلك log(n)
2047
+ MR R2
log(n)
+
1+
Proof of Corollary 3
To show Corollary
3 we
fz
R
k=1
where Co constant, and by the same argument as the proof of Corollary 2
we can show that
TE 2x
1
Then, through a cumbersome calculation, we have that
rt
Σ C kR
Ve,
Pt
cu
for a universal constant C. Moreover, we can show that Ty can be bounded as
c0((2/EtI11)
S 2k
This also gives
rL S C² exp(c((VVL-1)11
a universal constant C². Then, redefining Cr. = eexplco (2VL 1)), we can apply the same argument as in the proof of Corollary
2
Indeed, we can show
RU
1/8
8+1 1
R2 mh + C
2/8
m
m
r1
B 3-1
From the above argument, if we set Ō = NN(m",
20 3
maxt my V max; my mFRF), then there
20
exists & such that
1f Gllm S
where
#2 rt.
Moreover, show
2 S.CO (M 1)(S, + 1 + S2 S2log(n)) Mt
20-1
S3
142n
M
n
n
where
S
mfm
1=1
82 LS, log( (R2 V 1)(mxx me 1)3) =0 =) (111 m log(n)
S3
mz) Ba)) 1/0 (lg(()) + 2L log(2L(Ra v () my + 1)2)]
1=1
=0 L
m2) B/ log(n)
Here, to evaluate S3, we used the argument in Sec. B.4 (proff of Corollary 2
The remaining argument is the same the proof of Theorem 3 and Theorem 4 (Sec. B.5
28

---

Published as a conference paper at ICLR 2020
C AUXILIARY LEMMAS
In this section, we give several auxiliary lemmas that are used the proof of the theorems. These results are new all, but we explicitly present them for completeness.
C. COVERING NUMBER OF DEEP NETWORK MODELS
Define the neural network with height L, width m, sparsity constraint S and norm constraint B as
m,,, S, B) {Go (W())())) + (())) .... (W + +D) [W()) R!xm ((7) R, ((1) E Rmxd ((0) R", w( E mmxm b09) E R (1 < L),
E (=1 (1 + 1lo) s S, max || v || B),
where || llo is the lo-norm of the matrix (the number of non-zero elements of the matrix) and || is the -nom of the matrix (maximum of the absolute values of the elements).
llo
The following evaluation of the covering number of the model + (L, m, S, B) shown by Schmidt- Hieber (2019: Suzuki (2019).
Lemma 4 (Covering number evaluation (Schmidt-Hieber 2019 Suzuki 2019)). ). The covering num- ber of ④ (T,, m, S, B) can be bounded by
log.N (C S, B),1I 11,,, s 5log(6 1) 1)24) < 2SL log( (B V 1)(m + 1)) + S 100((811)))))
Proof of Lemma
Given a network f E (LL, m, S, B) expressed as
f(x) G n(.)) + ((L)) x b()),
let
(x)))))) = oo (w((-1), l(k
(W())x + b(2),
and
(z))(x) = Go (w(")() (()) o .... (w(*) + b(k)),
the last and first layer, we define (f))(f) and (z) x. Then, it easy to see that f(x) Bx+1 o (W()) +b(*)) o (x) Now,
for 2. Corresponding
suppose that a pair of different two networks f.g E @L,, m, S, B) given by
f(x) = Go(W (4) m()) (6(4)))))))--)--)))))))))))))))) (W g(x) (o(W(1))
(W(')=-60')
has parameters with distance | (( 11.0 S 5 and | -100 S.. 6. Now, not that |/) S max; [[] |
+ B S (B V and similarly the Lipshitz continuity of B&( with respect to 50 norm is bounded as (Bm) Then, it holds that
+ [b] I
1)(m + As-l ls) I (Bv1)*-1(n)) + 1))
[f(x) g(0)
B (W(()) +8(00) (x()(z)) Bkt1(g) (W(+). +b(0)' An())())
Bmm) 1.- (| (x())(=) (W(+). +6(0)) Ax())
B öL(B (
29

---

R2 and [| S Rp. The covering number of Published as a conference paper at ICLR 2020
Thus, for fixed sparsity pattern (the locations of non-zero parameters), the covering number is bounded by (6/LL(BV (m + 1) - There are the number configurations of the sparsity pattern is bounded by ("m*+))") z (m + 1)45, Thus, the covering number the whole space & is bounded as
(m + 1)45 (5/1[(Bv1)) 1)
1)245
which gives the assertion.
Let NN(m, R2, Rp) be the set of neural networks with depth m || NN R2, Rş) can be bounded by
Lemma 5 (Covering number evaluation).
log (NN((m, R2, Rp), 6))
mcm++1) loge+ L L(2 V 1)¹ 1- (max my + 1)a²)
mcme+1) log( log(t + L t=
(ome4))log((L()) V 1) + 1)).
8=1
Moreover, the set of networks with low rank weight matrices, NN(m, R2, Rp), has the following covering number bound:
log PogN(NN(m,,ss s, R2, Rp), 1l
(m + me+1) log(6 L 1)26- (max my 1)22.
Proof of Lemma 5 Let B R2, m max, myg and S Σt memgg11, then can that (N R2, Rs) is a subset of 4(L, m, S, B) because || 1oo < || |2. Hence Lemma 4 gives the first assertion. As for the second one, ber of NN(m, s, R2, Rp) can be bounded by the one given in Lemma 5 for 4(2L, m, S, B) with
can easily check that the covering num-
S= El se(me + me+1). Then, obtain the second assertion.
C.2 COMPRESSION ERROR BOUND FOR ONE LAYER
The following proposition was shown by Bach 2017D: p. Suzuki al. 2018 Let Σn E Rx"
for integers K, H E and a matrix Σ,,r' E I xxH be a matrix (En for the index sets [me]* K and I' E [me]" Let F = {1. me) be the full index set. Let the degrees freedom corresponding to Σ be Ñ(A) == Ne(A, Σ) (see Eq. (2 for À > 0.
Proposition 1. Let U (U,,),, is the orthogonal matrix that diagonalizes Σ, that E Udiag (Ai...., ., Pim,) U for ù 20 1,...,,,!! Define
1 mc
(
T/ = ((A)
22
+ "bs (j E fl...., me))
(23)
j.1
P
X
2(2)
For X >> 0.
m > (N Log(SO
then there exist U1, ..,, Um E (1,...,,oo, m² such that, for every E RRm,,
inf BER
a (F(FF
Σ (5n(Fe-1
+ mX
< 4Aa T -T) (24)
1=1
30

---

Published as a conference paper at ICLR 2020
and E/=1 1 1/11 I 3m me, where ||31| D==1 8J Let mXr' and I, diag (T).
Then, A : EF.r(Es, +1,) for J = -Vi..... Um satisfies
20
|l S V me,
and the optimal that achieves the infimum is given by B = A a for any a E Rm.
C.3 CONCENTRATION INEQUALITY
Proposition (Talagrand's Concentration Inequality (Tlaggand, 1996, Bousquet 2002 ). Let g
be function class X that is separable with respect co-norm, and { 1 be i..dd random variables with values in X. Furthermore, let 2 0 and U 2 be == supyeg Blig - B(g) and
U == supgeg log then Z == supgeg 1/2 +L= g(z,) - Elg]/. we have
2Bt
21t
P 2 28|2]
S Set
(25)
n
n
for all
D NUMERICAL EXPERIMENTS
In this section, we experimentally validate the assumptions we made in the theoretical analysis and investigate how large the intrinsic dimensionality becomes. We use VGG-19 network trained on CIFAR-10. The VGG-19 network have 16 convolution layers (named c0, .... c15) and fully connected layers (named 116,-. .l.. 118). The size of each filter in each convolution layer is 3 x 3. Our theory does support convolution layer in strict sense, but adopt it follows. If the convolution layer in the f-th layer has the input channel size my and the output channel size mg+1 with the filter size l x ls (in case 3), then the weight matrix is given 4-way tensor with the size m4+1 X me X A x k: W(()) gm xkxk Although singular value of 4-way tensor not well-defined, we can perform low rank approximation of the weight matrix by folding out the tensor to a large matrix. Actually, considering "similarity" between the filters
k:
me++
K(0) = Σ
Σ
( ioMing
( J,0,1182
E R Xme+1
xx=1
i==1
then easily see that, for se [meti], it holds that
me+t
- PT
Σ ay (K)))
where P E Porxme+1 is a projection matrix to the eigen-space corresponding to the Sy largest singular values of K(e). W PW ( P.e W:(t) (2)
V.j.k. (.J.A.)))))......l....... [[b]]( and the Frobenius norm || ||r of a tensor the Euclidean norm as vector. Therefore, we can use the
eigenvalues of K(t) to evaluate the redundancy of parameters among filters.
As for the covariance matrix in convolution layer, we also apply the same argument. That is, the input to the ε-th layer (which is a convolution layer) is given by dr(z) E RmmeXxx where I and J are the width and height of the input, and we define the following "covariance" matrix as similarity measure between the channels:
mi.m
1/ = 1 Σ Σ n
Σ 1S455J
de (
R
m
This also serve the redundancy measure and analogous argument to the main text be applied.
31

---

Published as a conference paper at ICLR 2020
Near low rank properties of the covariance matrix and weight matrix Here, plausibil- ity of the near low rank assumptions we made in the analysis. Figure !| presents the eigenvalues of covariance matrix {e in each of layer c2, c7, c12 and 116. The eigenvalues are sorted in decreas- ing order. We can see that the eigenvalue distributions are highly concentrated around 0 and the eigenvalues decrease quickly, which indicates the near rank property of E(e)-
30-
3102 valo2
599
LG-
130
(a) c2
(b)
1.5
3900
Inder
(c) c12
(d) 116
Figure 1: Eigenvalue distribution of the covariance matrices
Next, we plot the eigenvalues of K(e) in Figure 2 for layer c2, c7, c12 and 116. We again observe rapid decrease of the eigenvalues. These results justify our theoretical assumptions.
layenic Insight
Insight mati
2190
0.0
Inder
Inter
c2
(b) c7
layenc12 besight mani
syentté Instghtmani
2.2
1.7
510390 601E
1.K
3.7
344
Inde:
Insex
(c) c12
(d) 116
Figure 2: Singular-valee value distribution of the weight matrices
Intrinsic dimensionality Here, we calculate the intrinsic dimensionalities of the VGG-19 net- work. For that purpose, set threshold parameter {10-1, (10-1,10-2 10-33 and compute
32

---

Published as a conference paper at ICLR 2020
Table 3: The effective ranks tin and se in each layer for each threshold v. "In/Out" indicates the channel sizes of the input and output.
layer
In/Out
Cov (rite)
Weight (st)
V 10
10-2
10
V 10
10-2
10
c0
3/64
3
3
16
19
cl
64/64
5
21
51
26
62
64
c2
64/128
5
33
64
37
110
128
c3
128/128
9
76
128
50
128
128
c4
128/256
11
110
128
102
255
256
c5
256/256
200
256
93
256
256
c6
256/256
17
219
256
55
230
256
c7
256/256
253
175
252
c8
256/512
10
35
129
30
122
349
c9
512/512
6
33
16
60
217
c10
512/512
3
15
41
16
42
127
512/512 c11
2
12
23
39
129
c12
512/512
2
7
16
7
18
46
c13
512/512
3
6
16
22
46
c14
512/512
3
18
16
38
59
c15
512/512
4
14
28
36
51
92
116
512/4096
10
21
49
117
4096/4096
7
10
11
10
49
990
118
4096/10
10
9
82 = #(i E [meta] (K())) 2 maxy (K)) and mh == #1 E [me] o ( > v X max, o (Ee) (which corresponds to setting 7 = 4y x max, By ( Table 4 sum- marizes the effective ranks rize, of all layers. We can that the effective ranks smaller than the channel sizes several layers (especially layers from c8 to 118.), which indicates the network has high redundancy and its intrinsic dimensionality could be much smaller than the actual number of parameters.
be much
Next, compute the intrinsic dimensionality of each layer based the effective ranks calculated above. Basically, the main term of our bound (Theorem 4 is given by Et= 1hs+11 (note that
mi is essentially controlled by ryy). Hence, we employ mh++1 me as the intrinsic dimensionality of each fully connected layer. As for convolution layer, we employ thf4ithg as the intrinsic dimensionality which is the number of parameters of compressed network. We also calculate the intrinsic dimensionality obtained by compressing only weight matrix. That is given by sym,k? 2 + me+18t. Both of them are summarized in Table 4 We smaller than the actual number of parameters. In particular, it is much smaller for higher layers such c8 to 118. This indicates that the information required for classification is almost distilled the first few layers and the contribution the subsequent layers would much smaller than the earlier layers. Moreover, smaller intrinsic dimensionalities than the weight matrix. This is because the improvement induced by decreasing mh is quadratic order but that by 5, is just a linear order. Another reason is that the effective rank of the covariance matrix is more data dependent in sense that it is strongly dependent on the distribution of the data, and thus it can capture data dependent redundancy more efficiently (see also Figures and 2 Since the intrinsic dimensionality is much smaller than the actual number of parameters, the VC-dimension bound is too pessimistic and a compression based bound like ours gives better generalization error bound.
that the intrinsic dimensionality is
see that compressing the network using the covariance matrix gives
Finally, we give a comparison of intrinsic dimensionalities calculated by Arora et al. (2018) and ours. We borrowed the values presented in the paper (Arora et al. 2018). We would like note that the comparison is not completely fair because the intrinsic dimensionality of both our analysis and that of Arora al. (2018) neglect constant functors (such as depth), and thus the final gener- alization enror is not merely determined by the raw values. However, the comparison offers better understanding of our analysis by observing difference and similarity between them. We
33

---

Published as a conference paper at ICLR 2020
Table 4: The intrinsic dimensionality in each layer for each threshold v. Here again, "In/Out" indicates the channel sizes of the input and output. "Orig" indicates the number of parameters (m x filter size) in each layer.
layer
In/Out
Orig
Cov
Weight
10-1
10-2
10-3
10-1
10-2
10-3
3/64
1,728
567
1,377
910
910
910
cl
64/64
36,864
225
6,237
29,376
1,920
1.920
1,920
64/128
73,728
405
22,572
73,728
6,336
11.264
13,376
128/128
147,456
75,240
147,456
33,280
79.360
81,920
04
128/256
294,912
1,287
198,000
294,912
52,096
154,880
180,224
c5
256/256
589,824
1,989
394,200
589,824
128,000
327,680
327,680
256/256
589,824
1,683
216,810
582,912
261,120
652,800
655,360
256/256
589,824
990
34,650
293,733
238,080
655,360
655,360
c8
256/512
1,179,648
540
10,395
91,719
154,880
647.680
720,896
c9
512/512
2,359,296
162
4,455
29,151
189,440
896,000
1,290,240
c10
512/512
2,359,296
1,620
8,487
153,600
624.640
1,786,880
c11
512/512
2,359,296
36
756
3,312
81,920
307,200
1,111,040
c12
512/512
2,359,296
54
378
2,304
81,920
215,040
650.240
c13
512/512
2,359,296
81
378
2,592
56,320
199,680
660,480
c14
512/512
2,359,296
108
882
4,536
35,840
92,160
235,520
c15
512/512
2,359,296
180
1,260
2,772
46,080
112,640
235,520
116
512/4096
2,097,152
35
100
121
73,728
175,104
271,872
117
4096/4096
16,777,216
42
100
294,912
417,792
753,664
118
4096/10
40,960
42
90
90
45,166
86,226
201,194
Table 5: Comparison of the intrinsic dimensionality of analysis and that in
Arora al.
(0018
layer
In/Out
Orig
Arora et al. (2018)
Cov
10
10
10-3
c0
3/64
1,728
1,645
135
567
1,377
c3
128/128
147,456
644,654
891
75,240
147,456
c5
256/256
589,824
3,457,882
1,989
394,200
589,824
c8
256/512
1,179,648
36,920
540
10,395
91,719
c11 512/512
2,359,296
22,735
36
756
3,312
c14
512/512
2,359,296
26,584
108
882
4,536
that our intrinsic dimensionality gives a smaller number than theirs. This is because compression through the covariance matrix gives quadratic factor improvement while compression through low rank property of the weight matrices gives linear order improvement. This indicates considering low rank properties of both of weight matrices and covariance matrices yields sharper bounds. It can be realized by our unified theoretical frame-work.
34


Reviews:
[{"review_id": "BygRLlp3cS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper obtains a compression-based generalization bound (Theorem 1) for the original network, while prior work gives bounds for the compressed network. The general bound given by Theorem 1 is further applied to networks with low-rank weight matrices (Theorem 2 and Corollary 1) or low-rank covariance matrices (Theorem 3 and 4). In some cases, the bound given by Theorem 1 for the original network could be better than the bound for the compressed network.\n\nIn terms of proof techniques, Lemma 2 is a general result to control the local Rademacher complexity using upper bounds on the covering numbers, which is interesting and could be useful in other problems.\n\nOn the other hand, there are two technical concerns.\n(1) In eq. (5), the covering number of {\\phi(f)-\\phi(g)} is bounded by the covering number of {f-g}, which is not necessarily true. For example, in the 1-dimensional case, it is possible that f-g is always 1, while \\phi(f)-\\phi(g) is not a constant. This example might appear since f and g are not freely chosen from F and G; they further need to satisfy the condition that |f-g|_{L_2} is bounded by r. If the claim in eq. (5) is indeed true, a proof is needed.\n(2) Despite the issue in (1), many bounds in the paper may actually be okay, since in the proofs the covering numbers of F (the original networks) are used (e.g., in eq. (6) and Lemma 2). Therefore it looks like the local Rademacher complexity of F can be controlled directly using Lemma 2. The question then is how compression helps in the analysis?\n\nI hope the above points can be clarified, and I would like to participate in the discussion.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Byevc7PaYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides generalization bound based on the compression arguments. A key contribution is that instead of bounding the\npopulation risk for the compressed model, this paper manages to give bounds on the non-compressed network following a unified analysis framework. Also, this paper applies the unified framework to low-rank assumption on weigh matrices and covariance matrices.\n\nOverall, I believe this paper should be accepted because of its contribution to our understanding of generalization theory. The central contribution here is using localized Rademacher complexity to bound the $L_2$ norm between original network and compressed network. However, I think there are several issues unclear and in need of clarification.\n\nOne thing I hope the authors could clarify is the novelty in the proof of Theorem 1, because it seems the techniques used here such as entropy integral and peeling are all well-known. It would be better if the authors could give a comparison between this paper and papers with similar techniques.\n\nAnother question is, in the statement of Theorem 1, the term $\\sqrt{M \\frac{2t}{n}}$ is marked as part of 'main term' and the term $C \\dot r \\sqrt{\\frac{t}{n}}$ is marked as part of 'fast term'. I hope the authors could give a more detailed explanation of why $\\dot r$ could be seen as a faster term than a constant, which seems not sensible to me. \n\nAlso, I hope the authors could explain why $\\Phi(\\sqrt{2(\\hat r ^2 + r ^2 _*)})$ is a 'faster term', because it seems this term is not faster than $\\sqrt{\\frac{1}{n}}$.\n\nThe questions above essentially concern how sharp this general bound could be. I would appreciate it if the authors could give a thorough response to questions mentioned above. This can help me achieve a better understanding and a more precise evaluation on this paper.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkg4y5FCYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents novel theoretical results on generalization bounds via compression. Similar ideas in the last few years appeared, but only bounds on a compressed network were obtained. In contrast, the current submission gives a bound on the original (uncompressed) network in terms of the complexity of the compressed network class.\n\nOverall, the paper seems to be well-written. I appreciate that the outlines of the proofs are included in the main text, which helps the reader follow the ideas. The result is novel and quite interesting. The new bounds seem to be still quite far from giving tight generalization theory, but I believe the paper provides some nice theoretical results for other researchers to improve upon. I think the paper could be improved immensely by some empirical analysis of the rank of compressed standard vision networks and rank of activation covariance matrices.  There are also some citation issues (see detailed comments below).\n\nCitation issues:\nIn the introduction, paragraph 2, the authors cite Neyshabur et al. 2019 for the observation that networks generalize well despite being overparameterized. It seems like an odd choice. Why is Barttlet’s ‘99 paper [“Size of the weights…”]  not cited? Or at least Neyshabur et al. 2015? \nThen the authors mention that classical learning theory cannot explain the phenomena mentioned above, and classical theory “.. suggests ” that overparameterized models cause overfitting…”. The authors need to be more precise and add citations (I am assuming that the authors are talking about VC bounds for worst-case ERM generalization).\nIn the third paragraph, where the authors talk about norm-based bounds being lose, it seems that Nagarajan and Kolter 2019 should be cited (not only at the end), as well as Dzigaite and Roy 2017 (they look into the looseness of path-norm and margin-based bounds).\n\nCould the authors comment more on how the bound in Theorem 2 is superior to VC dimension bound and whether conditions under which the bound is tight are realistic for standard compressed vision networks. Having weight matrices to be close to rank 1 seems unrealistic.I would like to see some sort of empirical evidence if the authors believe that this is the case. And for larger ranks, the bound seems to be close to VC bound.\n\nIn general, I found the notation a bit hard to follow and had to constantly be looking through the paper to find the definitions of various quantities. Having three different r’s, multiple mu’s with dots, bars, stars, etc., was definitely confusing and required extra attention to detail.\n\nOther minor comments:\n\nIn section 2, marginal distributions over x and y are introduced. Are those used in the main text?\nIs that a definition of \\mu with the dot on top in assumption 5, or is this mu with the dot defined earlier? Using notation := would make it clearer whether the quantity is being defined.\nIn Section 3, “The main difference from the…” paragraph, there is \\Psi(\\dot r) used. Where is that defined?", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has a few interesting contributions: (a) a bound for un-compressed networks in terms of the compressed network (this is in contrast to some prior work, which only gives bounds on the compressed network); (b) the use of local Rademacher complexity to try to squeeze as much as possible out of the connection; (c) an application of the bound to a specific interesting favorable condition, namely low-rank structure.

As a minor suggestion, I'd like to recommend that the authors go ahead and use their allowed 10th body page!
Decision: Accept (Spotlight)