Title: ON TIGHTER GENERALIZATION BOUNDS FOR DEEP NEURAL NETWORKS: CNNS, RESNETS, AND BEYOND

Abstract: We propose a generalization error bound for a general family of deep neural networks based on the depth and width of the networks, as well as the spectral norm of weight matrices. Through introducing a novel characterization of the Lipschitz properties of neural network family, we achieve a tighter generalization error bound. We further obtain a result that is free of linear dependence on norms for bounded losses. Besides the general deep neural networks, our results can be applied to derive new bounds for several popular architectures, including convolutional neural networks (CNNs), residual networks (ResNets), and hyperspherical networks (SphereNets). When achieving same generalization errors with previous arts, our bounds allow for the choice of much larger parameter spaces of weight matrices, inducing potentially stronger expressive ability for neural networks.

1. INTRODUCTION:

We aim to provide a theoretical justification for the enormous success of deep neural networks (DNNs) in real world applications (He et al., 2016; Collobert et al., 2011; Goodfellow et al., 2016) . In particular, our paper focuses on the generalization performance of a general class of DNNs. The generalization bound is a powerful tool to characterize the predictive performance of a class of learning models for unseen data. Early studies investigate the generalization ability of shallow neural networks with no more than one hidden layer (Bartlett, 1998; Anthony & Bartlett, 2009) . More recently, studies on the generalization bounds of deep neural networks have received increasing attention (Dinh et al., 2017; Bartlett et al., 2017; Golowich et al., 2017; Neyshabur et al., 2015; 2017) . There are two major questions of our interest in these analysis of the generalization bounds:

(Q1) Can we establish tighter generalization error bounds for deep neural networks in terms of the network dimensions and structure of the weight matrices? (Q2) Can we develop generalization bounds for neural networks with special architectures? For (Q1), (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2017; Golowich et al., 2017) have established results that characterize the generalization bounds in terms of the depth D and width p of networks and norms of rank-r weight matrices. For example, Neyshabur et al. (2015) provide an exponential bound on D based on the Frobenius norm W d F , where W d is the weight matrix of d-th layer; Bartlett et al. (2017) ; Neyshabur et al. (2017) provide a polynomial bound on p and D based on W d 2 (spectral norm) and W d 2,1 (sum of the Euclidean norms for all rows of W d ). Golowich et al. (2017) provide a nearly size independent bound based on W d F . Nevertheless, the generalization bound depends on other than the spectral norms of the weight matrices may be too loose. In specific, W d F ( W d 2,1 ) is in general √ r (r) times larger than W d 2 . Given m training data points and suppose W d 2 = 1 for ease of discussion, Bartlett et al. (2017) and Neyshabur et al. (2017) demonstrate generalization error bounds as O( D 3 pr/m), and Golowich et al. (2017) achieve a bound O(r D/2 min(m -1/4 , D/m)), where O(•) represents the rate by ignoring logarithmic factors. In comparison, we show a tighter generalization error bound as O( Dpr/m), which is significantly smaller than existing results and achieved based on a new Lipschitz analysis for DNNs in terms of both the input and weight matrices. We notice that some recent results characterize the generalization bound in more structured ways, e.g., by considering specific error-resilience parameters (Arora et al., 2018) , which can achieve empirically improved Table 1 : Comparison of existing results with ours on norm based generalization error bounds for DNNs. For ease of illustration, we suppose the upper bound of input norm R and the Lipschitz constant 1 γ of the class of loss functions g γ are generic constants. We use B d,2 , B d,F , and B d,2→1 as the upper bounds of W d 2 , W d F , and W d 2,1 respectively. For notational convenience, we suppose the width p d = p for all layers d = 1, . . . , D. We further show the results when W generalization bounds than existing ones based on the norms of weight matrices. However, it is not clear how the weight matrices explicitly control these parameters, which makes the results less interpretable. Thus, we do not compare with these types of results. We summarize the comparison between existing norm based generalization bounds with our results in Table 1 , as well as the results when W d 2 = 1 for more explicit comparison in terms of the network sizes (i.e, depth and width).

For (Q2), we consider several widely used architectures to demonstrate, including convolutional neural networks (CNNs) (Krizhevsky et al., 2012) , residual networks (ResNets) (He et al., 2016) , and hyperspherical networks (SphereNets) (Liu et al., 2017b) . By taking their structures of weight matrices into consideration, we provide tight characterization of their resulting capacities. In particular, we consider orthogonal filters and normalized weight matrices, which show good performance in both optimization and generalization (Mishkin & Matas, 2015; Xie et al., 2017) . This is closely related with normalization frameworks, e.g., batch normalization (Ioffe & Szegedy, 2015) and layer normalization (Ba et al., 2016) , which have achieved great empirical performance (Liu et al., 2017a; He et al., 2016) . Take CNNs as an example. By incorporating the orthogonal structure of convolutional filters, we achieve 

O k s D 2 √ Dk 2 / √ m ,

1 4 √ m , D m (rank(W d ) = p in CNNs),

where k is the filter size that satisfies k p and s is stride size that is usually of the same order with k; see Section 4.1 for details. Here we achieve stronger results in terms of both depth D and width p for CNNs, where our bound only depend on k rather than p. Some recent result achieved results that is free of the linear dependence on the weight matrix norms by considering networks with bounded outputs (Zhou & Feng, 2018) . We can achieve similar results using bounded loss functions as discussed in Section 3.2, but do not restrict ourselves to this scenario in general. Analogous improvement is also attained for ResNets and SphereNets. In addition, we consider some widely used operations for width expansion and reduction, e.g., padding and pooling, and show that they do not increase the generalization bound. Further numerical evaluation is provided for quantitative comparison in Section 4.5.

Our tighter bounds result in potentially stronger expressive power, hence higher training/testing accuracy for the DNNs. In particular, when achieving the same order of generalization errors, we allow the choice of a larger parameter space with deeper/wider networks and larger matrix spectral norms. We further show numerically that a larger parameter space can lead to better empirical performance. Quantitative analysis for the expressive power of DNNs is of great interest on its own, which includes (but not limited to) studying how well DNNs can approximate general class of functions and distributions (Cybenko, 1989; Hornik et al., 1989; Funahashi, 1989; Barron, 1993; 1994; Lee et al., 2017; Petersen & Voigtlaender, 2017; Hanin & Sellke, 2017) , and quantifying the computation hardness of learning neural networks; see e.g., Shamir (2016) ; Eldan & Shamir (2016) ; Song et al. (2017) . We defer our investigation toward this to future efforts.

Notation. Given an integer n > 0, we define [n] = {1, . . . , n}. Given a matrix A ∈ R n×m , we denote A as a generic norm, A 2 as the spectral norm, A F as the Frobenius norm, and A 2,1 = n i=1 A i * 2 . We use the standard notations O (•), Θ (•), and Ω (•) to denote limiting behaviors ignoring constants, and O (•), Θ (•) and Ω (•) to further ignore logarithmic factors.

2. PRELIMINARIES:

We provide a brief description of the DNNs. Given an input x ∈ R p0 , the output of a D-layer network is defined as

f D f (W D , x) = f W D (• • • f W1 (x)) ∈ R p D , where f W d (y) = σ d (W d • y) : R p d-1 → R p d with

an entry-wise activation function σ d (•). We specify σ d as the rectified linear unit (ReLU) activation (Nair & Hinton, 2010) for ease of discussion. The extension to more general activations, e.g., Lipschitz continuous functions, is straightforward. Then we denote DNNs with bounded weight matrices

EQUATION

where x ∈ R p0 is an input, and {B d } are real positive constants. We will specify the norm Given a loss function g(•, •), we denote a class of loss functions measuring the discrepancy between a DNN's output f (W D , x) and the corresponding observation y ∈ Y m for a given input x ∈ X m as

G F D, • = g(f (W D , x) , y) ∈ R | x ∈ X m , y ∈ Y m , f (•, •) ∈ F D, • ,

where the sets of bounded inputs X m and the corresponding observations

EQUATION

where {±1} m ∈ R m is the set of vectors only containing entries +1 and -1, and ∈ R m is a vector with Rademacher entries, i.e., i = +1 or -1 with equal probabilities.

Take the classification as an example. For multi-class classification, suppose p D = N class is the number of classes. Consider g with bounded outputs, namely the ramp risk. Specifically, for an input x belonging to class y ∈ [N class ], we denote ν = (f (W D , x)) y -max i =y (f (W D , x)) i . For a given real value γ > 0, the class of ramp risk functions with parameter γ is

EQUATION

nience, we denote g γ (f (W D , x) , y) as g γ (f (W D , x)) (or g γ ) in the rest of the paper.

Then the generalization error bound for PAC learning (Bartlett et al., 2017) (Lemma 3.1) states the following. Given any real δ ∈ (0, 1) and g γ , with probability at least 1 -δ, we have that for any f (•, •) ∈ F D, • , the generalization error is upper bounded with respect to (w.r.t.) the ERC satisfies

E [g γ (f (W D , x))] -1 m m i=1 g γ (f (W D , x i )) ≤ 2R m G γ F D, • + 3 log( 2 δ ) 2m .

(4)

The right hand side of (4) is viewed as a guaranteed error bound for the gap between the testing and the empirical training performance. Since the ERC is generally the dominating term in (4), a small R m is desired for DNNs given the loss function g γ . Analogous results hold for regression tasks; see e.g., Kearns & Vazirani (1994) ; Mohri et al. (2012) for details.

3. GENERALIZATION ERROR BOUND FOR DNNS:

We introduce some additional notations first. Given any two layers i, j ∈ [D] and input x, we denote J x i:j as the Jacobian from layer i to layer j, i.e., f

Wj (• • • f Wi (x)) = J x i:j • x.

For convenience, we denote f Wi (x) = J x i,i • x when i = j and denote J x i:j = I when i > j. Next, we denote B Jac,x i:j,2 as an upper bound of the norm of Jacobian for input x over the parameter, i.e., sup W D J x i,i 2 ≤ B Jac,x i:j,2 .

3.1. A TIGHTER ERC BOUND FOR DNNS:

We first provide the ERC bound for the class of DNNs defined in (1) and Lipschitz loss functions in the following theorem. The proof is provided in Appendix B. Theorem 1. Let g γ be a 1 γ -Lipschitz loss function and F D, • 2 be the class of DNNs defined in (1),

EQUATION

:D,2 , and

C Net = B Jac \d,2 •R √ Dm/r•max d B d,2 sup f ∈F D, • 2 ,x∈Xm gγ (f (W D ,x)) . Then the ERC satisfies R m G γ F D, • 2 = O R• D d=1 B d,2 √ Dpr log C Net γ √ m .

(5)

Remark 1. Note that C Net depends on the norm of Jacobian, which is significantly smaller than the product of matrix norms that is exponential on D in general. For example, when we obtain the network from stochastic gradient descent using randomly initialized weights, then B 

O Π D d=1 B d,F • min D m , m -1 4 • log 3 4 (m) log (C ) , where C = R•Π D d=1 B d,F sup x∈Xm f (W D ,x) 2 .

This has a tighter dependence on network sizes. Nevertheless, W d F is generally √ r times larger than W d 2 , which results in an exponential dependence p D/2 compared with the bound based on the spectral norm. Moreover, log(C ) is linear on D except that the stable ranks W d F / W d 2 across all layers are close to 1 (rather than almost independent on D as in (5) without low-rank constraints). In addition, it has m -1 4 dependence rather than m -1 2 except when D = O ( √ m). Note that our bound is based on a novel characterization of Lipschitz properties of DNNs, which may be of independent interest from the learning theory point of view. We refer to Appendix B for details.

We also remark that when achieving the same order of generalization errors, we allow the choices of larger dimensions (D, p) and spectral norms of weight matrices, which lead to stronger expressive power for DNNs. For example, when achieving the same bound with W d 2 = 1 in spectral norm based results (e.g. in ours) and W d F = 1 in Frobenius norm based results (e.g., in Golowich et al. (2017) ), they only have

W d 2 = O(1/ √ r)

in Frobenius norm based results. The later results in a much smaller space for eligible weight matrices as r is of order p in general (i.e., r = δp for some constant δ ∈ (0, 1)), which may lead to weaker expressive ability of DNNs. We also demonstrate numerically in Section 4.5 that when norms of weight matrices are constrained to be very small, both training and testing performance degrade significantly. A quantitative analysis for the tradeoff between the expressive ability and the generalization for DNNs is deferred to a future effort.

3.2. A SPECTRAL NORM FREE ERC BOUND:

When, in addition, the loss function is bounded, we have the ERC bound free of the linear dependence on the spectral norm, as in the following corollary. The proof is provided in Appendix C. Corollary 1. In addition to the conditions in Theorem 1, suppose we further let g γ be bounded, i.e.,

EQUATION

The boundedness of G γ holds for certain loss functions, e.g., the ramp risk defined in (3). When b is constant (e.g., b = 1 for the ramp risk) and R D d=1 B d,2 > γ, we have that the ERC reduces to O( Dpr/m). This is close to the VC dimension of DNNs, which can be significantly tighter than existing norm based bounds in general. Similar norm free results hold for the architectures discussed in Section 4 using argument for Corollary 1, which we skip due to space limit. Moreover, our bound ( 6) is also tighter than recent results that are free of linear dependence on D d=1 B d,2 (Zhou & Feng, 2018; Arora et al., 2018) . Specifically, Zhou & Feng (2018) show that the generalization bound for CNNs is O D pr 2 /m , which results in a bound larger than (6) by O( √ Dr). Arora et al. (2018) derive a bound for a compressed network in terms of some error-resilience parameters, which is O( D 3 p 2 /m) since the cushion parameter therein is of the order µ = O(1/ √ p). Further discussion is provided in Appendix A.1.

4. EXPLORING NETWORK STRUCTURES:

The generic result in Section 3 does not highlight explicitly the potential impacts for specific structures of the networks. In this section, we consider several popular architectures of DNNs, including convolutional neural networks (CNNs) (Krizhevsky et al., 2012) , residual networks (ResNets) (He et al., 2016) , and hyperspherical networks (SphereNets) (Liu et al., 2017b) , and provide sharp characterization of the corresponding generalization bounds. In particular, we consider orthogonal filters and normalized weight matrices, which have shown good performance in both optimization and generalization (Mishkin & Matas, 2015; Huang et al., 2017) . Such constraints can be enforced using regularizations on filters and weight matrices, which is very efficient to implement in practice. This is also closely related with normalization approaches, e.g., batch normalization (Ioffe & Szegedy, 2015) and layer normalization (Ba et al., 2016) , which have achieved tremendous empirical success.

4.1. CNNS WITH ORTHOGONAL FILTERS:

CNNs are one of the most powerful architectures in deep learning, especially in tasks related to images and videos (Goodfellow et al., 2016) . We consider a tight characterization of the generalization bound for CNNs by generating the weight matrices using unit norm orthogonal filters, which has shown great empirical performance (Huang et al., 2017; Xie et al., 2017) . Specifically, we generate the weight matrices using a circulant approach, as follows. For the convolutional operation at the dth layer, we have n d channels of convolution filters, each of which is generated from a k ddimensional feature using a stride side s d . Suppose that s d divides both k d and p d-1 , i.e., k d-1 s d and p d-1 s d are integers, then we have

p d = n d •p d-1 s d

. This is equivalent to fixing the weight matrix at the d-th layer to be generated as in (7) , where

for all j ∈ [n d ], each W (j) d ∈ R p d-1 s d ×p d-1

is formed in a circulant-like way using a vector w (d,j) ∈ R k d with unit norms for all j as in (8).

EQUATION

When the stride size

s d = 1, W (j) d

corresponds to a standard circulant matrix (Davis, 2012). The following lemma establishes that when w (d,j) n d j=1 are orthogonal vectors with unit Euclidean norms, the generalization bound only depend on s d and k d that are independent of the width p d . The proof is provided in Appendix D. Corollary 2. Let g γ be a 1 γ -Lipschitz and bounded loss function, i.e., |g γ | ≤ b, and F D, • 2 be the class of CNNs defined in (1). Suppose the weight matrices in CNNs are formed as in ( 7) and ( 8) with s d = s, k d = k, and s divides both k and p d for all d ∈ [D], where w (d,j) n d j=1 satisfies w (j) w (i) = 0 for all i, j ∈ [n d ] and i = j with w (d,j) 2 = 1 for all j ≤ n d . Denote

C Net = B Jac \d,2 •R √ Dm/s sup f ∈F D, • 2 ,x∈Xm gγ (f (W D ,x)) . Then the ERC for CNNs satisfies R m G γ F D, • 2 = O min R(k/s) D/2 γ , b • k D d=1 n d •log C Net m .

Since n d ≤ k in our setting, the ERC for CNNs is proportional to

√ Dk 2 instead of √ Dpr.

For the orthogonal filtered considered in Corollary 2, we have

W d F = √ p d and W d 2,1 = p d , which

lead to the bounds of CNNs in existing results in Table 2 . In practice, one usually has k d p d , which exhibit a significant improvement over existing results, i.e.,

√:

Dk 2 D 3 p 2 . Even without the orthogonal constraint on filters, the rank r in CNNs is usually of the same order with width p, which also makes the existing bound undesirable. On the other hand, it is widely used in practice that k d = µs d for some small constant µ ≥ 1 in CNNs, then we have 

(k d /s d ) D/2 p D/2 resulted from R m G γ F D, • F . Remark 2.

Generalization Bound CNNs:

Neyshabur et al. ( 2015)

O 2 D •p D 2 √ m Bartlett et al. (2017) O ( k s ) D-1 2 • √ D 3 p 2 √ m Neyshabur et al. (2017) O ( k s ) D-1 2 • √ D 3 p 2 √ m Golowich et al. (2017) O p D 2 min 1 4 √ m , D m Our results O ( k s ) D 2 √ Dk 2 √ m w (j,1) ∈R √ k d 0 • • • • • • 0 ∈R p d-1 k d - √ k d • • • • • • • • • w (j, √ k d ) ∈R √ k d 0 • • • • • • 0 ∈R p d-1 k d - √ k d 0 • • • • • • • • • • • • 0 ∈R p d-1 -√ p d-1

.

Correspondingly, the stride size is

s 2 d k d on average and we have W d 2 ≤ k d s d if w (j,i) 2

= 1 for all i, j; see Appendix F for details. This is equivalent to permuting the columns of W d generated as in (8) by vectorizing the matrix filters in order to validate the convolution of the filters with all patches of the matrix input. Remark 3. A more practical scenario for CNNs is when a network has a few fully connected layers after the convolutional layers. Suppose we have D C convolutional layers and D F fully connected layers. From the analysis in Corollary 2, when s d = k d for convolutional layers and W d 2 = 1 for fully connected layers, we have that the overall ERC satisfies

O R• √ D C k 2 +D F pr γ √ m .

4.2. RESNETS WITH STRUCTURED WEIGHT MATRICES:

Residual networks (ResNets) (He et al., 2016) is one of the most powerful architectures that allows training of tremendously deep networks. Then we denote the class of ResNets with bounded weight matrices

EQUATION

Given an input x ∈ R p0 , the output of a D-layer ResNet is defined as

f (V D , U D , x) = f V D ,U D (• • • f V1,U1 (x)) ∈ R p D , where f V d ,U d (x) = σ (V d • σ (U d x) + x).

For any two layers i, j ∈ [D] and input x, we denote J x i:j as the Jacobian from layer i to layer j, i.e., f Vi,Uj (• • • f Vi,Ui (x)) = J x i:j • x, and B Jac,x i:j,2 as an upper bound of the norm of Jacobian for input x over the parameter, i.e., sup W D J x i,i 2 ≤ B Jac,x i:j,2 . We then provide an upper bound of the ERC for ResNets in the following corollary. The proof is provided in Appendix E. Corollary 3. Let g γ be a 

C Net = B Jac \d,2 max d (BV d ,2 +B U d ,2) R √ m/q sup f ∈F D, • 2 ,x∈Xm gγ (f (V D ,V D ,x)) . Then the ERC satisfies R m G γ F RN D, • 2 = O min R• D d=1 (BV d ,2 B U d ,2 +1) γ , b • Dpq•log C Net m .

Compared with the D-layer networks without shortcuts (1), ResNets have a stronger dependence on the input due to the shortcuts structure, which leads to (B V d ,2 B U d ,2 + 1) dependence for each layer. When B V d ,2 and B U d ,2 are of order 1/ √ D, we still have D d=1 (BV d ,2BU d ,2 + 1) = O(1). This partially explains the observation in practice that ResNets have good performance when the weight matrices have relatively small scales. Also note that to achieve the same bound for Rm Gγ F RN D, • F , we require B V d ,F , B U d ,F ≤ c, which leads to a much smaller parameter space than the space corresponding to B V d ,2 , B U d ,2 ≤ c for the same c.

4.3. HYPERSPHERICAL NETWORKS:

We also consider the hyperspherical networks (SphereNets) (Liu et al., 2017b) , which demonstrate improved performance than the vanilla DNNs. In specific, the SphereNets has the same architecture with DNNs defined in (1), except that the weight matrix can be viewed as

W d = S W d W d ,

where S W d is a diagonal matrix with the i-th diagonal entries being the Euclidean norm of the i-th row of W d . Note that we do not normalize the input x as in (Liu et al., 2017b) for ease of the discussion. A direct result of applying Theorem 1 implies that Rm Gγ F SN

D, • 2 = O(R • D d=1 B W d ,2 • √ Dpr/ (γ √ m)

). Such a self-normalization architecture has a benefit that B W d ,2 is small (close to 1) in general when the weights are spread out. In addition, it has lower computational costs than the weight normalization based on the spectral norm directly, and improved empirical results over batch normalization have been observed (Liu et al., 2017b; a) . 

R m G γ F D, • 2 = O R•Π D d=1 B d,2 •Π t∈I T Tt 2 • √ Dpr γ √ m

. Next, we illustrate several popular examples to show that Π t∈I T T t 2 is a size independent constant. We refer to Goodfellow et al. (2016) for more operations of changing the width.

Width Expansion. Two popular types of width expansion are padding and 1 × 1 convolution. For ease of discussion, suppose p d+1 = s • p d for some positive integer s ≥ 1. Taking padding with 0 as an example, where we plug in (s -1) zeros before each entry of x {d} , which is equivalent to setting  and (T d ) ij = 0 otherwise. This implies that T d 2 = 1.

T d ∈ R sp d ×p d with (T d ) ij = 1 if i = js,

For 1 × 1 convolution, suppose that the convolution features are {c 1 , . . . , c s }. Then we expand width by performing convolution (essentially entry-wise product) using s features respectively. This is equivalent to setting

T d ∈ R sp d ×p d with (T d ) ij = c k if i = j +(k-1)s for k ∈ [s], and (T d ) ij = 0 otherwise. It implies that T d 2 = s i=1 c 2 i . When s i=1 c 2 i ≤ 1, we have T d 2 ≤ 1. Width Reduction.

Two popular types of width reduction are average pooling and max pooling. Suppose p d+1 = p d s is an integer for some positive integer s. For average pooling, we pool each nonoverlapping s features into one feature. This is equivalent to setting

T d ∈ R p d s ×p d with (T d ) ij = 1/s if j = (i -1)s + k for k ∈ [s]

, and (T d ) ij = 0 otherwise. This implies that T d 2 = 1/s.

For max pooling, we choose the largest entry in each nonoverlapping feature segment of length s. Denote the set I s = {(i -1) × s + 1, . . . , i • s}. This is equivalent to setting  and (T d ) ij = 0 otherwise. This implies that T d 2 = 1. For pooling with overlapping features, similar results hold.

T d ∈ R p d s ×p d with (T d ) ij = 1 if |(x {d} ) j | ≥ |(x {d} ) k | ∀ k ∈ I s , k = j,

4.5. NUMERICAL EVALUATION:

To better illustrate the difference between our result and existing ones, we demonstrate some comparison results in Figure 1 using real data. In specific, we train a simplified VGG19-net (Simonyan & Zisserman, 2014) using 3 × 3 convolution filters (with unit norm constraints) on the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) . We first compare with the capacity terms in Bartlett et al. ( 2017 Note that since we may have more filters n d than their dimension k, we do not assume orthogonality here. Thus we simply use the upper bounds of norms B d rather than the form as in Table 2 . Following the analysis of Theorem 1, we have k D d=1 n d dependence rather than

• Ours: Π D d=1 B d,2 k D d=1 n d • Bound1: Π D d=1 B d,2 D d=1 B 2/3 d,2→1 B 2/3 d,2 3/2 • Bound2: Π D d=1 B d,2 D 2 p D d=1 p d B 2 d,F B 2 d,2 • Bound3: Π D d=1 B d,F √ D

√ Dpr as k D d=1 n d

is the total number free parameter for CNNs, where n d is the number of filters at d-th layer. Also note that we ignore the logarithms factors in all bounds for simplicity and their empirical values are small constants compared with the the dominating terms.

For the same network and corresponding weight matrices, we see from Figure 1 2017) (both are of order D 3 pr). In addition, this verifies that spectral dependence is significantly tighter than Frobenius norm dependence in Golowich et al. (2017) . Further, we show the training accuracy, testing accuracy, and the empirical generalization error using different scales on the norm of the filters in Figure 1 (b) . We see that the generalization errors decrease when the norm of filters decreases. However, note that when the norms are too small, the accuracies drop significantly due to a potentially much smaller parameter space. Thus, the scales (norms) of the weight matrices should be nether too large (induce large generalization error) nor too small (induce low accuracy) and choosing proper scales is important in practice as existing works have shown. On the other hand, this also support our claim that when Rm Gγ F D, • F (or other existing bound) attains the same order with our Rm Gγ F D, • 2 , we have better training/testing performance. Further experimental result that compare our bound (Corollary 1) with (Zhou & Feng, 2018; Arora et al., 2018) in the bounded output case is provided in Appendix A.1.

We want to remark that all numerical evaluations are empirical estimation of the generalization bounds, rather than their exact values. This is because all existing bounds requires to take uniform bounds of some quantities on parameters or the supremum value over the entire space, which is empirically not accessible. For example, in the case that when it involve the upper/lower bound of quantities (norm, rank, or other parameters) depending on weight matrices, theoretically we should take the values of their upper/lower bounds (this leads to worse empirical bounds) rather than estimating them from the training process; or in the case that the bounds involve some quantities depending on the supremum over the entire parameter space, numerical evaluations cannot exhaust the entire parameter space to reach the supremum (Bartlett et al., 2017; Golowich et al., 2017; Neyshabur et al., 2015; 2017; Zhou & Feng, 2018; Arora et al., 2018) . Our experiments here (including Appendix A) cannot avoid such restrictions, but the comparison is fair across various bounds as they are obtained from the same training process.

A EXTENDED NUMERICAL RESULTS:



A.1 COMPARISON WITH EXISTING RESULTS WITH BOUNDED OUTPUT:

We compared our norms based bound with several other norm based results in Section 4.5. In this section, we further compare our result with bounded output in Corollary 1 with Zhou & Feng (2018) ; Arora et al. (2018) . Analogous to Section 4.5, we train a simplified VGG19-net (Simonyan & Zisserman, 2014) using 3 × 3 convolution filters (with unit norm constraints) on the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) . We compare with the capacity terms in Zhou & Feng (2018) (Bound 1) and Arora et al. (2018) (Bound 2) by ignoring the factor R γ √ m as follows:

• Ours: b k D d=1 n d . Note that b = 1 in this case. • Bound1: Dk D d=1 rank(W d ) • n d .

Note that their activation functions for the intermediate layers are sigmoid and the last layer is softmax, with squared error, which essentially has a bounded output. We also take the last layer as convolution layer for ease of discussion.

• Bound2: max x∈Xm f (W D , x) 2 • CDβ D d=1 k/s 2 µ 2 d µ 2 d→

, where C = Ω( 1 The resulting bounds on the trained networks are provided in Figure 2 . We observe that our bound is smaller than Zhou & Feng (2018) ; Arora et al. (2018) by at least an order of magnitude. Specifically, our bound is of order ≈ 10 2 , while Zhou & Feng (2018) result in a bound of order > 10 3 and Arora et al. ( 2018) result in a bound of order > 10 4 . This coincide with our discussion in Section 3.2 and allows us to obtain non-vacuous bound (generalization bound < 1) with moderate training sample sizes (e.g., m = Ω(10 4 )). Also note that compared with the norm based based results in Figure 1 , the results here based on the bounded output are significantly tighter in general. We regard this as a trade-off between the looser norm based bounds that allow more explicit interpretability in terms of the weight matrix structures and the tighter bounds that are more obscure in terms of dependence on the network structures. A result that have both merits are desired as a future direction.

A.2 COMPARISON BETWEEN B JAC \d,2 AND d B d,2

We demonstrate the empirical difference between B Jac \d,2 and d B d,2 . Using the same setting of the network and dataset as above, we provide the empirical distribution of B Jac \d,2 and d B d,2 over the training set using different random initializations of weight matrices, which is provided in Figure 3 . We can observe that the values of B We further provide an empirical evaluation to see how strong the quantities B Jac \d,2 and d B d,2 depend on the depth. Note that we use d as the variable for depth. Using the same setting as above, we provide the magnitude of log B Jac \d,2 and log d B d,2 in Figure 4 . We also provide the plots for log d and log d 2 as reference. We can observe that log d B d,2 has an approximately linear dependence on the depth, which matches with our intuition. In terms of log B Jac \d,2 , we can see that it has a significantly slower increasing rate than log d B d,2 . Compared with the reference plots log d and log d 2 , we can observe even a slower rate than log d 2 . This further indicates that log B Jac \d,2 may has a dependence slower than some low degree of poly(d). 

B PROOF OF THEOREM 1:

We start with some definitions of notations. Given a vector x ∈ R p , we denote x i as the i-th entry, and x i:j as a sub-vector indexed from i-th to j-th entries of x. Given a matrix A ∈ R n×m , we denote A ij as the entry corresponding to i-th row and j-th column, A i * (A * i ) as the i-th row (column), A I1I2 as a submatrix of A indexed by the set of rows I 1 ⊆ [n] and columns

I 2 ⊆ [m].

Given two real values a, b ∈ R + , we write a ( )b if a ≤ (≥)cb for some generic constant c > 0.

Our analysis is based on the characterization of the Lipschitz property of a given function on both input and parameters. Such an idea can potentially provide tighter bound on the model capacity in terms of these Lipschitz constants and the number of free parameters, including other architectures of DNNs. We first provide an upper bound for the Lipschitz constant of f (W D , x) in terms of the input x. Lemma 1. Given W D , for any

f (W D , •) ∈ F D, • 2 and x 1 , x 2 ∈ R p0 , we have f (W D , x 1 ) -f (W D , x 2 ) 2 ≤ x 1 -x 2 2 • D d=1 B d .

Proof. We prove by induction. Specifically, we have

f (W D , x 1 ) -f (W D , x 2 ) 2 = σ (W D f (W D-1 , x 1 )) -σ (W D f (W D-1 , x 2 )) 2 (i) ≤ W D f (W D-1 , x 1 ) -W D f (W D-1 , x 2 ) 2 ≤ W D 2 • f (W D-1 , x 1 ) -f (W D-1 , x 2 ) 2 ≤ B D • f (W D-1 , x 1 ) -f (W D-1 , x 2 ) 2 ,

where (i) comes from the entry-wise 1-Lipschitz continuity of σ(•). For the first layer, we have

f (W 1 , x 1 ) -f (W 1 , x 2 ) 2 = σ (W 1 x 1 ) -σ (W D x 2 ) 2 ≤ W 1 x 1 -W 1 x 2 2 ≤ B 1 • x 1 -x 2 2 .

By repeating the argument above, we complete the proof.

Next, we provide an upper bound for the Lipschitz constant of f (W D , x) in terms of the parameters

W D . Lemma 2. Given any x ∈ R p0 satisfying x 2 ≤ R, for any f (W D , x) , f W D , x ∈ F D, • 2 with W D = {W d } D d=1 and W D = W d D d=1

, and denote

EQUATION

:D,2 , then we have

f (W D , x) -f W D , x 2 ≤ B Jac,x \d,2 • R √ D D d=1 W d -W d 2 F .

Proof. Given x and two sets of weight matrices

{W d } D d=1 , W d D d=1

, we have

EQUATION

where (i) is derived from adding and subtracting intermediate neural network functions recurrently,

where f W D • • • f W d+1 f W d • • • f W1 (x)

share the same output of activation functions from

d + 1-th layer to D-the layer with f W D f W D-1 (• • • f W1 (x))

, (ii) is from fixing the activation function output, and (iii) is from the entry-wise 1-Lipschitz continuity of σ(•). On the other hand, for any d ∈ [D], we further have

EQUATION

)

where (i) is from the entry-wise 1-Lipschitz continuity of σ(•) and (ii) is from recursively applying the same argument.

In addition, we denote

W d = U d V d and W d = U d V d , where U d , V d , U d , V d ∈ R p×r and U 2 = V 2 = U 2 = V 2 = W d 1/2

2 . Then we have

EQUATION

Applying ( 10) recursively and combining ( 11) and ( 12), we obtain the desired result as

f W D f W D-1 (• • • f W1 (x)) -f W D f W D-1 • • • f W1 (x) 2 ≤ D d=1 B Jac,x (d+1):D • B Jac,x 1:(d-1) • x 2 • W d 1/2 2 V -V F + U -U F ≤ B Jac,x \d,2 • R √ D • max d B 1/2 d,2 D d=1 V -V F + U -U F ≤ B Jac,x \d,2 • R √ 2D • max d B 1/2 d,2 D d=1 V -V 2 F + U -U 2 F . Lemma 3. Suppose g(w, x) is L w -Lipschitz over w ∈ R h with w 2 ≤ K and α = sup g∈G,x∈Xm |g(w, x)|. Then the ERC of G = {g(w, x)} satisfies R m (G) = O   α h log KLw √ m α √ h √ m   .

Proof. For any w, w ∈ R h and

EQUATION

)

Since g is a parametric function with h parameters, then we have the covering number of G under the metric ∆ in (13) satisfies

N (G, ∆, δ) ≤ 3KL w δ h .

Then using the standard Dudley's entropy integral bound on the ERC (Mohri et al., 2012) , we have the ERC satisfies Then we have

EQUATION

R m (G) inf β>0 β + 1 √ m α β h log KL w δ dδ ≤ inf β>0 β + α h log KLw β m (i) α h log KLw √ m α √ h √ m ,

where (i) is obtained by taking β = α h/m.

By definition, we have α = sup f ∈F D, • 2 ,x∈Xm g γ (f (W D , x)). From Lemma 1 and 1 γ -Lipschitz continuity of g, we also have

EQUATION

)

From Lemma 2, we have

L w ≤ max x∈Xm B Jac,x \d,2 • R √ 2D • max d B 1/2 d,2 .

Moreover, when p d = p for all d ∈ [D], we have

K = D d=1 W d 2 F ≤ pD • max d B d,2 .

Combining the results above with Lemma 3 and h = 2Dpr, we have

R m (G) α h log KLw √ m α √ h √ m R • D d=1 B d,2 Dpr log B Jac \d,2 •R √ Dm/r•max d B d,2 sup f ∈F D, • 2 ,x∈Xm gγ (f (W D ,x)) γ √ m .

C PROOF OF COROLLARY 1

The analysis follows Theorem 1, except that the bound for α in (15) satisfies

α ≤ min b, R • D d=1 B d,2 γ ,

since g satisfies |g| ≤ b and 1 γ -Lipschitz continuous. Then we have the desired result.

D PROOF OF COROLLARY 2:

We first show that using unit norm filters for all d ∈ [D] and n d ≤ k d , we have

EQUATION

First note that when n d = k d , due to the orthogonality of w (d,j) k d j=1 , for all i, q ∈ [k d ], i = q, we have

EQUATION

)

When

EQUATION

where (i) is from (17). For the off-diagonal entries of W d W d , i.e., for i = q, i, q ∈ [p d ], we have

EQUATION

where (i) is from (17). Combining ( 18) and ( 19), we have that W d W d is a diagonal matrix with

W d W d 2 = k d s d =⇒ W d 2 = k d s d .

For n d < n k , we have that W d is a row-wise submatrix of that when

n d = k d , denoted as W d . Let S ∈ R n d k d s d

×p d be a row-wise submatrix of an identity matrix corresponding to sampling the row of

W d to form W d .

Then we have that ( 16) holds, and since

W d 2 = S • W d W d • S 2 2 = k d s d . Suppose k 1 = • • • = k D = k

for ease of discussion. Then following the same argument as in the proof of Theorem 1 and Lemma 3, we have

EQUATION

h = k D d=1 n d .

Using the fact that the number of parameters in each layer is no more than kn d rather than 2pr, we have

R m (G) α h log KLw √ m α √ h √ m R • D d=1 k s d • k D d=1 n d log B Jac \d,2 •R √ Dm/s sup f ∈F D, • 2 ,x∈Xm gγ (f (W D ,x)) γ √ m .

E PROOF OF COROLLARY 3:

The analysis is analogous to the proof for Theorem 1, but with different construction of the intermediate results. We first provide an upper bound for the Lipschitz constant of f (V D , U D , x) in terms of x.

Lemma 4. Given V D and U D , for any f

EQUATION

Proof. Consider the ResNet layer, for any x 1 , x 2 ∈ R k , we have

f (V D , U D , x 1 ) -f (V D , U D , x 2 ) 2 = f V D ,U D (• • • f V1,U1 (x 1 )) -f V D ,U D (• • • f V1,U1 (x 2 )) 2 = σ V D • σ U D • f V D-1 ,U D-1 (• • • f V1,U1 (x 1 )) + f V D-1 ,U D-1 (• • • f V1,U1 (x 1 )) -σ V D • σ U D • f V D-1 ,U D-1 (• • • f V1,U1 (x 2 )) + f V D-1 ,U D-1 (• • • f V1,U1 (x 2 )) 2 (i) ≤ V D • σ U D • f V D-1 ,U D-1 (• • • f V1,U1 (x 1 )) -V D • σ U D • f V D-1 ,U D-1 (• • • f V1,U1 (x 2 )) 2 + f V D-1 ,U D-1 (• • • f V1,U1 (x 1 )) -f V D-1 ,U D-1 (• • • f V1,U1 (x 2 )) 2 (ii) ≤ ( V D 2 U D 2 + 1) • f V D-1 ,U D-1 (• • • f V1,U1 (x 1 )) -f V D-1 ,U D-1 (• • • f V1,U1 (x 2 )) 2 ,

where (i) is the fact that σ is 1-Lipschitz, and (ii) is from repeating the arguments of (i) and (ii). By recursively applying the argument above, we have the desired result.

Next, we provide an upper bound for the Lipschitz constant of f

(V D , U D , x) in terms of V D and U D . Lemma 5. Given any x ∈ R p0 satisfying x 2 ≤ R, for any f (V D , U D , x) , f V D , U D , x ∈ F D, • 2 with V D = {V d } D d=1 , U D = {U d } D d=1 , V D = V d D d=1

, and

U D = U d D d=1

, and denote

EQUATION

:D,2 , then we have

f (V D , U D , x) -f V D , U D , x 2 ≤ B Jac,x \d,2 max d (B V d ,2 + B U d ,2 ) R √ 2D • D d=1 V D -V D 2 F + D d=1 U D -U D 2 F .

Proof. Given x and two sets of weight matrices

{W d } D d=1 , W d D d=1

, we have

EQUATION

EQUATION

EQUATION

where (i) and (ii) from the entry-wise 1-Lipschitz continuity of σ(•). In addition, for any d ∈ [D], we further have

EQUATION

)

Combining ( 21) and ( 22), we obtain

f V D ,U D (• • • f V1,U1 (x)) -f V D , U D • • • f V1, U1 (x) 2 ≤ D d=1 B Jac,x (d+1):D • B Jac,x 1:(d-1) • x 2 • V d -V d F • U d 2 + U d -U d F • V d 2 ≤ B Jac,x \d,2 max d (B V d ,2 + B U d ,2 ) R D d=1 • V d -V d F + U d -U d F ≤ B Jac,x \d,2 max d (B V d ,2 + B U d ,2 ) R √ 2D • D d=1 V D -V D 2 F + D d=1 U D -U D 2 F .

On the other hand, for any d ∈ [D], we have

EQUATION

)

where (i) is from the entry-wise 1-Lipschitz continuity of σ(•) and (ii) is from recursively applying the same argument.

Let p 1 = • • • = p D = p and q 1 = • • • = q D = q. Then following the same argument as in the proof of Theorem 1 and ( 23), we have 

α = sup f ∈F D, • 2 ,x∈Xm g γ (f (V D , V D , x)) ≤ R • D d=1 (B V d ,2 B U d ,2 + 1) γ , L w ≤ max x∈Xm B Jac,x \d,2 max d (B V d ,2 + B U d ,2 ) R √ 2D, K = D d=1 V d 2 F + U d 2 F ≤ pD • max d (B V d ,2 + B U d ,

d (i, l) = 0 for i = l. For diagonal blocks, we have

W (j) d (i, i) =                 w (j,1) ∈R √ k d 0 • • • • • • • • • • • • 0 ∈R p d-1 k d - √ k d • • • • • • • • • • • • • • • w (j, √ k d ) ∈R √ k d 0 • • • • • • • • • • • • • • • • • • • • • 0 ∈R p d-1 k d - √ k d 0 • • • 0 ∈R s d √ k d w (j,1) ∈R √ k d 0 • • • • • • • • • • • • 0 ∈R p d-1 k d - √ k d • • • • • • • • • • • • • • • w (j, √ k d ) ∈R √ k d 0 • • • • • • • • • • • • • •0 ∈R p d-1 k d - √ k d - s d √ k d

. . . w (j,1)

EQUATION

)

where w and ( 25), we have that the stride for W (j)

d is s 2 d k d .

Using the same analysis for Corollary 2. We have

W d 2 = 1 if i w (j,i) 2 2 = k d s d .

For image inputs, we need an even smaller matrix W (j) d (i, i) with fewer rows than (25), denoted as

EQUATION

)

Then W d 2 ≤ 1 still holds if i w (j,i) 2 2 = k d s d since W d generated using ( 26) is a submatrix of W d generated using (25).

:

D •Π D d=1 B d,F √ m

Figures and Tables:

d 2 = 1 for all d = 1, . . . , D, where W d F = Θ( √ r) and W d 2,1 = Θ(r) in generic scenarios.

while Bartlett et al. (2017); Neyshabur et al.

1 γ -Lipschitz and bounded loss function, i.e., |g γ | ≤ b, and F RN D, • 2 be the ResNets defined in (9) with p d = p and q d = q for all d ∈ [D], B Jac \d,2 = max d∈[D],x∈Xm B Jac,x 1:(d-1),2 B Jac,x (d+1):D,2 , and

4.4 EXTENSION TO WIDTH-CHANGE OPERATIONSChange the width for certain layers is a widely used operation, e.g., for CNNs and ResNets, which can be viewed as a linear transformation in many cases. In specific, denote x {d} ∈ R p d as the output of the d-th layer. Then we can use a transformation matrix T d ∈ R p d+1 ×p d to denote the operation to change the dimension between the output of the d-th layer and the input of the (d + 1)-th layer as f W d+1 x {d} = σ W d+1 T d x {d} . Denote the set of layers with width changes by I T ⊆ [D]. Combining with Theorem 1, we have that the ERC satisfies

) (Bound1), Neyshabur et al. (2017) (Bound2), and Golowich et al. (2017) (Bound3) by ignoring the common factor R γ √ m as follows:

Figure 1: Panel (a) shows comparison results for the same VGG19 network trained on CIFAR10 using unit norm filters. The vertical axis the corresponding bounds in the logarithmic scale. Panel (b) shows the training accuracy (red diamond), testing accuracy (blue cross), and the empirical generalization error using different scales of the filters listed on the horizontal axes.

(a) that our result (10 4 ∼ 10 5 ) is significantly smaller than Bartlett et al. (2017); Neyshabur et al. (2017) (10 8 ∼ 10 9 ) and Golowich et al. (2017) (10 14 ∼ 10 15 ). As we have discussed, our bound benefits from tighter dependence on the dimensions. Note that k D d=1 n d is approximately of order Dk 2 , which is sigin Bartlett et al. (2017) and D 2 p D d=1 p d B 2 d,F /B 2 d,2 in Neyshabur et al. (

) is the activation contraction, β = Ω(1) is the well-distributed Jacobian, µ d = O(1/ √ p) is the layer cushion, and µ d→ = O(1/ √ p) is the interlayer cushion. See more details in Arora et al. (2018).

Figure 2: Comparison results for the same VGG19 network trained on CIFAR10. The vertical axis is the corresponding bounds in the logarithmic scale.

Figure 3: Empirical distribution of B Jac \d,2 and d B d,2 for the same VGG19 network trained on CIFAR10.

Figure 4: Comparison results for the dependence of B Jac \d,2 and d d,2 on depth. The horizontal axes is the depth and the vertical axes is the values of corresponding quantities in the logarithmic scale.

Since we have α = sup g∈G,x∈Xm ∆ (g, 0) = sup g∈G,x∈Xm |g(w, x)| .

2 ) , andh = 2Dpq, V d ,2 B U d ,2 + 1) • Dpq • log B Jac \d,2 max d (BV d ,2 +B U d ,2) R √ m/q sup f ∈F D, • 2 ,x∈Xm gγ (f (V D ,V D ,x)) γ √ m . F SPECTRAL BOUND FOR W d IN CNNS WITH MATRIX FILTERSWe provide further discussion on the upper bound of the spectral norm for the weight matrix W d in CNNs with matrix filters. In particular, by denoting W d using submatrices as in (7), i.e., zero matrices, i.e., W

Comparison with existing norm based bounds of CNNs. We suppose R and γ are generic constants for ease of illustration. The results of CNNs in existing works are obtained by substituting the corresponding norms of the weight matrices generated by orthogonal filters, i.e., W d 2 = k/s, W d F = √ p, and W d 2,1 = p.

Table content: <table><tr><td>We consider vector input in</td></tr><tr><td>Corollary 2. For matrix inputs, e.g., images,</td></tr><tr><td>similar results hold by considering vectorized</td></tr><tr><td>input and permuting columns of W d . Specif-ically, suppose √ k d and √ p d-1 are integers</td></tr><tr><td>for ease of discussion. Consider the input as a</td></tr><tr><td>p d-1 dimensional vector obtained by vector-izing a √ p d-1 × √ p d-1 input matrix. When</td></tr><tr><td>the 2-dimensional (matrix) convolutional fil-ters are of size √ k d × √ k d , we form the rows of each W (j) d by concatenating √ k d vectors {w (j,i) } √ k d</td></tr></table>

Jac \d,2 are approximately 2 orders smaller than the values of d B d,2 , which support our claim that B Jac \d,2 is a tighter quantification then d B d,2 .

Table content: <table><tr><td>26</td><td>28</td><td>30 B Jac \d,2</td><td>32</td><td>34</td><td>2500</td><td>2700 ⇧ d B d,2</td><td>2900</td></tr></table>

Peer review (iclr2019):
 The paper provides a generalization bound for multi-layered deep neural networks in terms of dimensions rather than norms. The bound is derived by controlling Rademacher complexity of the Ramp loss under the Lipschitzness of the network as a parametric function in Depth * Width ^2 number of parameters, and then using standard L-2 covering and Dudley Integral. They extend this technique for CNNs, Resnets, Hyper-spherical Networks, etc and provide specialized bounds for each case. In the end, the authors provide comparisons to the existing bounds. Although intended, the bound in Theorem-1 depends on the number of parameters and hold only if m > d * (p^2) = number of parameters (from the last line of proof of Lemma 3, we need .beta < .alpha and thus m > h). Such bounds are already know in the literature (see Anthony and Bartlett, 1999). Adaptive (completely norm dependent, like Bartlett et. al. 2017) bounds will be better than explicit dimension dependent bounds. The comparison in Figure-1 which suggest their bound to be better is unfair because they are comparing their specialized bounds for CNN to generic bounds for standard feedforward networks. Same for comparison in Table-2. It was already established in Theorem 3.4 (Bartlett et al. 2017) that spectral norms are necessary for any generalization bounds for Deep Neural Networks, thus voiding the claims made in the paper (and discussion) about the importance of spectral norms. Typos / Errors : 1. Statement of Lemma 2 does not contain the spectral norms terms. 2. The third equation in Page 13 should be K <= .sqrt{pD} max B_{d, 2}; and this changes the bound further. The paper introduces some new techniques on mathematical analysis of specialized neural networks.