Theoretical Investigation of Generalization Bound for Residual Networks

1 Introduction

Deep neural networks have been applied to many fields, including computer vision, speech recognition, natural language processing, audio recognition, social network filtering, machine translation, and more. Since ResNets have been introduced to improve imagin recognition [He et al., 2016], [Goodfellow et al., 2016], ResNets have taken the deep learning world by storm. Though the robustness and efficiency of ResNets has proven to be enormously successful in various artificial intelligence tasks [Huang et al., 2017], [Srivastava et al., 2015], [Fan et al., 2018], we aim to examine the capacity of ResNets theoretically. Previous studies have investigated the capacity of several simple network structures, such as unregularized DNN, DNN without bias or DNN with ReLU active functions [Bartlett et al., 2017], [Golowich et al., 2018a], [Neyshabur et al., 2017], [Neyshabur et al., 2015], [Sun et al., 2016], [Shalev-Shwartz and Ben-David, 2014] .

∗These authors have contributed equally to this work. The order of name is alphabetical.

†Corresponding Author.

ResNets and other powerful structures, however, require further explorations in literature.

Intuitively, great robustness should be compatible with relatively small generalization bounds. Inspired by the amazing performance of ResNets in regression problems, we hope to answer a central question : can we find a tighter generalization bound for ResNets and other developed structures ?

In this paper, we focus on providing a tighter generalization bound with respect to ℓp,q-norm for ResNets. Since most prior studies are restricted to simple DNN structures [Golowich et al., 2018b], [Bartlett et al., 2017], [Neyshabur et al., 2017], [Sun et al., 2016], we take the layer-wise weight normalization and hidden layers with bias into consideration to pursue a more general sight. After showing comparisions with some related works , further discussions extend the parallel conclusions to DNN cases.

We first formulate the function class, which is derived from the combination of Residual-Blocks, and define the ℓp,qweight normalization. After providing an upper bound for the Rademacher Complexity for the ResNets function class, we induce the generalization bound with respect to regression problems. In particular, we obtain a width-free generalization bound with 1/p + 1/q ⩾ 1; therefore, several prior conclusions under ℓ2,2-norm, ℓ1,∞-norm are covered. By utilizing the same method, we extend the width-free generalization bound to DNN and Convolutional-ResNets nontrivialy.

The contributions of this paper are summarized as follows : 1. We obtain a tighter generalization bound for ResNets with layer-wise ℓp,q-normalization and bias; 2. We justify the tightness by comparing the results with related works; 3. We extend the parallel conclusions to structures, including DNN and Convolutional-ResNets.

In Section 2, we introduce some notations as well as the formulation of the ResNets function class. To prepare for the main result, we provide the upper bound of the Rademacher Complexity for the ResNets function class. Section 4 discusses the generalization bound for ResNets and several comparisions. We explore the parallel conclusions of DNN and Convolutonal-ResNets in Section 5 and Section 6, respectively. In Section 7, numerical experiments are explained to verify the previous theoretical results. The proof details are concluded in the supplementary materials.[Mo and Chen, 2019]

2 Preliminary

Traditionally, ResNets refer to networks with forms similar to Figure 1: By adding bias to each hidden layers, we obtain a representation of the mapping of a single residual-block as :

Fi : Rdi-1,2 → Rdi,2 . The bias is forced to be commensurate with the weight matrix in terms of dimension. In order to simplify Fi, we rewrite the function as:

By denoting every ˜xi ≜ (xi 1 ), Mi,j ≜ (Wi,j, bi,j), ˜MTi,j ≜ (MTi,j , eTdi )T , ∀i = 1, ..., k and j = 1, 2, eTdi the dith natural basis, we rewrite ˜ Fi : Rdi-1,2+1 →Rdi,2+1 as:

The introduced notations are unambiguous:

(1) Mi,2,Mi,1: Mi,2 ∈ Rdi,2×di,1 ,Mi,1 ∈ Rdi,1×di-1,2 . (2) Ii: Ii ∈ Rdi,2×di-1,2 , instead of the Identity matrix, Ii is introduced to ensure that Ii · ˜xi-1 is commensurate with Mi,2 · σ [Mi,1 · ˜xi-1] in terms of dimension.

(3) σ [·]: A ρ-lipschitz continuous active function.

(4) ℓp,q-norm: The ℓp,q-norm of a n×mmatrix A is defined

We denote the last weight layer as ˜ Fk+1 : Rdk,2+1 → Rdk+1+1 and the corresponding matrix is defined as Mk+1 ∈

Rdk+1×(dk,2+1) , where Mk+1 ≜ (Wk+1, bk+1). With ℓp,qnorm, the weight matrixes {Mi,1,Mi,2}ki=1 , Mk+1 are constrained by ∥Mi,2∥ ⩽ ci,2, ∥Mi,1∥p,q ⩽ ci,1, ∀i = 1, . . . , k; ∥Mk+1∥p,q ⩽ ck+1. The discussion above induces a function class called the Weight-NormalizedResidual-Network class, which contains elements that can be represented by combining residual-blocks.

Definition 2.1. RN k,d p,q,c This definition depicts a class of functions that can be represented by the previously mentioned WN-RN structure.

p, q: The norm is set as ℓp,q-norm

d: d ≜ (dk+1, dk,2, dk,1 . . . , d1,2, d1,1, d0) is a vector with width information. We denote di,1, di,2 as the width of the 1st and 2nd layer of the ith residual block, respectively.

By definition, the following theorem is obvious:

Theorem 2.2. The property of RN k,d p,q,c .

Given p, q, c(1) , c(2) , k1, k2, and vectors d(1) , d(2) with k1 ⩽ k2, d(1) ⩽ d(2) , c(1) ⩽ c(2) w.r.t, the components precede the k1th component:

Intuitively, a shallow and thin ResNet can be represented by a relative deeper and wider one.

3 The Estimation of the Rademacher Complexity for RN n,d p,q,c

In this section, we provide an upper bound for the Rademacher Complexity of RN k,d p,q,c .

Definition 3.1. Rademacher Compexity of a function class. Assume that f is a real value function, ϵi is the Rademacher Random Variable:

(1) Empirical Rademacher Compexity:

(2) Rademacher Compexity:

Without a loss of generality, we consider the input space as X ≜ {x ∈ Rd0 | ∥x∥p∗ ⩽ 1}. Moreover, we assume dk+1 = 1, so that the Rademacher Complexity is well defined.

Theorem 3.2. The Rademacher Complexity of RN k,d p,q,c . If p ⩾ 1, q ⩾ 1, k ⩾ 0 and c > 0, ρ is the lipschitz constant of the active function; di,j ∈ N+, ∀i = 1, . . . , k, j = 1, 2.

We prepare this theorem for the main result. According to [Mohri et al., 2012], the generalization bound can be deduced from the upper bound of the Rademacher Complexity.

4 The Generalization Bound for Weight-Normalized-ResNets

In this section, we provide an estimation for the generalization bound in the data regression problem. With ℓp,q-norm satisfying 1p + 1q ⩾ 1, the estimation has a more laconic form.

The Regression Problem

S ≜ {(x1, y1), ...(xn, yn)} ∼ D are i.i.d samples in X ×Y ⊂ Rd0+1 . We are interested in finding h : X → Y in order to satisfy yi = h(xi) + εi, ∀i = 1, ..., n, where εi represents independent noise. To evaluate the choice of h, we introduce the loss function class :

Definition 4.1. Loss Function Class RG k,d p,q,c :

If we assume that ∀g ∈ RG k,d p,q,c : Y × Y → [0, 1] is a γ-Lipschitz function, the Loss Function Class is denoted as RGγ ≜ {g is γ-Lipschitz| g ∈ RG k,d p,q,c }.

By definition 4.1, since the first variable of a loss function g(f(x), y), that is, f(x), belongs to ResNets, connection matrixes of g are the same as the ones of f ∈ RN k,d p,q,c . Hence, we omit the repetitious discussions. In fact, for generalization bound, the only contribution from loss function class is its Lipschitz-constant: γ. We discuss the choice of γ after the main results.

Definition 4.2. Generalization Error:

If ∀g ∈ RGγ, the true risk and the empirical risk is defined as:

The true risk: ED[g] ≜ E(x,y)∼D [g(x, y)] ,

The generalization error is the deviation between the expected and the empirical error:

Generalization bound is an upper bound for generalization error. Intuitively, high generalization error indicates that the model is overfitting. Hence, generalization bound guarantees generalization error to be lower than a controllable level. In other words, generalization bound provides us with an explicit guidance to avoid overfitting. A tight generalization bound promises that a network can fit the unseen data well.

4.1 Main Results

Theorem 4.3. Estimation of Generalization Bound:

We assume that z ≜ (x, y) ∼ D, S ≜ {z1, ..., zn} is a dataset with n i.i.d samples selected from the distribution D. Then, we fix δ ∈ (0, 1), ∀k ∈ N+, ∀di,j ∈ N+ i = 1, ..., k, j = 1, 2. With probability of at least 1 - δ over the generation of S, it holds that:

According to the given conditions in theorem 4.3, we assume that the range of our loss function is an interval [a, a+1] (we set a > 0). For MSE, namely L(v1, v2) = |v1 - v2|2 , γ can be chosen as √a + 1. Similarly, we set γ as 1 when we adopt MAE, that is |v1-v2|. In fact, we can bound the derivative of loss function and hence obtain γ. Generally, since the training data (xi, yi) and f(xi) are finite (by definition 4.1), we can rescale the range of L(f(x), y) to be [a, a+1]. In this way, the case is reduced to the previous one.

The rescaling process implies that, once the loss value is small, the γ can be small, so do generalization bound. γ is a relative value to generalization bound and it contributes little effect to generalization bound. Hence, our work focuses on the dominate terms in generalization bound.

When weight matrixes are normalized with respect to the Frobenius norm, we set p = q = 2. Moreover, when we set 1/p + 1/q ⩾ 1, the bound is reduced to a laconic form.

We assume that z ≜ (x, y) ∼ D, S ≜ {z1, ..., zn} is a dataset with n i.i.d samples selected from the distribution D. Then, we fix δ ∈ (0, 1), ∀k ∈ N+, ∀di,j ∈ N+ i = 1, ..., k, j = 1, 2. With probability of at least 1 - δ over the generation of S, it holds that:

More generally, if the ith residual-block contains hi layers, with the ℓp,q-norm bound of each block set as ∥Mi,j∥p,q ⩽ ci,j, ∀j = 1, 2, · · · , hi, then there is a similar result.

Corollary 4.5. Generalization Bound in General Cases.

We assume that z ≜ (x, y) ∼ D, S ≜ {z1, ..., zn} is a dataset with m i.i.d samples selected from the distribution D. Then, we fix δ ∈ (0, 1), ∀k ∈ N+, ∀di,j ∈ N+, j = 1, ..., hi, i = 1, ..., k. With probability of at least 1 - δ over the generation of S, it holds that:

where s0 = d 1 p∗ 0 , for i = 1, 2, · · · , k,

When we set ReLU or another homogeneity functions as activation functions, the corresponding upper bounds {ci,j}hi j=1 and {c′i,j }hi j=1 hold ∏hi j=1 ci,j = ∏hi j=1 c′i,j . We can obtain a tighter bound with s0 = d 1 p∗ 0 , si = ( ∏hi j=1 ci,j +1)si-1 +∏hi l=1 ci,l, ∀i = 1, 2, · · · , k, by taking ci,hi , · · · , ci,2 → 0+.

4.2 Comparisons

We focus on the term Rn(RGγ) with p = q = 2, ρ = 1:

A recent conclusion [Li et al., 2018] argues that:

Rn(RGγ)

where Bj,i is the upper bound of ∥Mj,i∥2,2 with bias bj,i = 0, j = 1, ..., k; i = 1, 2. The widths of the 1st and 2nd layer in the jth residual-block are denoted as d1, d2, respectively. Since cj ⩽ Bj,1Bj,2, ∀j = 1, ..., k , we obtain a tighter generalization bound for the ResNets structures with bias, which can be extended from the Frobenius Norm to a general ℓp,qnorm. In particular, ∀p, q s.t. 1/p + 1/q ⩾ 1 can reduce the generalization bound to a more laconic form .

The comparison shows that our generalization bound is tighter than [Li et al., 2018]'s , which is the tightest previous generalization bound for ResNets and DNN. Comparisons between [Li et al., 2018]'s work and previous work are included in that paper. While [Li et al., 2018]'s work is restricted to Frobenius-norm, we generally obtain generalization bound with respect to ℓp,q-norm.

5 Parallel Extensions forWeight-Normalized DNN

Using the same methods, our conclusions can be extended to Deep Neural Networks. We introduce the definition of the DNN function class as, ˜ Ti : Rdi-1+1 → Rdi+1 , ˜ Ti((x1)) ≜ σ[(Wi bi 0 1 ) · (x1)], ∀x ∈ Rdi-1 .

We also introduce the notation as, Ui ≜ (Wi bi 0 1 ). By

˜

sharing several notations Fk+1,Mk+1, c, d, k, n, we obtain the parallel definitions:

Definition 5.1. N k,d p,q,c This definition describes the class of functions f that can be represented by DNN.

p, q: The norm is set as ℓp,q-norm.

d: d = (dk+1, . . . , d1, d0) is a vector with width information. c: c ≜ (ck+1, ck, ck-1, ..., c1), where ∥Ui∥p,q ⩽ ci, ∀i = 1, . . . , k + 1;

Theorem 5.2. The properties of N k,d p,q,c

Since we have p, q, c(1) , c(2) , k1, k2 and vectors d(1) , d(2) with k1 ⩽ k2, d(1) ⩽ d(2) , c(1) ⩽ c(2) w.r.t the components precede the k1th component:

Definition 5.3. The Loss Function Class G k,d p,q,c .

G k,d p,q,c ≜ {g(f(x), y) ∈ R| x ∈ X, y ∈ Y, f ∈ N k,d p,q,c }. If we assume that ∀g ∈ G k,d p,q,c : Y × Y → [0, 1] is a γ-Lipschitz function, the Loss Function Class is denoted as Gγ ≜ {g is γ-Lipschitz| g ∈ G k,d p,q,c }.

Theorem 5.4. An Estimation of Generalization Bound.

We assume that z ≜ (x, y) ∼ D, S ≜ {z1, ..., zn} is a dataset with m i.i.d samples selected from the distribution D. Then, we fix δ ∈ (0, 1), ∀k ∈ N+, ∀di ∈ N+ i = 1, ..., k. With probability of at least 1 - δ over the generation of

holds that:

Corollary 5.5. The Generalization Bound with 1p + 1q ⩾ 1. We assume that z ≜ (x, y) ∼ D, S ≜ {z1, ..., zn} is a dataset with n i.i.d samples selected from the distribution D. Then, we fix δ ∈ (0, 1), ∀k ∈ N+, ∀di ∈ N+ i = 1, ..., k. With probability of at least 1 - δ over the generation of S, it holds that::

With ReLU as activation function, we obtain:

Comparisions:

We focus on the term Rn(Gγ) with p = q = 2, ρ = 1 :

A recent conclusion [Li et al., 2018] argues that:

Rn(Gγ)

where Bj is the upper bound of the corresponding ∥Uj∥p,q, with bias bj = 0, j = 1, ..., k; i = 1, 2. The widths of the jth layer is denoted as d. We obtain a tighter generalization bound for DNN structures with bias, which can be extended from the Frobenius Norm (p = q = 2) to a general ℓp,q-norm.

For DNN, our result is tighter than [Xu andWang, 2018]'s, since our 2(k + 2)log2 is smaller than their (k + 1)log16. Moreover, the normalization bounds {ci}ki=1 need not to be the same value and the weight normalization constrains are inequalities rather than equalities. Hence, our generalization bound is tighter and more general than Xu Y's.

6 Parallel Extensions for Kernel-Normalized CNN

Our conclusions can be extended to CNN cases, since a convolutional connection is tantamount to a full connection with sparse matrix. In this section, we represent the CNN structure by reducing the convolution blocks to a combination of linear functions and active functions.

In image recognition tasks, we feed a CNN with image data (pixel matrixes and RGB channels). To obtain a similar form as Section 4 and 5, we reshape the input matrixes for each layers as vectors. In practice, we rarely adopt networks that consist only of convolutional connection blocks. Without a loss of generality, we focus on a single convolution connection block. Hence, we introduce the following notations.

Definition 6.1. The size of input image: w1 ×w2, The number of input and output channels: vin, vout, The size of kernels: u.

For convenience, we reshape the image data as: x[l] = imagem3 [m2][m1], for l = (m3 - 1)w1w2 + (m2 - 1)w1 + m1, 1 ⩽ m1 ⩽ vin, 1 ⩽ m2 ⩽ w2, 1 ⩽ m3 ⩽ w1. This suggests that x[l] corresponds to the element at the m1th row and m2th column of the kernel in the m3th channel. Thus, we define the row of the weight matrix as:

where K(m1,k) is the m1th kernel in kth channel,

By definition, the ℓp-norm of V(k) i,j is ∥(K(1,k) ,K(2,k) , . . . ,K(vin,k) )∥p. With a fixed value for k, there are w1w2 rows; therefore, we can represent the ℓp,q-norm of matrixM as:

If we constraint each kernel as ∥K∥p ⩽ ˆ c , then

In these cases, we prefer kernel normalization to weight normalization. By substituting the normalization-bound c in Chapter 3 with (vinˆ cp + 1) 1p (w1w2) 1 q , we extend our conclusion to apply to CNN cases. Moreover, c can be rewritten as ˆ c(vin) 1p (w1w2) 1 q when we set the bias as 0.

7 Numerical Experiments

In this section, we discuss numerical experiments that implies the generalization properties of ResNets is better than DNN's. In particular, we train two simple networks to solve a regression problem and calculate the generalization bound for the networks. While both of the networks share the same initialization and parameters, a residual shortcut is added to the second network.

Intuitively, we hypothesize that ResNets has the capacity to generalize better than DNN.

7.1 Experiment Settings

Dataset

We convey our experiment on a non-linear regression problem: y = 1 1+exp(-t) , t = 1T x+ cos(1T x). We sample 500 random samples {(xi, yi)}500 i=1 ⊂ R300 × R for training set, and 1500 samples for testing set from the following procedure.

1. Independently sample an auxiliary variable zi ∈ R300 from N(0, I).
2. Generate xi by xi[1] = zi[1], xi[j] = zi[j]+0.2(zi[j1] + zi[j + 1]), for j = 2, ..., 300.
3. Compute yi = 1 1+exp(-ti) , ti = 1T xi + cos(1T xi) for i = 1, ..., 500 (for i = 1, ..., 1500 for test dataset).

Network Model

We first set Net-A and Net-B as two fully connected DNNs with four hidden layers. Then, we add a residual shortcut to Net-B between the second layer and the third one. The parameters are shown in Figure 2. Through the course of several experiments, we found that the choice of widths did not affect the general conclusion; hence, we selected the width parameters arbitrarily.

We first initialize the weights of Net-A by the Xavier Initialization and set all the bias components as 0.1, as the choice in bias does not greatly affect the conclusion. As a control group, Net-B shares all the initialized parameters with NetA. We vary the scale of the initialization before training by dividing the weights from the Xavier Initialization by the 'scale'. Then, we adopt Mean Square Loss as loss function and ReLU as active functions.

After training Net-A and Net-B with the same strategy, we calculate the ℓ2,2-norm of their weights, respectively. By Thereom 4.3, 5.4, we compare the generalization bound of the two models (AGB and BGB for short). AGB > BGB suggests that the ResNets structure has a relatively lower generalization bound while the testing error of Net-A and Net-B are close. We obtain evidence that supports our hypothesis by setting the scale as 10, 15, 20, 25, and other larger numbers. For each scale, we repeat the experiment for fifty times.

7.2 Results

In Figure 3, we display a representative result where the scale is set as 10. The rest of experiment data is concluded in the supplementary material [Mo and Chen, 2019].

The results suggest that ResNet structure has a lower generalization bound than DNN, while the test error of two models are close (more than 95% of the data holds AGB > BGB). The experiment implies that the ResNets structure contributes to better generalization properties.

8 Conclusion

8.1 Guidance on parameters to avoid overfitting

According to theorem 4.3, the following settings can improve the network structures' generalization capacity: (1).1/p + 1/q >= 1; (2).As the p,q-norm of each matrix Mi is constrained to be less than ci, we can set ci as constants that small enough to force generalization bound to be a small value; (3).The residual connection structures (short cut) render the generalization bound smaller, which explains why ResNets generalizes better than DNN does.

8.2 Future work

With the guidance, we can develop efficient algorithms to train Weight-Normalized networks with small generalization bound. In the future, we will focus on the generalization bound when it is restricted on a smaller function space (i.e. a vicinity of a local maximal solution) for further exploration of the generalization properties.

Acknowledgments

We would like to thank the anonymous reviewers for their comments and suggestions which greatly improve the manuscript. The work is supported by the NSF of China (No. 11871447), and Anhui Initiative in Quantum Information Technologies (AHY150200).