{'fraction_non_alphanumeric': 0.060690571049136784, 'fraction_numerical': 0.01759628154050465, 'mean_word_length': 3.9233409610983982, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complexity Measures for Neural Networks with General Activation Functions Using Path-based Norms

A simple approach is proposed to obtain complexity controls for neural networks with general activation functions. The approach is motivated by approximating the general activation functions with one-dimensional ReLU networks, which reduces the problem to the complexity controls of ReLU networks. Specifically, we consider two-layer networks and deep residual networks, for which path-based norms are derived to control complexities. We also provide preliminary analyses of the function spaces induced by these norms and a priori estimates of the corresponding regularized estimators.


Introduction
Norm-based complexity measures have played an essential role in analyzing the generalization ability of machine learning models. For example, a variety of norms have been explored for linear models, such as the ℓ 1 norm for LASSO and ℓ 2 norm for ridge regression. A good choice of the norm can help design good regularization strategies and provide accurate estimate of the model's error on test data. In deep learning, norm-based complexity measures are especially crucial, since neural networks used in practice are always over-parameterized, in which case measures depending on the network size inevitably lead to vacuous generalization bounds. In contrast, norm-based measures are able to provide size-independent controls of the model's complexity.
The work [16] obtained the first norm-based controls for multilayer fully-connected networks with ReLU activation functions via pure Rademacher complexity-based analysis.
[5] later generalized the result to deep residual networks. [2] provided a covering number-based approach to obtain similar results for fully connected networks. All the complexity measures identified in these work are certain path-based norms. [8,5,6,7] further developed the approximation and estimation theories for function spaces induced by these norms. However, all these results are limited to activation functions with the positive homogeneity property, such as ReLU and leaky ReLU [11]. In this work, we aim to extend these results to neural networks with general activation functions, since activation functions other than ReLU and leaky-ReLU (e.g. Sigmoid, Tanh) are also widely used in practice.
Our approach to deal with general activation functions can be decomposed into two steps. Firstly, we approximate the activation function by a two-layer ReLU network. Thus the original network is converted to a ReLU network but with more parameters. Secondly, we apply the path-norm complexity control to the induced ReLU networks, then we obtain a new path-based norm for the original networks. This norm can be used to control the complexity of the original networks.

Our contribution
We explicitly write down the path-based norms for two-layer neural networks and deep residual networks. Moreover, the estimates of the Rademacher complexity based on these norms are also provided. These path-based norms in general consist of two terms. The first one is the same as the path norm for the corresponding ReLU networks. The second one is an additional term arising from the approximation of activation functions. Notably, different from the original path norm which only depends on the full paths, the new path-based norm relies on all the paths with different lengths, including the short ones starting from intermediate layers.
We also provide some results for the a priori estimates for the generalization error of the regularized estimatorθ n := argmin θR n (θ) + λ θ , whereR n is the empirical risk and θ is the norm acting as the complexity measure. These results can be viewed as the extension of the previous work on function spaces and a priori estimates of ReLU neural networks [8,5,6,7].
Beside the main results, we also provide the characterization of the approximation ability of onedimensional ReLU networks with finite path norm, which may be of independent interest to readers. Roughly speaking, we show that an one-dimensional function f can be approximated in L ∞ (R) by two-layer ReLU networks with bounded path norm as long as γ 0 (f ) := R |f ′′ (x)|(|x| + 1)dx < +∞. (1) Moreover, the ReLU network's path norm can be roughly bounded by γ 0 (f ) (see Theorem 1 for details). A similar characterization appeared in [21], but neglected the bias terms. [3,10,15] also provided complexity controls for neural networks with general activation functions, but in a layer-wise fashion. For example, [3] considered the fully connected network f (x; θ) = A L σ(A L−1 σ(. . . σ(A 1 x))) controlled in the following way where θ is a norm of θ.

Related work
[16, 2,5] showed that for positive homogeneous networks, this type of control can produce path-based complexity measures, which usually appear in the form of |A i | , where |A i | denotes the matrix obtained by taking entry-wise absolute values for A i . Usually this type of norms are better than A i [24]. In this paper, we extend this type of results to the case of general activation functions.
Another closely related work is [13], which also obtained the path-based complexity measures for neural networks with general activation functions. The distinguishes between our work and theirs are given as follows.
[13] considered fully connected networks (including two-layer networks), while we considered two-layer networks and deep residual networks. The limits of two-layer and deep residual networks as network size goes to infinity are well-defined [6], so we also study the approximation function spaces induced by the path-based norms. In contrast, the limit of multilayer fully connected networks are still unclear now [17,23]. Moreover, the techniques used are different.
[13] used the sampling-based approach to obtain the bounds of covering numbers, which cannot be directly applied to neural networks with skip-connections [24]. However, our approach is more general, which can be applied to any architectures as long as the complexity controls of corresponding ReLU networks exist.
It is worth mentioning that the idea of approximating activation functions with a small network was also exploited in the literature on network in network [14], which proposed to replace the simple activation function with a complex "micro network" to enhance model's expressivity.
We use X Y to indicate that there exists an absolute constant C 0 > 0 such that X ≤ C 0 Y , and X Y is similarly defined. For any matrix A = (a i,j ), denote by |A| = (|a i,j |). For any x ∈ R d , let x = (x T , 1) T ∈ R d+1 .

Preliminaries
In this work, we consider the standard supervised learning setup.
where T [0,1] is the truncation operator such that T [0,1] g(x) = min{max{g(x), 0}, 1} for any function g : R d → R. Then the population risk and empirical risk are defined as The difference between two risks is called the generalization gap.
For a function class F, the (empirical) Rademacher complexity [22] with respect to the data set S is defined as where the {ξ i } n i=1 are independent random variables with P(ξ i = 1) = P(ξ i = −1) = 1/2. A two-layer neural network is given by where σ : R → R is a nonlinear activation function, and θ = {(a k , b k , c k )} m k=1 denote the parameters to be learned from the training data. For the ReLU networks, i.e. σ(t) = σ R (t) := max(0, t), we define its path norm [16] by Throughout this paper, we will use σ R to denote ReLU function.

Approximating one-dimensional functions by two-layer ReLU networks
We begin with the characterization of one-dimensional functions that can be approximated by twolayer ReLU networks with bounded path norms. This result will serve as the cornerstone for the analysis of neural networks with general activation functions in the following sections. and If γ(f ) < +∞, then for any ǫ > 0, there exists a two-layer ReLU neural network f m (·; θ) of width m < +∞, such that Here, the derivatives f ′ and f ′′ should be understood in the weak sense. The complete proof is deferred to Appendix B.1. Notice that for any h(x) = a + bx with a, b ∈ R, we have γ 0 (f + h) = γ 0 (f ). It implies that adding a linear part does not change the value of γ 0 (·), but the two-layer neural networks used for approximation must change accordingly. The extra term inf x∈R g(x) is introduced to account for the linear part of f . Theorem 1 implies that the "norm" γ(·) is a good measure to characterize whether an activation function can be approximated by two-layer ReLU network with bounded path norm. As a comparison, [21] provided a similar characterization as follows for two-layer ReLU networks with m k=1 |a k ||b k | bounded. Apparently, the condition (12) is weaker than γ(f ) < +∞. But it neglects the influence of the bias term c k , which is crucial for providing complexity control.
To prove Theorem 1, we need the following lemma, whose proof can be found in Appendix B.1.1.
Lemma 1. Let f satisfies γ 0 (f ) < +∞, then there exist constants a, b, c and d, such that The above lemma suggests that our method can only deal with activation functions that possess linear asymptotes. This property is surprisingly satisfied by all the commonly used activation functions. We calculate the γ(·) norms for common activation functions and the results are shown in Table  1. We see that all functions considered in Table 1 have finite γ(·) norms.
For general activation functions, we define the following norm 2 .
This norm is stronger than the path norm since θ P = θ P + m k=1 |a k |. The additional term n k=1 |a k | only depends on the paths of length 1, while θ P depends on the paths of length 2. The intuition behind this definition will be clear from the proof of the following theorem.
Theorem 3. Assume that the activation function σ(·) satisfies the conditions in Theorem 1. Let Proof. According to Theorem 1, for any ǫ > 0, there exists a two-layer ReLU networks g K (t; we can decompose it as follows: where and is a two-layer ReLU networks with the path norm where the last inequality follows (17) and the definition of the norm · P . Therefore, h f 2 ∈ F 0 (γ(σ)+ǫ)Q . Using the decomposition (18), we have

Function space
Let Ω be the Borel σ−algebra on R d+1 and P (R d+1 ) be the collection of all the probability measures on (R d+1 , Ω). Following [8, 6], consider the functions that admit the following integral representation: where π ∈ P (R d+1 ), and a(·) is a measurable function with respect to (R d+1 , Ω). (24) can be viewed as an infinite wide two-layer neural network. Notice that σ(·) is a general activation function which may not enjoy the positive homogeneity property, hence the integral domain can not be normalized to the unit ball S d+1 as done in [8,6]. For any f : X → R, we define where Π f := (a, π) : f (x) = E w∼π [a(w)σ(w Tx )], ∀x ∈ X . For a specific representation (a, π), the right hand side of (25) is actually the modified path norm (15) of the infinite wide network (24). Notice that for a function f , the representations may not be unique. Therefore, it is crucial to take the infimum over Π f , since it can make the norm independent of representations, hence becoming a function norm. For simplicity, we let B = {f : f B < +∞}.
The proof can be found in Appendix C.1.

A priori estimates
In this section, we provide the a priori estimates of the following regularized estimator: where λ > 0 is a tuning parameter. Notably, with the function norm defined in (25), the analysis is almost the same as the a priori estimates of two-layer ReLU networks [8].
In the following, we state the approximation result and the a priori estimates. The proofs can be found in Appendix C.2 and C.3, respectively.
Then for any δ ∈ (0, 1), with probability at least 1 − δ over the random training samples {x i } n i=1 , the generalization error satisfies Therefore, if we take λ ≍ λ n , we will have Notice the above estimates depend on the activation function σ only through the appearance of constant C σ and the target function norm f * B . Especially, when σ is ReLU, it exactly recover Theorem 4.1 of [8], which is the result specifically derived for two-layer ReLU networks.
Remark 3. Theorem 3 demonstrates the new path-based norm (15) is defined such that the Rademacher complexity is independent of the network width. Theorem 4 and 5 together show that the induced the function norm can effectively control both the approximation and estimation errors. In this sense, the complexity measure (15) for general activation function σ is well defined.

Residual neural networks
In this section, we consider the residual networks defined by Here, θ = {V, W 1 , U 1 , W 2 , U 2 , · · · , W L , U L , α} denotes the set of parameters, V ∈ R D×(d+1) , W l ∈ R m×D , U l ∈ R D×m , α ∈ R D . L is the number of layers (depth), m is the width of the residual blocks and D is the width of skip connections. σ(·) is the (general) activation function.
To bound the Rademacher complexity of residual networks (with general activation functions), we propose the following norms, which can be viewed as a modification of the weighted path norm defined in [5].
Definition 1. For any residual network defined as (32) with parameters θ, let its norm be with the convention that A L A L−1 · · · A i+1 = I when i ≥ L. Here U 0 := V , and c σ > 4γ(σ) + 1 is an absolute constant only related to the activation function σ(·).
With the norm defined above, we can state the theorem about the Rademacher complexity of residual networks. The bound depends linearly on the norm defined in (33). The proof is given in Appendix D.1.
Before the next subsection about the a priori estimate using the norm-based bounds, we make several comments on the norm (33) for residual networks.
(1) The norm can be viewed as an extension based on the weighted path norm proposed in [5], with two modifications. Firstly, the weight factor is switched from 3 to a constant c σ depending on the activation function; Secondly, an additional term (modification) is added to the weighted path norm, to address the bias terms originally in the neural network or arising when approximating the activation function by ReLU networks. In fact, we have the following recursive definition (of the modified weighted path norm), which is equivalent to the norm (33): Lemma 3. The norm (33) can be written as a modification of the weighted path norm defined in [5]: where the modification term r can be recursively defined as by selecting appropriate {M 1 } L l=1 . Remark 4. In fact, the {M l } L l=1 defined by (36) can be viewed as the modification term at the l-th layer. That is to say, compared to the original weighted path norm, our new norm (35) not only includes those paths starting from the biases in all the layers to the output, but also can be extended to hidden neurons, which is crucial for the proof of Theorem 6. Please see Appendix D.1.1 for more details.
(2) We have the following upper bound for the modification terms M l and r. This theorem shows that these additional terms are not much larger than the original path norm part.
Theorem 7. For l = 1, 2, · · · , L, i = 1, 2, · · · , m, we have where M l,i is the i-th element of M l , and A i,: is the i-th row of A.
(3) In the case of ReLU network without bias terms, we will not have the +1 m term in (36), the recursive definition of M l , hence M 1 = 0 m implies M l = 0 for all l = 1, 2, · · · , L and r = 0. In this case, our norm is equivalent with the weighted path norm studied in [5]. Therefore, while our norm applies to more general cases, it works as good as the norm specifically defined for the case of ReLU activation functions.
The proofs of Lemma 3 and Theorem 7 are given in Appendix D.2 and Appendix D.3 respectively.

A priori estimates
An important observation is that by splitting the two-layer neural network into several parts and stacking them vertically, we can obtain a ResNet structure like (32). Based on this observation and Theorem 4, we can obtain the following embedding result, whose proof is given in Appendix D.4.
Proposition 8. For any f ∈ B and L, m ∈ N * , there exists a residual network f (x;θ) with depth L and width 4 m, such that where C σ,2 = 4γ(σ) + 1.
The above proposition implies that the norm (33) is well-defined in the sense that it is compatible with the norm (15) defined for two-layer networks. Let us consider the regularized estimator: where λ > 0 is a tuning parameter. Similar as the work [5], we have Proposition 9. Assume f * ∈ B, and choose λ ≥ λ n := ((8γ(σ) + 2) 2 ln (2d + 2) + 1)/ √ n. Then for any δ ∈ (0, 1), with probability at least 1 − δ over the random training samples {x i } n i=1 , the generalization error satisfies Therefore, if we take λ ≍ λ n , we will have The proof of Proposition 9 can be found in Appendix D.5. However, this proposition only implies that residual networks with proper regularization can learn functions in B, the approximation function space for two-layer neural networks. To fully understand the superiority of residual network compared to the two-layer networks, we need to identify the function spaces specialized for residual networks.
Consider a scaled version of (32), There are two potential ways to define the function spaces. The first one is to consider (43) with L fixed. Taking m → ∞ in (32), we obtain 4 Here we refer to the width of residual blocks.
where Π = {π l } L l=1 . Following the expression (33), we could define the norm of continuous ResNet (44) by Another ways is to take both L → ∞ and m → ∞, we obtain an ODE The output function is accordingly defined as f (x; π) := α T h(1) with π = (π t ) 1 t=0 . In this case, (43) can be viewed a stochastic approximation of (46).
[6] has developed the function space theory in this way for the case σ being ReLU, and the norm is defined through the linearized ODE: As shown in [6], to control the Euler-forward discretization error of (43) approximating (46), we must make certain continuous assumption on the probability measures (π t ) 1 t=0 , i.e. d(π t , π s ) ≤ c|t − s| for some distance d(·, ·). In contrast, there is no restriction for {π l } L l=1 in (44). To define function spaces appropriately in either way requires involved mathematical analysis, which we leave as the future work.

Conclusion
We propose a simple approach to build complexity measures for neural networks with general activation functions. Using this approach, we derive the path-based norms for two-layer networks and deep residual networks. Moreover, these norms are well-defined in the sense that the Rademacher complexity can be bounded by them without depending on the network size. This property enables us to study the infinitely wide and deep networks, i.e. the function spaces induced by these norms containing functions learnable by corresponding models.
One direct future work is to complete the definition of function spaces for residual networks, which can be viewed as an extension of the function spaces defined in [6] but for deep residual networks with ReLU activation function.
It would also be interesting to extend our results to fully connected networks. However, this is more challenging, since we are still far away from understanding the approximation function spaces for multilayer fully connected networks, even for the three-layer case [23, 17].
[7] Weinan E, Chao Ma, and Lei Wu. On the generalization properties of minimum-norm solutions for over-parameterized neural network models. arXiv preprint arXiv:1912.06987, 2019.
[10] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In this section, we provide the definition of weak derivatives as well as some results that will be used in the following analysis. We denote the classical derivatives of a one-dimensional function u by du dx , d 2 u dx 2 , · · · , d n u dx n , and the weak derivatives by u ′ , u ′′ , · · · , u (n) .

Definition 2.
We say a function u defined on R has some properties P locally, if u has properties P on any compact subset of R.
Definition 3. Assume that u(x) is locally Lebesgue integrable on R. If there exists another locally Lebesgue integrable function v(x), which satisfies the integration by parts then u is n-th order weakly differentiable on R, and v is the derivative, i.e. v = u (n) . Now we can state the following theorems required to prove Theorem 1.
The proof of Theorem 10 can be found in any standard textbooks on real analysis.
Theorem 11. Assume that u(x) is locally Lebesgue integrable on R. Then u is weakly differentiable ⇔ u is locally absolutely continuous on R.
We also need a proposition, which can be seen as a weak form of the mean value theorem for integrals. and where m(E) denotes the measure of a measurable set E. Therefore, there always exists Proof. We only prove (48), since the proof of (49) is similar. Consider the set which is a contraction.

A.2 Redemacher complexity
The following standard results will be repeatedly used in our analysis, the proof of which can be found from classic machine learning theory books, e.g. [22].

and the class of linear functions
We have the Rademacher complexity-based generalization bound as follows.
Theorem 13. Given a function class H, for any δ ∈ (0, 1), with probability at least 1 − δ over the random samples Proof. We only prove that f has an asymptote when x → +∞, since the condition that x → −∞ is similar. Firstly, we show that lim x→+∞ f ′ (x) exists. If not, we can find a constant δ and infinite many pairs Hence, we have R |f ′′ (x)|dx = +∞, which is contradictory with γ 0 (f ) < +∞.
Then, without loss of generality, we assume lim If not, similarly we can show that This is contradictory with Combining the existence of f ′ (+∞) and the existence of f (+∞) when f ′ (+∞) = 0, we can conclude that f has an asymptote when x → +∞. In fact, let f ′ (+∞) = a, then for F (x) := f (x) − ax, we have γ 0 (F ) = γ 0 (f ) and F ′ (+∞) = 0, then F (+∞) exists. Let F (+∞) = b, then we have lim Remark 5. The basic tools used in the proof is Cauchy criterion for convergence, Newton-Leibniz formula and Fubini theorem, where only the Newton-Leibniz formula needs to be checked in the weak form. Its validity is guaranteed by Corollary 2.
Since γ 0 (f ) < +∞, we can simultaneously have For any positive integer N , make a uniform partition and On the other hand, obviously h r N (x) is a two-layer neural network with a finite width N + 1. Its path norm is This limit will be verified later in Appendix B.1.3. Hence, with a similar analysis for θ(h l N ) P and by (54), there exists N 2 = N 2 (ǫ), such that Finally, let and N ≥ max{N 1 , N 2 } = N (ǫ), we have which completes the proof.

B.1.3 A supplemental proof
This subsection gives a rigorous proof of the limit (57).
Proof. The aim is to show Notice that we can divide the analysis into three parts.
Recall the definition of γ(f ):

B.2.5 swish
The swish function is f (x) = xσ s (βx), where σ s (x) is the sigmoid function σ s (x) = (1 + e −x ) −1 , and β > 0. We have f (x) ∈ C 2 (R), and Now we need to determine the sign of f ′′ (x). Let f ′′ (x) = 0, we get It is easy to see that (61) has two different roots Similar to the computation in Appendix B.2.1, we have Combining above gives .

B.2.7 Gaussian Error Linear Unit (GELU)
The Gaussian Error Linear Unit (GELU) function is f (x) = xΦ(x), where Φ(x) is the cumulative distribution function of the standard normal distribution We have f (x) ∈ C 2 (R), and The monotonicity is the same as swish except the different critical points x 1 , x 2 . According to the expression of γ 0 (f ) in Appendix B.2.5, we have We have f (0) = 0, and by L'Hospital rule, For any x > 0, notice that On the other hand, using the fact that x 1 = −x 2 and Φ(x) − Φ(−x) = 2Φ(x) − 1 for any x > 0, we have In the meanwhile, it is not hard to have g(−∞) = 0, therefore

C Proofs for Section 4 C.1 Proof of Lemma 2
Proof. For any π ∈ P (R d+1 ), according to [19], . For any f ∈ B, f also has the integral representation (24) by (25). Then there exists (a 0 , π 0 ) ∈ Π f , such that Notice that On the other hand, for any π ∈ P c (R d+1 ), denote the support of π by supp(π), then supp(π) ⊂ R d+1 is compact, hence it is bounded and closed. Let For any f ∈ H kπ , where π ∈ P c (R d+1 ), we have Combining above gives which completes the proof.
By (64), (65) and Hölder's inequality, we have where the last inequality is due to (63). Combining above gives Denote the modified path norm off U (x) by A U , i.e.
which implies E 2 U [A U ] ≤ f 2 B + ǫ due to Jensen's inequality and (63). Now we obtain Consider the event By Markov's inequality and taking ǫ ≤ f 2 B /100, we have Therefore, the probability that two events happen together is which completes the proof by taking ǫ → 0.

C.3 Proof of Theorem 5
Now we are ready to derive a priori estimates for the generalization error of two-layer neural networks with general activation functions. The proof is almost the same as [5], except for a different upper bound of the Rademacher complexity.

C.3.1 A posteriori estimates
According to Theorem 13 in Appendix A.2, the Rademacher complexity can help bound the generalization gap. Combining with Theorem 3 we have the following a posteriori estimates.
Combining with Theorem 4 yields (31), which completes the proof. Definition 4. Given a residual network defined by (32), let g l = σ(W l h l−1 ), l = 1, 2, · · · , L, and g i l be the i-th element of g l . Define its norm to be with the convention that A l−1 A l−2 · · · A k+1 = I when k ≥ l − 1. Here U 0 := V , W i,: l is the i-th row of W l , and c := c σ > 0 is an absolute constant only related to the activation function.
Obviously this definition is a natural extension of the norm (33) to hidden neurons, and consistent with (33). Next, we give the following recursive form of the norm (69), which will be used in the proof of Theorem 6.
Theorem 15. The norm (69) can be written as a modification of the weighted path norm for hidden neurons g i l P defined in [5]: where the modification term M l,i satisfies with M 1 = 0 m . Here M k := (M k,1 , M k,2 , · · · , M k,m ) T for k = 1, 2, · · · , l.
Proof. The fact that M 1 = 0 m is obvious. We need to prove the equivalence of (71) and (73), i.e.
Remark 6. The M l defined in Theorem 15 is exactly the desired M l in Lemma 3. As a result, the proof of Lemma 3 is totally the same as above. That is to say, the recursive definition (35)-(36) is equivalent to the closed form (33).
Remark 7. Theorem 15 and Lemma 3 show that M l and r can be viewed as the modification of the weighted path norm (see [5]) at the l-th layer and the output, respectively. In addition, this modification captures the effect of all bias, and can be obtained recursively.
Remark 8. Since the modification is caused by the approximation for activation functions (utilizing two-layer ReLU networks), it does not occur until the first activation. Therefore, the modified terms (35) and (71) do not contain V and W 1 , since they are both before the first activation.
The following lemmas establish the relationship between θ P and g i l P . It is in fact similar to the ReLU case handled in [5], only with a change of weight factor from 3 to any constant c > 0.
Lemma 6. For the weighted path norm θ P and g i l P , we have and where U :,j l is the j-th column of U l .
The following two lemmas will be repeatedly utilized in the Rademacher calculus of residual networks (the proof of Theorem 6).
Proof. Obviously we have (G q l ) ′ ⊂ (G Q l ) ′ for any q ≤ Q. Notice that both the two parts of (g i l ) ′ P ( (g i l ) ′ P and M l,i ) have an output parameter W i,: l , meaning that the scaling process can be done on the row vector W i,: l , we can easily have (G q l ) ′ = q Q (G Q l ) ′ . In fact, for any (g i l ) ′ ∈ (G Q l ) ′ , define (g i l ) ′ by replacing the output parameter W i,: l by q Q W i,: l , then we have (g i l ) ′ = q Q (g i l ) ′ , and by (72), The following simple lemma shows the Lipschitz continuity of the activation function σ(·).

D.1.2 Proof of Theorem 6
Based on Lemma 4 and Lemma 5 in Appendix A.2, and Appendix D.1.1, we can now get down to prove Theorem 6.
Proof. The crucial step is to inductively estimate the Rademacher complexity of G Q l . We will show that Rad n (G Q l ) ≤ Q 2 ln (2d + 2) n , l = 1, 2, · · · , L.
(1) The first layer: a standard analysis For l = 1, according to the contraction lemma (Lemma 5) and the Rademacher complexity of linear functions (Lemma 4), we have as long as c ≥ L σ .
(2) The general layer: approximation and decomposition Assume the result (80) holds for 1, 2, · · · , l, the aim is to prove that (80) holds for l + 1. Consider the following dynamicsh whereσ i := (σ i,k ), i = 1, 2, · · · , l, k = 1, 2, · · · , m, are some two-layer ReLU networks which can vary from different neurons at different layers, and the activation is operated in the same indices. According to Theorem 1, the dynamics (81) can be seen as an approximation of ResNet (32) up to the (l + 1)-th layer by selecting appropriateσ(·). Then consider the decomposition where condition (1) is according to (72). Since M l+1,i is a function of parameters U 1 , W 2 , U 2 , · · · , W l , U l , W i,: l+1 , just like g i l+1 P , the supreme is in fact taken over parameters up to the (l + 1)-th layer which satisfy the (modified weighted path) norm control. Notice that g l+1 andg l+1 enjoy the same parameters, the last equality holds.
Next we need to bound I 1 and I 2 respectively. The basic framework is as follows: • control the "approximation error" I 1 to be arbitrarily small (i.e. smaller than a pre-selected tolerance error ǫ), by selecting appropriateσ(·); • derive a "uniform" upper bound for I 2 like (80) for any ǫ-approximation dynamics (81), by taking appropriate weight c σ (according to different ǫ); • combining the above and letting ǫ → 0 yield the desired conclusion.
Then applying the Cauchy-Schwarz inequality to have (2b) The main term I 2 By the contraction lemma (Lemma 5) and approximation dynamics (81), we have that ξ t w T l+1 Vx t := L σ I 2,1 + L σ I 2,2 .