Improved Generalization Bound for Deep Neural Networks Using Geometric Functional Analysis
Authors: Phani raj Chinnalingu
Rajarshi Banerjee
Venue: ICLR 2022 Submitted (2022)
Keywords: Generalization bounds
Geometric functional analysis

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.

Under review as a conference paper at ICLR 2022
IMPROVED GENERALIZATION BOUNDS FOR DEEP NEURAL NETWORKS USING GEOMETRIC FUNC- TIONAL ANALYSIS
Anonymous authors Paper under double-blee blind review
ABSTRACT
Understanding how neural network behaves in multiple domains is the key to further its explainability, generalizability. and robustness. this paper, we prove a novel generalization bound using the fundamental concepts of geometric func- tional 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 the first approach which utilizes covering numbers to estimate such generalization bounds.
INTRODUCTION
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 al. 2017
Dziugaite & Roy| 2017: Neyshabur et al. 2018 Golowich et al. [018]] Nagarajan & Kolter 2018
Daniely & Granot 2019), More specifically, most of the state-of-the-an 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 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 per- spective (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, their parameters are generally huge and any frame work that finite will not cover all possible models. Specifically, our approach involves using the covering number of a vector space to derive bound for the generalization error of given neural network. However, comput- ing 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 '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 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 scale more rapidly with the size of the matrix (Vershynin 2011).
We approach the neural network in rather unorthodox manner by treating it as recurrent poly- nomial 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

---

Under review as a conference paper at ICLR 2022
the following sections along with other mathematical preliminaries. This is followed by several intermediate theorems, which are then used to derive our generalization bound.
2 RELATED WORK
The concept of generalization bounds were introduced (Barlettt 1998) rather indirectly by ana- lyzing the probability of misclassification (Zhang al. 2017) showed that uniform convergence over data points is what is required to understand the generalization of networks. Dziugaite & Roy (017)) obtained control, sharpness and robustness on generalization. (Neyshabur et al. 2018) used spectral norm to give 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.
vacuous bounds. (Neyshabur al. 2017) compared the effect of norm based
3 MATHEMATICAL PRELIMINARIES
3.1 POLYNOMIAL FRAMEWORK OF NEURAL NETWORKS
Consider the mathematical formulation of Neural Networks, neural network W with layers is function which takes input vector æ and returns vector (x) such that:
= fiW...WWWW.......... (W.
(I)
where W; is the weight matrix of network layer 8th layer, is the corresponding non-linear activation function. If I = [=]....e x".] is the output of the jth layer with ny nodes, then:
I = 9 (WIr1-1)
(2)
As mentioned earlier if the activation functions are approximated using polynomials then mathe- matically 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 (1-1,) be the weight of the neural network from the ith node in - 1 layer to the jth node in the 4th layer and P be the Polynomial approximation of the activation function. Then based on the above mathematical description of neural networks the output 2nd layer with n2 nodes is
n1
T2
Pi
(1.2)
21
Pi
(1,2) 02 x
P
(1,2) Ana
(3)
Similarly for the 3rd layer, 2y can be obtained as
12
R2
1)
n2
11
)
33
P2
j1
(2.3)
P
Σ
11
(1.2) m1
Ps
Σ
a
92
(2.3)
P
Σ a
2
1=1
j=1
(4)
n2
n1
...,
Ps
jna
(2.3)
P
aing
(1.2)
11
Clearly, by standard properties of polynomials the above tuple is also polynomial. Now, if we look into the pattern followed by each layer then the general form of the output at any arbitrary 7th layer can be obtained
2

---

Under review as a conference paper at ICLR 2022
R1-1
mi-2
21 =
Pt-1
Σ
11
(1-1.1
P1-2
Σ
i1
(1
(1-21111
1/t
1/-2
1=1
i=1
B1-1
Mi-2
P1-
Σ
j2
(1-1.1)
PI-
Σ
aj2
(1-2,1-1)
x1-2
(5)
/=1
i=1
RI-1
Mi-2
P1
Σ
(1-1
P1-2
Σ
1)
xt-2
jm
By the same logic applied hitherto the above tuple also a polynomial. The reason for such an unconventional formulation of neural network in the above framework is to analyze the degree of the polynomials using some of its basic properties. Regarding degree polynomials we have the following standard results:
For any C1 C2.... Ck E RR and polynomials P1, P2....Pp Pk
deg(c) Pi +... cx)p) c z sup (d)
(6)
i= ()...k
where deg(.) is the degree of the polynomial and for any polynomial Pa and Pb
d.)(P.PP)
By applying equation
on the first element of the vector øι from equation we get
1
2
deg
Pi-1
Σ
(1-1,1)
j1
P1-2
Σ
ai
(1221-1)
j=1
m1-11
M4-
deg (PI-1) deg
f1
(1-1.))
P1-2
Σ
an
(12.1-1) xf-2
112211
Similarly, by applying equation
(6)
on equation
we obtain
))
deg (Pi-1) deg
Σ
(-100)
P1-2
Σ
(-2,1-1) i1
<
deg deg((P:)))deg((PPa))))
(9)
By iterating over all the layers in the network and applying equation
we get
deg < deg((Rt))ddg((PPa)) ...gg)
(10)
We make use of the above inequality in the next sections in obtaining the generalization bound.
3.2 COVERING NUMBER
Covering number of 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 neural network on an unknown set by understanding its behaviour on a known one. Formally, (e, V) is the covering number of the space V. conceptually this gives measure of generalizability of the neural network on potentially infinite and unknown datapoints when trained finite subset (i.e. the training dataset). Thus, any bound on the covering number would imply that we can predict the lower limit the number of datapoints essential for accurate prediction on unknown sets.
3

---

Under review as a conference paper at ICLR 2022
3.3 VITUSHKIN'S S INEQUALITY
The Vitushkin's 's inequality (Friedland & Yomdin 2014; Yomdin 2011) has been widely used in ge- ometric functional analysis for studying the behaviour level sets of analytic functions (Kovalenko) 2017). Along with its many applications this inequality can be used to bound the covering number of metric space V using the lesbesgue measure (Burk) 2011 Bartle 2014).
Formally, let P(r, n, d) T2,1, IT)) ball of unit radius in re-dimensions and v₂((), be the set of all polynomials that bounded by p. i.e.
Z2.....
be polynomial of degree d in n variables, B" be
V((P) E IB" (P(x, n,
(11)
Then according Vitushkin's 's inequality:
n-
(1)
(
M(e, - Σ d(
+ un (V))
(12)
(
S Ma(e) + (V)
where (V) is the n--dimensional Leshesgue measure (Bartle 2014) of the set and Ma(e) are variables defined as:
C,(n, d) 2 2' 12 i
(d - 1)
(13)
Ma(c) 2 n-1
Ca(n, d)
3.4 METRIC (N,D)-SPAN
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 know- ing the Lesbesgue measure 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 C B", we define constant wa(2 (Z) which is the metric (n,d)-span of set Z denoted by:
war (2) sup (Mpp"[[((e,] 2) Ma(e)] c20
(14)
3.5 DIFFERENTIABLE RIGIDITY CONSTANT
The differentiable rigidity constant YYmdiin 2011 measures the minimum variation of a function which differenniable, i.e.
lower on the variation of function. Formally, let f B TR Cddt1 where d N and Qf()) max,e Σl El Here C* is the family of all times continuously differentiable functions and Σ [x) is the sum of absolute values of all the partial derivatives of of order I. Then the th differentiable rigidity constant given by
RCa inf Qa+1()) fEU,
(15)
where Ug is the set of all d++1 smooth functions f(2) on 1 vanishing on Z with Qo(f) 1.
3.6 REMEZ D-SPAN
The Remez d-span (Brudnyi & Ganzburg 1973 Yomdin 2011) measures the variation of the func-
tion when extended from smaller set bigger set, this instrument allows for extensive analysis
4

---

Under review as a conference paper at ICLR 2022
of neural networks when it transitions from the training the testing dataset. Formally, for any poly- nomial P. set C B" and E N the Remez d-span is the minimal number that is the ratio of supremum of polynomial the whole set to that of supremum of polynomial on the set Z
su Sup
Ra(Z) = min K
I
(16)
sup2 P
3.7 BRUDNYI-GANZBURG' INEQUALITY
inequality (Brudnyi & Ganzburg. 1973 Yomdin 2011) tells the varia- tion in performance from a continuous train dataset to test dataset. However, it is not applicable for discreet datapoints as the case when deep neural networks and have use of Ra and RC., to derive the corresponding bound for the discreet dataset. Let B C Rn be a convex body and let let Z C be a measurable set. Then for any real polynomial P(æ) = P(x1..... Fn) of degree we have
The
1+ (1 A) 1 X)
sup Pl S Tá
sup |
(17)
Here (92) n., (B) with (n being the Lebesgue measure R² and Tg is the Chebychev polynomial of the first kind RRvllin 1974).
THEOREMS
Theorem ① gives a bound on differentiable rigidity constant in terms of the Chebychev polynomial and since this has closed form solution it is computationally efficient to obtain Ra (Z).
Theorem 1. If (Z) > 0 and pm (V 2 wa( ()) is finite and it satisfies the inequality
1 (1 ()))
RZ S Ta
(18)
(1 w. (2))
Proof. Suppose P| < on Z. Clearly Z C (P(P) as P is bounded in absolute value by 1 on (P). Then by applying Brudnyi-Ganzburg' inequality 117 with B R and (P( we get the above expression.
Theorem 2. For any real number 0 < w S 1 the following inequality holds
4n
Ta
(19)
Proof. We use the simplified expression of Ta(x) when r 2 1, then by simple algebraic manipula- tions get
1 1 y
d
Ta
(20)
2
1 -
By substituting y = (1 w) in equation (00
we obtain
1 + (1 w)
1
1 (1 (-)) w)
Ta
2
(21)
1 - w)
2
(1 w
Now, as n. < 1 and < 1, by applying Bernoulli's inequality on y we obtain
(1 w) <
(22)

---

Under review as a conference paper at ICLR 2022
Applying equation
22 in
21
leads to the final result
1 w
4n
1- w
w
+ w)
4n
d
-
(23)
1 (1-
w
(1
4n
To
Theorem 33) gives relation between the differentiable rigidity constant and the Remez d-span, this enables us relate our generalization bound with Remez d-span.
Theorem 3. For any subset Z C B and d E N
RCx(Z)) Z (Z
(24)
Proof. Let f B -R. Ch, P(n, d) is the set of all real polynomials of degree in n variables and for d E N we define [a( as
Ea(f) = min max [f(x) P(x)
(25)
PEP(n,d) aEB
Let Pa(x) be the polynomial of degree for any fixed d such that the minimum is achieved. Thus, equation (25) can we rewritten as
Pa(S)
max [f(x) Pa(x)) =EB*
(26)
By applying the triangle inequality on equation 26 for the subset E B we obtain
max Pa(x)) xEZ
< max [f(x] + Ea(f)
(27)
xE2
By the definition of Remez d-span in equation (16) we get
max Pa(x)) < Ra(Z) Ea()
(28)
REB
where max [f(x)). Again, by applying triangle inequality on max [f(x) we get
max
[fx)]
max [f()) Pa(x))
max Pa(x))
(29)
zE2
=
ZEB"
By combining equation
28
and equation
29
we get
max [f(x) < Ea(f) + R EE())
(30)
zE
As the inequality in equation
30
holds for any value of we therefore get
inf
(Ra (2)
IL Ea(si]
< inf [R( Ex())) Ex()
(31)
d
de (o.o......11
Let Ef(F) max
|| and as Ea(f) < (f) equation (1) further reduces (d+1)]

---

Under review as a conference paper at ICLR 2022
max TER
[f(x)]
inf de dE(o....k_1)
[2(Z))L+ + + EX0
(32)
For finite set Z U {x) where x E T we define the function fz. as
So. i Z 11
(33)
if B
Let fz.0 be the analytic extension of fz,= to IB", Then by applying equation 32
we obtain
Qo(fz,))
inf de de(0....k-11
+ E((
(34)
If L = 0 and Qo(f2,,) 2 then
1 x min
11
(35)
dE dE(U....k-1)
Thus, Qa+1 Ra(2)+I and by the definition of the rigidity constant in equation (15) get desired result (C,(Z)) 2 2Ra(Z)
Let be the minimum distance between any two points in set Z with cardinality l:
P min EZ
|
x2ll
(36)
And for neural network N with n input nodes and di be the degree of approximation the activation function for the Lu then the following theorem holds true
Theorem 4. The product of k and p is bounded by the metric (n, d) -span of the set Z for any n and d:
Wd, (Z) 2 kp
(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 tion bound for deep neural networks.
and now derive generaliza-
Theorem 5. The loss I(N) incurred by the network N using the loss fanction I on the super-set B given the loss in the subset Z is bounded by
4
Eg ((N)) < EZ(((N] +o
II
8n kp
w.ll
W
(38)
Proof. Let us assume that the input the neural network is randomly sampled according continuous probability distribution (i.e) Bayesian assumption. We first obtain the bound for the randomly generated input and thereby extend to the deterministic case by using the strong law of large numbers.
(P(P) fa n
P(x)) S p) if C Vp(P) then M(c, Z) S M(c, (o(c) and further using
Vitushkin's 's inequality [12 we get
M(e, Z) & M(e, VV(P) < Ma(e) + (V) (
(39)
So (c, Z) Ma(c)Je" p., (V) for all and by taking supremum of both sides get
u. (V) 2 wa(22 (Z). On combining equation (18) from theorem (I) and equation (19) from theorem
get
7

---

Under review as a conference paper at ICLR 2022
1 Ro(Z) 5
(_4n
4n wa(
2)
2)
(40)
is easy to see from equation (40) follows that
An
-
4n wx(2)
and by applying
2x)
equation (37) from theorem (4) we can further simplity the equation (40)
4n
d
Ra(Z)= S
(41)
kp
For any E B" we define special function which captures the effect of sample points on the generalization behaviour, mathematically we define it as
h((21) P((x:) - E P((y)a 2 (2 Ilft Wille
(42)
where vi is a C function on E such that (0) 1 and &b vanishes on the boundary on 8", x is the output 4 layer embedding for the input x and {zo.....x) E Z. .x.
As each function bi + (3( z;)) is supported on ball of radius & centered žj get
Qu+1(w)) (2) Qa+ (+)). From equation (42) it can be seen that hy is a linear combination of v/
and hence by definition Qi()) m (x)) and substituting C(n, d) 2 Q we have
C(n, d) pdit1 Ilfe Will
Qu+1( S max(
(43)
C(n, d) pditI
sup(Qat+1 S maxx(P((2)))
Ilft Will2d
(44)
From equation
it is evident that
C(n, d) IIfi o Will2a p4+1 Ra,(2)
RCa(Z) <
(45)
From equation
24 in theorem know that
C(n,d) IIft Willad: Rd, (Z)
8n kp
(di + 1)!
(46)
pd++1
Simplifying equation
466) we bound Rd, (Z) as
Ra, (Z)
8n
C(n,d)
pait1 p
IIfe 11fe
Will2d
kip
(47)
C(n, d)
(8n|lfi o 2
p
kp
Since I [| and as [[fill depends on the activation function which is a constant I]ft 2ill (1.... The unknown constant C'n, d) which arises in equation (47) has an effect on the final generalization bound and to capture its effect all the layers we introduce a single unknown parameter y where 0 < 1. By the mathematical description of neural networks in equation (T). and using equation I0 which validates the multiplicative convergence (Kolmogorov Bartle 2014)
8

---

Under review as a conference paper at ICLR 2022
Ra(Z)
1 7
II
1
8n kp
[w&l??
4.
(48)
As we have assumed that the data to comes from data distribution with finite mean and variance we can now apply the strong law of large obtain the final expression
8n
d
E2 [(AN E2[((N] O
[ (13)
(49)
kp
5 COMPARISON WITH OTHER BOUNDS
Some of the most promising norm based methods like that of Neyshabur et al. use spectral norm of the matrix give tight generalization bounds. However, such bounds have issue of scaling abnormally high with the size of weight matrices (Vershynin, 2011) which showed that for an m x n random matrix A with i.idd entries the spectral norm is of order /m vni i.c. ||Al|2 Olym + yn) 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.
Neyshabur 2018
7.5
Our
Log(d)und)
6
4.5
3
6
12
Depth
Figure 1: The comparison of our bound with spectrally-normalizee normalized margin bound Neyshabur al. 2018) with neural networks of increasing depths trained on the MNIST dataset.
CONCLUSION & FUTURE WORK
In this paper we introduced a novel generalization bound using geometric functional analysis. We have compared
approach 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 which minimizes the generalization error would be viable direction to pursue.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp- 254-263. PMLR, 2018

---

Under review as a conference paper at ICLR 2022
Robert G Bartle. The elements of integration and Lebesgue measure. John Wiley & Sons, 2014.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normaaizee margin bounds for neural networks. Advances in Neural Information Processing Systems, 30:6241 6250, 2017.
Peter L Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525-5360 1998.
Alberto Bietti, Grégoire Mialon, Dexiong Chen, and Julien Mairal. kernel perspective for regu- larizing deep neural networks. In International Conference on Machine Learning, pp. 664-674. PMLR, 2019.
Yu A Brudnyi and Michael Iosifovich Ganzburg. On an extremal problem for polynomials in n variables. Mathematics of the USSR-Izvestiya, 7(2):35,, 1973.
Frank Burk. Lebesgue measure and integration: an introduction, volume 32. John Wiley & Sons, 2011.
Amit Daniely and Elad Granot. Generalization bounds for neural networks via approximate descrip- tion length. Advances in Neural Information Processing Systems, 100000000666,,, 2019.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Omer Friedland and Yosef Yomdin. Vitushkin-type theorems. Geometric aspects of functional analysis, pp. 147-157. Springer, 2014.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- sizeenndepnnd sample complexity of neural networks. In Conference On Learning Theory, pp. 299. PMLR, 2018.
Richard B Holmes. Geometricfunctionu analysis and its applications, volume 24. Springer Science & Business Media, 2012.
Andreī Kolmogorov. Introductory real analysis.
Oleg V Kovalenko. Ostrowski type inequalities for sets and functions of bounded variation. Journal of inequalities and applicaations, 2017(1):1-16, 2017.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URLhttp:///pe
lecun Beccu.ccom/exooo exdd//nixm/miii stt
James R Munkres. Topology, 2000.
Vaishnavh Nagarajan and Zico Kolter.
Deterministic pac-bayesial generalization bounds for deep
networks via generalizing noise-resilience. In International Conference on Learning Representa- tions, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring general- ization in deep learning. Advances in Neural Information Processing Systems, 30:5947-5956.
2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to
spectrally margin bounds for neural networks. International Conference on Learn- ing Representations, 2018.
TJ Rivlin. The chebyshev polynomials, pure and applied mathematics, 1974.
Matus Telgarsky. Neural networks and rational functions. International Conference on Machine Learning, pp. 3387-3393. PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2022
Roman Vershynin. Spectral norm of products of random and deterministic matrices. Probability theory and related fields, 150(3):471-509 2011.
Yosef Yomdin. Remez-type inequality for discrete sets. Israel Journal of Mathematics, 186(1):
45-60, 2011.
Randy K Young. Wavelet theory and its applications, volume 189, Springer Science & Business Media, 2012.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization (2016). arXiv preprint 11115:6111003500, 2017.


Reviews:
[{"review_id": "xoVQbZeWKff", "reviewer": "Reviewer_FW5M", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe main strength of the paper is in bringing tools from geometric function analysis to understand generalization of neural networks. There are several tools which are used which seem interesting, and could potentially be valuable in deep learning theory.\n\nWeaknesses:\n\nUnfortunately there are several concerns regarding the presentation and the writing due to which I recommend rejection. To begin, it does not appear to me that the bound in Thm 5 actually has the nice properties that the authors claim. First, the authors say that in contrast to prior work their bound does not depend on spectral norm. However, I think the $\\rho$ in Thm 5 could implicitly hide the spectral norm dependence. $\\rho$ is the maximum value the polynomial can take in the domain, which just seems like spectral norm. Additionally, the authors say that the spectral norm guarantee is worse because for a mxn random matrix the spectral norm is $\\sqrt{m}+\\sqrt{n}$ which depends on $m$, but the Frobenious norm for such a matrix will scale with with $\\sqrt{mn}$, which is much worse. Thm 5. additionally hides dependence on other parameters too. The big-oh notation hides $1/\\gamma$, which is $C(n,d)$ which seems like it could be exponentially large in $n$ and $d$. \n\nThis brings me to a major concern regarding the presentation of the paper. The paper is not well-written, to the extent that it is difficult for me to do a sanity check of the results to make sure of their validity. To begin, the notation is not well-specified and is quite confusing. For instance, Thm. 5 uses $l$ both for the loss function and the depth of the network. The paper should clearly state in the beginning (and in the thereom too) what $n, d$ and $k$ are (in fact, I'm still not fully sure what $k$ is in the context of the neural network, not the polynomial). The proof also doesn't seem rigorous and I cannot be sure that it is correct, for e.g. the authors say in Eq. 49 that they use the law of large numbers to get the concentration, but what is needed here is a finite sample guarantee, not asymptotic convergence which the strong law of large numbers gives. The right concentration bounds need to used, and the failure probability needs to be analyzed here. In fact, the generalization bound in Thm 5 does not even depend on the number of samples, which is strange. \n\nThe authors should also spend much more space discussing the tools from geometric function analysis. Some of the proofs can be moved to the appendix, and the entire analysis in page 3 for products of polynomials seems a bit trivial and unnecessary to spend so much time on, when there's more interesting stuff to talk about.\n\nThe paper also seems to say that it is the first to derive covering number bounds for neural networks, but these were also derived by Bartlett-Foster-Telgarsky. \n\nThe idea of using geometric function analysis for deep learning theory seems interesting and I encourage the authors to pursue this more, but the paper falls short of the bar.\n\nTypos:\n\n1. page 1: 'it generalization problem'\n2. page 4: 'lower on the variation of a function'\n3. it should be mentioned that the norm is the Frobenious norm in Thm 5.", "summary_of_the_paper": "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.", "summary_of_the_review": "Due to the above issues regarding the results and the presentation, I recommend rejection for the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "p-EM-maAdqk", "reviewer": "Reviewer_YPEk", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I recommend rejection, for the reason that the theory in this paper (i.e. the main contribution) is either incorrect or missing many crucial steps. The statements and proofs brush many details under the rug and hence are very difficult to verify. Even if there is a correct underlying argument, I believe the paper would benefit from substantial revision and submission to a later venue.\n\nHere are some of the concrete mathematical issues I found with the paper:\n\nInitial theorems\n- The definition of the Remez d-span R_d(Z) seems incorrect; it should be a supremum over all degree-d polynomials (the notation does not have a dependence on P, and e.g. Theorem 3 would not make sense if R_d(Z) is defined for a specific polynomial)\n- Given this, Theorem 1 does not make sense. It seems to be saying that if there exists a polynomial P satisfying \\mu_n(V_1(P)) >= \\omega_d(Z) then there is an upper bound on R_d(Z). However, since R_d(Z) is a supremum over polynomials, it does not seem possible to upper bound it just by looking at P. Indeed, the proof seems to bound |sup_B P| / |sup_Z P| via Brudnyi-Ganzburg, but this does not bound R_d(Z).\n\nTheorem 5\n- In equation (43), why is ||f_l \\circ W_l|| raised to the power (2d_l)?\n- I don't understand how equation (44) implies equation (45). Certainly by definition RC_d(Z) <= sup Q_{d_l+1}(h_l) / sup Q_0(h_l), but now you seem to upper bound |max_j P_l(z_j)| / |sup Q_0(h_l)| <= |sup_Z h_l| / |sup_B h_l| <= 1/R_{d_l}(Z), but the last inequality goes in the wrong direction.\n- I also don't understand how equation (46) is obtained from (45) and (24).\n- The last sentence on page 8 is crucial to the whole proof, and does not make sense to me. Given upper bounds on R_{d_l}(Z), how do we upper bound R_d(Z)? Certainly it's not multiplicative. Equation (10) is about multiplicativity of degree when composing polynomials, but I don't see how that's relevant.\n- What is the loss function used in the statement of Theorem 5?\n- Why does 1/gamma disappear in the statement of Theorem 5? It's not a constant; it's exponential in the dimension.\n\nExperiment\n- Was the \"constant\" 1/gamma taken into account in experimentally computing the generalization bound?\n- The closest-pair distance of the dataset was estimated by taking a subsample. This seems wrong; if there is a single pair of very close images, then the subsample closest-pair distance may be much larger than the true distance, which would artificially strengthen your generalization bound.", "summary_of_the_paper": "This paper claims to contribute a novel generalization bound for deep neural networks based on treating the network as a polynomial (for polynomial activation function) with degree bounded by O(depth). This bound is experimentally compared against the norm-based bound from the prior work [NBS18].", "summary_of_the_review": "I recommend rejection, for the reason that the theory in this paper (i.e. the main contribution) is either incorrect or missing many crucial steps. The statements and proofs brush many details under the rug and hence are very difficult to verify. Even if there is a correct underlying argument, I believe the paper would benefit from substantial revision and submission to a later venue.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bmJ2rhVHTqw", "reviewer": "Reviewer_3Prr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Maybe I lose some details, I am still puzzled on how to go from Eqn48 to Eqn49. Could the authors provide more details? Besides, could the authors explain how to go from sup over the Z (in Eqn 16) to mean over the Z (conclusion in Theorem5).\n\n2. Could the authors explain the statement: \"Another by-product of the analysis is that the bound obtained is in terms of the\nFrobenius norm of the weight matrices rather than its spectral norm, which has shown to scale more rapidly with the size of the matrix\". In my opinion, F-norm will produce a worse bound than the spectral norm.\n\n3. I believe this paper can benefit a lot from more careful writing and some more precise statements. For example, could the authors validate the statement “this is the most suited framework for dealing with deep neural networks” (in the introduction part)? \n\n4. This paper is not well organized. For example, Eqn3 and Eqn4 contain little information. Besides, some common techniques like the covering number are not encouraged to be introduced in the main text (since they are not strongly correlated to the main theorem). And each subsection in section3 is too short. \n\nSome other comments:\n\n1. In the second line of Eqn12, the symbol “\\leq” may be improper. \n\n2. There are some typos in the main text, for example, the introduction part: “it is widely in the ***”. Section3.5, f^l or f^{(l)}.\nMissing ) in Eqn39.\n\n3. What is the “strong law of large”, missing number?\n\n4. Missing | in Eqn16.\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "It seems this paper is not in its shape to be published due to the above concerns, including the concerns on the proof and the unclear statements. More explanations on the theorem and the proof procedure may help reshape the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OidUeuH_nlh", "reviewer": "Reviewer_nLh5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength** \n\nThis is a novel framework for the study of the generalization behavior of neural networks. Novel perspectives of the paper in my opinion are using a polynomial to approximate the activation function of neural nets and importing Vitushkin’s inequality to bound the generalization error via covering numbers. The tools introduced are likely to be useful for other analyses in a different context.\n\n**Weakness**\n\n* Approximating the activation function using a polynomial p(x) is unlikely to be accurate for unbounded x.\n* The presented bound is algorithm-independent and is expected to be very loose for neural networks trained with SGD.\n* More background literature on the generalization bounds of neural nets can be included. For example, \"Information-Theoretic Generalization Bounds for Stochastic Gradient Descent\" (Neu, 2021)\n* The experimental verification seems lacking. The authors are encouraged to compare the developed bound with the true generalization error for various network architectures and datasets and compare the bound against other bounds developed for SGD.\n* A question: In Figure 1, what is the degree of the polynomial approximating the activation function? How is the choice justified?\n", "summary_of_the_paper": "The paper presents a new generalization bound for neural networks, which is shown to be tighter than the bound in [Neyshabur 2018]. ", "summary_of_the_review": "The paper presents a novel framework for bounding the generalization error of neural networks. The techniques introduced in the paper are likely to have a broad impact. But the algorithm-independent nature of the developed bounds is likely to make the bound compare inferiorly to bounds derived specifically for SGD.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8NYm8ABJmxC", "reviewer": "Reviewer_SWDb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written and well organized. I find it easy to follow. Also, this paper is technically sound. However, I think the assumption that activation functions of neural networks are polynomials with certain degrees, makes the contribution of this paper limited. Although many functions can be approximated by polynomials, this does not mean that replacing activation functions with polynomials is a good idea, since the errors can be accumulated layer by layer. Thus, the function assumed by authors could be far away from the actual function of a given neural network. Hope that the authors make more discussions on this issue. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "Although this paper is technically sound, I think the polynomial assumption on activation functions of neural networks is not very convincing, making the contribution of this paper limited. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a new geometric functional analysis perspective for the generalization bounds for neural networks. As the AC, I actually quite liked the twist the authors are providing for this particular work. Unfortunately, the current presentation is too crude to provide an elementary picture for the developments and I strongly encourage the authors to revise the paper for the next deadline based on the remarks from the reviewers.
Decision: Reject