Koopman-based generalization bound: New aspect for full-rank weights
Authors: Yuka Hashimoto
Sho Sonoda
Isao Ishikawa
Atsushi Nitanda
Taiji Suzuki
Venue: ICLR 2024 poster (2024)
Keywords: generalization bound
full-rank weight matrix
Koopman operator
Primary area: learning theory
TL;DR: We propose a new bound for generalization of neural networks, which sheds light on a new perspective regarding full-rank weight matrices and provides a connection between operator-theoretic analysis and generalization of neural networks.

Abstract: We propose a new bound for generalization of neural networks using Koopman operators. Whereas most of existing works focus on low-rank weight matrices, we focus on full-rank weight matrices. Our bound is tighter than existing norm-based bounds when the condition numbers of weight matrices are small. Especially, it is completely independent of the width of the network if the weight matrices are orthogonal. Our bound does not contradict to the existing bounds but is a complement to the existing bounds. As supported by several existing empirical results, low-rankness is not the only reason for generalization. Furthermore, our bound can be combined with the existing bounds to obtain a tighter bound. Our result sheds new light on understanding generalization of neural networks with full-rank weight matrices, and it provides a connection between operator-theoretic analysis and generalization of neural networks.

Published as a conference paper at ICLR 2024
KOOPMAN-BASED GENERALIZATION BOUND: NEW ASPECT FOR FULL-RANK WEIGHTS
Yuka Hashimoto 1,, Sho Sonoda', Isao Ishikawa A Atsushi Nitanda', Taiji Suzuki 1 NTT, 2 RIKEN AIP, 3 Ehime University, A A*STAR CFAR, 5 The University of Tokyo
ABSTRACT
We propose new bound for generalization of neural networks using Koopman operators. Whereas most of existing works focus on low-rank weight matrices, we focus on full-rank weight matrices. Our bound tighter than existing norm-based bounds when the condition numbers of weight matrices it is completely independent of the width of the network if the weight matrices are orthogonal. Our bound does not contradict to the existing bounds but is a complement to the existing bounds. As supported by several existing empirical results, low-rankness is not the only reason for generalization. Furthermore, bound can be combined with the existing bounds to obtain a tighter bound. Our result sheds new light on understanding generalization of neural networks with full-rank weight matrices, and it provides a connection between operator- theorttc analysis and generalization of neural networks.
small. Especially,
INTRODUCTION
Understanding the generalization property has been one of the biggest topics for analyzing neural networks. A major approach for theoretical investigation of this topic is bounding some complex- ity of networks (Bartlett & Mendelson 2002, Mohri et al. 2018). Intuitively, large number of parameters makes the complexity and generalization eтror large. This intuition has been studied, for example, based on a classical VC-dimension theory (Harvey et al., 2017, Anthony Bartleu 2009). However, for neural networks, small generalization error can be achieved even in over- parameterized regimes (Novak et al., 2018 Neyshabur et al., 2019p. To explain this behavior, norm- based bounds have been investigated (Neyshabur et al. 2015 Bartlett et al. 2017 Golowich et al, Neyshabur et al. 2018 Wei &
2018
2021 Ju et al. 2022 Weinan E al, These bounds do not depend on the number of parameters explicitly. However, they typ- ically described by the (p, 9) norms of the weight matrices, and if the norms are large, these bounds
2020 Li et al.
2022
tackle over- parameterized networks is a compression-basse approach (Arora et al.) 2018)] (Suzuki er al.) 2020). These bounds explain the generalization of networks by investigating how much the networks can be compressed. The bounds get smaller as the ranks of the weight matrices become smaller. However, low-rankness not the only reason for generalization. Goldblum al. (2020) empirically showed that even with high-rank weight matrices, networks generalize well. This implies that if the ranks of the weight matrices are large, the existing compression bounds are not always tight.
grow exponentially with respect the depth of the network. Another approach
In this paper, we derive completely different type of uniform bounds of complexity using Koopman operators, which sheds light on why networks generalize well even when their weights are high- or full-rank matrices. More precisely, let I, be the depth, d, be the width of the jth layer, be the final nonlinear transformation, and n be the number of samples. For 1,..., I,, let W,- E Rdd xd;-1 be an injective weight matrix, sj > / describes the smoothness of a function space H, where the Koopman operator is defined. Our results are summarized as follows, where ||-|| is the operator norm, Ej and Gy are factors determined by the activation functions and the range of Wj, respectively:
Rademacher complexity o |Llll II G,E,
det(W)W,)175
Surprisingly, the determinant factor tells us that if the singular values of W, are large, the bound gets small. It is tight when the condition number of W,, i.e, the ratio of the largest and the

---

Norm-based bounds Generalization bounds based the norm of W, have been investigated in previous studies. These bounds are described typically by the (p. q) matrix norm | [Willp, of W; (see the upper part of Table [Tp. Thus, although these bounds do not explicitly depend on the width of the layers, they tend to be large as the width of the layers becomes large. For example, the (p. q) matrix norm of the d by identity matrix is d'/r. This situation is totally different from our case, where the factor related to the weight matrix is reduced to 1 if it is orthogonal. We can our bound is described by the spectral property of the weight matrices and tight when the condition number of W, small. [Bartlett al. (2017): Wei & Ma (2020); JJu et al. (2022) showed bounds with reference matrices A, and By. These bounds allow us to explain generalization property through the discrepancy between the weight matrices and fixed reference matrices. A main difference of these bounds from ours is that the existing bounds only focus on the discrepancy from fixed reference matrices whereas our bound is based on the discrepancy of the spectral property from a certain class of matrices, which is much broader than fixed matrices. Li et al.) (2021) showed bound described by IT ||W, 1/. the discrepancy between the product of largest singular values of Wi.... W....., Wr and 1. It is motivated by the covering number cx of the input space X' and diameter 7x of the covering set, which depends on the input samples x = (#1,..., Ix).. ,.,...,,,,.........., This bound somewhat describes the spectral properties of W,. However, they only focus the largest singular values of Published as a conference paper at ICLR 2024
smallest singular values, is small. Especially, when W is orthogonal, G2 and the factor reduces to 1. We can interpret that Wj transforms signals in certain di- rections, which makes it easy for the network to extract features of data. Networks with orthogonal weight matrices have been proposed (Maduranga et al. 2019 Wang et al. 2020 Li et al. 2021).
Our bound also justifies the generalization property of these networks.
In addition to providing the new perspective, we can combine our bound with existing bounds. In other words, our bound can be complement to existing bounds. Goldblum et al. (2020) pointed out that the rank of the weight matrix tends to be large near the input layer. but be small near the output layer. By adopting our bound for lower layers and existing bounds for higher layers, we ob- tain a tight bound that takes the role of each layer into account. The determinant factors come from Koopman operators. Koopman operator is a linear operator defined by the composition of functions. has been investigated for analyzing dynamical systems and time-series data generated from dy- namical systems (Koopman] 1931 BudiSić et al. 2012 Kawahara 2016 | Ishikawa et al. [0188] Klus
et al., 2020; Hashimoto et al. 2020 Ginnakis & Das 2020 Brunton et al., (022). Its theoretical aspects also have been studied (Das et al. 2021 Ikeda et al. 2022a Ishikawa 2023). Connections between Koopman operators and neural networks have also been diseussed. For example, efficient learning algorithms are proposed by describing the learning dynamics of the parameters of neural networks by Koopman operators (Redman et al. 2022 Dogra & Redman (020). [usch et al. (2017) applied neural networks to identifying eigenfunctions of Koopman operators extract features of dynamical systems. Konishi & Kawahara (023) applied Koopman operators to analyze equilibrium models. On the other hand, this paper, we represent the composition structure of neural networks using Koopman operators, and apply them to analyzing the complexity of neural networks from an operator-theoretic perspective.
Our main contributions are as follows:
We show a new complexity bound, which involves both the norm and determinant of the weight matrices. By virtue of the determinant term, our bound gets small if the condition numbers of the weight matrices get small. Especially, it justifies the generalization property of existing networks with orthogonal weight matrices. It also provides new perspective about why the networks with
high-rank weights generalize well (Section 2 the paragraph after Proposition 4 and Remark 3). We can combine our bound with existing bounds to obtain a bound which describes the role of each layer (Subsection 4.4).
We provide an operator-theon theoretic approach to analyzing networks. We use Koopman operators to derive the determinant term in our bound (Subsection 3.44onnnddddd Subsection 4.1. We emphasize that our operator-theoretic approach reveals new aspect of neural networks.
2 RELATED WORKS
W3 and do not take the other singular values into account. On the other hand, our bound is described
by how much the whole singular values of W, differ from its largest singular value.
2

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of our bound to existing bounds.
Authors
Rate
Type
2
11 v'n
12.2
Neyshabur et
2015)
L maxx d, IT |1W5l|
IW51l
1/2
Neyshabur et al.
2018
vn
j=1
I[
Norm-based
Golowich al.
2018
T j=1 135l2.22)
min
3/2
11 vn
||
IIW
-A,
Bartlett et al.
2017
Σj=1
E/ "1 min((: (1.
IW: 1.:---44 112.2.11; B3, 12.1112)2/339122
Wei & Ma (020))
v/n
Ei B,1lW, A,1l2,2
Ju et al.
2022
v/i
Li et al.
2021)
x
1 |W
11 7/x + V
Arora et al.
2018
4+
L max, ((x))]
| f=1 1²344...
1
1/2
Compression
Suzuki et al.
2020
1 83 Py(dz- + d,))
1/2
Vn
1Ill V/n
I1 G, 1
Operator-theoretic Kj and 0j are determined by the Jacobian and Hessian of the network f with respect to the jth layer and Wj, respectively. Fg and d, are rank and dimension of the jth weight matrices for compressed network.
Ours
det(W, Wet(W
Compression-base based bounds Arora et al. (2018) and Suzuki et al. (2020) focused on compression of the network and showed bounds that also get small as the rank of the weight matrices decreases, with the bias i induced by compression (see the middle part of Table [ Arora et al. (2018) intro- duced layer cushion J4, and interlayer cushion μ4 for layer j. which tends be small if the rank of Wj is small. They also observed that noise is filtered by the weight matrices whose stable ranks are small. (Suzuki al. (2020) showed the dependency on the rank more directly. The bounds describe why networks with low-rank matrices generalize well. However, networks with high-rank matrices can also generalize well (Goldblum al., 2020), and the bounds cannot describe this phenomenon. Arora et al.) (2018) Figure 1) also empirically show that noise rapidly decreases on higher layers. Since the noise stability related to the rank of the weight matrices, the result supports the tightness of their bound on higher layers. However, the result also implies that noise does not really decrease on lower layers, and we need an additional theory that describes what happens on lower layers.
3 PRELIMINARIES
3.1 NOTATION
For a linear operator W on Hilbert space, its range and kernel are denoted by R(W) and ker(W), respectively. Its operator norm is denoted by [[W] For function p E (RR), its - is denoted by ||p]l... For a function on Rd and a subset of Rd, the restriction by hls. For f e (TR)), we denote the Fourier transform of f as f(w) J f(z)e- -irddr. We denote the adjoint of matrix W by W
on is denoted
3.2 KOOPMAN OPERATOR
Let Fi and F2 be function spaces on Rd and d2 For a function f Rd - R2d, we define the Koopman operator from F2 to Fi by the composition as follows. Let Dj {u E F2 gos E Fi). The Koopman operator Ky from F2 to F, with respect to f is defined as Kfg = o for E Dy.
3.3 REPRODUCING KERNEL HILBERT SPACE (RKHS)
As function spaces, we consider RKHSs. Let p be a non-negative function such that p E (-(R)). Let HR.) = (f E (TR) | fl E (RR)) be the Hilbert space equipped with the inner product ( (J19) Sax (w)) ( We can that (z, v) Sge vl( p(w)d
3

---

Published as a conference paper at ICLR 2024
is the reproducing kernel of Hp(R)), i... (), (b) f(x) for f E Hp(R*). Note that since (IR)) S (RR", the value of functions in HR(R)) vanishes at infinity.
One advantage of focusing on RKHSs that they have well-defined evaluation operators induced by the reproducing property. This property makes deriving an upper bound of the Rademacher complexity easier (see, for example, Mohri et al. (2018 Theorem 6.))..
Example 1 Set p(w) = 1/(1 + [|=]l for s > d/2. Then, Hp (IR)) is the Sobolev space (RR) of order s. Here, || is the Euclidean norm of w E RR. Note that if E N. then Il = Eials Ca.s,d f where Ca,a, = Appendix(K] for more details.
|ail)! and a is a multi index. See
3.4 PROBLEM SETTING
In this paper, we consider an L-layer deep neural network. Let do be the dimension of the input space. For j 1,... L, we set the width as dj, let W, Rd - Rd be linear operator, let by Rd + Rdd be a shift operator defined as x + + aj with bias aj E Rd, and let oy IRd; + I& be nonlinear activation function. In addition, let g Rdd + C be nonlinear transformation the final layer. We consider network f defined
g by WL 00L-1 o 6b-1 WL- o00 ca Wi.
Typically, regard that W1 is composed by b1, 01 to construct the first layer. We sequentially construct the second and third layers, and so on. Then we get the whole network f. On the other hand, from operator-theoretic perspective, we analyze f in the opposite direction. For O,.... L, let Pj be a density function of a finite positive measure on Rdd The network f is described by the Koopman operators Kw, Hp, (Rd)) ) - Hp, (RR: Kaz: Kaz Hp, (R2,) - H7, (R²4) as Ko,_, Kw, Ko,g.
f f= Kw, Ko, Ko, ...
The final nonlinear transformation y is first provided. Then, y is composed by by and Wz, i.e. the corresponding Koopman operator acts on g. We sequentially apply the Koopman operators corresponding to the 1)th layer, (L-2) 2) layer, and so on. Finally, we get the whole network f. By representing the network using the product of Koopman operators, can bound the Rademacher complexity with the product of the norms of the Koopman operators.
To simplify the notation, we denote (RR)) by Hj. We impose the following assumptions.
Assumption The function g is contained in H and Ka, is bounded for L.....,
Assumption There exists B > 0 such that for any E Rd, Ikpo (z. 20 < B?.
We denote by F the set of all functions the form of (2) with Assumption I As a typical example, we set (w) 1/(1 + | (2)ss for 8j > d and g(x) = -|ll" then Assumption holds
Kay is bounded, and kpo satisfies Assumption 2
Remark Let be smooth function which does not decay at infinity, (e.g., sigmoid). Although H, (R.) does not contain g. we can construct a function ğ E HR() such that ğ(x) = g(x) for x in a sufficiently large compact region and replace by ğ in practical cases. See 6 details.
For the activation function, we have the following proposition (c.f. Sawano 2018 Theorem 4.46)).
Proposition 1 Let p(w) 1/((1 [|])) for E 1Rd E N. and > d/2. the activation funnctoionfuunction a has the following properties, then Ko (RR) + (IR) is bounded.
is s-limes differentiable and its derivative 8 is bounded for any multi-index ((o1,...,,aa) ES= 0jj $)..
a is bipsshhcii,,, i.e,, a is bijective and both a and -1 are Lipschitz continuous.
Example 2 We choose smooth version of Leaky ReLU (Biswas et al. 2022). We will see how we can deal with other activation functions. such as the sigmoid and the hyperbolic tangent in Remark g
4

---

Published as a conference paper at ICLR 2024
Remark 2 We have ||K,|] I
det((Jo max (1, ooo.......... 11 bc) is and a is
elementwise, where Jo the Jacobian of a As we will discuss in Appendix B deriving a tight bound for larger is challenging and future work.
4 KOOPMAN-BASEI BOUND OF RADEMACHER COMPLEXITY
We derive an upper bound of the Rademacher complexity. We first focus on the case where the weight matrices invertible injective. Then, we generalize the results the non-injective case.
Let Ω be a probability space equipped with a probability measure P. We denote the integral Jn ((w) of measurable function on 52 by E[s]. Let S1,-..158 be i.i.d. Rademacher variables. For a function class and #1, 21,..., Uin Rd we denote the empirical Rademacher com- plexity by (x, G), where x = ( rn). We will provide an upper bound of R. (x, G) using Koopman operators in the following subsections.
4.1 BOUND FOR INVERTIBLE WRIGHT MATRICES (dj dd)
In this subsection, we focus on the case d, = d (j = 0..... L) for some d N and W, is invertible for j = 1,.... L. This is the most fundamental case. For C, W(C, D) = (W& E Rdxd |[W]| S C, |det(W))) 2 D} and a function class Fin C, D) = {f E
O, set class of weight matrices
F W3 E D)). We have the following theorem for bound of Rademacher complexity.
Theorem (First Main Theorem) The Rademacher complexity Rr, (x, Pine (C, (C,D)) is bounded as
Rí (x,, DC) Bllghl sup Vn W,EW(C.D)
Ippy//p;-1 ll (Ii
II [IK,,)))
L-1
(3)
|de)(W)))1/2
By representing the network using the product of Koopman operators, we can get the whole bound by bounding the norm of each Koopman operator. A main difference of our bound from existing bounds, such as the ones by Neyshabur et al. (2015): Golowich et al.] (2018) is that our bound has from change of variable when we bound the norm of the Koopman operators, described by the following inequality:
the determinant factors in the denominator in Eq. (3) They
|| kw; || S (Ilp:/Ps-1 o Wj I det,
|Ka, 1=
for j = 1, ... L. Since the network f in Eq. (2) satisfies f Ho, using the reproducing property of Hn. derive upper bound of Ri (x, F)C in similar manner that for kernel methods (see,Moohr) Mohri et al. (2018 Theorem 6.12)).
Regarding the factor (1p)//pp-oo// W]) in Eq. 3. obtain the following lemma and proposition, which show is bounded by [|Wyl| and induces the factor / /el WW 2// in Eq. 1
Lemma Let p(w) = 1/(1 + (ر for > d/2 and Pj = for 0,..., Then, we have (pp(pp & I max(1, ||W,|||
As result, the following proposition is obtained by applying Lemma to Theorem
Proposition 4 Let p(w) 1/(1 + [|= for d/2 and P5 p for 0, O,..., L. We have Rx, Finv (C, D))
B Bgg ||
mmxx( 11, O*3 (maxt), VD
1--1
II [[,K,,)).
Vn
Comparison to existing bounds We investigate the bound in terms of the singular values of d/2. Then, the term de- Wj. Let mh.j ... 2 nd. be the singular values of W, and let 1/2 where rej = m..//E.. pending on the weight matrices in bound 1 is described as n/ II -i=
On the other hand, the existing bound by Golowich et al. (018)) is described as m/, (Ed r 1// Since they are just upper bounds, our bound does not contradict the existing bound. Our bound is tight when the condition number Ta.; of W; is small. The existing bound is tight when Ta,j is large. Note that the factors in our bound (1) are bounded below by 1.
5

---

Published as a conference paper at ICLR 2024
Remark 3 If weight matrix W is orthogonal, then the factor | /dt in the bound (7) reduced to 1. On the other hand, existing norm-based bounds are described by the (p.q) matrix norm. The (p. 9) matrix norm of the d by d identity matrix is d which is larger than 1. Indeed, limiting the weight matrices to orthogonal matrices has been proposed (Maduranga et al. (209 Wang et al. 2020)) Li al.) (027). The tightness of our bound in the case of orthogonal matrices implies the advantage of these methods from the perspective of generalization.
Remark 4 There is tradeoff between and B. We focus on the case where Pý(W) 1/(1+|
According to Lemma 3 the factor / Wlooo becomes small as 8 approaches to d/2. However, the factor B goes to infinity as goes to d/2. Indeed, we have kp(z, = J p(w)dw = s-d/2 for some constant C > O. This behavior corresponds the fact that if s = d/2, the Sobolev space not an RKHS, and the evaluation operator becomes unbounded.
S (Trrerer 2 C (r-1)4/2-1 dr - $12 ddj2-1-*dt ddr C 24/2-
4.2 BOUND FOR INJECTIVE WEIGHT MATRICES (dj 2 d)-1)
We generalize Theorem 2 that for injective weight matrices. dz dj-1, then Wj is not
surjective. However, it can be injective, and we first focus on the injective case. Let W,(C, D)
{W E - dj 2 dj-1, || C, ddet(W-W) 2 D} and DC, o by o WT o OL-1 b Wt.1 o.... o oj o by and G₃ =
{f F
W, E W,(C, Let fg [1b, (R(W)) /llll, We have the following theorem for injective weight matrices.
Theorem (Second Main Theorem) The Rademacher complexity Rx, (C, D)) is bounded as
(x, (C,
S
B Blg Vn (C.D)(C.D)
sup
L 1p5-1/(p5-1 W II j=1
R(W,), Gj We,
L-1
II j=1
K. 11) (4)
Since Wj not always square, we do not have de)(W;) in Theorem However, we can place det(W,) with det (W, WW2,,)1/2, As Lemma A we have the following lemma about the factor |lpy/(e, (0///1;-130 ( (RR(3)))) in Eq. 4h.
Lemma Let (,(w) = 1/(1 + || for 8; > d and for O...., L. Then, we have 1p0-1//0p-11 o W3 (lR I max (1, | 23
Applying Lemma to Theorem 5 we finally obtain the bound TT. Regarding the factor Gj. the following lemma shows that Gj determined by the isotropy of Jj-
Lemma Let (yw = 1/(1+ [| so > d and be the Sobolev space on R(W,)) with p(w) = 1/(11 + 3))s Then, G, S G.oolfflR((,))
for for j = O....,
...... L. Let sj 2 8j-1 and H3
fa IIn,f/ll where Gj,0 ||5; n
The factor G is expected to be small. Indeed, if fz(x) e-olaall (It is true if g is Gaussian and L.), Gj gets small 8, and d, gets large. Moreover, Gj can alleviate the dependency of l|KK,,l on dj and sj. See Appendix more details.
Remark 5
4.3 BOUNDS FOR NON-INIECTIVE WEIGHTT MATRICES
The bounds in Theorems 2 and 5 are only valid for injective weight matrices, and the bound goes to infinity if they become singular. This is because W, d1 + Rd has singularity, h W for h E H, becomes constant along the direction of ker(W,), )). As result, h W, is not contained in H and Kw, becomes unbounded. To deal with this situation, we propose two approaches that valid for non-injective weight matrices, graph-based and weighted Koopman- hhased ones.

---

Published as a conference paper at ICLR 2024
4.3.1 GRAPH-BASE BASED BOUND
The first approach deal with this situation is constructing an injective operator related to the graph of w. For j I....,L, let ry (W,)), 6, Σk=o rk- and W, be defined as (z(11 22) = (W5z1, P. for 21 E IR and 22 E R for j 2 and W (Wyæ. x. Pςæ) for j = 1. Here. Pj is the projection onto ker(W,), Then, W3 is injective (See Appendix D Let ōj R& + R& and by R& + R& be defined respectively as (2), = (z) 22) and
( 02) = (by(21), x2) for 21 R and 22 R In addition, let 9 Hps (R**) be defined
as x2) ((2)))(()))) for 1 E gd and æ2 E R where v is rapidly decaying function on R so that (P (R Consider the following network:
f(x) = go hn o Wr ........ ................ oh o (x)
-PProi..-oll o bb WT.- a o bi Wi((), (......... Pro ob W1()), Pιæ)
100 o W
o ob o (x)).
(5)
Since det W,) = do, W 1) and ||W = / || Wll we set W,C,, (W R4 | V W < C, W +1) 2 D) and F(C, U FE W E D),. Moreover, put H2 Hpp (IE4)). By Theorem | we obtain the following bound, where the determinant factor does not go to infinity by virtue of the identity appearing in W,.
Proposition 8
The Rademacher complexity R., (x, F(C, D)) is bounded as lpp//p//1 Wj)l
1/22 1/2 R(W3),00 1/4
G
)
L-1
(x, F(C, D))) Vn
(II
II [IKo;11)
sup (C.D,
det(W, + 1)1/4
Remark 6 The difference between the networks 5 and (2) is the factor th. we set 1p as (bxx)= =1
for x in sufficiently large region Ω then f(x) f(x) for x E Ω2 We can set vb for example,
as a smooth bump function (Tu 2017 Chapter 13). See Appendix fifor the definition. the data is in a compact region, then the output of each layer is also in a compact region since [Wi S
V VIII+ W2W,ll S C. Thus, it is natural to assume that f can be replaced by f in practical cases.
it, grows as Ω becomes large. This is because | 1) becomes large as the volume Sf gets large. This fact does not contradict the fact that the bound in Theorem goes to infinity if W is singular. More details are explained in Appendix E
Remark 7 The factor |
4.3.2 WEIGHTED KOOPMAN-BASHR BOUND
Instead of constructing the injective operators in Subsection 4.3.1 man operators. For v5 R&d C, define Kw, h 1) h W5. which is called the weighted Koopman operator. We construct the same network as / in Eq. 5 using Kw,-
can also use weighted Koop-
f(x) = Kw, Ko. ... Kw, Korg(z)
(z) bi Wi(x)) ..
W 0000--00..0000bb oo. Wi()))
g(b o W2 o.... .....001:000 o o W1(x))
(HLL-10bL-1 o o..-
b W1 (z)..... bb (1))),
g(b o WL o ......... .00 bb o (x)),,
where (x .L) 2 (x1) ... (ZL) for Ij Rd 1, Let We, = W ker wer be the restricted operator of W, to ker (er(W,)+ Set W,,(C, = (W E Rdd,-idd
[W] < {s F W2 Wr,(C, By letting dy decay in the direction of ker(W,), e.g., the smooth bump function, Kw,h h for h E H, decays in all the di- rections. We only need to care about W.jj, not the whole of WG, Note that tú has the same role as v in Eq. (5). If the data is in compact region, we replace f by which coincides with on the compact region. By virtue of the decay property of v/y, we can bound Kw, even if W, is singular.
C, |det(W.)) D} and D)
7

---

Published as a conference paper at ICLR 2024
Proposition 9 Let Py P)(w) 1/(1 |w)l) with 8j N. 83 8j-1. and 83 d
Let H4j1 -p, (k)r(W;)) and v be function satisfying 4)(0) 25,( for some 11 E H1-1, where x 21 + D2 for xı E ker(W;) and 22 E k- Moreover, let Then, we have
Gj= (Kkrll),--kor(WW)))) (ker(W,)))
(x, ((CC,D) S BlggH sup vn w,eW,,(C.D) 1=1
(II
I 1,s ( |W
L-1
II IIK,,
[det(W
Remark Although we focus on the singularity of Kw; and use the weighted Koopman operator with respect to Wj. we can deal with the singularity of Kaz in the same manner as Kw,- i.e, by constructing the weighted Koopman operator Ko, with respect to J. For example, the sigmoid and hyperbolic langent do not satisfy the assumption for og stated in Proposition 7 This is because the Jacobian o not bounded. However, Ka is bounded by virtue 4/--
Remark The norm of 43 can be canceled by the factor Gy. See Appendix F for more details.
4.4 COMBINING THE ROOPMAN-BASER BOUND WITH OTHER BOUNDS
In this subsection, we show that our Koopman-based bound is flexible enough to be combined with another bound. As stated in Subsection 4.1 the case where our bound is tight differs from the case where existing bounds such the one by Golowich al. (2018) are tight. We combine these
bounds to obtain a tighter bound. For 1 < [ S L, let Fist be the set all functions in the form
Jy by o W, 01-1 b o Wi-1 00000 b o W, with Assumption I and let Fiatin C, D) {f E Fia W3 E ()C For s L-1, 1, consider the set of all functions in Hi which have the form
(6)
g bz. Wz. 00L-1 o br.-1 Wt.1 o... 0141 b4t W4+1
and consider any nonempty subset Fi+1.1 of it. For 1 Fi,comb (C, D) (fi fz fi FI+1,L, fo E FI,, The following proposition shows the connection between the Rademacher complexity of Fi.comb(C. D) and that of FI+1.L.
L, we set FL+IZ = {g). Let
Proposition 10 Let x (31,...,,.., ..)) E (Rd)). Let Un (w) Ei= kp (1,2),, Gn(w) E si(w)ip 2.). W {(W, I.W...... Wi) W3 E W, D)), and Yn = 1lu, Ho / /I Balle Then, GyI|K,,ll
Rx, Fl,comb (C, D)) I sup.w..... w.J. IT 1=1 (X, F1-1.)) + vi inf
P--1
1/2
p. 1ow
RRW,)) ).00 det(W;
E
[ball [all
on 11,,,)
The complexity of the whole network is decomposed into the Koopman-based bound for the first / layers and the complexity of the remaining L- layers, together with term describing the approx-
imation power of the function class corresponding to L - layers. Note that Proposition I0 gener-
alizes Theorem 5 up to the multiplication of constant. Indeed, if / = I., we have R₁ (x. F1+1.2) =
O. In addition, we have inforeFiiL E (suPhgEFi4ia. ||/ ha 0.. u. [1]] = E [llg
Ill / ||I < [1a]|E> [(1 + 7..
Remark 10 We can also combine our Koopman-basee approach with the existing "peeling" ap- proach, e.g., by Neyshabur et al.) (2015); Golowich et al.) (2018) (see Appendix G). Then, for 1 1 L. obtain bound such as O(I IIW - l|W, We, 1/4)) Typically, in many networks, the width grows sequentially near the input layer, i.e. dj-1 dj for small j and decays near the output layer, i.e. dz-1 2 dj for large j. Therefore, this type of combination is suitable for many practical cases for deriving tighter bound than existing bounds.
Proposition 10 and Remark I0 theoretically implies that our Koopman- based bound is suitable for lower layers. Practically, we can interpret that signals are transformed the lower layers that its essential information is extracted on the higher layers. This interpretation also supports the result in Figure by Arora et al. (2018). Noise is removed (i.e., signals are extracted) by the higher layers, but is not completely removed by lower layers. We will investigate the behavior of each layer numerically in Section 5 and Appendix J.2.1 J.2.1
8

---

Published as a conference paper at ICLR 2024
20
With Reg. Pegudorization
(mutippedd by Onutipteed by 5)
15
0.88
Regusetization
0.86
(a)
(b)
(c)
0.84
0.82
0.80
400
500
1200
1600
10
3x100 6x iterations
9x10 12
Ceneraliation Err.
Epechs
Figure 1: (a) Scatter plot of the generalization set to get dark as the epoch proceeds. (b) Test accuracy with and without the regularization based on our bound. (c) The condition number Td.) //..//a, of the weight matrix for layer j = 2....,4.
versus bound (for 5 'ndependeent runs). The color is
5 NUMERICAL RESULTS
Validity of the bound To investigate our bound numerically, we consider a regression problem
on IR' where the target function t is ((x) e --112=-111" We constructed a simple network f(x g(W2o(WWx b1) ( +b2), where W1 33333, W2 E R6x3 by E R2, by E RR g(x) e -- and is a smooth version of Leaky ReLUU proposed by Biswas et al. (022). We created a training dataset
||=+||
from samples randomly drawn from the standard normal distribution. Figure [ (a) illustrates the
relationship between the generalization error and our bound O || /(det( (W,,,) W,) Here, we set s; = (d, /. In [ we can see that our bound gets smaller in proportion to the generalization error. In addition, we investigated the generalization property of a network with a regularization based on our bound. We considered the classification task with MNIST. For training the network, we used only n 1000 samples to create situation where the model is hard to generalize. We constructed a network with four dense layers and trained it with and without a regularization term |/ det (T + W,), which makes both the norm and determinant of W; small. Figure T (b) shows the test accuracy. We can see that the regularization based on our bound leads to better generalization property, which implies the validity of our bound.
Singular values of the weight matrices We investigated the difference in the behavior of singular values of the weight matrix for each layer. We considered the classification task with CIFAR-10 and AlexNet (Krizhevsky et al. 2012). AlexNet has five convolutional layers followed by dense layers. For each J = 2,...,,,, 5, we computed the condition number rd., of the weight matrix. The results are illustrated in Figure (c). We scaled the values for 4,5 5 for readability. Since the weight matrix of the first layer (j = 1) is huge and the computational cost of computing its singular values expensive, we focus on j 2, 2....... 5... We can see that for the second layer (j = 2). rá.j tends to be small as the learning process proceeds (as the test accuracy grows). On the other hand, for the third and fourth layers (j = 3, 4), the ra,j tends to be large. This means that the behavior of the singular values is different depending on the layers. According to the paragraph after Proposition 4 our bound becomes smaller as rd.j becomes smaller, but the existing bound becomes smaller as ra.j becomes larger. In this case, our bound describes the behavior of the second layer, and the existing bound describes that of the third and fourth layers. See Appendix D for more details and results.
6 CONCLUSION AND DISCUSSION
In this paper, we proposed a new uniform complexity bound of neural networks using Koopman operators. Our bound describes why networks with full-rank weight matrices generalize well and justifies the generalization property of networks with orthogonal matrices. In addition, we provided an operator-theoretic approach analyzing generalization property of neural networks. There are several possible limitations. First, our setting excludes non-smooth activation functions. Generaliz- ing our framework to other function spaces may help us understand these final nonlinear transfor- mations and activation functions. Moreover, although the factor |,,,, is bounded if we set certain activation functions, how this factor changes depending on the choice of the activation function has not been clarified yet. Further investigation of this factor is required. Furthermore, we assume a modification of the structure of the neural network for deriving a bound for non-injective matrices. Thus, we still have room for improvement about this bound. We simply decomposed the product of Koopman operators into every single Koopman operator. For more refined analysis, they should be tied together to investigate the connection between layers. Considering function space mani- fold that contains the range of the transformation corresponding to each layer may also be effective for resolving this issue. These challenging topics are left future work.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
SS was partially supported by JST PRESTO JPMJPR2125 and JST CREST JPMJCR2015. was partially supported by JST CREST JPMICRI91S and IST ACT-X JPMJAX2004. AN was partially supported by JSPS KAKENHI 22H03650 and JST PRESTO JPMJPR1922 1928. TS was partially sup- ported by JSPS KAKENHI 20H00576 and JST CREST.
REFERENCES
Martin Anthony and Peter L. Bartlett. Neural network learning: Theoretical foundations. Cam- bridge University Press, 2009.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th International Conference on Machine Learning (ICML),
2018. 2018.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. In Proceedings of Advances Neural Information Processing Systems 31 (NIPS), 2017.
Koushik Biswas, Sandeep Kumar, Shilpak Banerjee, and Ashish Kumar Pandey. Smooth maximum unit: Smooth activation function for deep networks using smoothing maximum technique. Pro- ceedings of 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Steven L. Brunton, Marko Budišić, Eurika Kaiser, and Nathan Kutz. Modern Koopman theory for dynamical systems. SIAM Review, 64(2):229-340, 2022.
Marko Budišié, Ryan Mohr, and Igor Mezić. Applied Koopmanism. Chaos (Woodbury, N.Y.), 22: 047510, 2012.
Suddhasattwa Das, Dimitrios Giannakis, and Joanna Slawinska. Reproducing kernel Hilbert space compactification of unitary evolution groups Applied and Computational Harmonic Analysis, 54:75-136. 2021.
Akshunna S. Dogra and William Redman. Optimizing neural networks via Koopman operator the- ory. In Proceedings of Advances in Neural Information Processing Systems 34 (NeurIPS), 2020.
Dimitrios Giannakis and Suddhasattwa Das. Extraction and prediction of coherent patterns in in- compressible flows through space-time Koopman analysis. Physica D: Nonlinear Phenomena, 402:132211, 2020.
Micah Goldblum, Jonas Geiping, Avi Schwarzschild, Michael Moeller, and Tom Goldstein. Truth or backpropaganda? an empirical investigation of deep learning theory. Proceedings of the 8th International Conference Learning Representations (ICLR), 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of
neural networks. In Proceedings of the 2018 Conference On Learning Theory (COLT), 2018.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension bounds for piecewise linear neural networks. In Proceedings of the 2017 Conference on Learning Theory (COLT), pp. 1064-1068, 2017.
Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Yoichi Matsuo, and Yoshinobu Kawahara. Krylov subspace method for nonlinear dynamical systems with random noise. Journal of Machine Learn- ing Research, 21(172); 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of 2015 IEEE International Conference Computer Vision (ICCV), 2015.
10

---

Published as a conference paper at ICLR 2024
Masahiro Ikeda, Isao Ishikawa, and Yoshihiro Sawano. Boundedness of composition operators reproducing kernel Hilbert spaces with analytic positive definite functions. Journal of Mathemat- ical Analysis and Applications, 511(1): 2022a.
Masahiro Ikeda, Isao Ishikawa, and Corbinian Schlosser. Koopman and Perron- Frobennus operators reproducing kernel Banach spaces. Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(12):123143, 2022b.
Isao Ishikawa. Bounded composition operators on functional quasi-banach spaces and stability of dynamical systems. Advances in Mathematics, 424:109048, 2023.
Isao Ishikawa, Keisuke Fujii, Masahiro Ikeda, Yuka Hashimoto, and Yoshinobu Kawahara. Metric on nonlinear dynamical systems with Perron-Frobenius operators. In Proceedings of Advances in Neural Information Processing Systems 32 (NeurIPS), 2018.
Haotian Ju, Dongyue Li, and Hongyang R Zhang. Robust fine-tuning of deep neural networks with Hessian-based generalization guarantees. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022.
Yoshinobu Kawahara. Dynamic mode decomposition with reproducing kernels for Koopman spec- tral analysis. In Proceedings of Advances in Neural Information Processing Systems 30 (NIPS), 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015.
Stefan Klus, Ingmar Schuster, and Krikamol Muandet. Eigendecompositions of transfer operators in reproducing kernel Hilbert spaces. Journal of Nonlinear Science, 30:283-315, 2020.
Takuya Konishi and Yoshinobu Kawahara. Stable invariant models via Koopman spectra. Neural Networks, 165:393-4000 405, 2023.
Bernard Koopman. Hamiltonian systems and transformation in Hilbert space. Proceedings of the National Academy of Sciences, 17(5):315-11,, 1931.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In Proceedings of Advances in Neural Information Processing Systems 26 (NIPS), 2012.
Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 135043313 2021.
Bethany Lusch, J. Nathan Kutz, and Steven L. Brunton. Deep learning for universal linear embed- dings of nonlinear dynamics. Nature Communications, 9:4950, 2017.
Kehelwala D. G. Maduranga, Kyle E. Helfrich, and Qiang Ye. Complex unitary recurrent neural networks using scaled Cayley transform. Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of the 2015 Conference on Learning Theory (COLT), 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to eecttrall-normalizee margin bounds for neural networks. In Proceedings of the 6th Interna- tional Conference on Learning Representations (ICLR), 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrizatinn in generalization of neural networks. In Proceedings of the 7th International Conference Learning Representations (ICLR), 2019.

---

Published as a conference paper at ICLR 2024
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeftrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization in neural networks: an empirical study. In Proceedings of the 6th International Conference Learning Representations (ICLR), 2018.
William T. Redman, Maria Fonoberova, Ryan Mohr, Yannis Kevrekidis, and Igor Mezić. An op- erator theoretic view on pruning deep neural networks. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
B. Rubin. A note on the blaschke- saacckke-petkantschine formula, Riesz distributions, and Drury's identity. Fractional Calculus and Applied Analysis, 21: 11:1611-,,50, 2018.
Yoshihiro Sawano. Theory of Besov Spaces. Springer Singapore, 2018.
Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non-compressed
network: unified generalization enror analysis of large compressible deep neural network. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Loring W. Introduction to Manifolds. Springer New York, second edition, 2011.
Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X. Yu. Orthogonal convolutional neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recog- nition (CVPR), 2020.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via Lip- schitz augmentation. In Proceedings of Advances in Neural Information Processing Systems 33 (NeurIPS), 2019.
Colin Wei and Tengyu Ma. Improved sample complexities for deep neural networks and robust classification via an all-layer margin. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
Weinan E, Chao Ma, and Lei Wu. The Barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 11369-406, 2022.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A PROOFS
We provide the proofs of the theorems, propositions, and lemmas in the main text.
Proposition 1 Let p(w) = 1/(1 + [| for E Rdd E N, and & > dj2. If the activation function has the following properties, then Ka Hp H (R(R)) is bounded.
a is 8-fimes differentiable and its derivative 0 is bounded for any multi-index a E {(a1....., aa) Ej=1 Oj S s}.
is bi-iiphchitz, Le., a is bijective and both and 0- are Lipschitz continuous.
Proof For h E ((R)), we have || (R())) Ejols c We denote o(x) (o1(z)..... oz))) and Dzo(x)= (0 (z)). ,o)a(()))) for y Nd. By the Faà di Bruno formula, we have
(oba(z))
(zh)))(z)= Σ (M(((z)
Σ
Σ al II
j=l ky1(1,1)|k11
i= ()
Ej- 1kyl4 for some m I |a| and 8, n. 5, E No. (8] I Jal. hal s |a). |& s la). By the boundedness of the derivatives σ, there exists CR 0 such that
= 17 8)- Thus, (h o (x) is written as the finite weighted sum of a (((()))
where p(a, 3)
(kI,.... h, 1e..,,..,11 10544
8 (o(x))
I2 (1)) dr S Cans Jud
(0)((((z)))dd.
Rdd
1=1
Moreover, by the Lipschitzness of a-! there exists Ö > 0 such that
|a9(()) Por S zO =0f (a*h(x)))
[=) = det((o llooo Ru JR
Jzd
where Ja- the Jacobian of which shows the boundedness of Ko.
Theorem
2
The Rademacher complexity ft, (x, (inv(C, D)) is bounded as
Bllggl sup Vn W,Ew(C.D)
lp, (p/((py11 W II
II [K,, il) j=1
Rx,, (C,
dot(W,))1/2
We use the following lemma to show Theorem
Lemma A Assume W, R2d - TRd is invertible for = 1,..., L.
Then, for j = -1, 1,..., we have
[Kw, ())
Pj
1
1/2
[K6, =
PJ-1 W
det((
Proof For h Hj. have (h o W (w) JRn h(W ix h(W, (w) detttWW) Thus, the norm of the Koopman operator is bounded as
Kww, h1 = Jge |det( (det(W,)1ppj--(44 (w) de S ||Ali
lh(W,"") "2
(m(
sup weld P (W dee
13

---

Published as a conference paper at ICLR 2024
In addition, for Hj, we have (ww o-loy-h(()). Thus, we obtain |K5,, hls2 ||A]]2 m
................................ Sn be i.idd Rademacher variables (random variables following the uniform distribution on {-1,1]. By the reproducing property of Ho and the Cauchy-Schwarrd inequality, we have
Proof of Theorem Let 2 Fn E do and s......
1F sup Σ
Σ FE (C,D)
(sikip (3, HH
sup
n
(E,
i=1
1/2
E
sup VEFimr(C.D)
11fll
n
< sup
[If E
Σ
8495 kpo (p (2()
n1 fe (C,D)
1/2
S sup
|l
Σ Aipo (2rgs 2is)
(C,((C,D)
B
S
sup
||Kw; Ko, Kos ... KWLK gll
vn W,EW(C.D)
I. II K,, Iellmm
B
S
sup Vn W,EW(C.D))
j=1
where the third inequality is derived by the Jensen's inequality. By Lemma A result.
we obtain the final
Lemma
Let p(w) = 1/(1 + [|w|12) for d/2 and Pj = p for j O,.... L. Then, we have
lp/(p W3 &l I max ||W,,, 11*x)
Proof By the definition of we have
p(w) p(WJw)
[L+IWWja )( max [W,
sup WER'
sup wERd
p W
+ ||
Let W) (W e idd-1 | d, dz-1, |[ S C, ddet(W-W) 2 D} and D) W, E Wj(C,D), The Rademacher complexity Rn (x, Pini(C, D)) is bounded as
Theorem
Rx(x, Finj (C,))))
B Blghu <
sup Va wjew, (C.D)
f |p 1p)-1/(00-1 W3) 1/2 Gj
4-1
II ==1
[ 1)
W,,
where G; =
and S3 gob. W, 001-1000- Wt-10....
Jj o bj.
Proof For h Hy, we have
h(w, w) det((R))
(h (hoW))(w) = _ h(W5z)e to dr
h(x)e in.,," "dr det (R₂))
RRWS)
14

---

Published as a conference paper at ICLR 2024
where W, R2 is the QR decomposition of W, and R(W,) ) is the range of W,. In addition, regard W R R., Since det(Ry)] (det R2 R2)) (det (W, 1/2 the norm of the Koopman operator is bounded as
1 det Ik(W5"w)22 dw
1n(w)1
[KKw, Mli =
JR(W)) det det W p/ dw
P Pi-1 (w)
| (R(W))) (R(W))
sup wER(W,) Pp-1 (W) w)
det det(W; (W W/)1/2
(8)
Thus, have
po(w) 1/2
|| = Jills S I (R(W))) WER(WL)
sup
po(w)
1/2
Gillfilla, WER(W)) po (W]
sup
dei(WW
Po(w) (WWW)
S GillK,,lla, falfal WER(WN)
sup
det(WT
Applying the inequality
8 iteratively, obtain
1/2
GjI[Ko,]
ll
$ II
P5-1
(9)
Pj- o W
(.5)).o del (W))
j=1
Applying the inequality
[[ in the inequality completes the proof.
Lemma 6 Let (w) 1/(1 + || for 8; > dj/2 and for = 0,..., L. Then, we have o Wj )lRs)),.. I max(1, |W 12
Proof By the definition of pj and the assumption of 8j 2 85-1, we have
Pj-1
P--1(44) (w)
sup wER(W,)
Pj-1 o W
PW-1(W9w))
R(W,),00
(1 || 23)3-11
< sup wER(W;)
(1 + || 23
1 + |
85-1
< max(1, |W || 22g
sup wER(W;)
+ |
max(1,
I 2
Lemma Let (ww) = 1/(1+ 11/1+||[[?)) for s; d and
for = O.... L. Let 8 2 8j-1 and H3
be the Sobolev space on R(W,)) with p(w) 1/(1 + [|0| -5 1, Then, G, S G.oollfsR where Gj,0 [|fs
Remark 11 Since W, is injective, dim(R(W))+) dj dj-1. Thus, have 8j 8j-1 -)
15

---

Published as a conference paper at ICLR 2024
Proof By the definition of Gj,o, and since R(W,) and R(W)) are orthogonal, have
IIf, lii,, - (R(W))) = (w)
1
Pj- P)-1(w) dw
JR(W,)
3, R((S))
(f)(w)) + || 112) dww
(f((2)) + ||:22 122 clws
JR(W))-
(1+ [H-lw/ll 11551 - ||ا2 11 85-1 dwgdw1
3%
(w2))
((WS) R(WS)-
Ps(w1 + w2)
(1 + |w + 22 12)
1
G3,0
[1
(R(W)) (R(W))
Pj( + w2)
(1 + || 113) (1+ + ||02|
(1 ||ا 2 | ( ())--) + || 112 + 1|w2 12) dwydws
&G R(W)) R
py(wi + w2) dwydwa
= -Cao Rd, 12)(2))2 pj(w)
dw G Colli = G3,0lfs1111, ||5sl
where h(x) h(x)) (2(22) for x =1 Iı E R(Ws). and 22 E R(W;)+ Note that since R(W,) and R(,))* 1 are orthogonal, we have h(wr)h(wz) h(w).
Proposition 9 Let Py(w) 1/(1 + [|wl12)s with 8, N. 8j 2 Sj-1, and 8j > dj/2. Let 1hj be a function satisfying 4y = (2)( for some 29 E Hp--1 (ker(W,))) where = I1 + I2 for I1 E ker(W) (W3) and D2 E ker(W,) and ker(W,) is the kernel of W,. Let (a, D) = {W E R xd, Moreover, let G3-
|[]|| < C, [det(W;)] 2 D) and FC D) = {s E W, E (C, D)).
//1ff,lll,, Then, have
(x, F,C, D))) < Bllgll sup vn W.e.W,(C.D)
(II j=1
I1 i. Go max [W;1| 1
[Ka,]
[d:,(W
Proof For h Hj, we have [|ww, h Imss 100 h W))l where the directions of the derivatives along the directions of ker (W,) and ker(W,). We have
Jz (x)) (y) ||W5
(10)
In addition, let be function satisfying (xx) th (21) for some Φ1 Hp (ker(W,)); where 21 + x2 for aı E ker(W;) and Ø2 ker(W,) Let Hp,-, Hp (Rd)1). Then, we have
J (o(z)u(W;=))aa
ker(WW,) (kor(W)))
(01(x1)u(W,,r) dxzdr1
ker((,)) 1 (01(2)))da))
|u 1u(Waaz)) drz
ke
|| ([<(ker(W)))) ker(Ws))
(n(Wax2)
(11)
Combining Eqs. 10 and we obtain
[
10 ())) (x) < 11W,
2 vl ||09 1 (1222 Jkoe(wW))+
(8"))
< |W5 ||a bb 122 (ker(W,)) det(W Boo(WW)) (0)h()))2dx.
16

---

Published as a conference paper at ICLR 2024
As result, we have
E
11000 ho W;) W3)
1a|S83-1
Σ
ker(W,) (eer(ws)) (0) (3)(22)
تa|S
Σ
19,85-197, 01.d, ker(W,) J 10 3 (z1) W5)(s2)
ker(W,
181Seg-1 11150/-1-181
Σ
Σ
1100 11 (kor()))
10 (k)r
CBisg 1555
det(W,,)) (W,j))
181sej l9|5;; 1-101
max |W, [22/11]
Σ
CB 1. 100 (5111112(((o0((15
Σ 1d 11 A (k))
de((W
max(1, [W, |225
| 11 H1 (Ker (
det(W
where 3 the second line of the above formula the multi index whose elements corresponding to (W)) equal to those of and other elements zero. In addition, ry tim(ker(W,)) and Co, (2m)/s//al/(s /al)!. Therefore, setting h fj. we have
G, [Kw,fflle,, S 11lyall,, ((krr(W))) (de.(W..)))1?? max(1, 1
which completes the proof of the proposition.
Proposition 10 Let (i1,..., In) E (R&y", Let un(w) E kn (,,))). (.((w)
Σ 8 (. Ti), and 7n = ||l, Ho /I [a, Then, we have
Ka, || (, W,,
1/2
Rn(x, Ft.comb (1comb(C,,)) (C,
II
Pj-1
sup W,e.,(C.D) (j=l....)
PJ-1 o W
j=1
B
h io En 1
(x, F(tr))
+ vn MIE
inf
E
sup L
h1
| H.
Proof To simplify the notation, let
1/2
G Il
Pj-1
8, =
Pí-1 o
W*
R(W)). We,
17

---

Published as a conference paper at ICLR 2024
By the reproducing property of Ho and the Cauchy-Shwartz Shwartz inequality, have
-E sup n
10
-B
Ro (x, Fi,comb(C. D))
8i (x))
sup
(Uns n 1Ho
comb (C,D i=1
n
SEF (C.D)
sup fEe Fo.mom
||nlll KW,, Kb, Ko, ... Kw; Ku, Ko, Kwi+i Kb Koum ... Kw, Korg
n
1/2
GyllKa,
|1r.ll Ho II
Pj-1 j=1 Py-1 W
sup
R,W,),,00 det We) 1/4
12
Wi44 Kou4s Koun"
Kw, Kbr. gle
Ün. | Mr |un No On
II B3
sup (C.D)) (j-1.....))
sup
n
j=1
Hi
1
| He The on -1))
sup (CED
II
sup A
(Dn (Da,)) + On:
|0 Hr
j=1
(j=1 1 !..!!
sup n (C.. j=1
1
3 II
sup E
(ūn, h1.Hi + sup
Ün 112 H. In En
1
| (H
11.
(=1...))
h 112 7a On
11.1)
sup W.W.A.DDD) (==,....)
II Bg (x,
Ü H
sup
1 (hll
j=1
for any h Fitia Moreover, again by the Cauchy- Cauchy-Schwartz inequality, have
Ün l
sup h Pi
112ll Tn 8n [
1
S E [| EE
sup hgE
122ll Yn On
2
1
H.
H1
1122 (aallmm H. Ya [i
S ByRE
sup hgg Fi
6n
where the second inequality is derived in the same manner the proof of Theorem Fi+1.L is arbitrary, we obtain the final result.
Since h
B DETAILS OF REMARK
To derive bound ||Kll bound Epis aa. a)ll by Ejoss Ga,s,a|100h) As the proof of the boundedness of || Koll, one strategy is using the Faà di Bruno formula. By the Faà di Bruno formula, we have
Σ a! II (Obo())) j=1 kg((11))Rss
g (hoo)(o))
Σ (l(((()))
Σ
18ls|al
TEp(a.8)
where p(a, 3) = {- = (kI...., .......... Ke. (1......4. (o) 1
Ej= E Ejn1kyy4
33. a elementwise, I, and k, are chosen so that each of them has only one nonzero element, such as (14)) 0..,,,,,.. 0). By counting the number of terms in the summation and calculating the coefficients the terms, we can derive a bound of K&ol- However, analytically representing the number of terms in the summation is challenging task. We admit that this strategy does not give us a tight bound. There may be a more sophisticated approach to deriving a tight bound of ||Kl]] However, the main goal of this paper is to investigate how the property of the weight matrices affects
18

---

Published as a conference paper at ICLR 2024
the generalization property. Since ||Koll does not depend on the weight matrices, if assume the structure of the network is given, the property of the weight matrices does not affect | As we stated in Section 6 investigating | || and deriving a tighter bound is future work.
C DETAILS OF REMARK 5
We first show that Gj is bounded by a constant that is independent of Jj- Since Gj depends on k,r(W)), we denote it by G3 (,(ker(W))). Let W be k-dimennsional subspace of R and (u...... Up} be an orthonormal basis of W. We consider the average ()W) on the Grassmann manifold Ga.k- For this purpose, we an orthonormal basis e1,..... : ed on Id and denote by 0, the derivative of f in the direction of 6ç. In addition, we denote dg = II E uz,;0,)0, where U5,i = (uj, ez).
Let 8 E N. Then, we have
I1fllr-www = Σ
Σ
Σ
Ca. flltzww)
la|sa
1=1 |3|=1
Da,d, Σ
Σ Ca,a,d Σ
110d flltaw
|a
18|=1
= Ds.dt
Ca.aid
Σ
1100 llli=(w)
la/ss
Da (d (2 1)*
(12)
[815a
Here, we used the Cauchy-Seaee Schwartz inequality and derive the second inequality as follows:
Σ p aj 1)
Σ U,
Σ Di
II
[8|= (3) D3S < Dad,k
Σ
(3)
Σ 10 S1
[8|=|a]
for some Da,d,k > 0 that depends on d, and k. Here DJ is the operator defined as D. = 10.
and D3/ 10,0 f12 Assume (ar Rdd | S <) is not contained in the support of f. In this case, have
Σ c fll S k-d
Σ
{(x))
(13)
13
1815
Integrating the both sides of 113 and by Theorem 2 by Rubin 2018), we have
J Σ
aa flliawaa k-d
Σ Cp.add [8|S
Od Tk JRa
fx)))
respect to the (d/22) and I is the Gamma function. In addition, dW is the integration with probability measure on Id.k and (d) is the orthogonal group Rd
where 0a 4/2
Combining with Eq. (12.. we obtain
[
I S (2. 1) k- Od σk
||
Ga.k
As result, we obtain
|| I dw
J G,WW/aw
<
Guggllgn
< Dr, Dejid (dg + (2 (2m)) d--1-dd Od;
(14)
Od,-1
19

---

Published as a conference paper at ICLR 2024
We admit that this inequality is not tight from the perspective of the dependence on 8ز, dj. and dj-1- However, surprisingly. the inequality (14) shows that the factor G5 is bounded by a constant that is independent of f, if {a E Rd ||=||| - <} is not contained in the support of fz. The assumption about {or E R2 ||س||| S E} can be satisfied if the input is transformed so that does not take the value near O.
One of the reasons for the looseness of the above bound is that we upper bounded [Iffl) by |l ( If fg can be controlled by the Gaussian, then the factor G3 does not seriously affect the bound, Indeed, let de(xr) e -= In the case of (if( + w2)1 2 (( for wi E R(W,) and w2 E R(W,) we can evaluate G3 as follows:
[0c(w)) + (2)
e 0-27"|u=1? /e(1 + (
EEER
WER
2 2272r// (c(1 + -2) dr 2T
e
0
d-2
= 2π
2x 2/1
Σ
8
2itd dr
22
0
1=1
i+(d-1)/2
2x 2
--ttt(d-1)/3
dt
C2
2T2
π
St
(=1
d-2
+dd//2 x 220 d+1 -- d/2
0-400d/2 22-
d-2
20- = - -22---22--- + d/2)
II
(15)
where a b means a/b + 1 as s 00 and d co. In addition, é; = - sin' 0d0. Thus, we have
G7 [1,sl (11 (
||
1|5i177,
S (85 + w2) (2 + || 1|3 + ||w|| )
SRIW 15) (w1)) + || 11))
$ SE.. (3) (21 + || 112 + ||
(R(WA) 15 (w1) 2 (1 + ||ا| 13)
SEC (1(1)) 2 (w2) (2 ++++++1 W 13)) (1 + ||w2 12)
"RRWY) 2o(w2) + ||22|| 12)
d 2
(1 3
+ 2
II
dj where 8y 8, 8 and d, d - d Note that since 8y 83-1 and dj 2 dy-1, Gj
becomes small as e becomes large and 8j and d, becomes large. The assumption (f,(wi + w2)l 2 (W)()))
means that f; decays slower or equal to the speed of the Gaussian in the direction of w2. Even if is chosen small to satisfy the condition, the factor I'(3, + d2/ becomes sufficiently large if sj is sufficiently large. As a result, the upper bound becomes sufficiently small if sj is sufficiently large.
Moreover, the factor G, can alleviate the dependency of |K,,, |l on dy and sy. Even if the dependence of KK on d, and 8, is exponential, since the exponents appeared in the above evaluation are -dd 1) and -s, - -) we can expect that the dependency on dj and sj is reduced to the dependency on d and 8--1-
20

---

Published as a conference paper at ICLR 2024
D DETAILS OF REMARK 6
As an example of th we can use a bump function (xx) = [[|]]]| -|]l==13=a2//0000 d²2/(0² -d²) on R for
O < a < b, where g(z) -
f(x) = c- 1/ for x > O. and f(z) for x 1 0. fo E RR ||||| S a). If the output of each layer is bounded on fir E Rd ||||| S a), then we can obtain a modified
In this case, the support of is fz E R | I b) and (xx) = for
network that is exactly the same on fxr E Rd |||||| I <a} with this bump function. If and b are large, then the support of v becomes large, which makes the -orm of & large. and the Sobolev (yy)
yll for ||=|| a and //)a becomes large. Thus, the I.2 -nomms of the derivatives of dh are expected to be large, and the Sobolev norm of t also becomes large if b small.
norm of & also becomes large. a 6 is small, then [x(2) -
E DETAILS OF REMARK
The factor |ا ir grows Ω becomes large, where is the region such that f(x) f(x) on x Ω for the network f and the modified network f. Indeed, if PL(W) = 1/(1 + [| for Sy E N, then we have
1 HL
Σ
Ca. +dd 11 (660g))l22 ())l)
=
Σ
Ca.sz,
00 12
|a|S#L
Σ
(2( 1100 110000000000000 "000099lllaa0 91122
=
Sel
where 3 is the multi index whose elements corresponding to 87-1 equals to those of and the other elements are zero. The factor || 22 becomes large as the volume of gets large. Thus, under the condition that ||0 ( large. Indeed, assume őд = =1. (xx) = for x E Ω, and Q is an interval (e.g.. ab is the bump function defined in Appendix D Then we can create new function & that satisfies [| [I:2 [L((())))))))))))))))))) for any 1, 2, ... from v/ follows. Here, w5(1) is the ith derivative of dh. For simplicity, we consider the case where Ω = [-a,a] for some a > O. For > O, we set w0xx) = for æ E [0, c). (xx) (x e) for æ E (c, oo), (xx) = 1 for E I-c, 0J. (xx) wea + c) for (-o0,
does not change, llāll becomes large Q gets
F DETAILS OF REMARK 9
In Proposition by combining with the factor Gj. the norm of bh can be canceled follows. Let Py (w) 1/(1 ||=||>)); and sy 28 We have
11 1177, (Wkrr(W,))) )) -
)ee(W)) (w5( (1 + || |1:)0 -dwz dww
1f, (2 + (w) - ker(W,))
(w)(())) (wz)) ||w + w21l3) dwn
ker((W,) ker(W,))
1 [ 11? (1 1)'
Thus, we obtain
1 e (ker ( 1ll L(kor(W,))
1| (05]ll,,-,kerr(Wy
[|f 18s,
|1 (ker(W,) (
lfglla
21

---

Published as a conference paper at ICLR 2024
If 23,1f (oof)) f3+ e.g. Ø3 and fy are the Gaussian, and dy-1 dj. then the factor || 1 G. is bounded by L.
G DETAILS OF REMARK T0
We combine our Koopman-basee approach with the existing "peeling" approach. For 1 S ( S. L, let F E:ReLU (C1) be the set of (-layer ReLU networks where the Frobenius norms of Wi...., W₁ are bounded by C1, considered by Neyshabur et al. (0115). Let Fix be the set of functions defined in the same manner as Eq. 66. except for replacing with E Hi. In addition, let FidLinj D) VS E Fia | W (C, D)}. We combine PE (Ci) and Fia,inj(C2,, D), and we define I.RLUUL (O,, C2 D) (h f he (F f F1n,ing (C2, D)}. Then, applying Theorem by Neyshabur et al. (2015), we can bound the complexity of I--layer networks using that of (L-1)- layer networks and the Frohenius norm of WL. For example, by Eq. (8) by Golowich et al. 2018 we have
(x,
(C1, C2, R.LL.. (2, < [22l22.2 (x, a (F
1:1,n))
S 2| (x, 1::.inj
pReLU.L-1
(C1, C22 D)),
where (x, F) for a vector-valued function class F defined Ee 1/n E.= (1.) and a is the ReLU. As a result, we obtain
FRELU,L (C2, C22 D)) & 2 2 W R,, 111,nn Rn (x, 1:1,5nj
PR (C1, C2, D))
2/ II
2 R., 2, 1:d, (O2, D))
==H+
Gj 11| (Ii
$ 2
I1gll Hi
II j=++1
[W 122222.2)
de; Net(W,,
W,
/=1
We can also apply other peeling approaches in the same manner as the above case.
H EXAMPLES OF CONCRETE KOOPMAN-BASH BASED BOUNDS
We show examples of our Koopman-basee bounds.
Example 3 Let g(x) = -cll=]] Let (,(w) = 1/(1 + ||w]|2ys; for 83 > dz/2. We consider shallow network fz)) = g(W x + b). Assume Z do and W is full-rank. The final nonlinear transformation in f maps the high dimensional vector on Rdh to scalar value. In this case, fa(2) = =((x b) is also the Gaussian. We have
Fing Fin s Gillllaa max (1, [
B
nn
det(W-W)1/4
Since llgll, Il.f by Eq. [5) we have
Gilllli,, [1filR(w) (l I99l Hi
do-2
~ 50 do0 do/2 -20 -
22002122200000 200-t12-o-dd//2((s do/2ITsn + do/2)
C.. II
lf
im1
As a result, we have
Rx(x, DI)
20////dd/4 -80 1/200-1/222222 20/2222222220-- 10000//40000000000000000000000 do/4 Vn
B
da-2
II
1/2
I(so + dn/2) 1/2 max (1, [[]]]
1/1/4"
Note that dim (annR(WW) = do is the dimension of the input and sp is chosen as sn > dn/2. They are independent of the structure of the network.
22

---

Published as a conference paper at ICLR 2024
Example 4 (eto(z)= (e- ..... - ||=|| Ler (ww) 1/(1+ [|]l)) 1/[1+||w11)))) for s, d We consider a shallow network f() = Using the "peeling" approach and Example 3 we obtain
(Wix + b). Assume d1 2 do. d2 = and W is full-rank. W
Rn (x, F finm C2, S 1122l22222 (x, Fin (C2, D))
d1
do-2 2
1/2
T(00 + do/2) max 1, |
S 1122l222
Σ
V
20/2-doff do/4 - 10+1/22 20 2 do/4
II 1=1
0
det(W; W; 1/4
Here, we used the inequality
(((((r))))) )
Rm(x, F)
E
sup
Σ (T))
sup
Σ
n
FEF i=1
n
SEF
sup
d
Σ (((((1))),)
LE
sup fEF
Σ s
n
sf
71
fEF
72
j=l
Σ 8:
(((aa))
sup
JEF
j=1
i=1
where (f(zi)) is the jth element in the vector f(ra). In this case, the bound depends on d2 linearly.
I INJECTIVITY OF W,
The operator W, defined in Subsection 4.3.1 is injective. Indeed, assume (Wiæ, P1.) = (W1y, Piy) for x, y E RR Then, we have x - y E ker (.). ) On the other hand, we have (r y) = 0. Since y E (W)) we have y Pi (z v) = 0. The case of j > 2 is the same.
J EXPERIMENTAL DETAILS AND ADDITIONAL. EXPERIMENTAL RESULTS
We explain details of experiments in Section 5 and show additional experimental results. All the experiments were executed with Python 3.9 and TensorFlow 2.6.
J.1 VALIDITY OF THE BOUND (SYNTHETIC DATA)
We constructed network fo(x) WWW2 b1) + b2). where W1 E 33x3 W2 E Rx b E R3, by E RR, 0 = (W1, b1, b2), ozz) = ((1 + a)x + (1 a)z g(x) e |>11 Here, erf is the Gaussian error function, and is smooth version of Leaky ReLU proposed by Biswas et al. (2022). We set a = =.5.5 0.5. For training the network, we used n = 1000 samples v, (i 1,... 1000) drawn independently from the normal distribution with mean 0 and standard deviation 1. The weight matrices are initialized by Kaiming Initialization (He et al. 2013). and we used the SGD for the optimizer. In addition, we set the error function as (o y) [fa( - y12, and added the regularization term 0.01 det W,) + 10 10 [IW We added this regularization term since, according to our bound, both the determinant and the operator norm of W, should be small for achieving small generalization error. The generaliza- tion error here means [E(1 (Ir, ((x)) 1/n > (x ((x))), which compared to our bound
/2, and
O1L || /(det(W 2/9) in Figure (a). Here, we set 8j (d, + 0.1)/2.
J.2 VALIDITY OF THE BOUND (MNIST)
We constructed network fa(x) layers, where W1 E R 1044xx784 W. E R 2048x 1024 W, E R 22488x2446 Wa E R 100x2008 by E R 1024 by 2004 by 2204 b, R 0 (W1, by W2, by, Ws, by. Wa, b1), is the same function as Section [.I] and g is the softmax. See Remark [ for the validity of our bound for the case where g is the softmax. For training the network, used only 1000 samples create
b1) + b2) + b2) + by) with dense
23

---

Published as a conference paper at ICLR 2024
0.7
m
0.6
[cos
0.4
With Regularization
Without Hegularization
0.3
400
800
1200
1600
Epochs
Figure 2: Behavior the value cos( Here, 0 the maximum value of the angles between output of the second layer and the directions of singular vectors of W3 associated with the singular values that are larger than 0.1.
10
[a.) Ina.
faj== Fha.
j-1 1
==1
4 (multiplied
2
(multiplied by
400
800
1200
1600
400
800
1200
1600
Epochs
Epochs
Figure 3: The ratio ridj = mmg/na of singular values (condition number) of weight matrices for layers j = 1, 4. (Right) Without regularization (Left) With the regularization based on our bound.
situation where the model is hard generalize. We consider the regularization term X W ++ /2/ det(T + W,W,), where A = X = 0.01 to make both the norm and the determinant of W; small (thus, makes our bound small). Based on the observation in the last part of Subsection 4.4 set the regularization term for only j = 1, 2. The weight matrices are initialized by the orthogonal initialization for j 1,2 2 and by the samples from a truncated normal distribution for j 3, and we used Adam (Kingma & Ba 2015) for the optimizer. In addition, we set the eтror function as the categorical cross- cross-entropy loss.
J.2.1
TRANSFORMATION SIGNALS LOWER LAYERS
We also investigated the transformation by lower layers, as we stated in the last part of Subsee- tion 4.4 We computed cos(f)), where is the maximum value of the angles between the output of the second layer and the directions of singular vectors of W3 associated with the singular values that larger than 0.1. The results are illustrated in Figure We can see that with the regularization based on our bound, as the test accuracy grows, the value cos(()) also grows. This result means that the signals turn the directions of the singular vectors of the subsequent weight matrix associ- ated with large singular values. That makes the extraction of information from the signals in higher layers easier. On the other hand, without the regularization, neither the test accuracy nor the value cos(0) do not become large after a sufficiently long learning process (see also Figure I (b)). The results in Figures (b) and are obtained by three independent runs.
J.3 SINGULAR VALUES OF THE WEIGHT MATRICES
We constructed an AlexNet Krizhevsky et al. 2012 where the ReLU activation function replaced by the smooth version of Leaky ReLU (a Section J.I) to meet our setting. For training the network, we used n = 50000 samples and used the Adam optimizer. We set the error function as the categorical cross-entropy loss. We show the test accuracy through the learning process in Figure 4 In addition to the AlexNet, we also computed the ratio ra, of the largest and the smallest singular values (condition number) of the weight matrices for the network used in Section [.2 Since the
24

---

Published as a conference paper at ICLR 2024
Test Accuracy
0.7
0.6
With Regularization
Without Hegularization
0.5
x0
6
9
1.2x
Iterations
Figure 4: Test accuracy of AlexNet traind by CIFAR-10 with and without regularization.
With Regularization
With Regularization
Without Regularization
2.0
Without Regularization
2.0
Train Loss
1.5
Test
1.0
1.0
0.5
3
6 10
9
122 10
3x 104
6x100
9x
122 x2x
Iterations
Iterations
Figure 5: Test and train loss of AlexNet trained by CIFAR-10 with and without regularization. (Right) Test loss (Left) Train loss.
behavior of the singular values of W3 was unstable and did not have clear patterns, we only show the result for j = 1, 2, 4 in 3 We scaled the values for j = for readability. In the case of the AlexNet, the behavior of singular values of each weight matrix
different depending on the layer. However, in the case of the network in Section J.2 without the regularization, the condition number rd, stagnates for j 1, 2, through the learning process, and the test accuracy also stagnates. On the other hand, with the regularization based on our bound, rd,j becomes small for j = 1, as the learning process proceeds by virtue of the regularization. We can also see that rd.j grows for as the learning process proceeds, which makes the angle 0 in Figure large. As discussed in the last part Subsection 4.4 we can conclude that the regularization transforms the signals in lower layers (j - 1, 2) and makes it easier for them to be extracted in higher layers (j 4), and the test accuracy becomes higher than the case without the regularization. The results in Figures (c), and are obtained by three independent runs.
J.4 VALIDITY OF THE BOUND (CIFAR-10)
We used the same network and the same dataset Appendix J.3 and observed the generalization property with and without a regularization based on our result. We consider the regularization term >2/||00.1/++ + W. W Il. where X; 0.1 and X₂ 0.001 to make both the largest and the smallest singular values of W, small (thus, makes our bound small). Since the AlexNet is composed of convolutional layers, represented the convolutional layers matrices. For the convolution
X [W]|- +
EE E/=1 fk-i.--5Tk. with convolutional filter F [fr.g]. we can construct tensor Wi,.k.I fR-i115. if or out of the bound of the index of the filter, then we fú, 0. We can combine the indices (i,j) and (ks, 1) in W, and obtain a matrix W, that represents the convolution. Note that since the dimension of W, is large, setting a regularization term with the determinant of W, can cause numerical overflows. Thus, we set ||0.01/ + W W,ll instead of its determinant in the same manner Appendix J.2 Based on the observation in the last part of Subsection 4.4 we set the regularization term for only j = 1, Figure shows the test accuracy obtained with and without the regularization. The behavior of the accuracy obtained with and without the regularization similar. Figure 5 shows the test and train loss. We can see that without the regularization, although the train loss becomes small, the test loss becomes large the iteration proceeds. On the other hand,
25

---

Published as a conference paper at ICLR 2024
with the regularization, the train loss becomes small, and the test loss does not become so large as the case without the regularization.
K NORM OF THE SOBOLEV SPACE
Let p(w) = (1 + [[ with s E N. We can represent the Sobolev norm Il using the derivatives of if N. Indeed, we have
I1 = Jpcd (1( + (p = Jee 1f(W))
Σ
1
==
= =Jn- 12(w))
wj
dw
1=0
f=1
= 1f(w))
Σ
(wo )
Σ
s!
If(w)
a
(s la Ma! Jun
0m
la|=i
la|sa
s!
Σ
(2 (1 M1
(s - lal)!a!
Sa
26


Reviews:
[{"review_id": "lZtZR64jBB", "reviewer": "Reviewer_i9ex", "summary": "This paper provide an operator-theoretic approach to analyzing networks. They proposed a novel bound for generalization of neural networks using Koopman operators and Rademacher complexity, which reveals a new aspect of neural networks.", "questions": "See above", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper proposed a new complexity bound that involves both the norm and determinant of the weight matrices. This bound is particularly useful when the condition numbers of the weight matrices are small. \n2.\tIt provides a new perspective on why networks with high-rank weights generalize well. By combining our bound with existing bounds, we can obtain a more comprehensive description of the role of each layer in the network. \n3.\tThis paper presented an operator-theoretic approach to analyzing networks, using Koopman operators to derive the determinant term in our bound. This approach offers a new way to analyze the generalization performance of neural networks.", "weaknesses": "This paper gives the generalization error bound of neural networks from a novel perspective which sounds very interesting and introduces new tools to generalization analysis. But since I'm not familiar with dynamic-based Koopman operators, I have some concerns that I'd like to see answered by the author.\n\n1. As the author said, Efficient learning algorithms have been proposed by describing the learning dynamics of the parameters of neural networks by Koopman operators. It seems that the author represents the composition structure of neural networks using Koopman operators, and then uses the complexity method to give an upper bound. My question is, dynamics sound algorithm-related, while complexity is algorithm-independent, so what's the point of using Koopman operators here.\n\n2. Looking at the entire proof, the conclusion of this paper seems to be highly related to the hypothesis of RKHS. My intuitive feeling is that the conclusion of this paper mainly comes from the RKHS assumption, and whether the neural network is abstracted into Koopman operators has little relevance. I hope the author can explain the relationship between Koopman operators, RKHS and the final conclusion and give an idea of what kind of these techniques/assumptions play a role in the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YnNhrJt8wB", "reviewer": "Reviewer_K7E7", "summary": "This paper establishes a new generalization bound for neural networks based on the Koopman operator. To be specific, the authors first represent the network by the product of Koopman operators. Then, new upper bounds of Rademacher complexity are derived for invertible, injective, and non-injective weight matrices, respectively. Furthermore, the Koopman-based bound is combined with other generalization bounds such that both high and low layers can be sharply bounded. Finally, numerical results validate the effectiveness of the regularization induced by the Koopman-based bound, and the different behaviors of singular values of the weight matrix for each layer are also observed.", "questions": "Please refer to Weakness", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The proposed generalization bound is sharp and fills the theoretical gap. Specifically, benefiting from the denominator induced by the Koopman operator, the generalization bound can be sharp when the condition number of the weight matrix is small. What’s more, if the weight matrices are orthogonal, the bound reduces to 1 and is independent of the width of the network. This result explains the generalization ability of neural networks when the weight matrices are full-rank.  By contrast, existing results either depend on the $(p, q)$ matrix norm, which scales by the order of $d^{1/p}$ for a $d \\times d$ matrix, or become loose when faced with high-rank weight matrices.\n- The authors validate the proposed bound with the help of numerical results. On one hand, experimental results on both regression and classification validate the proposed generalization bound. On the other hand, the different behaviors of singular values of the weight matrix for each layer are also observed for AlexNet on the CIFAR dataset.\n- This paper is well organized, which makes it easy to understand.", "weaknesses": "- The authors mainly consider the neural networks with dense layers. I wonder whether these theoretical results can generalize well to neural networks with other structures such as convolution. A simple explanation is recommended.\n- The experimental results on MNIST validate the effectiveness of the induced regularization term. Can it boost model performance on datasets with larger scales such as CIFAR?\n- Besides, there are some typos. For example, \n\t- In the introduction part, \"depth of the network.Another approach\" should be \"depth of the network. Another approach\". \n\t- In the introduction part, the third paragraph has an extra indent.\n\t- In Table 1, a larger line spacing is recommended.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bo7ljLaIhm", "reviewer": "Reviewer_ebFP", "summary": "This paper proves generalization bounds for deep neural networks by establishing that they belong to the RHKS of sobolev spaces of a given order: in the most basic result (theorem 1 and proposition 5), a very concrete bound is shown which under the assumption that the transformations associated to the weights in each layer are invertible. The bound scales as the product of the $s$th power of the operator norms of the weights divided by the square root of their determinant. There is also a factor  $\\|K_{\\sigma}\\|_H$ which depends on the activation function. Furthermore, follow-up theorems extend the results to the situation where the weight matrices are not invertible but only injective: in this case, a similar bound holds with the determinant of the weight replaced by the square root of the determinant of $W^{adj} W$, but at the cost of a product of factors $G_j$, which depend on the isotropy of the networks' function. Finally, further generalizations are provided which completely circumvent the need for injectivity by considering an augmented version of the network where each layer outputs a copy of its input (in addition to outputting the usual output). It is also shown that the bounds can be combined with existing bounds by employing one method for some of the layers and another for the remaining layers. Experiments demonstrate that imposing regularization inspired from the bounds provided improves performance.", "questions": "What is the norm of the bump functions $\\phi_j$ assumed to satisfy in Proposition 10? Are they constant, or equal to 1? How can this be achieved without additional dependence on the ambient dimension at all? Could you provide a concrete example? \n\nCould you address the points mentioned in the weaknesses, especially the control over the quantity $G_j$ (from lemma 8)and avoiding dimensional dependence when summing over multi-indices in Sobolev norms? \n\nCould you write a complete and detailed version of your result for a fully concrete example where the loss function is either the cross entropy loss or the square loss and the activation is component-wise and fully explicit (e.g. the smooth version of leaky relu), without using any undefined quantity such as $G_j$, $f_j$ or even $\\phi_j$ (you can choose a concrete $\\phi_j$ if necessary, and show that the corresponding factors in the bound are bounded by the absolute constants)?  How can you concretely control the quantity $G_j$ in the case where we have a two-layer neural network with a very wide hidden layer?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This is an **extremely interesting direction** which, to the best of my knowledge, is underexplored. The results presented in this paper have the potential to be of great interest to the community for further research, since it approaches the problem from an entirely different perspective: instead of controlling the function class capacity through norms of the weights or number of parameters, properties of the learned functions in terms of their smoothness over the inputs are used instead. This may really be a key to more a more satisfying approach to generalization bounds in the overparametrized setting.\n\n\nGiven the great potential this work has, I am quite disappointed that the treatment offered doesn't more thoroughly study in a reader-friendly way the concrete implications in terms of lack of architectural dependencies for concrete networks. Fortunately, ICLR allows authors to upload a new pdf with very substantial revisions, so I am looking forward to that and may increase my score to 8 if my doubts are all thoroughly resolved.", "weaknesses": "The writing is quite crisp and abstract, sometimes to the detriment of precision. I think the results make sense in that bounds for the norms of the neural network are indeed given, but the interpretation in terms of asymptotics and the lack of dependence on the number of parameters don't fully make sense due to the presence of obscure quantities with unclear asymptotic behavior. \n\n To be honest, I am **not completely convinced of the correctness** of the final conclusions from a mathematical standpoint. In particular, the notations used by the authors rely a lot on Sobolev norms which are then absorbed into the O notations as if they were constants, and this process is not performed nearly carefully enough to ensure that no additional dependency on the number of parameters appears.  Here are a few examples where there are imprecisions which must be very thoroughly cleared up during the rebuttal for me to keep my score or increase it: \n\n1 (may be fixable): Proposition 5 includes factors of $\\|K_{\\sigma}\\|$. According to the authors, such factors can be controlled by Proposition 1, which seems to be the justification for absorbing those factors into the $O$ notation in equation (1). I can sort of believe that the final conclusion, but note that the proof given is at best sloppy: each term in the sum over multi-indices with components living in a set of cardinality equal to the layer width is bounded individually by a term $C_{\\beta,\\gamma,\\delta}$, thus, this analysis cannot be used directly to obtain a result truly of the order claimed in equation (1), since the use of this proposition would introduce **an additional dependency on the width of the network**. Now, I agree that this is probably avoidable by using a **component-wise** activation function, which would make most of the terms cancel in the sum,  but this assumption is not even clearly stated, nor is it used anywhere. There are many missing details for the results to truly qualify as applicable to concrete neural networks.\n\n\n2. (more serious) I am not convinced by the applicability of the result in the case of injective but non bijective maps: the bound contains the factors $G_j$, which depend on the \"the isotropy of $f_j$\", with $f_j$ only definable via the composition of the network's functions. It is absolutely unclear to what extent these quantities can be considered as constants. Even in the extremely hypothetical case where $G_j\\leq G$ for some absolute constant $G$, there is still an exponential dependence in the depth of the network which is not explicitly written in the $O$ notation. In addition, it doesn't seem to be the case that the $G_j$ can be controlled properly either. In page 6, below lemma 8, the authors attempt to reassure the readers by giving an example where $G_j$ can be bounded by $(4/\\pi)^{dim(R(W_j)^\\top)/4}$. Note that even in that case, **this term introduces intractable, exponential dependence** in the architectural parameters $L$ (the depth) and $dim(R(W_j)^\\top)$ (which is closely related to the width). \n\n\n3. Similarly, the argument in appendix B is a bit vague and certainly appears to introduce dimensional dependence. \n\n\n\n\n\n\n\n==============Minor comments (maths)=======\n\n\nIn general, it would be nice to make the paper more reader-friendly by adding more lines in the calculations for readers not familiar with the techniques used. For instance, it would be nice to remind the readers in a separate theorem of the Faa di Bruno formula mentioned on page 13 at the beginning of the proof of Proposition 1. \n\n\nFor instance, in the proof of Theorem 2 on page 14, the fact that the $s_i$s are Rademacher variables is not even explicitly stated. \n\nThe implication of Assumption 2 should be explained in terms of concrete assumptions about the network and the inputs to the network. I know that later theorems rely on a concrete formula for $p(\\omega)$ which appears to make this assumption hold trivially, but this absolutely should be explained explicitly. It also seems like not choosing the $p(\\cdot)$ earlier on \n\nThe spaces $R(W_j)$, which refer to the column spaces of $W_j$, should also be defined somewhere. The same applies to the non-standard notation $W^{-\\star}$, which refers to the inverse of the adjoint of $W^{*}$. It also seems a little strange to use conjugate transpose notation (without introduction or justification) when all the weights are presumably real). \n\nIn addition, some of the basic notation for Fourier analysis and the relevant inner products absolutely should be included. Note that various authors use different constants in the definition of the Fourier transform, and it is not clearly stated in this paper which convention is used. I deduced from the first line of the proof of Lemma 3 on page 13 the convention used is the one where there is no constant factor in the definition of the Fourier transform. Similarly, the second equality on the same line takes some time to digest without additional details. \n\nSimilarly, the fact that the Sobolev norms are both equal to sums over all multi-indices of the relevant derivatives, and to the RKHS norm defined at the bottom of page 3 should be explained in much more detail. \n\nAlso, the main paper and the appendix are too heavily reliant on each other, it is better practice to make the appendix fully mathematically self-contained, which would imply at a minimum the following reminders to the readers: the definition of $J\\sigma^{-1}$ on page 13, a reminder of the definitions of $F_{inj}$ on page 14 in the proof of Theorem 6, a better separation go Proposition 11 from proposition 10 on page 16 (since it actually refers to a completely different setting), and the definition of $G_j$ at the beginning of page 15. \n\n\n\n\n\n============minor typos/ language=======\n\n\nFourth line of the introduction: \"a large number of parameters make the complexity\" should be \"a large number of parameters makes the complexity\" \n\nat the beginning of remark 1, it would be better to write \" Let $g$ be a smooth function which doesn't decay at infinity (e.g., a sigmoid), ...\" \n\nIn the beginning of Section 4.3, \"as a result $h\\circ W_j$ does not contained in...\" should be \"as a result $h\\circ W_j$ is not contained in...\"\n\nSection 4.3.2 \"We only need...., not whole $W_j$\" should be \"We only need...., not the whole of  $W_j$\"\n\n\nJust before the second equation in Section 4.4 \" set of all functions which has\" ==> \"set of all functions which have\" \n\nPage 9 \"we constructed a network and learned it\" ===> \"trained\" \n\n\nTop of Page 18 in Appendix B, there shouldn't be a capital letter at  \"then By\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)