COMPRESSION BASED BOUND FOR NON-COMPRESSED NETWORK: UNIFIED GENERALIZATION ERROR ANAL- YSIS OF LARGE COMPRESSIBLE DEEP NEURAL NET- WORK
Year: 2020

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 framework 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 framework, we can obtain a data dependent generalization error bound which gives a tighter evaluation than the data independent ones.

heading: 1 INTRODUCTION
text: Deep learning has shown quite successful results in wide range of machine learning applications. such as image recognition (Krizhevsky et al., 2012), natural language processing (Devlin et al., 2018) and image synthesis tasks (Radford et al., 2015). The success of deep learning methods is 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, its theoretical analysis is also getting much important. For example, it has been known that the deep neural network has universal approximation capability (Cybenko, 1989; Hornik, 1991; Sonoda & Murata, 2015) and its expressive power grows up in an exponential order against the number of layers (Montufar et al., 2014; Bianchini & Scarselli, 2014; Cohen et 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, a generalization error analysis is one of the biggest issues in the machine learning literature. An important property of deep learning is that it generalizes well even though its parameter size is quite large compared with the sample size (Neyshabur et al., 2019). This can not be well explained by a 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 et al., 2017b; Neyshabur et al., 2017; Golowich et al., 2018). These bounds are beneficial
because the bounds are not explicitly dependent on the number of parameters and thus are useful to explain the generalization error of overparameterized network (Bartlett, 1998; Neyshabur et al., 2015; 2019). However, these bounds are typically exponentially dependent on the number of layers and thus tends to be loose for deep network situations (Dziugaite & Roy, 2017; Arora et al., 2018; Nagarajan & Kolter, 2019). As a result, Arora et al. (2018) reported that a simple VC-dimension bound (Li et al., 2018; Harvey et al., 2017) can still give sharper evaluations than these norm based bounds in some practically used deep networks. Wei & Ma (2019) improved this issue by involving a data dependent Lipschitz constant as performed in Arora et al. (2018); Nagarajan & Kolter (2019).
On the other hand, compression based bound is another promising approach 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), batch-normalization (Ioffe & Szegedy, 2015), and mix-up (Zhang et al., 2018; Verma et al., 2018). Zhang et al. (2016) reported that such explicit regularization does not have much effect 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 et 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., 2019; Suzuki et 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 a bound of the size of the compressed network. Suzuki et al. (2018) has developed a 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 a noncompressed 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 generalizes 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 is overcome by developing novel data dependent capacity control technique using local Rademacher complexity bounds (Mendelson, 2002; Bartlett et al., 2005; Koltchinskii, 2006; Giné & Koltchinskii, 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 in 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 observations 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 stability 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 compression ability. Our contributions in this paper are summarized as follows:
• We give a unified framework to obtain a compression based bound for non-compressed network 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 a result, we obtain a sharp generalization
Other related work Recently, the role of over-parameterization 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 is also applied to obtain a non-vacuous compression based bound (Zhou 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 a different framework as in Littlestone & Warmuth (1986) and minimum description code length (Hinton & Van Camp, 1993). Our bound would share the same spirits with these studies but give a new analysis by incorporating recent observations in deep learning researches.

heading: 2 PRELIMINARIES: PROBLEM FORMULATION AND NOTATIONS
text: In this section, we give the problem setting and notations that will be used in the theoretical analysis. We consider the standard supervised leaning formulation where data consists of input x ∈ Rd and output (or label) y ∈ R. We consider a single output setting, i.e., the output y is a 1-dimensional real value, but it is straight forward to generalize the result to a multiple output case. Suppose that we are given n i.i.d. observations Dn = (xi, yi)ni=1 distributed from a probability distribution P . To measure the performance of a trained function f , we use a loss function ψ : R× R→ R and define
a training error and its expected one as
Ψ̂(f) := 1
n n∑ i=1 ψ(yi, f(xi)), Ψ(f) := E[ψ(Y, f(X))],
where the expectation is taken with respect to (X,Y ) ∼ P . Basically, we are interested in the generalization error Ψ(f̂)− Ψ̂(f̂) for an estimator f̂ . We denote the empirical L2-norm by ‖f‖n :=√∑n
i=1 f(zi) 2/n for an empirical observation zi = (xi, yi) (i = 1, . . . , n). The population L2norm is denoted by ‖f‖L2 := √ EZ∼P [f(Z)2].
This paper deals with deep neural networks as a model. The activation function is denoted by η which will be assumed to be 1-Lipschitz as satisfied by ReLU (Assumption 1). Let the depth of the network be L and the width of the `-th internal layer be m` (` = 1, . . . , L + 1) where we set m1 = d (dimension of input) and mL+1 = 1 (dimension of output) for convention. Then, the set of networks having depth L and width m = (m1, . . . ,mL) with norm constraint as
NN(m, R′2, R ′ F) :=
{ f(x) = G ◦ (W (L)η(·)) ◦ (W (L−1)η(·)) ◦ · · · ◦ (W (1)x) |
W (`) ∈ Rm`×m`+1 , ‖W (`)‖2 ≤ R′2, ‖W (`)‖F ≤ R′F } .
where ‖W‖2 := supu:‖Wu‖6=0 ‖Wu‖/‖u‖1 is the operator norm (the maximum singular value), ‖W‖F := √∑ i,jW 2 i,j is the Frobenius norm, and G is the “clipping” operator that is defined by G(x) = max{−M,min{x,M}} for a 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 we can avoid unrealistically loose generalization error. Note that the clipping operator does not change the classification error for binary classification. We express F to represent the “full model”: F = NN(m, R2, RF) for a given R2, RF > 0. Here, we implicitly suppose that R2 is close to 1 so that the norm of the output from internal layers is not too much amplified, while RF 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 R̂n(F ′) := E [ supf∈F ′ 1 n ∑n i=1 if(zi) | Dn ] where Dn = (zi)ni=1 = (xi, yi) n i=1, and i (i = 1, . . . .n) is an i.i.d. Rademacher sequence (P ( i = 1) = P ( i = −1) = 1/2). This is also called conditional Rademacher complexity because the expectation is taken conditioned on fixed Dn. Its expectation with respect to Dn is denoted by R̄n(F ′) := EDn [R̂n(F ′)]. Roughly speaking the Rademacher complexity measures the size of the model and it gives an 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 complexity 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 f̂ can be compressed. If the network can be compressed to much smaller one, then its intrinsic dimensionality can be regarded as small. To describe it more precisely, suppose that the trained network f̂ is included in a subset of the neural network model: f̂ ∈ F̂ ⊂ F . For example, F̂ 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 a uniform bound valid for any estimator f̂ that falls into F̂ and satisfies the following compressibility condition. We suppose that the network f̂ is easy to compress, that is, f̂ can be compressed to a smaller network ĝ which is included in a submodel: ĝ ∈ Ĝ. For example, Ĝ 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 ĝ to that of f̂ and eventually obtains a tighter evaluation.
1In this paper, ‖ · ‖ denotes the Euclidean norm: ‖u‖ = √∑
i u 2 i .
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
Ψ(ĝ) ≤ Ψ̂(f̂) + ‖f̂ − ĝ‖n + CR̄n(Ĝ), (1)
for a constant C > 0 under some assumptions (Table 1). The term ‖f̂ − ĝ‖n appears to adapt the empirical error of f̂ to that of ĝ, that is called “compression error” which can be seen as a bias term. We see that, in the right hand side, there appears the complexity of Ĝ which is assumed to be much smaller than that of the full model F . However, the left hand side is not the expected error of f̂ but that of ĝ. One way to transfer this bound to that of f̂ is that we have |Ψ(ĝ) − Ψ(f̂)| ≤ ‖ĝ − f̂‖L2 by assuming Lipschitz continuity of the loss function and then convert the bound (1) to
Ψ(f̂) ≤ Ψ̂(f̂) + (‖f̂ − ĝ‖n + ‖f̂ − ĝ‖L2) + R̄n(Ĝ).
However, to bound the term ‖f̂ − ĝ‖n + ‖f̂ − ĝ‖L2 , there typically appears the complexity of the model F̂ which is larger than the compressed model Ĝ like ‖f̂ − ĝ‖n ≤ √ ‖f̂ − ĝ‖2L2 +Op(R̄(F̂)), which results in slow convergence rate. To overcome this difficulty, we need to carefully control the difference between the training and test error of f̂ and ĝ by utilizing the local Rademacher complexity technique (Mendelson, 2002; Bartlett et al., 2005; Koltchinskii, 2006; Giné & Koltchinskii, 2006). The local Rademacher complexity of a model F ′ with radius r > 0 is defined as
Ṙr(F ′) := R̄n({f ∈ F ′ | ‖f‖L2 ≤ r}). The main difference from the standard Rademacher complexity is that the model is localized to a set of functions satisfying ‖f‖L2 ≤ r. As a result, we obtain a tighter error bound. Throughout this paper, we always assume the following assumptions. Let PX and PY denote the marginal distribution of x and that of y respectively. Assumption 1 (Lipschitz continuity of loss and activation functions). The loss function ψ is 1- Lipschitz continuous with respect to the function output:
|ψ(y, u)− ψ(y, u′)| ≤ |u− u′| (∀y ∈ supp(PY), u, u′ ∈ R).
The activation function η is also 1-Lipschitz continuous: ‖η(u) − η(u′)‖ ≤ ‖u − u′‖ (∀u ∈ Rd′) where d′ is any positive integer. Assumption 2. The norm of input is bounded by Bx > 0: ‖x‖ ≤ Bx (∀x ∈ supp(PX )). Assumption 3. The L∞-norms of all elements in F̂ and Ĝ are bounded by M ≥ 1: ‖f‖∞, ‖g‖∞ ≤ M for all f ∈ F̂ and g ∈ 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,m`, R2, RF,M,Bx are 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`) L `=1 in a sub-linear order by using the compression based approach.
Existing bounds for no-compressed network Here we give a brief review of the generalization error bound for non-compressed models. (i) VC-bound: The Rademacher complexity of the full model F can be bounded by a naive VC-dimension bound (Harvey et al., 2017) which is
R̄n(F) = O (√ L ∑n `=1m`m`+1
n log(n)
) . In this bound, there appears the number of parame-
ters ∑n `=1m`m`+1 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 generalization ability of overparameterized networks. (ii) Norm-based bound: Golowich et al. (2018) showed
the norm based bound which is given as R̄n(F) = O (√ LRLF n ) . However, this is exponentially
dependent on the depth as RLF resulting in quite loose bound. Neyshabur et al. (2017) showed a norm based bound of R̄n(F) = O (√ L3(max`m`)R2F/R 2 2
n
) which avoids the exponential de-
pendency. However, there is still dependency on the width, ∑ `m`R 2 F, which is larger than the
linear order of the width since RF could be moderately large. Bartlett et al. (2017b) showed
R̄n(F) = O ( RL2√ n ( L R 2/3 2→1
R 2/3 2
)3/2) . The norm constraint on R2→1 implicitly assumes sparsity on
the weight matrix and R2→1 typically depends on the width linearly. Wei & Ma (2019) improved the exponential dependency RL2 appearing in this bound (Bartlett et al., 2017b) to obtained a bound
O ( 1√ n ( 1 + Lκ 4 3R 2/3 2→1 + Lκ 2 3R 2/3 1→1 )3/2) where κ is the Lipschitz continuity between layers.
We can see that R22→1 and R 2 1→1 can depend on the width linearly and quadratically respectively even though R2 is bounded.

heading: 3 COMPRESSION BOUND FOR NONCOMPRESSED NETWORK
text: 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 Ĝ are fixed independently on each data observation2. For sets of functions, F ′ and G′, we denote the Minkowski difference of them by F ′ − G′ := {f − g | f ∈ F ′, g ∈ G′}. We assume that the local Rademacher complexity of F̂ − Ĝ has a concave shape with respect to r > 0: Suppose that there exists a function φ : [0,∞)→ [0,∞) such that Ṙr(F̂ − Ĝ) ≤ φ(r) and φ(2r) ≤ 2φ(r) (∀r > 0). 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 > 0 ∣∣∣∣∣ 8φ(r)r2 +M √ 4t r2n +M2 2t r2n ≤ 1 2 } . (2)
This is roughly given by the fixed point of a function r2 7→ φ(r), and it is useful to bound the ratio of the empirical L2-norm and the population L2-norm of an element h in F̂ −Ĝ: ‖h‖2L2/(‖h‖ 2 n+r 2 ∗) ≤ 1/2 with high probability. Finally, we denote ψ(F ′) := {ψ(·, f(·)) | f ∈ F ′} for a set F ′ of functions. Then, we obtain the following theorem that gives the compression based bound for noncompressed networks.
Theorem 1. Suppose that the empirical L2-distance between f̂ and ĝ is bounded by ‖f̂ − ĝ‖n ≤ r̂2 for a fixed r̂ > 0 almost surely. Let ṙ := √ 2(r̂2 + r2∗), then, under Assumptions 1, 2, 3, there exists a universal constant C > 0 such that
Ψ(f̂) ≤ Ψ̂(f̂) + 2R̄n(Ĝ) + √ M 2t
n︸ ︷︷ ︸ main term +C
[ Ṙṙ(ψ(F̂)− ψ(Ĝ)) + ṙ √ t
n +
1 + tM
n ] ︸ ︷︷ ︸
bias term
.
with probability at least 1− 3e−t for all t ≥ 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 Ĝ which could be much smaller than F̂ . The bias term represents a sample complexity to bridge the original model and the compressed model. Typically we have r2∗ = o(1/ √ n), and if we set r̂ = op(1), then the bias term can be faster than the main term which is O(1/ √ n). The term Ṙṙ(ψ(F̂)− ψ(Ĝ)) can be refined a little bit and the refined term can be evaluated by using the covering number of the model. The refined version is given in Appendix A (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. (2019); Suzuki et al. (2018) where the complexity of Ĝ and the bias r̂ are analyzed for their generalization error bounds.
The main difference from the compression bound (1) for ĝ is that the bias term r̂ = ‖f̂ − ĝ‖n is replaced by 1√
n ‖f̂− ĝ‖n which is √ n times smaller. Since r2∗ is typically o(1/ √ n) and Ṙṙ(ψ(F̂)−
2 We can extend the result to data dependent models F̂ and Ĝ by taking uniform bound for all possible choice of the pair F̂ and Ĝ. However, we omit explicit presentation of this uniform bound for simplicity.
ψ(Ĝ)) can be made in the same order as the main term or even faster by setting r̂ appropriately, we may neglect these terms. Then, the bound is informally written as
Ψ(f̂) ≤ Ψ̂(f̂) +Op ( R̄n(Ĝ) + 1√n‖f̂ − ĝ‖n + √ 1/n ) .
This allows us to obtain tighter bound than the compression bound for ĝ because the bias term r̂/ √ n
is much smaller than r̂ and eventually we can let the variance term R̄n(Ĝ) much smaller by taking small compressed model Ĝ when we balance the bias and variance trade-off. This is an advantageous point of directly bounding the generalization error of f̂ 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 a 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 0 so that the bias is balanced with the variance term, which is a more difficult problem setting. Example 1. In practice, a 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 on a pruning procedure. In this situation, we may suppose that Ĝ is the set of networks with S non-zero parameters where S is much smaller than the total number of parameters: Ĝ = {f ∈ NN(m, R2, RF) | ∑L `=1 ‖W (`)‖0 ≤ S} where ‖W (`)‖0 is the number of nonzero parameters of the weight matrix W (`). In this situation, its Rademacher complexity is bounded by R̄(Ĝ) ≤ CM √ LSn log(n) (see Appendix B.2
for the proof). This is much smaller than the VC-dimension bound √ L ∑n `=1m`m`+1
n log(n) if S ∑n `=1m`m`+1.
Although our bound can be adopted to several compression based bounds, we are going to demonstrate how small the obtained bound can be through some typical situations in the following.

heading: 3.1 COMPRESSION BOUND WITH NEAR LOW RANK WEIGHT MATRIX
text: Here, we analyze the situation where the trained network has near low rank weight matrices (W (`))L`=1. It has been reported that the trained network tends to have near low rank weight matrices experimentally (Gunasekar et al., 2018; Ji & Telgarsky, 2019) (see Appendix D for the empirical verification). This situation has been analyzed in Arora et al. (2018) where the low rank property is characterized by their original quantities such as layer cushion. However, we employ a much simpler and intuitive condition to highlight how the low rank property affects the generalization.
Assumption 4. Assume that each of weight matrices W (`) (` = 1, . . . , L) of any f ∈ F̂ is near low rank, that is, there exists α > 1/2 and V0 > 0 such that
σj(W (`)) ≤ V0j−α,
where σj(W ) is the j-th largest singular value of a matrix W (σ1(W ) ≥ σ2(W ) ≥ · · · ≥ 0).
In this situation, we can see that for any 1 ≤ s ≤ min{m`,m`+1}, we can approximate W (`) by a rank s matrix W ′ as ‖W (`) − W ′‖2 ≤ V0s−α. Let the set of networks with exactly low rank weight matrices be NN(m, s, R2, RF) := {f ∈ NN(m, R2, RF) | the weight matrix W (`) of f has rank s`} for s = (s1, . . . , sL). If we set Ĝ = NN(m, s, R2, RF), then we have the following theorem.
Theorem 2. The compressed model Ĝ = NN(m, s, R2, RF) has the following complexity:
R̄n(Ĝ) ≤CM √ L ∑L `=1 s`(m` +m`+1)
n log(n).
If F̂ satisfies Assumption 4, we can set r̂ = V0RL−12 Bx ∑L `=1 s −α ` : for any f̂ ∈ F̂ , there ex-
ists ĝ ∈ Ĝ such that ‖f̂ − ĝ‖n ≤ r̂. Then, letting A1 = L ∑L `=1 s`(m`+m`+1)
n log(n) and
A2 = L ( ∑L `=1m`)(2LV0R L−1 2 Bx) 1/α
n , the overall generalization error is bounded by Ψ(f̂) ≤ Ψ̂(f̂) + C [ MA1 +M 2α−1 2α+1A 2α 1+2α 2 + √ r̂2(1−2α)A2 + (r̂ +M) √ A1 + 1 + tM
n
] ,
with probability 1− 3e−t for any t > 1 where C > 0 is a constant depending on α.
See Appendix B.3 for the proof. This indicates that, if α > 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 s` can be arbitrary chosen and r̂ and A1 are in a 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 4, using the same notation as Theorem 2, it holds that
Ψ(f̂) ≤ Ψ̂(f̂) + C [ M1−1/2α √ L ( ∑L `=1m`)(2LV0R L−1 2 Bx) 1/α
n log(n) +M 2α−1 2α+1A 2α 2α+1 2 + 1 + tM
n ] with probability 1− 3e−t for any t > 1 where C is a constant depending on α.
An important point here is that the bound is O( √ L ∑L `=1m` n ) which has linear dependency on the width m` in the square root, but the naive VC-dimension bound has quadratic dependency
O( √ L ∑L `=1m`m`
n ). 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 a compressible model achieves much better generalization than the naive VC-bound.
In the generalization error bound, there appears RL2 . Even though R2 can be much smaller than RF, the exponential dependency RL2 can give loose bound as pointed out in Arora et al. (2018). This is 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 1 in Appendix B.4 by using data dependent Lipschitz constants such as interlayer cushion and interlayer smoothness introduced by Arora et al. (2018). The refined bound does not involve the exponential term RL2 , but instead κ 2 (κ: Lipschitz continuity) appears.

heading: 3.2 COMPRESSION BOUND WITH NEAR LOW RANK COVARIANCE MATRIX
text: Strictly speaking, the near low rank condition on 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 ĝ using the low rank property of the covariance has been studied by Suzuki et al. (2018), but their analysis requires a bit strong condition on the weight matrix. In this paper, we employ a weaker assumption.
Let Σ̂(`) = 1n ∑n i=1 φ`(xi)φ`(xi)
> be the covariance matrix of the nodes in the `-th layer where φ`(x) = η ◦ (W (`−1)η(·)) ◦ · · · ◦ (W (1)x). Assumption 5. Suppose that the trained network f̂ satisfies the following conditions:
σj(Σ̂(`)) ≤ µ̇ (`) j =: U0j −β , (3)
for a fixed β > 1 and U0 > 0.
If f̂ satisfies this assumption, then we can show that f̂ can be compressed to a smaller one f ] that has width (m]`) L `=2 with compression error roughly evaluated as ‖f̂ − f ]‖n . ∑ `(m ] `) −β/2. More precisely, for given r̃` > 0 (` = 1, . . . , L) which corresponds to the compression error in the `- th layer, let ṁ` := max{1 ≤ j ≤ m` | µ̇(`)j ≥ r̃2`/4}. Then, we define N`(r̃) = β+1 β−1ṁ` +
8 ( ∑`−1 k=1 R (`−1−k) 2 RFr̃k) 2
r̃2` , for r̃ = (r̃1, . . . , r̃L). Correspondingly we set
m]` := 5N`(r̃) log(80N`(r̃)).
Then, we obtain the following theorem.
Theorem 3. Let r̂ := ∑L k=1R (L−k) 2 RFr̃k. Then, under Assumption 5, there exists ĝ with width m] = (m1,m ] 2, . . . ,m ] L) that satisfies ĝ ∈ NN(m], √ 20 3 max`m`R2 √ 20 3 max`m`RF) and
‖f̂ − ĝ‖n ≤ r̂. In particular, we may set Ĝ = NN(m], √
20 3 max`m`R2, √ 20 3 max`m`RF), and then it holds that
R̄n(Ĝ) ≤ C √ L ∑L `=1 m]`+1m ] ` n log(n) for a constant C > 0.
See Appendix B.5 for the proof. Here, we again observe that there appears a trade-off between r̂ and m]` because as r̃` becomes small, then ṁ` becomes large and thus m ] ` becomes large. The evaluation given in Theorem 3 can be substituted to the general bound (Theorem 1). If F̂ is the full model F , then there appears the number ∑L `=1m`m`+1 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 5 are satisfied. Theorem 4. Under Assumptions 4 and 5, it holds that
Ψ(f̂) ≤ Ψ̂(f̂) + C [ M √√√√√ [PL ∨QL]L1+ β4α(2α−1)+β n ( L∑ `=1 m` ) 4/β 4/β+2(1−1/2α) log(n)3
+M 2α−1 2α+1 ( LPL ∑L `=1m` n log(n) ) 2α 2α+1 +M R2FL 2
R22
√ log(n)3
n + 1+Mt n
] ,
for PL = (2LV0RL−12 Bx) 1/α and QL =
[ 4U0R 2 F(1∨R2) L exp( 14 (2 √ L−1))
(0.25)4(1∧R2)2L
]2/β with probability 1 −
3e−t (t > 1), where C is a constant depending on α, β.
If we omit L and log(n) terms for simplicity of presentation, then the bound can be written as
Õ
 √ ( ∑L `=1m`) 4/β 4/β+2(1−1/2α)
n + (∑L `=1m` n ) 2α 2α+1  , where the Õ(·) symbol hides the poly-log order. This is tighter than that of Corollary 1. We can see that as β and α get large, the bound becomes tighter. Actually, by taking the limit of α, β →∞, then the bound goes to L2 √ log(n) n + L ∑L `=1m` n . Moreover, the term dependent on the width is O(1/n)
with respect to the sample size n which is faster than the rateO( √∑L
`=1m` n ) which was presented in
Corollary 1. 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 RL2 , we can give a refined version that does not contain the exponential term by assuming interlayer cushion (Arora et al., 2018). See Appendix B.6 for the refined version. There appears exp( 14 (2 √ L − 1)) which is exponentially dependent on L. However, this term is moderately small for realistic settings of the depth L. Actually, it is 7.27 for L = 20 and 26.7 for L = 50 (we can replace this term in exchange for larger polynomial dependency onL). The bound is not optimized with respect to the dependency on the depth L. In particular, the term L2 √ log(n)/n could be an artifact of the proof technique and the L2 term would be improved.
Finally, we compare our bound with the following norm based bounds; O ( RL2√ n ( L R 2/3 2→1
R 2/3 2 )3/2) by Bartlett et al. (2017b) and O ( 1√ n ( 1 + Lκ 4 3R 2/3 2→1 + κ 2 3LR 2/3 1→1 )3/2) by Wei & Ma (2019).
Since our bound and their bounds are derived from different conditions, we cannot tell which is better. Here, we consider a special case where m` = m (∀`) and W (`) = 1m11
> ∈ Rm×m which is an extreme case of low rank settings (note that W (`) has rank 1). Then, R2 = 1, RF = 1,
R2→1 = √ m and R1→1 = m, and thus their bounds are O( √ m/n) and O( √ (m+m2)/n)
respectively. However, β and α in our bound √ m 4/β 4/β+2(1−1/2α) /n = √ m 1 1+β(1−1/2α)/2 /n can be
arbitrary large in this situation, so that our bound has much milder dependency on the width m. On the other hand, if the weight matrix has small norm and has no spectral decay (corresponding to small α and β), then our bound can be looser than theirs. Combining compression based bounds and norm based bounds would be interesting future work.

heading: 4 CONCLUSION
text: In this paper, we derived a compression based error bound for non-compressed network. The bound is general and it can be adopted to several compression based bound derived so far. The main difficulty lies in evaluating the population L2-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.
Acknowledgment We thank the anonymous reviewers for their valuable comments. TS was partially supported by MEXT Kakenhi (15H05707, 18K19793 and 18H03201), Japan Digital Design, and JST-CREST, Japan .

heading: 5 PROOF OUTLINE OF THEOREM 1
text: Remember that for a trained network f̂ , ĝ is its compressed version that is included in a submodel Ĝ. First, we decompose the generalization gap as
Ψ(f̂)− Ψ̂(f̂) = [(Ψ(f̂)−Ψ(ĝ))− (Ψ̂(f̂)− Ψ̂(ĝ))] + (Ψ(ĝ)− Ψ̂(ĝ)). (4) The second block in the right hand side is easy to bound, i.e., by applying the standard Rademacher complexity bound (Theorem 3.1 of Mohri et al. (2012)) with the contraction inequality (Theorem 11.6 of Boucheron et al. (2013) or Theorem 4.12 of Ledoux & Talagrand (1991)), it holds that
Ψ(ĝ)− Ψ̂(ĝ) ≤ 2R̄n(Ĝ) + √ M 2tn ,
with probability 1 − e−t. Since Ĝ is a small model, this bound could be much smaller than a naive VC-dimension bound. The first block “bridges” the generalization gap of ĝ to that of f̂ , but bounding the first block is more involved. We make use of the local Rademacher complexity to bound the term. Suppose that the event in which ‖f̂ − ĝ‖L2 ≤ ṙ holds has high probability (which should be proven later), then it is also expected that ψ(y, f)− ψ(y, g) has small L2-norm. This is true because of the Lipschitz continuity assumption (Assumption 1). Actually, the Talagrand’s concentration inequality yields that
Ψ(f̂)−Ψ(ĝ)− (Ψ̂(f̂)− Ψ̂(ĝ)) ≤ C [ Φ(ṙ) + √ ṙ tn + 1+tM n ] ,
for Φ(r) := R̄n({ψ(f) − ψ(g) | f ∈ F̂ , ĝ ∈ Ĝ, ‖f − g‖L2 ≤ ṙ}) with probability 1 − e−t. Since Φ(ṙ) requires the restriction ‖f − g‖L2 ≤ ṙ, this quantity is much smaller than the standard Rademacher complexity R̄n(ψ(F̂)− ψ(Ĝ)), which yields fast convergence rate.
Finally, we should bound the probability of ‖f̂ − ĝ‖L2 ≤ ṙ. This can be bounded by utilizing the ratio type empirical process. Actually, we can show that
P ( sup
h∈F̂−Ĝ
(P − Pn)(h2) Ph2 + r2∗ ≥ 1 2
) ≤ e−t,
for r∗ defined in Eq. (2), where Pnf := 1n ∑n i=1 f(zi) and Pf = E[f(Z)]. This yields that ‖f̂ − ĝ‖2L2−‖f̂ − ĝ‖ 2 n ≤ 12 (‖f̂ − ĝ‖ 2 L2
+r2∗) with probability 1−e−t and equivalently ‖f̂ − ĝ‖2L2 ≤ 2(‖f̂ − ĝ‖2n + r2∗). Since ‖f̂ − ĝ‖2n ≤ r̂2 a.s., we have ‖f̂ − ĝ‖2L2 ≤ 2(r̂ 2 + r2∗) = ṙ 2.
We can show that Φ(ṙ) ≤ Ṙṙ(ψ(F̂) − ψ(Ĝ)) by using the Lipschitz continuity assumption (Assumption 1). Then, we obtain the assertion.

heading: NOTATION LISTS
text: Since we use plenty of notations, we give the notation list in Table 2.

heading: APPENDIX
text: In the appendix, we give the proofs of the main text. We use the following notation throughout the appendix:
Pnf := 1
n n∑ i=1 f(zi), Pf = E[f(Z)].
To evaluate it, the covering number is useful (van der Vaart & Wellner, 1996).
Definition 1 (Covering number). For a metric space F̃ equipped with a metric d̃, the -covering numberN (F̃ , 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 ∧ b := min{a, b} and a ∨ b := max{a, b} for a, b ∈ R.

heading: A PROOF OF THEOREM 1
text: Denote the local Rademacher complexity of {ψ(f)− ψ(g) | f ∈ F̂ , ĝ ∈ Ĝ, ‖f − g‖L2 ≤ r} by
Φ(r) := R̄n({ψ(f)− ψ(g) | f ∈ F̂ , ĝ ∈ Ĝ, ‖f − g‖L2 ≤ r}).
Here, we restate Theorem 1 in the following in more complete form. Remember that f̂ ∈ F̂ and ĝ ∈ Ĝ are the trained original network and the compressed network respectively.
Theorem 5. Suppose that the empirical L2-distance between f̂ and ĝ is bounded by ‖f̂ − ĝ‖n ≤ r̂2 for a fixed r̂ > 0 almost surely. Let ṙ := √ 2(r̂2 + r2∗), then, under Assumptions 1, 2, 3, there exists a universal constant C > 0 such that
Ψ(f̂) ≤ Ψ̂(f̂) + 2R̄n(Ĝ) + √ 2Mt
n + C
[ Φ(ṙ) + ṙ √ t
n +
1 + tM
n
] .
with probability at least 1− 3e−t for all t ≥ 1.
Note that Ṙ(ψ(F̂) − ψ(Ĝ)) in the statement of Theorem 1 of the main body is replaced by refined quantity Φ(ṙ) (we can show Φ(ṙ) ≤ Ṙ(ψ(F̂)− ψ(Ĝ)) from the Lipschitz continuity of ψ).
Proof of Theorems 1 and 5. First, by the standard Rademacher complexity analysis, we have that
Ψ(ĝ)− Ψ̂(ĝ) = 1 n n∑ i=1 (ψ(zi, ĝ(xi))− E[ψ(Z, ĝ(X))])
≤ sup g∈Ĝ
1
n n∑ i=1 (ψ(zi, g(xi))− E[ψ(Z, g(X))])
≤ 2EDn, [ sup g∈Ĝ 1 n n∑ i=1 iψ(zi, g(xi)) ] + √ M 2t n ≤ 2R̄n(Ĝ) + √ M 2t n (5)
with probability 1 − e−t, 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) or Theorem 4.12 of Ledoux & Talagrand (1991) and its proof) in the last line. We let this event be E0(t). Next, we observe that
Ψ(f̂)− Ψ̂(f̂) = Ψ(f̂)−Ψ(ĝ) + Ψ(ĝ)− Ψ̂(ĝ) + Ψ̂(ĝ)− Ψ̂(f̂)
= (Ψ(f̂)−Ψ(ĝ)− (Ψ̂(f̂)− Ψ̂(ĝ))) + Ψ(ĝ)− Ψ̂(ĝ) ≤ [Ψ(f̂)−Ψ(ĝ)− (Ψ̂(f̂)− Ψ̂(ĝ))] + 2R̄n(Ĝ) + √ M 2t
n (6)
where we used Eq. (5) in the last line. Here, it should be noticed that it is not a good strategy to bound the first term Ψ(f̂) − Ψ(ĝ) − (Ψ̂(f̂) − Ψ̂(ĝ)) by bounding Ψ(f̂) − Ψ̂(f̂) and Ψ(ĝ) − Ψ̂(ĝ) 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 ĝ are date dependent and we can only bound the empirical L2-distance between them. On the other hand, the local Rademacher complexity is characterized by the population L2norm. To bridge this gap, we need to bound the populationL2-distance ‖f̂−ĝ‖L2 between f̂ and ĝ in terms of the empirical L2-norm bound ‖f̂− ĝ‖n ≤ r̂. To do so, we also bound the local Rademacher complexity of F̂ − Ĝ: Ṙr(F̂ − Ĝ). Suppose that there exists a function φ : [0,∞) → [0,∞) such that the the following conditions are satisfied:
Ṙr(F̂ − Ĝ) ≤ φ(r) and φ(2r) ≤ 2φ(r). Note that Eq. (11) gives one example of φ(r). Then, by the so-called peeling device, we can show that for any r > 0,
P ( sup
h∈F̂−Ĝ
(P − Pn)(h2) Ph2 + r2 ≥ 8φ(r) r2 +M
√ 4t
r2n +M2
2t
r2n
) ≤ e−t
for all t > 0 (Theorem 7.7 and Eq. (7.17) of Steinwart & Christmann (2008)). Hence, if we choose r∗ = r∗(t) so that
8 φ(r∗)
r2∗ +M
√ 4t
r2∗n +M2
2t r2∗n ≤ 1 2 ,
then it holds that P (h2) ≤ 2Pn(h2) + 2r2∗ uniformly over all h ∈ F̂ − Ĝ with probability greater than 1 − e−t. We let this event as E1(t). In this event, if ‖f̂ − ĝ‖2n ≤ r̂2, then it holds that
‖f̂ − ĝ‖2L2 ≤ 2(r̂ 2 + r2∗) = ṙ 2.
Next, we bound Ψ(f̂)−Ψ(ĝ)− (Ψ̂(f̂)− Ψ̂(ĝ)). To bound this term, we apply the Talagrand’s concentration inequality (Proposition 2 and Talagrand (1996); Bousquet (2002)). To apply it, we should bound the variance and L∞-norm of ψ(y, f(x))−ψ(y, g(x))− (E[ψ(Y, f(X))]−E[ψ(Y, g(X))]) for any f ∈ F̂ , g ∈ Ĝ with ‖f − g‖L2 ≤ r (where r will be set 2(r̂2 + r2∗)). Due to the Lipschitz continuity of ψ, we have that
Var[ψ(Y, f(X))− ψ(Y, g(X))] ≤ Var[f(X)− g(X)] ≤ ‖f − g‖2L2 ≤ r 2.
Similarly, it holds that
|ψ(y, f(x))− ψ(y, g(x))− (E[ψ(Y, f(X))]− E[ψ(Y, g(X))])| ≤ |ψ(y, f(x))− E[ψ(Y, f(X))]|+ |ψ(y, g(x))− E[ψ(Y, g(X))])| ≤ 2M.
Hence, by the Talagrand’s concentration inequalit (Proposition 2 and Talagrand (1996); Bousquet (2002)), it holds that
sup f,g:‖f−g‖L2≤r
(P − Pn)(ψ(Y, f(X))− ψ(Y, g(X)))
≤ 2E [ sup
f,g:‖f−g‖L2≤r (P − Pn)(ψ(Y, f(X))− ψ(Y, g(X)))
] + r √ 2t
n +
4tM
n ,
with probability at least 1− e−t for any t > 0. The first term in the right hand side can be bounded as
E [ sup
f,g:‖f−g‖L2≤r (P − Pn)(ψ(Y, f(X))− ψ(Y, g(X)))
]
≤ 2EDn,
[ sup
f,g:‖f−g‖L2≤r
1
n n∑ i=1 i[ψ(yi, f(xi))− ψ(yi, g(xi))] ] = 2Φ(n),
where we used the standard symmetrization argument (see Lemma 11.4 of Boucheron et al. (2013) for example).
Combining these inequalities, it holds that
sup f,g:‖f−g‖L2≤r
(P − Pn)(ψ(Y, f(X))− ψ(Y, g(X))) ≤ C [ Φ(r) + r √ t
n +
1 +Mt
n
] .
for a universal constant C > 0 with probability at least 1 − e−t for all t > 0. We denote by this event as E2(t, r). We define an event E3(t) = E1(t) ∩ E2(t, ṙ). Then P (E3(t)) ≥ 1− 2e−t for all t > 0. In this event, ‖f̂ − ĝ‖2L2 ≤ ṙ 2 and thus it holds that
Ψ(f̂)−Ψ(ĝ)− (Ψ̂(f̂)− Ψ̂(ĝ)) ≤ C [ Φ(ṙ) + ṙ √ t
n +
1 + tM
n
] ,
for a universal constant C > 0. Combining this and Eq. (6), we obtain the assertion on the event E0(t) ∩ E3(t). This gives the proof of Theorem 5. To show Theorem 1, note that ‖ψ(f) − ψ(g)‖L2 ≤ ‖f − g‖L2 by the Lipschitz continuity of ψ and this yields {ψ(f) − ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r} ⊂ {ψ(f) − ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖ψ(f)− ψ(g)‖L2 ≤ r}. Therefore, we have
Φ(ṙ) ≤ Ṙṙ(ψ(F̂)− ψ(Ĝ)).
Hereafter, we derive some upper bounds of the (local) Rademacher complexities under some covering number conditions.
Lemma 1. For a given r > 0, let γ̂n = γ̂n(Dn) := sup{‖f −g‖n | ‖f −g‖L2 ≤ r, f ∈ F̂ , g ∈ Ĝ}. Then, it holds that
max{Φ(r), Ṙr(F̂ − Ĝ)}
≤ C  1n + EDn ∫ γ̂n
1/n
√ log(N (F̂ , ‖ · ‖n, /2))
n d + ∫ γ̂n 1/n
√ log(N (Ĝ, ‖ · ‖n, /2))
n d  , (7)
and
Φ(r) ≤ C ′Ṙr(ψ(F̂)− ψ(Ĝ)) √ log(n) log(2nM), (8)
where C,C ′ are universal constants.
Proof. The conditional Rademacher complexity of the set {ψ(y, f(x)) − ψ(y, g(x)) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r} can be bounded by a constant times the following Dudley integral (see Theorem 5.22 of Wainwright (2019) or Lemma A.5 of Bartlett et al. (2017a) for example):
inf α>0 α+ ∫ γ̂n α √ log(N ({ψ(f)− ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r}, ‖ · ‖n, )) n d  ≤ 1 n + ∫ γ̂n 1/n √ log(N ({ψ(f)− ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r}, ‖ · ‖n, )) n d (9)
≤ 1 n + ∫ γ̂n 1/n
√ log(N (ψ(F̂), ‖ · ‖n, /2)) + log(N (ψ(Ĝ), ‖ · ‖n, /2))
n d
≤ 1 n + ∫ γ̂n 1/n
√ log(N (F̂ , ‖ · ‖n, /2)) + log(N (Ĝ, ‖ · ‖n, /2))
n d
≤ 1 n + ∫ γ̂n 1/n
√ log(N (F̂ , ‖ · ‖n, /2))
n d + ∫ γ̂n 1/n
√ log(N (Ĝ, ‖ · ‖n, /2))
n d , (10)
where we used ‖ψ(f)−ψ(g)− (ψ(f ′)−ψ(g′))‖n ≤ ‖ψ(f)−ψ(f ′)‖n+‖ψ(g)−ψ(g′)‖n ≤ for f, f ′ ∈ F̂ and g, g′ ∈ Ĝ with ‖f−f ′‖n ≤ /2 and ‖g−g′‖n ≤ /2 in the third line, and 1-Lipschitz continuity of the loss function ψ in the fourth line (i.e., |ψ(y, f(x))− ψ(y, g(x))| ≤ |f(x)− g(x)| which yields ‖ψ(f)− ψ(g)‖n ≤ ‖f − g‖n),
In the same way, we can see that Ṙr(F̂ − Ĝ) is bounded by the Dudley integral as
Ṙr(F̂ − Ĝ)
≤ C n + CEDn ∫ γ̂n 1/n √ log(N ({f̂ − ĝ | f̂ ∈ F̂ , ĝ ∈ Ĝ, ‖f̂ − ĝ‖L2 ≤ r}, ‖ · ‖n, )) n d  ≤ C n + CEDn ∫ γ̂n 1/n √ log(N (F̂ , ‖ · ‖n, /2)) n d + ∫ γ̂n 1/n √ log(N (Ĝ, ‖ · ‖n, /2)) n d
 , (11) where we used the same argument as Eq. (10) and C > 0 is a universal constant. Then, we conclude Eq. (7).
Next, we show Eq. (8). The term Eq. (9) can be evaluated by using the local Rademacher complexity of ψ(F̂) − ψ(Ĝ). Note that ‖ψ(f) − ψ(g)‖L2 ≤ ‖f − g‖L2 by the Lipschitz continuity of ψ and this yields {ψ(f) − ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r} ⊂ {ψ(f) − ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖ψ(f)−ψ(g)‖L2 ≤ r}. Then, the Sudakov’s minoration (Corollary 4.14 of Ledoux & Talagrand (1991)) gives an upper bound of the right hand side of Eq. (9):∫ γ̂n
1/n
√ log(N ({ψ(f)− ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖f − g‖L2 ≤ r}, ‖ · ‖n, ))
n d
≤ ∫ γ̂n 1/n √ log(N ({ψ(f)− ψ(g) | f ∈ F̂ , g ∈ Ĝ, ‖ψ(f)− ψ(g)‖L2 ≤ r}, ‖ · ‖n, )) n d
≤ ∫ γ̂n 1/n R̂n,r(ψ(F̂)− ψ(Ĝ)) √ log(n) 1 d ≤ R̂n,r(ψ(F̂)− ψ(Ĝ)) √ log(n) log(nγ̂n),
where R̂n,r(ψ(F̂)−ψ(Ĝ)) := E [ sup{ 1n ∑n i=1 i(ψ(yi, f(xi))− ψ(yi, g(xi))) | f ∈ F̂ , g ∈ Ĝ, ‖ψ(f)− ψ(g)‖L2 ≤ r} ] . Since γ̂n ≤ 2M , the expectation of the right hand side with respect to Dn is Ṙr(ψ(F̂) − ψ(Ĝ)) √ log(n) log(2nM). This gives an upper bound of the right hand side of Eq. (9) and yields Eq. (8). Lemma 2. E [ sup{Pnh2 | h ∈ F̂ − Ĝ : ‖h‖L2 ≤ r} ] ≤ r2 + 2Mφ(r).
Proof. By the contraction inequality of the Rademacher complexity (Theorem 4.12 of Ledoux & Talagrand (1991) and its proof), we have
E [ sup{Pnh2 | h ∈ F̂ − Ĝ : ‖h‖L2 ≤ r} ] ≤ E [ sup{(Pn − P )h2 | h ∈ F̂ − Ĝ : ‖h‖L2 ≤ r} ] + r2
≤ 2E [ sup{ 1
n n∑ i=1 ih(xi) 2 | h ∈ F̂ − Ĝ : ‖h‖L2 ≤ r}
] + r2
(symmetrization; Lemma 11.4 of Boucheron et al. (2013))
≤ 2ME [ sup{ 1
n n∑ i=1 ih(xi) | h ∈ F̂ − Ĝ : ‖h‖L2 ≤ r}
] + r2 (∵ contraction inequality)
= 2MṘr(F̂ − Ĝ) + r2 ≤ 2Mφ(r) + r2.
Lemma 3. Suppose that
sup Dn log(N (F̂ , ‖ · ‖n, /2)) + sup Dn log(N (Ĝ, ‖ · ‖n, /2)) ≤ S1 + S2 log(1/ ) + S3 −2q
for q < 1. Then, for a universal constant C > 0 and a constant Cq > 0 which depends on q < 1, it holds that
Φ(r) ≤ C max
{ 1
n +M
S1 + S2 log(n)
n + r
√ S1 + S2 log(n)
n ,
Cq
[ 1
n +
( M1−qS3
n
) 1 1+q + r1−q √ S3 n ]} .
In particular,
r2∗ ≤ C
[ M S1 + S2 log(n)
n +
( M1−qS3
n
) 1 1+q
+ 1 +Mt
n
] .
Proof. Remember that γ̂n := sup{‖f − g‖n : ‖f − g‖L2 ≤ r, f ∈ F̂ , g ∈ Ĝ} for a given r > 0. Under the assumption, we may take φ(r) (defined below) as an upper bound of Φ(r) by Lemma 1:
φ(r) = C
( 1
n + 1√ n E [∫ γ̂n 1/n √ S1 + S2 log( −1) + S3 −2qd ]) ,
where C > 0 is a universal constant. The right hand side can be evaluated as
E [∫ γ̂n 1/n √ S1 + S2 log(1/ ) + S3 −2qd ] ≤ E [ γ̂n √ S1 + S2 log(n) ] + 1 1− q √ S3E[γ̂ 1−q n ]
≤ √ E[{Pnh2 | h ∈ F̂ − Ĝ, ‖h‖L2 ≤ r}] √ S1 + S2 log(n)
+
√ S3 1− q E[{Pnh2 | h ∈ F̂ − Ĝ, ‖h‖L2 ≤ r}] 1−q 2
≤ √ r2 + 2Mφ(r) √ S1 + S2 log(n) + √ S3
1− q (r2 + 2Mφ(r))
1−q 2 , (12)
where we used Lemma 2. Hence, if the first term is larger than the second term, we have that
φ(r) ≤ C
( 1
n +
√ S1 + S2 log(n)
n
√ r2 + 2Mφ(r)
)
≤ C n + C2M S1 + S2 log(n) n + Cr
√ S1 + S2 log(n)
n + φ(r) 2 .
Therefore, we obtain that
φ(r) ≤ 2C n + 2C2M S1 + S2 log(n) n + 2Cr
√ S1 + S2 log(n)
n . (13)
On the other hand, if the second term in Eq. (12) is larger than the first one, then Young’s inequality gives that
φ(r) ≤ C
( 1
n +
√ S3
n(1− q)2 (r2 + 2Mφ(r))
1−q 2
)
≤ C n + C q(c′1−qC2S3 n(1− q)2 ) 1 1+q + (1− q)2Mφ(r) c′ + √ S3 n(1− q)2 r2(1−q)  . where c′ > 0 is any positive real. Thus taking c′ sufficiently large (which depends on M, q), we conclude that
φ(r) ≤ Cq
[ 1
n +
( M1−qS3
n
) 1 1+q
+ √ S3 n r2(1−q) ] , (14)
whereCq is a constant depending only on q < 1. These two inequalities (Eq. (13) and Eq. (14)) give the first assertion. By noticing the assumption M ≥ 1, r∗ can be derived from a simple calculation.

heading: B DERIVATION OF COMPRESSION BASED BOUND FOR NON-COMPRESSED NETWORKS

heading: B.1 FULL MODEL BOUND
text: Here, we assume that the model F̂ of the trained network is the full model F̂ = F = NN(m, R2, RF) and Ĝ is included in NN(m, R̂2, R̂F). Then, their covering entropy is bounded by log(N (F̂ , ‖ · ‖∞, )) ≤ ( L∑ `=1 m`m`+1) log( −1) + L( L∑ `=1 m`m`+1) log(L(R2 ∨ 1)(max ` m` + 1)),
log(N (Ĝ, ‖ · ‖∞, )) ≤ ( L∑ `=1 m`m`+1) log( −1) + L( L∑ `=1 m`m`+1) log(L(R̂2 ∨ 1)(max ` m` + 1)).
Hence, the condition in Lemma 3 holds for S1 = ∑L `=1m`m`+1, S2 = LS1 log(L(R2 ∨ R̂2 ∨ 1)(max`m` + 1)) and S3 = 0. In this case, we can set
r2∗ = C (M + 1)(S1 + 1 + S2 log(n)) +Mt
n
for a constant C > 0.

heading: B.2 COMPLEXITY OF A SPARSE MODEL (PROOF OF EXAMPLE 1)
text: Suppose that Ĝ is the model with sparse weight matrices given in Example 1. Let m = max`m` and B = R2, then we can see that Ĝ ⊂ Φ(L,m, S,B) where the definition of Φ(L,m, S,B) is given in Appendix C.1. Therefore, its covering number is bounded by
log(N (Ĝ, ‖ · ‖∞, )) ≤ S log( −1) + LS log(L(R2 ∨ 1)(max
` m` + 1)) ≤ O(SL log(n) + S log( −1)),
by Lemma 4. Hence, the Rademacher complexity is bounded as Ĝ ≤ CM √ L S
n log(nL(R2 ∨ 1)(max ` m` + 1)) = O
( M √ L S
n log(n)
) ,
by the Dudley integral, R̄(Ĝ) . ∫M 0 √ log(N (Ĝ,‖·‖∞, )) n d , where C is a universal constant.

heading: B.3 NEAR LOW RANK CONDITION ON THE WEIGHT MATRIX (PROOF OF THEOREM 2 AND
text: COROLLARY 1 )
Here, we give proofs of Theorem 2 and Corollary 1 which give a generalization error bound when the trained network has near low rank weight matrices (W (`))L`=1 (Assumption 4).
Under Assumption 4, we can see that for any 1 ≤ s ≤ min{m`,m`+1}, we can approximate W (`) by a rank s matrix W ′ as
‖W (`) −W ′‖2 ≤ V0s−α, ‖W ′‖2 ≤ ‖W (`)‖2 (15)
‖W (`) −W ′‖F ≤ 1√
2α− 1 V0(s− 1)(1−α)/2. (16)
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 ∈ F̂ , there exists f ′ ∈ F such that it has width s = (s1, . . . , sL), weight matrix W ](`) with ‖W ](`)‖2 ≤ R2, ‖W ](`)‖F ≤ RF and
‖f − f ′‖∞ ≤ L∑ `=1 V0R L−1 2 s −α ` Bx. (17)
This can be proved as follows. Let f ′(x) = G ◦ (W ](L)η(·)) ◦ · · · ◦ (W ](1)x) where W ](`) is a rank s` matrix that satisfies Eqs. (15) and (16) for W ′ = W ](`). Let f`(x) = G ◦ (W ](L)η(·))◦ · · · ◦ (W ](`+1)η(·))◦ (W (`)η(·))◦ · · · ◦ (W (1)x) and f0(x) = f ′. Then, ‖f −f ′‖∞ ≤∑L `=1 ‖f`−f`−1‖∞.We can see that ‖(W (`)η(·))◦· · ·◦(W (1)x)‖ ≤ ∏` k=1 ‖W (k)‖2‖x‖ ≤ R`2Bx, ‖(W ](`)η(·)) ◦ (W (`−1)η(·)) ◦ · · · ◦ (W (1)x) − (W (`)η(·)) ◦ (W (`−1)η(·)) ◦ · · · ◦ (W (1)x)‖ ≤ ‖W (`) −W ](`)‖2‖(W (`−1)η(·)) ◦ · · · ◦ (W (1)x)‖ ≤ V0s−α` R
`−1 2 Bx. This gives ‖f` − f`‖∞ ≤∏L
k=`+1 ‖W (k)‖2V0s −α ` R `−1 2 Bx ≤ R L−1 2 V0s −α ` Bx. Finally, by summing up this from ` = 1 to
` = L, we obtain Eq. (17).
In particular, for any > 0, by setting s′` = s ′ `( ) = min{d( /(LV0R L−1 2 Bx)) −1/αe,m` ∧m`+1} for all `, then ‖f − f ′‖∞ ≤ . This indicates that, by Lemma 5, the covering entropy of F̂ is bounded by
log(N (F̂ , ‖ · ‖∞, )) ≤ ( L∑ `=1 (m` +m`+1)s ′ `( /2) ) [log( −1) + 2L log(2L(R2 ∨ 1)(max ` m` + 1))]
(18)
≤ 2( L∑ `=1 m`)(2LV0R L−1 2 Bx) 1/α −1/α[log( −1) + 2L log(2L(R2 ∨ 1)(max ` m` + 1))].
As the compressed network Ĝ, we may choose Ĝ = NN(m, s, R2, RF) for s = (s1, . . . , sL) so that, for all f ∈ F̂ , there exists g ∈ Ĝ satisfying
‖f − g‖∞ ≤ (V0RL−12 Bx) L∑ `=1 s−α` .
Hence, we may set r̂2 = [(V0RL−12 Bx) ∑L `=1 s −α ` ]
2. In this case, the covering number of Ĝ is bounded as (18) by replacing s′` with s`.
Therefore, Lemma 3 gives that
r2∗ ≤ C (M + 1)(S1 + 1 + S2 log(n)) +Mt
n ∨M
2α−1 2α+1 ( S3 n ) 2α 1+2α ,
where
S1 = L∑ `=1 s`(m` +m`+1),
S2 = LS1 log(L(R2 ∨ 1)(max ` m` + 1)),
S3 = ( L∑ `=1 m`)(2LV0R L−1 2 Bx) 1/α[log(n) + 2L log(2L(R2 ∨ 1)(max ` m` + 1))],
where q = 1/2α was used. This indicates that, if α > 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 is smaller than ∑L `=1m`m`+1
n because each rank s` must satisfy s` ≤ min{m`,m`+1}. Finally, we observe that
R̄n(Ĝ) ≤CM √ L ∑L `=1 s`(m` +m`+1)
n log(nL(R2 ∨ 1)(max ` m` + 1)),
by Lemma 5 for Ĝ = NN(m, s, R2, RF) and the Dudley integral (van der Vaart & Wellner, 1996): R̄(Ĝ) . ∫M 0 √ log(N (Ĝ,‖·‖∞, )) n d . This gives Theorem 2.
Corollary 1 can be obtained by substituting s` = min{m`,m`+1, dLV0RL−12 Bxe1/α}.
B.4 IMPROVED BOUND WITH LIPSCHITZ CONTINUITY CONSTRAINT
In the generalization error bound of Theorem 2 and Corollary 1, there appears RL2 . Even though R2 can be much smaller than RF, the exponential dependency RL2 could give lose bound as pointed out in Arora et al. (2018). We improve this exponential dependency by assuming the following condition.
Assumption 6 (Lipschitz continuity between layers: Interlayer cushion, interlayer smoothness (Arora et al., 2018)). For the trained network f̂ = G ◦ (W (L)η(·)) ◦ · · · ◦ (W (1)x), let φ`(x) = η ◦ (W (`−1)η(·))◦· · ·◦(W (1)x) be the input to the `-th layer andM`,`′(x) = (W (`
′)η(·))◦· · ·◦(W (`)x) be the transformation from the `-th layer to `′-th layer. Then, we assume that there exists κ, τ > 0 such that τ ≤ 1/(2κ2L) and for any `, `′ ∈ [L],
n∑ i=1 [M`,`′(φ`(xi) + ξ (1) i )−M`,`′(φ`(xi) + ξ (1) i + ξ (2) i )] 2 ≤ κ2 ( ‖ξ(1)‖+ τ‖ξ(2)‖ )2 ,
for all ξ(1) = (ξ(1)1 , . . . , ξ (1) n )> ∈ Rn and ξ(2) = (ξ(2)1 , . . . , ξ (2) n )> ∈ Rn.
This assumption is a simplified version of the interlayer cushion and the interlayer smoothness introduced in Arora et al. (2018). Although a trivial bound of κ is κ ≤ RL2 , the practically observed Lipschitz constant is usually much smaller. Assumption 6 captures this point and gives better dependency on the depth L. Actually, we can remove the exponential dependency on R2 as in the following corollary. Corollary 2. Under Assumptions 4 and 6, it holds that
Ψ(f̂) ≤ Ψ̂(f̂) + C [ M1−1/2α √ L ( ∑L `=1m`)(2LV0κ 2Bx)1/α
n log(n) +M 2α−1 2α+1A′2 2α 2α+1 + 1 + tM
n ] for A′2 = L ( ∑L `=1m`)(2LV0κ 2Bx) 1/α n with probability 1 − 3e −t for any t > 1 where C is a constant depending on α.
This is almost same as Corollary 1, but the exponential dependency on RL2 is replaced by the Lipschitz continuity κ2.
Proof of Corollary 2. Suppose that s` ≥ min { m`,m`+1, d(4κV0L)1/αe } , (19)
then we show that Eq. (17) can be replaced by
‖f − f ′‖n ≤ 4 L∑ `=1 V0κ 2s−α` Bx, (20)
where if s` = min{m`,m`+1}, then s−α` term can be replaced by 0 (which means no-compression in the layer `). Once we obtain this evaluations, then the following argument is same as the proof of Theorem 2 and Corollary 1 (Sec. B.3).
Let φ`(x) = η ◦ (W (`)η(·)) ◦ · · · ◦ (W (1)x) and φ]`(x) = η ◦ (W ](`)η(·)) ◦ · · · ◦ (W ](1)x) for ` = 1, . . . , L− 1, and let φL(x) = G ◦ (W (L)η(·)) ◦ · · · ◦ (W (1)x) and φ]L(x) = G ◦ (W ](L)η(·)) ◦ · · · ◦ (W ](1)x). Let CB := 2κBx. We will show that
‖φk − φ]k‖n ≤ 2κV0CB  k∑ j=1 s−αj  , ‖φ]k‖n ≤ CB , for all k = 1, . . . , L. We show this by inductive reasoning. To do so, we assume that, for k = 1, . . . , ` − 1, this is satisfied, and then we show this for k = `. Note that, for all k with k < `, it holds that, for any `′ > k,
‖Mk,`′ ◦ φ]k −Mk−1,`′φ ] k−1‖n ≤ κ(‖φ ] k − η(W (k)φ]k−1)‖n + τ‖η(W (k)φ]k−1)− φk‖n)
≤ κ(V0s−αk ‖φ ] k−1‖n + τκ‖φ ] k−1 − φk−1‖n)
≤ κ V0s−αk CB + τκ2κV0CB ∑ j≤k−1 s−αj  (by induction) ≤ κV0CB
s−αk + 1L k−1∑ j=1 s−αj  (by the assumption of τ). Note that the term s−αk can be replaced by 0 if sk = min{mk,mk+1} which corresponds to the full rank setting (W ](k) = W (k)). Therefore, we have that
‖φ` − φ]`‖n ≤ ∑̀ j=1 ‖Mj,` ◦ φ]j −Mj−1,` ◦ φ ] j−1‖n ≤ 2κV0CB (∑̀ k=1 s−αk ) .
Under the setting (19), this gives that
‖φ` − φ]`‖n ≤ CB/2.
Finally, noting that ‖φ`‖n ≤ CB/2, we have
‖φ]`‖n ≤ CB . This concludes the inductive reasoning.
Finally, noting that f = φL and f ′ = φ ] L, we have Eq. (20).

heading: B.5 NEAR LOW RANK CONDITION ON THE COVARIANCE MATRIX (PROOF OF THEOREM 3 AND THEOREM 4)
text: 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 ](k))`−1k=1 where each W ](k) has size m]k+1 × m ] k (here, m ] k ≤ mk is assumed), and, in the ` − 1-th layer, W ](`−1) has size m` × m]`−1. The input to the `-th layer of the compressed networkis denoted by φ]`(x) = η(W ](`−1)η(· · ·W ](1)x) · · · ). Let r2` = ‖‖φ` − φ ] `‖‖2n and Σ ] (`) := 1 n ∑n i=1 φ ] `(xi)(φ ] `(xi)) >.
For a given matrix Σ and a precision r2 > 0, the degrees of freedom3 are defined as
N`(r 2,Σ) := m∑̀ j=1 σj(Σ) σj(Σ) + r2 . (21)
Since the degrees of freedom are monotonically increasing with respect to each σj(Σ), we can see that N`(r2,Σ) ≥ N`(r2,Σ′) if Σ Σ′. Let4
m]` = d5N`(r 2,Σ](`)) log(80N`(r 2,Σ](`)))e,
then Proposition 1 tells that there exits a matrix Â` ∈ m` ×m]` and J` ⊂ {1, . . . ,m`}m ] ` such that
‖w>φ]` − w >Â`φ ] `,J` ‖2n ≤ 4r2w>Σ ] (`)(Σ ] (`) + r 2I)−1w ≤ 4r2‖w‖2, (22)
for any w ∈ Rm`5, and the norm of Â` is bounded as ‖Â`‖2 ≤ √ 20
3 m`.
Next, we evaluate the degrees of freedom of Σ](`). We bound this by using the degrees of freedom of Σ̂(`). First note that r2` = ‖‖φ` − φ ] `‖‖2n. Let s ≤ m. For any matrix U ∈ Rm`×s such that U>U = Is, Tr[U>Σ ] (`)U ] = Pn[φ ] ` > UU>φ]`] ≤ 2{Pn[φ>` UU>φ`] + Pn[(φ` − φ ] `) >UU>(φ` − φ]`)]} by the Cauchy-Schwartz inequality. Here, let U be the matrix that gives Pn[φ>` UU>φ`] =∑m` j=m`−s+1 σj(Σ̂(`)) = infU :U>U=Is Pn[φ > ` UU >φ`], then by noticing Pn[(φ` − φ]`)>UU>(φ` − φ]`)] ≤ Pn‖φ` − φ ] `‖2 ≤ r2` , we obtain that Pn[φ ] ` > UU>φ]`] ≤ 2[ ∑m` j=m`−s+1 σj(Σ̂(`)) + r 2 ` ]. Finally, by minimizing the left hand side with respect to U , we obtain that
m∑̀ j=m`−s+1 σj(Σ ] (`)) ≤ 2  m∑̀ j=m`−s+1 σj(Σ̂(`)) + r 2 `  . By setting s = m` −m+ 1 for 1 ≤ m ≤ m`, this indicates that
m∑̀ j=m σj(Σ ] (`)) ≤ 2  m∑̀ j=m σj(Σ̂(`)) + r 2 `  ≤ 2  m∑̀ j=m µ̇ (`) j + r 2 `  . 3The definition is not dependent on `, but to make it clear that we are dealing with the `-th layer, we use the notation N`. 4dxe is the smallest integer that is not less than x ∈ R. 5For a vector x ∈ Rm and index set J ∈ {1, . . . ,m}l, xJ is the vector corresponding to the index set J , that is, xJ = (xj)j∈J .
Now, let ṁ` := min{j ∈ {1, . . . ,m`} | µ̇(`)j ≤ r2} (if µ̇ (`) m` > r 2, then we set ṁ` = m`). Then,
N`(r 2,Σ](`)) = m∑̀ j=1 σj(Σ ] (`)) σj(Σ ] (`)) + r 2 ≤ ṁ` + ∑ j>ṁ` σj(Σ ] (`)) σj(Σ ] (`)) + r 2
≤ ṁ` + ∑ j>ṁ` σj(Σ ] (`)) r2 ≤ ṁ` + 2 r2 r2` + ∑ j>ṁ` σj(Σ̂(`))  ≤ ṁ` + 2
r2
( r2` + U0 ṁ1−β` β − 1 ) ≤ ṁ` + 2 r2 ( r2` + ṁ`r 2 β − 1 ) ≤ ṁ` + 2
r2
( r2` + ṁ`r 2
β − 1
) = β + 1
β − 1 ṁ` + 2 r2` r2 .
Now, let
r2 = 1
4 r̃2` ,
then
N`(r 2,Σ](`)) ≤
β + 1 β − 1 ṁ` + 8 r2` r̃2` .
We define the right hand side as m]`:
m]` := β + 1
β − 1 ṁ` + 8 r2` r̃2` .
We have, by Eq. (22), m`+1∑ j=1 ‖η(W (`)j,: φ ] `)− η(W (`) j,: Â`φ ] `,J` )‖2n ≤ 4 m`+1∑ j=1 ‖W (`)j,: ‖ 2r2
≤ 4R2F × 1
4 r̃2` = R 2 Fr̃ 2 ` .
By the induction assumption, we also have that
‖‖η(W (`)φ]`)− φ`+1‖‖ 2 n = ‖‖η(W (`)φ ] `)− η(W (`)φ`)‖‖2n ≤ ‖W (`)‖22r2` ≤ R22r2` .
Combining these inequalities, if we define
φ]`+1 = η(W (`)Â`φ ] `,J` (x)),
and set W ](`) = W (`)Â` and reset W ](`−1) ←W ](`−1)J`,: , then it holds that
‖‖φ`+1 − φ]`+1‖‖n ≤ r`+1 where we let
r`+1 = R2r` +RFr̃`.
Letting r0 = 0, by an induction argument, we obtain
r`+1 ≤ ∑̀ k=1 R (`−k) 2 RFr̃k.
Finally, we obtain
‖f̂ − f ]‖2n ≤ r2L ≤ [ L∑ k=1 R (L−k) 2 RFr̃` ]2 ,
for a compressed network f ] that has width m] = (m]1, . . . ,m ] L) with parameters W ](`) = W (`) J`+1,: Â`. Note that
‖W ](`)‖2 ≤ ‖W (`)J`+1,:‖2‖Â`‖2 ≤ R2
√ 20
3 m`, ‖W ](`)‖F ≤ ‖W (`)J`+1,:‖F‖Â`‖2 ≤ RF
√ 20
3 m`.
Therefore, if we set Ĝ = NN(m], √
20 3 max`m`R2, √ 20 3 max`m`RF ), then there exists ĝ ∈ Ĝ
such that ‖f̂ − ĝ‖n ≤ r̂
where r̂2 = r2L.
Moreover, applying Lemma 5 to Ĝ and the Dudley integral yields
R̄(Ĝ) ≤ CM √ L ∑L `=1m ] `m ] `+1
n log(nL(R2 ∨ 1)(max ` m` + 1)2).
This gives the assertion of Theorem 3.
Here, we consider a situation where R2Fr̃ 2 ` = c 2 0 r2`R 2 2 ` for some constant c0 > 0. Then it holds that
r`+1 = R2
( 1 + √ c20 ` ) r` = R ` 2 ∏̀ k=1 ( 1 + √ c20 k ) r1 ≤ R`2 exp ( c0(2 √ `− 1) ) r1.
Therefore, by setting CL := (1 ∨ R2)L exp ( c0(2 √ L− 1) ) , it holds that r` ≤ CLr1 for ` =
1, . . . , L, in particular, we have r̂ ≤ CLr1.
In this situation, the degrees of freedom are bounded by
N`(r 2,Σ](`)) ≤ m ] ` =
β + 1 β − 1 ṁ` + 8` R2F c20R 2 2 .
Next, we bound ṁ`. To do so, we should bound r̃` from below. Note that
r̃` = c0R2 RF 1√ ` r` = c0R2 RF 1√ ` R`−12 `−1∏ k=1
( 1 + √ c20 k ) r1 ≥ c0R ` 2
RF 1√ ` `−1∏ k=1
( 1 + √ c20 k ) r1
≥ c0R ` 2
RF 1√ `
( 1 +
`−1∑ k=1 √ c20 k ) r1 ≥ c0R ` 2 RF 1√ ` ( 1 + 2c0( √ `− 1) ) r1
≥ c0R ` 2
RF ( 1√ ` + 2c0(1− 1√ ` ) ) r1.
Hence, ṁ` ≤ (r̃2`/(4U0))−1/β ≤ (4U0)1/β { c0R ` 2
RF [ 1√ ` + 2c0(1− 1√ ` ) ] r1 }−2/β ≤ (4U0)1/β [ RF c0R`2 ]2/β ( 1 2 ∧ c0 )−2/β r −2/β 1 ≤ [ 4U0R 2 F (0.5 ∧ c0)2c20R2`2 ]1/β r −2/β 1 .
By Lemma 3, we can evaluate r2∗ for F̂ satisfying Assumption 4 as
r2∗ ≤ C (M + 1)(S1 + 1 + S2 log(n)) +Mt
n ∨M
2α−1 2α+1 ( S3 n ) 2α 1+2α ,
where
S1 = L∑ `=1 m]`m ] `+1,
S2 = LS1 log(L(R2 ∨ 1)(max ` m` + 1) 2) = O
( L
L∑ `=1 m]`m ] `+1 log(n)
) ,
S3 = ( L∑ `=1 m`)(2LV0R L−1 2 Bx) 1/α[log(n) + 2L log(2L(R2 ∨ 1)(max ` m` + 1) 2)]
= O ( L(
L∑ `=1 m`)(2LV0R L−1 2 Bx) 1/α log(n)
) ,
Then, the overall generalization error is upper bounded by
Ψ(f̂) ≤ Ψ̂(f̂) + C r2∗ +√S3n r̂2(1−1/2α) + √ (M2 + r̂2)L ∑L `=1m ] `m ] `+1 n log(n) + 1 +Mt n  , with probability 1−3e−t for all t ≥ 1. By lettingQ′L,α,n := L (2LV0R L−1 2 Bx) 1/α log(n) n and assuming r̂ ≤ 1, the second and third terms in C[·] is bounded by√√√√Q′L,α,n( L∑ `=1 m`)(CLr1)2(1−1/2α) + C ′M √ L ∑L `=1 [ṁ` + `R 2 F/(c 2 0R 2 2)] 2 n log(n)3
≤ √√√√Q′L,α,n( L∑ `=1 m`)(CLr1)2(1−1/2α) + 2C ′M √√√√ L L [ 4U0R2F (0.5∧c0)2c20(1∧R2)2L ]2/β r −4/β 1 + L 3R4F/R 4 2 n log(n)3.
Hence, by setting CLr1 = (∑L `=1m` L )− 1 4/β+2(1−1/2α)
which balances the first and the second terms, then r̂ ≤ CLr1 ≤ 1 and the right hand side is bounded by√√√√Q′L,α,n( L∑
`=1
m`) 4/β 4/β+2(1−1/2α)L 2(1−1/2α) 4/β+2(1−1/2α)
+ CM √√√√ L L 2(1−1/2α) 4/β+2(1−1/2α) ( ∑L `=1m`) 4/β 4/β+2(1−1/2α) (CL)4/β [ 4U0R2F (0.5∧c0)2c20(1∧R2)2L ]2/β n log(n)3
+ CM R2F R22
√ L4
n log(n)3.
Finally, by setting c0 = 1/4, we obtain the assertion for
QL =
4U0R2F(1 ∨R2)L exp ( c0(2 √ L− 1) ) (0.5 ∧ c0)2c20(1 ∧R2)2L 2/β ≤ 4U0R2F(1 ∨R2)L exp ( 1 4 (2 √ L− 1) ) (0.25)4(1 ∧R2)2L 2/β . This gives Theorem 4.
B.6 IMPROVED BOUND OF THEOREM 4 WITH LIPSCHITZ CONTINUITY CONSTRAINT
Here, we again note that there appearsRL2 in PL andQL in the bound of Theorem 4. This is due to a rough evaluation of the interlayer Lipschitz continuity. We can reduce this exponential dependency under Assumption 6. Corollary 3. Assume Assumption 6 in addition to Assumptions 4 and 5, then the bound in Theorem 4 holds for the following redefined PL and QL:
PL = (2LV0κ 2Bx) 1/α, QL =
[ 4U0R 2 F exp( 14 (2 √ L−1))
(0.25)4
]2/β ,
except that the term M R 2 FL 2
R22
√ log(n)3
n is replaced by Mκ 2R2FL
2 √ log(n)3
n :
Ψ(f̂) ≤ Ψ̂(f̂) + C [ M √√√√√ [PL ∨QL]L1+ β4α(2α−1)+β n ( L∑ `=1 m` ) 4/β 4/β+2(1−1/2α) log(n)3
+M 2α−1 2α+1 ( LPL ∑L `=1m` n log(n) ) 2α 2α+1 +Mκ2R2FL 2 √ log(n)3 n + 1+Mt n ] .
Proof of Corollary 3. To show Corollary 3, we set
r̃` = 1√ ` `−1∏ k=1
( 1 + √ c20 k ) r1 RF ,
where c0 is a constant, and by the same argument as in the proof of Corollary 2, we can show that
r` ≤ 2κ ∑̀ k=1 1√ k k−1∏ j=1 1 +√c20 j  r1. Then, through a cumbersome calculation, we have that
r` r̃` ≤ CκRF c0
√ `,
for a universal constant C. Moreover, we can show that r` can be bounded as
r` ≤ 2κ ec0(2 √ `+1−1) − ec0 c0 r1.
This also gives rL ≤ C ′ κ
c0 exp(c0(2
√ L− 1))r1,
for a universal constant C ′. Then, redefining CL = κ exp(c0(2 √ L − 1)), we can apply the same argument as in the proof of Corollary 2. Indeed, we can show
ṁ` .
[ 4U0R 2 F
(0.5 ∧ c0)2c20κ2
]1/β , m]` = β + 1
β − 1 ṁ` + C 2` R2F c20 r −2/β 1 .
From the above argument, if we set Ĝ = NN(m], √
20 3 max`m`R2, √ 20 3 max`m`RF ), then there
exists ĝ ∈ Ĝ such that ‖f̂ − ĝ‖n ≤ r̂
where r̂2 = r2L.
Moreover, we can show
r2∗ ≤ C (M + 1)(S1 + 1 + S2 log(n)) +Mt
n ∨M
2α−1 2α+1 ( S3 n ) 2α 1+2α ,
where
S1 = L∑ `=1 m]`m ] `+1,
S2 = LS1 log(L(R2 ∨ 1)(max ` m` + 1) 2) = O
( L
L∑ `=1 m]`m ] `+1 log(n)
) ,
S3 = ( L∑ `=1 m`)(2LV0κ 2Bx) 1/α[log(n) + 2L log(2L(R2 ∨ 1)(max ` m` + 1) 2)]
= O ( L(
L∑ `=1 m`)(2LV0κ 2Bx) 1/α log(n)
) .
Here, to evaluate S3, we used the argument in Sec. B.4 (proof of Corollary 2).
The remaining argument is the same as the proof of Theorem 3 and Theorem 4 (Sec. B.5).

heading: C AUXILIARY LEMMAS
text: In this section, we give several auxiliary lemmas that are used in the proof of the theorems. These results are not new at all, but we explicitly present them for completeness.

heading: C.1 COVERING NUMBER OF DEEP NETWORK MODELS
text: Define the neural network with height L, width m, sparsity constraint S and norm constraint B as
Φ(L,m, S,B) := {G ◦ (W (L)η(·) + b(L)) ◦ · · · ◦ (W (1)x+ b(1)) |W (L) ∈ R1×m, b(L) ∈ R, W (1) ∈ Rm×d, b(1) ∈ Rm, W (`) ∈ Rm×m, b(`) ∈ Rm(1 < ` < L),∑L
`=1 (‖W (`)‖0 + ‖b(`)‖0) ≤ S,max ` ‖W (`)‖∞ ∨ ‖b(`)‖∞ ≤ B},
where ‖ · ‖0 is the `0-norm of the matrix (the number of non-zero elements of the matrix) and ‖ · ‖∞ is the `∞-norm of the matrix (maximum of the absolute values of the elements).
The following evaluation of the covering number of the model Φ(L,m, S,B) is shown by SchmidtHieber (2019); Suzuki (2019). Lemma 4 (Covering number evaluation (Schmidt-Hieber, 2019; Suzuki, 2019)). The covering number of Φ(L,m, S,B) can be bounded by
logN (Φ(L,m, S,B), ‖ · ‖∞, δ) ≤ S log(δ−1L(B ∨ 1)L−1(m+ 1)2L) ≤ 2SL log((B ∨ 1)(m+ 1)) + S log(δ−1L).
Proof of Lemma 4. Given a network f ∈ Φ(L,m, S,B) expressed as
f(x) = G ◦ (W (L)η(·) + b(L)) ◦ · · · ◦ (W (1)x+ b(1)),
let Ak(f)(x) = η ◦ (W (k−1)η(·) + b(k−1)) ◦ · · · ◦ (W (1)x+ b(1)),
and Bk(f)(x) = G ◦ (W (L)η(·) + b(L)) ◦ · · · ◦ (W (k)η(x) + b(k)),
for k = 2, . . . , L. Corresponding to the last and first layer, we define BL+1(f)(x) = x and A1(f)(x) = x. Then, it is easy to see that f(x) = Bk+1(f) ◦ (W (k) · +b(k)) ◦ Ak(f)(x). Now, suppose that a pair of different two networks f, g ∈ Φ(L,m, S,B) given by
f(x) = G◦(W (L)η(·)+b(L))◦· · ·◦(W (1)x+b(1)), g(x) = G◦(W (L) ′ η(·)+b(L) ′ )◦· · ·◦(W (1) ′ x+b(1) ′ ),
has a parameters with distance δ: ‖W (`) −W (`)′‖∞ ≤ δ and ‖b(`) − b(`) ′‖∞ ≤ δ. Now, not that ‖Ak(f)‖∞ ≤ maxj ‖W (k−1)j,: ‖1‖Ak−1(f)‖∞ + ‖b(k−1)‖∞ ≤ mB‖Ak−1(f)‖∞ + B ≤ (B ∨ 1)(m+ 1)‖Ak−1(f)‖∞ ≤ (B ∨ 1)k−1(m+ 1)k−1, and similarly the Lipshitz continuity of Bk(f) with respect to ‖ · ‖∞-norm is bounded as (Bm)L−k+1. Then, it holds that
|f(x)− g(x)|
= ∣∣∣∣∣ L∑ k=1 Bk+1(g) ◦ (W (k) ·+b(k)) ◦ Ak(f)(x)− Bk+1(g) ◦ (W (k) ′ ·+b(k) ′ ) ◦ Ak(f)(x) ∣∣∣∣∣ ≤
L∑ k=1 (Bm)L−k‖(W (k) ·+b(k)) ◦ Ak(f)(x)− (W (k) ′ ·+b(k) ′ ) ◦ Ak(f)(x)‖∞
≤ L∑ k=1 (Bm)L−kδ[m(B ∨ 1)k−1mk−1 + 1]
≤ L∑ k=1 (Bm)L−kδ(B ∨ 1)k−1mk ≤ δL(B ∨ 1)L−1(m+ 1)L.
Thus, for a fixed sparsity pattern (the locations of non-zero parameters), the covering number is bounded by ( δ/[L(B ∨ 1)L−1(m+ 1)L] )−S . There are the number of configurations of the sparsity
pattern is bounded by ( (m+1)L
S
) ≤ (m + 1)LS . Thus, the covering number of the whole space Φ is
bounded as (m+ 1)LS { δ/[L(B ∨ 1)L−1(m+ 1)L] }−S = [δ−1L(B ∨ 1)L−1(m+ 1)2L]S ,
which gives the assertion.
Lemma 5 (Covering number evaluation). Let NN(m, R2, RF) be the set of neural networks with depth m(m1, . . . ,mL), ‖W (`)‖∞ ≤ R2 and ‖W (`)‖F ≤ RF . The covering number of NN(m, R2, RF) can be bounded by
logN (NN(m, R2, RF), ‖ · ‖∞, δ)
≤ ( L∑ `=1 m`m`+1) log(δ −1L(R2 ∨ 1)L−1(max ` m` + 1) L)
≤ ( L∑ `=1 m`m`+1) log(δ −1) + L( L∑ `=1 m`m`+1) log(L(R2 ∨ 1)(max ` m` + 1)).
Moreover, the set of networks with low rank weight matrices, NN(m, s, R2, RF), has the following covering number bound:
logN (NN(m, s, R2, RF), ‖ · ‖∞, δ)
≤ L∑ `=1 s`(m` +m`+1) log(δ −1L(R2 ∨ 1)2L−1(max ` m` + 1) 2L.
Proof of Lemma 5. Let B = R2, m = max`m`, and S = ∑L `=1m`m`+1, then we can see that NN(m, R2, RF) is a subset of Φ(L,m, S,B) because ‖W‖∞ ≤ ‖W‖2. Hence Lemma 4 gives the first assertion. As for the second one, we can easily check that the covering number of NN(m, s, R2, RF) can be bounded by the one given in Lemma 5 for Φ(2L,m, S,B) with S = ∑L `=1 s`(m` +m`+1). Then, we obtain the second assertion.

heading: C.2 COMPRESSION ERROR BOUND FOR ONE LAYER
text: The following proposition was shown by Bach (2017); Suzuki et al. (2018). Let Σ̂I,I′ ∈ RK×H for integers K,H ∈ N and a matrix Σ̂I,I′ ∈ RK×H be a matrix (Σ̂i,j)i∈I,j∈I′ for the index sets I ∈ [m`]K and I ′ ∈ [m`]H . Let F = {1, . . . ,m`} be the full index set. Let the degrees of freedom corresponding to Σ̂ be N̂(λ) := N`(λ, Σ̂) (see Eq. (21)) for λ > 0.
Proposition 1. Let U = (Uj,l)j,l is the orthogonal matrix that diagonalizes Σ̂, that is, Σ̂ = Udiag (µ̂1, . . . , µ̂m`)U > for µ̂j ≥ 0 (j = 1, . . . ,m`). Define
τ ′j = 1
N̂(λ) m∑̀ l=1 U2j,l µ̂ (`) l µ̂ (`) l + λ = 1 N̂(λ) [Σ̂(Σ̂ + λI)−1]j,j (j ∈ {1, . . . ,m`}). (23)
For λ > 0, if m ≥ 5N̂(λ) log(80N̂(λ)),
then there exist v1, . . . , vm ∈ {1, . . . ,m`} such that, for every α ∈ Rm` ,
inf β∈Rm  ∥∥∥∥∥∥α>η(F̂`−1(·))− m∑ j=1 βjη(F̂`−1(·))vj ∥∥∥∥∥∥ 2
n
+mλ‖β‖2τ ′  ≤ 4λα>Σ̂(Σ̂ + λI)−1α, (24)
and ∑m j=1 τ ′ j −1 ≤ 53m × m`, where ‖β‖ 2 τ ′ := ∑m j=1 β 2 j τ ′ j . Let τ := mλτ ′ and Iτ = diag (τ). Then, Â := Σ̂F,J(Σ̂J,J + Iτ )−1 for J = {v1, . . . , vm} satisfies
‖Â‖2 ≤ √ 20
3 m`,
and the optimal β that achieves the infimum is given by β̂ = Â>α for any α ∈ Rm` .

heading: C.3 CONCENTRATION INEQUALITY
text: Proposition 2 (Talagrand’s Concentration Inequality (Talagrand, 1996; Bousquet, 2002)). Let G be a function class on X that is separable with respect to ∞-norm, and {xi}ni=1 be i.i.d. random variables with values in X . Furthermore, let B ≥ 0 and U ≥ 0 be B := supg∈G E[(g−E[g])2] and U := supg∈G ‖g‖∞, then for Z := supg∈G ∣∣ 1 n ∑n i=1 g(xi)− E[g]
∣∣, we have P ( Z ≥ 2E[Z] + √ 2Bt
n +
2Ut
n
) ≤ e−t, (25)
for all t > 0.

heading: D NUMERICAL EXPERIMENTS
text: 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 3 fully connected layers (named l16, . . . , l18). The size of each filter in each convolution layer is 3 × 3. Our theory does not support a convolution layer in a strict sense, but we adopt it as follows. If the convolution layer in the `-th layer has the input channel size m` and the output channel size m`+1 with the filter size k × k (in our case k = 3), then the weight matrix is given as a 4-way tensor with the size m`+1×m`× k× k: W (`) ∈ Rm`+1×m`×k×k. Although a singular value of a 4-way tensor is not well-defined, we can perform a low rank approximation of the weight matrix by folding out the tensor to a large matrix. Actually, considering “similarity” between the filters as
K(`) := ( m∑̀ c=1 k,k∑ κ1,κ2=1 W (`) i,c,κ1,κ2 W (`) j,c,κ1,κ2 )m`+1 i,j=1 ∈ Rm`+1×m`+1 ,
then we can easily see that, for s` ∈ [m`+1], it holds that
‖W (`) − P>W ′‖F = √√√√m`+1∑ j′=ṁ σj′(K(`)),
where P ∈ Rs`×m`+1 is a projection matrix to the eigen-space corresponding to the s` largest singular values of K(`), W ′ := PW (`) = ( ∑m`+1 i′=1 Pi,i′W (`) i′,j,k,k′)i,j,k,k′∈[s`]×[m`]×[k]×[k] and the Frobenius norm ‖ · ‖F of a tensor is the Euclidean norm as a vector. Therefore, we can use the eigenvalues of K(`) to evaluate the redundancy of parameters among filters.
As for the covariance matrix in a convolution layer, we also apply the same argument. That is, the input to the `-th layer (which is a convolution layer) is given by φ`(x) ∈ Rm`×I×J where I and J are the width and height of the input, and we define the following “covariance” matrix as a similarity measure between the channels:
Σ̂(`) =  1 n n∑ i′=1 ∑ 1≤c1≤I ∑ 1≤c2≤J φ`,(i,c1,c2)(xi′)φ`,(j,c1,c2)(xi′) m`,m` i,j=1 ∈ Rm`×m` .
This also serve the redundancy measure and analogous argument to the main text can be applied.
Near low rank properties of the covariance matrix and weight matrix Here, we see plausibility of the near low rank assumptions we made in the analysis. Figure 1 presents the eigenvalues of covariance matrix Σ̂(`) in each of layer c2, c7, c12 and l16. The eigenvalues are sorted in decreasing order. We can see that the eigenvalue distributions are highly concentrated around 0 and the eigenvalues decrease quickly, which indicates the near low rank property of Σ̂(`).
Next, we plot the eigenvalues of K(`) in Figure 2 for layer c2, c7, c12 and l16. We again observe a rapid decrease of the eigenvalues. These results justify our theoretical assumptions.
Intrinsic dimensionality Here, we calculate the intrinsic dimensionalities of the VGG-19 network. For that purpose, we set a threshold parameter ν ∈ {10−1, 10−2, 10−3} and compute
s` := #{j ∈ [m`+1] | σj(K(`)) ≥ ν × maxj′ σj′(K(`))} and ṁ` := #{j ∈ [m`] | σj(Σ̂(`)) ≥ ν × maxj′ σj′(Σ̂(`))} (which corresponds to setting r̃2` = 4ν × maxj′ σj′(Σ̂(`))). Table 4 summarizes the effective ranks ṁ`, s` of all layers. We can see that the effective ranks can be much smaller than the channel sizes in several layers (especially layers from c8 to l18,), which indicates the network has high redundancy and its intrinsic dimensionality could be much smaller than the actual number of parameters.
Next, we compute the intrinsic dimensionality of each layer based on the effective ranks calculated above. Basically, the main term of our bound (Theorem 4) is given by √∑L
`=1 ṁ`+1ṁ` n (note that
m]` is essentially controlled by ṁ`). Hence, we employ ṁ`+1 × ṁ` as the intrinsic dimensionality of each fully connected layer. As for a convolution layer, we employ ṁ`+1ṁ`k2 as the intrinsic dimensionality which is the number of parameters of compressed network. We also calculate the intrinsic dimensionality obtained by compressing only the weight matrix. That is given by s`m`k2+ m`+1s`. Both of them are summarized in Table 4. We can see that the intrinsic dimensionality is smaller than the actual number of parameters. In particular, it is much smaller for higher layers such as c8 to l18. This indicates that the information required for classification is almost distilled in the first few layers and the contribution of the subsequent layers would be much smaller than the earlier layers. Moreover, we see that compressing the network using the covariance matrix gives smaller intrinsic dimensionalities than the weight matrix. This is because the improvement induced by decreasing ṁ` is a quadratic order but that by s` is just a linear order. Another reason is that the effective rank of the covariance matrix is more data dependent in a 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 1 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 a better generalization error bound.
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 to note that the comparison is not completely fair because the intrinsic dimensionality of both our analysis and that of Arora et al. (2018) neglect constant functors (such as depth), and thus the final generalization error 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 can see
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 near low rank properties of both of weight matrices and covariance matrices yields sharper bounds. It can be realized by our unified theoretical frame-work.

Review summaries:
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.