Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 ‖Wd‖F, where Wd 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 ‖Wd‖2 (spectral norm) and ‖Wd‖2,1 (sum of the Euclidean norms for all rows of Wd). Golowich et al. (2017) provide a nearly size independent bound based on ‖Wd‖F. Nevertheless, the generalization bound depends on other than the spectral norms of the weight matrices may be too loose. In specific, ‖Wd‖F (‖Wd‖2,1) is in general √ r (r) times larger than ‖Wd‖2. Given m training data points and suppose ‖Wd‖2 = 1 for ease of discussion, Bartlett et al. (2017) and Neyshabur et al. (2017) demonstrate generalization error bounds as Õ( √ D3pr/m),
and Golowich et al. (2017) achieve a bound Õ(rD/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
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 ‖Wd‖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 √ Dk2/ √ m ) , while Bartlett et al. (2017); Neyshabur et al. (2017)
achieve Õ (( k s )D−1 2 √ D3p2/ √ m ) and Golowich et al. (2017) achieve Õ ( p D 2 min { 1 4√m , √ D m }) (rank(Wd) = 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 ∈ Rn×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 ‖Ai∗‖2. We use the standard notations O (·), Θ (·), and Ω (·) to denote limiting behaviors ignoring constants, and Õ (·), Θ̃ (·) and Ω̃ (·) to further ignore logarithmic factors.

heading: 2 PRELIMINARIES
text: We provide a brief description of the DNNs. Given an input x ∈ Rp0 , the output of a D-layer network is defined as fDf (WD, x) = fWD (· · · fW1 (x)) ∈ RpD , where fWd(y) = σd (Wd · y) : Rpd−1 → Rpd 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 matricesWD = {Wd ∈ Rpd×pd−1} D d=1 and ranks as
FD,‖·‖ = { f (WD, x) | ∀d ∈ [D],Wd ∈ WD, ‖Wd‖ ≤ Bd, rank (Wd) ≤ rd } , (1)
where x ∈ Rp0 is an input, and {Bd} are real positive constants. We will specify the norm ‖·‖ and the corresponding upper bounds Bd, e.g., ‖·‖2 and Bd,2, or ‖·‖F and Bd,F, when necessary. Given a loss function g(·, ·), we denote a class of loss functions measuring the discrepancy between a DNN’s output f (WD, x) and the corresponding observation y ∈ Ym for a given input x ∈ Xm as
G ( FD,‖·‖ ) = { g(f (WD, x) , y) ∈ R | x ∈ Xm, y ∈ Ym, f (·, ·) ∈ FD,‖·‖ } ,
where the sets of bounded inputs Xm and the corresponding observations Ym are Xm = {xi ∈ Rp0 | ‖xi‖2 ≤ R for all i ∈ [m]} ⊂ X and Ym = {yi ∈ [pD] for all i ∈ [m]} ⊂ Y. Then the empirical Rademacher complexity (ERC) of G ( FD,‖·‖ ) given Xm and Ym is
Rm ( G ( FD,‖·‖ )) = E ∈{±1}m
[ sup
f(·,·)∈FD,‖·‖ ∣∣∣∣ 1m m∑ i=1 i · g (f (WD, xi) , yi) ∣∣∣∣ ∣∣∣∣∣ Xm,Ym ] , (2)
where {±1}m ∈ Rm is the set of vectors only containing entries +1 and−1, and ∈ Rm 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 pD = Nclass is the number of classes. Consider g with bounded outputs, namely the ramp risk. Specifically, for an input x belonging to class y ∈ [Nclass], we denote ν = (f (WD, x))y −maxi 6=y (f (WD, x))i. For a given real value γ > 0, the class of ramp risk functions with parameter γ is Gγ ( FD,‖·‖ ) ={
gγ (f (WD, x) , y) |fD ∈ FD,‖·‖ }
, where gγ is 1 γ -Lipschitz continuous, defined in (3). For conve-
gγ (f (WD, x) , y) =  0, ν > γ1− νγ , ν ∈ [0, γ]1, ν < 0, (3) nience, we denote gγ (f (WD, x) , y) as gγ (f (WD, 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 (·, ·) ∈ FD,‖·‖, the generalization error is upper bounded with respect to (w.r.t.) the ERC satisfies
E [gγ (f (WD, x))]− 1m ∑m i=1 gγ (f (WD, xi)) ≤ 2Rm ( Gγ ( FD,‖·‖ )) + 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 Rm 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.

heading: 3 GENERALIZATION ERROR BOUND FOR DNNS
text: We introduce some additional notations first. Given any two layers i, j ∈ [D] and input x, we denote Jxi:j as the Jacobian from layer i to layer j, i.e., fWj (· · · fWi (x)) = Jxi:j · x. For convenience, we denote fWi (x) = J x i,i · x when i = j and denote Jxi: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., supWD ∥∥Jxi,i∥∥2 ≤ BJac,xi:j,2 .

heading: 3.1 A TIGHTER ERC BOUND FOR DNNS
text: 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 FD,‖·‖2 be the class of DNNs defined in (1), pd = p, rd = r for all d ∈ [D], BJac\d,2 = maxd∈[D],x∈Xm B Jac,x 1:(d−1),2B Jac,x (d+1):D,2, and C Net =
BJac\d,2·R √ Dm/r·maxd Bd,2
supf∈FD,‖·‖2 ,x∈Xm gγ(f(WD,x))
. Then the ERC satisfies Rm ( Gγ ( FD,‖·‖2 )) = O
( R· ∏D d=1 Bd,2 √ Dpr logCNet
γ √ m
) . (5)
Remark 1. Note that CNet 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 BJac\d,2 ∏ dBd,2.
Empirical distributions of BJac\d,2 and ∏ dBd,2 are provided in Appendix A.2, where B Jac \d,2’s are
constants that are orders of magnitude smaller than ∏ dBd,2. Further experiment in Appendix A.3 shows thatBJac\d,2 has a dependence slower than some low degree poly(depth), rather than exponential on the depth as in ∏ dBd,2. Thus, logC
Net can be considered as a constant almost independent of D in practice. Even in the worst case that BJac\d,2 ≈ ∏ dBd,2 (this almost never happens in practice), our bound is still tighter than existing spectral norm based bounds (Bartlett et al., 2017; Neyshabur et al., 2017) by an order of √ D. Also note that CNet is a quantity (including BJac\d,2) only depending on the training dataset, which is due to the fact that the ERC only depends on the training dataset.
For convenience, we treat R/γ as a constant here. We achieve Õ(ΠDd=1Bd,2 · √ Dpr/m) in Theorem 1, which is tighter than existing results based on the network sizes and norms of weight matrices, as shown in Table 1. In particular, Neyshabur et al. (2015) show an exponential dependence on D, i.e., O(2DΠDd=1Bd,F/ √ m), which can be significantly larger than ours. Bartlett et al. (2017); Neyshabur et al. (2017) demonstrate polynomial dependence on sizes and the spectral norm of weights, i.e., Õ(ΠDd=1Bd,2 · √ D3pr/m). Our result in (5) is tighter by an order of D, which is significant in practice. More recently, Golowich et al. (2017) demonstrate a bound w.r.t the Frobenius norm as Õ ( ΠDd=1Bd,F ·min {√ D m ,m− 1 4 · log 3 4 (m) √ log (C ) }) , where C = R·Π D d=1Bd,F
supx∈Xm‖f(WD,x)‖2 .
This has a tighter dependence on network sizes. Nevertheless, ‖Wd‖F is generally √ r times larger than ‖Wd‖2, which results in an exponential dependence pD/2 compared with the bound based on the spectral norm. Moreover, log(C ) is linear on D except that the stable ranks ‖Wd‖F / ‖Wd‖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 ‖Wd‖2 = 1 in spectral norm based results (e.g. in ours) and ‖Wd‖F = 1 in Frobenius norm based results (e.g., in Golowich et al. (2017)), they only have ‖Wd‖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.

heading: 3.2 A SPECTRAL NORM FREE ERC BOUND
text: 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., |gγ | ≤ b. Then the ERC satisfies
Rm ( Gγ ( FD,‖·‖2 )) = O ( min { R ∏D d=1 Bd,2 γ , b } · √ Dpr logCNet m ) . (6)
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=1Bd,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=1Bd,2 (Zhou & Feng, 2018; Arora et al., 2018). Specifically, Zhou & Feng (2018) show that the generalization bound for CNNs is Õ ( D √ pr2/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̃( √ D3p2/m) since the cushion parameter therein is of the order µ = O(1/√p). Further discussion is provided in Appendix A.1.

heading: 4 EXPLORING NETWORK STRUCTURES
text: 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.

heading: 4.1 CNNS WITH ORTHOGONAL FILTERS
text: 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 nd channels of convolution filters, each of which is generated from a kddimensional feature using a stride side sd. Suppose that sd divides both kd and pd−1, i.e.,
kd−1 sd
and pd−1sd are integers, then we have pd = nd·pd−1 sd
. This is equivalent to fixing the weight matrix at the d-th layer to be generated as in (7), where for all j ∈ [nd], each W (j)d ∈ R pd−1 sd ×pd−1 is formed in a circulant-like way using a vector w(d,j) ∈ Rkd with unit norms for all j as in (8).
Wd = [ W (1)> d · · · W (nd)> d ]> ∈ Rpd×pd−1 , (7)
W (j) d =  w(d,j) 0 · · · · · · · · · · · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈Rpd−1−kd 0 · · · 0︸ ︷︷ ︸ ∈Rsd w(d,j) 0 · · · · · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈Rpd−1−kd−sd ...
w (d,j) (sd+1):kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈Rpd−1−kd w (d,j) 1:sd
 . (8)
When the stride size sd = 1, W (j) d corresponds to a standard circulant matrix (Davis, 2012). The following lemma establishes that when { w(d,j) }nd j=1
are orthogonal vectors with unit Euclidean norms, the generalization bound only depend on sd and kd that are independent of the width pd. The proof is provided in Appendix D.
Corollary 2. Let gγ be a 1γ -Lipschitz and bounded loss function, i.e., |gγ | ≤ b, and FD,‖·‖2 be the class of CNNs defined in (1). Suppose the weight matrices in CNNs are formed as in (7) and (8) with sd = s, kd = k, and s divides both k and pd for all d ∈ [D], where { w(d,j) }nd j=1 satisfies
w(j)>w(i) = 0 for all i, j ∈ [nd] and i 6= j with ∥∥w(d,j)∥∥
2 = 1 for all j ≤ nd. Denote CNet =
BJac\d,2·R √ Dm/s
supf∈FD,‖·‖2 ,x∈Xm gγ(f(WD,x))
. Then the ERC for CNNs satisfies
Rm ( Gγ ( FD,‖·‖2 )) = O ( min { R(k/s)D/2 γ , b } · √ k ∑D d=1 nd·logCNet m ) .
Since nd ≤ k in our setting, the ERC for CNNs is proportional to √ Dk2 instead of √ Dpr. For the orthogonal filtered considered in Corollary 2, we have ‖Wd‖F = √ pd and ‖Wd‖2,1 = pd, which lead to the bounds of CNNs in existing results in Table 2. In practice, one usually has kd pd, which exhibit a significant improvement over existing results, i.e., √ Dk2 √ D3p2. 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 unde-
sirable. On the other hand, it is widely used in practice that kd = µsd for some small constant µ ≥ 1 in CNNs, then we have (kd/sd)D/2 pD/2 resulted from Rm ( Gγ ( FD,‖·‖F )) . Remark 2. We consider vector input in Corollary 2. For matrix inputs, e.g., images, similar results hold by considering vectorized input and permuting columns of Wd. Specifically, suppose √ kd and √ pd−1 are integers for ease of discussion. Consider the input as a pd−1 dimensional vector obtained by vectorizing a √ pd−1 × √ pd−1 input matrix. When the 2-dimensional (matrix) convolutional filters are of size √ kd × √ kd, we form the rows of each W (j)d by concatenating √ kd vectors {w(j,i)} √ kd
i=1 padded with 0’s, each of which is a concatenation of one row of the filter of size√ kd with some zeros as follows:
Table 2: 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., ‖Wd‖2 =√ k/s, ‖Wd‖F = √ p, and ‖Wd‖2,1 = p.
Generalization Bound CNNs Neyshabur et al. (2015) O ( 2D·p D 2
√ m ) Bartlett et al. (2017) Õ ( ( ks ) D−1 2 · √ D3p2
√ m ) Neyshabur et al. (2017) Õ ( ( ks ) D−1 2 · √ D3p2
√ m ) Golowich et al. (2017) Õ ( p D 2 min { 1 4√m , √ D m
}) Our results Õ ( ( ks ) D 2 √ Dk2
√ m
)
w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈Rpd−1− √ pd−1 .
Correspondingly, the stride size is s 2 d
kd on average and we have ‖Wd‖2 ≤ kd sd
if ∥∥w(j,i)∥∥
2 = 1 for all
i, j; see Appendix F for details. This is equivalent to permuting the columns of Wd 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 DC convolutional layers and DF fully connected layers. From the analysis in Corollary 2, when sd = kd for convolutional layers and ‖Wd‖2 = 1 for fully connected layers, we have that the overall ERC satisfies Õ ( R· √ DCk 2+DF pr
γ √ m
) .

heading: 4.2 RESNETS WITH STRUCTURED WEIGHT MATRICES
text: 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 VD = {Vd ∈ Rpd×qd} D d=1, UD = {Ud ∈ Rqd×pd−1} D d=1 as
FRND,‖·‖ = { f (VD,UD, x) ∈ RpD ∣∣ ‖Vd‖ ≤ BVd , ‖Ud‖ ≤ BUd}, (9) Given an input x ∈ Rp0 , the output of a D-layer ResNet is defined as f (VD,UD, x) = fVD,UD (· · · fV1,U1 (x)) ∈ RpD , where fVd,Ud (x) = σ (Vd · σ (Udx) + x). For any two layers i, j ∈ [D] and input x, we denote Jxi:j as the Jacobian from layer i to layer j, i.e., fVi,Uj (· · · fVi,Ui (x)) = Jxi: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.,
supWD ∥∥Jxi,i∥∥2 ≤ BJac,xi: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 1γ -Lipschitz and bounded loss function, i.e., |gγ | ≤ b, and F RN D,‖·‖2
be the ResNets defined in (9) with pd = p and qd = q for all d ∈ [D], BJac\d,2 = maxd∈[D],x∈Xm
BJac,x1:(d−1),2B Jac,x (d+1):D,2, and C
Net = BJac\d,2 maxd(BVd,2+BUd,2)R
√ m/q
supf∈FD,‖·‖2 ,x∈Xm gγ(f(VD,VD,x))
. Then the ERC satisfies
Rm ( Gγ ( FRND,‖·‖2 )) = O ( min { R· ∏D d=1(BVd,2BUd,2+1) γ , b } · √ Dpq·logCNet 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 (BVd,2BUd,2 + 1) dependence for each layer. When BVd,2 and BUd,2 are of order 1/ √ D, we still have ∏D d=1 (BVd,2BUd,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 forRm ( Gγ ( FRND,‖·‖F )) , we require BVd,F, BUd,F ≤ c, which leads to a much smaller parameter space than the space corresponding to BVd,2, BUd,2 ≤ c for the same c.

heading: 4.3 HYPERSPHERICAL NETWORKS
text: 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 = SWdWd, where SWd is a diagonal matrix with the i-th diagonal entries being the Euclidean norm of the i-th row of Wd. 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γ ( FSND,‖·‖2 )) =
Õ(R · ∏D d=1 BW̃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).

heading: 4.4 EXTENSION TO WIDTH-CHANGE OPERATIONS
text: Change 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} ∈ Rpd as the output of the d-th layer. Then we can use a transformation matrix Td ∈ Rpd+1×pd 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 fWd+1 ( x{d} ) = σ ( Wd+1Tdx
{d}). Denote the set of layers with width changes by IT ⊆ [D]. Combining with Theorem 1, we have that the ERC satisfies Rm ( Gγ ( FD,‖·‖2 )) = Õ ( R·ΠDd=1Bd,2·Πt∈IT ‖Tt‖2· √ Dpr γ √ m ) . Next, we illustrate several popular examples to show that Πt∈IT ‖Tt‖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 pd+1 = s · pd 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 Td ∈ Rspd×pd with (Td)ij = 1 if i = js, and (Td)ij = 0 otherwise. This implies that ‖Td‖2 = 1.
For 1 × 1 convolution, suppose that the convolution features are {c1, . . . , cs}. Then we expand width by performing convolution (essentially entry-wise product) using s features respectively. This is equivalent to setting Td ∈ Rspd×pd with (Td)ij = ck if i = j+(k−1)s for k ∈ [s], and (Td)ij = 0 otherwise. It implies that ‖Td‖2 = √∑s i=1 c 2 i . When ∑s i=1 c 2 i ≤ 1, we have ‖Td‖2 ≤ 1.
Width Reduction. Two popular types of width reduction are average pooling and max pooling. Suppose pd+1 = pds 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 Td ∈ R pd s ×pd with (Td)ij =
1/s if j = (i− 1)s+ k for k ∈ [s], and (Td)ij = 0 otherwise. This implies that ‖Td‖2 = √ 1/s.
For max pooling, we choose the largest entry in each nonoverlapping feature segment of length s. Denote the set Is = {(i− 1)× s+ 1, . . . , i · s}. This is equivalent to setting Td ∈ R pd s ×pd with (Td)ij = 1 if |(x{d})j | ≥ |(x{d})k| ∀ k ∈ Is, k 6= j, and (Td)ij = 0 otherwise. This implies that ‖Td‖2 = 1. For pooling with overlapping features, similar results hold.

heading: 4.5 NUMERICAL EVALUATION
text: 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) (Bound1), Neyshabur et al. (2017) (Bound2), and Golowich et al. (2017) (Bound3) by ignoring the common factor R
γ √ m as follows: • Ours: ΠDd=1Bd,2 √ k ∑D d=1 nd
• Bound1: ΠDd=1Bd,2 (∑D
d=1
B 2/3 d,2→1
B 2/3 d,2 )3/2 • Bound2: ΠDd=1Bd,2 √ D2p ∑D d=1 pdB 2 d,F
B2 d,2
• Bound3: ΠDd=1Bd,F √ D
105
1010
1015
Ours Bound1 Bound2 Bound3
} } }
}
0.99 0.98
0.81
0.26
0.92 0.91
0.76
0.23 Training Accuracy Testing Accuracy
1 1/5 1/25 1/100
Filter Norm
A cc
ur ac
y
0.07 0.07
0.05
0.03
(a) (b)
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.
Note that since we may have more filters nd than their dimension k, we do not assume orthogonality here. Thus we simply use the upper bounds of norms Bd rather than the form as in Table 2. Following the analysis of Theorem 1, we have √ k ∑D d=1 nd dependence rather than √ Dpr as k ∑D d=1 nd is the total number free parameter for CNNs, where nd 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 (a) that our result (104 ∼ 105) is significantly smaller than Bartlett et al. (2017); Neyshabur et al. (2017) (108 ∼ 109) and Golowich et al. (2017) (1014 ∼ 1015). As we have discussed, our bound benefits from tighter dependence on the dimensions. Note that k ∑D d=1 nd is approximately of order Dk
2, which is significantly smaller than (∑D d=1 B 2/3 d,2→1/B 2/3 d,2 )3 in Bartlett et al. (2017) and D2p∑Dd=1 pdB2d,F/B2d,2 in Neyshabur et al. (2017) (both are of order D3pr). 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γ ( FD,‖·‖F )) (or other existing bound)
attains the same order with our Rm ( Gγ ( FD,‖·‖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.

heading: A EXTENDED NUMERICAL RESULTS
text: 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 nd. Note that b = 1 in this case.
• Bound1: √ Dk ∑D d=1 rank(Wd) · nd. Note that their activation functions for the interme-
diate 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: maxx∈Xm ‖f(WD, x)‖2 · CDβ √∑D d=1 dk/se2 µ2dµ 2 d→ , where C = Ω(1) is the activa-
tion 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).
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 ≈ 102, while Zhou & Feng (2018) result in a bound of order > 103 and Arora et al. (2018) result in a bound of order > 104. 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 = Ω(104)). 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 BJAC\d,2 AND ∏ dBd,2
We demonstrate the empirical difference between BJac\d,2 and ∏ dBd,2. Using the same setting of the
network and dataset as above, we provide the empirical distribution of BJac\d,2 and ∏ dBd,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 BJac\d,2 are approximately 2 orders smaller than the values of∏ dBd,2, which support our claim that B Jac \d,2 is a tighter quantification then ∏ dBd,2.
A.3 DEPENDENCE OF BJAC\d,2 AND ∏ dBd,2 ON DEPTH
We further provide an empirical evaluation to see how strong the quantities BJac\d,2 and ∏ dBd,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 logBJac\d,2 and log ∏ dBd,2 in Figure 4. We also provide the plots
for log d and log d2 as reference. We can observe that log ∏ dBd,2 has an approximately linear dependence on the depth, which matches with our intuition. In terms of logBJac\d,2, we can see that it has a significantly slower increasing rate than log ∏ dBd,2. Compared with the reference plots log d and log d2, we can observe even a slower rate than log d2. This further indicates that logBJac\d,2 may has a dependence slower than some low degree of poly(d).

heading: B PROOF OF THEOREM 1
text: We start with some definitions of notations. Given a vector x ∈ Rp, we denote xi as the i-th entry, and xi:j as a sub-vector indexed from i-th to j-th entries of x. Given a matrix A ∈ Rn×m, we denote Aij as the entry corresponding to i-th row and j-th column, Ai∗ (A∗i) as the i-th row (column), AI1I2 as a submatrix of A indexed by the set of rows I1 ⊆ [n] and columns I2 ⊆ [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 (WD, x) in terms of the input x. Lemma 1. GivenWD, for any f (WD, ·) ∈ FD,‖·‖2 and x1, x2 ∈ R p0 , we have
‖f (WD, x1)− f (WD, x2)‖2 ≤ ‖x1 − x2‖2 · D∏ d=1 Bd.
Proof. We prove by induction. Specifically, we have
‖f (WD, x1)− f (WD, x2)‖2 = ‖σ (WDf (WD−1, x1))− σ (WDf (WD−1, x2))‖2 (i)
≤ ‖WDf (WD−1, x1)−WDf (WD−1, x2)‖2 ≤ ‖WD‖2 · ‖f (WD−1, x1)− f (WD−1, x2)‖2 ≤ BD · ‖f (WD−1, x1)− f (WD−1, x2)‖2 ,
where (i) comes from the entry-wise 1–Lipschitz continuity of σ(·). For the first layer, we have
‖f (W1, x1)− f (W1, x2)‖2 = ‖σ (W1x1)− σ (WDx2)‖2 ≤ ‖W1x1 −W1x2‖2 ≤ B1 · ‖x1 − x2‖2 .
By repeating the argument above, we complete the proof.
Next, we provide an upper bound for the Lipschitz constant of f (WD, x) in terms of the parameters WD.
Lemma 2. Given any x ∈ Rp0 satisfying ‖x‖2 ≤ R, for any f (WD, x) , f ( W̃D, x ) ∈ FD,‖·‖2
withWD = {Wd}Dd=1 and W̃D = { W̃d }D d=1 , and denoteBJac,x\d,2 = maxd∈[D]B Jac,x 1:(d−1),2B Jac,x (d+1):D,2, then we have ∥∥∥f (WD, x)− f (W̃D, x)∥∥∥ 2 ≤ BJac,x\d,2 ·R √ D √√√√ D∑ d=1 ‖Wd − W̃d‖2F. Proof. Given x and two sets of weight matrices {Wd}Dd=1, { W̃d }D d=1
, we have∥∥∥fWD (fWD−1 (· · · fW1 (x)))− fW̃D (fW̃D−1 (· · · fW̃1 (x)))∥∥∥2 (i) =
∥∥∥∥∥ D∑ d=1 fWD ( · · · fWd+1 ( f W̃d ( · · · f W̃1 (x) ))) − fWD ( · · · fWd ( f W̃d−1 ( · · · f W̃1 (x) )))∥∥∥∥∥
2 ≤ D∑ d=1 ∥∥∥fWD (· · · fWd+1 (fW̃d (· · · fW̃1 (x))))− fWD (· · · fWd (fW̃d−1 (· · · fW̃1 (x))))∥∥∥2 (ii) =
D∑ d=1 ∥∥∥Jx(d+1):D · fW̃d (· · · fW̃1 (x))− Jx(d+1):D · fWd (fW̃d−1 (· · · fW̃1 (x)))∥∥∥2 (iii)
≤ D∑ d=1 BJac,x(d+1):D · ∥∥∥W̃dfW̃d−1 (· · · fW̃1 (x))−WdfW̃d−1 (· · · fW̃1 (x))∥∥∥2
≤ D∑ d=1 BJac,x(d+1):D · ∥∥∥Wd − W̃d∥∥∥ 2 · ∥∥∥fW̃d−1 (· · · fW̃1 (x))∥∥∥2 , (10)
where (i) is derived from adding and subtracting intermediate neural network functions recurrently, where fWD ( · · · fWd+1 ( f W̃d ( · · · f W̃1 (x) ))) share the same output of activation functions from
d + 1-th layer to D-the layer with fWD ( fWD−1 (· · · fW1 (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
‖fWd (· · · fW1 (x))‖2 = ‖J x 1:d · x‖2 ≤ B Jac,x 1:d · ‖x‖2 . (11)
where (i) is from the entry-wise 1–Lipschitz continuity of σ(·) and (ii) is from recursively applying the same argument.
In addition, we denote Wd = UdV >d and W̃d = ŨdṼ > d , where Ud, Vd, Ũd, Ṽd ∈ Rp×r and ‖U‖2 = ‖V ‖2 = ∥∥∥Ũ∥∥∥ 2 = ∥∥∥Ṽ ∥∥∥
2 = ‖Wd‖1/22 . Then we have∥∥∥Wd − W̃d∥∥∥ 2 = ∥∥∥UdV >d − ŨdṼ >d ∥∥∥ 2
= ∥∥∥UdV >d − UdṼ >d + UdṼ >d − ŨdṼ >d ∥∥∥
2 ≤ ‖U‖2 ∥∥∥V − Ṽ ∥∥∥ 2 + ∥∥∥Ṽ ∥∥∥ 2 ∥∥∥U − Ũ∥∥∥ 2
≤ ‖Wd‖1/22 (∥∥∥V − Ṽ ∥∥∥ F + ∥∥∥U − Ũ∥∥∥ F ) . (12)
Applying (10) recursively and combining (11) and (12), we obtain the desired result as∥∥∥fWD (fWD−1 (· · · fW1 (x)))− fW̃D (fW̃D−1 (· · · fW̃1 (x)))∥∥∥2 ≤
D∑ d=1 BJac,x(d+1):D ·B Jac,x 1:(d−1) · ‖x‖2 · ‖Wd‖ 1/2 2 (∥∥∥V − Ṽ ∥∥∥ F + ∥∥∥U − Ũ∥∥∥ F ) ≤ BJac,x\d,2 ·R √ D ·max
d B
1/2 d,2 D∑ d=1 (∥∥∥V − Ṽ ∥∥∥ F + ∥∥∥U − Ũ∥∥∥ F )
≤ BJac,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 Lw-Lipschitz over w ∈ Rh with ‖w‖2 ≤ K and α = supg∈G,x∈Xm |g(w, x)|. Then the ERC of G = {g(w, x)} satisfies
Rm (G) = O
α √ h log KLw √ m α √ h√
m  . Proof. For any w, w̃ ∈ Rh and Xm = {xi}mi=1, we consider the matric ∆ (g1, g2) = maxxi∈Xm |g1(xi)− g2(xi)|, which satisfies
∆ (g1, g2) = max x∈Xm |g1(x)− g2(x)| = |g (w, x)− g (w̃, x)| ≤ Lw ‖w − w̃‖2 . (13)
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,∆, δ) ≤ (
3KLw δ
)h .
Then using the standard Dudley’s entropy integral bound on the ERC (Mohri et al., 2012), we have the ERC satisfies
Rm (G) . inf β>0 β + 1√ m ∫ supg∈G ∆(g,0) β √ logN (G,∆, δ) dδ. (14)
Since we have
α = sup g∈G,x∈Xm ∆ (g, 0) = sup g∈G,x∈Xm
|g(w, x)| .
Then we have
Rm (G) . inf β>0 β + 1√ m ∫ α β √ h log KLw δ 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 α = supf∈FD,‖·‖2 ,x∈Xm gγ (f (WD, x)). From Lemma 1 and 1 γ -Lipschitz continuity of g, we also have
α ≤ LxR γ ≤ R · ∏D d=1Bd,2 γ . (15)
From Lemma 2, we have
Lw ≤ max x∈Xm
BJac,x\d,2 ·R √
2D ·max d B 1/2 d,2 .
Moreover, when pd = p for all d ∈ [D], we have
K = √√√√ D∑ d=1 ‖Wd‖2F ≤ √ pD ·max d Bd,2.
Combining the results above with Lemma 3 and h = 2Dpr, we have Rm (G) . α √ h log KLw √ m α √ h√
m
.
R · ∏D d=1Bd,2 √ Dpr log BJac\d,2·R √ Dm/r·maxd Bd,2
supf∈FD,‖·‖2 ,x∈Xm gγ(f(WD,x))
γ √ m
.

heading: C PROOF OF COROLLARY 1
text: The analysis follows Theorem 1, except that the bound for α in (15) satisfies
α ≤ min { b, R · ∏D d=1Bd,2 γ } ,
since g satisfies |g| ≤ b and 1γ -Lipschitz continuous. Then we have the desired result.

heading: D PROOF OF COROLLARY 2
text: We first show that using unit norm filters for all d ∈ [D] and nd ≤ kd, we have ‖Wd‖2 = √ kd sd , (16) First note that when nd = kd, due to the orthogonality of { w(d,j) }kd j=1
, for all i, q ∈ [kd], i 6= q, we have
kd∑ j=1 ( w (d,j) i )2 = 1 and kd∑ j=1 w(d,j)q · w (d,j) i = 0. (17)
When nd = kd, we have for all i ∈ [pd−1], the diagonal entries of W>d Wd satisfy
( W>d Wd ) ii = kd∑ j=1 ∥∥∥(W (j)d )∗i∥∥∥2 = kd∑ j=1 kd sd∑ h=1 ( w (d,j) (i%sd)+(h−1)sd )2 (i) = kd sd . (18)
where (i) is from (17). For the off-diagonal entries of W>d Wd, i.e., for i 6= q, i, q ∈ [pd], we have( W>d Wd ) iq = kd∑ j=1 ( W (j) d )> ∗q ( W (j) d ) ∗i
= kd∑ j=1 kd sd∑ h=1 w (d,j) (i%sd)+(h−1)sd · w (d,j) (q%sd)+(h−1)sd
(i) = 0, (19)
where (i) is from (17). Combining (18) and (19), we have that W>d Wd is a diagonal matrix with∥∥W>d Wd∥∥2 = kdsd =⇒ ‖Wd‖2 = √ kd sd .
For nd < nk, we have that Wd is a row-wise submatrix of that when nd = kd, denoted as W̃d. Let S ∈ R ndkd sd ×pd be a row-wise submatrix of an identity matrix corresponding to sampling the row of
Wd to form W̃d. Then we have that (16) holds, and since∥∥∥W̃d∥∥∥ 2 = √∥∥S ·WdW>d · S>∥∥22 = √ kd sd .
Suppose k1 = · · · = kD = k for ease of discussion. Then following the same argument as in the proof of Theorem 1 and Lemma 3, we have
α = sup f∈FD,‖·‖2 ,x∈Xm
gγ (f (WD, x)) ≤ R · ∏D d=1Bd,2 γ = R · ∏D d=1 √ k sd γ ,
Lw ≤ max x∈Xm
BJac,x\d,2 ·R √ 2Dk/s,
K = √√√√ D∑ d=1 nd∑ j=1 ∥∥w(d,j)∥∥2 2 = √√√√ D∑ d=1 nd, and
h = k D∑ d=1 nd.
Using the fact that the number of parameters in each layer is no more than knd rather than 2pr, we have
Rm (G) . α √ h log KLw √ m α √ h√
m
.
R · ∏D d=1 √ k sd · √ k ∑D d=1 nd log
BJac\d,2·R √ Dm/s
supf∈FD,‖·‖2 ,x∈Xm gγ(f(WD,x))
γ √ m
.

heading: E PROOF OF COROLLARY 3
text: 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 (VD,UD, x) in terms of x.
Lemma 4. Given VD and UD, for any f (VD,UD, ·) ∈ FD,‖·‖2 and x1, x2 ∈ R p0 , we have
‖f (VD,UD, x1)− f (VD,UD, x2)‖2 ≤ ‖x1 − x2‖2 ·Π D d=1 (BUd,2BVd,2 + 1) . (20)
Proof. Consider the ResNet layer, for any x1, x2 ∈ Rk, we have
‖f (VD,UD, x1)− f (VD,UD, x2)‖2 = ‖fVD,UD (· · · fV1,U1 (x1))− fVD,UD (· · · fV1,U1 (x2))‖2 = ∥∥σ (VD · σ (UD · fVD−1,UD−1 (· · · fV1,U1 (x1)))+ fVD−1,UD−1 (· · · fV1,U1 (x1)))
− σ ( VD · σ ( UD · fVD−1,UD−1 (· · · fV1,U1 (x2)) ) + fVD−1,UD−1 (· · · fV1,U1 (x2)) ) ∥∥ 2
(i) ≤ ∥∥VD · σ (UD · fVD−1,UD−1 (· · · fV1,U1 (x1)))− VD · σ (UD · fVD−1,UD−1 (· · · fV1,U1 (x2)))∥∥2
+ ∥∥fVD−1,UD−1 (· · · fV1,U1 (x1))− fVD−1,UD−1 (· · · fV1,U1 (x2))∥∥2
(ii) ≤ (‖VD‖2 ‖UD‖2 + 1) · ∥∥fVD−1,UD−1 (· · · fV1,U1 (x1))− fVD−1,UD−1 (· · · fV1,U1 (x2))∥∥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 (VD,UD, x) in terms of VD and UD. Lemma 5. Given any x ∈ Rp0 satisfying ‖x‖2 ≤ R, for any f (VD,UD, x) , f ( ṼD, ŨD, x ) ∈
FD,‖·‖2 with VD = {Vd} D d=1, UD = {Ud} D d=1 ,ṼD =
{ Ṽd }D d=1 , and ŨD = { Ũd }D d=1 , and denote
BJac,x\d,2 = maxd∈[D]B Jac,x 1:(d−1),2B Jac,x (d+1):D,2, then we have
∥∥∥f (VD,UD, x)− f (ṼD, ŨD, x)∥∥∥ 2
≤ BJac,x\d,2 maxd (BVd,2 +BUd,2)R √ 2D · √√√√ D∑ d=1 ∥∥∥VD − ṼD∥∥∥2 F + D∑ d=1 ∥∥∥UD − ŨD∥∥∥2 F .
Proof. Given x and two sets of weight matrices {Wd}Dd=1, { W̃d }D d=1
, we have∥∥∥fVD,UD (fVD−1,UD−1 (· · · fV1,U1 (x)))− fṼD,ŨD (fṼD−1,ŨD−1 (· · · fṼ1,Ũ1 (x)))∥∥∥2 ≤
∥∥∥∥∥ D∑ d=1 fVD,UD ( · · · fVd+1,Ud+1 ( fṼd,Ũd (· · · ) )) − fVD,UD ( · · · fVd+1,Ud+1 ( fṼd,Ud (· · · ) )) + fVD,UD ( · · · fVd+1,Ud+1 ( fṼd,Ud (· · · ) )) − fVD,UD ( · · · fVd,Ud ( fṼd−1,Ũd−1 (· · · ) ))∥∥∥∥∥ 2
≤ D∑ d=1 ∥∥∥fVD,UD (· · · fVd+1,Ud+1 (fṼd,Ũd (· · · )))− fVD,UD (· · · fVd+1,Ud+1 (fṼd,Ud (· · · )))∥∥∥2 +
D∑ d=1 ∥∥∥fVD,UD (· · · fVd+1,Ud+1 (fṼd,Ud (· · · )))− fVD,UD (· · · fVd,Ud (fṼd−1,Ũd−1 (· · · )))∥∥∥2 =
D∑ d=1 ∥∥∥Jx(d+1):D · fṼd,Ũd (fṼd−1,Ũd−1 (· · · ))− Jx(d+1):D · fṼd,Ud (fṼd−1,Ũd−1 (· · · ))∥∥∥2 +
D∑ d=1 ∥∥∥Jx(d+1):D · fṼd,Ud (fṼd−1,Ũd−1 (· · · ))− Jx(d+1):D · fVd,Ud (fṼd−1,Ũd−1 (· · · ))∥∥∥2 ≤
D∑ d=1 BJac,x(d+1):D · ∥∥∥fṼd,Ũd (fṼd−1,Ũd−1 (· · · ))− fṼd,Ud (fṼd−1,Ũd−1 (· · · ))∥∥∥2
+ D∑ d=1 BJac,x(d+1):D · ∥∥∥fṼd,Ud (fṼd−1,Ũd−1 (· · · ))− fVd,Ud (fṼd−1,Ũd−1 (· · · ))∥∥∥2
(i) ≤ D∑ d=1 BJac,x(d+1):D · ∥∥∥Ṽdσ (Ũd · fṼd−1,Ũd−1 (· · · ))− Ṽdσ (Ud · fṼd−1,Ũd−1 (· · · ))∥∥∥2
+ D∑ d=1 BJac,x(d+1):D · ∥∥∥Ṽdσ (Ud · fṼd−1,Ũd−1 (· · · ))− Vdσ (Ud · fṼd−1,Ũd−1 (· · · ))∥∥∥2
(ii) ≤ D∑ d=1 BJac,x(d+1):D · (∥∥∥Ud − Ũd∥∥∥ 2 ‖Vd‖2 + ∥∥∥Vd − Ṽd∥∥∥ 2 ‖Ud‖2 )∥∥∥fṼd−1,Ũd−1 (· · · )∥∥∥2 , (21) where (i) and (ii) from the entry-wise 1–Lipschitz continuity of σ(·). In addition, for any d ∈ [D], we further have ∥∥∥fṼd−1,Ũd−1 (· · · fṼ1,Ũ1 (x))∥∥∥2 = ‖Jx1:d · x‖2 ≤ BJac,x1:(d−1) · ‖x‖2 . (22) Combining (21) and (22), we obtain∥∥∥fVD,UD (· · · fV1,U1 (x))− fṼD,ŨD (· · · fṼ1,Ũ1 (x))∥∥∥2
≤ D∑ d=1 BJac,x(d+1):D ·B Jac,x 1:(d−1) · ‖x‖2 · (∥∥∥Vd − Ṽd∥∥∥ F · ‖Ud‖2 + ∥∥∥Ud − Ũd∥∥∥ F · ∥∥∥Ṽd∥∥∥ 2 ) ≤ BJac,x\d,2 maxd (BVd,2 +BUd,2)R D∑ d=1 · (∥∥∥Vd − Ṽd∥∥∥ F + ∥∥∥Ud − Ũd∥∥∥ F )
≤ BJac,x\d,2 maxd (BVd,2 +BUd,2)R √ 2D · √√√√ D∑ d=1 ∥∥∥VD − ṼD∥∥∥2 F + D∑ d=1 ∥∥∥UD − ŨD∥∥∥2 F .
On the other hand, for any d ∈ [D], we have
‖fVd,Ud (· · · fV1,U1 (x))‖2 (i) ≤ ‖Vd‖2 ‖Ud‖2 · ∥∥fVd−1,Ud−1 (· · · fV1,U1 (x))∥∥2 + ∥∥fVd−1,Ud−1 (· · · fV1,U1 (x))∥∥2
(ii) ≤ d∏ i=1 (‖Vi‖2 ‖Ui‖2 + 1) · ‖x‖2 . (23)
where (i) is from the entry-wise 1–Lipschitz continuity of σ(·) and (ii) is from recursively applying the same argument.
Let p1 = · · · = pD = p and q1 = · · · = qD = q. Then following the same argument as in the proof of Theorem 1 and (23), we have
α = sup f∈FD,‖·‖2 ,x∈Xm
gγ (f (VD,VD, x)) ≤ R · ∏D d=1 (BVd,2BUd,2 + 1)
γ ,
Lw ≤ max x∈Xm BJac,x\d,2 maxd (BVd,2 +BUd,2)R
√ 2D,
K = √√√√ D∑ d=1 ‖Vd‖2F + ‖Ud‖ 2 F ≤ √ pD ·max d (BVd,2 +BUd,2) , and h = 2Dpq,
Combining Lemma 3, and Lemma 4, Lemma 5, we have
Rm (G) . α √ h log KLw √ m α √ h√
m
≤ R · ∏D d=1 (BVd,2BUd,2 + 1) ·
√ Dpq · log ( BJac\d,2 maxd(BVd,2+BUd,2)R √ m/q
supf∈FD,‖·‖2 ,x∈Xm gγ(f(VD,VD,x)) ) γ √ m .
F SPECTRAL BOUND FOR Wd IN CNNS WITH MATRIX FILTERS
We provide further discussion on the upper bound of the spectral norm for the weight matrix Wd in CNNs with matrix filters. In particular, by denoting Wd using submatrices as in (7), i.e.,
Wd = [ W (1)> d · · · W (nd)> d ]> ∈ Rpd×pd−1 ,
we have that each block matrix W (j)d is of the form
W (j) d =  W (j) d (1, 1) W (j) d (1, 2) · · · W (j) d ( 1, √ pd−1 ) W (j) d (2, 1) W (j) d (2, 2) · · · W (j) d ( 2, √ pd−1 ) ... ... . . . ...
W (j) d (√ pd−1kd sd , 1 ) W (j) d (√ pd−1kd sd , 2 ) · · · W (j)d (√ pd−1kd sd , √ pd−1 )  , (24)
where W (j)d (i, l) ∈ R √ pd−1kd sd ×√pd−1 for all i ∈ [√ pd−1kd sd ] and l ∈ [√ pd−1 ] . Particularly, off-
diagonal blocks are zero matrices, i.e., W (j)d (i, l) = 0 for i 6= l. For diagonal blocks, we have
W (j) d (i, i) =  w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd 0 · · · 0︸ ︷︷ ︸ ∈R sd√ kd w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · ·0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd− sd√ kd ... w
(j,1){ sd√ kd } 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · · · · · · · ·0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd w (j,1) { sd1 }
 .
(25)
where w(j,1){ sd1 } = w (j,1)
1: sd√ kd
∈ R sd√ kd and w(j,1){
sd√ kd
} = w(j,1)(√ kd−
sd√ kd +1
) : √ kd ∈ R sd√ kd . Combining (24)
and (25), we have that the stride for W (j)d is s2d kd . Using the same analysis for Corollary 2. We have ‖Wd‖2 = 1 if √∑ i ∥∥w(j,i)∥∥2 2 = kdsd .
For image inputs, we need an even smaller matrix W (j)d (i, i) with fewer rows than (25), denoted as
W (j) d (i, i) =  w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd 0 · · · 0︸ ︷︷ ︸ ∈R sd√ kd w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · ·0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd− sd√ kd ... 0 · · · · · · · · · · · · · · · · · · 0︸ ︷︷ ︸
∈R
√ pd−1 kd − √ kd
w(j,1)︸ ︷︷ ︸ ∈R √ kd 0 · · · · · · · · · · · · · · · 0︸ ︷︷ ︸ ∈R √ pd−1 kd − √ kd · · · · · · · · · · · · · · ·w(j, √ kd)︸ ︷︷ ︸ ∈R √ kd
 .
(26) Then ‖Wd‖2 ≤ 1 still holds if √∑ i ∥∥w(j,i)∥∥2 2
= kdsd since Wd generated using (26) is a submatrix of Wd generated using (25).

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