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

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.

1. INTRODUCTION:

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 L 2 -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 α represents the eigenvalue drop rate of the weight matrix, and β represents that of the covariance matrix among the nodes in each internal layer. r is the bias induced by compression. "Original" indicates whether the bound is about the original network or not.

Compression No:

Ours (Thm. 1)

r 1 n + Ṙr ( F -G) + Rn ( G) General Yes Ours (Cor. 1) L(Lκ 2 ) 1/α Lm n

Low rank weight Yes:

Ours (Thm. 4)

L 1+ β 4α (2α-1) +β (Lm) 4/β 4/β+2(1-1/2α) n Low rank weight Low rank cov.

Yes 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-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.

2. PRELIMINARIES: PROBLEM FORMULATION AND NOTATIONS:

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 ∈ R d 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 D n = (x i , y i ) n i=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 ψ(y i , f (x i )), Ψ(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 L 2 -norm by

f n := n i=1 f (z i ) 2 /n for an empirical observation z i = (x i , y i ) (i = 1, . . . , n). The population L 2 - norm is denoted by f L2 := E Z∼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 m 1 = d (dimension of input) and m L+1 = 1 (dimension of output) for convention. Then, the set of networks having depth L and width m = (m 1 , . . . , m L ) with norm constraint as

NN(m, R 2 , R F ) := f (x) = G • (W (L) η(•)) • (W (L-1) η(•)) • • • • • (W (1) x) | W ( ) ∈ R m ×m +1 , W ( ) 2 ≤ R 2 , W ( ) F ≤ R F .

where W 2 := sup u: W u =0 W u / u1 is the operator norm (the maximum singular value),

W F := i,j W 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, R 2 , R F ) for a given R 2 , R F > 0.

Here, we implicitly suppose that R 2 is close to 1 so that the norm of the output from internal layers is not too much amplified, while R F 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 Rn (F ) := E sup f ∈F

1 n n i=1 i f (z i ) | D n where D n = (z i ) n i=1 = (x i , y i ) 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 D n . Its expectation with respect to D n is denoted by Rn (F ) := E Dn [ Rn (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.

The biggest difficulty for transforming the compression bound to that of f lies in evaluation of the population L 2 -norm between f and g. Basically, the compression based bounds are given as

EQUATION

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 ) + Rn ( 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 2 L2 + O p ( 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 (F ) := Rn ({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 P X and P Y 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(P Y ), u, u ∈ R).

The activation function η is also 1-Lipschitz continuous:

η(u) -η(u ) ≤ u -u (∀u ∈ R d )

where d is any positive integer. Assumption 2. The norm of input is bounded by B x > 0: x ≤ B x (∀x ∈ supp(P X )).

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 , R 2 , R F , M, B x 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

Rn (F) = O L n =1 m m +1 n log(n) .

In this bound, there appears the number of parameters n =1 m 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. 

(F) = O L 3 (max m )R 2 F /R 2 2 n

which avoids the exponential dependency. However, there is still dependency on the width, m R2 F , which is larger than the linear order of the width since R F could be moderately large. Bartlett et al. (2017b) showed

Rn (F) = O R L 2 √ n L R 2/3 2→1 R 2/3 2 3/2

. The norm constraint on R 2→1 implicitly assumes sparsity on the weight matrix and R 2→1 typically depends on the width linearly. Wei & Ma (2019) improved the exponential dependency R L 2 appearing in this bound (Bartlett et al., 2017b) to obtained a bound

O 1 √ n 1 + Lκ 4 3 R 2/3 2→1 + Lκ 2 3 R 2/3 1→1 3/2

where κ is the Lipschitz continuity between layers.

We can see that R 2 2→1 and R 2 1→1 can depend on the width linearly and quadratically respectively even though R 2 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 G are fixed independently on each data observation 2 . 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 ( 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

EQUATION

This is roughly given by the fixed point of a function r 2 → φ(r), and it is useful to bound the ratio of the empirical L 2 -norm and the population L 2 -norm of an element h in F -G: h 2 L2 /( 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 L 2 -distance between f and g is bounded by f -g n ≤ r2 for a fixed r > 0 almost surely. Let ṙ := 2(r 2 + r 2 * ), then, under Assumptions 1, 2, 3, there exists a universal constant C > 0 such that

Ψ( f ) ≤ Ψ( f ) + 2 Rn ( G) + M 2t n main term +C Ṙ ṙ (ψ( F) -ψ( G)) + ṙ 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 r 2 * = o(1/ √ n), and if we set r = o p (1), then the bias term can be faster than the main term which is

O(1/ √ n). The term Ṙ ṙ (ψ( 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 r 2 * is typically o(1/ √ n) and Ṙ ṙ (ψ( F) - ψ( 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 ) + O p Rn ( 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 Rn ( 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, R 2 , R F ) | 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 L S n log(n) (see Appendix B.2 for the proof). This is much smaller than the VC-dimension bound

L n =1 m m +1 n log(n) if S n =1 m 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.

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 ( ) ) 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 V 0 > 0 such that

σ j (W ( ) ) ≤ V 0 j -α , 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 ≤ V 0 s -α . Let the set of networks with exactly low rank weight matrices be NN

(m, s, R 2 , R F ) := {f ∈ NN(m, R 2 , R F ) | the weight matrix W ( ) of f has rank s } for s = (s 1 , . . . , s L ). If we set G = NN(m, s, R 2 , R F ),

then we have the following theorem.

Theorem 2. The compressed model G = NN(m, s, R 2 , R F ) has the following complexity:

Rn ( G) ≤CM L L =1 s (m + m +1 ) n log(n). If F satisfies Assumption 4, we can set r = V 0 R L-1 2 B x L =1 s -α : for any f ∈ F, there ex- ists g ∈ G such that f -g n ≤ r. Then, letting A 1 = L L =1 s (m +m +1 ) n log(n) and A 2 = L ( L =1 m )(2LV0R L-1 2 Bx) 1/α n

, the overall generalization error is bounded by

Ψ( f ) ≤ Ψ( f ) + C M A 1 + M 2α-1 2α+1 A 2α 1+2α 2 + r2(1-2α) A 2 + (r + M ) A 1 + 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 A 1 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 M 1-1/2α L ( L =1 m )(2LV0R L-1 2 Bx) 1/α n log(n) + M 2α-1 2α+1 A 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 =1 m 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 =1 m 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 R L 2 . Even though R 2 can be much smaller than R F , the exponential dependency R L 2 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 R L 2 , but instead κ 2 (κ: Lipschitz continuity) appears.

3.2. COMPRESSION BOUND WITH NEAR LOW RANK COVARIANCE MATRIX:

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

Σ ( ) = 1 n n i=1 φ (x i )φ (x i

) 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:

EQUATION

for a fixed β > 1 and U 0 > 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 theth layer, let ṁ :

= max{1 ≤ j ≤ m | μ( ) j ≥ r2 /4}. Then, we define N (r) = β+1 β-1 ṁ + 8 ( -1 k=1 R ( -1-k) 2 RF rk ) 2 r2

, for r = (r 1 , . . . , rL ). Correspondingly we set m := 5N (r) log(80N (r)). Then, we obtain the following theorem.

Theorem 3. Let r := L k=1 R (L-k) 2

R F rk . Then, under Assumption 5, there exists g with width

m = (m 1 , m 2 , . . . , m L ) that satisfies g ∈ NN(m , 20 3 max m R 2 20 3 max m R F ) and f -g n ≤ r.

In particular, we may set G = NN(m , 20 3 max m R 2 , 20 3 max m R F ), and then it holds that

Rn ( G) ≤ C L L =1 m +1 m 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 ṁ 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 =1 m 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]L 1+ β 4α (2α-1) +β n L =1 m 4/β 4/β+2(1-1/2α) log(n) 3 + M 2α-1 2α+1 LP L L =1 m n log(n) 2α 2α+1 + M R 2 F L 2 R 2 2 log(n) 3 n + 1+M t n , for P L = (2LV 0 R L-1 2 B x ) 1/α and Q L = 4U0R 2 F (1∨R2) L exp( 1 4 (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

Õ   ( L =1 m ) 4/β 4/β+2(1-1/2α) n + L =1 m n 2α 2α+1   ,

where the Õ(•) 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

L 2 log(n) n + L L =1 m n

. Moreover, the term dependent on the width is O(1/n) with respect to the sample size n which is faster than the rate O(

L =1 m 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 R L 2 , 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( 1 4 (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 on L). The bound is not optimized with respect to the dependency on the depth L. In particular, the term L 2 log(n)/n could be an artifact of the proof technique and the L 2 term would be improved.

Finally, we compare our bound with the following norm based bounds; O

R L 2 √ 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 3 R 2/3 2→1 + κ 2 3 LR 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 ( ) = 1 m 11 ∈ R m×m which is an extreme case of low rank settings (note that W ( ) has rank 1). Then, (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.

R 2 = 1, R F = 1, R 2→1 = √ m and R 1→1 = m,

4. CONCLUSION:

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 L 2 -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.

5. PROOF OUTLINE OF THEOREM 1:

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) ≤ 2 Rn ( G) + M 2t

n , 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 ≤ ṙ holds has high probability (which should be proven later), then it is also expected that ψ(y, f ) -ψ(y, g) has small L 2 -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 Φ( ṙ) + ṙ t n + 1+tM n , for Φ(r) := Rn ({ψ(f ) -ψ(g) | f ∈ F, g ∈ G, f -g L2 ≤ ṙ}) with probability 1 -e -t .

Since Φ( ṙ) requires the restriction f -g L2 ≤ ṙ, this quantity is much smaller than the standard Rademacher complexity Rn (ψ( F) -ψ( G)), which yields fast convergence rate.

Finally, we should bound the probability of f -g L2 ≤ ṙ. This can be bounded by utilizing the ratio type empirical process. Actually, we can show that

P sup h∈ F -G (P -P n )(h 2 ) P h 2 + r 2 * ≥ 1 2 ≤ e -t ,

for r * defined in Eq. ( 2), where

P n f := 1 n n i=1 f (z i ) and P f = E[f (Z)]. This yields that f -g 2 L2 -f -g 2 n ≤ 1 2 ( f -g 2 L2 + r 2 * )

with probability 1 -e -t and equivalently f - Theorem 5. Suppose that the empirical L 2 -distance between f and g is bounded by f -g n ≤ r2 for a fixed r > 0 almost surely. Let ṙ := 2(r 2 + r 2 * ), then, under Assumptions 1, 2, 3, there exists a universal constant C > 0 such that

g 2 L2 ≤ 2( f -g 2 n + r 2 * ). Since f -g 2 n ≤ r2 a.s., we have f -g 2 L2 ≤ 2(r 2 + r 2 * ) = ṙ2 .

i = (x i , y i ) i-th observation (x i : input, y i : output) D n = (z i ) n i=1 training data ψ(y, f (x)) loss function M L ∞ -norm bound of models B x norm bound of input • n empirical L 2 -norm ( f n := n i=1 f (z i ) 2 /n) • L2 population L 2 -norm ( f L2 := E Z∼P [f (Z) 2 ]) Ψ(f )

Ψ( f ) ≤ Ψ( f ) + 2 Rn ( G) + 2M t n + C Φ( ṙ) + ṙ t n + 1 + tM n .

with probability at least 1 -3e -t for all t ≥ 1.

Note that Ṙ(ψ( F) -ψ( G)) in the statement of Theorem 1 of the main body is replaced by refined quantity Φ( ṙ) (we can show Φ( ṙ) ≤ Ṙ(ψ( F) -ψ( G)) from the Lipschitz continuity of ψ).

Proof of Theorems 1 and 5. First, by the standard Rademacher complexity analysis, we have that

EQUATION

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 E 0 (t).

Next, we observe that

EQUATION

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 L 2 -distance between them. On the other hand, the local Rademacher complexity is characterized by the population L 2norm. To bridge this gap, we need to bound the population L 2 -distance f -g L2 between f and g in terms of the empirical L 2 -norm bound f -g n ≤ r. To do so, we also bound the local Rademacher complexity of F -G: Ṙr ( F -G). Suppose that there exists a function φ : [0, ∞) → [0, ∞) such that the the following conditions are satisfied:

Ṙ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 -P n )(h 2 ) P h 2 + r 2 ≥ 8 φ(r) r 2 + M 4t r 2 n + M 2 2t r 2 n ≤ 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 * ) r 2 * + M 4t r 2 * n + M 2 2t r 2 * n ≤ 1 2 , then it holds that P (h 2 ) ≤ 2P n (h 2 ) + 2r 2 *

uniformly over all h ∈ F -G with probability greater than 1 -e -t . We let this event as

E 1 (t). In this event, if f -g 2 n ≤ r2 , then it holds that f -g 2 L2 ≤ 2(r 2 + r 2 * ) = ṙ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 + r 2 * )). Due to the Lipschitz continuity of ψ, we have that

Var[ψ(Y, f (X)) -ψ(Y, g(X))] ≤ Var[f (X) -g(X)] ≤ f -g 2 L2 ≤ 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 L 2 ≤r

(P -P n )(ψ(Y, f (X)) -ψ(Y, g(X))) ≤ 2E sup f,g: f -g L 2 ≤r (P -P n )(ψ(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 L 2 ≤r (P -P n )(ψ(Y, f (X)) -ψ(Y, g(X))) ≤ 2E Dn, sup f,g: f -g L 2 ≤r 1 n n i=1 i [ψ(y i , f (x i )) -ψ(y i , g(x i ))] = 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 L 2 ≤r (P -P n )(ψ(Y, f (X)) -ψ(Y, g(X))) ≤ C Φ(r) + r t n + 1 + M t n .

for a universal constant C > 0 with probability at least 1 -e -t for all t > 0. We denote by this event as E 2 (t, r).

We define an event E 3 (t) = E 1 (t) ∩ E 2 (t, ṙ). Then P (E 3 (t)) ≥ 1 -2e -t for all t > 0. In this event, f -g 2 L2 ≤ ṙ2 and thus it holds that

Ψ( f ) -Ψ( g) -( Ψ( f ) -Ψ( g)) ≤ C Φ( ṙ) + ṙ t n + 1 + tM n ,

for a universal constant C > 0. Combining this and Eq. ( 6), we obtain the assertion on the event E 0 (t) ∩ E 3 (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 Φ( ṙ) ≤ Ṙ ṙ (ψ( 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 (D

n ) := sup{ f -g n | f -g L2 ≤ r, f ∈ F, g ∈ G}.

Then, it holds that

EQUATION

and

EQUATION

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):

EQUATION

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 ( F -G) is bounded by the Dudley integral as

EQUATION

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 Rn,r (ψ( F) -ψ( G)) log(n) 1 d ≤ Rn,r (ψ( F) -ψ( G)) log(n) log(nγ n ),

where Rn,r (ψ( F)-ψ( G))

:= E sup{ 1 n n i=1 i (ψ(y i , f (x i )) -ψ(y i , g(x i ))) | f ∈ F, g ∈ G, ψ(f ) -ψ(g) L2 ≤ r} . Since γn ≤ 2M

, the expectation of the right hand side with respect to D n is Ṙ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{P n h 2 | h ∈ F -G : h L2 ≤ r} ≤ r 2 + 2M φ(r).

Proof. By the contraction inequality of the complexity (Theorem 4.12 of Ledoux & Talagrand (1991) and its proof), we have

E sup{P n h 2 | h ∈ F -G : h L2 ≤ r} ≤ E sup{(P n -P )h 2 | h ∈ F -G : h L2 ≤ r} + r 2 ≤ 2E sup{ 1 n n i=1 i h(x i ) 2 | h ∈ F -G : h L2 ≤ r} + r 2

(symmetrization; Lemma 11.4 of Boucheron et al. (2013) )

≤ 2M E sup{ 1 n n i=1 i h(x i ) | h ∈ F -G : h L2 ≤ r} + r 2 (∵ contraction inequality) = 2M Ṙr ( F -G) + r 2 ≤ 2M φ(r) + r 2 . Lemma 3. Suppose that sup Dn log(N ( F, • n , /2)) + sup Dn log(N ( G, • n , /2)) ≤ S 1 + S 2 log(1/ ) + S 3 -2q

for q < 1. Then, for a universal constant C > 0 and a constant C q > 0 which depends on q < 1, it holds that

Φ(r) ≤ C max 1 n + M S 1 + S 2 log(n) n + r S 1 + S 2 log(n) n , C q 1 n + M 1-q S 3 n 1 1+q + r 1-q S 3 n .

In particular,

r 2 * ≤ C M S 1 + S 2 log(n) n + M 1-q S 3 n 1 1+q + 1 + M t 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 S 1 + S 2 log( -1 ) + S 3 -2q d ,

where C > 0 is a universal constant. The right hand side can be evaluated as

EQUATION

)

where we used Lemma 2. Hence, if the first term is larger than the second term, we have that

φ(r) ≤ C 1 n + S 1 + S 2 log(n) n r 2 + 2M φ(r) ≤ C n + C 2 M S 1 + S 2 log(n) n + Cr S 1 + S 2 log(n) n + φ(r) 2 .

Therefore, we obtain that

EQUATION

)

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 + S 3 n(1 -q) 2 (r 2 + 2M φ(r)) 1-q 2 ≤ C n + C   q c 1-q C 2 S 3 n(1 -q) 2 1 1+q + (1 -q) 2M φ(r) c + S 3 n(1 -q) 2 r 2(1-q)   .

where c > 0 is any positive real. Thus taking c sufficiently large (which depends on M, q), we conclude that

EQUATION

)

where C q 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.

B DERIVATION OF COMPRESSION BASED BOUND FOR NON-COMPRESSED NETWORKS B.1 FULL MODEL BOUND:

Here, we assume that the model F of the trained network is the full model

EQUATION

RF ). 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(R 2 ∨ 1)(max m + 1)), log(N ( G, • ∞ , )) ≤ ( L =1 m m +1 ) log( -1 ) + L( L =1 m m +1 ) log(L( R2 ∨ 1)(max m + 1)).

Hence, the condition in Lemma 3 holds for

S 1 = L =1 m m +1 , S 2 = LS 1 log(L(R 2 ∨ R2 ∨ 1)(max m + 1)

) and S 3 = 0. In this case, we can set

r 2 * = C (M + 1)(S 1 + 1 + S 2 log(n)) + M t n

for a constant C > 0.

B.2 COMPLEXITY OF A SPARSE MODEL (PROOF OF EXAMPLE 1):

Suppose that G is the model with sparse weight matrices given in Example 1. Let m = max m and B = R 2 , 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(R 2 ∨ 1)(max m + 1)) ≤ O(SL log(n) + S log( -1 )),

by Lemma 4. Hence, the Rademacher complexity is bounded as Here, we give proofs of Theorem 2 and Corollary 1 which give a generalization error 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

G ≤ CM L S n log(nL(R 2 ∨ 1)(max m + 1)) = O M L S n log(n) , by the Dudley integral, R( G) M 0 log(N ( G, • ∞, )) n d ,

EQUATION

)

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 = (s 1 , . . . , s L ), weight matrix

EQUATION

)

This can be proved as follows. Let 1) x) where W ( ) is a rank s matrix that satisfies Eqs. ( 15) and ( 16) for

EQUATION

W = W ( ) . Let f (x) = G • (W (L) η(•)) • • • • • (W ( +1) η(•)) • (W ( ) η(•)) • • • • • (W (1) x) and f 0 (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 2 B x , (W ( ) η(•)) • (W ( -1) η(•)) • • • • • (W (1) x) -(W ( ) η(•)) • (W ( -1) η(•)) • • • • • (W (1) x) ≤ W ( ) -W ( ) 2 (W ( -1) η(•)) • • • • • (W (1) x) ≤ V 0 s -α R -1 2 B x . This gives f -f ∞ ≤ L k= +1 W (k) 2 V 0 s -α R -1 2 B x ≤ R L-1 2 V 0 s -α B x .

Finally, by summing up this from = 1 to = L, we obtain Eq. ( 17).

In particular, for any > 0, by setting s = s ( ) = min{ ( /(LV 0 R L-1 2 B x )) -1/α , 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(R 2 ∨ 1)(max m + 1))] (18) ≤ 2( L =1 m )(2LV 0 R L-1 2 B x ) 1/α -1/α [log( -1 ) + 2L log(2L(R 2 ∨ 1)(max m + 1))].

As the compressed network G, we may choose G = NN(m, s, R 2 , R F ) for s = (s 1 , . . . , s L ) so that, for all f ∈ F, there exists g ∈ G satisfying

f -g ∞ ≤ (V 0 R L-1 2 B x ) L =1 s -α . Hence, we may set r2 = [(V 0 R L-1 2 B x ) 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

r 2 * ≤ C (M + 1)(S 1 + 1 + S 2 log(n)) + M t n ∨ M 2α-1 2α+1 S 3 n 2α 1+2α

, where

S 1 = L =1 s (m + m +1 ), S 2 = LS 1 log(L(R 2 ∨ 1)(max m + 1)), S 3 = ( L =1 m )(2LV 0 R L-1 2 B x ) 1/α [log(n) + 2L log(2L(R 2 ∨ 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 =1 m m +1 n

because each rank s must satisfy s ≤ min{m , m +1 }.

Finally, we observe that

Rn ( G) ≤CM L L =1 s (m + m +1 ) n log(nL(R 2 ∨ 1)(max m + 1)),

by Lemma 5 for G = NN(m, s, R 2 , R F ) 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 , LV 0 R L-1 2 B x 1/α }.

B.4 IMPROVED BOUND WITH LIPSCHITZ CONTINUITY CONSTRAINT:

In the generalization error bound of Theorem 2 and Corollary 1, there appears R L 2 . Even though R 2 can be much smaller than R F , the exponential dependency R L 2 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 1) x) be the input to the -th layer and

f = G • (W (L) η(•)) • • • • • (W (1) x), let φ (x) = η • (W ( -1) η(•))•• • ••(W (

M , (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κ 2 L) and for any ,

EQUATION

EQUATION

n ) ∈ R n .

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 κ ≤ R L 2 , 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 R 2 as in the following corollary. Corollary 2. Under Assumptions 4 and 6, it holds that

Ψ( f ) ≤ Ψ( f ) + C M 1-1/2α L ( L =1 m )(2LV0κ 2 Bx) 1/α n log(n) + M 2α-1 2α+1 A 2 2α 2α+1 + 1 + tM n for A 2 = L ( L =1 m )(2LV0κ 2 Bx) 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 R L 2 is replaced by the Lipschitz continuity κ 2 .

Proof of Corollary 2. Suppose that

EQUATION

then we show that Eq. ( 17) can be replaced by

EQUATION

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 C B := 2κB x . We will show that φ k -φ k n ≤ 2κV 0 C B   k j=1 s -α j   , φ k n ≤ C B ,

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,

M k, • φ k -M k-1, φ k-1 n ≤ κ( φ k -η(W (k) φ k-1 ) n + τ η(W (k) φ k-1 ) -φ k n ) ≤ κ(V 0 s -α k φ k-1 n + τ κ φ k-1 -φ k-1 n ) ≤ κ   V 0 s -α k C B + τ κ2κV 0 C B j≤k-1 s -α j   (by induction) ≤ κV 0 C B   s -α k + 1 L k-1 j=1 s -α j 

 (by the assumption of τ ).

Note that the term s -α k can be replaced by 0 if s k = min{m k , m k+1 } which corresponds to the full rank setting (W (k) = W (k) ). Therefore, we have that

φ -φ n ≤ j=1 M j, • φ j -M j-1, • φ j-1 n ≤ 2κV 0 C B k=1 s -α k .

Under the setting (19), this gives that

φ -φ n ≤ C B /2.

Finally, noting that φ n ≤ C B /2, we have

φ n ≤ C B .

This concludes the inductive reasoning.

Finally, noting that f = φ L and f = φ L , we have Eq. (20).

B.5 NEAR LOW RANK CONDITION ON THE COVARIANCE MATRIX (PROOF OF THEOREM 3 AND THEOREM 4)

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) ) -1 k=1 where each W (k) has size m k+1 × m k (here, m k ≤ m k 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 r 2 = φ -φ 2 n and Σ ( ) := 1 n n i=1 φ (x i )(φ (x i ))

. For a given matrix Σ and a precision r 2 > 0, the degrees of freedom3 are defined as

EQUATION

)

Since the degrees of freedom are monotonically increasing with respect to each σ j (Σ), we can see that

N (r 2 , Σ) ≥ N (r 2 , Σ ) if Σ Σ . Let 4 m = 5N (r 2 , Σ ( ) ) log(80N (r 2 , Σ ( ) )) ,

then Proposition 1 tells that there exits a matrix Â ∈ m × m and J ⊂ {1, . . . , m } m such that

EQUATION

)

for any w ∈ R m5 , and the norm of Â is bounded as

Â 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 r 2 = φ -φ 2 n . Let s ≤ m. For any matrix U ∈ R m ×s such that

U U = I s , Tr[U Σ ( ) U ] = P n [φ U U φ ] ≤ 2{P n [φ U U φ ] + P n [(φ -φ ) U U (φ - φ )]

} by the Cauchy-Schwartz inequality. Here, let U be the matrix that gives

P n [φ U U φ ] = m j=m -s+1 σ j ( Σ ( ) ) = inf U :U U =Is P n [φ U U φ ], then by noticing P n [(φ -φ ) U U (φ - φ )] ≤ P n φ -φ 2 ≤ r 2 , we obtain that P n [φ U U φ ] ≤ 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   . Now, let ṁ := min{j ∈ {1, . . . , m } | μ( ) j ≤ r 2 } (if μ( ) m > r 2 , then we set ṁ = m ). Then, N (r 2 , Σ ( ) ) = m j=1 σ j (Σ ( ) ) σ j (Σ ( ) ) + r 2 ≤ ṁ + j> ṁ σ j (Σ ( ) ) σ j (Σ ( ) ) + r 2 ≤ ṁ + j> ṁ σ j (Σ ( ) ) r 2 ≤ ṁ + 2 r 2   r 2 + j> ṁ σ j ( Σ ( ) )   ≤ ṁ + 2 r 2 r 2 + U 0 ṁ1-β β -1 ≤ ṁ + 2 r 2 r 2 + ṁ r 2 β -1 ≤ ṁ + 2 r 2 r 2 + ṁ r 2 β -1 = β + 1 β -1 ṁ + 2 r 2 r 2 . Now, let r 2 = 1 4 r2 , then N (r 2 , Σ ( ) ) ≤ β + 1 β -1 ṁ + 8 r 2 r2 .

We define the right hand side as m :

m := β + 1 β -1 ṁ + 8 r 2 r2 .

We have, by Eq. ( 22),

m +1 j=1 η(W ( ) j,: φ ) -η(W ( ) j,: Â φ ,J ) 2 n ≤ 4 m +1 j=1 W ( ) j,: 2 r 2 ≤ 4R 2 F × 1 4 r2 = R 2 F r2 .

By the induction assumption, we also have that

η(W ( ) φ ) -φ +1 2 n = η(W ( ) φ ) -η(W ( ) φ ) 2 n ≤ W ( ) 2 2 r 2 ≤ R 2 2 r 2 .

Combining these inequalities, if we define

φ +1 = η(W ( ) Â φ ,J (x)),

and set W ( ) = W ( ) Â and reset W ( -1) ← W ( -1) J ,:

, then it holds that

φ +1 -φ +1 n ≤ r +1

where we let r +1 = R 2 r + R F r . Letting r 0 = 0, by an induction argument, we obtain

r +1 ≤ k=1 R ( -k) 2 R F rk .

Finally, we obtain

f -f 2 n ≤ r 2 L ≤ L k=1 R (L-k) 2 R F r 2 ,

for a compressed network f that has width m = (m 1 , . . . , m L ) with parameters W ( ) = W ( ) J +1 ,:

Â . Note that

W ( ) 2 ≤ W ( ) J +1 ,: 2 Â 2 ≤ R 2 20 3 m , W ( ) F ≤ W ( ) J +1 ,: F Â 2 ≤ R F 20 3 m .

Therefore, if we set G = NN(m , 20 3 max m R 2 , 20 3 max m R F ), then there exists g ∈ G such that f -g n ≤ r where r2 = r 2 L . Moreover, applying Lemma 5 to G and the Dudley integral yields

R( G) ≤ CM L L =1 m m +1 n log(nL(R 2 ∨ 1)(max m + 1) 2 ).

This gives the assertion of Theorem 3.

Here, we consider a situation where R 2

F r2 = c 2 0 r 2 R 2

2 for some constant c 0 > 0. Then it holds that

r +1 = R 2 1 + c 2 0 r = R 2 k=1 1 + c 2 0 k r 1 ≤ R 2 exp c 0 (2 √ -1) r 1 .

Therefore, by setting

C L := (1 ∨ R 2 ) L exp c 0 (2 √ L -1)

, it holds that r ≤ C L r 1 for = 1, . . . , L, in particular, we have r ≤ C L r 1 .

In this situation, the degrees of freedom are bounded by

N (r 2 , Σ ( ) ) ≤ m = β + 1 β -1 ṁ + 8 R 2 F c 2 0 R 2 2 .

Next, we bound ṁ . To do so, we should bound r from below. Note that

r = c 0 R 2 R F 1 √ r = c 0 R 2 R F 1 √ R -1 2 -1 k=1 1 + c 2 0 k r 1 ≥ c 0 R 2 R F 1 √ -1 k=1 1 + c 2 0 k r 1 ≥ c 0 R 2 R F 1 √ 1 + -1 k=1 c 2 0 k r 1 ≥ c 0 R 2 R F 1 √ 1 + 2c 0 ( √ -1) r 1 ≥ c 0 R 2 R F 1 √ + 2c 0 (1 - 1 √ ) r 1 .

Hence,

ṁ ≤ (r 2 /(4U 0 )) -1/β ≤ (4U 0 ) 1/β c 0 R 2 R F 1 √ + 2c 0 (1 - 1 √ ) r 1 -2/β ≤ (4U 0 ) 1/β R F c 0 R 2 2/β 1 2 ∧ c 0 -2/β r -2/β 1 ≤ 4U 0 R 2 F (0.5 ∧ c 0 ) 2 c 2 0 R 2 2 1/β r -2/β 1

.

By Lemma 3, we can evaluate r 2 * for F satisfying Assumption 4 as

r 2 * ≤ C (M + 1)(S 1 + 1 + S 2 log(n)) + M t n ∨ M 2α-1 2α+1 S 3 n 2α 1+2α

, where

S 1 = L =1 m m +1 , S 2 = LS 1 log(L(R 2 ∨ 1)(max m + 1) 2 ) = O L L =1 m m +1 log(n) , S 3 = ( L =1 m )(2LV 0 R L-1 2 B x ) 1/α [log(n) + 2L log(2L(R 2 ∨ 1)(max m + 1) 2 )] = O L( L =1 m )(2LV 0 R L-1 2 B x ) 1/α log(n) ,

Then, the overall generalization error is upper bounded by

Ψ( f ) ≤ Ψ( f ) + C   r 2 * + S 3 n r2(1-1/2α) + (M 2 + r2 )L L =1 m m +1 n log(n) + 1 + M t n   ,

with probability 1-3e -t for all t ≥ 1. By letting Q 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 )(C L r 1 ) 2(1-1/2α) + C M L L =1 [ ṁ + R 2 F /(c 2 0 R 2 2 )] 2 n log(n) 3 ≤ Q L,α,n ( L =1 m )(C L r 1 ) 2(1-1/2α) + 2C M L L 4U0R 2 F (0.5∧c0) 2 c 2 0 (1∧R2) 2L 2/β r -4/β 1 + L 3 R 4 F /R 4 2 n log(n) 3 .

Hence, by setting

C L r 1 = L =1 m L - 1 4/β+2(1-1/2α)

which balances the first and the second terms, then r ≤ C L r 1 ≤ 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 =1 m ) 4/β 4/β+2(1-1/2α) (C L ) 4/β 4U0R 2 F (0.5∧c0) 2 c 2 0 (1∧R2) 2L 2/β n log(n) 3 + CM R 2 F R 2 2 L 4 n log(n) 3 .

Finally, by setting c 0 = 1/4, we obtain the assertion for

Q L =   4U 0 R 2 F (1 ∨ R 2 ) L exp c 0 (2 √ L -1) (0.5 ∧ c 0 ) 2 c 2 0 (1 ∧ R 2 ) 2L   2/β ≤   4U 0 R 2 F (1 ∨ R 2 ) L exp 1 4 (2 √ L -1) (0.25) 4 (1 ∧ R 2 ) 2L   2/β .

This gives Theorem 4.

B.6 IMPROVED BOUND OF THEOREM 4 WITH LIPSCHITZ CONTINUITY CONSTRAINT:

Here, we again note that there appears R L 2 in P L and Q L 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 P L and Q L :

P L = (2LV 0 κ 2 B x ) 1/α , Q L = 4U0R 2 F exp( 1 4 (2 √ L-1)) (0.25) 4 2/β , except that the term M R 2 F L 2 R 2 2 log(n) 3 n is replaced by M κ 2 R 2 F L 2 log(n) 3 n : Ψ( f ) ≤ Ψ( f ) + C M [PL ∨ QL]L 1+ β 4α (2α-1) +β n L =1 m 4/β 4/β+2(1-1/2α) log(n) 3 + M 2α-1 2α+1 LP L L =1 m n log(n) 2α 2α+1 + M κ 2 R 2 F L 2 log(n) 3 n + 1+M t n .

Proof of Corollary 3. To show Corollary 3, we set

r = 1 √ -1 k=1 1 + c 2 0 k r 1 R F ,

where c 0 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 + c 2 0 j   r 1 .

Then, through a cumbersome calculation, we have that

r r ≤ C κR F c 0 √ ,

for a universal constant C. Moreover, we can show that r can be bounded as

r ≤ 2κ e c0(2 √ +1-1) -e c0 c 0 r 1 .

This also gives

EQUATION

)), we can apply the same argument as in the proof of Corollary 2. Indeed, we can show

ṁ 4U 0 R 2 F (0.5 ∧ c 0 ) 2 c 2 0 κ 2 1/β , m = β + 1 β -1 ṁ + C 2 R 2 F c 2 0 r -2/β 1 .

From above argument, if we set G = NN(m , 20 3 max m R 2 , 20 3 max m R F ), then there exists g ∈ G such that f -g n ≤ r where r2 = r 2 L . Moreover, we can show

r 2 * ≤ C (M + 1)(S 1 + 1 + S 2 log(n)) + M t n ∨ M 2α-1 2α+1 S 3 n 2α 1+2α

, where

S 1 = L =1 m m +1 , S 2 = LS 1 log(L(R 2 ∨ 1)(max m + 1) 2 ) = O L L =1 m m +1 log(n) , S 3 = ( L =1 m )(2LV 0 κ 2 B x ) 1/α [log(n) + 2L log(2L(R 2 ∨ 1)(max m + 1) 2 )] = O L( L =1 m )(2LV 0 κ 2 B x ) 1/α log(n) .

Here, to evaluate S 3 , 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).

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 = [δ -1 L(B ∨ 1) L-1 (m + 1) 2L ] S ,

which gives the assertion.

Lemma 5 (Covering number evaluation). Let NN(m, R 2 , R F ) be the set of neural networks with depth m(m 1 , . .

. , m L ), W ( ) ∞ ≤ R 2 and W ( ) F ≤ R F . The covering number of NN(m, R 2 , R F ) can be bounded by log N (NN(m, R 2 , R F ), • ∞ , δ) ≤ ( L =1 m m +1 ) log(δ -1 L(R 2 ∨ 1) L-1 (max m + 1) L ) ≤ ( L =1 m m +1 ) log(δ -1 ) + L( L =1 m m +1 ) log(L(R 2 ∨ 1)(max m + 1)).

Moreover, the set of networks with low rank weight matrices, NN(m, s, R 2 , R F ), has the following covering number bound: 

log N (NN(m, s, R 2 , R F ), • ∞ , δ) ≤ L =1 s (m + m +1 ) log(δ -1 L(R 2 ∨ 1) 2L-1 (max m + 1) 2L .

C.2 COMPRESSION ERROR BOUND FOR ONE LAYER:

The following proposition was shown by Bach (2017) ; Suzuki et al. (2018) . Let Σ I,I ∈ R K×H for integers K, H ∈ N and a matrix Σ I,I ∈ R K×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 = (U j,l ) j,l is the orthogonal matrix that diagonalizes Σ, that is, Σ = U diag (μ 1 , . . . , μm ) U for μj ≥ 0 (j = 1, . . . , m ). Define

EQUATION

For λ > 0, if m ≥ 5 N (λ) log(80 N (λ)), then there exist v 1 , . . . , v m ∈ {1, . . . , m } such that, for every α

∈ R m , inf β∈R m      α η( F -1 (•)) - m j=1 β j η( F -1 (•)) vj 2 n + mλ β 2 τ      ≤ 4λα Σ( Σ + λI) -1 α, (24)

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 ( ) ) ≥ ν × max j σ j (K ( ) )} and ṁ := #{j ∈ [m ] | σ j ( Σ ( ) ) ≥ ν × max j σ j ( Σ ( ) )} (which corresponds to setting r2 = 4ν × max j σ j ( Σ ( ) )). Table 4 sumthe effective ranks ṁ , 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 ṁ +1 ṁ n

(note that m is essentially controlled by ṁ ). Hence, we employ ṁ +1 × ṁ as the intrinsic dimensionality of each fully connected layer. As for a convolution layer, we employ ṁ +1 ṁ k 2 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 k 2 + m +1 s . 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 ṁ 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.

:

In this paper, • denotes the Euclidean norm: u = i u

i .

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.

The definition is not dependent on , but to make it clear that we are dealing with the -th layer, we use the notation N .

x is the smallest integer that is not less than x ∈ R.

For a vector x ∈ R m and index set J ∈ {1, . . . , m} l , xJ is the vector corresponding to the index set J, that is, xJ = (xj)j∈J .

Figures and Tables:

(ii) Norm-based bound: Golowich et al. (2018) showed the norm based bound which is given as Rn (F) = O LR L F n . However, this is exponentially dependent on the depth as R L F resulting in quite loose bound. Neyshabur et al. (2017) showed a norm based bound of Rn

and thus their bounds are O( m/n) and O( (m + m 2 )/n) respectively. However, β and α in our bound m

( ) m = (m 1 , . . . , m L ) list of widths of networks m = (m 1 , m 2 , . . . , m L ) list of widths of compressed networks s = (s 1 , . . . , s L ) list of ranks of the weight matrices of compressed networks F = NN(m, R 2 , R F ) the whole set of networks with width m F set of trained networks G set of compressed networks f ∈ F trained network g ∈ G compressed network μ( ) j an upper bound of the j-th largest eigenvalue of the covariance matrix in the -th layer of f α decreasing rate of the eigenvalues of W ( ) β decreasing rate of the eigenvalues of Σ ( )

Proof of Lemma 5. Let B = R 2 , m = max m , and S = L =1 m m +1 , then we can see that NN(m, R 2 , R F ) 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, R 2 , R F ) 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.

Figure 1: Eigenvalue distribution of the covariance matrices

Figure 2: Singular-value distribution of the weight matrices

Comparison of each generalization error to our bound. R F is the Frobenius norm of the weight matrix, R 2 is the operator norm of the weight matrix, R p→q is the (p, q) matrix norm, L is the depth, m is the maximum of the width, n is the sample size. Rn and Ṙr represent the Rademacher complexity and local Rademacher complexity respectively. κ is a Lipschitz constant between layers.

Table content: <table/>



Table content: <table><tr><td>: Notation list</td></tr></table>

where C is a universal constant.

Table content: <table><tr><td>B.3 NEAR LOW RANK CONDITION ON THE WEIGHT MATRIX (PROOF OF THEOREM 2 AND</td></tr><tr><td>COROLLARY 1 )</td></tr></table>

The effective ranks ṁ and s in each layer for each threshold ν. "In/Out" indicates the channel sizes of the input and output. layer In/Out Cov ( ṁ ) Weight (s ) ν : 10 -1 10 -2 10 -3 ν : 10 -1 10 -2 10 -3

Table content: <table><tr><td>c0</td><td>3/64</td><td>3</td><td>3</td><td>3</td><td>9</td><td>16</td><td>19</td></tr><tr><td>c1</td><td>64/64</td><td>5</td><td>21</td><td>51</td><td>26</td><td>62</td><td>64</td></tr><tr><td>c2</td><td>64/128</td><td>5</td><td>33</td><td>64</td><td>37</td><td>110</td><td>128</td></tr><tr><td>c3</td><td>128/128</td><td>9</td><td>76</td><td>128</td><td>50</td><td>128</td><td>128</td></tr><tr><td>c4</td><td>128/256</td><td>11</td><td>110</td><td>128</td><td>102</td><td>255</td><td>256</td></tr><tr><td>c5</td><td>256/256</td><td>13</td><td>200</td><td>256</td><td>93</td><td>256</td><td>256</td></tr><tr><td>c6</td><td>256/256</td><td>17</td><td>219</td><td>256</td><td>55</td><td>230</td><td>256</td></tr><tr><td>c7</td><td>256/256</td><td>11</td><td>110</td><td>253</td><td>37</td><td>175</td><td>252</td></tr><tr><td>c8</td><td>256/512</td><td>10</td><td>35</td><td>129</td><td>30</td><td>122</td><td>349</td></tr><tr><td>c9</td><td>512/512</td><td>6</td><td>33</td><td>79</td><td>16</td><td>60</td><td>217</td></tr><tr><td>c10</td><td>512/512</td><td>3</td><td>15</td><td>41</td><td>16</td><td>42</td><td>127</td></tr><tr><td>c11</td><td>512/512</td><td>2</td><td>12</td><td>23</td><td>11</td><td>39</td><td>129</td></tr><tr><td>c12</td><td>512/512</td><td>2</td><td>7</td><td>16</td><td>7</td><td>18</td><td>46</td></tr><tr><td>c13</td><td>512/512</td><td>3</td><td>6</td><td>16</td><td>9</td><td>22</td><td>46</td></tr><tr><td>c14</td><td>512/512</td><td>3</td><td>7</td><td>18</td><td>16</td><td>38</td><td>59</td></tr><tr><td>c15</td><td>512/512</td><td>4</td><td>14</td><td>28</td><td>36</td><td>51</td><td>92</td></tr><tr><td>l16</td><td>512/4096</td><td>5</td><td>10</td><td>11</td><td>11</td><td>21</td><td>49</td></tr><tr><td>l17</td><td>4096/4096</td><td>7</td><td>10</td><td>11</td><td>10</td><td>49</td><td>990</td></tr><tr><td>l18</td><td>4096/10</td><td>6</td><td>10</td><td>10</td><td>9</td><td>9</td><td>9</td></tr></table>

The intrinsic dimensionality in each layer for each threshold ν. Here again, "In/Out" indicates the channel sizes of the input and output. "Orig" indicates the number of parameters (m +1 m × filter size) in each layer.

Table content: <table><tr><td colspan="2">layer In/Out</td><td>Orig</td><td>Cov</td><td/><td/><td>Weight</td><td/><td/></tr><tr><td/><td/><td/><td>ν : 10 -1</td><td>10 -2</td><td colspan="2">10 -3 ν : 10 -1</td><td>10 -2</td><td>10 -3</td></tr><tr><td>c0</td><td>3/64</td><td>1,728</td><td>135</td><td>567</td><td>1,377</td><td>910</td><td>910</td><td>910</td></tr><tr><td>c1</td><td>64/64</td><td>36,864</td><td>225</td><td>6,237</td><td>29,376</td><td>1,920</td><td>1,920</td><td>1,920</td></tr><tr><td>c2</td><td>64/128</td><td>73,728</td><td>405</td><td>22,572</td><td>73,728</td><td>6,336</td><td>11,264</td><td>13,376</td></tr><tr><td>c3</td><td>128/128</td><td>147,456</td><td>891</td><td colspan="2">75,240 147,456</td><td>33,280</td><td>79,360</td><td>81,920</td></tr><tr><td>c4</td><td>128/256</td><td>294,912</td><td colspan="3">1,287 198,000 294,912</td><td colspan="2">52,096 154,880</td><td>180,224</td></tr><tr><td>c5</td><td>256/256</td><td>589,824</td><td colspan="5">1,989 394,200 589,824 128,000 327,680</td><td>327,680</td></tr><tr><td>c6</td><td>256/256</td><td>589,824</td><td colspan="5">1,683 216,810 582,912 261,120 652,800</td><td>655,360</td></tr><tr><td>c7</td><td>256/256</td><td>589,824</td><td>990</td><td colspan="4">34,650 293,733 238,080 655,360</td><td>655,360</td></tr><tr><td>c8</td><td>256/512</td><td>1,179,648</td><td>540</td><td>10,395</td><td colspan="3">91,719 154,880 647,680</td><td>720,896</td></tr><tr><td>c9</td><td>512/512</td><td>2,359,296</td><td>162</td><td>4,455</td><td colspan="4">29,151 189,440 896,000 1,290,240</td></tr><tr><td>c10</td><td>512/512</td><td>2,359,296</td><td>54</td><td>1,620</td><td colspan="4">8,487 153,600 624,640 1,786,880</td></tr><tr><td>c11</td><td>512/512</td><td>2,359,296</td><td>36</td><td>756</td><td>3,312</td><td colspan="3">81,920 307,200 1,111,040</td></tr><tr><td>c12</td><td>512/512</td><td>2,359,296</td><td>54</td><td>378</td><td>2,304</td><td colspan="2">81,920 215,040</td><td>650,240</td></tr><tr><td>c13</td><td>512/512</td><td>2,359,296</td><td>81</td><td>378</td><td>2,592</td><td colspan="2">56,320 199,680</td><td>660,480</td></tr><tr><td>c14</td><td>512/512</td><td>2,359,296</td><td>108</td><td>882</td><td>4,536</td><td>35,840</td><td>92,160</td><td>235,520</td></tr><tr><td>c15</td><td>512/512</td><td>2,359,296</td><td>180</td><td>1,260</td><td>2,772</td><td colspan="2">46,080 112,640</td><td>235,520</td></tr><tr><td>l16</td><td>512/4096</td><td>2,097,152</td><td>35</td><td>100</td><td>121</td><td colspan="2">73,728 175,104</td><td>271,872</td></tr><tr><td>l17</td><td colspan="2">4096/4096 16,777,216</td><td>42</td><td>100</td><td colspan="3">110 294,912 417,792</td><td>753,664</td></tr><tr><td>l18</td><td>4096/10</td><td>40,960</td><td>42</td><td>90</td><td>90</td><td>45,166</td><td>86,226</td><td>201,194</td></tr></table>

Comparison of the intrinsic dimensionality of our analysis and that inArora et al. (2018).

Table content: <table><tr><td colspan="2">layer In/Out</td><td>Orig</td><td colspan="2">Arora et al. (2018) Cov</td><td/><td/></tr><tr><td/><td/><td/><td/><td>ν : 10 -1</td><td>10 -2</td><td>10 -3</td></tr><tr><td>c0</td><td>3/64</td><td>1,728</td><td>1,645</td><td>135</td><td>567</td><td>1,377</td></tr><tr><td>c3</td><td>128/128</td><td>147,456</td><td>644,654</td><td>891</td><td colspan="2">75,240 147,456</td></tr><tr><td>c5</td><td>256/256</td><td>589,824</td><td>3,457,882</td><td colspan="3">1,989 394,200 589,824</td></tr><tr><td>c8</td><td colspan="2">256/512 1,179,648</td><td>36,920</td><td>540</td><td>10,395</td><td>91,719</td></tr><tr><td>c11</td><td colspan="2">512/512 2,359,296</td><td>22,735</td><td>36</td><td>756</td><td>3,312</td></tr><tr><td>c14</td><td colspan="2">512/512 2,359,296</td><td>26,584</td><td>108</td><td>882</td><td>4,536</td></tr></table>

Peer review (iclr2020):
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. Overall, 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). Citation issues: In 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? Then 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). In 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). Could 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. In 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. Other minor comments: In section 2, marginal distributions over x and y are introduced. Are those used in the main text? Is 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. In Section 3, “The main difference from the…” paragraph, there is Psi(dot r) used. Where is that defined?