IMPROVED GENERALIZATION BOUNDS FOR DEEP NEURAL NETWORKS USING GEOMETRIC FUNC-
Year: 2021

Abstract:
Understanding how a neural network behaves in multiple domains is the key to further its explainability, generalizability, and robustness. In this paper, we prove a novel generalization bound using the fundamental concepts of geometric functional analysis. Specifically, by leveraging the covering number of the training dataset and applying certain geometric inequalities we show that a sharp bound can be obtained. To the best of our knowledge this is the first approach which utilizes covering numbers to estimate such generalization bounds.

heading: 1 INTRODUCTION
text: The problem of generalization of deep neural networks from the perspective of theoretical analysis has recently received a considerable amount of interest (Neyshabur et al., 2015; Zhang et al., 2017; Dziugaite & Roy, 2017; Neyshabur et al., 2018; Golowich et al., 2018; Nagarajan & Kolter, 2018; Daniely & Granot, 2019). More specifically, most of the state-of-the-art bound are based on spectral norm based generalization bounds and have shown to give tighter and sharper bounds compared to conventional ones leveraging PAC Bayesian theory (Bartlett et al., 2017; Neyshabur et al., 2015; 2018). However, the bounds in such works are quite limited as they only apply in cases where the parameters are drawn from a distribution or when they are represented by fewer bits than required (Nagarajan & Kolter, 2018).
In this paper, we provide a novel framework based on the foundational mathematics of geometric functional analysis to obtain a sharp bound. We show that this analysis has many advantages over the conventional conceptions which solely rely on stochastic assumptions ignoring the geometric structure of the neural networks and to the best of our knowledge this is the first work attempts to foray in this direction. We compare our result with that of Neyshabur et al. to show that our bound is better than the bounds derived using spectral norms.
Geometric functional analysis deals with infinite dimensional vector spaces from a geometric perspective (Holmes, 2012), of its many applications it is widely in the theoretical analysis of wavelet theory (Young, 2012). In fact we believe this is the most suited framework for dealing with deep neural networks, as their parameters are generally huge and any frame work that is finite will not cover all possible models. Specifically, our approach involves using the covering number of a vector space to derive a bound for the generalization error of a given neural network. However, computing the covering number of a high dimensional vector space becomes an intractable problem as the size of the input space becomes sufficiently large. Thus, we make use of the Vitushkin’s inequality (Friedland & Yomdin, 2014) to bound the covering numbers using the Lesbesgue measure, which is a tractable quantity. This bound along with functional inequalities forms the groundwork by which we extend it generalization problem of neural networks which also takes into account the geometry of the data input. Another by product of the analysis is that the bound obtained is in terms of the Frobenius norm of the weight matrices rather than its spectral norm, which has shown to scale more rapidly with the size of the matrix (Vershynin, 2011).
We approach the neural network in a rather unorthodox manner by treating it as a recurrent polynomial function which can be approximated to some arbitrary degree (Telgarsky, 2017), as it is the most amicable framework for exploiting its geometric properties. We explain this in detail in
the following sections along with other mathematical preliminaries. This is followed by several intermediate theorems, which are then used to derive our generalization bound.

heading: 2 RELATED WORK
text: The concept of generalization bounds were introduced in (Bartlett, 1998) rather indirectly by analyzing the probability of misclassification. (Zhang et al., 2017) showed that uniform convergence over data points is what is required to understand the generalization of networks. Dziugaite & Roy (2017) obtained non vacuous bounds. (Neyshabur et al., 2017) compared the effect of norm based control, sharpness and robustness on generalization. (Neyshabur et al., 2018) used spectral norm to give a bound which incorporated the weights of the neural networks. (Arora et al., 2018) obtained sharp generalization bounds in terms of sample complexity. (Bietti et al., 2019) used Reproducible kernel Hilbert spaces for studying regularization of deep neural network from analytic viewpoint.

heading: 3 MATHEMATICAL PRELIMINARIES

heading: 3.1 POLYNOMIAL FRAMEWORK OF NEURAL NETWORKS
text: Consider the mathematical formulation of Neural Networks, a neural network N with l layers is a function which takes an input vector x and returns a vector N (x) such that:
N (x) = fl(Wl . . . f2(W2f1(W1x)) . . . ) (1)
where Wi is the weight matrix of network at layer ith layer, fi is the corresponding non-linear activation function. If xl = [x1l . . . x nl l ] is the output of the l th layer with nl nodes, then:
xl = gl(Wlxl−1) (2)
As mentioned earlier if the activation functions are approximated using polynomials then mathematically there are only polynomials at each node at every layer in the network, so in our analysis we consider the activation functions as polynomials with certain degrees. Let a(l−1,l)ij be the weight of the neural network from the ith node in l − 1th layer to the jth node in the lth layer and Pl be the Polynomial approximation of the activation function. Then based on the above mathematical description of neural networks the output at 2nd layer with n2 nodes is
x2 = [ P1 ( n1∑ i=1 a (1,2) i1 x i 1 ) , P1 ( n1∑ i=1 a (1,2) i2 x i 1 ) , . . . , P1 ( n1∑ i=1 a (1,2) in2 xi1 )] (3)
Similarly for the 3rd layer, x3 can be obtained as
x3 = [ P2  n2∑ j=1 a (2,3) j1 P1 ( n1∑ i=1 a (1,2) i1 x i 1 ) , P2  n2∑ j=1 a (2,3) j2 P1 ( n1∑ i=1 a (1,2) i2 x i 1 ) , . . . , P2
 n2∑ j=1 a (2,3) jn3 P1 ( n1∑ i=1 a (1,2) in2 xi1 )] (4)
Clearly, by standard properties of polynomials the above tuple is also a polynomial. Now, if we look into the pattern followed by each layer then the general form of the output at any arbitrary lth layer can be obtained as
xl = [ Pl−1 nl−1∑ j=1 a (l−1,l) j1 Pl−2 ( nl−2∑ i=1 a (l−2,l−1) i1 x i l−2 ) , Pl−1
nl−1∑ j=1 a (l−1,l) j2 Pl−2 ( nl−2∑ i=1 a (l−2,l−1) i2 x i l−2 ) , . . . , Pl−1
nl−1∑ j=1 a (l−1,l) jnl Pl−2 ( nl−2∑ i=1 a (l−2,l−1) inl−1 xil−2 )] (5)
By the same logic applied hitherto the above tuple is also a polynomial. The reason for such an unconventional formulation of a neural network as in the above framework is to analyze the degree of the polynomials using some of its basic properties. Regarding degree of polynomials we have the following standard results:
For any c1, c2, . . . ck ∈ R and polynomials P1, P2, . . . Pk
deg(c1P1 + . . .+ ckPk) ≤ sup i={1,...,k} |deg(Pi)| (6)
where deg(.) is the degree of the polynomial and for any polynomial Pa and Pb
deg(PaPb) = deg(Pa)deg(Pb) (7)
By applying equation (7) on the first element of the vector xl from equation (5) we get
deg Pl−1 nl−1∑ j=1 a (l−1,l) j1 Pl−2 ( nl−2∑ i=1 a (l−2,l−1) i1 x i l−2 ) = deg (Pl−1) deg
nl−1∑ j=1 a (l−1,l) j1 Pl−2 ( nl−2∑ i=1 a (l−2,l−1) i1 x i l−2 ) (8)
Similarly, by applying equation (6) on equation (8) we obtain
deg (Pl−1) deg nl−1∑ j=1 a (l−1,l) j1 Pl−2 ( nl−2∑ i=1 a (l−2,l−1) i1 x i l−2 ) ≤ deg(Pl−1)|deg(Pl−2)| (9) By iterating over all the layers in the network and applying equation (9) we get
deg(Pl) ≤ deg(Pl−1)deg(Pl−2) . . . deg(P1) (10)
We make use of the above inequality in the next sections in obtaining the generalization bound.

heading: 3.2 COVERING NUMBER
text: Covering number of a general topological space counts the number of spherical balls needed to cover the entire space (Munkres, 2000). This is relevant to our present analysis as it gleans the behaviour of a neural network on an unknown set by understanding its behaviour on a known one. Formally, M( , V ) is the covering number of the space V , conceptually this gives a measure of generalizability of the neural network on potentially infinite and unknown datapoints when trained on a finite subset (i.e. the training dataset). Thus, any bound on the covering number would imply that we can predict the lower limit of the number of datapoints essential for accurate prediction on unknown sets.

heading: 3.3 VITUSHKIN’S INEQUALITY
text: The Vitushkin’s inequality (Friedland & Yomdin, 2014; Yomdin, 2011) has been widely used in geometric functional analysis for studying the behaviour of level sets of analytic functions (Kovalenko, 2017). Along with its many applications this inequality can be used to bound the covering number of a metric space V using the lesbesgue measure (Burk, 2011; Bartle, 2014).
Formally, let P (x, n, d) = P (x1, x2, . . . , xn) be a polynomial of degree d in n variables, Bn be a ball of unit radius in n-dimensions and Vρ(P ) be the set of all polynomials that is bounded by ρ, i.e.:
Vρ(P ) = {x ∈ Bn : |P (x, n, d)| ≤ ρ} (11) Then according to Vitushkin’s inequality:
M( , V ) ≤ n−1∑ i=0 Ci(n, d) ( 1 )i + µn(V ) ( 1 )n ≤Md( ) + µn(V ) ( 1
)n (12) where µn(V ) is the n-dimensional Lesbesgue measure (Bartle, 2014) of the set and Md( ) are variables defined as:
Ci(n, d) , 2 i ( n i ) (d− i)i Md( ) , n−1∑ i=0 Ci(n, d) ( 1 )i (13)

heading: 3.4 METRIC (N,D)-SPAN
text: Metric (n,d)-span measures the accuracy of approximation of the covering number with Lesbesgue measure, that is to say it determines how well the covering number can be approximated by knowing the Lesbesgue measure of that set. This transforms the intractable problem of computing the covering number of the set V into a tractable one, this is extremely important as this quantifies the accuracy of computational experiments to that of theoretical expressions. More formally, for any subset Z ⊂ Bn, we define a constant ωd(Z) which is the metric (n,d)-span of set Z denoted by:
ωd(Z) = sup ≥0
n[M( , Z)−Md( )] (14)

heading: 3.5 DIFFERENTIABLE RIGIDITY CONSTANT
text: The differentiable rigidity constant (Yomdin, 2011) measures the minimum variation of a function which is differentiable, i.e. it is a lower on the variation of a function. Formally, let f : Bn → R, f ∈ Cd+1 where d ∈ N and Ql(f) = maxx∈Bn ∑ |f (l)(x)|. Here Ck is the family of all k times
continuously differentiable functions and ∑ |f l(x)| is the sum of absolute values of all the partial derivatives of f of order l. Then the dth differentiable rigidity constant is given by
RCd = inf f∈Ud Qd+1(f) (15)
where Ud is the set of all Cd+1 smooth functions f(z) on Bn vanishing on Z with Q0(f) = 1.

heading: 3.6 REMEZ D-SPAN
text: The Remez d-span (Brudnyi & Ganzburg, 1973; Yomdin, 2011) measures the variation of the function when extended from a smaller set to a bigger set, this instrument allows for an extensive analysis
of neural networks when it transitions from the training to the testing dataset. Formally, for any polynomial P , set Z ⊂ Bn and d ∈ N the Remez d-span is the minimal number K that is the ratio of supremum of polynomial on the whole set to that of supremum of polynomial on the set Z
Rd(Z) = min { K : ∣∣∣∣ supBn |P |supZ |P | ≤ K }
(16)

heading: 3.7 BRUDNYI-GANZBURG’S INEQUALITY
text: The Brudnyi-Ganzburg’s inequality (Brudnyi & Ganzburg, 1973; Yomdin, 2011) tells us the variation in performance from a continuous train dataset to a test dataset. However, it is not applicable for discreet datapoints as in the case when deep neural networks and we have use of Rd(Z) and RCd to derive the corresponding bound for the discreet dataset. Let B ⊂ Rn be a convex body and let let Ω ⊂ B be a measurable set. Then for any real polynomial P (x) = P (x1, . . . xn) of degree d we have
sup B |P | ≤ Td ( 1 + (1− λ) 1n 1− (1− λ) 1n ) sup Ω |P | (17)
Here λ = µn(Ω)µn(B) , with µn being the Lebesgue measure on R n and Td is the Chebychev polynomial of the first kind (Rivlin, 1974).

heading: 4 THEOREMS
text: Theorem (1) gives a bound of on the differentiable rigidity constant in terms of the Chebychev polynomial and since this has a closed form solution it is computationally efficient to obtain Rd(Z).
Theorem 1. If ωd(Z) > 0 and µn(V1(P )) ≥ ωd(Z) is finite and it satisfies the inequality
Rd(Z) ≤ Td
[ 1 + (1− ωd(Z)) 1 n
1− (1− ωd(Z)) 1 n
] (18)
Proof. Suppose |P | ≤ 1 on Z. Clearly Z ⊂ V1(P ) as P is bounded in absolute value by 1 on V1(P ). Then by applying Brudnyi-Ganzburg’s inequality (17) with B = Rn and ω = V1(P ) we get the above expression.
Theorem 2. For any real number 0 ≤ ω ≤ 1 the following inequality holds
Td [ 1 + (1− ω) 1n 1− (1− ω) 1n ] ≤ 1 2 ( 4n ω − 2 )d
(19)
Proof. We use the simplified expression of Td(x) when x ≥ 1, then by simple algebraic manipulations we get
Td
[ 1 + y
1− y
] = 1
2
( 2 1 + y
1− y
)d (20)
By substituting y = (1− ω) 1n in equation (20) we obtain
Td [ 1 + (1− ω) 1n 1− (1− ω) 1n ] = 1 2 ( 2 1 + (1− ω) 1n 1− (1− ω) 1n )d (21)
Now, as 1n < 1 and as ω ≤ 1, by applying Bernoulli’s inequality on y we obtain
(1− ω) 1n ≤ 1− ω n
(22)
Applying equation (22) in (21) leads to the final result
2 1 + (1− ω) 1n 1− (1− ω) 1n
≤ ( 4n ω − 2 )
( 2
1 + (1− ω) 1n 1− (1− ω) 1n
)d ≤ ( 4n ω − 2 )d
Td [ 1 + (1− ω) 1n 1− (1− ω) 1n ] ≤ 1 2 ( 4n ω − 2 )d
(23)
Theorem (3) gives a relation between the differentiable rigidity constant and the Remez d-span, this enables us to relate our generalization bound with Remez d-span. Theorem 3. For any subset Z ⊂ Bn and d ∈ N
RCd(Z) ≥ 1
2Rd(Z) (24)
Proof. Let f : Bn → R, f ∈ Ck, P(n, d) is the set of all real polynomials of degree d in n variables and for d ∈ N we define Ed(f) as
Ed(f) = min P∈P(n,d) max x∈Bn
|f(x)− P (x)| (25)
Let Pd(x) be the polynomial of degree d for any fixed d such that the minimum is achieved. Thus, equation (25) can we rewritten as
Ed(f) = max x∈Bn
|f(x)− Pd(x)| (26)
By applying the triangle inequality on equation (26) for the subset Z ∈ Bn we obtain
max x∈Z |Pd(x)| ≤ max x∈Z |f(x)|+ Ed(f) (27)
By the definition of Remez d-span in equation (16) we get
max x∈B |Pd(x)| ≤ Rd(Z)[L+ Ed(f)] (28)
where L = maxx∈Z |f(x)|. Again, by applying triangle inequality on maxx∈Bn |f(x)| we get
max x∈Bn |f(x)| ≤ max x∈Bn |f(x)− Pd(x)|+ max x∈Bn |Pd(x)| (29)
By combining equation (28) and equation (29) we get
max x∈Bn
|f(x)| ≤ Ed(f) +Rd(Z)[L+ Ed(f)] (30)
As the inequality in equation (30) holds for any value of d we therefore get
inf d [Rd(Z) [L+ Ed(f)]] ≤ inf d∈{0,...,k−1} [Rd(Z)[L+ Ed(f)] + Ed(f)] (31)
Let Etd(f) = maxx∈Bn ||fd+1|| (d+1)! and as Ed(f) ≤ E t d(f) equation (31) further reduces to
max x∈Bn |f(x)| ≤ inf d∈{0,...,k−1} [Rd(Z)[L+ Etd(f)] + Etd(f)] (32)
For a finite set Z ∪ {x} where x ∈ Bn we define the function fZ,x as
fZ,x = { 0, if x ∈ Z 1, if x ∈ Bn − Z (33)
Let f̌Z,x be the analytic extension of fZ,x to Bn. Then by applying equation (32) we obtain
Q0(f̌Z,x) ≤ inf d∈{0,...,k−1} [Rd(Z)[L+ Etd(f)] + Etd(f)] (34)

heading: If L = 0 and Q0(f̌Z,x) ≥ 1 then
text: 1 ≤ min d∈{0,...,k−1} (Rd(Z) + 1)Qd+1(f̌Z,x) (35)
Thus, Qd+1 ≥ 1Rd(Z)+1 and by the definition of the rigidity constant in equation (15) we get our desired resultRCd(Z) ≥ 12Rd(Z) .
Let ρ be the minimum distance between any two points in a set Z with cardinality k:
ρ = min x1,x2∈Z
||x1 − x2|| (36)
And for neural network N with n input nodes and dl be the degree of approximation the activation function for the lth then the following theorem holds true Theorem 4. The product of k and ρ is bounded by the metric (n, d)-span of the set Z for any n and dl
ωdl(Z) ≥ kρ (37)
The proof of theorem (4) has been relegated to the appendix. Using all the above theorems we have derived till now the derive the final theorem describing the generalization bound.
By leveraging the bounds introduced in theorems (1), (2), (3) and (4) we now derive our generalization bound for deep neural networks. Theorem 5. The loss l(N ) incurred by the networkN using the loss function l on the super-set Bn given the loss in the subset Z is bounded by
EBn [l(N )] ≤ EZ [l(N )] +O [ l∏ i=1 ( 8n kρ ||Wi||2 )di] (38)
Proof. Let us assume that the input x to the neural network is randomly sampled according to a continuous probability distribution (i.e) Bayesian assumption. We first obtain the bound for the randomly generated input and thereby extend it to the deterministic case by using the strong law of large numbers.
Vρ(P ) = {x ∈ Bn : |P (x)| ≤ ρ} if Z ⊂ Vρ(P ) then M( , Z) ≤ M( , Vρ(P )) and further using Vitushkin’s inequality (12) we get
M( , Z) ≤M( , Vρ(P ) ≤Md( ) + µn(V ) ( 1 )n (39)
So [M( , Z) − Md( )] n ≤ µn(V ) for all and by taking supremum of on both sides we get µn(V ) ≥ ωd(Z). On combining equation (18) from theorem (1) and equation (19) from theorem (2) we get
Rd(Z) ≤ 1
2
( 4n ωd(Z) − 2 )d
(40)
It is easy to see from equation (40) it follows that 12 ( 4n ωd(Z) − 2 )d ≤ 12 ( 4n ωd(Z) )d and by applying equation (37) from theorem (4) we can further simplify the equation (40) as
Rd(Z) ≤ 1
2
( 4n
kρ
)d (41)
For any x ∈ Bn we define a special function which captures the effect of sample points on the generalization behaviour, mathematically we define it as
hl(xl) = Pl(xl)− k∑ j=1 Pl(zj)ψ ( 2 ρ (xl − zj) ) ||fl ◦Wl||F (42)
where ψ is a C∞ function on Bn such that ψ(0) = 1 and ψ vanishes on the boundary on Bn, xl is the output lth layer embedding for the input x and {z0, . . . zk} ∈ Z.
As each function ψj = ψ ( 2 ρ (xl − zj) ) is supported on a ball of radius ρ2 centered at zj we get Qd+1(ψj) = ( 2 ρ ) dQd+1(ψ). From equation (42) it can be seen that hl is a linear combination of ψj
and hence by definition Ql(f) = maxx∈Bn ∑ |f (l)(x)| and substituting C(n, d) = 2d+1Qd+1(ψ) we have
Qdl+1(hl) ≤ max j
(Pl(zj)) C(n, d)
ρdl+1 ||fl ◦Wl||2dl (43)
sup(Qdl+1(hl)) ≤ max j
(Pl(zj)) C(n, d)
ρdl+1 ||fl ◦Wl||2dl (44)
From equation (44) it is evident that
RCd(Z) ≤ C(n, d) ρdl+1 ||fl ◦Wl||2dl Rdl(Z)
(45)
From equation (24) in theorem (3) we know that
C(n, d) ρdl+1 ||fl ◦Wl||2dl Rdl(Z)
≥ (dl + 1)! ( 8n
kρ
)−dl (46)
Simplifying equation (46) we bound Rdl(Z) as
Rdl(Z) ≤ ( 8n
kρ )dl C(n, d) ρdl+1 ||fl ◦Wl||2dl
≤ C(n, d) ρdl+1
( 8n||fl ◦Wl||2
kρ
)dl (47)
Since ||fl ◦Wl||2 ≤ ||fl||2||Wl||2 and as ||fl|| depends on the activation function which is a constant ||fl ◦ Wl||2 ∼ O(||Wl||2). The unknown constant C(n, d) which arises in equation (47) has an effect on the final generalization bound and to capture its effect in all the layers we introduce a single unknown parameter γ where 0 < γ ≤ 1. By the mathematical description of neural networks in equation (1), and using equation (10) which validates the multiplicative convergence (Kolmogorov; Bartle, 2014)
Rd(Z) = 1
γ [ l∏ i=1 ( 8n kρ ||Wi||2 )di] (48)
As we have assumed that the data to comes from a data distribution p with finite mean and variance we can now apply the strong law of large to obtain the final expression
EBn [l(N )] ≤ EZ [l(N )] +O
[ 1
γ l∏ i=1 ( 8n kρ ||Wi||2 )di] (49)

heading: 5 COMPARISON WITH OTHER BOUNDS
text: Some of the most promising norm based methods like that of Neyshabur et al. use spectral norm of the matrix to give tight generalization bounds. However, such bounds have an issue of scaling abnormally high with the size of weight matrices (Vershynin, 2011) which showed that for anm×n random matrix A with i.i.d entries the spectral norm is of order √ m + √ n, i.e. ||A||2 ∼ O( √ m +√
n) which scales with the number of nodes. Figure (1) demonstrates this on neural networks with varying depths trained on the MNIST dataset (LeCun & Cortes, 2010), the details of which has been relegated to the appendix.

heading: 6 CONCLUSION & FUTURE WORK
text: In this paper we introduced a novel generalization bound using geometric functional analysis. We have compared our approach to that of the previously existing spectral norm based generalization bounds and have shown the advantage of our method. We hope that this paper attracts more attention towards the use of geometric functional analysis in theoretical analysis of deep neural networks.
Future work includes extending this idea to specialized architectures such that various different properties of polynomials can be effectively leveraged to obtain architectural specific generalization bounds. Also finding an optimal value of the total number of training samples k which minimizes the generalization error would be an viable direction to pursue.

Review summaries:
The paper considers the problem of obtaining generalization bounds for deep neural networks. The paper uses tools from geometric function analysis to derive bounds for the covering number of neural networks, and derive generalization bounds using the covering numbers. The main strength of the bound as claimed by the paper is that they depend on Frobenius norm rather than the spectral norm, but I have several concerns about the results.

This paper aims at proving generalization bound via geometric functional analysis. Although the topic is interesting, this paper suffers from an unclear organization and there are some unclear points in the proof (see the following for more details). Therefore, I tend to give a "reject" and I hope the authors can provide more explanations for the theorems and carefully polish the writing in the next version. 

The authors study the generalization bound of neural networks. First, They assume that the activation functions as polynomials with certain degrees. Under this assumption, they prove a novel generalization bound using geometric functional analysis. The authors also compared their bounds with the method in (Neyshabur et al., 2018), showing that their bounds are better.