Reproducing Kernel Banach Space Models for Neural Networks with Application to Rademacher Complexity Analysis
Authors: Alistair Shilton
Sunil Gupta
Santu Rana
Svetha Venkatesh
Venue: NeurIPS 2025 poster ()
Keywords: uniform convergence
rademacher complexity
resnet
transformer
Primary area: theory
TL;DR: We construct an exact RKBS model for neural networks with arbitrary width, depth and topology and use this model to derive tight bounds on Rademacher complexity.

Abstract: This paper explores the use of Hermite transform based reproducing kernel Banach space methods to construct exact or un-approximated models of feedforward neural networks of arbitrary width, depth and topology, including ResNet and Transformers networks, assuming only a feedforward topology, finite energy activations and finite (spectral-) norm weights and biases. Using this model, two straightforward but surprisingly tight bounds on Rademacher complexity are derived, precisely (1) a general bound that is width-independent and scales exponentially with depth; and (2) a width- and depth-independent bound for networks with appropriately constrained (below threshold) weights and biases.

Reproducing Kernel Banach Space Models for Neural Networks with Application to Rademacher Complexity Analysis
Alistair Shilton, Sunil Gupta, Santu Rana, Svetha Venkatesh
Applied Artificial Intelligence Initiative,
Deakin University, Geelong, Australia
alistair shilton&deakin edu.au, au, sunil gupaadeakki edu. au, santu. www.rrraaannnnnneemmm edu. au, svetha. venkateshhdeakinn edu.an au
Abstract
This paper explores the use of Hermite transform based reproducing kernel Banach space methods construct exact or un-approximated models of feedforward neural networks of arbitrary width, depth and topology. including ResNet and Transform- ers networks, assuming only a feedforward topology, finite energy activations and finite (spectral-) norm weights and biases. Using this model, two straightforward but surprisingly tight bounds on Rademacher complexity are derived, precisely (1) general bound that is width-independerr and scales exponentially with depth; and (2) width- and depth-independent bound for networks with appropriately con- strained (below threshold) weights and biases.
Introduction
significant challenge in neural networks understanding how large models, despite their high capacity to overfit training data, can still generalize effectively (Neyshabur et al. (0144). Learning theory tells us that inductive bias plays an important role in explaining this phenomena, where inductive bias is the restriction of the space of potential learned functions (neural networks) to a small subset FF of the total space of space, either explicitly through regularization or implicitly through the training algorithm used. Rademacher complexity (Bartlett & Mendelson 22022; Steinwart & Christman 2008) is one measure the complexity or expressive power of F that has been used to understand inductive bias through the lens of uniform convergence that is, the rate at which the empirical risk (on the training dataset of N samples) converges to actual risk (on the data distribution) (for discussion of alternative approaches see (Valle-Pérez & Louis (020)) A representative approach to Rademacher complexity analysis neural networks is "peeling" (Neyshabur et al.) 20155 Golowich et al. 2018 Truong 2022). In this approach, the total compexity is bounded by "peeling off the output layer to extract factors due to that layer and thus express the total Racehmacher complexity as product of terms due to the output layer D and the Rademacher complexity of the preceeding (D - llyyr network. The process is then repeated, peeling off successive layers until the process terminates the input layer. This typically results in bound that exhibits width independence (assuming popular schemes such as LeCun, He or Glorot weight scaling) and exponential depth dependence, and contains some (typically Lipschitz-type) scaling term due to the neural activations as well a (typically depth-exponential) "nuisance factor". For example in (Neyshabur et al.) 2015) is shown that, for simple unbiased layerwise network with spectral-norm bound weight matrices Wollo and Lipschitz activations, the Rademacher complexity is bounded as:
12 11 wi 1:2
RN (F ( s wلدا O
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This bound can be refined in various ways (eg. (Golowich et al. (2018), but the basic form remains, as do the nuisance factors (the term 2n in the above bound, for example) in one form or another.
An alternative approach is to construct a bilinear (dual) representation of the model that splits the input x E X and parameters ④ E W into separate terms in a dual representation:
(x; = (v (+) (x))
where V W + W. Φb X X' are feature maps and ( [] W X' - R is continuous bilinear product. Examples of this type of model are the neural network Gaussian process (Rasmussen & Williams 2006) (NNGP) models (Neal 1996). which treat all layers prior to the output fixed and model the influence of the weights in the output layer; neural tangent kernel (NTK) models (Jacot et al. 2018 Daniely 2017 Daniely et al. 2016), which model the (first-order) variation of the weights about their initial values in a reproducing kernel Hilbert space (RKHS) (Aronszajn, 1950)
(see for example (Du al., 2019b Allen-Zhu et al.] 2019 Du et al.. 2019a Zou al. 2020 Zou &
2019 Arora et al. 22 10 Cao & 2019)) and reproducing kernel Banach space (RKBS)
(Lin et al.
2022
Zhang et al. 1009/ZZang & Zhang 2012 Song al. 2013 Sriperumbudur et al.)
2011: Xu & Ye
2014) approaches such as (Shilton et al. 2023). which recursively construct feature maps V W- W. Φ X + X' exactly model the neural network (beyond first-order) In all
cases the utility of the model in the context of Rademacher complexity analysis is that it makes the construction of bounds straightforward through the use of either the Cauchy-Schwe Schwarz inequality (if ( is an inner product) or the continuity of the bilinear product; and moreover, as peeling is not applied directly the Rademacher complexity, nuisance factors arising from this procedure may be avoided. However the assumptions made by these models (wide-networks, lazy training, restrictions
on neural activations and network topology etc (Arora et al., 2019b] Lee al., 2019 Bai & Lee 2019) can complicate analysis and limit their applicabilityy
Our goal in this paper is address questions, (1) can we formulate exact (non-approximate) model for a wide class of neural networks, including ResNet and Transformers, avoiding entirely
the question of gaps between the performance of the neural network and its model; and (2) can such a model be used to derive straightforward, non-vacuous, widely applicable, bounds on Rademacher complexity without nuisance factors. We answer these questions with the following contributions:
1. Exact RKBS model (Theorem I):
For feedforward neural network with arbitrary topology, finite weight and biases and finite-nnery neural activations, we construct an exact model that recasts neural networks elements in a reproducing kernel Banach space (RKBS) defined by the bilinear product:
f (z: ( (9), (x))
where V : W + W a weight/bias feature map, & X + is a data feature map, and ( (.-g g W x X + R is continuous bilinear form characterized by indefinite metric g.
2. Rademacher Complexity Bound (Theorem f) We observe that, for our RKBS model:
(2; S Ce | (x)
where Co S and, using this, derive a straightforward non-asymptotic bound for the Rademacher complexity of very general class of neural networks (including ResNet and Transformers) that is width-independent, depth-exponential and contains no nuisance-factors For example for a scalar-valued, layerwise, fully-connected, unbiased ReLU network of depth D, our bound is exactly:
- VN
Rx (F: Wb-11:) ||2 I wii-l <
where || 112 is the spectral norm. More generally, we derive conditions under which the Rademacher complexity bound is both width- and depth- ingpeeedddee,dntt, and subsequently
(F) < 1_ and discuss implications for ReLU, ResNet and Transformer networks.
VN*
"Beoond bilinear RKBS Lin et al.
2022 more general RKBS models have been used in eg. (Bartolucci
al.
2023
Sanders 2020 Shilton et al.
2003 Parhi & Nowak 2021 Unser 2021 2019 Spek al. 2022

---

Layero
Layer1
Layer
Layer
Nodaj
X091
x7.11
x01
WD:11
x!1
wtr
xlr
Neural Activation
Weight
Combine
Bias
Figure 1: Layerwise feedforward neural network structure. Each layer j E ZD contains nodes L,Lal, where the output of the node is computed as shown in the inset. Note that computational skeleton (Daniely et al. 2016) with one input and one output can be modified to this form by inserting skip nodes (nodes with Ab) (ī), w = I, bbi = 0, -.o] id) into the graph as required.
1.1 Mathematical Notations
Vectors and matrices: Column vectors are a, b with elements a, bj. Matrices are A, B with
elements Aij. rows A; and columns A.j- |a| and sgn(a) are the elementwise norm and sign. ||A||2 max (A) is the spectral norm and ||A|| is the Frobenius norm. A B. A 8 B, A A
are Hadamard, Kronecker and columnwise Kronecker (Khatri-Rao Raatrii-aa) product. A e B = [A T B is
columnar matrix concatenation. A OO A timex() is the exponentiation for operator O.
Products and norms: (,,)) (1 (.......)) >) and ( are inner, multilinear and bilinear products, where (a. b) E; a,b,, ((a, b, c....) .) E, a.b.c.... (a, b) & = E; g.a,b, and (A, b) throughout. We also find it convenient to define an operator form (1)), a; = ((11. a2 ............
E.
Sets and functions: N {0, 10,1.... 1, 2+ 2,, J. EN = {1,..., N). 0A is the boundary of A. (a) a. [a]+ = max (a, 0}. |a]+ = [[..]]]: a (0b) sgn(a) @ a o DDrr & Lee 2007
L [R E [(I])) (T: - [CER= 1B2 KK dāc are the finite-energy functions.
Multi-indices: Multi-indices are k, N with elements ki, 4- [k| = E, k! ПI k4. 2 a² 11. a ( = II. (*) Det II. ghe We use the shorthands k >n /for E N and [ > 4
In for N and k I, inn for k N and k 1, In for E N" and |K S..
Hermite Polynomials: Hey are the (probabilist's) Hermite polynomials. Hex(x) = II, Hes, (x;)
the multivariate Hermite polynomials. He (e), He. Heg (0) the Hermite numbers (Abramowitz et al. 1972, Morse Feshbach 1953 Olver et al. 2010 Rahman 2017).
Indexing Conventions: Layers are j E 7. (there are D) layers). Nodes are j E ZE (there are E nodes). Layer contains nodes L C Zg: Ujezp Lbi Zg. L(ii n 0Vj + j'. Node e
[ in layer has parents j E A C ----)) L L(P) {E} are the input/output layers.
2 Setting and Assumptions
We consider layerwise feedforward neural networks as shown in Figure T This contains E nodes
j E Eg arranged in D layers E Zp and virtual input node j 0 (in virtual layer j = 0), where layer E Zp contains nodes [ C e and layer D) contains a single output node F.. A node j E T has parents Abi C ا with its function being specified by an operator O {s, Σ @, (-)) Given input æ, data flows from node j = node j E as per Figure
ar
O
W
Gvl + 1 bbbi
R
JEAU]
Vj ZØ
(a)
(1)
x [if]
- (zlli)
R n
Vÿ Ab
f (x; θ)
3

---

AlaYOs MASER
(b) Attention Block
W 3044
10
RoLU
W
BaLU
(c) Residual Block
(a) Single-Query Attention Block
Block Type
Norm-bound (sce Appendices
DJ1
D.2
D3
and D.4
Residual Block
6
+II
on
LayerNorm Block
H
H
Single. Suel--yrrry Attention Block
4
Single-Hon Head Attention Block
(for queries)
Norm
(c) Bounds Relevant to Section 2.1
LayerNorm Block
Figure 2: Residual, attention and LayerNorm blocks. In the residual block (0, 1). The single- query attention block (a) is for single query ø1,Q with keys 21,K- K. and values 21,V, 22, ... A single-head attention block (b) formed from multiple single-query blocks (the usual (matrix) output has been vectorized here). See Table 3 for definitions of neural activations used here.
neural activation functions; W weight matrices; bld biases; ااu E {0, 1} (unbiased and biased); and θ {-i b : E Eg.Je Abl.. We assume that:
where -l7d 4
(55))
1. Bounded inputs: i E X {ar E R ||0|||| I 1}.
2. Finite weights/hiases: E = (Wi7)) bbl: w 2, bbbl <0 :300,,
3. Finite activations: -0-1l 2 ( - IICI1 vg Abl, E ZE.
(4. Lipschitz/Bounded activations: and 0% = {x E 12" ||æ||| 1} if any - are non-Lipschitz.)
-0:] is either Lipschitz or bounded Vÿ E AbI j ZF.
Note that assumption is not required when constructing bilinear feature space model of neural networks, but is required to cast this model in RKBS and subsequently derive our Rademacher complexity bound. The set of neural networks satisfying assumptions is F, and its dual is Ft:
F= F
θ
X + |T| as per [ satisfying assumptions 1-4) W
Rm f as per satisfying assumptions 1-4)
This model is rather general encompass wider variety of network architectures. Residual (He et al. 2016) blocks can be built using additive nodes obul Σ as shown in Figure 2.. Single

---

Neural Activation
L*(R", (KlE))
Lipschitz (L,)
Bounded (B)
Valid here
Lineur
-() C
ReL.U
(C) K
V (1)
Poly- R
(()((4) K
(paP-1)
Tanh
(()
Baan(G 44
(1)
Sigmoid
r (()((()
V (+)
Softmax
(C)
chfer
(()
Softmax;
(C)
(A)
Norm
(()
x
(())
Figure 3: Characteristics common neural activation functions. We include poly-ReLU (Cho Saul 2009) here as an example where the Lipschitz constant L. of T/a depends on the radius See (Gao & Pavel 2017) for more detail regarding the softmax Lipschitz constant.
query attention blocks (Vaswani et al. 2017) can be constructed shown in Figure 2 using not just additive but also inner- proouct CD = (-)). multiplicative o = @ and columnar concatenation اbill = + nodes. Full attention block can be constructed as shown in Figure 2p (and similarly multi- head attention). Finally, a LayerNorm (layer normalization (Ba et al. 20166) block is shown in Figure Zt. We note that blocks of this sort may be combined to form more general networks. Later, we find convenient to include non-trivial nodes or blocks in the network, so for example we may speak of an "attention node" j that encompasses (abstracts away) complete attention block (Figure[p).
2.1 Characterization of Neural Activations
As noted previously, assume all activation functions in the network are Lipschitz/bundee and finite energy. The finite-energy assumption allows us to apply the Hermite transform to the neural activation functions and subsequently construct bilinear model of the network, while the Lipschitz/buunded property suffices to ensure that the bilinear model is continuous. Starting with the mhite-eneryy assumption, the multivariate (probabilist's) Hermite polynomials (Abramowitz et al.)
1972: Morse & Feshbach 1953 Olver et al. 2010 Rahman 2017) are, for multi-index k E N":
He, (C) = (-1) e 11C1 aq
1
Σ Hez-
where Hex
He) are Hermite numbers. These form an orthogonal basis of L2 e 11113
(Appendix)
By assumption +(7d]] ( --- --l111)), and thus the Hermite transform exists
-i (C) = DDil (0) + k>
Σ #5
a
Gol
Σ He)
0 15*
(3)
where: [JJ] /2nk! Scepenin
(n
(C)
+ اlاا| (0)) Hex (C) e -11SSB
[7:11
From this we define the magnitude functions 87
:R, - RR+ (where 17 E R.4:;:
8q (<) 17² [ud (0)]1 + Σ
poil
[ol a
(1 (c) 1111-1
(4)
K
which are monotonically increasing and superadditive on R4,. Note that while the Hermite transform terms and magnitude functions play important role in the construction of our model, they play no role in our subsequent analysis of Rademacher complexity (they vanish in our analysis in the limit ? O+). Thus, for our purposes, beyond their existence (which is guaranteed), their exact value/form does not matter here. Nevertheless, see Appendix B for a full analysis of the ReLU activation.
Regarding assumptions if Jol|a (70)) restricted ball of radius a) is Lipschitz then we denote the Lipschitz constant by [Pd]] Conversely, if ( is absolutely bounded, we denote the bound B08)), where D (C) < BDDl VÇ. While assumption| 4 is not required to construct our bilinear
dual representation we find it useful include L!!ssl here to simplify later results. When [ is ill- defined we use the nominal value [ = Blisi / in the bounded case, or [7,1] = 1 if assumption 4 is not satisfied. Table 3 provides Lipschitz constants/bounds for common neural activations.
"These are conditionally convergent series in general, ordering of multi-indices k. 1 in sums and vectors must be enforced consistently and must be compatible with the semi-ordering imposed by zn0
5

---

Layoro
Layer
Layer
LagerD
Node]
(w0l) gill af (i)
(win)) g gi9
Sten
(w-ll all pli))
(oul) 41
M0 me weee (es.aallloo aoll [ot Souer
Mr (9) In: Φb (xx)
a.
w.g!"
1, 2010 1.
4
b
(+D0) (0) (o1))
yydag
(e)
ding (ol
(Vi (0))
Wiii
JEAM V (1)
w 15 Bar w
8l1l
7 1- (0)
(61 (ar)
x
201
(vRT) (ze) onn
w(Rd]
(1)
WjeZe (a)
JEA
wi 15k
(5)
+ 1 musi (#
(13
[lok-1
15k
g312
2012
L (0002
MeaM
BEAM
w (0) = w (0). = لع
(2).8-= g -1 61
diag
ir =
Where:
if ir =Σ
O -M=
if O
(+.E) H <
and 6
Σ
if ir ( Σ
ir X
II
X 1
OO (-))
Figure 4: Recursive definition of the bilinear representation f(x; ( ( Φ(x)) The upper figure schematic representation of the formal definition (5). where the bilinear representation of the output of each node is obtained, using (5)), from the bilinear representations of the inputs E All to that node. Subsequently the bilinear representation of the network is defined recursively in terms of the (trivial) bilinear representation of æ (I, 1/ R2, is (arbitrary) constant that will be helpful in our Rademacher complexity analysis. With regard notation, we recall that node j is characterized by its operation (اu E (Φ), Σ 8, (.))). and subsequently the form of the feature-map recursion (5)) depends on this operation as specified by the operators Db] (weight map operator), أ (data map/metric operator) and ااار (norm bound operator) defined. For non-Lipschitz neural activations we set [iul Blial /g0l in the bounded case and [7:) 1 if assumption is not satisfied.

---

3 Neural Networks in Reproducing Kernel Banach Space
As noted in introduction, recurring theme in the machine learning (most famously kernel methods) is the use of bilinear (dual) representations to cleanly separate data and model parameters, ie:
f (a:; Q) = ( (+). (a:)
Here the set of network parameters + and the data æ, are mapped entirely independently into distinct feature spaces by. respectively, Lp W + W (weights and biases) and Φ X - X' (data).
The bilinear product (---] W x > R generalizes the inner product of eg SVMs (Cortes & Vapnik 1995 Burges 1998: Cristianini & Shawe-Taylon 2005, Steinwart & Christman (2088) without losing the very useful property of bilimearity that makes this formalism so convenient to work with. Apart from the potential for constructing representor theory (kernelization), if the bilinear product is continuous (ie. if 3 C' E R so that (V, Φ] S C or (V, Φ) S | (VV then the existence of such model significantly simplifies the development of Rademacher complexity bounds. A model of this type was developed in (Shilton et al. 2023) using a recursive Taylor series expansion of the neural activations- in brief, noting that (a. bj (a (aSn, bb
Ig@., "I" if the input to neuron can be represented bilinearly then so too could the output, which recursion defines the model. Unfortunately this approach only works for continuous neural activations, and even then only within the RoC of the Taylor expansion, rendering it inapplicable for common activations such as ReLU. Alternatively, in this paper we propose using a Hermite polynomial expansion, which has two benefits, precisely (1) the Hermite polynomial expansion exist for all finite-energy activations and is convergent everywhere (applicability), and (2) as the Hermite polynomials are constructed from monomials can also use (a. bl (a &n 8an g to construct our model (practicality).
We begin by constructing our dual representation:
Theorem 1. Let f: K W I.m be a neural network (7) satisfying assumptions 7
Assume
nominal bounds || |WD:3
|l2 < wGii < oo and [bblll2 S gDl < oo Vjj ΣE, J AD, Let n E Rt. 1 (data)
Defining feature maps W W R=xx (weights and biases) and & : X'
and metric g E R as per 55) (Figure 4). the network may be written in bilinear form::
f (x: = ( (9) Φ (x))]
(6)
where [[)(E S Sn < 00 AO E W, [[ S on < 00 Va E X. (the constants Von On are provided in Appendix C. where lim 4,, 1b and lim On oū and we note that lim, (0000l1@(=1]))))))))))>))))))( = o Vxz E dX (ie. i||||| = 1), and lim,- [1 ll > 0 Va + O.
A full inductive proof can be found in Appendix C.I To summarize, picking layer j E ED. as- sume all nodes J E [|] in the preceding layer may be written x = y (+), ΦLū (z)] g which
trivial for the base case j = O. Then, using b) 3D (A @ P SP) in combination with the Hermite (number) expansion of the neural activation function, we write the incoming edge activa-
tions [aa as bilinear products (Pss = ( y Gul (0), ΦlاVi (æ)] glas] (see Appendix for full definitions).
This, combined with the observation that JEAGI W I (0W)
[i]
JEADI WBblyT [i] x
suffices to show that lb1 (O). db gial as given, and the result follows by induction.
As alluded to in section 2 we can readily incorporate non-trivial nodes into this framework. In the recursive construction of the feature maps, (5)) is effectively a recipe for converting the bilincar expansion of the inputs to that node to bilinear expansion of the node's output. As stated, (5)) is for a trivial node of the type shown in Figure [ but alternatively we could wrap an entire sub-network or block inside this node (eg. attention block- Figure 2b) and replace (5)) with the overall recipe for converting bilinear expansions of its input to a bilinear expansion of its output. Thus we may reasonably speak of "attention node" in Transformer network without needless clutter. For example Figure 2 includes a table detailing calculations for é for attention, residual and LayerNorm blocks (nodes) (derivations for these can be found in Appendix D.I D.2 D.3
and D.4p
Unfortunately the dual representation (6) insufficient for Rademacher complexity analysis without assumption 4 which requires that the neural activations be Lipschitz bounded (and in the latter case that |00|| = 1). This assumption is central to casting the dual model (6) into RKBS, precisely: Definition 1 (Reproducing kernel Banach space (RKBS)). A RKBS on X is a Banach space B of functions f= X > Y, where Y is normed, for which the point evaluation functionals (,) = f(x on B are continuous (i.c. Vz E X 3C2 E R_ such that | (f) < C. flls Vf B).
7

---

This is somewhat generic, so following (Lin et al. 2022) we focus on the special case:
B = {f (:: y (@) Φ Olwxxl @ E W]
(7)
where Φ X + A' is a data feature map, L W + W is weight feature map, N' and W are Banach spaces, and ('s 'lwxx W X + Rn is continuous bilinear form. Given this prequel we have: Corollary 2. The set F of networks (2) satisfying assumptions f with Lipschitz neural ac- livations and weights and biases bounded as per Theorem | is an RKBS with [[f(:; [()]))] & lim (O)]lr S 1 < oo and (f(a;)))l: S C=Ilf(:; (0)l: Il where C. Væ E X.
Corollary 3. The set F of networks 2 satisfying assumptions 4 with Lipschitz bounded neural / is RKBS with [I; >ll>- - lim,--- (x)) I á < co and [<:; 0) S Ce Cal (Ilas,)) where Ce AA E W.
activations and with weights and biases bounded as per Theorem
See Appendix C.3 for proofs (the structure of which minics that of the proof of Theorem T follows from this that the model presented in Theorem D suffices to achieve our primary goal. Note that this result applies to a very wide range of networks, including feedforward ReLU networks, convolutional networks, residual networks (ResNet), and Transformer networks (see later discussion). We observe that the conditions for F to be an RKBS are stricter than the conditions for F= to be an RKBS, as non- non-hipschitz neural activations appears incompatible with F being an RKBS. However as we will see that we only require F be an RKBS to proceed with our Rademacher complexity analysis.
4 Rademacher Complexity Bounds
We now address our secondary goal, namely using our dual model to bound the Rademacher complexity of neural networks. For h I + R, the Rademacher complexity is defined as:
RN (h o F) = E,E,
sup N E esh (f (ass)
fET
for Rademacher random variables G E {=1). where x ~ v. We have:
Theorem 4. Let F be the set of networks
2 satisfying assumptions
4 with weights and biases
bounded as per Theorem [ and let h : R.
be T.-Lipschitz. Then:
RN (h o F W[ [7 l|2 S will [|bbl||2 S (bll) <
Hnd vN
(8)
where H1 = 11 id, Hm = /2mL. otherwise, and Φ is defined in Figure
The proof follows the usual template for RKHS models (see eg. (Bartlett & Mendelson, 2002)
using our feature map; replacing the Cauchy-Schwarz inequality with [<;; O) Cel 2;
taking the limit 77 - 0+: and recalling that Ce = and lim, (()) S Φ. so [[[(;; θ) ll2 S
Cell (ell)(())]l S Φ. See Appendix F for full details.
Considering this Rademacher complexity bound, we recall that typically neural network weights and biases are initialized with magnitude proportional to 1
/ (LeCun initialization) VHGST (He
initialization). and stay close to their initial values in the wide limit, assuming a convex objective. Thus we would expect that || [Ps [ ||a (and hence its upper bound w,(Fil) should be independent of network width, rendering the complexity bound in [eforett]]fffecttiiee that the complexity bound does not contain any explicitly depth-dependent terms (nuisance terms that are often present in such bounds as discussed in (Golowich et al. 2018)); however the bound will in general grow exponentially with depth due to the multiplicative build-up of terms in ó from input to output, which is typical of such results (Neyshabur et al. 2015 Golowich et al. 2018 Truong 2022). For scalar-valued, unbiased, Lipschitz network with 1 node j per layer, becomes
iedtthinddepedeet. We also observe
I wol)- 11 Lb 10 10
R (F::
VN
While this bound is depth-exponeeee exponential in general, we can use to to derive conditions (on the weights) under which this exponentiality can be (in effect) neutralised. Motivated by this, the following result gives general, non-tri conttrivial threshold conditions for ippph-indeeendentt Rademacher complexity:
Converselyy we know that Rn
S w/bl 1:s1) 2 A IP alt (--1))) Golowich et al.
n. [ w
2018 Theorem 7), and hence Rx (F=: Wbb11:]
S 1 x
vN
8

---

Nodo or Block Type
Depul--ndrpenleeee Condition
Notes
Trivial
[bbl]] @l" 1.5 [|Wii 51 Tee,
Figure
equation
Residual
[ S
Figure
this haund we denote weight matris for (intemal) layer paw.
Wirsh, Scc AppenS D.I for the complete derivation.
Engle-Query Attention
2|Wrla [Will 1
Pigure
bound
heat parameter for sottmax. Appendix
cmmplee derivation.
Single and Mulii Head Attention
Av Wolll/
See Figure this bound A the hest parameter for the sofiman. ler dugad the pooduct di the namber of queries and the mamber of heads See Appendix D for complett dericstion.
Figure 5: Conditions for Depth Independent Rademacher Complexity Bounds for Typical Nodes.
2 satisfying our assumptions with weights and biases bounded as per Theorem | and let h m 7 R be L-Lipschitz. If:
Corollary 5. Let JF be the set of networks
(( ll2 S كاه = 16 E ALl = (1)ا S x0هح= =1
(10)
for all nodes j E Zg, then R (h o F) - /N'
Hm, independent of both width and depth.
This follows from the recursive definition of Φ in ( (Figure 4 as a sufficient condition to ensure that =1 xD0=1
given اهxه 1 for all nodes j E Z.... E Abl, and subsequently (recursively) =3 1. In practice the interpretation of this result is node specific. Conditions for various nodes (in the Lipschitz case) can be found in Table 5 where derivations may be found in the appendices noted. The general, non-Lipschitz (bounded) case is somewhat more complicated. Recall that if there are non-Lipschitz neural activations in the network we assume that x E 0% or, equivalently, || ||2 =
and for non-Lipschitz, bounded neural activations T [aal,, we set L such non-Lipschitz neural activation - |iッ1,, in the recursive definition of the norm-bound á in 5 the corresponding term in the sum becomes T. e55l BJ-- so, for example, for LayerNorm block (Figure 2 j E Zg we see that (ناه = / [a] (for full derivation see Appendix D.2), and moreover if this is the only node in its layer then the Rademacher complexity bound will be independent of all layers preceeding it. However we would advise caution here; the assumption x E 0% is quite strong and may not be realistic in general. We will discuss how this assumption may be relaxed, along with what impact this relaxation has on our Rademacher complexity bound, in section
B / / Considering one
4.1 Generalizations and Standard Toplogies
In this section, we consider two more realistic relaxions assumption T- firstly expanding the bounds on ||ا|||, and secondly considering x X drawn from an unbounded distribution X' such that it lies in the bounded of case I with high probability (whp). Using these, we conclude the paper by analysing range of standard network topologies. Formally, we consider two generalization of assumption [
Strictly Bounded: æ E Xp.r (ar E IR" S ||0|||2 S r), where USPS S E IR, and >
the network contains non-Lipschitz neural activations.
Distributional: æ X' for a distribution X' for which there exists 0 S S R4 (0 0 if the network contains non-Lipschitz neural activations) such that x E Xpr with high probability 2 1 c.
In both cases we consider a mild modification of our feature map (5) precisely V [0] (0) rIn, Φ [0]
(x:)
g0
_ 11
(0
r, 00 p. f0) =
(n)
[2)
[b/]2 = 3b12 + O JEADY Gall
T. T 52
if i is Lipschitz otherwise
(11)
Vj ZE
and moreover for non-Lipschitz, bounded neural activations Iiii), we set L [ Blisl /0 Fora
full discussion of this generalization see Appendix
C Observe that, in the limit 17 + 0+:
L Gi ebi 6D7
if -Ddl is Lipschitz otherwise
øb12 =اbار +
Gi]
c
B 6
Vj EF
(12)
0|61 < lom
الاوا (z))112 S (نا
Va E XXprr
'In both the cases 0. = 1 (the fully Lipschitz variant of assumption 1 and = (the non- Lipschitz variant of assumption 1 this reduces the standard feature map 5

---

The Rademacher complexity bound (Theorem 8 takes the same form as usual. The exact impact of letting * 1 is dependent on the network topology. For simple, layerwise. fully Lipschitz neural network with 1 trivial node j = å per layer, as demonstrated in Appendix R.1
R2 (h || 1 S wwسs 1:3)) S
Hm 11. L
1:a1
VN
This bound is exponential in depth, as discussed previously. As a mild generalization of this scenario, if we allow non-Lipschitz neural activations (for example LayerNorm blocks) in this simple network, with the last such at layer j = D4. then, using 12) and noting that (هاا) / L E &n U {0):
Hl. -1 115 دلااايل
RN (h o F: | ||2 I - =
where note that this bound is exponential in the depth to the non-Lipschitz node D D2 and proportional to 5- The independence from the weights of layers preceeding Dr is noteworthy, but we consider as an example a ReLU network terminated by a LayerNorm and observe that the scale of these weights is entirely arbitrary, it perhaps not surprising. The term reflects the need assume that, in the worst-case, small inputs will be "amplified" (e.g. by LayerNorm) to the largest possible output.
The transformer can be similarly analysed. multiplicative. In particular (see Appendices D.3 D.4 for details), for an attention block:
The catch in this case is that the attention block is
dont
@oat..h C2. Aoous 0n..
Contt Qu (oant,,, (1n.V
so, unlike the simpler case considered above, each attention block will cause polynomial growth in the ratio & Subsequently, as shown in Appendix E.3 the overall bound (due to the final LayerNorm) is: $1
RN (h F: [Wouulle S w) S (4)
39M-1
Hm Hm VN
where W out the weights for the linear output layer of the transformer If p (that is, æ E 0X as in assumption 1) this collapses to weights in all but the output layer of the network, this bound grows doubly- coubly--xponentially in depth, dependent on the ratio / of smallest/largest inputs.
Hm, Amgadaw but in general, despite being independent of the vN
Finally, bounds for the distributional case follow the strictly bounded case, but only whp c. For example, in Appendix C.4 we consider x: ~ X = =N I2I,),, showing that p < ||0||| < r, where:
(n)
p 0, r 2n In (2)o
(r(*+1)5)
whp 2 1- c which apply, respectively, for the purely Lipchitz and bounded cases. particular, the latter result allows one to explore Rademacher complexity bounds in the general case without giving
p or r (the bounds on ||æ|||,, where p particular may difficult to quantify intuitively) a-priori.
5 Conclusions
In this paper we have constructed a dual model of a very general set of feedforward neural networks that re-expresses them as continuous bilinear product between a weight/bias feature map and data feature map that is, a reproducing kernel Banach space (RKBS) model. This model is exact, with no approximation or assumptions beyond bounded (norm) inputs, bounded (spectral norm) weights and biases, and finite-energy neural activations, and incorporates networks ranging from simple layerwise models (ReLU ctc) to ResNet and Transformers. Subsequently, we have applied this model to the analysis of the Rademacher complexity analysis of neural networks, giving simple recursive bound for the Rademacher complexity of all models neural network topologies covered by our model. This bound is exact -symptttttooic and does not include depth- or width- dependent nuisance factors. Moreover is width aidtt-inddependet and, while exponential in depth (due to the multiplicative build-up of terms through the layers of the networks), enables to derive straightforward (spectral) threshold conditions under which depth-dependence may be removed entirely.
Thii also applies to ResNet, where for residual blocks j with d internal layers we let [:)12 + s² as also described in Appendix E. M here is the size of the encoder/decoder stacks, We use M here rather than N as used in (Vaswan et al. 2017 to avoid notational ambiguity within our paper.
(w 1: w 1-1
10

---

References
Abramowitz, M., Stegun, I. A., and McQuarrie, D. A. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, 1972.
Allen-Zhul Z., Li, Y., and Song, Z. convergence theory for deep learning via over--evaeeeeceeeee ouermparrattiiiiiationn In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Aronszajn, N. Theory of reproducing kernels. Transuctions of the American Mathematicul Sociely, 68:337-404, Jan-Jun 1950.
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and generaliza- tion for overparameterizzed two-layer neural networks. In International Conference Machine Learning, pp. 322-332. PMLR, 2019a.
Arora, S., Du, S. S., Hu, W. Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, pp. 8139- 8148, 2019b.
Ba, L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.064500 2016.
Bai, Y. and Lee, J. Beyond linearization: quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv:1910001619 2019.
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learming Research, 482, 2002.
Bartolucci, F., De Vito, E., Rosasco, L., and Vigogna, S. Understanding neural networks with reproducing kernel banach spaces. Applied and Computational Harmonic Analysis, 62:194-236, January 2023.
Boyd, P. The rate of convergence of hermite function series. Mathematics of Computation, 35 (152):1309-1316 October 1980.
Burges, C. J. C. A tutorial on support vector machines for pattern recognition. Knowledge Discovery and Data Mining, 2(2):121-167, 1998.
Cao, Y. and Gu, Q. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in neural information processing systems, volume 32, 2019.
Cho, Y. and Saul, I. K. Kernel methods for deep learning. In Y., B., D., S., D., L. J., Williams, C. K. I, and Culotta, A. (eds.), Advances in Neural Information Processing Systems 22, pp. 342-350. Curran Associates, Inc., 2009, URL httt:::/paperraapppccc//ap/eee/e wethods-for-dess learning.pdff
kernel
Cortes, C. and Vapnik, V. Support vector networks. Machine Learning, 20(3):273-297, 1995.
Courant, R. and Hilbert, D. Methods Mathematical Physics. John Wiley and sons, New York, 1937.
Cristianini, N. and Slawe-Taylos An Introduction to Support Vector Machines and other Kernel- Based Learning Methods. Cambridge University Press, Cambridge, UK, 2005.
Daniely, A. SGD learns the conjugate kernel class of the network. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Ad- vances in Neural Information Processing Systems 30, pp. 1422-24330 Curran Associates, Inc., 2017. URL http: http:tttppppppr..../t http://ppppprs.in..ccooo -lass-of-the-nnexort
6836 learns the conjugate-eeeeeeeeeeeeeeee kernel-
Daniely, A., Frostig, R., and Singer, Y. Toward deeper understanding neural networks: The power of initialization and a dual view on expressivity. In Lee, D. D., Sugiyama, M., Luxburg, U. V., Guyon, I., and Garnett, R. (eds.), Advances Neural Information Processing Systems 29, pp. 2253- 2261. Curran Associates, Inc., 2016. URL
www.wviwwwwweeeeeee diduualviee--eee on- expresssviity..pdf
11

---

Der, R. and Lee, D. Large-marge margin classification in banach spaces. In Proceedings of the JMLR Workshop and Conference AISTATS2007, pp- 91-98, 2007.
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685. PMLR, 2019; 9a.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over-parameterized neural networks. In Conference on Learning Representattions 2019b.
Gao, B. and Pavel, L. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: 00805, 2017.
Golowich, N., Rakhlin, A., and Shamir, O. Size- Size-independent sample complexity of neural networks. In COLT, 2018.
Gradshteyn, I. S. and Ryzhik, I. M. Table of Integrals, Series, and Products. Academic Press, London, 2000.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Hille, E. Contributions to the theory of Hermitian series. II. The representation problem. Trans. Amer. Math. Soc., 47:80-94 -4,, 1940.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp.
2018.
Lee, J., Xiao, L.,, Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein, J., and Pennington, J. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Lin, R., Zhang, H., and Zhang, J. On reproducing kernel banach spaces: Generic definitions and unified framework of constructions. Acta Mathematica Sinica, English Series, 2022.
Maurer, A. A vector-contraction inequality for rademacher complexities. In Ortner, R., Simon, H. U., and Zilles, S. (eds.), Algorithmic Learning Theory, pp. 3-17, Cham, 2016. Springer International Publishing. ISBN 978- 978-3-719-4637977
Morse, P. M. and Feshbach, H. Methods of Theoretical Physics. McGraw-Hill, 1953.
Neal, R. M. Priors for infinite networks, pp. 29-53. Springer, 1996.
Neyshabur, B., Tomioka, R., and Srebro. N. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6441 2014.
Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Proceedings of Conference on Learning Theory, pp. 1376-1401, 2015.
Olver, F. W., Lozier. D. W., Boisvert, R. F., and Clark, C. W. NIST Handbook of Mathematical Functions. Cambridge University Press, USA, 1st edition, 2010. ISBN 0521 140633.
Parhi, R. and Nowak, R. D. Banach space representer theorems for neural networks and ridge splines.
J. Mach. Learn. Res., 22(43):1-40, 2021.
Rahman, S. Wiener-hermite polynomial expansion for multivariate gaussian probability measures. Journal of Mathematical Analysis and Applications, 454(1):303-334, 2017.
Rasmussen, C. and Williams, C. K. I. Gaussian Processes for Machine Learning. MIT Press, 2006.
Sanders, K. Neural networks as functions parameterized by measures: Representer theorems and approximation benefits. Master's thesis, Eindhoven University of Technology. 2020.
Shilton, A., Gupta, S., Rana, S., and Venkatesh, S. Gradient descent in neural networks as sequential learning in reproducing kernel banach space. In Krause, A., Brunskill, E.,, Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 31435-31333333 -14888 PMLR, 23-29 Jul 2023.
12

---

Song. G., Zhang, H., and Hickernell, F. J. Reproducing kernel banach spaces with the norm. Applied and Computational Harmonic Analysis, 34(11)96-116, Jan 2013.
Spek, L., Heeringa, J., and Brune, C. Duality neural networks through reproducing kernel banach spaces, arXiv preprini arXiv:2211.05000, 2022.
Sriperumbudur, B. K., Fukumizu, K., and Lanckriet, G. R. Learning in hilbert banach spaces: A measure embedding viewpoint. In Advances in Neural Information Processing Systems, pp. 1773-1781, 2011.
Steinwart, I. and Christman, A. Support Vector Machines. Springer, 2008.
Truong. L. V. On rademacher complexity-basee generalization bounds for deep learning. arXiv preprint arXiv:2208. 244.044444 2022.
Unser, M. A representer theorem for deep neural networks. J. Mach. Learn. Res., 20(110):1-30. 2019.
Unser, M. A unifying representer theorem for inverse problems and machine learning. Foundations of Computational Mathematics, 21(4):941-96, 2021.
Valle-Pérez, G. and Louis, A. A. Generalization bounds for deep learning. arXiv preprint arXiv:2012.041155, 2020.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Guyon, I., Luxburg. U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.). Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL htttpps:://pocceediinie neur cc. Paper .df!
Xu, and Ye, Q. Generalized mercer kernels and reproducing kernel banach spaces. arXiv preprint arXiv:1412.8663, 2014.
Zhang, H. and Zhang, J. Regularized learning in banach spaces optimization problem: repre- senter theorems. Journal of Global Oplimization, 54(2):235-250, Oct 2012.
Zhang, H., Xu, Y., and Zhang, J. Reproducing kernel banach spaces for machine learning. Journal of Machine Learning Research, 10:2741-2775 2009.
Zou, D. and Gu, Q. An improved analysis of training over-parameterized deep neural networks. In Advances in neural information processing systems, volume 32, 2019.
Zou, D., Cao, Y., Zhou, D., and Gu, Q. Gradient descent optimizes over-parameterized deep relu networks. Machine learning, 109(3):467-492, 2020.
13

---

A Properties of Hermite polynomials
A.1
Univariate Case
The (probabilist's) Hermite polynomials are given by (Abramowitz et al. 1972 Morse & Feshbach
1953
Olver al. 2010 Courant & Hilbert 1937):
Hex (C) (-1)* 2
der
d'
vKEN
or, explicitly:
Her (5) k! Σ
2ppl(h 2p)! S
112
kk-2p
VKEN
(13)
052pCR
and form an orthogonal basis of (IR e))) For any f E L²(R,e-*) there exist Hermite coefficients ag, d1.... E R (the Hermite transform of such that:
(() E KEN
Hex (C) VE,CER
where:
S kl/2
Hee (5) dg
0k
and moreover the series representation converges everywhere the real line The Hermite numbers derive from the Hermite polynomials
( 1 if k even otherwise
Heg
Heg (0)
=
(15)
where k!!! k(k - () 4)... Feshbach 1953)):
is the Nouble-factorial It is well known that (see eg. Morse &
Hew ()+ OSTSc
Σ
Her-
and so:
He (C) E Hex
oSisk
follows that, taking care not to change or order of summation (remember this is an alternating series, convergence depends on the order of the summation):
s() (())-((0) Σ
Hes
For later reference we also note that the Hermite polynomials satisfy the well-known recursion and derivative relation for & >> 1:
CH& (5) 1 H (5) 1 (5) 3 Hx+1 (C) + kH (C)
(16)
Hille (1940] : Boyd 1980) show that this series converges
strip X =
Im(2) p) of
width p about the real axis the complex plane, where (note that Hille (190)) Boyd (1980) use the normalized physicist's Hermite polynomials. The additional scale factor here arises in the translation to the un un-normalized probabilist's Hermite polynomials used here);
p lim sup 8-
log
(14)
'Typically the Hermite numbers are defined from the physicist's Hermite polynomials, but as we use the Probabilist's ' form we find these more convenient for purposes.
14

---

A.2 Multivariate Case
The multivariate Hermite polynomials Heg R + R. E N", are the functions (Rahman 2017):
He (C) = (-1) exp () dct
exp (-) = 11: Hek, (Si)
where we use multi-indes notation |x| = Σ, kis a² = II, : k! = II. ki!, k!! = ПI kgl!, and
11: 0y: For any (2 ,e e 5) there exists coefficients 0x k Σn (the Hermite act""
transform of f), where In means k E [k E E" k) 2 i), such that:
f(C) Σ Hx (C) JA R" k=n0
where:
ak u((2)) I-x f() S/e Hox (C
kvl22 GeER & Her (C1) k2lv26 SCJE
& Heu, (G) d(2d(
and the series representation converges everywhere on R".
As in the univariate case, the multivariate Hermite numbers are defined as:
1)lk /2x 2!l
He, Hex (0) = II, Hek.
ko, ki,... are all even otherwise
where in the final step we have used (15.. Subsequently:
- -
Σ
Og
Σ
Hex-1
where k > means k E {k E N"
| > i7.
Finally, if we consider vector-valued function f R + Rm valued expansion can be extended to:
then it not hard see that scalar-
(C) f (()
Σ a Σ Er.U
Hez-
(17)
0-,, 15k
where azii are the Hermite coefficients of f.. We note that if n m and f(() elementwise (for example a neural activation that acts elementwise) then:
[o(S:)]; acts
Øx bx
(18)
where bp, by.... are the (univariate) Hermite coefficients R + R.
B ReLU Activation Function Analysis
In this section we derive the Hermite-polie polyioia expansion of the ReLU activation function:
[RRLUU] (C) = [c]+
We find it convenient work in terms of the physicists Hermite polynomials H2 suit (Gradshteyn
& Ryzhik 2000). So:
ReLU
V2nk! So Çe- Hep
(C)
k
Venkt Jo Çe- /2
H
(5)
dç
v2
V Jo v22
(+2)
(
d.
122
v2.
V2
V2'RR k! 100 -5- Hy (C)
and hence, using (6) and Gradshteyn & Ryzbik 2000
(7.373)):
6/
[eLLU]
(k+1)) S0 -5² Hesi (9) dc v
1000 -
H (5) dc
Va
v2"
(k-1))
15

---

and using (Gaddhheeyn & Ryzhik 2000 (7.373)) again:
b [eLLU]
(k + 1) (e Hx (0) - x0 H4
+ ...
v '2"
(x+1)!
v2)
1
( H (0) -
Hk-2
00
vi v²t [k-1]
v2
Ha (0) + /2" -k-
H (0)
2
v2 (k-1))
(k- 1)!
If k = 2p and p > 0 then, noting that (0) = 2²" Hcą:
22
[RoLU]]
(2p + 22 (0) -2 (2p- 13!
Hzp 2 (0)
v2x
(2p
11!
(2p H2p (0) /2"
H2p-2 2 (0)
22
22th (2p+1)
3
(2p- 1)!
1)p-1
1)) (2p 1)p! H2p (0)
1) 2p!
H 2p 2 (0)
V2
1)2pp!
[2
(2 1j1l
(-1)*+)
1)0+(((2 (2p 13p 2D (- (2p)
(-1) 2p!
2n 1 1)0 (3p-2)1 (2(p-1)) 1)}!
(2p 1)2mp!
(2p)
2ppl
(p- 1)12"
(-1)
V2 (2p- 1)2pp!
If k = 2p + and > 0 then:
by 1
1
V2 22 (2p+2) (2p + (2p+2) H2p+1 (0) +
(2p)) H 2p (0)
2m
(z
(2p + 2) H 22 (0) -z (2p))
(2p)) H2
(0)
(2p+2)
22
H 22 (0) 2-(2p)] H
./2
2p (0)
72m
(2p+T]
0
For the cases k- = 0, 1 we use the result:
fh m 52 dc = 1 (m mm+1 , n²) r (m=t] b2)
and so:
Sa c ds + الس a²))
In the case k- = 0:
b ReLU]] = V f0000
10550 ce
VpT (1,
and in the case ks === 1:
8 Rel.U]
2 So c2- dc
Vir r (3.0) 0)
2
Subsequently, for the elementwise ReLU neural activaiton, using (8)
ag Mx dRs 1
(19)
Next we derive the magnitude functions for the ReLU. Using integration by parts, see that: /2n fc Ex (e2t* - 1) de
1) d
/2
22
v/2
1
1
1
(e8² 1)
dg
V2H V2
(e35² -1
eete² -
e dg
+
+ vক
(e2s² - 1
11 (e2c0=
-
+ 2 マス
2
s 3 el² de
v2n
vs
(ete'= - 1)
errl
($
erri
2 (ete" (e)
16

---

So:
b/
[RLLU
5* =
p)
7 + V2n
2p-
(2p
1)2rp!
+
1 CJe
2pp
3p
22
2
11-11ppp!
1 515 3.
80
df
2dpl
2 + 2 S/e
dc
1 + /2 S Se マ
#/
()))))
p
dg
/ + 1 Se
1
-t 1 de
J erfi
+ 1
erfi (2)
+
2 (ete
(1 (1- e+(*)
v2
V2 8
Select e so that the first derivative c:::
-erfi
+
e -1) = 0 c=
V2
V2
Hence:
81
[ReLU] (5) A
Σ
|eLUU
(1 +))*
Σ
|
|ReLU
= 71))
erfi
1+nc
+ 1
1
et (((((()))) - erfi
+
1
v2
2
v2
(20)
- e
22
= 1in (rri
1+t V2
+
+
e e (((t)))))))) +
erfi
L+te v2
erfi
22
v2
C Bilinear Representation Proofs, Bounds and Generalizations
In this section we present proof of theorems, bounds and generalizations related to the bilinear representation. To avoid repeating work we consider mild generalization of the map presented in the body of the paper, as shown in Figure The key generalizations here over the main body of the paper are:
1. We let x E X = fx E R |00|2 < r for some 0 < S r R., In the main body of the paper we let p = r 1 for simplicity when all neural activations are Lipschitz, and p r = otherwise. In general we require >> 0 when considering a network containing non-Lipschitz neural activations.
2. We use base-case (T(0( = rI, gl. [o)
! 1, here (recall in the main body).
3. We use L [7.]]
to scale the feature map here rather than L [io] #1 a
[
b and L [irl 213)
Note, however,
that (as we demonstrate) lim,- woli = أاا and lim of Φbب so the definitions coincide in the limit 7) 0+, which is the we are primarily concerned with (as it is used in our Rademacher complexity bound).
4. For non-Lipschitz, bounded neural activations (edges), we let L
Bu ..
where @ is
lower bound on |ل (x:) [|2 (recall that p = in the main body of the paper, and note that we will prove that Φ [3 = d in this case). More generally for neural activations that are neither bounded or Lipschitz we let T. = 1. Note, however, that we cannot prove continuity of our bilinear product in this case, the relevant parts of the proof do not apply for this.
17

---

Lagen
Nodej
Go0 bolow
(000 ghi
(wtl) """""" pin)
(0) -I,i (3n) an. m.
$1.0
ydligg (0/188))))))
(0)
ding 24
cot
(VTRr (et)
(00)
aliol
(m))
((E)
M (ar1)
(odges)
(1)
Iynoul
Hea-1 (H0
10
1. 1520
Z
Vij e (block)
Layers & (scqumtiall)
(21)
661 (9))
(iH (e) wiFl
5l01 (xz)
(R
Jm jol
(node)
@ go
glll
+ by gli
Wlot Bap
@
JBP Bon
2012
@ Lol
W (9)
(9)
(ae)
Gf (ae) m
6,
Where 7
①
if IOM
Ol
Σ
E
IF e e
it IF
O
#O (
t e OWWW
11
Figure 6: Complete version of Figure (recursive definition of bilinear representation) splitting edge/node maps, showing limits and including correct weights (the main body uses simplified weights that are correct in the limit and sets 1, 0 (or = if non-Lipschitz neurons present). For non-Lipsehitz, bounded neural activations [ we set r. [-j BDaa / / and for non-Lipschitz
and unbounded neural activations we set [_[
18

---

Note that for each j E Zg the feature map construction is split into two steps construction 21 for the incoming edges [ : j], which we refer to as the edge case; and construction (2Ip) for the (core of the) node itself, which we refer to as the node case. This split will simplify our proofs and improve clarity by separating the key steps therein. representation is:
the main body of the paper the overall
f ((;; θ)
T (+) Φ (2))
(22)
We will also show that:
x Gij 535 (9) انتا (x) (D))
V LF,J E Abl Vj Eg U {0}
x bi 1 (+) أbاه (x) gl))
(23)
where the following bounds hold:
V bーン (0) F S F
Vj ME. Abl e Vj NR. x
( (a))l2 <9 nt
[i5)] [ial
(24)
1 (0) S 4h
VjE e
| (x) E m th
(
Vj U(0)
noting that [ [i]
> 0 if p > 0 and:
m
(a)]lb 1
Vj Zg.Je Abl, 2 W | P
| (a) 122 // F
Vj Zg.Je = W: | =
(25)
| (a) 2 o
Vj (0), X: | p
| (z)]l of
Vj Σg U (0}, e X |
C.1 Proof of Theorem Bilinear Representation
Recalling that the network is arranged in layers j 1, ... ... D, and given that we know the feature map representation for the input layer j = 0 is, tivially:
00
(I
[0] (+) Φ [0] (z) gl
where (0) = rl, 10 (a) x and g [0] 1, it suffices to show that if all outputs of all nodes Je - (L {0}) in layer j - 1 can be expressed in terms of bilinear products:
x v ())
57 (x)) gl
(26)
then all nodes j E I_L using the definitions given, can be written:
2biil ( (0) Φ D:5l
(a:) gi-l
Vy A
(27)
and:
ااب (bb (0) 55 (æ)] gidl
(28)
We call (7 the edge case and (88 the node case, and will treat them separately.
Edge case: We are given that 26 is correct. Substituting (2la) into the bilinear product and using 26).. and (17), we find that:
T DMl (O), 3i (m)) (M (0).
Iill (2))gon
-B
(0)
Σ
a
Gul
Σ
Hor-
x
L by (e) oy
,000 (x)
FES will
-
(0) + Σ
BJ
Σ
Hov- (wDl (9), s (a=) A
0 1sk
= (0) + Σ
Bul
Σ
Hox-
Dv]
which is the desired result 27
19

---

Node case: We have shown that (27 is correct. Substituting
(T into the bilinear product and using
27 we find that, for columnar concatenation nodes O | (so
[
diag,
[i] θ)
(906) (8) dil (or) = -11bb1 +
7M beaw
1i5 (e) wool
t in Big (ar)
Wit olsl (ar) Ges gi (m)
Beol (a) wilzo
(glle)) (e) wike,, oi (a)) ahia Buul wisee,, dloo (xr) att
=yb0bbb +
-701b0
+1bbb0 +
+
will =x
For additive nodes O0: E (so
[i]
+):
(w/l (0), الوه (a)) = -6bbb +
Goll (e)
Wirl
6l Doll (o (xr)
FEADl
FEAM
JEAli
W
G & (w) Well B Bi (x)
=>b1bb] +
Basi
Wibs))
80 0a 8 17
--(0bbb + Σ (pii (9) W cbl (a>) gmn
FEAM
Σ W ab
Je361
For Kronecker-produet nodes O01
x (so
[i] )
(1/3) (0), و65 (x) g3i = =11ibb bbil
(0)
Wivl,
o
G1 Gill ( (m)
FEAM
JeADl
TeA Jig gool
-11/bbil +
Fill
(e)
Will
( (w)
FEAM
JEAM
X Jeali w
=bl +
Db
(e) wisl
Dul (x)
gB
win
JeAl
JeAu
Jeata
--1/bbi
(e) wiRd
(GoTal (ax) @ Fbl)
JeAut
=>libbi
WoJT (plo
(0) أناا (m)) gool
-blibbll
W I. [r
JePul
20

---

For Hadamard product nodes Ou] (so
[+]
(Q))
(x)] g3:
=blibbl
whx
Gisl
(e)
wirl
G
L Pa (x)
FEAB
JEADI
-yl/bbl +
(θ)
W
G p (x)
FeAld
JEAUI
--libbi blll +
p (+) Widl
p (x)
g
winl
Jealn
JEAlS
JEAUT
-ylibb bbl
Ge (ar)
g
FeAld
TEAM
-1.bbbl biil
II
w
( (a)) o g
JeASi
7 bb +
II
T
ا (az) 3 g551)
JEAM
7 blll
[MM (9) G (=))
JEA
=-ll ->1/bi bbl +
II
WIRT Pu
JEAM
=-bibli
W
JeBul
For multi-inner-produce nodes O ((-)) (so |i
1. D
b1
(wbl (O), الو (x)) g01 = =blibb +
Uil JeAU
whi
اiااا (e) wisl
Gl Lil @Bib) (x)
JEADI
Deal
=ybbbbl +
8 JeAl:
viاا (e)
wisl
Gi Goll (ar)
whoo
JEAM
Feall
= =bbbbll +
x
vD (9)
Wisl
plui (x)
x g g( Geal
JeADi
jeAll
-bbbbb IT
X JeADi
о g glidl)
JEAD
-66 IT
II
g Fdl)
JEAM
bbbil T
11
J-l
(x) g Bdl
JEAM
-Uib + 1
II
WITT (po (9) أ
(x)) 21
JEAMI
=b01bl 1TT
II
JEAMI
= 1
W
=bbbbbl
x
je
where on the final line we use (()) an operator (see notation section). So, in all cases:
V 1l (0) ا (m) gln
bbl
WDJT [
jeFul
which is the desired result 28 for the node case.
21

---

C.2 Proof of Theorem 1 Norm-Bounds
Recalling that the network is arranged in layers j 20.,,,..... ... D, and noting that for the input layer
j = 0 is, tivially from our assumptions:
0 (+)
121
F
00
[0]
4n
Q7
where w/4 010 and o it suffices to show that ifl outputs of all nodes j E T_ in
layer - satisfy:
ا (+) o - ألاهه (z:)
(29)
then all nodes j (5), using the definitions given, satisfy:
وا (+)lI
1/
VE Abl
(30)
2 [ Uy
(x)
and:
-151 (bاه (x: Fr =016 (
811 < in
(31)
We call (30p the edge case and 33 the node case, and will treat them separately. correct. By direct calculation, for incoming edges 21 1), using
Edge case: We are given that the multinomial theorem at step
Ruta
(0))12
diag
(0M(44)
at
(t)
(ViNO)) (B)) 1917
(D)
NeNwill
200
v |
10
+
Σ
a
[alll
iT (0)) OF
min
FEN W/N
Σ
B
(VA9))
7
(1))
10
(1)
Tikk
Σ
Σ
2 (e)
15k
mm
IR [o:
|
Σ
144-111
2 (0011)) -1))
(1
03
REN
|
(0)
Σ
|,.0011
(1+
1 (3)
-1)
-10
Σ
||ل
(1)))))
(1
22

---

and:
|
10 (1)
- 35l [0)
xx
(1) $ (voel) (a:)
ask
T 32 (0)112 + Σ
1 11,
(t)
(Vircbi) (xz) 01l
(
k> 0
of 1 (0)1 + Σ
Σ
(1) (VTTb (3z) 1
()
x> ml
Dx nis 15k
1 [0)1
Σ
Σ
(v 2 (<z) 1nl
())
x> HIs
D 1<555755
1p
139 (0))
Σ
|1. (1+ (11 (mm)1t) 14 -1) )
(mm))))
2 (1)
L 12
Jull
(1 (+)))
(1)
which we may bound as (using that Sny
is increasing on IR:
L Ju Bul (1)()))))
(0)
va
2 (1)
Dull
(0)))
[
I, 1.
which is the desired result (30
Node case: We have shown that 330 is correct. For columnar concatenation nodes O = -+ (so
diag,
D): ):
(1 (10)
T b (0) | = ||bb
Σ JEALi
|
bلا (m) = -B01 +
2012
(1)) (1)
JEAl:
For additive nodes Ol1 Σ (so
[i]
T bl (0) | = ||bb]]
|
+
Σ
Doje
Boll
2 (
(
JEADI
الاها [2 = 3ااا + Σ
Du
of (1
(
(1)
SEAD
For Kronecker- product nodes O
X
(so
51
L bl (+)
||bbi|
+
L
Di
(
JEAD)
|لااا (z)]
3اuا +
II
L
Dij
[Pol
0
JEAM
For Hadamard product nodes O01 O
(so
( 1-:)
T il (0) | < ||bi]] 1 +
Gigle
(
JEAD)
(1)()))))))
ألا (z) = ماحا
+
II
(1)
JEAM
23

---

For nodes Ou) ((-)) (so
1, -
x
y b1 (+) | - |bb 2
L
D7
(1)
JEAD]
(1
|لاها (z)] 3
07122
(1)
JeAM
Thus in general, for all nodes considered here:
Fd
1 51 (+) F - [|b ? + II
|
JEAL
Fal
(1
| (x))11
3 + II
L
2012
D
(1)
JEAl
which we may bound as:
| [0)l - جززر
ألطه (z) (z) E in [
which is the desired result 31 for the node case.
We observe that the data-feature- mapp bound is tight:
| (a:) of if || = P, and 2l if
| (x))]12 o if || =
In the limit 17 0, identifying اووع vith اfو11
oot 1) v/- Φ1 Ø
é = Φo+: v/- = 251 Φ사 = 11 Φ و| where, recursively Vj E ZØ:
L Lajl 2012 &bil
if - Lipschitz otherwise
أ/ا & bb12 + c G) WDi1
B D. yoi Li Sta df
JEAM
will
r Daj
if D Lipschitz otherwise if -f Lipschitz otherwise
0/12
(32)
B Doi2
JEAD]
L [ajj2
al d
3b12
D
Do glte dime
JEAL!
[)))())
(here we have used that lim,
z by observation of the definition), which justifies our
25 (1)
simplification in the main body of the paper.
C.3 Proof of Corollaries and Continuity Bounds
Our approach here mimics the previous proofs. For the input node j 0, for given + E W:
sup mex
1 (e))
(x))
10
sup mEX
100 00
[0]2 e.n
1
for given θ W
6 (2))
( (e).
sup mex
d (m)
10
sup
|
W
A
1
VO E
w
xex
( (e).
sup 6EW
|
C 2.1)
[0]2
for given a E
(x/00 (
sup 6eW
10
|m
C
[0
Vr E X
[))
24

---

As in the previous section consider a single node j E [ in layer j. Assume that, for all nodes in the previous layer J E 1
2 (0)
sup
mEX
(w))
201
C
O,,
for given θ E W
1712 G, S
( (0).6))
C D12 W.
sup mex
4O E w
(
( (e)
sup oew
D 20.1
for given E
17 C.2
2. I Ix,
(v)
sup 9eW
D X.n
Vx E X
v (0)
Edge case: for a Lipschitz neural activation T0:1, for incoming edges 21 for fixed θ E W:
(e) [a [c=) ( 2
sup
sup sex
( (2)) 1|
( (2)
sup
=eX
Lay 0
L 1
0 2
< sup
(c)
#EX
(1)
|
{ (w (0) [z)) 11 11=
sup
sup xex
| ||
#EX
1 [au]
M
M (o) 01
sup =EX
| (20)
1
and similarly for fixed x E X:
())
sup ecw
sup
[0)
ecw
Boll
sup
DI
wee
L
sup BEW
Bula
cl
1 3 ( 11 10
( (0).
(c=)
2
sup
3
sup
[e)
(B),
<
sup
[
BeW
25

---

Alternatiely,. for bounded (non-Lipschitz) neural activations:
10 (9)
(m)) (x)))
7 (n (x.)))
shs #EX
sup
wex
alyye
18
B00Ta
sup
(1000000
(
(1)
sup
(1
(>))
mex
1012
which is finite; and:
(
(x) Gul
Gul
sup OEW
sup
New
1/2
4q
(x
sup
eew
sup
[
l1:)
OcW
which is unbounded in general. It follows that:
i is Lipschitz
(e)
sup
B.
for given è W
otherwise
(
G & C
401 2 Wi9
of is Lipschitz.
(0)
sup xex
[
C.8.
otherwise
3ite 1 (P
Ziopp c 7lo322 +QQ
T2 if Gul is Lipschitz
sup
[
cli
for given X
otherwise
C. < C
Cg. Gl X,9
- Zuri +
Dol Lipschitz
Va X
6ew
otherwise
26

---

Edge case: using 21 for columnar concatenation nodes O + (so
[1]
diag, diag. [ + ):
(o) (2))
m
sup eck
sup xxx
[0 1
acc
sup
sup
ac
M
sni 3
1a3 aa
pollenn Ceriin 3 + Soie
Misss 2
/
ma Ail
max
diver 2e
man mm 199 xax -max
and:
(1)) obl
Σ
(m)
sup OEW
1 (
sup
Dete
[b
1 Marrril (l)) (
|bb 12++
||
| 11
W
max
m
me m
Ca. m
Ful2
JEAHH
max
max TEAD]
a.11
For additive nodes O0) Σ (so
[5]
Gl )
Σ b114
Aarere Win
2
1nl
sup 3
(x))
sup
(1
sup
3 4 111
sup
3
M
2ovit 3
Mossoee 5 + Papee
3 + (Aw
dup
2 + 1
-o Wiii 3 1
S
1 ( ccriy
< sup -u1z
aed
Σ.
max 1
(,01
,
max (
Cen
|
27

---

and:
1 11 Σ
|/
(w)
[x]]
2
JEAbi
sup 9EW
4
(0)
sup NeW
[b
+
Σ
|
W
|
F
TEa
|
||
60
(m)
JCAU1
|bb
+
W
|1:1
max
max jEAbl
JEali
bb,
[
max
max
JEAD
For Cronecker-produce nodes O
x (so
biil
(0)
| [[)))())
(
sup mex
sup =ex
sup sex
Sealn
1
w
JealD
S sup
xCX
gb.2+
Jeaur
||b0]] 112 Ll
W Alea
(e) (
+ Panlg
anse Meeee (
|
11
1I
max bl,, Jeaui
II
II
seali
max
761,
II
G3l2 Ca.
and:
|bb
||:]| 1
(wl)) (1)
x51
3E40l
sup eew
1
sup oEW
|
SeA
w
(=))
JE4lal
Tb1 II
Gol2 Ca.
bb
W
1
max
JEAM
Jealst
max
II
JEAM
For Hadamard product nodes
O
(so
using that the norm of the
28

---

Hadamard product of unit vectors is S 1:
(wl)) (9).0 26
(x)
sup mEx
sup xex
[
2es sus
O + 1i:
unies
a au
+
11
11
1 dne
II 4 Panc
11 11111 (ingg
Toleere Heese Il
1 S0le
max mas
11, II seal
sea a
2215
11
Anw ar
C clee
1 max
Cen
and:
1 (e)
(b)1))))
11
(m)
DEW an
Mae A
(=)
Dul2
1 max
II
Cam
bb
+
W
JEAM
seali
D7
max
II
2,17
Jealn
For multi-inner- product nodes O = ((-)) (so inner-product of (2-norm) unit vectors most 1:
(-) 1,
J
using that the multi-
(O)
(0).6" (z) 44
|b 1001+(( (Wllss
sup mCK
(x)
1
[x)
=
sup =C
( (m)) 11:
(ww Wi of
mup
II
11
3
wex mm
(e) (o
Live 2
11 Pand mn deaee
11 1111 1
II
Rul2 Cen
<
sex sus
II sEAu!
II
max اil
II TEAD
03:12 Can
29

---

and:
|
|
||]||
(vbl
SCAU1
sup Gew
[
sup GE
+
||
JEA
||b0]]
||
Seald
max
ااب1
II JEAM
scall
max
T601
II JEAM
Thus in general, for all nodes considered here:
sup =cx
[
<
(,,9
c/112
max
bا4 Obi
Dii2 G..
for given θ W
JEASI
c S c
(1)))))
cbil W.99
max
y|11
CDul2 W.9
AA E W
=ex
JEAM
(e))
sup ecw
clil2
max
7
for given a E
JEADI
clil cki
(0)
sup 0ew
CH12 X,M
max
73)
7712 X,n
Væ E X
JEAL
where we have defined:
if OF E (EDE Σ}
max II
if if E 1 (())
Consequently, defining Ce.- Co.m
[1]
Own
W. Cz. Cl..) and Ox.n C%,y"
[E].
sup =ex
C2 0,
for given θ E W
Ce.n S Cwn
sup weX
< in
AA W
[(
sup
|
for given æ eX
eew
Can S Ox.
(()0))
sup
||
CZ,,
Vo e
eew
where Ow.,, is finite in general and Cx is finite if all neural activations are Lipschitz.
The limit case y - 0+ is of particular interest here. Defining Ce = lim Co cli
-o- Co,mp Cw lim Ow,, cl -im Clil we observe that, using the form of the base case and recursion:
Ce clil Cw =chl
clul =1
if all neural activations are Lipschitz or bounded if all neural activations are Lipschitz
Vj E Z
C. = C Cx =1
This result, combined with Theorem suffices to prove Corollaries 2 and
C.4 Bounds for Data Drawn from a Distribution
common variation of our assumption terms of its 2-norm is that æ ~ X' is drawn from some data distribution X. With regard to our analysis, for arbitrary data distributions is possible extend our analysis; however if it can be 2 - for suitable r then our results will follow whp c. To take simple example, suppose we draw data from an n--imennional normal distribution:
Xp.r that is, the assumption that æ is hard-limited in
proven that æ E Xp.r
X = N (On, IIIn)
30

---

id
ld
w/hn1)
ReLU
id
42
RoLU
Id
05
42
ReLU
1d
W/6- hdd]
ReLU
4ou
Figure 7: Calculation of Øout in a residual network block.
Trivially, for x X:
Pr [||2]||2 S SP S 2n/2aT 2 p²
2
Pr |||| 2 r] $ 2e
Thus we have x E X with high probability 2 1 where:
2mln In [1-Uje]
= 22 (T' ( 1) uE)
for [0, 1), In the purely Lipschitz case we can simplify this by setting (so p 0):
2n 2n In (2)
(33)
and more generally, if we allow non-Lipschitz neural activations, whp 2 E:
Valu( (ーー (
(34)
(r(*+1)oe)
D Non-Trivial Blocks
In this section we consider norm- and continuity- bounds for particular common neural network archictectural blocks. Note that in all cases the continuity bounds Co. Ow, Ca. Cx are well-behaved, so task is to analyse the norm-bound In this regard we refer the reader to 21 in Figure 6
31

---

4m
11
H
Qmid
Norm
VHI
Pout
Figure 8: Calculation of Pout in residual network block.
D.1
Residual Block Bounds
In this section we consider the calculation of & for residual block. Figure 7 shows the notation we use here. All neural activations this block are 1-Lipschitz so trivially, using our bounds:
R R.
d-1 dd
4/ d- = 1/ w
Vin
21 1, Qd-21 24 d1-31 =
R
It
21
R = R
Øinl
d-
R
=
Qd-2 =od3
R
Od-3
R
2 = Φp = Φin
and:
d wil (dd-2:d-1 pb
d-2
wll wld-2:d-11 w
wld-2:d-11 ld-3:--2 ... ...w! 11
wld-2:d 3:d w 1:1: p/m
14 Ll
wid-2:d-1l
0
wld-2:d-11
d-
wid-2:d
11 Id-3:d 3:d 21
... 1:21 +
w
ld-3:-d 2|
: (0:1] ppnn
L
widd-2d-111
0
wild widd-:d- 2:d w
3:d 2) 2
ج =
w 1:12
wild 1idd2:d-110 (d 3:d 2
w الجج u:1] din
and subsequently:
2/2
out
1/
(1 x² v
(w
id=1222 w
1:222
0:12
52) wht
d2
out
Pd-14 + (1 22) 04
12
(35)
1:d2-1:d12 wl (1:21 10:12
52) Pim
22
p
o
(1 52) a
(wlt wldd1:dd2 1:d/2 w 10:0 10112 - 52) Hin
where we note that, for p >>>00 0:
Doat Qio
Pouts Pint
D.2 LayerNorm Block Bounds
As shown in Figure & the LayerNorm block is distinct insofar as it is non-Lipschitz. First we note that
that [|VH1||2 2 H. |I
||2 1, so may set a (lnmidd] 1, a [mid:out]
/ H.. Noting
32

---

coftmaa
Figure 9: Single-query attention block.
that the Norm activation is non-Lipschitz and bounded by B[Norm] see that:
Vout [midiout] Umid
VH
s/mid
Pimid
Pmid.
Øout = w /id:oout]
HH
Pout w juidoout]
drnid
Oani
@lmidd
Pmidd
and trivially v/mid = wiimmidd vinn Wins Dmidy
w Jinauid Oin = cinn and emid w wiummid din
din. Hence, overall:
Mout
H
tin
Gmli
Dont
H
(36)
Øout
H
dim.
dini
where we note that, for p > 0:
Donr Oin. Pini
(37)
Pouts
D.3 Single-query Attention Block Bounds
The standard bounds presented in 21 needlessly pessimistic for softmax nodes in attention blocks (Figure 2 as they are derived without taking into account the operation of the softmax in layer 3, which is full softmax that has been split into components here while we can bound the set of all QK outputs, the standard bounds only bound the individual components without taking into account the interaction between then. The following more nuanced analysis gives tighter bound.
In the following analysis we make the simplifying assumption ,,,,,,V vn, Pn = 6, 6 vv V.,,K Ky 0g Ky Dn..K Kg Given this:
Layer 1: following the standard approach:
2.V Vn.VV
F V1 =
DJV An.
33

---

11
mIQK
Vn.QWn,
Qn
QK4
M2QK
Layer 2: following the standard approach:
[2
2/ 11
V.V
ni.V Vn
Φ NI = 19,44
Φ n.VV
& N = Dnv
1/22/2 = 1 Σx 11ll1
v22
DKK
dx
11/2 12
nn nKK
22/2
`k Σ, 1 QK
QK
BOK dR Σx 112
22
= 2 n
Layer 3: we need to take some care with this layer. In particular, noting that the output of the layer is effectively the softmax split componentwise, we can constrain the sum of d R,..QK as:
E.V v/
[3]
V.,.V
2
Φ
2IVI = 19.44
NEVV
&
V.V = DT.V
182
2:3 wll
X2
12:8)
nTQKKK
23
7
(1)
[2:8]
22
x²
9.0XL
x²
MIQKI
12:9 (1)
[3
2 X2
[2:9]
x22
2::3
1,.KKK
(1)
for some C1, C2.... 0: E, c (in the standard analysis we would let e = C2 ....= 1).
Layer 4: following the standard approach:
142
n. vi n V...V. n.Q. = =2,,2
2b [aj2
2.25
V.V
142
[31 [8]2
x22002
q...V. qiiQK
4/2
13/2
13/2
222002
n. n
D
Layer 5: recalling that cı, . 2 0 satisfy Σx 0g =
w = Σx 1b 1//422
|5|2
dx 22
13
o.
V.V.
23
0
[6]2
Σ,
[4]2
X²
12:0
n.
Σ, [4/2
@n
Taking the limit + 0+ we summarise the overall operation of this block as:
Voot / dubi, v Vin. Qin, dout = Xdm, Viin, Pm. dout Adin. iin. 2in.K
where note that, for p 0:
BuaL. D.n.V Rin Q Rin. K.
Pouts Iu.. Oun.Qu D..
34

---

X1y
X2,V
X1,0
X20
X1,8
X2,K
id
id
id
id
Wr
W
W Q
WO
Single-Query Attention Block
Single-Query Attention Block
Figure 10: Single-Head attention block.
D.4 Single-Head and Multi-Head Attention Block Bounds
The standard single-head attention block is constructed from from single-query attention blocks as shown in figure TO Multi-head attention is similar, with an additional h concatenations. Making the additional assumption, over section D.3 that Vn3.v Vn, Pnā,v = V,, G,,āv Qy,V. not difficult to see that:
Vout v hd hd A Vin.. Vin
Pout v hdq Xomn V 1 Qt K4
Dout v /hdq Adin, Wwn.
where do is the number of queries and h is the number of heads. We note that, for p > 0:
dont
Gii V.
Pin Q Gin. K.
(38)
Poats
Ou. ou..q4 Pi.
E Bounds for Standard Network Toplogies
In this section we apply our results, and in particular our norm-bound [| I $ Va E Xp, which is central in our Rademacher complexity bound, to standard network topologies.
E.1 Simple Unbiased Lipschitz Layerwise Network and ResNet
Consider simple network with unbiased node with L-Lipschitz activations per layer, so D = E,
j = j E En, and A = { - 1}. In this case, using 21 Vj E En:
Φهاا Layld- 11511
and hence, using that g
= rrrL iie فاي wنز--1:ي 1:j1
and we find that the norm-bound ø (and hence our Rademacher complexity bound) proportional to the product of the weight-matrix norms, the maximum input norm r, and the exponentiated Lipschitz constant. In the distributional case, assuming æ ~ Ao I²I,) and using (33) whp 2 - e:
Φ = D / 2n In (2) II Se w 1gj
We can also bound the residual network (ResNet) norm with this by including residual blocks as
35

---

nodes in the network. For example, if node j is a residual block then the effective weight-norn bound wiت-1:3l becomes, for that non-trivial block, using 35
wنر-1: ( (w)l--1:8k2 w
+ )2)
where wis - 1:3]a the norm-boum for the h weight matrix W W:jll in the residual block j.
E.2 Simple Unbiased non-Lipschitz Layerwise Network and LayerNorm
In this section we consider the same network as in the previous section E.
excepting that we assume
at least 1 non-Lipschitz, bounded neural activation. In this case, using 21
V E 2p:
L 1 - of
[|5-1]
if 1 1gj is Lipschitz
w 1:jl
Bla-1:a)
otherwise
(39)
if - is Lipschitz
i]
الااه = w 1:61
B
1:31 dix-1)
otherwise
where [0] p and 0:
We immediately observe that:
10-11
=
Vj ED
and hence
39 simplifies to:
L 1 6( 1]
if ( 1:j is Lipschitz otherwise if 1:: is Lipschitz otherwise
of1 = wi 1.1-1:31 1:3)
Bli-1:j) 1:3]
(40)
(لل1) wib 1:50
B
1:jl
If we further assume that node D2 is the non-Lipschitz node closest to the output node, bounded by B(D,-1:P1), the norm bound becomes:
= -BB..--..11.--- IP wلز-1:اس
The first thing to note with this bound is that is no longer depth exponential, but rather depth-to- non-Lipschitz (D DD) exponential. This may appear surprising at first, but it is perhaps not so surprising when we note that the Lipschitz norm-bound scales with the max weight- bound, while bounded neural-activation displays attributes that, in crude sense, flatten out the magnitude of their input from previous layers. The obvious extreme case network combining ReL.U and LayerNorm nodes, in which case we can scale weight matrices preceeding the LayerNorm arbitrarily without affecting the operation of the network in any way. This is directly reflected the above expression, where the norm-bound is independent of the magnitude (matrix norm) of the before the LayerNorm.
norm-
weight-matrices in layers 1,2,..., Dj
The ratio I in the bound is perhaps less intuitive. In particular, while we would expect that the norm bound of [[)())] should scale (increase) ||æ|| S increases (which the norm-bound does), it is less obvious that the bound should increase as the lower bound | 2 p decreases. To understand this behaviour, recall that we only characterise neural activation - [ by its upper bound -1:DD1 (1 for simplicity), so we must make a worst-case assumption that |P = 1 for all X If || = p then, in our worst-case analysis, the node must, in effect, amplify the input so that [2
the smaller p. the larger the amplification required This is why take care not to over-claim in the case =
in the main body of the paper.
Another apparent difficulty with this norm-bound is that one may argue that the lower bound || 2 artificial, and that real data may not satisfy this bound. To cover this, we may use the distributional
In the limit p - 0+ the amplication must approach oo, which is why insist p > 0 in this case.
36

---

case. For example, if node D2 is LayerNorm node and assuming æ ~ (N I then, using (36 and with high probability 2 1
(nH D-D I11 n2 W l:
(T(4+1)5)*
We observe that this bound is scale-independent, both in terms of the "size" a of the data distribution and weight-norm bounds for layers prior to the final non-Lipschitz node DJ. The proportionality to arises from the choice of LayerNorm, and the exact form of the new scaling arises from our choice of distribution 10
E.3
Transformers
Finally we may consider the Transformer. For concreteness we will assume the structure described in (Vaswan et al. 2017] Figure 1); and for tractability we will ignore the input/output embedding and positional encoding, and instead assume inputs and outputs eeasseeeddddi///noiinggg æ zo E Xp.r = fx Rx p S || r).
Encoder:
The first layer in the encoder stack consists of multi-head attention block inside a residual block, followed by LayerNorm block. Using 388 the output norm-bound of the multihead attention block will satisfy:
(4)
Omnha
Subsequently, the output norm norm-bound of the residual block will satisfy:
Oren
din +0mba.
denhan
Pmahn
+1
(e)
Orenn
Onnn + Pmhaa
Pindd
Pmbhal
and we from 37 that the output of the LayerNorm will satisfy:
@m
= (?))
This is followed by feed-forward network inside residual block, again followed by LayerNorm block. The analysis of this similar to the above, excepting that, because the block inside the residual block is additive, there is need to cube the ratio. The output of the LayerNorm in this layer will therefore satisfy:
(4)
At total of M = these layers occur sequentially, where for each the ratio is cubed due to the presence of the multi-head attention block. Subsequently, for the output of the encoder, find:
(e) 3M
denn
Ponci
Decoder: The decoder similar, with some important caveats. Perhaps most importantly, in the first layer the output of the second attention block (and therefore the output of the first layer in the decoder) will satisfy:
dMHA = -(5 3+2.3 (5) gM
AMBAL
This is followed by (M 5 additional layers, and so it may be seen that the output of the decoder, prior to the final linear and softmax, will satisfy:
(2) 3MM+1
3JM-1
Osscc ddecs
and, using 36):
Ødec I (2) 3
33M-1
dmodde
Subsequently, assuming the weights the linear output layer of the Transformer satisfy || S w and assuming À= in the final softmax we find that the overall norm-bound for the Transformer is:
33M-1
Φ < / /modelw (g)
1t may be informative to investigate the impact the distribution a ~ X' this bound future work. We use M here rather than N due the notational clash between Vaswani 2017 and use of N.
37

---

Proof of Theorem 4 Rademacher Complexity
We are concerned with calculating the Rademacher complexity of:
RN (F) E,
sup Leww
1 Ei, exh (f (2xx)
where h is L-Lipschitz. We have from MMurer 2016) that:
RN (F) E:
22L,,
sup + Ex en (xx)
Leew
Thus reduce the dimensionality of the problem to 1-dimension. Proceeding with the standard argument:
E,
sup LeEw
N
>x cafi (xxx = E.
sup [V
(Ex cafe (Ix)) New
Jeusen's sani'ss-iiin -inequality
Be sup New
(Ex Eu (xx)))
N Ev
E. sup BEW
Ene kil eneisi (xxa Si (221)
B E.
Σx k sup f (xx))
New
1F N 4p
Σ k sup (v (0) Φ (2x)
BeW
( (O) 31
2
En
Ee sup NEW
11 (xxx))
N
[0(xx)122
and So:
RN (F) <
V2L N
E:
Σx sup NeW
(i.x()) [ 1
2 1|ob (ota) 112
(1) (0) )²
1 norm -2 norm-onm--nn inequlilyy
2m En
E, New
sup
[0
1| (amx))12
v/2mL E,
(0)
||Φ (2=))12
k sup OEW
[< 111
bilinear-
y 22m Ey
Ex k sup C² 1lbb (xx)) OEW
nort moorm-boman bounding
22mL E,
Σn
W.y 02
cleanup
22mL Cw VN
N
and the final result follows in the limit 7
0+, recalling lim, o Cw,n lim, 01 = 6:
RN (F)
V22L
VN
NB: in the special case 1, h id, can skip the first step which contributed the factor V2L
and the 1-norm-2-none 2--orm--nequuuiliy.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: the abstract/introduction written after the key contributions were pleted specifically to reflect them.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: the limitations of the work are clearly outlined in the Setting and Assumptions section of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (eg.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, eg., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: All assumptions are clearly stated in the body of the paper. Most (non-trivial) proof's are summarised in the body, with reference relevant appendices for details.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is purely theoretical work. Results will apply any network satisfying our assumption, which are analytic in nature: network topology. bounds on weights/biases that are translated the final result, and requirements on neural network activation functions.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (eg.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (eg., large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: This is purely theoretical work. As noted previously, results will apply to any network satisfying our assumption, which are analytic in nature: network topology, bounds weights/biases that are translated to the final result, and requirements neural network activation functions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niipscc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 hnips.cc/public/gutt http://uudde//oeSSuubbee ssi assionolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: See previous justification re results, data and code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
See previous justification re results, data and code.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: See previous justification re results, data and code.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttlp::///neuiiie
Answer: [Yes]
Justification:
The research conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is purely theory, so cannot foresee specific societal impacts beyond improved performance in neural networks.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
42

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: see previous responses.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: this is theory paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
43

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwprssstspsssssccdeeee.. wwt.coo///aaat datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: this is theory paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
44

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are core this method, though the complexity bounds derived herein may apply to them.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy hatp:p///boaaiiprccoooootrrreeee for what should or should not be described.
45


Reviews:
[{"review_id": "zwIT1WVYAt", "reviewer": "Reviewer_oQnH", "summary": "For the problem that the theoretical results of Rademacher complexity in capacity-based generalization analysis may be vacuous, \na novel theoretical framework is proposed, which uses the reproducing kernel Banach space (RKBS) based on the Hermite transform to accurately model feedforward neural networks, including complex structures such as ResNet and Transformer. This model does not require approximate assumptions, as long as the weights are bounded and the activation functions are finite energy. Based on this model, the authors derive two novel upper bounds on Rademacher complexity: one is an upper bound that is independent of width but exponential in depth, and the other is an upper bound that is independent of width and depth when the weights are constrained below a certain threshold. These novel theory bounds bring new insights into understanding the generalization of deep learning.", "questions": "Please refer to the Weaknesses for details.", "limitations": "This work does not seem to have any potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper extends the RKBS framework to neural networks of arbitrary topology (including Transformer) without the need for \"wide network\" or \"lazy training\" assumptions.\n\n2. The derived upper bound of Rademacher complexity has no nuisance factors, which avoids the $2^D$ term induced by the traditional \"peeling\" argument. This is the most important theoretical contribution of this paper.\n\n3. The proposed model is compatible with complex structures such as residual connections and attention mechanisms, and provides a modular recursive definition of the corresponding bilinear representation.\n\nWeaknesses:\n\n1. In my opinion, the greatest contribution of this paper is that the upper bound of Rademacher complexity can be analyzed under the RHBS framework to avoid nuisance factors. However, the readability of this paper is relatively poor. From the perspective of theoretical techniques, where does this improvement essentially come from? The authors need to add relevant clarifications and explanations to improve readability.\n\n2. In addition to avoiding nuisance factors, what special advantages do the theoretical results obtained in this paper under the RHBS framework have? Compared with the NTK model, in addition to not requiring assumptions about network width and being an accurate model without approximation, what other essential advantages does the RKBS model have? In order to enhance the readability of the paper, some relevant discussions and comparative analyses are necessary.\n\n3. In order to obtain a complexity bound that is independent of depth, the weights and biases need to be constrained below certain thresholds. Do these threshold constraints affect the actual generalization performance? What do they correspond to in practice? Due to the lack of experimental verification, it is somewhat difficult to understand, although this is a theoretical work. Some explanation and discussion of these threshold constraints is necessary.\n\n4. Failure to summarize and present the key steps of the theoretical proof in the main paper will undermine the theoretical contribution of this paper. It is recommended to add key proof ideas and steps in the main paper to increase readability and theoretical novelty.", "was_revised": true, "final_justification": "The authors' response partially addressed my concerns. I recommend acceptance on the condition that the authors include a summary of the key points of their theoretical proof and an explanation of the essence of the theoretical improvements in the final version to improve readability.", "rebuttal": "**Response to reviewer oQnH:**\n\n**Q1:** In my opinion, the greatest contribution of this paper is that the upper bound of Rademacher complexity can be analyzed under the RHBS framework to avoid nuisance factors... where does this improvement essentially come from?\n\n**A:** Roughly, the nuisance factors seem to come from the fact that Golowich et al (and other peeling-based bounds) work directly with the Rademacher complexity when recursing through the network. To take a simple example, starting from the output layer (or any intermediate latyer), the Rademacher complexity of the neural network terminated at that layer can be re-written in terms of the Rademacher complexity of the neural network terminated at the previous layer using the Rademacher contraction principle, which states that, for an L-Lipschitz neural activation $\\tau$:\n\n$\\mathcal{R}_N (\\tau(\\mathbb{A})) = 2L \\mathcal{R}_N (\\mathbb{A})$\n\n(weights are also factored in, but this does not introduce additional nuisance factors in general). Applying this recursively for a $D$-layer network gives a multiplicatively built-up nuisance factor $2^D$. The important point to note here is that *the nuisance factor is a side-effect of the Rademacher contraction principle* - if we can avoid using this principle, we may avoid the introduction of the nuisance factors.\n\nThe key difference in our approach is that, rather than diving directly into the question of Rademacher complexity, we first re-write the network as a bilinear product. This allows us to bound the Rademacher complexity in terms of the continuity constant $C_{\\mathbb{W}}$ (which is a property of the bilinear form) and the norm of the data feature map $\\phi$ as our first step, using an approach analogous to that used in the analysis of e.g. SVM Rademacher complexity. Only after this do we bound $C_{\\mathbb{W}}$ and $\\phi$ using a procedure analogous to peeling using the method sketched in the body of the paper and detailed in appendix D. The key observation is that, because we are no longer dealing directly with the Rademacher complexity but rather matrix/vector norms, we can use inequality bounds that do not have nuisance factors (in contrast to the Rademacher contraction principle). *Hence our peeling procedure does not introduce nuisance factors into the bound*.\n\nWe have expanded our discussion in the paper to make this point more clearly (unfortunately we cannot upload the new version as yet due to the pdf restrictions in the review process).\n\n\n**Q2:** In addition to avoiding nuisance factors, what special advantages do the theoretical results obtained in this paper under the RHBS framework have? Compared with the NTK model, in addition to not requiring assumptions about network width and being an accurate model without approximation, what other essential advantages does the RKBS model have?\n\n**A:** There are two immediate benefits to our RKBS framework:\n\n- it enables us to analyse e.g. the Rademacher complexity of neural networks in the abstract, rather than directly, allowing us to remove nuisance factors from the bound.\n\n- it opens up the possibility of an exact analogue of the NTK to better understand the evolution of the NN during training. In this paper we have formulated our theory using the origin (zero weights and biases) as our \"zero point\", which rules out a straight-forward NTK-type (ie gradient flow) analysis that takes the current weights (at some point during training) as the \"zero point\" and formulates the change in the network relative to this. However it is possible to rewrite much of the analysis using an arbitrary \"zero point\", enabling an analysis more analogous to (corrected) gradient flow than the simpler version presented in the paper. However the resulting formulation is significantly more complicated and very notation-heavy, so we thought it best to publish this simpler precursor (and the insights that arise from it) first before proceeding to the more difficult case.\n\nMore generally, history shows that re-casting complex models into a simpler (equivalent) dual forms that cleanly disentangle the role of the factors involved - in this case network structure, network parameters (weight/biases), and input data - can lead, directly or indirectly, to better understanding and practical (algorithmic) advances.\n\n\n**Q3:** Do the [norm-bounds on the weights and biases] affect the actual generalization performance? What do they correspond to in practice?\n\n**A:** The effect of these thresholds is directly observable in the Rademacher complexity bounds. It is difficult to say too much about these in practice without extensive experimental work that is beyond our means at present, but in the unbiased, wide network or lazy training case we may make \"first-order\" assumptions - LeCun or He initialization, weights close to their initialization - and then, as discussed in section 4 of the paper, we would expect that any increase over $\\phi = 1$ would cause a depth-exponential increase in the Rademacher complexity.\n\n\n**Q4:** ...present the key steps of the theoretical proof in the main paper...\n\n**A:** We have endeavoured to do this (see lines 160-167 and 206-209), but on reflection in our efforts to reduce to mathematical load we may have made these summaries too brief, so we will expand them somewhat (particularly in line with our response to Q1) to improve readability and better highlight the key points of difference in our method."}, {"review_id": "z2lvgR24my", "reviewer": "Reviewer_szLf", "summary": "The authors apply RKBS to represent neural network architectures, including ResNet and Transformers networks. They use Hermite polynomials to expand activation functions and construct feature maps. They show that the neural networks are representaed using dual representation that separates the parameter feature and the input feature. Using this representation, they derive a generalization bound whose dependency on the network width is milder than existing typical bounds.", "questions": "Are there any ideas of deriving a generalization bound whose dependency on the depth of the network is milder than the exponential dependency?", "limitations": "In assumption 1, they assume the data is normalized to a unit ball. However, this assumption may not true for test data. Is it difficult to generalize the results to unbounded data space?\n\nMinor comment:\nThe notations in Corollary 5 are confusing. Could you check it and clarify the statement?", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The application of RKBS to derive generalization bounds of deep neural networks is very interesting topic. They construct a feature maps for representing wide range of neural network architectures, and use the reproducing property to derive the generalization bound. The bound depends on the operator norm of weights, whose dependency on the width is milder than typical bounds with the Frobenius norm.\n\nAlthough this paper provides a promissing direction of theoretical analysis of deep neural networks, understanding the overview of this work may be difficult for readers from various backgrounds. Providing a figure that shows the workflow of deriving the results could be helpful for readers (e.g. visualize the connection among expanding activation function, constructing feature maps, and deriving a generalization bound).", "was_revised": true, "final_justification": "I think this paper provides an important theoretical contribution.", "rebuttal": "**Response to reviewer szLf:**\n\n**Q1:** Are there any ideas of deriving a generalization bound whose dependency on the depth of the network is milder than the exponential dependency?\n\n**A:** Unfortunately no. Moreover as we discuss in section 4 (in particular lines 220-221), this may not be possible in many cases using Rademacher complexity, as (Golowich et al, 2018, Theorem 7) gives an effective lower bound on Rademacher complexity that is depth-exponential. However as we note in the paper this is only problematic if the base exceeds 1 - otherwise the result is (in effect) depth-independent.  Nor does it mean that such a result is ruled out for particular cases, only that it may not be possible for simple feed-forward networks with norm-bounded weights and inputs in the unit ball. Indeed, as a counter-example we give a depth-independent bound for the transformer network on lines 252-258; however to do so we are forced to restrict ourselves to the case where data lies *on the boundary of the unit ball* ${\\bf x} \\in \\partial \\mathbb{X} = $ { ${\\bf x} : || {\\bf x} ||_2 = 1$ }, which is a strong assumption (stronger than made for all other results in our paper) that may not be met in practical scenarios.\n\n\n**Q2:** In assumption 1, they assume the data is normalized to a unit ball. However, this assumption may not true for test data. Is it difficult to generalize the results to unbounded data space?\n\n**A:** The assumption that data lies in a unit ball is fairly standard in the literature. It's not difficult to extend this to the case $|| {\\bf x} ||_2 \\leq r$. If we consider the derivation of the norm-bound $\\phi$ in appendix D, the only change is on line 492, specifically: in the base case $j=0$, we have (note that we have now fixed the minor typo here in the paper):\n\n$|| {\\bf \\phi}^{[0]} ({\\bf x}) ||_2^2 \\leq \\phi^{[0]2} = r^2$\n\nrather than $\\phi^{[0]2} = 1$. The net result of this is that $\\phi \\to r \\phi$ in (5), figure 4 (that is, a linear rescaling of the norm-bound, and subsequently a linear rescaling of the Rademacher complexity bound).\n\nTo treat the unbounded case would require additional assumptions on the data distribution. If you could assert (or demonstrate/prove) that $|| {\\bf x} ||_2 \\leq r$ with high probability then we may reframe our results as high-probability results. For example if we assume a Gaussian (or sub-Gaussian) distribution on ${\\bf x}$ then standard concentration inequalities (eg the Chernoff bound) tell us that there exists $r \\sim \\mathcal{O} (1 / \\log \\epsilon)$ such that $|| {\\bf x} || \\leq r$ with probability $\\geq \\epsilon$, and our result follow with probability $\\geq \\epsilon$. Once again we note that the only impact on the Rademacher complexity bound is a linear rescaling and an additional (with-high-probability) caveat in the theorem.\n\nWe will add a formalised version of this answer to the supplementary material.\n\n\n**Q3:** The notations in Corollary 5 are confusing. Could you check it and clarify the statement?\n\n**A:** Sorry about that - we have now removed the confusing second $\\forall \\tilde{j} \\in \\mathbb{A}^{[j]}$ condition which we had mistakenly included in the original."}, {"review_id": "N8Zkkg6QZv", "reviewer": "Reviewer_t2Jm", "summary": "This paper formulates extensive classes of neural networks as elements of a Reproducing Kernel Banach Space (RKBS), using Hermite transforms. The main result is that neural networks can be written in the corresponding bilinear form, and coefficients are provided explicitly (coefficients can be computed by induction on nodes of the network).\nThis formulation is then used to bound the Rademacher complexity of neural network function classes, in particular, the authors provide conditions under which this Rademacher complexity does not grow exponentially with depth.", "questions": "Main questions above. Minor questions/comments below.\n\np1 l26-27. There seem to be missing words.\n\np1 l29. What do you mean by \"spectral-norm bound weight matrices\"? Do you mean \"spectral-norm bounded weight matrices\"?\n\np2 l63. At this point, neither $C_\\Theta$ nor $C_W$ have been defined, so perhaps deleting $C_W$ at this point of the presentation would be clearer.\n\np2 Add definition of $\\oplus$ in this context.\n\np6 caption of Fig 4. \"neither Lipschitz or bounded\" -> \"neither Lipschitz nor bounded\"\n\np7 The statement of Theorem 1 is quite obscure with respect to the parameter $\\eta$. This parameter has not been appropriately discussed at this point. At this point in the paper, it is impossible for the reader to appreciate what the limit statements as $\\eta\\to 0^+$ mean/refer to. Some of the quantities inside these statements do not have explicit dependency in $\\eta$ either (e.g. $\\|\\phi^{[j]}(x)\\|_2$ and $\\|\\phi(x)\\|_2$).\n\np7 l165 \"quarantined\" do you mean \"guaranteed\"?\n\np8 Eq(8). Where is $\\phi$ defined in Figure 4? Is it supposed to be $\\phi^{[E]}$?\n\n\np8 l223. \"exponentially\" do you mean \"exponential\"?\n\np8 l220-222. From what I understand, writing these requires that the functions are 1-Lipschitz. If so, this should be explcitly stated before writing the equation. Otherwise, where did the factors $L^{[j-1:j]}$ go? Also, what are the assumptions required for Golowich\n221 et al., 2018, Theorem 7? In your result, if the Lipschitz constants become small, these would contradict that result.\n\np8 Eq (10). Should the second quantifier $\\forall \\tilde j\\in A^{[j]}$ be deleted?\n\n\np9 l257-258 some grammatical issues.\n\np17 l447 \"tivially\" -> \"trivially\"", "limitations": "Limitations could be discussed in more depth -- see comments above. N/A for societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe proposed RKBS representation is extremely general and covers most (basically all) neural networks architectures of interest. The representation is also exact (so long as the coefficients in the Hermite decomposition can be nicely computed). \n\nThis representation also naturally leads to bounds on the Rademacher complexity of the considered function classes---given by the neural network architecture, and appropriate coefficient/spectral bounds. In some sense, these are cleaner than previous works as in they do not explicitly contain exponential factors.\n\nWeaknesses:\n\nThe paper would gain by giving more details on the motivation for the current approach. Viewing neural networks (NNs) through the lens of RKBS (or RKHS) is quite standard in the literature, but I am less familiar with analyzing the Rademacher complexity of neural networks for understanding their performance in practice. I think the paper would gain by giving more details as to why using a uniform convergence approach is useful/reasonable for NNs (especially for non-experts), since this is currently the main motivation given in the introduction. Usually, training is performed in the over-parametrized regime and achieves 0 training error -- so in practice I imagine that we never have uniform convergence, since we do not even have convergence for the trained model.\n\n\n\nUsing the language from the paper, why should one expect the bounds to be non-vacuous ($\\phi<<\\sqrt N$) in standard regimes of training? Along the same lines, the paper provides some conditions under which dependency of the Rademacher in depth is not exponential, but these are very technical and hard to interpret. As a non-expert these seem quite restrictive---are these actually realistic? Further, the paper claims to remove explicit exponential in depth bounds from previous papers (Golowich et al. 2018), but the main term $\\phi$ grows exponentially with depth in an implicit manner and is not related in an obvious way (at least to me) with the terms from their bound (the $w$'s) whenever the neural network has width>1. Is there any way to compare the bounds formally? \n\n\n\nLast, the presentation is very heavy in notations and technicalities, which makes it quite hard to read. Most of these technicalities, however, seem necessary to properly define the RKBS representation and other results. Still, there seems to be a few imprecisions/typos within the text, I listed those that I saw below but surely missed others.\nA careful pass to fix these minor issues is necessary.", "was_revised": true, "final_justification": "I maintain my score. The paper provides some good contributions to Rademacher analysis for neural networks, but the presentation makes it hard to digest", "rebuttal": "**Response to reviewer t2Jm:**\n\n**Q1:** The paper would gain by giving more details on the motivation for the current approach. Viewing neural networks (NNs) through the lens of RKBS (or RKHS) is quite standard in the literature, but I am less familiar with analyzing the Rademacher complexity of neural networks for understanding their performance in practice. I think the paper would gain by giving more details as to why using a uniform convergence approach is useful/reasonable for NNs (especially for non-experts), since this is currently the main motivation given in the introduction. Usually, training is performed in the over-parametrized regime and achieves 0 training error -- so in practice I imagine that we never have uniform convergence, since we do not even have convergence for the trained model.\n\n**A:** The gap between training error and testing (actual) error remains is an area of active research. The classical result states that, without taking the training algorithm into account and only considering the set $\\mathcal{F}$ of possible neural networks under certain constraints (in our case the assumption of norm-bounded weights and biases), the gap between training error and (expected) testing error is bounded, roughly speaking and with-high-probability $\\geq 1-\\delta$, as:\n\n$\\sup_{f \\in \\mathcal{F}} | \\frac{1}{N} \\sum_i l ( f(x_i), y_i ) - \\mathbb{E}_{x,y \\sim \\mathcal{D}} [ l ( f(x), y ) ] | \\sim \\mathcal{O} ( \\sqrt{\\frac{{\\rm complexity} + \\log (\\frac{1}{\\delta})}{N}} )$\n\nwhere many different measures of complexity have been studied (out of which we would argue that Rademacher complexity $\\mathcal{R}_N (\\mathcal{F})$ is one of the more rigorous and well-motivated). This is the *architectural bias* (note also that the term uniform convergence indicates that the gap converges with increasing training set size $N$ (assuming the complexity is well-behaved), which is distinct from convergence in the sense of training). In addition to this, more recent work has studied the effect of the training algorithm on this gap, which is known *training bias* - for example benign-overfitting can be studied by considering the gradient-flow model of training, in particular by analysing the spectral structure of the corresponding NTK.\n\nConsidering your example where training terminates prematurely with 0 error, we would expect this to have a strong effect on the training bias, as any eg. benign overfitting effects will be halted before they can have a significant impact on the result. By contrast, the architectural bias is *independent* of the training algorithm (unless training results in a significant increase in weights, which is unlikely if a training error of 0 is achieved quickly), and so should not be affected. Hence in your example the bound becomes (ie. for 0 training loss, $\\frac{1}{N} \\sum_i l ( f(x_i), y_i ) = 0$):\n\n$\\sup_{f \\in \\mathcal{F}} | \\mathbb{E}_{x,y \\sim \\mathcal{D}} [ l ( f(x), y ) ] | \\sim \\mathcal{O} ( \\sqrt{\\frac{\\mathcal{R}_N (\\mathcal{F}) + \\log (\\frac{1}{\\delta})}{N}} )$\n\nwith high probability. Thus while the *training bias* would be adversally effected in your (early terminated) example, the *architectural bias* bound from Rademacher complexity will remain unchanged.\n\nI hope this helps to answers your question, but I would be happy to discuss this further if desired.\n\n\n**Q2:** Using the language from the paper, why should one expect the bounds to be non-vacuous ($\\phi \\ll \\sqrt{N}$) in standard regimes of training? Along the same lines, the paper provides some conditions under which dependency of the Rademacher in depth is not exponential, but these are very technical and hard to interpret. As a non-expert these seem quite restrictive---are these actually realistic? Further, the paper claims to remove explicit exponential in depth bounds from previous papers (Golowich et al. 2018), but the main term grows exponentially with depth in an implicit manner and is not related in an obvious way (at least to me) with the terms from their bound (the $\\omega$s) whenever the neural network has width>1. Is there any way to compare the bounds formally?\n\n**A:** Whether the bounds are non-vacuous is a difficult question in the most general case, as this requires $\\phi \\sim \\mathcal{O} (\\sqrt{N})$, noting that this same problem will be present in all weight-norm based analyses of uniform convergence (eg Golowich et al, Neyshabur et al etc). We discuss this issue in section 4, in particular lines 210-225. To summarise, if we consider the case of LeCun or He initialization and take seriously the over-parameterised limit analysis then it is reasonable to conclude that the weight matrices will remain close to their initialization, and hence that their norm-bound will remain close to $|| {\\bf W}^{[\\tilde{j}:j]} ||_2 \\leq \\omega^{[\\tilde{j}:j]} \\approx 1$. When (or if) these assumptions hold more generally remains an area of active debate.\n\nWith regard to the depth-exponentiality of our bound, as noted on lines 222-225 our bound does exhibit exponential depth dependence. The point we are making here is that this is only a problem if the norm-bounds $\\omega^{[\\tilde{j}:j]}$ are greater than 1. Put simply, if we assume for simplicity that $\\omega^{[\\tilde{j}:j]} = \\omega$ (the bound is the same for all layers) then $\\mathcal{R}_N \\sim \\mathcal{O} (\\omega^D)$, so if $\\omega = 1$ then this collapses to $\\mathcal{R}_N \\sim \\mathcal{O} (1)$ - that is, no explicit depth independence. Much of section 4 is dedicated to generalizing this intuition to a variety of common network topologies and giving conditions under which it is true.\n\nFinally, with regard to width, while we cannot entirely rule out the possibility of it playing a role in our bounds through the weight norm-bound, we would observe that LeCun and He initialization both result in weight matrices whose norms are decoupled from network width, and it is difficult to see how such a dependency could occur during usual training.\n\n\n**Q3:** [too much notation]\n\n**A:** We have spent a lot of time trying to minimize the notational load in this paper. As you note, we do need some level of notation to unambiguously present our theory. We have also done our best to choose notations we feel will help to reader to navigate the mathematics. For example the superscript $[j]$ to indicate \"relating to node $j$, or $[\\tilde{j}:j]$ indicating \"relating to the link between nodes $\\tilde{j}$ and $j$.\" And the operator notation (as described in figure 4) has been used to avoid the needless repetition that would have otherwise been needed to describe each type of node independently - see figure 4 for the \"key\". To address specific concerns:\n\n- p2 Add definition of $\\oplus$ in this context: we define this as a matrix concatenation operator on page 2, line 76.\n\n- p7, parameter $\\eta$ and associated notation: I will add a short, preemptive discussion of $\\eta$ after the theorem. Essentially this parameter is a \"free parameter\" in this theorem. It makes no difference to the theorem (the result holds true for all $\\eta > 0$), but it becomes necessary later when bounding the Rademacher complexity as the bounds take a much simpler form in the limit $\\eta \\to 0_+$ (the limits on lines 158-159 are effectively a precursor to the later usage). With regard to us writing $\\phi ({\\bf x})$ etc instead of $\\phi_\\eta ({\\bf x})$ here, we considered including the subscript but decided that the loss of readability from the additional visual clutter was too much (we can reinstate these subscripts if you feel differently).\n\n\n**Q4:** p8, lines 220-222: From what I understand, writing these requires that the functions are 1-Lipschitz. If so, this should be explcitly stated before writing the equation. Otherwise, where did the factors go? Also, what are the assumptions required for Golowich 221 et al., 2018, Theorem 7? In your result, if the Lipschitz constants become small, these would contradict that result.\n\n**A:** in this context we are discussing the $1$-Lipschitz case, with a simple layerwise network as per Golowich, so I will note this in the paper. With regard the Lipschitz constants it is worth noting that we can always absorb these constants. Precisely, consider (dropping superscripts for simplicity):\n\n${\\bf W}^T \\tau ({\\bf x})$\n\nwhere $|| {\\bf W} || \\leq \\omega$ and $\\tau$ is $L$-Lipschitz. We can always rewrite this:\n\n$\\hat{\\bf W}^T \\hat{\\tau} ({\\bf x})$\n\nwhere $\\hat{\\bf W} = L {\\bf W}$, $|| \\hat{\\bf W} || \\leq \\hat{\\omega} = L\\omega$ and $\\hat{\\tau} ({\\bf x}) = \\frac{1}{L} \\tau ({\\bf x})$ is $1$-Lipschitz. Thus the $1$-Lipschitz assumption is non-restrictive.\n\n\n**Minor points:**\n\n- p2, Line 63: we will delete $C_{W}$ as suggested.\n\n- p7, line 165: we do actually mean quarantined here. It is possible to incorporate the Hermite numbers into the feature maps and not the metric (this is largely a stylistic decision), but this complicates the analysis, so we \"quarantine\" (wall off) these in the metric to make our lives a little easier.\n\n- p8, eq (8): $\\phi$ is defined in figure 4, at the end of the last line of equation 5.\n\n- p8, eq (10): we will remove the second qualifier."}, {"review_id": "VbjAU74PoC", "reviewer": "Reviewer_c4ND", "summary": "This paper introduces a theoretical framework which characterizes general neural network architectures using a reproducing kernel Banach space (RKBS) construction. It uses this construction to find bounds for the Rademacher complexity of various architectures which are sharper for deeper networks.", "questions": "See weaknesses. I am not confident in the correctness of the arguments for bounded activation functions and would like to see some clarification on this point.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n- The techniques in the paper allow one to improve existing Rademacher complexity bounds by a constant factor at each layer, which leads to an exponential improvement as a function of the number of layers.\n- The RKBS formalism is interesting and different from existing methods used to bound the expressivity of neural networks. It seems general enough to be useful to prove other theoretical results.\n- The paper considers a family of network architectures which is quite general, including fully connected networks, resnets, transformers, etc. I appreciated that there was some discussion on the special case of fully connected networks to make the results more concrete.\n- There is some intuition behind proofs of the theorems in the main text, which makes the ideas clearer.\n\n### Weaknesses:\n- The paper has a lot of cumbersome, non-standard notation which is hard to parse. This makes it difficult to understand the details of the formulas and check that they are correct.\n- For some architectures, the constants $\\phi_{\\eta}$ and $\\psi_{\\eta}$ determining the Rademacher complexity are complicated and hard to interpret.\n- For the depth-independence of the transformer, the argument seems to be that one gets depth-independence from having layer normalization late in the network layers, and using that layer-normalization is a bounded function? Why would this argument not hold for any architecture satisfying assumptions 1-4 with any bounded function at the end? This argument seems like it is proving too much; by this reasoning, one could have an architecture with high Rademacher complexity with layer normalization in the end to reduce it to a constant.\n\nMinor points:\n- The links to sections and references are broken.\n- On line 258, $\\partial \\mathbb{X} \\in$ should be $\\partial \\mathbb{X} =$.", "was_revised": true, "final_justification": "All of my comments were addressed. The point about the transformer Rademacher complexity was my biggest concern, and the authors have resolved it providing some intuition for why it should work and what the edge cases look like. The main outstanding weakness is the readability of the paper.", "rebuttal": "**Response to reviewer c4ND:**\n\n**Q1:** The paper has a lot of cumbersome, non-standard notation which is hard to parse. This makes it difficult to understand the details of the formulas and check that they are correct.\n\n**A:** In this paper we have tried to cover the widest range of NN topologies possible to make our results as widely applicable as possible. For example:\n\n- we consider non-layerwise topologies, so a simply \"layer j\" superscript does not suffice when specifying which weight, activation etc we are refering to. This motivates the $[j]$ (with respect to node $j$) and $[\\tilde{j}:j]$ (with respect the directed edge from node $\\tilde{j}$ to node $j$) indices for clarity.\n\n- we consider multiple \"types\" of node - including attention, layernorm etc. We could consider these separately, but this would result in a lot of redundant (repetetive) results with very low informational content after the first, which we would like to avoid for readability. This motivates the operator notation described in figure 4.\n\n- the use of $H$ for width is not original here, and the superscript versions $H^{[j]}$, $H^{[\\tilde{j}:j]}$ is necessary for the general case as we are not primarily interested in the infinitely-wide case (in which case \"the width\" is typically just taken as a constant for all layers).\n\n- the Hermite-related and multi-index notations (as well as other mathematical notations) are all fairly standard, though perhaps not so widely used in the NN community.\n\nTo help the reader we have summarised relevant notations in section 1.1. Note that we did consider dropping equation (5) from the body of the paper to the appendix, but decided that on balance it was important to retain it so that the interested reader could inspect the feature map underlying the bilinear (RKBS) representation if they so desired, even though it is not strictly necessary for the following Rademacher complexity bounds. Again, this is a question of balance.\n\n\n**Q2:** For some architectures, the constants and determining the Rademacher complexity are complicated and hard to interpret.\n\n**A:** We will endeavour to improve the writing and description around these. If possible could you please elaborate on which constants you have difficulty interpretting so that we can improve these cases in particular?\n\n\n**Q3:** For the depth-independence of the transformer, the argument seems to be that one gets depth independence from having layer normalization late in the network layers, and using that layer normalization is a bounded function? Why would this argument not hold for any architecture satisfying assumptions 1-4 with any bounded function at the end? This argument seems like it is proving too much; by this reasoning, one could have an architecture with high Rademacher complexity with layer normalization in the end to reduce it to a constant.\n\n**A:** The reason we have not reached this conclusion is that, for this final result to hold, it is necessary that the training data lies *on the boundary of the unit sphere* - that is, $|| {\\bf x} ||_2 = 1$, as stated in our caveat on line 257. The reason we require this is that, in this special case we can calculate\n\n$|| {\\bf{\\phi}} ({\\bf x}) ||_2$\n\nexactly (see appendix D.3), which is subsequently required to prove the continuity bound in Appendix D.4, in particular the equation immediately after line 545, where the inequality relies on $|| {\\bf{\\phi}} ({\\bf x}) ||_2$ being strictly non-zero. While we can imagine scenarios where the data does lie on the boundary of the unit sphere, in general this seems unlikely. Thus we include this result as an interesting special case, but take care to note the special circumstances involved, and subsequently not claim too much from it.\n\nAs an aside we note that we can \"expand\" the definition here very slightly. If we require instead that $0 < \\epsilon \\leq || {\\bf x} ||_2 \\leq 1$ then we find that:\n\n$|| {\\bf{\\phi}} ({\\bf x}) ||_2 > 0$\n\nwhich is not exact, but is non-zero. Because this is non-zero we obtain an inequality on the continuity constant similar to (though not as tight as) that on line 545 in Appendix D.4. However the choice of $\\epsilon$ here is somewhat arbitrarily, and moreover the additional scaling factor on the Rademacher complexity bound grows (loosely speaking) as $1/\\epsilon^D$, which appears to counteract the apparent \"too muchness\" of the result. Thus, to reiterate what we have written above, we consider this final corollary an interesting special case with rather limited applicability that is nevertheless worth noting."}]

Author rebuttal:

Meta-review: This manuscript develops a reproducing kernel Banach space (RKBS) model for neural networks; the model is then used to produce upper bounds on Rademacher complexity of a broad class of models.

The main strength of the manuscript is its approach to the theoretical analysis and, more significantly, that the RKBS approach yields bounds free of typical "nuisance" parameters. Given the latent importance of such bounds in understanding generalization capabilities there is a clear contribution here.

The main weakness of the manuscript is its presentation: it can be challenging to read and technically dense. As such, the submitted manuscript did raise several questions that were clarified in the rebuttal. Nevertheless, further refinement of the presentation is important.
Decision: Accept (poster)