# Koopman-based generalization bound:
New aspect for full-rank weights

Yuka Hashimoto1,2 Sho Sonoda2 Isao Ishikawa3,2 Atsushi Nitanda4,2 Taiji
Suzuki5,2
1\. NTT Network Service Systems Laboratories, NTT Corporation, Tokyo, Japan
2\. Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
3\. Center for Data Science, Ehime University, Ehime, Japan
4\. Faculty of Computer Science and Systems Engineering, Kyushu Institute of
Technology, Fukuoka, Japan
5\. Graduate School of Information Science and Technology, The University of
Tokyo, Tokyo, Japan

###### 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.

##  1 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 complexity of networks (Bartlett & Mendelson,
2002; Mohri et al., 2018). Intuitively, a large number of parameters make the
complexity and generalization error large. This intuition has been studied,
for example, based on a classical VC-dimension theory (Harvey et al., 2017;
Anthony & Bartlett, 2009). However, for neural networks, small generalization
error can be achieved even in over-parameterized regimes (Novak et al., 2018;
Neyshabur et al., 2019). To explain this behavior, norm-based bounds have been
investigated (Neyshabur et al., 2015; Bartlett et al., 2017; Golowich et al.,
2018; Neyshabur et al., 2018; Wei & Ma, 2019, 2020; Li et al., 2021; Ju et
al., 2022; Weinan E et al., 2022). These bounds do not depend on the number of
parameters explicitly. However, they are typically described by the $(p,q)$
norms of the weight matrices, and if the norms are large, these bounds grow
exponentially with respect to the depth of the network.Another approach to
tackle over-parameterized networks is a compression-based approach (Arora et
al., 2018; Suzuki et al., 2020). These bounds explain the generalization of
networks by investigating how much the networks can be compressed. The bounds
get small as the ranks of the weight matrices become small. However, low-
rankness is not the only reason for generalization. Goldblum et 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-based bounds are not always tight.

In this paper, we derive a 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 $L$ be the number of layers, $d_{j}$ be the width of the $j$th
layer, and $n$ be the number of samples. For $j=1,\ldots,L$, let
$W_{j}\in\mathbb{R}^{d_{j}\times d_{j-1}}$ be the weight matrix. Let
$s_{j}>d_{j}/2$ be the real number describing the smoothness of a function
space where the Koopman operator is defined. Our results are summarized as
follows, where $\|\cdot\|$ is the operator norm:

$\displaystyle\mbox{Rademacher complexity}\leq
O\bigg{(}\frac{1}{\sqrt{n}}\prod_{j=1}^{L}\frac{\|W_{j}\|^{s_{j-1}}}{\operatorname{det}(W_{j}^{*}W_{j})^{1/4}}\bigg{)}.$
(1)

Surprisingly, the determinant factor tells us that if the singular values of
$W_{j}$ are large, the bound gets small. It is tight when the condition number
of $W_{j}$, i.e., the ratio of the largest and the smallest singular values,
is small, especially, when $W_{j}$ is orthogonal. In this case, the factor
$\|W_{j}\|^{s_{j-1}}/\operatorname{det}(W_{j}^{*}W_{j})^{1/4}$ reduces to $1$.
We can interpret that $W_{j}$ transforms signals in certain directions, 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 a new perspective, we can combine our bound with
existing bounds. In other words, our bound can be a 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
obtain a tight bound that takes the role of each layer into account.

The determinant factor comes from Koopman operators. Koopman operator is a
linear operator defined by the composition of functions. It has been
investigated for analyzing dynamical systems and time-series data generated
from dynamical systems (Koopman, 1931; Budišić et al., 2012; Kawahara, 2016;
Ishikawa et al., 2018; Klus et al., 2020; Hashimoto et al., 2020; Giannakis &
Das, 2020; Brunton et al., 2022). Its theoretical aspects also have been
studied (Das et al., 2021; Ikeda et al., 2022a, b; Ishikawa, 2023).
Connections between Koopman operators and neural networks have also been
discussed. 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, 2020). Lusch et al.
(2017) applied neural networks to identifying eigenfunctions of Koopman
operators to extract features of dynamical systems. Konishi & Kawahara (2023)
applied Koopman operators to analyze equilibrium models. On the other hand, in
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 are small. Especially,
it justifies the generalization property of existing networks with orthogonal
weight matrices. It also provides a new perspective about why the networks
with high-rank weights generalize well (Section 2, the paragraph after
Proposition 5, and Remark 6).

  * •

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-theoretic approach to analyzing networks. We use
Koopman operators to derive the determinant term in our bound (Subsection 3.4
and Subsection 4.1).

We emphasize that our operator-theoretic approach reveals a new aspect of
neural networks.

##  2 Related works

##### Norm-based bounds

Generalization bounds based on the norm of $W_{j}$ have been investigated in
previous studies. These bounds are described typically by the $(p,q)$ matrix
norm $\|W_{j}\|_{p,q}$ of $W_{j}$ (see the upper part of Table 1). 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 $d$ identity matrix is $d^{1/p}$. This
situation is totally different from our case, where the factor is reduced to
$1$ if the weight matrices are orthogonal. We can see our bound is described
by the spectral property of the weight matrices and tight when the condition
number of $W_{j}$ is small. Bartlett et al. (2017); Wei & Ma (2020); Ju et al.
(2022) showed bounds with reference matrices $A_{j}$ and $B_{j}$. 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 a bound described by
$|\prod_{j=1}^{L}\|W_{j}\|-1|$, the discrepancy between the largest singular
value of $W_{j}$ and $1$. It is motivated by the covering number
$c_{\mathcal{X}}$ of the input space $\mathcal{X}$ and a diameter
$\gamma_{\mathbf{x}}$ of the covering set, which depends on the input samples
$\mathbf{x}=(x_{1},\ldots,x_{n})$. This bound somewhat describes the spectral
properties of $W_{j}$. However, they only focus on the largest singular values
of $W_{j}$ 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_{j}$ differ from its largest singular value.

##### Compression-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 $\hat{r}$ induced by compression (see the
middle part of Table 1). Arora et al. (2018) introduced layer cushion
$\mu_{j}$ and interlayer cushion $\mu_{j\rightarrow}$ for layer $j$, which
tends to be small if the rank of $W_{j}$ is small. They also observed that
noise is filtered by the weight matrices whose stable ranks are small. Suzuki
et 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 et 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 is 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.

Table 1: Comparison of our bound to existing bounds.

Authors | Rate | Type
---|---|---
Neyshabur et al. (2015) | $\frac{2^{L}\prod_{j=1}^{L}\|W_{j}\|_{2,2}}{\sqrt{n}}$ | Norm-based
Neyshabur et al. (2018) | $\frac{L\max_{j}d_{j}\prod_{j=1}^{L}\|W_{j}\|}{\sqrt{n}}\Big{(}\sum_{j=1}^{L}\frac{\|W_{j}\|_{2,2}^{2}}{\|W_{j}\|^{2}}\Big{)}^{1/2}$
Golowich et al. (2018) | $\Big{(}\prod_{j=1}^{L}\|W_{j}\|_{2,2}\Big{)}\min\bigg{\\{}\frac{1}{n^{1/4}},\sqrt{\frac{L}{n}}\bigg{\\}}$
Bartlett et al. (2017) | $\frac{\prod_{j=1}^{L}\|W_{j}\|}{\sqrt{n}}\bigg{(}\sum_{j=1}^{L}\frac{\|W_{j}^{T}-A_{j}^{T}\|_{2,1}^{2/3}}{\|W_{j}\|^{2/3}}\bigg{)}^{3/2}$
Wei & Ma (2020) | $\frac{(\sum_{j=1}^{L}\kappa_{j}^{2/3}\min\\{L^{1/2}\|W_{j}-A_{j}\|_{2,2},\|W_{j}-B_{j}\|_{1,1}\\}^{2/3})^{3/2}}{\sqrt{n}}$
Ju et al. (2022) | $\frac{\sum_{j=1}^{L}\theta_{j}\|W_{j}-A_{j}\|_{2,2}}{\sqrt{n}}$
Li et al. (2021) | $\|\mathbf{x}\||\prod_{j=1}^{L}\|W_{j}\|-1|+\gamma_{\mathbf{x}}+\sqrt{\frac{c_{\mathcal{X}}}{n}}$
Arora et al. (2018) | $\hat{r}+\frac{L\max_{i}\|f(x_{i})\|}{\hat{r}\sqrt{n}}\Big{(}\sum_{j=1}^{L}\frac{1}{\mu_{j}^{2}\mu_{j\rightarrow}^{2}}\Big{)}^{1/2}$ | Compression
Suzuki et al. (2020) | $\frac{\hat{r}}{\sqrt{n}}+\sqrt{\frac{L}{n}}\big{(}\sum_{j=1}^{L}\tilde{r}_{j}(\tilde{d}_{j-1}+\tilde{d}_{j})\big{)}^{1/2}$
Ours | $\frac{1}{\sqrt{n}}\prod_{j=1}^{L}\frac{\|W_{j}\|^{s_{j-1}}}{\operatorname{det}(W_{j}^{*}W_{j})^{1/4}}$ | Operator-theoretic

$\kappa_{j}$ and $\theta_{j}$ are determined by the Jacobian and Hessian of
the network $f$ with respect to the $j$th layer and $W_{j}$, respectively.
$\tilde{r}_{j}$ and $\tilde{d}_{j}$ are the rank and dimension of the $j$th
weight matrices for the compressed network.

##  3 Preliminaries

###  3.1 Notation and structure of the paper

For a linear operator $W$ on a Hilbert space, its range and kernel are denoted
by $\mathcal{R}(W)$ and $\operatorname{ker}(W)$, respectively. Its operator
norm is denoted by $\|W\|$. For a function $p\in L^{\infty}(\mathbb{R}^{d})$,
its $L^{\infty}$-norm is denoted by $\|p\|_{\infty}$. For a function $h$ on
$\mathbb{R}^{d}$ and a subset $\mathcal{S}$ of $\mathbb{R}^{d}$, the
restriction of $h$ on $\mathcal{S}$ is denoted by $h|_{S}$. All the proofs are
in Appendix A.

###  3.2 Koopman operator

Let $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ be function spaces on
$\mathbb{R}^{d_{1}}$ and $\mathbb{R}^{d_{2}}$. For a function
$f:\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}$, we define the Koopman operator
from $\mathcal{F}_{2}$ to $\mathcal{F}_{1}$ by the composition as follows. Let
$\mathcal{D}_{f}=\\{g\in\mathcal{F}_{2}\,\mid\,g\circ f\in\mathcal{F}_{1}\\}$.
The Koopman operator $K_{f}$ from $\mathcal{F}_{2}$ to $\mathcal{F}_{1}$ with
respect to $f$ is defined as $K_{f}g=g\circ f$ for $g\in\mathcal{D}_{f}$.

###  3.3 Reproducing kernel Hilbert space (RKHS)

As function spaces, we consider RKHSs. Let $p$ be a density function of a
positive finite measure on $\mathbb{R}^{d}$. Let
$H_{p}(\mathbb{R}^{d})=\\{f\in
L^{2}(\mathbb{R}^{d})\,\mid\,\hat{f}/\sqrt{p}\in L^{2}(\mathbb{R}^{d})\\}$ be
the Hilbert space equipped with the inner product $\left\langle
f,g\right\rangle_{H_{p}(\mathbb{R}^{d})}=\int_{\mathbb{R}^{d}}\hat{f}(\omega)\hat{g}(\omega)/p(\omega)\mathrm{d}\omega$.
Here, for $f\in L^{2}(\mathbb{R}^{d})$, $\hat{f}$ is the Fourier transform of
$f$. We can see that
$k_{p}(x,y):=\int_{\mathbb{R}^{d}}\mathrm{e}^{\mathrm{i}(x-y)\cdot\omega}p(\omega)\mathrm{d}\omega$
is the reproducing kernel of $H_{p}(\mathbb{R}^{d})$, i.e., $\left\langle
k_{p}(\cdot,x),f\right\rangle_{H_{p}(\mathbb{R}^{d})}=f(x)$ for $f\in
H_{p}(\mathbb{R}^{d})$. Note that since $H_{p}(\mathbb{R}^{d})\subseteq
L^{2}(\mathbb{R}^{d})$, the value of functions in $H_{p}(\mathbb{R}^{d})$
vanishes at infinity.

One advantage of focusing on RKHSs is 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.12)).

###### Example 1

Set $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $s>d/2$. Then,
$H_{p}(\mathbb{R}^{d})$ is the Sobolev space $W^{s,2}(\mathbb{R}^{d})$ of
order $s$. Here, $\|\omega\|$ is the Euclidean norm of
$\omega\in\mathbb{R}^{d}$.

###  3.4 Problem setting

In this paper, we consider an $L$-layer deep neural network. Let $d_{0}$ be
the dimension of the input space. For $j=1,\ldots,L$, we set the width as
$d_{j}$, let $W_{j}:\mathbb{R}^{d_{j-1}}\to\mathbb{R}^{d_{j}}$ be a linear
operator, let $b_{j}:\mathbb{R}^{d_{j}}\to\mathbb{R}^{d_{j}}$ be a shift
operator defined as $x\mapsto x+{a}_{j}$ with a bias
${a}_{j}\in\mathbb{R}^{d_{j}}$, and let
$\sigma_{j}:\mathbb{R}^{d_{j}}\to\mathbb{R}^{d_{j}}$ be a nonlinear activation
function. In addition, let $g:\mathbb{R}^{d_{L}}\to\mathbb{C}$ be a nonlinear
transformation in the final layer. We consider a network $f$ defined as

$f=g\circ b_{L}\circ W_{L}\circ\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}.$ (2)

Typically, we regard that $W_{1}$ is composed by $b_{1}$, $\sigma_{1}$ 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
$j=0,\ldots,L$, let $p_{j}$ be a density function of a finite positive measure
on $\mathbb{R}^{d_{j}}$. The network $f$ is described by the Koopman operators
$K_{W_{j}}:H_{p_{j}}(\mathbb{R}^{d_{j}})\to
H_{p_{j-1}}(\mathbb{R}^{d_{j-1}})$,
$K_{b_{j}},K_{\sigma_{j}}:H_{p_{j}}(\mathbb{R}^{d_{j}})\to
H_{p_{j}}(\mathbb{R}^{d_{j}})$ as

$f=K_{W_{1}}K_{b_{1}}K_{\sigma_{1}}\cdots
K_{W_{L-1}}K_{b_{L-1}}K_{\sigma_{L-1}}K_{W_{L}}K_{b_{L}}g.$

The final nonlinear transformation $g$ is first provided. Then, $g$ is
composed by $b_{L}$ and $W_{L}$, i.e., the corresponding Koopman operator acts
on $g$. We sequentially apply the Koopman operators corresponding to the
$(L-1)$th layer, $(L-2)$th layer, and so on. Finally, we get the whole network
$f$. By representing the network using the product of Koopman operators, we
can bound the Rademacher complexity with the product of the norms of the
Koopman operators.

To simplify the notation, we denote $H_{p_{j}}(\mathbb{R}^{d_{j}})$ by
$H_{j}$. We impose the following assumptions.

###### Assumption 1

The final nonlinear transformation $g$ is contained in $H_{L}$, and
$K_{\sigma_{j}}$ is bounded.

We denote by $F$ the set of all functions in the form of (2) with Assumption
1. As for the assumption of $g$, let $g(x)=\mathrm{e}^{-\|x\|^{2}}$ and
$p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $x,\omega\in\mathbb{R}^{d}$ and
$s>d/2$. Then, $g\in H_{p}(\mathbb{R}^{d})$.

###### Remark 1

Let $g$ be smooth but does not decay at infinity, e.g., sigmoid. Although
$H_{p}(\mathbb{R}^{d})$ does not contain $g$, we can construct a function
$\tilde{g}\in H_{p}(\mathbb{R}^{d})$ such that $\tilde{g}(x)=g(x)$ for $x$ in
a sufficiently large compact region. Thus, we can replace $g$ by $\tilde{g}$
in practical cases. See Remark 12 for more details.

For the activation function, we have the following proposition (c.f. Sawano
(2018, Theorem 4.46)).

###### Proposition 2

Let $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $\omega\in\mathbb{R}^{d}$
$s\in\mathbb{N}$, and $s>d/2$. If the activation function $\sigma$ has the
following properties, then $K_{\sigma}:H_{p}(\mathbb{R}^{d})\to
H_{p}(\mathbb{R}^{d})$ is bounded.

  * •

$\sigma$ is $s$-times differentiable and its derivative
$\partial^{\alpha}\sigma$ is bounded for any multi-index
$\alpha\in\\{(\alpha_{1},\ldots,\alpha_{d})\,\mid\,\sum_{j=1}^{d}\alpha_{j}\leq
s\\}$.

  * •

$\sigma$ is bi-Lipschitz, i.e., $\sigma$ is bijective and both $\sigma$ and
$\sigma^{-1}$ are Lipschitz continuous.

###### Example 2

We can choose $\sigma$ as a 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 tanh in Remark 15.

###### Example 3

We have
$\|K_{\sigma}\|\leq\|\operatorname{det}(J\sigma^{-1})\|_{\infty}\max\\{1,\|\partial_{1}\sigma\|_{\infty},\ldots,\|\partial_{d}\sigma\|_{\infty}\\}$
if $s=1$ and $\sigma$ is elementwise, where $J\sigma^{-1}$ is the Jacobian of
$\sigma^{-1}$.

We impose an additional assumption about the boundedness of the reproducing
kernel of $H_{0}$. Note that the Sobolev spaces mentioned in Example 1 satisfy
this assumption.

###### Assumption 2

There exists $B>0$ such that for any $x\in\mathbb{R}^{d}$,
$|k_{p_{0}}(x,x)|\leq B^{2}$.

##  4 Koopman-based bound of Rademacher complexity

We derive an upper bound of the Rademacher complexity. We first focus on the
case where the weight matrices are invertible or injective. Then, we
generalize the results to the non-injective case.

Let $\Omega$ be a probability space equipped with a probability measure $P$.
We denote the integral $\int_{\Omega}s(\omega)\mathrm{d}P(\omega)$ of a
measurable function $s$ on $\Omega$ by $\mathrm{E}[s]$. Let
$s_{1},\ldots,s_{n}$ be i.i.d. Rademacher variables. For a function class $G$
and $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, we denote the empirical Rademacher
complexity by $\hat{R}_{n}(\mathbf{x},G)$, where
$\mathbf{x}=(x_{1},\ldots,x_{n})$. We will provide an upper bound of
$\hat{R}_{n}(\mathbf{x},G)$ using Koopman operators in the following
subsections.

###  4.1 Bound for invertible weight matrices ($d_{j}=d$)

In this subsection, we focus on the case $d_{j}=d\ (j=0,\ldots,L)$ for some
$d\in\mathbb{N}$ and $W_{j}$ is invertible for $j=1,\ldots,L$. This is the
most fundamental case. For $C,D>0$, set a class of weight matrices
$\mathcal{W}(C,D)=\\{W\in\mathbb{R}^{d\times d}\,\mid\,\|W\|\leq C,\
|\operatorname{det}(W)|\geq D\\}$ and a function class
${F}_{\operatorname{inv}}(C,D)=\\{f\in F\,\mid\,W_{j}\in\mathcal{W}(C,D)\\}$.
We have the following theorem for a bound of Rademacher complexity.

######  Theorem 3 (Firs Main Theorem)

The Rademacher complexity
$\hat{R}_{n}(\mathbf{x},{F}_{\operatorname{inv}}(C,D))$ is bounded as

$\displaystyle\hat{R}_{n}(\mathbf{x},{F}_{\operatorname{inv}}(C,D))\leq\frac{B\|g\|_{H_{L}}}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}(C,D)}\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\infty}^{1/2}\frac{\|K_{\sigma_{j}}\|}{|\operatorname{det}(W_{j})|^{1/2}}.$
(3)

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 the determinant
factors in the denominator in Eq. (3). They come from a change of variable
when we bound the norm of the Koopman operators, described by the following
inequality:

$\displaystyle\|K_{W_{j}}\|\leq\bigg{(}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\infty}\frac{1}{|\operatorname{det}(W_{j})|}\bigg{)}^{1/2},\quad\|K_{b_{j}}\|=1$

for $j=1,\ldots,L$. Since $f\in H_{0}$, using the reproducing property of
$H_{0}$, we derive an upper bound of $\hat{R}_{n}(\mathbf{x},F(C,D))$ in a
similar manner to that for kernel methods (see, Mohri et al. (2018, Theorem
6.12)).

Regarding the factor $\|{p_{j}}/(p_{j-1}\circ W_{j}^{*})\|_{\infty}$ in Eq.
(3), we obtain the following lemma and proposition, which show it is bounded
by $\|W_{j}\|$ and induces the factor
$\|W_{j}\|^{s_{j-1}}/\operatorname{det}(W_{j}^{*}W_{j})^{1/4}$ in Eq. (1).

###### Lemma 4

Let $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $s>d/2$ and $p_{j}=p$ for
$j=0,\ldots,L$. Then, we have $\|{p}/({p\circ
W_{j}^{*}})\|_{\infty}\leq{\max\\{1,{\|W_{j}\|^{2s}}\\}}$.

Asu a result, the following proposition is obtained by applying Lemma 4 to
Theorem 3.

###### Proposition 5

Let $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $s>d/2$ and $p_{j}=p$ for
$j=0,\ldots,L$. We have

$\displaystyle\hat{R}_{n}(\mathbf{x},{F}_{\operatorname{inv}}(C,D))\leq\frac{B\|g\|_{H_{L}}}{\sqrt{n}}\prod_{j=1}^{L}\frac{\|K_{\sigma_{j}}\|\max\\{1,C^{s}\\}}{\sqrt{D}}.$

##### Comparison to existing bounds

We investigate the bound (1) in terms of the singular values of $W_{j}$. Let
$\eta_{1,j}\geq\ldots\geq\eta_{d,j}$ be the singular values of $W_{j}$ and let
$\alpha=s-d/2$. Then, the term depending on the weight matrices in bound (1)
is described as $\eta_{1,j}^{\alpha}\prod_{i=1}^{d}r_{i,j}^{1/2}$, where
$r_{i,j}=\eta_{1,j}/\eta_{i,j}$. On the other hand, the existing bound by
Golowich et al. (2018) is described as
$\eta_{1,j}(\sum_{i=1}^{d}r_{i,j}^{-2})^{1/2}$. Since they are just upper
bounds, our bound does not contradict the existing bound. Our bound is tight
when the condition number $r_{d,j}$ of $W_{j}$ is small. The existing bound is
tight when $r_{d,j}$ is large. Note that the factors in our bound (1) are
bounded below by $1$.

###### Remark 6

If a weight matrix $W_{j}$ is orthogonal, then the factor
${\|W_{j}\|^{s_{j-1}}}/{\operatorname{det}(W_{j})^{1/2}}$ in the bound (1) is
reduced to $1$. On the other hand, existing norm-based bounds are described by
the $(p.q)$ matrix norm. The $(p,q)$ matrix norm of the $d$ by $d$ identity
matrix is $d^{1/p}$, which is larger than $1$. Indeed, limiting the weight
matrices to orthogonal matrices has been proposed (Maduranga et al., 2019;
Wang et al., 2020; Li et al., 2021). The tightness of our bound in the case of
orthogonal matrices implies the advantage of these methods from the
perspective of generalization.

###### Remark 7

There is a tradeoff between $s$ and $B$. We focus on the case where
$p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s}$. According to Lemma 4, the factor
$\|{p_{j}}/(p_{j-1}\circ W_{j}^{*})\|_{\infty}$ becomes small as $s$
approaches to $d/2$. However, the factor $B$ goes to infinity as $s$ goes to
$d/2$. Indeed, we have
$k_{p}(x,x)=\int_{\mathbb{R}^{d}}p(\omega)\mathrm{d}\omega\geq\prod_{i=1}^{d}\int_{\mathbb{R}}1/(1+|\omega|^{2})^{s}\mathrm{d}\omega\geq
2\sum_{n=1}^{\infty}1/(1+n^{2})^{s}$. This behavior corresponds to the fact
that if $s=d/2$, the Sobolev space is not an RKHS, and the evaluation operator
becomes unbounded.

###  4.2 Bound for injective weight matrices ($d_{j}\geq d_{j-1}$)

We generalize Theorem 3 to that for injective weight matrices. If
$d_{j}>d_{j-1}$, then $W_{j}$ is not surjective. However, it can be injective,
and we first focus on the injective case. Let
$\mathcal{W}_{j}(C,D)=\\{W\in\mathbb{R}^{d_{j-1}\times d_{j}}\,\mid\,d_{j}\geq
d_{j-1},\ \|W\|\leq C,\ \sqrt{\operatorname{det}({W^{*}W})}\geq D\\}$ and
$F_{\operatorname{inj}}(C,D)=\\{f\in
F\,\mid\,W_{j}\in\mathcal{W}_{j}(C,D)\\}$. Let $f_{j}=g\circ b_{L}\circ
W_{L}\circ\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{j}\circ b_{j}$ and
$G_{j}=\|f_{j}|_{\mathcal{R}(W_{j})}\|_{H_{p_{j}}(\mathcal{R}(W_{j}))}/\|f_{j}\|_{H_{j}}$.
We have the following theorem for injective weight matrices.

######  Theorem 8 (Second Main Theorem)

The Rademacher complexity
$\hat{R}_{n}(\mathbf{x},F_{\operatorname{inj}}(C,D))$ is bounded as

$\displaystyle\hat{R}_{n}(\mathbf{x},F_{\operatorname{inj}}(C,D)))\leq\frac{B\|g\|_{H_{L}}}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}_{j}(C,D)}\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}.$
(4)

Since $W_{j}$ is not always square, we do not have $\operatorname{det}(W_{j})$
in Theorem 3. However, we can replace $\operatorname{det}(W_{j})$ with
$\operatorname{det}(W_{j}^{*}W_{j})^{1/2}$. As Lemma 4, we have the following
lemma about the factor $\|{p_{j}}/({p_{j-1}\circ
W_{j}^{*}})\|_{\mathcal{R}(W_{j}),\infty}$ in Eq. (4).

###### Lemma 9

Let $p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s_{j}}$ for $s_{j}>d_{j}/2$ and for
$j=0,\ldots,L$. Let $s_{j}\geq s_{j-1}$. Then, we have
$\|{p_{j}}/({p_{j-1}\circ
W_{j}^{*}})\|_{\mathcal{R}(W_{j}),\infty}\leq{\max\\{1,{\|W_{j}\|^{2s_{j-1}}}\\}}$.

Regarding the factor $G_{j}$, the following lemma shows that $G_{j}$ is
determined by the isotropy of $f_{j}$. Note that if
$p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s_{j}}$ for $s_{j}>d_{j}/2$, then the
assumption in Lemma 10 is satisfied.

###### Lemma 10

Assume $p_{j}(\omega_{1}+\omega_{2})\leq p_{j}(\omega_{1})$ for
$\omega_{1}\in\mathcal{R}(W_{j})$ and
$\omega_{2}\in\mathcal{R}(W_{j})^{\perp}$. Then, $G_{j}\leq
G_{j,0}\|f_{j}|_{\mathcal{R}(W_{j})}\cdot
f_{j}|_{\mathcal{R}(W_{j})^{\perp}}\|_{H_{j}}/\|f_{j}\|_{H_{j}}$, where
$G_{j,0}^{2}=1/\int_{\mathcal{R}(W_{j})^{\perp}}|\hat{f_{j}}(\omega)|^{2}\mathrm{d}\omega$.

Indeed, if $f_{j}(x)=\mathrm{e}^{-c\|x\|^{2}}$ (It is true if $g$ is Gaussian
and $j=L$.), then
$G_{j}\leq(2c/\pi)^{\operatorname{dim}(\mathcal{R}(W_{j})^{\perp})/4}$.
Applying Lemmas 9 and 10 to Theorem 8, we finally obtain the bound (1).

###  4.3 Bounds for non-injective weight matrices

The bounds in Theorems 3 and 8 are only valid for injective weight matrices,
and the bound goes to infinity if they become singular. This is because if
$W_{j}:\mathbb{R}^{d_{j-1}}\to\mathbb{R}^{d_{j}}$ has singularity, $h\circ W$
for $h\in H_{j}$ becomes constant along the direction of
$\operatorname{ker}(W_{j})$. As a result, $h\circ W_{j}$ does not contained in
$H_{j-1}$ and $K_{W_{j}}$ becomes unbounded. To deal with this situation, we
propose two approaches that are valid for non-injective weight matrices,
graph-based and weighted Koopman-based ones.

####  4.3.1 Graph-based bound

The first approach to deal with this situation is constructing an injective
operator related to the graph of $W_{j}$. For $j=1,\ldots,L$, let
$\delta_{j}=\sum_{k=0}^{j}d_{k}$ and
$\tilde{W}_{j}:\mathbb{R}^{\delta_{j-1}}\to\mathbb{R}^{\delta_{j}}$ be defined
as $\tilde{W}_{j}(x_{1},x_{2})=(W_{j}x_{1},x_{1},x_{2})$ for
$x_{1}\in\mathbb{R}^{d_{j-1}}$ and $x_{2}\in\mathbb{R}^{\delta_{j-2}}$ for
$j\geq 2$ and $\tilde{W}_{j}x=(W_{j}x,x)$ for $j=1$. Then, $\tilde{W}_{j}$ is
injective. Let
$\tilde{\sigma}_{j}:\mathbb{R}^{\delta_{j}}\to\mathbb{R}^{\delta_{j}}$ and
$\tilde{b}_{j}:\mathbb{R}^{\delta_{j}}\to\mathbb{R}^{\delta_{j}}$ be defined
respectively as $\tilde{\sigma}_{j}(x_{1},x_{2})=(\sigma_{j}(x_{1}),x_{2})$
and $\tilde{b}_{j}(x_{1},x_{2})=(b_{j}(x_{1}),x_{2})$ for
$x_{1}\in\mathbb{R}^{d_{j}}$ and $x_{2}\in\mathbb{R}^{\delta_{j-1}}$. In
addition, let $\tilde{g}\in H_{p_{L}}(\mathbb{R}^{\delta_{L}})$ be defined as
$\tilde{g}(x_{1},x_{2})=g(x_{1})\psi(x_{2})$ for $x_{1}\in\mathbb{R}^{d_{L}}$
and $x_{2}\in\mathbb{R}^{\delta_{L-1}}$, where $\psi$ is a rapidly decaying
function on $\mathbb{R}^{\delta_{L-1}}$ so that $\tilde{g}\in
H_{p_{L}}(\mathbb{R}^{\delta_{L}})$. Consider the following network:

$\displaystyle\tilde{f}(x)$
$\displaystyle=\tilde{g}\circ\tilde{b}_{L}\circ\tilde{W}_{L}\circ\cdots\circ\tilde{\sigma}_{1}\circ\tilde{b}_{1}\circ\tilde{W}_{1}(x)$
$\displaystyle=\psi(\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ
W_{1}(x),\ldots,\sigma_{1}\circ b_{1}\circ W_{1}(x),x)$
$\displaystyle\qquad\qquad\cdot g(b_{L}\circ
W_{L}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}(x)).$ (5)

Since
$\operatorname{det}(\tilde{W}_{j}^{*}\tilde{W}_{j})=\operatorname{det}(W_{j}^{*}W_{j}+I)$
and $\|\tilde{W}_{j}\|=\sqrt{\|I+W_{j}^{*}W_{j}\|}$, we set
$\tilde{\mathcal{W}}_{j}(C,D)=\\{{W}\in\mathbb{R}^{d_{j-1}\times
d_{j}}\,\mid\,\sqrt{\|I+W^{*}W\|}\leq C,\
\sqrt{\operatorname{det}(W^{*}W+I)}\geq D\\}$ and
$\tilde{F}(C,D)=\\{\tilde{f}\,\mid\,f\in F,\
{W}_{j}\in\tilde{\mathcal{W}}_{j}(C,D)\\}$. Moreover, put
$\tilde{H}_{L}=H_{p_{L}}(\mathbb{R}^{\delta_{L}})$. By Theorem 8, we obtain
the following bound, where the determinant factor does not go to infinity by
virtue of the identity $I$ appearing in $\tilde{W}_{j}$.

###### Proposition 11

The Rademacher complexity $\hat{R}_{n}(\mathbf{x},\tilde{F}(C,D))$ is bounded
as

$\displaystyle\hat{R}_{n}(\mathbf{x},\tilde{F}(C,D)))\leq\frac{B\|\tilde{g}\|_{\tilde{H}_{L}}}{\sqrt{n}}\sup_{{W}_{j}\in\mathcal{W}_{j}(C,D)}\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ\tilde{W}_{j}^{*}}\bigg{\|}_{\mathcal{R}(\tilde{W}_{j}),\infty}^{1/2}\frac{\tilde{G}_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j}+I)}}^{1/4}}.$

###### Remark 12

The difference between the networks (5) and (2) is the factor $\psi$. If we
set $\psi$ as $\psi(x)=1$ for $x$ in a sufficiently large region $\Omega$,
then $\tilde{f}(x)=f(x)$ for $x\in\Omega$. We can set $\psi$, for example, as
a smooth bump function (Tu, 2011, Chapter 13). If the data is in a compact
region, then the output of each layer is also in a compact region since
$\|W_{j}\|\leq\sqrt{\|I+W_{j}^{*}W_{j}\|}\leq C$. Thus, it is natural to
assume that $f$ can be replaced by $\tilde{f}$ in practical cases.

###### Remark 13

The factor $\|\tilde{g}\|_{\tilde{H}_{L}}$ grows as $\Omega$ becomes large.
This is because $\|\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}$ becomes
large as the volume of $\Omega$ gets large. This fact does not contradict the
fact that the bound in Theorem 3 goes to infinity if $W_{j}$ is singular. More
details are explained in Appendix B.

####  4.3.2 Weighted Koopman-based bound

Instead of constructing the injective operators in Subsection 4.3.1, we can
also use weighted Koopman operators. For
$\psi_{j}:\mathbb{R}^{d_{j}}\to\mathbb{C}$, define
$\tilde{K}_{W_{j}}h=\psi_{j}\cdot h\circ W_{j}$, which is called the weighted
Koopman operator. We construct the same network as $\tilde{f}$ in Eq. (5)
using $\tilde{K}_{W_{j}}$.

$\displaystyle\tilde{f}(x)$
$\displaystyle=\tilde{K}_{W_{1}}K_{b_{1}}K_{\sigma_{1}}\cdots\tilde{K}_{W_{L}}K_{b_{L}}g(x)$
$\displaystyle=\psi_{1}(x)\psi_{2}(\sigma_{1}\circ b_{1}\circ
W_{1}(x))\cdots\psi_{L}(\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}(x))$
$\displaystyle\qquad\qquad\cdot g(b_{L}\circ
W_{L}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}(x))$
$\displaystyle=\psi(\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ
W_{1}(x),\ldots,\sigma_{1}\circ b_{1}\circ W_{1}(x),x)$
$\displaystyle\qquad\qquad\cdot g(b_{L}\circ
W_{L}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}(x)),$

where $\psi(x_{1},\ldots,x_{L})=\psi_{1}(x_{1})\cdots\psi_{L}(x_{L})$ for
$x_{j}\in\mathbb{R}^{d_{j-1}}$. Let
$W_{\operatorname{r},j}=W_{j}|_{\operatorname{ker}(W_{j})^{\perp}}$ be the
restricted operator of $W_{j}$ to $\operatorname{ker}(W_{j})^{\perp}$. Set
$\mathcal{W}_{\operatorname{r},j}(C,D)=\\{W\in\mathbb{R}^{d_{j-1}\times
d_{j}}\,\mid\,\|W\|\leq C,\ |\operatorname{det}(W_{\operatorname{r}})|\geq
D\\}$ and $F_{\mathrm{r}}(C,D)=\\{f\in
F\,\mid\,{W}_{j}\in{\mathcal{W}}_{\mathrm{r},j}(C,D)\\}$. By letting
$\psi_{j}$ decay in the direction of $\operatorname{ker}(W_{j})$, e.g., the
smooth bump function, $\tilde{K}_{W_{j}}h$ for $h\in H_{j}$ decays in all the
directions. We only need to care about $W_{\operatorname{r},j}$, not whole
$W_{j}$. Note that $\psi_{j}$ has the same role as $\psi$ in Eq. (5). If the
data is in a compact region, we replace $f$ by $\tilde{f}$, which coincides
with $f$ on the compact region. By virtue of the decay property of $\psi_{j}$,
we can bound $\tilde{K}_{W_{j}}$ even if $W_{j}$ is singular.

###### Proposition 14

Let $p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s_{j}}$ with $s_{j}\in\mathbb{N}$,
$s_{j}\geq s_{j-1}$, and $s_{j}>d_{j}/2$. Let $\psi_{j}$ be a function
satisfying $\psi_{j}(x)=\psi_{j,1}(x_{1})$ for some $\psi_{j,1}\in
H_{p_{j-1}}(\operatorname{ker}(W_{j}))$, where $x=x_{1}+x_{2}$ for
$x_{1}\in\operatorname{ker}(W_{j})$ and
$x_{2}\in\operatorname{ker}(W_{j})^{\perp}$. Then, we have

$\displaystyle\hat{R}_{n}(\mathbf{x},{F}_{\mathrm{r}}(C,D)))\leq\frac{B\|{g}\|_{H_{L}}}{\sqrt{n}}\sup_{{W}_{j}\in\mathcal{W}_{\operatorname{r},j}(C,D)}O\bigg{(}\prod_{j=1}^{L}\max\\{1,\|W_{j}\|^{s_{j-1}}\\}\frac{G_{j}\|K_{\sigma_{j}}\|}{|{\operatorname{det}(W_{\operatorname{r},j})}|^{1/2}}\bigg{)}.$

###### Remark 15

Although we focus on the singularity of $K_{W_{j}}$ and use the weighted
Koopman operator with respect to $W_{j}$, we can deal with the singularity of
$K_{\sigma_{j}}$ in the same manner as $K_{W_{j}}$, i.e., by constructing the
weighted Koopman operator $\tilde{K}_{\sigma_{j}}$ with respect to
$\sigma_{j}$. For example, the sigmoid and hyperbolic tangent do not satisfy
the assumption for $\sigma_{j}$ stated in Proposition 2. This is because the
Jacobian of $\sigma^{-1}$ is not bounded. However, $\tilde{K}_{\sigma_{j}}$ is
bounded by virtue of $\psi_{j}$.

###  4.4 Combining the Koopman-based 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 and the case where existing bounds such as the one by
Golowich et al. (2018) are tight are different. We can combine these bounds to
obtain a tighter bound. For $1\leq l\leq L$, let $F_{1:l}$ be the set of all
functions in the form

$\sigma_{l}\circ b_{l}\circ W_{l}\circ\sigma_{l-1}\circ b_{l-1}\circ
W_{l-1}\circ\cdots\circ\sigma_{1}\circ b_{1}\circ W_{1}$ (6)

with Assumption 1, and let $F_{1:l,\operatorname{inj}}(C,D)=\\{f\in
F_{1:l}\,\mid\,W_{j}\in\mathcal{W}_{j}(C,D)\\}$. For $l\leq L-1$, consider the
set of all functions in $H_{l}$ which has the form

$g\circ b_{L}\circ W_{L}\circ\sigma_{L-1}\circ b_{L-1}\circ
W_{L-1}\circ\cdots\circ\sigma_{l+1}\circ b_{l+1}\circ W_{l+1}$

and consider any nonempty subset $F_{l+1:L}$ of it. For $l=L$, we set
$F_{L+1:L}=\\{g\\}$. Let $F_{l,\operatorname{comb}}(C,D)=\\{f_{1}\circ
f_{2}\,\mid\,f_{1}\in F_{l+1,L},\ f_{2}\in
F_{1:l,\operatorname{inj}}(C,D)\\}$. The following proposition shows the
connection between the Rademacher complexity of
$F_{l,\operatorname{comb}}(C,D)$ and that of $F_{l+1:L}$.

###### Proposition 16

Let
$\tilde{\mathbf{x}}=(\tilde{x}_{1},\ldots,\tilde{x}_{n})\in(\mathbb{R}^{d_{l}})^{n}$.
Let $v_{n}(\omega)=\sum_{i=1}^{n}s_{i}(\omega)k_{p_{0}}(\cdot,x_{i})$,
$\tilde{v}_{n}(\omega)=\sum_{i=1}^{n}s_{i}(\omega)k_{p_{l}}(\cdot,\tilde{x}_{i})$,
and $\gamma_{n}=\|v_{n}\|_{H_{0}}/\|\tilde{v}_{n}\|_{H_{l}}$. Then, we have

$\displaystyle\hat{R}_{n}(\mathbf{x},F_{l,\operatorname{comb}}(C,D))$
$\displaystyle\leq\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{l}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}$
$\displaystyle\qquad\cdot\bigg{(}\hat{R}_{n}(\tilde{\mathbf{x}},F_{l+1:L})+\frac{B}{\sqrt{n}}\inf_{h_{1}\in
F_{l+1:L}}\\!\\!\\!\mathrm{E}^{\frac{1}{2}}\bigg{[}\\!\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}h_{1}-\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}\bigg{\|}_{H_{l}}^{2}\bigg{]}\bigg{)}.$

The complexity of the whole network is decomposed into the Koopman-based bound
for the first $l$ layers and the complexity of the remaining $L-l$ layers,
together with a term describing the approximation power of the function class
corresponding to $L-l$ layers. Note that Proposition 16 generalizes Theorem 8
up to the multiplication of a constant. Indeed, if $l=L$, we have
$\hat{R}_{n}(\mathbf{x},F_{l+1,L})=0$. In addition, we have $\inf_{h_{1}\in
F_{l+1:L}}\mathrm{E}^{1/2}[\sup_{h_{2}\in
F_{l+1:L}}\|h_{1}-{\|h_{2}\|\gamma_{n}\tilde{v}_{n}}/{\|\tilde{v}_{n}\|}\|^{2}]=\mathrm{E}^{1/2}[\|g-{\|g\|\gamma_{n}\tilde{v}_{n}}/{\|\tilde{v}_{n}\|}\|^{2}]\leq\|g\|\mathrm{E}^{1/2}[(1+\gamma_{n})^{2}]$.

###### Remark 17

We can also combine our Koopman-based approach with the existing “peeling”
approach, e.g., by Neyshabur et al. (2015); Golowich et al. (2018) (see
Appendix C). Then, for $1\leq l\leq L$, we obtain a bound such as

$\displaystyle
O\big{(}(\prod_{j=l+1}^{L}\|W_{j}\|_{2,2})(\prod_{j=1}^{l}{\|W_{j}\|^{s_{j}}}/{\operatorname{det}(W_{j}^{*}W_{j})^{1/4}})\big{)}.$

Typically, in many networks, the width grows sequentially near the input
layer, i.e., $d_{j-1}\leq d_{j}$ for small $j$ and decays near the output
layer, i.e., $d_{j-1}\geq d_{j}$ for large $j$. Therefore, this type of
combination is suitable for many practical cases for deriving a tighter bound
than existing bounds.

Proposition 16 and Remark 17 theoretically implies that our Koopman-based
bound is suitable for lower layers. Practically, we can interpret that signals
are transformed on the lower layers and are extracted on the higher layers.
The transformation leads to the better extraction of signals on the higher
layers. This interpretation also supports the result in Figure 1 by Arora et
al. (2018). Noise is removed (i.e., signals are extracted) by the higher
layers, but it is not completely removed by lower layers. We will investigate
the behavior of each layer numerically in Section 5 and Appendix D.2.1.

##  5 Numerical results

##### Validity of the bound

To investigate our bound numerically, we consider a regression problem on
$\mathbb{R}^{3}$, where the target function $t$ is
$t(x)=\mathrm{e}^{-\|2x-1\|^{2}}$. We constructed a simple network
$f(x)=g(W_{2}\sigma(W_{1}x+b_{1})+b_{2})$, where $W_{1}\in\mathbb{R}^{3\times
3}$, $W_{2}\in\mathbb{R}^{6\times 3}$, $b_{1}\in\mathbb{R}^{3}$,
$b_{2}\in\mathbb{R}^{6}$, $g(x)=\mathrm{e}^{-\|x\|^{2}}$, and $\sigma$ is a
smooth version of Leaky ReLU proposed by Biswas et al. (2022). We created a
training dataset from samples randomly drawn from the standard normal
distribution. Figure 1 (a) illustrates the relationship between the
generalization error and our bound
$O(\prod_{j=1}^{L}\|W_{j}\|^{s_{j}}/(\mathrm{det}(W_{j}^{*}W_{j})^{1/4}))$.
Here, we set $s_{j}=(d_{j}+0.1)/2$. In Figure 1 (a), we can see that our bound
gets small 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 a situation
where the model is hard to generalize. We constructed a network with four
dense layers and learned it with and without a regularization term
$\|W_{j}\|+1/\operatorname{det}(I+W_{j}^{*}W_{j})$, which makes both the norm
and determinant of $W_{j}$ small. Figure 1 (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.

Figure 1: (a) Scatter plot of the generalization error versus our bound (for 5
independent runs). The color is set to get dark as the epoch proceeds. (b)
Test accuracy with and without the regularization based on our bound. (c) The
condition number $r_{d,j}=\eta_{1,j}/\eta_{d,j}$ of the weight matrix for
layer $j=2,\ldots,4$.

##### 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,\ldots,5$, we computed the
condition number $r_{d,j}$ of the weight matrix. The results are illustrated
in Figure 1 (c). We scaled the values for $j=4,5$ for readability. Since the
weight matrix of the first layer ($j=1$) is huge and the computational cost of
computing its singular values is expensive, we focus on $j=2,\ldots,5$. We can
see that for the second layer ($j=2$), $r_{d,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 $r_{d,j}$ tends to be large. This
means that the behavior of the singular values is different depending on the
layer. According to the paragraph after Proposition 5, our bound becomes small
as $r_{d,j}$ becomes small, but the existing bound becomes small as $r_{d,j}$
becomes large. Thus, 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 high-rank
weight matrices generalize well and justifies the generalization property of
networks with orthogonal matrices. In addition, we provided an operator-
theoretic approach to analyzing generalization property of neural networks.

There are several possible limitations. First, our setting excludes non-smooth
activation functions. Generalizing our framework to other function spaces may
help us understand these final nonlinear transformations and activation
functions. Moreover, although the factor $\|K_{\sigma_{j}}\|$ 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 a function space on a
manifold that contains the range of the transformation corresponding to each
layer may also be effective for resolving this issue. These challenging topics
are left to future work.

### Acknowledgement

SS was partially supported by JST PRESTO JPMJPR2125 and JST CREST JPMJCR2015.
II was partially supported by JST CREST JPMJCR1913 and JST ACT-X JPMJAX2004.
AN was partially supported by JSPS KAKENHI 22H03650 and JST PRESTO JPMJPR1928.
TS was partially supported by JSPS KAKENHI 20H00576 and JST CREST.

## References

  * Anthony & Bartlett (2009) Martin Anthony and Peter L. Bartlett.  _Neural network learning: Theoretical foundations_.  Cambridge University Press, 2009.
  * Arora et al. (2018) Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , 2018.
  * Bartlett & Mendelson (2002) Peter L. Bartlett and Shahar Mendelson.  Rademacher and Gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3:463–482, 2002\.
  * Bartlett et al. (2017) Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In _Proceedings of Advances in Neural Information Processing Systems 31 (NIPS)_ , 2017.
  * Biswas et al. (2022) Koushik Biswas, Sandeep Kumar, Shilpak Banerjee, and Ashish Kumar Pandey.  Smooth maximum unit: Smooth activation function for deep networks using smoothing maximum technique.  In _Proceedings of 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Brunton et al. (2022) Steven L. Brunton, Marko Budišić, Eurika Kaiser, and J. Nathan Kutz.  Modern Koopman theory for dynamical systems.  _SIAM Review_ , 64(2):229–340, 2022.
  * Budišić et al. (2012) Marko Budišić, Ryan Mohr, and Igor Mezić.  Applied Koopmanism.  _Chaos (Woodbury, N.Y.)_ , 22:047510, 2012.
  * Das et al. (2021) 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.
  * Dogra & Redman (2020) Akshunna S. Dogra and William Redman.  Optimizing neural networks via Koopman operator theory.  In _Proceedings of Advances in Neural Information Processing Systems 34 (NeurIPS)_ , 2020.
  * Giannakis & Das (2020) Dimitrios Giannakis and Suddhasattwa Das.  Extraction and prediction of coherent patterns in incompressible flows through space-time Koopman analysis.  _Physica D: Nonlinear Phenomena_ , 402:132211, 2020.
  * Goldblum et al. (2020) Micah Goldblum, Jonas Geiping, Avi Schwarzschild, Michael Moeller, and Tom Goldstein.  Truth or backpropaganda? an empirical investigation of deep learning theory.  In _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , 2020.
  * Golowich et al. (2018) 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.
  * Harvey et al. (2017) 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.
  * Hashimoto et al. (2020) Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Yoichi Matsuo, and Yoshinobu Kawahara.  Krylov subspace method for nonlinear dynamical systems with random noise.  _Journal of Machine Learning Research_ , 21(172):1–29, 2020.
  * He et al. (2015) 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 on Computer Vision (ICCV)_ , 2015.
  * Ikeda et al. (2022a) Masahiro Ikeda, Isao Ishikawa, and Yoshihiro Sawano.  Boundedness of composition operators on reproducing kernel Hilbert spaces with analytic positive definite functions.  _Journal of Mathematical Analysis and Applications_ , 511(1):126048, 2022a.
  * Ikeda et al. (2022b) Masahiro Ikeda, Isao Ishikawa, and Corbinian Schlosser.  Koopman and Perron-–Frobenius operators on reproducing kernel Banach spaces.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , 32(12):123143, 2022b.
  * Ishikawa (2023) Isao Ishikawa.  Bounded composition operators on functional quasi-banach spaces and stability of dynamical systems.  _Advances in Mathematics_ , 424:109048, 2023.
  * Ishikawa et al. (2018) 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.
  * Ju et al. (2022) 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.
  * Kawahara (2016) Yoshinobu Kawahara.  Dynamic mode decomposition with reproducing kernels for Koopman spectral analysis.  In _Proceedings of Advances in Neural Information Processing Systems 30 (NIPS)_ , 2016.
  * Kingma & Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_ , 2015.
  * Klus et al. (2020) Stefan Klus, Ingmar Schuster, and Krikamol Muandet.  Eigendecompositions of transfer operators in reproducing kernel Hilbert spaces.  _Journal of Nonlinear Science_ , 30:283–315, 2020.
  * Konishi & Kawahara (2023) Takuya Konishi and Yoshinobu Kawahara.  Stable invariant models via Koopman spectra.  _Neural Networks_ , 165:393–405, 2023.
  * Koopman (1931) Bernard Koopman.  Hamiltonian systems and transformation in Hilbert space.  _Proceedings of the National Academy of Sciences_ , 17(5):315–318, 1931.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  In _Proceedings of Advances in Neural Information Processing Systems 26 (NIPS)_ , 2012.
  * Li et al. (2021) Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao.  Orthogonal deep neural networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 43(04):1352–1368, 2021.
  * Lusch et al. (2017) Bethany Lusch, J. Nathan Kutz, and Steven L. Brunton.  Deep learning for universal linear embeddings of nonlinear dynamics.  _Nature Communications_ , 9:4950, 2017.
  * Maduranga et al. (2019) Kehelwala D. G. Maduranga, Kyle E. Helfrich, and Qiang Ye.  Complex unitary recurrent neural networks using scaled Cayley transform.  In _Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI)_ , 2019.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of Machine Learning_.  MIT press, 2018.
  * Neyshabur et al. (2015) 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.
  * Neyshabur et al. (2018) Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.  A PAC-bayesian approach to spectrally-normalized margin bounds for neural networks.  In _Proceedings of the 6th International Conference on Learning Representations (ICLR)_ , 2018.
  * Neyshabur et al. (2019) Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.  The role of over-parametrization in generalization of neural networks.  In _Proceedings of the 7th International Conference on Learning Representations (ICLR)_ , 2019.
  * Novak et al. (2018) Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Sensitivity and generalization in neural networks: an empirical study.  In _Proceedings of the 6th International Conference on Learning Representations (ICLR)_ , 2018.
  * Redman et al. (2022) William T. Redman, Maria Fonoberova, Ryan Mohr, Yannis Kevrekidis, and Igor Mezić.  An operator theoretic view on pruning deep neural networks.  In _Proceedings of the 10th International Conference on Learning Representations (ICLR)_ , 2022.
  * Sawano (2018) Yoshihiro Sawano.  _Theory of Besov Spaces_.  Springer Singapore, 2018.
  * Suzuki et al. (2020) Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura.  Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network.  In _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , 2020.
  * Tu (2011) Loring W. Tu.  _An Introduction to Manifolds_.  Springer New York, second edition, 2011.
  * Wang et al. (2020) Jiayun Wang, Yubei Chen, Rudrasis Chakraborty, and Stella X. Yu.  Orthogonal convolutional neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Wei & Ma (2019) Colin Wei and Tengyu Ma.  Data-dependent sample complexity of deep neural networks via Lipschitz augmentation.  In _Proceedings of Advances in Neural Information Processing Systems 33 (NeurIPS)_ , 2019.
  * Wei & Ma (2020) 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 et al. (2022) Weinan E, Chao Ma, and Lei Wu.  The Barron space and the flow-induced function spaces for neural network models.  _Constructive Approximation_ , 55:369–406, 2022.

## Appendix

##  Appendix A Proofs

We provide the proofs of the theorems, propositions, and lemmas in the main
text.

Proposition 2 Let $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for
$\omega\in\mathbb{R}^{d}$ $s\in\mathbb{N}$, and $s>d/2$. If the activation
function $\sigma$ has the following properties, then
$K_{\sigma}:H_{p}(\mathbb{R}^{d})\to H_{p}(\mathbb{R}^{d})$ is bounded.

  * •

$\sigma$ is $s$-times differentiable and its derivative
$\partial^{\alpha}\sigma$ is bounded for any multi-index
$\alpha\in\\{(\alpha_{1},\ldots,\alpha_{d})\,\mid\,\sum_{j=1}^{d}\alpha_{j}\leq
s\\}$.

  * •

$\sigma$ is bi-Lipschitz, i.e., $\sigma$ is bijective and both $\sigma$ and
$\sigma^{-1}$ are Lipschitz continuous.

Proof  For $h\in H(\mathbb{R}^{d})$, we have
$\|K_{\sigma}h\|_{H_{p}(\mathbb{R}^{d})}^{2}=\sum_{|\alpha|\leq
s}\|\partial^{\alpha}(h\circ\sigma)\|_{L^{2}(\mathbb{R}^{d})}^{2}$. We denote
$\sigma(x)=(\sigma_{1}(x),\ldots,\sigma_{d}(x))$ and
$D_{\gamma}\sigma(x)=(\partial^{\gamma}\sigma_{1}(x),\ldots,\partial^{\gamma}\sigma_{d}(x))$
for $\gamma\in\mathbb{N}^{d}$. By the Faà di Bruno formula,
$\partial^{\alpha}(h\circ\sigma)(x)$ is written as the finite weighted sum of
$\partial^{\beta}h(\sigma(x))\prod_{i=1}^{m}(D_{\gamma_{i}}\sigma(x))^{\delta_{i}}$
for some $m\leq|\alpha|$ and $\beta,\gamma_{i},\delta_{i}\in\mathbb{N}^{d}$,
$|\beta|\leq|\alpha|$, $|\gamma_{i}|\leq|\alpha|$, $|\delta_{i}|\leq|\alpha|$.
By the boundedness of the derivatives of $\sigma$, there exists
${C}_{\beta,\gamma,\delta}>0$ such that

$\displaystyle\int_{\mathbb{R}^{d}}\bigg{|}\partial^{\beta}h(\sigma(x))\prod_{i=1}^{m}(D_{\gamma_{i}}\sigma(x))^{\delta_{i}}\bigg{|}^{2}\mathrm{d}x\leq{C}_{\beta,\gamma,\delta}\int_{\mathbb{R}^{d}}|\partial^{\beta}h(\sigma(x))|^{2}\mathrm{d}x.$

Moreover, by the Lipschitzness of $\sigma^{-1}$, there exists $\tilde{C}>0$
such that

$\displaystyle\int_{\mathbb{R}^{d}}|\partial^{\beta}h(\sigma(x))|^{2}\mathrm{d}x\leq\|\operatorname{det}(J\sigma^{-1})\|_{\infty}\int_{\mathbb{R}^{d}}|\partial^{\beta}h(x)|^{2}\mathrm{d}x\leq\tilde{C}\int_{\mathbb{R}^{d}}|\partial^{\beta}h(x)|^{2}\mathrm{d}x,$

which shows the boundedness of $K_{\sigma}$. $\Box$

Theorem 3 The Rademacher complexity
$\hat{R}_{n}(\mathbf{x},{F}_{\operatorname{inv}}(C,D))$ is bounded as

$\displaystyle\hat{R}_{n}(\mathbf{x},{F}_{\operatorname{inv}}(C,D))\leq\frac{B\|g\|_{H_{L}}}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}(C,D)}\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\infty}^{1/2}\frac{\|K_{\sigma_{j}}\|}{|\operatorname{det}(W_{j})|^{1/2}}.$

We use the following lemma to show Theorem 3.

###### Lemma A

Assume $W_{j}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is invertible for
$j=1,\ldots,L$. Then, for $j=1,\ldots,L$, we have

$\displaystyle\|K_{W_{j}}\|\leq\bigg{(}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\infty}\frac{1}{|\operatorname{det}(W_{j})|}\bigg{)}^{1/2},\quad\|K_{b_{j}}\|=1.$

Proof  For $h\in H_{j}$, we have $\widehat{(h\circ
W_{j})}(\omega)=\int_{\mathbb{R}^{d}}h(W_{j}x)\mathrm{e}^{-\mathrm{i}x\cdot\omega}\mathrm{d}x={\hat{h}(W_{j}^{-*}\omega)}/{|\operatorname{det}(W_{j})|}$.
Thus, the norm of the Koopman operator is bounded as

$\displaystyle\|K_{W_{j}}h\|_{H_{j-1}}^{2}$
$\displaystyle=\int_{\mathbb{R}^{d}}\frac{|\hat{h}(W_{j}^{-*}\omega)|^{2}}{|\operatorname{det}(W_{j})|^{2}p_{j-1}(\omega)}\mathrm{d}\omega\leq\|h\|_{H_{j}}^{2}\sup_{\omega\in\mathbb{R}^{d}}\bigg{|}\frac{p_{j}(\omega)}{p_{j-1}(W_{j}^{*}\omega)}\bigg{|}\frac{1}{|\operatorname{det}(W_{j})|}.$

In addition, for $h\in H_{j}$, we have $\widehat{(h\circ
b_{j})}(\omega)=\mathrm{e}^{-\mathrm{i}a_{j}\cdot\omega}\hat{h}(\omega)$.
Thus, we obtain $\|K_{b_{j}}h\|^{2}=\|h\|^{2}$. $\Box$

Proof of Theorem 3 By the reproducing property of $H_{0}$ and the
Cauchy–Schwartz inequality, we have

$\displaystyle\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{\operatorname{inv}}(C,D)}\sum_{i=1}^{n}s_{i}f(x_{i})\bigg{]}=\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{\operatorname{inv}}(C,D)}\sum_{i=1}^{n}\left\langle
s_{i}k_{p_{0}}(\cdot,x_{i}),f\right\rangle_{H_{0}}\bigg{]}$
$\displaystyle\qquad\leq\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{\operatorname{inv}}(C,D)}\bigg{(}\sum_{i,j=1}^{n}s_{i}s_{j}k_{p_{0}}(x_{i},x_{j})\bigg{)}^{\frac{1}{2}}\|f\|_{H_{0}}\bigg{]}$
$\displaystyle\qquad\leq\frac{1}{n}\sup_{f\in{F}_{\operatorname{inv}}(C,D)}\|f\|_{H_{0}}\,\mathrm{E}^{\frac{1}{2}}\bigg{[}\sum_{i,j=1}^{n}s_{i}s_{j}k_{p_{0}}(x_{i},x_{j})\bigg{]}$
$\displaystyle\qquad\leq\frac{1}{n}\sup_{f\in{F}_{\operatorname{inv}}(C,D)}\|f\|_{H_{0}}\bigg{(}\sum_{i=1}^{n}k_{p_{0}}(x_{i},x_{i})\bigg{)}^{\frac{1}{2}}$
$\displaystyle\qquad\leq\frac{B}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}(C,D)}\|K_{W_{1}}K_{b_{1}}K_{\sigma_{1}}\cdots
K_{W_{L}}K_{b_{L}}g\|_{H_{0}}$
$\displaystyle\qquad\leq\frac{B}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}(C,D)}\bigg{(}\prod_{j=1}^{L}\|K_{W_{j}}\|\|K_{b_{j}}\|\|K_{\sigma_{j}}\|\bigg{)}\|g\|_{H_{L}},$
(7)

where the third inequality is derived by the Jensen’s inequality. By Lemma A,
we obtain the final result. $\Box$

Lemma 4 Let $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $s>d/2$ and $p_{j}=p$ for
$j=0,\ldots,L$. Then, we have $\|{p}/({p\circ
W_{j}^{*}})\|_{\infty}\leq{\max\\{1,{\|W_{j}\|^{2s}}\\}}$.

Proof  By the definition of $p$, we have

$\displaystyle\bigg{\|}\frac{p}{p\circ W_{j}^{*}}\bigg{\|}_{\infty}$
$\displaystyle=\sup_{\omega\in\mathbb{R}^{d}}\bigg{|}\frac{p(\omega)}{p(W_{j}^{*}\omega)}\bigg{|}=\sup_{\omega\in\mathbb{R}^{d}}\bigg{|}\bigg{(}\frac{1+\|W_{j}^{*}\omega\|^{2}}{1+\|\omega\|^{2}}\bigg{)}^{s}\bigg{|}\leq\max\\{1,\|W_{j}\|^{2s}\\}.$

$\Box$

Theorem 8 The Rademacher complexity
$\hat{R}_{n}(\mathbf{x},F_{\operatorname{inj}}(C,D))$ is bounded as

$\displaystyle\hat{R}_{n}(\mathbf{x},F_{\operatorname{inj}}(C,D)))\leq\frac{B\|g\|_{H_{L}}}{\sqrt{n}}\sup_{W_{j}\in\mathcal{W}_{j}(C,D)}\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}.$

Proof  For $h\in H_{j}$, we have

$\displaystyle\widehat{({h}\circ W_{j})}(\omega)$
$\displaystyle=\int_{\mathbb{R}^{d_{j-1}}}h(W_{j}x)\mathrm{e}^{-\mathrm{i}x\cdot\omega}\mathrm{d}x=\int_{\mathcal{R}(W_{j})}h(x)\mathrm{e}^{-\mathrm{i}x\cdot
W_{j}^{-*}\omega}\mathrm{d}x\frac{1}{|\operatorname{det}(R_{j})|}=\frac{\hat{h}(W_{j}^{-*}\omega)}{|\operatorname{det}(R_{j})|},$

where $W_{j}=Q_{j}R_{j}$ is the QR decomposition of $W_{j}$ and we regard
$W_{j}:\mathbb{R}^{d_{j-1}}\to\mathcal{R}(W_{j})$. Since
$|\operatorname{det}(R_{j})|=(\operatorname{det}(R_{j}^{*}R_{j}))^{1/2}=(\operatorname{det}(W_{j}^{*}W_{j}))^{1/2}$,
the norm of the Koopman operator is bounded as

$\displaystyle\|K_{W_{j}}{h}\|^{2}_{H_{j-1}}$
$\displaystyle=\int_{\mathbb{R}^{d_{j-1}}}\frac{|\hat{h}(W_{j}^{-*}\omega)|^{2}}{\operatorname{det}(W_{j}^{*}W_{j})p_{j-1}(\omega)}\mathrm{d}\omega=\int_{\mathcal{R}(W_{j})}\frac{|\hat{h}(\omega)|^{2}}{\operatorname{det}(W_{j}^{*}W_{j})^{1/2}p_{j-1}(W_{j}^{*}\omega)}\mathrm{d}\omega$
$\displaystyle\leq\|h|_{\mathcal{R}(W_{j})}\|_{H_{p_{j}}(\mathcal{R}(W_{j}))}^{2}\sup_{\omega\in\mathcal{R}(W_{j})}\bigg{|}\frac{p_{j}(\omega)}{p_{j-1}(W_{j}^{*}\omega)}\bigg{|}\frac{1}{\operatorname{det}(W_{j}^{*}W_{j})^{1/2}}.$
(8)

Thus, we have

$\displaystyle\|f\|_{H_{0}}$
$\displaystyle=\|K_{W_{1}}f_{1}\|_{H_{0}}\leq\|f_{1}|_{\mathcal{R}(W_{1})}\|_{H_{p_{1}}(\mathcal{R}(W_{1}))}\sup_{\omega\in\mathcal{R}(W_{1})}\bigg{|}\frac{p_{1}(\omega)}{p_{0}(W_{1}^{*}\omega)}\bigg{|}^{1/2}\frac{1}{\operatorname{det}(W_{1}^{*}W_{1})^{1/4}}$
$\displaystyle=G_{1}\|f_{1}\|_{H_{1}}\sup_{\omega\in\mathcal{R}(W_{1})}\bigg{|}\frac{p_{1}(\omega)}{p_{0}(W_{1}^{*}\omega)}\bigg{|}^{1/2}\frac{1}{\operatorname{det}(W_{1}^{*}W_{1})^{1/4}}$
$\displaystyle\leq
G_{1}\|K_{\sigma_{1}}\|_{H_{1}}\|K_{W_{2}}f_{2}\|_{H_{1}}\sup_{\omega\in\mathcal{R}(W_{1})}\bigg{|}\frac{p_{1}(\omega)}{p_{0}(W_{1}^{*}\omega)}\bigg{|}^{1/2}\frac{1}{\operatorname{det}(W_{1}^{*}W_{1})^{1/4}}.$

Applying the inequality (8) iteratively, we obtain

$\displaystyle\|f\|_{H_{0}}\leq\prod_{j=1}^{L}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\,\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}.$
(9)

Applying the inequality (9) to $\|f\|_{H_{0}}$ in the inequality (7) completes
the proof. $\Box$

Lemma 9 Let $p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s_{j}}$ for $s_{j}>d_{j}/2$
and for $j=0,\ldots,L$. Let $s_{j}\geq s_{j-1}$. Then, we have
$\|{p_{j}}/({p_{j-1}\circ
W_{j}^{*}})\|_{\mathcal{R}(W_{j}),\infty}\leq{\max\\{1,{\|W_{j}\|^{2s_{j-1}}}\\}}$.

Proof  By the definition of $p_{j}$ and the assumption of $s_{j}\geq s_{j-1}$,
we have

$\displaystyle\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}$
$\displaystyle=\sup_{\omega\in\mathcal{R}(W_{j})}\bigg{|}\frac{p_{j}(\omega)}{p_{j-1}(W_{j}^{*}\omega)}\bigg{|}=\sup_{\omega\in\mathcal{R}(W_{j})}\bigg{|}\frac{(1+\|W_{j}^{*}\omega\|^{2})^{s_{j-1}}}{(1+\|\omega\|^{2})^{s_{j}}}\bigg{|}$
$\displaystyle\leq\sup_{\omega\in\mathcal{R}(W_{j})}\bigg{|}\frac{(1+\|W_{j}^{*}\omega\|^{2})^{s_{j-1}}}{(1+\|\omega\|^{2})^{s_{j-1}}}\bigg{|}$
$\displaystyle\leq\max\\{1,\|W_{j}\|^{2s_{j-1}}\\}\sup_{\omega\in\mathcal{R}(W_{j})}\bigg{|}\bigg{(}\frac{1+\|\omega\|^{2}}{1+\|\omega\|^{2}}\bigg{)}^{s_{j-1}}\bigg{|}$
$\displaystyle=\max\\{1,\|W_{j}\|^{2s_{j-1}}\\}.$

$\Box$

Lemma 10 Assume $p_{j}(\omega_{1}+\omega_{2})\leq p_{j}(\omega_{1})$ for
$\omega_{1}\in\mathcal{R}(W_{j})$ and
$\omega_{2}\in\mathcal{R}(W_{j})^{\perp}$. Then, $G_{j}\leq
G_{j,0}\|f_{j}|_{\mathcal{R}(W_{j})}\cdot
f_{j}|_{\mathcal{R}(W_{j})^{\perp}}\|_{H_{j}}/\|f_{j}\|_{H_{j}}$, where
$G_{j,0}^{2}=1/\int_{\mathcal{R}(W_{j})^{\perp}}|\hat{f_{j}}(\omega)|^{2}\mathrm{d}\omega$.

Proof  By the definition of $G_{j,0}$, we have

$\displaystyle\|f_{j}\|_{H_{p_{j}}(\mathcal{R}(W_{j}))}^{2}$
$\displaystyle=\int_{\mathcal{R}(W_{j})}|\hat{f_{j}}(\omega)|^{2}\frac{1}{p_{j}(\omega)}\mathrm{d}\omega$
$\displaystyle=G_{j,0}^{2}\int_{\mathcal{R}(W_{j})}|\hat{f_{j}}(\omega_{1})|^{2}\frac{1}{p_{j}(\omega_{1})}\mathrm{d}\omega_{1}\int_{\mathcal{R}(W_{j})^{\perp}}|\hat{f_{j}}(\omega_{2})|^{2}\mathrm{d}\omega_{2}$
$\displaystyle=G_{j,0}^{2}\int_{\mathcal{R}(W_{j})}\int_{\mathcal{R}(W_{j})^{\perp}}|\hat{f_{j}}(\omega_{1})|^{2}|\hat{f_{j}}(\omega_{2})|^{2}\frac{1}{p_{j}(\omega_{1}+\omega_{2})}\frac{p_{j}(\omega_{1}+\omega_{2})}{p_{j}(\omega_{1})}\mathrm{d}\omega_{2}\mathrm{d}\omega_{1}$
$\displaystyle\leq
G_{j,0}^{2}\int_{\mathcal{R}(W_{j})}\int_{\mathcal{R}(W_{j})^{\perp}}|\hat{f_{j}}(\omega_{1})\hat{f_{j}}(\omega_{2})|^{2}\frac{1}{p_{j}(\omega_{1}+\omega_{2})}\mathrm{d}\omega_{2}\mathrm{d}\omega_{1}$
$\displaystyle=G_{j,0}^{2}\int_{\mathbb{R}^{d_{j}}}|\widehat{\tilde{f_{j}}}(\omega)|^{2}\frac{1}{p_{j}(\omega)}\mathrm{d}\omega=G_{j,0}^{2}\|\tilde{f_{j}}\|_{H_{j}}^{2}=G_{j,0}\|f_{j}\|_{H_{j}}^{2}\frac{\|\tilde{f_{j}}\|^{2}_{H_{j}}}{\|{f_{j}}\|^{2}_{H_{j}}},$

where $\tilde{h}(x)=h(x_{1})h(x_{2})$ for $x=x_{1}+x_{2}$,
$x_{1}\in\mathcal{R}(W_{j})$, and $x_{2}\in\mathcal{R}(W_{j})^{\perp}$. Note
that since $\mathcal{R}(W_{j})$ and $\mathcal{R}(W_{j})^{\perp}$ are
orthogonal,
$\hat{h}(\omega_{1})\hat{h}(\omega_{2})=\widehat{\tilde{h}}(\omega)$. $\Box$

Proposition 14 Let $p_{j}(\omega)=1/(1+\|\omega\|^{2})^{s_{j}}$ with
$s_{j}\in\mathbb{N}$, $s_{j}\geq s_{j-1}$, and $s_{j}>d_{j}/2$. Let $\psi_{j}$
be a function satisfying $\psi_{j}(x)=\psi_{j,1}(x_{1})$ for some
$\psi_{j,1}\in H_{p_{j-1}}(\operatorname{ker}(W_{j}))$, where $x=x_{1}+x_{2}$
for $x_{1}\in\operatorname{ker}(W_{j})$ and
$x_{2}\in\operatorname{ker}(W_{j})^{\perp}$. Then, we have

$\displaystyle\hat{R}_{n}(\mathbf{x},{F}_{\mathrm{r}}(C,D)))\leq\frac{B\|{g}\|_{H_{L}}}{\sqrt{n}}\sup_{{W}_{j}\in\mathcal{W}_{\operatorname{r},j}(C,D)}O\bigg{(}\prod_{j=1}^{L}\max\\{1,\|W_{j}\|^{s_{j-1}}\\}\frac{G_{j}\|K_{\sigma_{j}}\|}{|{\operatorname{det}(W_{\operatorname{r},j})}|^{1/2}}\bigg{)}.$

Proof  For $h\in H_{j}$, we have
$\|\tilde{K}_{W_{j}}h\|^{2}_{H_{j-1}}=\sum_{|\alpha|\leq
s_{j-1}}\|\partial^{\alpha}(\psi_{j}\cdot h\circ
W_{j})\|_{L^{2}(\mathbb{R}^{d_{j-1}})}^{2}$, where the directions of the
derivatives are along the directions of $\operatorname{ker}(W_{j})^{\perp}$
and $\operatorname{ker}(W_{j})$. By the Leibniz rule,
$\partial^{\alpha}(\psi_{j}\cdot h\circ W_{j})(x)$ is written as the finite
weighted sum of $\partial^{\beta}\psi_{j}(x)\partial^{\gamma}(h\circ
W_{j})(x)$ for some $\beta,\gamma\in\mathbb{N}^{d}$, $\beta+\gamma=\alpha$. We
have

$\displaystyle\int_{\mathbb{R}^{d_{j-1}}}|\partial^{\beta}\psi_{j}(x)\partial^{\gamma}(h\circ
W_{j})(x)|^{2}\mathrm{d}x\leq\|W_{j}\|^{2|\gamma|}\int_{\mathbb{R}^{d_{j-1}}}|\partial^{\beta}\psi_{j}(x)(\partial^{\gamma}h)(W_{j}x)|^{2}\mathrm{d}x.$
(10)

In addition, let $\phi$ be a function satisfying $\phi(x)=\phi_{1}(x_{1})$ for
some $\phi_{1}\in H_{p_{j-1}}(\operatorname{ker}(W_{j}))$, where
$x=x_{1}+x_{2}$ for $x_{1}\in\operatorname{ker}(W_{j})$ and
$x_{2}\in\operatorname{ker}(W_{j})^{\perp}$. Let $u\in
H_{p_{j-1}}(\mathbb{R}^{d_{j-1}})$. Then, we have

$\displaystyle\int_{\mathbb{R}^{d_{j-1}}}|\phi(x)u(W_{j}x)|^{2}\mathrm{d}x$
$\displaystyle=\int_{\operatorname{ker}(W_{j})}\int_{\operatorname{ker}(W_{j})^{\perp}}|\phi_{1}(x_{1})u(W_{j}x_{2})|^{2}\mathrm{d}x_{2}\mathrm{d}{x_{1}}$
$\displaystyle=\int_{\operatorname{ker}(W_{j})}|\phi_{1}(x_{1})|^{2}\mathrm{d}x_{1}\int_{\operatorname{ker}(W_{j})^{\perp}}|u(W_{j}x_{2})|^{2}\mathrm{d}x_{2}$
$\displaystyle=\|\phi_{1}\|_{L^{2}(\operatorname{ker}(W_{j}))}\int_{\operatorname{ker}(W_{j})^{\perp}}|u(W_{j}x_{2})|^{2}\mathrm{d}x_{2}.$
(11)

Combining Eqs. (10) and (11), we obtain

$\displaystyle\int_{\mathbb{R}^{d_{j-1}}}|\partial^{\beta}\psi_{j}(x)(\partial^{\gamma}h\circ
W_{j})(x)|^{2}\mathrm{d}x\leq\|W_{j}\|^{2|\gamma|}\,\|\partial^{\beta}\psi_{j}\|_{L^{2}(\operatorname{ker}(W_{j}))}\int_{\operatorname{ker}(W_{j})^{\perp}}|(\partial^{\gamma}h)(W_{j}x)|^{2}\mathrm{d}x$
$\displaystyle\qquad\leq\|W_{j}\|^{2|\gamma|}\,\|\partial^{\beta}\psi_{j}\|_{L^{2}(\operatorname{ker}(W_{j}))}\frac{1}{\operatorname{det}(W_{\operatorname{r},j})}\int_{\operatorname{ker}(W_{j})^{\perp}}|\partial^{\gamma}h(x)|^{2}\mathrm{d}x.$

Since $s_{j}\geq s_{j-1}$, we have $\sum_{|\alpha|\leq
s_{j-1}}\|\partial^{\alpha}h\|^{2}\leq\sum_{|\alpha|\leq
s_{j}}\|\partial^{\alpha}h\|^{2}$. Therefore, setting $h=f_{j}$, we have

$\displaystyle\|\tilde{K}_{W_{j}}f_{j}\|^{2}_{H_{j-1}}\leq
O\bigg{(}\frac{G_{j}}{\operatorname{det}(W_{{\operatorname{r},j}})}\max\\{1,\|W_{j}\|^{2s_{j}}\\}\bigg{)}\|{f_{j}}\|_{H_{j}},$

which completes the proof of the proposition. $\Box$

Proposition 16 Let
$\tilde{\mathbf{x}}=(\tilde{x}_{1},\ldots,\tilde{x}_{n})\in(\mathbb{R}^{d_{l}})^{n}$.
Let $v_{n}(\omega)=\sum_{i=1}^{n}s_{i}(\omega)k_{p_{0}}(\cdot,x_{i})$,
$\tilde{v}_{n}(\omega)=\sum_{i=1}^{n}s_{i}(\omega)k_{p_{l}}(\cdot,\tilde{x}_{i})$,
and $\gamma_{n}=\|v_{n}\|_{H_{0}}/\|\tilde{v}_{n}\|_{H_{l}}$. Then, we have

$\displaystyle\hat{R}_{n}(\mathbf{x},F_{l,\operatorname{comb}}(C,D))$
$\displaystyle\leq\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{l}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}$
$\displaystyle\quad\cdot\bigg{(}\hat{R}_{n}(\tilde{\mathbf{x}},F_{l+1:L})+\frac{B}{\sqrt{n}}\inf_{h_{1}\in
F_{l+1:L}}\mathrm{E}^{\frac{1}{2}}\bigg{[}\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}h_{1}-\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}\bigg{\|}_{H_{l}}^{2}\bigg{]}\bigg{)}.$

Proof  To simplify the notation, let

$\beta_{j}=\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}.$

By the reproducing property of $H_{0}$ and the Cauchy–Shwartz inequality, we
have

$\displaystyle\hat{R}_{n}(\mathbf{x},F_{l,\operatorname{comb}}(C,D))=\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{l,\operatorname{comb}}(C,D)}\sum_{i=1}^{n}s_{i}f(x_{i})\bigg{]}=\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{l,\operatorname{comb}}(C,D)}\left\langle
v_{n},f\right\rangle_{H_{0}}\bigg{]}$
$\displaystyle\leq\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{l,\operatorname{comb}}(C,D)}\|v_{n}\|_{H_{0}}\|K_{W_{1}}K_{b_{1}}K_{\sigma_{1}}\cdots
K_{W_{l}}K_{b_{l}}K_{\sigma_{l}}K_{W_{l+1}}K_{b_{l+1}}K_{\sigma_{l+1}}\cdots
K_{W_{L}}K_{b_{L}}g\|_{H_{0}}\bigg{]}$
$\displaystyle\leq\frac{1}{n}\mathrm{E}\bigg{[}\sup_{f\in{F}_{l,\operatorname{comb}}(C,D)}\|v_{n}\|_{H_{0}}\prod_{j=1}^{l}\bigg{\|}\frac{p_{j}}{p_{j-1}\circ
W_{j}^{*}}\bigg{\|}_{\mathcal{R}(W_{j}),\infty}^{1/2}\frac{G_{j}\|K_{\sigma_{j}}\|}{{\operatorname{det}({W_{j}^{*}W_{j})}}^{1/4}}$
$\displaystyle\qquad\qquad\qquad\qquad\cdot\|K_{W_{l+1}}K_{b_{l+1}}K_{\sigma_{l+1}}\cdots
K_{W_{L}}K_{b_{L}}g\|_{H_{l}}\bigg{]}$
$\displaystyle\leq\frac{1}{n}\mathrm{E}\bigg{[}\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{l}\beta_{j}\sup_{h_{2}\in
F_{l+1:L}}\left\langle\tilde{v}_{n},\frac{\|h_{2}\|_{H_{l}}\|v_{n}\|_{H_{0}}}{\|\tilde{v}_{n}\|_{H_{l}}^{2}}\tilde{v}_{n}\right\rangle_{H_{l}}\bigg{]}$
$\displaystyle=\frac{1}{n}\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{l}\beta_{j}\mathrm{E}\bigg{[}\sup_{h_{2}\in
F_{l+1:L}}\bigg{(}\left\langle\tilde{v}_{n},h\right\rangle_{H_{l}}+\left\langle\tilde{v}_{n},\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\right\rangle_{H_{l}}\bigg{)}\bigg{]}$
$\displaystyle\leq\frac{1}{n}\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{L}\beta_{j}\mathrm{E}\bigg{[}\sup_{h_{1}\in
F_{l+1:L}}\left\langle\tilde{v}_{n},h_{1}\right\rangle_{H_{l}}+\sup_{h_{2}\in
F_{l+1:L}}\left\langle\tilde{v}_{n},\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\right\rangle_{H_{l}}\bigg{]}$
$\displaystyle\leq\sup_{\begin{subarray}{c}W_{j}\in\mathcal{W}_{j}(C,D)\\\
(j=1,\ldots,l)\end{subarray}}\prod_{j=1}^{L}\beta_{j}\bigg{(}\hat{R}_{n}(\mathbf{x},F_{l+1:L})+\frac{1}{n}\mathrm{E}\bigg{[}\|\tilde{v}_{n}\|_{H_{l}}\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\bigg{\|}_{H_{l}}\bigg{]}\bigg{)}$

for any $h\in F_{l+1:L}$. Moreover, again by the Cauchy–Schwartz inequality,
we have

$\displaystyle\mathrm{E}\bigg{[}\|\tilde{v}_{n}\|_{H_{l}}\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\bigg{\|}_{H_{l}}\bigg{]}$
$\displaystyle\leq\mathrm{E}^{\frac{1}{2}}[\|v_{n}\|_{H_{l}}^{2}]\mathrm{E}^{\frac{1}{2}}\bigg{[}\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\bigg{\|}^{2}_{H_{l}}\bigg{]}$
$\displaystyle\leq B\sqrt{n}\mathrm{E}^{\frac{1}{2}}\bigg{[}\sup_{h_{2}\in
F_{l+1:L}}\bigg{\|}\frac{\|h_{2}\|_{H_{l}}\gamma_{n}}{\|\tilde{v}_{n}\|_{H_{l}}}\tilde{v}_{n}-h\bigg{\|}^{2}_{H_{l}}\bigg{]},$

where the second inequality is derived in the same manner as the proof of
Theorem 3. Since $h\in F_{l+1:L}$ is arbitrary, we obtain the final result.
$\Box$

##  Appendix B Details of Remark 13

The factor $\|\tilde{g}\|_{\tilde{H}_{L}}$ grows as $\Omega$ becomes large.
Indeed, if $p(\omega)=1/(1+\|\omega\|^{2})^{s}$ for $s\in\mathbb{N}$, then By
the Leibniz rule, we have

$\displaystyle\|\tilde{g}\|_{\tilde{H}_{L}}^{2}$
$\displaystyle=\sum_{|\alpha|\leq s}\|\partial^{\alpha}(\psi\cdot
g)\|_{L^{2}(\mathbb{R}^{\delta_{L}})}^{2}$
$\displaystyle=\|g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\|\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}+\|g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\sum_{|\alpha|=1}\|\partial^{\alpha}\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}$
$\displaystyle\quad+\sum_{|\alpha|=1}\|\partial^{\alpha}g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\|\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}+\|g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\sum_{|\alpha|=2}\|\partial^{\alpha}\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}$
$\displaystyle\quad+2\bigg{(}\sum_{|\alpha|=1}\|\partial^{\alpha}g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\bigg{)}\bigg{(}\sum_{|\alpha|=1}\|\partial^{\alpha}\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}\bigg{)}+\sum_{|\alpha|=2}\|\partial^{\alpha}g\|^{2}_{L^{2}(\mathbb{R}^{d_{L}})}\|\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}\cdots.$

The factor $\|\psi\|^{2}_{L^{2}(\mathbb{R}^{\delta_{L-1}})}$ becomes large as
the volume of $\Omega$ gets large. Thus, under the condition that
$\|\partial^{\alpha}\psi\|$ does not change, $\|\tilde{g}\|_{\tilde{H}_{L}}$
becomes large as $\Omega$ gets large.

##  Appendix C Details of Remark 17

We can combine our Koopman-based approach with the existing “peeling”
approach. For $1\leq l\leq L$, let $F^{\operatorname{ReLU}}_{l}(C_{1})$ be the
set of $l$-layer ReLU networks where the Frobenius norms of
$W_{1},\ldots,W_{l}$ are bounded by $C_{1}$, considered by Neyshabur et al.
(2015). Let $\tilde{F}_{1:l}$ be the set of functions defined in the same
manner as Eq. (6), except for replacing $\sigma_{l}$ with $g\in H_{l}$. In
addition, let
$\tilde{F}_{1:l,\operatorname{inj}}(C_{2},D)=\\{f\in\tilde{F}_{1:l}\,\mid\,W_{j}\in\mathcal{W}_{j}(C_{2},D)\\}$.
We combine $F^{\operatorname{ReLU}}_{L-l}(C_{1})$ and
$\tilde{F}_{1:l,\operatorname{inj}}(C_{2},D)$, and we define
$F^{\operatorname{ReLU}}_{1:l,\operatorname{inj}}(C_{1},C_{2},D)=\\{h\circ
f\,\mid\,h\in F^{\operatorname{ReLU}}_{L-l}(C_{1}),\
f\in\tilde{F}_{1:l,\operatorname{inj}}(C_{2},D)\\}$. Then, applying Theorem 1
by Neyshabur et al. (2015), we can bound the complexity of $L$-layer networks
using that of $(L-1)$-layer networks and the Frobenius norm of $W_{L}$ (see
Eq. (8) by Golowich et al. (2018)). As a result, we obtain

$\displaystyle\hat{R}_{n}(\mathbf{x},F^{\operatorname{ReLU}}_{1:l,\operatorname{inj}}(C_{1},C_{2},D))$
$\displaystyle\leq
2^{L-l}\prod_{j=l+1}^{L}\|W_{j}\|_{\mathrm{F}}\hat{R}_{n}(\mathbf{x},\tilde{F}_{1:l,\operatorname{inj}}(C_{2},D))$
$\displaystyle\leq
2^{L-l}\|g\|_{H_{l}}\bigg{(}\prod_{j=l+1}^{L}\|W_{j}\|_{\mathrm{F}}\bigg{)}\,\bigg{(}\prod_{j=1}^{l}\frac{G_{j}\|K_{\sigma_{j}}\|\|W_{j}\|^{s_{j}}}{\operatorname{det}(W_{j}^{*}W_{j})^{1/4}}\bigg{)}.$

We can also apply other peeling approaches in the same manner as the above
case.

##  Appendix D 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.

###  D.1 Validity of the bound (Synthetic data)

We constructed a network $f_{\theta}(x)=g(W_{2}\sigma(W_{1}x+b_{1})+b_{2})$,
where $W_{1}\in\mathbb{R}^{3\times 3}$, $W_{2}\in\mathbb{R}^{6\times 3}$,
$b_{1}\in\mathbb{R}^{3}$, $b_{2}\in\mathbb{R}^{6}$,
$\theta=(W_{1},b_{1},W_{2},b_{2})$,
$\sigma(x)=((1+\alpha)x+(1-\alpha)x\,\mathrm{erf}(\mu(1-\alpha)x))/2$, and
$g(x)=\mathrm{e}^{-\|x\|^{2}}$. Here, $\mathrm{erf}$ is the Gaussian error
function, and $\sigma$ is a smooth version of Leaky ReLU proposed by Biswas et
al. (2022). We set $\alpha=\mu=0.5$. For training the network, we used
$n=1000$ samples $x_{i}\ (i=1,\ldots,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., 2015), and we used the
SGD for the optimizer. In addition, we set the error function as
$l_{\theta}(x,y)=|f_{\theta}(x)-y|^{2}$, and added the regularization term
$0.01(\prod_{j=1}^{2}\operatorname{det}(W_{j}^{*}W_{j})^{-1/2}+10\prod_{j=1}^{2}\|W_{j}\|)$.
We added this regularization term since, according to our bound, both the
determinant and the operator norm of $W_{j}$ should be small for achieving a
small generalization error. The generalization error here means
$|\mathrm{E}[l_{{\theta}}(x,t(x))]-1/n\sum_{i=1}^{n}l_{{\theta}}(x_{i},t(x_{i}))|$,
which is compared to our bound
$O(\prod_{j=1}^{L}\|W_{j}\|^{s_{j}}/(\mathrm{det}(W_{j}^{*}W_{j})^{1/4}))$ in
Figure 1 (a). Here, we set $s_{j}=(d_{j}+0.1)/2$.

###  D.2 Validity of the bound (MNIST)

We constructed a network
$f_{\theta}(x)=g(W_{4}\sigma(W_{3}\sigma(W_{2}\sigma(W_{1}x+b_{1})+b_{2})+b_{3})+b_{4})$
with dense layers, where $W_{1}\in\mathbb{R}^{1024\times 784}$,
$W_{2}\in\mathbb{R}^{2048\times 1024}$, $W_{3}\in\mathbb{R}^{2048\times
2048}$, $W_{4}\in\mathbb{R}^{10\times 2048}$, $b_{1}\in\mathbb{R}^{1024}$,
$b_{2}\in\mathbb{R}^{2048}$, $b_{3}\in\mathbb{R}^{2048}$,
$b_{4}\in\mathbb{R}^{10}$,
$\theta=(W_{1},b_{1},W_{2},b_{2},W_{3},b_{3},W_{4},b_{4})$, $\sigma$ is the
same function as Section D.1, and $g$ is the softmax. See Remark 1 for the
validity of our bound for the case where $g$ is the softmax. For training the
network, we used only $n=1000$ samples to create a situation where the model
is hard to generalize. We consider the regularization term
$\lambda_{1}\|W_{j}\|+\lambda_{2}/\operatorname{det}(I+W_{j}^{*}W_{j})$, where
$\lambda_{1}=\lambda_{2}=0.01$ to make both the norm and the determinant of
$W_{j}$ small (thus, makes our bound small). Based on the observation in the
last part of Subsection 4.4, we set the regularization term for only $j=1,2$.
The weight matrices are initialized by the orthogonal initialization for
$j=1,2$ and by the samples from a truncated normal distribution for $j=3,4$,
and we used Adam (Kingma & Ba, 2015) for the optimizer. In addition, we set
the error function as the categorical cross-entropy loss.

####  D.2.1 Transformation of signals by lower layers

We also investigated the transformation by lower layers, as we stated in the
last part of Subsection 4.4. We computed $|\cos(\theta)|$, where $\theta$ is
the maximum value of the angles between the output of the second layer and the
directions of singular vectors of $W_{3}$ associated with the singular values
that are larger than $0.1$. The results are illustrated in Figure 2. We can
see that with the regularization based on our bound, as the test accuracy
grows, the value $|\cos(\theta)|$ also grows. This result means that the
signals turn to the directions of the singular vectors of the subsequent
weight matrix associated 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(\theta)|$ do not become large after a sufficiently long learning
process (see also Figure 1 (b)). The results in Figures 1 (b) and 2 are
obtained by three independent runs.

Figure 2: Behavior of the value $|\cos(\theta)|$. Here, $\theta$ is the
maximum value of the angles between the output of the second layer and the
directions of singular vectors of $W_{3}$ associated with the singular values
that are larger than $0.1$.

Figure 3: The ratio $r_{d,j}=\eta_{1,j}/\eta_{d,j}$ of singular values
(condition number) of weight matrices for layers $j=1,2,4$. (Right) Without
regularization (Left) With the regularization based on our bound. Figure 4:
Test accuracy of AlexNet learned by CIFAR-10.

###  D.3 Singular values of the weight matrices

We constructed an AlexNet Krizhevsky et al. (2012) where the ReLU activation
function is replaced by the smooth version of Leaky ReLU ($\sigma$ in Section
D.1) 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 $r_{d,j}$ of
the largest and the smallest singular values (condition number) of the weight
matrices for the network we used in Section D.2. Since the behavior of the
singular values of $W_{3}$ was unstable and did not have clear patterns, we
only show the result for $j=1,2,4$ in Figure 3. We scaled the values for $j=4$
for readability. In the case of the AlexNet, the behavior of singular values
of each weight matrix was different depending on the layer. However, in the
case of the network in Section D.2, without the regularization, the condition
number $r_{d,j}$ stagnates for $j=1,2,4$ through the learning process, and the
test accuracy also stagnates. On the other hand, with the regularization based
on our bound, $r_{d,j}$ becomes small for $j=1,2$ as the learning process
proceeds by virtue of the regularization. We can also see that $r_{d,j}$ grows
for $j=4$ as the learning process proceeds, which makes the angle $\theta$ in
Figure 2 large. As discussed in the last part of 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 1 (c), 3, and 4 are obtained by three
independent runs.