# Length independent generalization bounds for deep SSM architectures with
stability constraints

Dániel Rácz<EMAIL_ADDRESS>
HUN-REN SZTAKI and ELTE
Budapest, Hungary Mihály Petreczky<EMAIL_ADDRESS>
Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL
F-59000 Lille, France Bálint Daróczy<EMAIL_ADDRESS>
HUN-REN SZTAKI
Budapest, Hungary

###### Abstract

Many state-of-the-art models trained on long-range sequences, for example S4,
S5 or LRU, are made of sequential blocks combining State-Space Models (SSMs)
with neural networks. In this paper we provide a PAC bound that holds for
these kind of architectures with _stable_ SSM blocks and does not depend on
the length of the input sequence. Imposing stability of the SSM blocks is a
standard practice in the literature, and it is known to help performance. Our
results provide a theoretical justification for the use of stable SSM blocks
as the proposed PAC bound decreases as the degree of stability of the SSM
blocks increases.

Keywords: generalization bounds, state-space models, stability, Rademacher
complexity

##  1 Introduction

The demand for learning powerful representation of time series have been
present for decades. The problem of modeling long-range sequences, i.e.
sequences with large number of time-steps, is an especially challenging task
of the field. Recurrent Neural Networks (RNNs) have always had a hard time
dealing with long time series, even advanced architectures such as LSTM or GRU
networks did not make a breakthrough. Transformer based architectures managed
to imrpove the results in some cases, however still performed poorly on more
difficult tasks.

Recently, several novel architectures have been published that are
outperforming previous models by a significant margin. The common basis of
these models are the so-called Structured State-Space Models (SSMs), which are
basically dynamical systems of either continuous or discrete time. Some of the
well-performing architectures are the S4 and S5 models and their variants, or
another linear system based model called LRU. These models all contain some
form of SSMs, either linear or nonlinear, and combine them with some sort of
nonlinear transformation from a single nonlinearity to deep neural networks.
These blocks of SSMs and neural networks then may be concatenated resulting in
a deep structure.

These trending architectures are usually validated empirically on commonly
accepted datasets such as the Long Range Arena benchmark. On the other hand,
the theoretical foundations of deep, SSM based structured are yet to be
discovered. One key point of these models is that they are equipped with some
form of stability constraints. For example, the LRU model contains linear SSMs
with a certain exponential parametrization of its coefficient matrices
enforcing stable behavior of the system. This motivates the question:

What is the role of stability in the success of deep SSM architectures for
long-range sequences?

In this paper, we focus on this question and provide a theoretical framework
to analyze the model’s generalization behavior in a rigorous manner. We show
that stability of deep SSM architectures has an influence on their Rademacher
complexity, resulting in a generalization bound that does not depend on the
length of the input sequence. In more details:

  * •

We prove that the Rademacher complexity of a set of SSMs can be upper bounded
by the maximal system norm of the considered systems. We consider two types of
system norms: $H_{2}$ and $\ell_{1}$ norm. These norms defined for dynamical
systems are well-known in control theory, along with their connection to
quadratic stability. This result clearly suggests that enforcing stability at
least up to a certain level is far beyond being a practical necessity and, in
fact, a significant aspect of understanding the essence of these
architectures. Consequently, we consider this point as the main takeaway of
our paper.

  * •

Furthermore, we establish an upper bound on the Rademacher complexity of
multilayer models by introducing the property of Rademacher Contraction for
various components of deep SSM structures, containing multiple separate SSMs
combined with nonlinear transformations in between, which is applicable for
the popular architectures mentioned above.

  * •

Using the previous results we establish a PAC-bound on the generalization
error of deep SSMs. The resulting bound does not depend on the length of the
input sequences, and it only implicitly depends on the depth of the model.

Most of the state-of-the art deep SSM architectures for long range sequences
are covered by our results. Moreover, all our our definitions, theorems and
proofs hold for both continuous and discrete time systems, as well as for both
classification and regression tasks. For the sake of compactness, we stick to
the discrete time representations.

Outline of the paper. In Section 2 we present the related literature, then we
set notations, definitions and our assumptions related to deep SSMs in Section
3. We propose our main result in Section 4. The majority of the proofs and
some additional details are shown in the Appendix.

##  2 Related work.

There are several PAC bounds for either discrete or continuous-time RNNs in
Koiran and Sontag (1998); Sontag (1998); Hanson et al. (2021) by using VC
dimension usually through covering numbers. PAC bounds for RNNs based on
Rademacher complexity were presented in Wei and Ma (2019); Akpinar et al.
(2020); Joukovsky et al. (2021); Chen et al. (2020), while in Zhang et al.
(2018) the authors developed PAC-Bayesian bounds. Bounds for general RNNs are
related to SSMs as Linear Time-Invariant (LTI) dynamical systems are essential
elements almost for all SSMs and they are a special class of RNNs. However all
of the previously mentioned PAC bounds depend on the number of time steps and
the error bounds tend to infinity with the integration time in continuous case
or with the number of time steps in discrete case. That is, these error bounds
are not meaningful for prediction errors on long-range sequences.

PAC bounds for both linear and nonlinear dynamical systems are either consider
problems not applicable to LTI systems (therefore not applicable for SSMs
considered in this paper, see Alquier and Wintenberger (2012); Alquier et al.
(2013); Shalaeva et al. (2020); Haussmann et al. (2021); Marion (2023);
Haddouche and Guedj (2022)), or not length independent (Hanson and Raginsky
(2024)). For example PAC bounds were developed for discrete-time
autoregressive models in Alquier and Wintenberger (2012); Alquier et al.
(2013); Shalaeva et al. (2020), for stochastic differential equations in
Haussmann et al. (2021), for neural ordinary differential equations in Marion
(2023), or for online learning in Haddouche and Guedj (2022). In Hanson and
Raginsky (2024) the authors propose a PAC bound based on Rademacher complexity
for input-affine non-linear systems however their bound is still exponential
in the length of the integration interval.

The generalization bound for single vanilla RNNs in (Chen et al., 2020,
Theorem 2) is an upper bound of the $H_{1}$ norm proposed in this paper, see
e.g. Chellaboina et al. (1999), thus our results based on the $H_{2}$ norm is
tighter. Their bound is consistent with our in case of a single linear RNN
block. Additionally, they assume bounded matrix norms and their bound depends
on the dimension of the representation. In comparison our bound does not
depend on the dimension of the state space and we assume only that the systems
have bounded $H_{2}$ norm, even in case of stacked RNNs.

In Trauger and Tewari (2024) the authors propose a sequence length independent
Rademacher complexity bound for a single layer transformer architecture. For
multi layer transformers they improve slightly the result in Edelman et al.
(2022) however the bound grows logarithmically with the sequence length.

There are some relevant results outside of the field of RNNs or dynamical
systems dealing with the depth of deep neural networks in generalization
bounds Bartlett et al. (2017); Liang et al. (2019); Golowich et al. (2018);
Truong (2022b). In Golowich et al. (2018) the authors derived a depth
independent bound under the condition of bounded Schatten p-norm and a bound
with polynomial dependence on depth for Rademacher complexity for DNNs with
ReLU activations by applying contraction. Similar approaches utilized spectral
norm Bartlett et al. (2017) or Fisher-Rao norm Liang et al. (2019) to
establish bounds with non exponential dependence on depth. In a recent paper
Truong (2022b) the author extends the bound in Golowich et al. (2018) for non
ReLU activations and show that the new, non-vacuous bound is depth
independent.

##  3 Problem setup

In this section, we formally define deep SSM models in way that popular
architectures from the literature are contained, the generalization error and
the concept of PAC bounds. As our results stand for both continuous-time (CT)
and discrete-time (DT) SSMs, in some cases we introduce parallel definitions
corresponding to each case.

Notation. We denote scalars with lowercase characters, vectors with lowercase
bold characters and matrices with uppercase characters. For a matrix $A$ let
$A_{i}$ denote its $i$th row. The symbol $\odot$ denotes the elementwise
product. We use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$ for
$n\in\mathbb{N}$.

For vector valued time dependent functions originating from a finite set, the
notation $\mathbf{u}_{i}^{(j)}(t)$ refers to the $j$th coordinate of the $i$th
function at time $t$. Similarly, in the discrete time case, the notation
$\mathbf{u}_{i}^{(j)}[k]$ refers to the $j$th component of the $i$th time
series at time step $k$.

$\Sigma$ denotes a dynamical system specified in the context. The constant
$n_{\text{in}}$ refers to the dimension of the input sequence, $T$ refers to
its length in time, while $n_{\text{out}}$ is the dimension of the output (not
necessarily a sequence).

Denote by $\ell^{2,2}_{T}(\mathbb{R}^{n})$ and
$\ell^{\infty,\infty}_{T}(\mathbb{R}^{n})$ the Banach spaces generated by the
all finite sequences over $\mathbb{R}^{n}$ of length $T$ with the norm
$\left\lVert\mathbf{u}\right\rVert^{2}_{\ell^{2,2}_{T}(\mathbb{R}^{n})}=\sum_{k=0}^{T-1}\left\lVert\mathbf{u}[k]\right\rVert_{2}^{2}$
and
$\left\lVert\mathbf{u}\right\rVert_{\ell^{\infty,\infty}_{T}(\mathbb{R}^{n})}=\sup\limits_{k=0,\ldots,T-1}\left\lVert\mathbf{u}[k]\right\rVert_{\infty}$
respectively. More generally, denote by $\ell^{2,2}(\mathbb{R}^{n})$ and
$\ell^{\infty,\infty}(\mathbb{R}^{n})$ the Banach spaces generated by the all
inifinite sequences over $\mathbb{R}^{n}$ such that the quantities
$\left\lVert\mathbf{u}\right\rVert^{2}_{\ell^{2,2}(\mathbb{R}^{n})}=\sum_{k=0}^{\infty}\left\lVert\mathbf{u}[k]\right\rVert_{2}^{2}$
and
$\left\lVert\mathbf{u}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n})}=\sup\limits_{k}\left\lVert\mathbf{u}[k]\right\rVert_{\infty}$
are well defined and finite. If
$\mathbf{u}=\mathbf{u}[0]\ldots,\mathbf{u}[T-1]$ is a finite sequence of
length $T$, then we can interpret it as an infinite sequence
$\mathbf{u}=\mathbf{u}[0]\ldots,\mathbf{u}[T-1],0,0,\ldots$; elements of which
are zero after the $T$th element. For a Banach space $\mathcal{X}$,
$B_{\mathcal{X}}(r)=\\{x\in\mathcal{X}\mid\left\lVert
x\right\rVert_{\mathcal{X}}\leq r\\}$ denotes the ball of radius $r>0$
centered in zero.

We use the symbols $E_{(u,y)\sim\mathcal{D}}$, $P_{(u,y)\sim\mathcal{D}}$,
$E_{\mathbf{S}\sim\mathcal{D}^{N}}$ and $P_{\mathbf{S}\sim\mathcal{D}^{N}}$ to
denote expectations and probabilities w.r.t. a probability measure
$\mathcal{D}$ and its $N$-fold product $\mathcal{D}^{N}$ respectively (see
Section 3.2). The notation $\mathbf{S}\sim\mathcal{D}^{N}$ tacitly assumes
that $\mathbf{S}\in(\mathcal{U}\times\mathcal{Y})^{N}$, i.e. $\mathbf{S}$ is
made of $N$ triplets of input and output trajectories.

###  3.1 Deep SSMs

A _State-Space Model (SSM)_ is a discrete-time linear dynamical system of the
form

$\Sigma\begin{cases}&\mathbf{x}[k]=A\mathbf{x}[k-1]+B\mathbf{u}[k],\leavevmode\nobreak\
\mathbf{x}[0]=0\\\ &\mathbf{y}[k]=C\mathbf{x}[k]+D\mathbf{u}[k]\end{cases}$
(1)

where $A\in\mathbb{R}^{n_{x}\times n_{x}},B\in\mathbb{R}^{n_{x}\times
n_{u}},C\in\mathbb{R}^{n_{y}\times n_{x}}$ and $D\in\mathbb{R}^{n_{y}\times
n_{u}}$ are matrices, is some function of $\mathbf{u}[k],\mathbf{x}[k]$, and
$k=1,2,\ldots,T$, where $T$ is the number of time steps. We consider the value
of $T$ to be fixed. The reason behind this is rather technical, namely to
conviniently handle the Pooling layer (see Definition 6). We emphasize that
the generalization bound in Theorem 18 is independent of $T$. For regression
tasks the model does not contain any pooling layer, thus this restriction is
not needed.

Input-output maps of SSMs.  The SSM (1) can be run for finite or infinite
number of time steps, and hence it realizes a sequence to sequence
transformation. SSM induce as sequence to sequence transformations: they map
any input sequence $\mathbf{u}$ of any length (including infinite length) to
the unique output sequence $\mathbf{y}$ of the same length, i.e. an SSM
$\Sigma$ induces the input-output map of $\Sigma$, denoted by
$\mathcal{S}_{\Sigma}$. Moreover, $\mathcal{S}_{\Sigma}$ is causal,
$\mathbf{y}[t]$ depends only on the first $t+1$ inputs. The outputs of SSMs
are linear combinations of past inputs, in fact, input-output maps can be
expressed by a convolution
$\mathbf{y}[k]=\mathcal{S}_{\Sigma}(\mathbf{u})[k]=\sum_{j=0}^{k}H_{j}\mathbf{u}(k-j)$,
where $H_{0}=D$ and $H_{j}=CA^{j-1}B$, $j>0$. That is, SSMs mix inputs along
the time axis, while preserving causality

Stability and input-output maps of SSMs as operators on $\ell^{p,p}$,
$p=\infty,2$. For SSMs to be robust transformations of sequences to sequences,
one needs stability. Stability is one, if not the most important concept used
in dynamical systems and control theory Antoulas (2005). Intuitively, the
solutions of a stable system are continuous in the initial state and input. In
particular, for stable systems, a small perturbation in past inputs will not
result in an increasing error in future outputs.

######  Definition 1 (Antoulas (2005))

SSM of the form (1) is internally stable, if the matrix $A$ is Schur, meaning
all the eigenvalues of $A$ are inside the complex unit disk.

In particular, a sufficient (but not necessary) condition for stability is
that $A$ is a contraction, i.e. $\|A\|_{2}<1$.

A stable SSM $\Sigma$ is not only robust to perturbations, but it is well-
known Antoulas (2005) that its input-output map $\mathcal{S}_{\Sigma}$ acts as
a linear operator
$\ell^{p,p}(\mathbb{R}^{n_{u}})\to\ell^{r,r}(\mathbb{R}^{n_{y}})$, for any
choice $p,r\in\\{\infty,2\\}$, as for any
$\mathbf{u}\in\ell^{p,p}(\mathbb{R}^{n_{u}})$,
$\mathcal{S}_{\Sigma}(\mathbf{u})\in\ell^{r,r}(\mathbb{R}^{n_{y}})$. In
particular, $\mathcal{S}_{\Sigma}$ has a well-defined induced norm as a linear
operator, defined in the usual way,
$\left\lVert\Sigma\right\rVert_{p,r}=\sup_{\mathbf{u}\in\ell^{p,p}(\mathbb{R}^{n_{u}})}\frac{\left\lVert\mathcal{S}_{\Sigma}(\mathbf{u})\right\rVert_{\ell^{r,r}(\mathbb{R}^{n_{y}})}}{\left\lVert\mathbf{u})\right\rVert_{\ell^{r,r}(\mathbb{R}^{n_{y}})}}$.
In this paper, we will use the induced norms
$\left\lVert\Sigma\right\rVert_{2,\infty}$ and
$\left\lVert\Sigma\right\rVert_{\infty,\infty}$, which can be upper bounded by
the following two norms defined on SSMs.

######  Definition 2 (Chellaboina et al. (1999))

For a SSM $\Sigma$ of the form (1) define the $\ell_{1}$ and $H_{2}$ norm of
$\Sigma$, denoted by $\left\lVert\Sigma\right\rVert_{1}$ and
$\left\lVert\Sigma\right\rVert_{2}$ respectively,

$\displaystyle\left\lVert\Sigma\right\rVert_{1}:=\max\limits_{1\leq i\leq
n_{y}}\left\lVert D_{i}\right\rVert_{1}+\sum\limits_{k=0}^{\infty}\left\lVert
C_{i}A^{k}B\right\rVert_{1},\quad\left\lVert\Sigma\right\rVert_{2}:=\sqrt{\left\lVert
D\right\rVert_{F}^{2}+\sum\limits_{k=0}^{\infty}\left\lVert
CA^{k}B\right\rVert_{F}^{2}}$

######  Lemma 3 (Chellaboina et al. (1999))

For a system of form (1)
$\left\lVert\Sigma\right\rVert_{\infty}\leq\left\lVert\Sigma\right\rVert_{1}$
and
$\left\lVert\Sigma\right\rVert_{2,\infty}\leq\left\lVert\Sigma\right\rVert_{2}$.

The norms defined above will play a cruicial role in in the main result of the
paper, as they will allow us to bound the Rademacher complexity of the deep
SSM model.

######  Remark 4 (Computing $\left\lVert\Sigma\right\rVert_{i}$,$i=1,2$)

The norm $\left\lVert\Sigma\right\rVert_{2}$ can be computed by solving
Sylvester equations, for which standard numerical algorithms exist Antoulas
(2005). The computation of $\left\lVert\Sigma\right\rVert_{1}$ is more
involved, it can be computed by taking a sufficiently large finite sum instead
of the infinite sum used in its definition. If $\|A\|_{2}<\beta<1$, then an
easy calculation reveals that
$\left\lVert\Sigma\right\rVert_{1}\leq\|D\|_{2}+\frac{\|B\|_{2}\|C\|_{2}}{1-\beta}$
and
$\left\lVert\Sigma\right\rVert_{2}\leq\sqrt{\|D\|_{F}^{2}+\frac{n_{y}\|B\|_{2}^{2}\|C\|_{2}^{2}}{1-\beta^{2}}}$.

Relationship with continuous-time models. In the literature, SSMs are often
derived by discretizing a continuous-time linear differential equation in time
(e.g. Gu and Dao (2023) and references therein). If the discretization step
$\Delta$ is a fixed constant, then we obtain time-invariant linear system of
the form (1). In some models, the discretization step can depend on the input
and state of the continuous-time state-space representation. In the latter
case, one still obtains a linear discrete-time state-space representation, but
then the matrices describing the system equation depend on the current input
and state, and hence the matrices are time-dependent. In this paper we will
stick to time-invariant models (1), for the sake of simplicity.

Deep SSM models. In this paper, we focus our attention to deep SSM models
comoposed of multiple linear SSMs. The main reason is that most of the state-
of-the-art architectures for long-range sequences are based on linear system.
A key characteristics of deep SSM models are the combination of SSM layers
with nonlinear transformations, typically some kind of neural network that is
constant in time. The general definition we use is the following.

###### Definition 5

A DT-SSM block (or simply SSM block) is a function
$f^{\text{DTB}}:\ell^{p,q}(\mathbb{R}^{n_{u}})\to\ell^{r,s}(\mathbb{R}^{n_{u}})$
that is composed of a stable SSM followed by a nonlinear transformation that
is constant in time. That is,
$f^{\text{DTB}}(\mathbf{u})[k]=g(\mathcal{S}_{\Sigma}(\mathbf{u})[k])+\alpha\mathbf{u}[k]$
for some $g:\mathbb{R}^{n_{u}}\to\mathbb{R}^{n_{u}}$ for all
$k\in\left[T\right]$. The function $g$ is represented as either an MLP or a
GLU network (see Definitions 7 and 8).

We incorporate $\alpha$ so that the definition covers residual connections
(typically $\alpha$ is either 1 or 0). The previous definition is inspired by
the series of popular architectures mentioned in the introduction. Similarly,
the definition of deep SSM models is also based on these architectures. A deep
SSM model consists of SSM blocks along with an encoder, and a decoder
transformation preceded by a time-pooling layer. In practice, it is common to
apply some normalization techniques, such as batch or layer normalization. As
they are not essential for our result, we omit them from the definition.
Indeed, once training is finished, a normalization layer corresponds to
applying a neural network with linear activation function, i.e., it can be
integrated into one of the neural network layer. Since the objective of PAC
bounds is to bound the generalization error for already trained models, for
the purposes of PAC bounds normalization layers can be viewed as an additional
neural network layer.

###### Definition 6

A discrete time deep SSM model for classification is a function
$f:\ell^{p,q}(\mathbb{R}^{n_{\text{in}}})\to\mathbb{R}^{n_{\text{out}}}$ of
the form $f=f^{\text{Dec}}\circ f^{\text{Pool}}\circ
f^{\text{B}_{L}}\circ\ldots\circ f^{\text{B}_{1}}\circ f^{\text{Enc}}$. The
functions $f^{\text{Enc}}$ and $f^{\text{Dec}}$ are linear transformations
which are constant in time, while $f^{\text{B}_{i}}$ is a DT-SSM block for all
$i$. By pooling we mean the operation
$f^{\text{Pool}}(\mathbf{u})=\frac{1}{T}\sum_{k=1}^{T}\mathbf{u}[k]$, an
avarage pooling over the time axis.
For regression tasks, we omit the pooling layer and define the Decoder as a
linear transformation that is identical for all time steps.

Model | SSM | Block
---|---|---
S4 Gu et al. (2021) |  LTI, $A=\Lambda-PQ^{*}$ block-diagonal |  SSM + nonlinear activation
S4D Gu et al. (2022) |  LTI, $A=-\text{exp}(A_{Re})+i\cdot A_{Im}$ block-diagonal |  SSM + nonlinear activation
S5 Smith et al. (2022) | LTI, diagonal $A$ |  SSM + nonlinear activation
LRU Orvieto et al. (2023) |  LTI, diagonal $A$ complex exponential parametrization |  SSM + MLP skip connection
Table 1: Summary of popular deep SSM models.

The Encoder and Decoder layers are given by the weight matrices
$W^{\text{Enc}}$ and $W^{\text{Dec}}$. Therefore
$f^{\text{Enc}}(\mathbf{u})[k]=W^{\text{Enc}}\mathbf{u}[k]$ and
$f^{\text{Dec}}(\mathbf{u})[k]=W^{\text{Dec}}\mathbf{u}[k]$ for all $k\in[T]$.
We use the slightly abused notations $f^{\text{Enc}}\equiv\langle
W^{\text{Enc}},\cdot\rangle$ and $f^{\text{Dec}}\equiv\langle
W^{\text{Dec}}\cdot\rangle$.

As for the Neural Network components of an SSM block, we consider the
following two variants.

######  Definition 7 (MLP layer)

An MLP layer is a function from $\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ to
$\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ that is induced by applying a deep
neural network $f:\mathbb{R}^{n_{u}}\to\mathbb{R}^{n_{u}}$ for each timestep.
A neural network of $L$ layer is a function of the form
$f=f_{W_{1},\mathbf{b}_{1}}\circ\ldots\circ f_{W_{L},\mathbf{b}_{L}}\circ
g_{W_{L+1},\mathbf{b}_{L+1}}$, where
$f_{W,\mathbf{b}}(\mathbf{x})=\rho(g_{W,\mathbf{b}}(\mathbf{x}))$ is called a
hidden layer, $g_{W,\mathbf{b}}(\mathbf{x})=W\mathbf{x}+\mathbf{b}$ is called
preactivation and $\rho$ is the activation function, which is identical for
all layers of the network and is either sigmoid or ReLU. The matrices are of
the size $W_{i}\in\mathbb{R}^{n_{i+1}\times n_{i}}$ and
$\mathbf{b}\in\mathbb{R}^{n_{i}}$ such that $n_{1}=n_{u}$ and $n_{L+1}=n_{u}$.
By slight abuse of notation, for
$\mathbf{u}\in\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ let
$f(\mathbf{u})\in\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})$ such that
$f(\mathbf{u})[k]=f(\mathbf{u}[k])$ for all $1\leq k\leq T$.

######  Definition 8 (GLU layer Smith et al. (2022))

A GLU layer is a function of the form
$GLU:\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})\to\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})$
parametrized by a linear operaetor $W$ such that
$GLU(\mathbf{u})[k]=GELU(\mathbf{u}[k])\odot\sigma(W(GELU(\mathbf{u}[k])))$,
where $\sigma$ is the sigmoid function and GELU is the Gaussian Error Linear
Unit Hendrycks and Gimpel (2016).

Note, that this definition of GLU layer differs from the original definition
in Dauphin et al. (2017), because in deep SSM models GLU is usually applied
individually for each time step, without any time-mixing operations. See
Appendix G.1 in Smith et al. (2022). The linear operation $W$ is usually
represented by a convolution operation.

###  3.2 Learning problem

We consider the usual supervised learning framework for sequential input data.
The considered models, parametrized by $\theta$, are of the form
$f_{\theta}:\mathcal{U}^{+}\to\mathcal{Y}$, where
$\mathcal{U}\subseteq\mathbb{R}^{n_{\text{in}}}$ is the input space,
$\mathcal{U}^{+}$ denotes the set of all finite sequences and $\mathcal{Y}$ is
the output space, either a finite set for classification or
$\mathcal{Y}\subseteq\mathbb{R}^{n_{\text{out}}}$ for regression. Without loss
of generality we assume $n_{\text{out}}=1$. In practice, $\theta$ is usually
obtained by some learning algorithm, such as Gradient Flow or (Stochastic)
Gradient Descent. In this paper, we are agnostic regarding the origin of
$\theta$ as we prove a generalization bound that holds for a set of models,
therefore we omit the subscript $\theta$ from the notation of $f$.

For training we will use input sequence of the same length $T$. More
precisely, let us denote by $\mathcal{U}^{T}$ the set of all sequences of
elements of $\mathcal{U}$ of length $T$. A dataset is an i.i.d sample of the
form $S=\\{(\mathbf{u}_{i},\mathbf{y}_{i})\\}_{i=1}^{N}$ where
$\mathbf{u}_{i}\in\mathcal{U}^{T}$ and $\mathbf{y}_{i}\in\mathcal{Y}$ for all
$i$, where the random sample is with respect to some probability measure
$\mathcal{D}$ defined on the $\sigma$-algebra generated by the Borel sets of
$\mathcal{U}^{T}\times\mathcal{Y}$, where $\mathcal{U}^{T}\times\mathcal{Y}$
is considered with respect to the standard topology as a subset of
$(\mathbb{R}^{n_{\text{in}}})^{T}\times\mathbb{R}^{n_{\text{out}}}$.

An elementwise loss function is of the form
$\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$ and is assumed to be
$K_{\ell}$-Lipschitz-continuous, i.e.
$|\ell(y_{1},y_{1}^{\prime})-\ell(y_{2},y_{2}^{\prime})|\leq
K_{\ell}(|y_{1}-y_{2}|+|y_{1}^{\prime}-y_{2}^{\prime}|)$ for all
$y_{1},y_{2},y_{1}^{\prime},y_{2}^{\prime}\in\mathbb{R}$, as well as
$\ell(y,y)=0$ for all $y\in\mathbb{R}$. Let
$\mathcal{L}_{emp}^{S}(f)=\frac{1}{N}\sum_{i=1}^{N}l(f(\mathbf{u}_{i}),y_{i})$
denote the empirical loss of a model $f$ w.r.t a dataset $S$. We denote the
true error by
$\mathcal{L}(f)=\mathbf{E}_{(\mathbf{u},y)\sim\mathcal{D}}[\ell(f(\mathbf{u}),y)]$.
The generalization error or gap of a model $f$ is defined as
$|\mathcal{L}_{emp}^{S}(f)-\mathcal{L}(f)|$. In practice, we can approximate
the generalization gap by the empirical generalization gap, i.e. the loss
difference on the training data and some test data (see Devroye et al.
(2013)).

###  3.3 Assumptions

Before moving forward to discuss the main result, we summarize the assumptions
we make in the paper for the sake of readibility. Hereinafter we denote by
$\mathcal{F}$ a set of deep SSM models represented by its direct product of
its layerwise parameters. Furthermore, let $\mathcal{E}$ denote the set of all
SSM models $\Sigma$ for which there is a model $f\in\mathcal{F}$ such that
$\Sigma$ is an SSM layer of $f$.

###### Assumption 9

We assume the following properties hold.

  1. 1.

Scalar output. Let $n_{\text{out}}=1$.

  2. 2.

Lipschitz loss function. Let the elementwise loss $l$ be $L_{l}$-Lipschitz
continuous.

  3. 3.

Bounded input. There exist $K_{\mathbf{u}}>0$ and $K_{y}>0$ such that for all
input trajectory $\mathbf{u}$ we have
$\left\lVert\mathbf{u}\right\rVert_{\ell^{2,2}(\mathbf{R}^{n_{\text{in}}})}\leq
K_{\mathbf{u}}$ and for all labels we have $|y|\leq K_{y}$ .

  4. 4.

Stability. All $\Sigma\in\mathcal{E}$ are internally stable, implying
$\left\lVert\Sigma\right\rVert_{p}<+\infty$ for $p=1,2$. Therefore we assume
there exist $K_{p}>0$ such that
$\sup\limits_{\Sigma\in\mathcal{E}}\left\lVert\Sigma\right\rVert_{p}<K_{p}$
for $p=1,2$.

  5. 5.

Bounded Encoder and Decoder. We assume the Encoder and Decoder have bounded
operator norms, i.e.
$\sup\limits_{W^{\text{Enc}}\in\mathcal{W}_{\text{Enc}}}\left\lVert
W^{\text{Enc}}\right\rVert_{2,2}<K_{\text{Enc}}$ and
$\sup\limits_{W^{\text{Dec}}\in\mathcal{W}_{\text{Dec}}}\left\lVert
W^{\text{Dec}}\right\rVert_{\infty,\beta}<K_{\text{Dec}}$ for
$\beta\in\mathbb{N}\cup\\{\infty\\}$.

Assumption 1. is not restrictive as we consider classification.

The Lipschitzness in Assumption 2. holds for most of the loss functions used
in practice. We mention that even the square-loss is Lipschitz on a bounded
domain. From the practical aspect, the upped boundedness is also mild, as
parameters along the learning algorithm’s trajectory usually make $l$ bounded.
In the worst case, $l$ is bounded on a bounded domain due to being Lipschitz.

Assumption 3. is yet again standard in the literature. Even in practical
applications the input is usually normalized or standardized as a
preprocessing step before learning.

Assumption 4. is the most important one as it plays a central role in our
work. The motivation behind this assumption is twofold. First, in practical
implementation of SSM based architectures, it is very common to apply some
structured parametrization of the matrices of the systems, which leads to
learning stable matrices. In many cases, the underlying intention is numerical
stability of the learning algorithm, however we argue that the major advantage
of such parametrizations is to ensure a stable behavior of the system. Second,
similar stability assumptions are standard in control theory.

Assumption 5. is again fairly standard, as it requires that the weights of the
encoder and decoder are bounded.

##  4 Main results

Our main result is a Rademacher complexity based generalization bound for deep
SSM models that does not depend on the sequence length. The main challenge to
establish such bounds are threefold:

  1. 1.

without any assumption on the SSMs, their Rademacher complexity itself is not
trivial to upper bound,

  2. 2.

even if one had a bound on the Rademacher complexity of SSMs, it needs to be
extened to a block of SSMs and deep neural networks,

  3. 3.

deep SSM structures usually contain several of these blocks, therefore any
estimation on the Rademacher complexity of the model class has to address this
situation.

As to the first point, we argue that the stability of the SSMs has a crucial
role in the generalization ability of these kind of models. While applying
stable parametrization is common in practical implementations, to best of our
knowledge, the literature has been lacking any theoretical guarantees on the
effect of stability to the model’s performance. To this end, we show that the
Rademacher complexity of a set of SSMs can be upper bounded by a term which
has a tight dependence on the maximal $H_{2}$ norm of the SSMs.

The second and third points can be translated to the task of estimating the
Rademacher complexity of a deep structure, where each block of the composition
may have a different mathematical nature. We can overcome this obstacle by
introducing a property of functions, referred to as Rademacher Contraction,
that is universal enough to include functions represented by both SSMs and
neural networks.

######  Definition 10 ($(\mu,c)$-Rademacher Contraction)

Let $X_{1}$ and $X_{2}$ be subsets of Banach spaces
$\mathcal{X}_{1},\mathcal{X}_{2}$, with norms $\|\cdot\|_{\mathcal{X}_{1}}$
and $\|\cdot\|_{\mathcal{X}_{2}}$, and let $\mu\geq 0$ and $c\geq 0$. A set of
functions $\Phi=\\{\varphi:X_{1}\to X_{2}\\}$ is said to be
$(\mu,c)$-Rademacher Contraction, or $(\mu,c)$-RC in short, w.r.t.
$\left\lVert\cdot\right\rVert_{X_{2}}$ and
$\left\lVert\cdot\right\rVert_{X_{1}}$, if for all $n\in\mathbb{N}^{+}$ and
$Z\subseteq X_{1}^{n}$ we have

$\mathbb{E}_{\sigma}\left[\sup\limits_{\varphi\in\Phi}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{n}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\varphi(\mathbf{u}_{i})\right\rVert_{\mathcal{X}_{2}}\right]\leq\mu\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{n}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\mathcal{X}_{1}}\right]+\frac{c}{\sqrt{N}},$
(2)

where $\sigma_{i}$ are i.i.d. Rademacher random variables, $i\in[N]$, i.e.
$\mathbb{P}(\sigma_{i}=1)=\mathbb{P}(\sigma_{i}=-1)=1/2$.

Rademacher Contractions in the literature. Special cases of the inequality in
Definition 10 can be found in the literature. In Golowich et al. (2018) the
authors considered biasless ReLU networks and proved a similar inequality
using Talagrand’s contraction lemma Ledoux and Talagrand (1991). In Truong
(2022b), the author considered neural networks with dense and convolutional
layers and derived a PAC bound via bounding the Rademacher complexity. One of
the key technical achievements is Theorem 9, which is a more general version
of the inequality in Golowich et al. (2018). This was then applied to obtain
generalization bounds for the task of learning Markov-chains in Truong
(2022a), however the generalization error was measured via the marginal cost
and the $(\mu,c)$-RC type inequality was only applied for time-invariant
neural networks. In contrast, we prove that along with time invariant models,
stable SSMs, defined between certain Banach spaces, also satisfy equation (2)
and apply it to deep structures.

In a recent work Trauger and Tewari (2024), the authors consider Transformers
and implicitly establish similar inequalities to (2) by bounding different
kinds of operator norms of the model and managed to extend it to a stack of
Transformer layers. Besides these similarities, some key differences in our
work are that Definition 10 provides an explicit way to combine SSMs with
neural networks, even in residual blocks; we do not assume the SSM matrices to
be bounded, instead we require the system norm to be bounded via stability,
which is a weaker condition; and we upper bound the Rademacher complexity
directly instead of bounding the covering number.

Interpretation of equation (2). Usually, the machine learning literature deals
with functions between vector spaces, whereas in the above definition we
consider functions between normed spaces. As a result, in order to apply this
definition to any component of a deep SSM model, which are defined as maps
between vector spaces in section 3.1, we need to equip the domain and range of
these maps with some norms. The choice of these norms is arbitrary, but the
constants $\mu$ and $c$ depend on it, and the analysis of a deep structure
componentwise requires that the image of a middle layer is equiepped with the
same norm as the domain of the succeeding layer. Foreshadowing the next
section, this is exactly what we would like to do, namely show, that each
component of a deep SSM model parametrized by some appropriate sets of
parameters, is $(\mu,c)$-RC for some $\mu$ and $c$.

In case of affine layers and SSMs, this is proven in Lemma 13 and those
results hold for unbounded $X_{1}$ and $X_{2}$ sets with $c=0$. Lemma 16 gives
similar results for sigmoid and ReLU MLPs with $c>0$, which are also valid for
ubounded input space. As for the GLU layers, it is possible to prove a
$(\mu,c)$-RC property, but the constants depend on the size of $X_{1}$.
Consequently, we restrict the input space of the nonlinear layers to a ball of
a fixed radius. As these layers are preceded and succeeded by other
components, we need to ensure that if the input of the deep SSM is from a ball
of some radius $r$, the output of each layer is also in a ball of a radius
that may depend on $r$ and the layer’s parameter set.

The following Lemma provides the way to establish a (2) type inequality for
deep structures whose components are each $(\mu,c)$-RC.

######  Lemma 11 (Composition lemma)

Let $\Phi_{1}=\\{\varphi_{1}:X_{1}\to X_{2}\\}$ be $(\mu_{1},c_{1})$-RC and
$\Phi_{2}=\\{\varphi_{2}:X_{2}\to X_{3}\\}$ be a $(\mu_{2},c_{2})$-RC. Then
the set of compositions
$\Phi_{2}\circ\Phi_{1}:=\\{\varphi_{2}\circ\varphi_{1}:X_{1}\to
X_{3}\mid\varphi_{1}\in\Phi_{1},\varphi_{2}\in\Phi_{2}\\}$ is a
$(\mu_{1}\mu_{2},\mu_{2}c_{1}+c_{2})$-RC.

The proof is in Appendix B. The upcoming corollary is straightforward by
induction along with the fact that the pooling layer $f^{\text{Pool}}$ is
$(1,0)$-RC (see Lemma 13).

###### Corollary 12

Let $f$ be a deep SSM model, i.e. according to Definition 6,
$f=f^{\text{Dec}}\circ f^{\text{Pool}}\circ f^{\text{B}_{L}}\circ\ldots\circ
f^{\text{B}_{1}}\circ f^{\text{Enc}}$, such that $f^{\text{Enc}}$,
$f^{\text{Dec}}$ and each $f^{\text{B}_{i}}$ are $(\mu_{0},c_{0})$-RC,
$(\mu_{L+1},c_{L+1})$-RC and $(\mu_{i},c_{i})$-RC respectively for all $i$.
Then $\psi$ is
$\left(\prod\limits_{i=0}^{L+1}\mu_{i},\sum\limits_{j=1}^{L}\left[\prod\limits_{i=j+1}^{L+1}\mu_{i}\right]c_{j}\right)$-RC.

What we have left are the following. First, in light of the previous
corollary, we need to show that each component of a deep SSM model is
$(\mu,c)$-RC for some $\mu$ and $c$ w.r.t. compatible normed spaces. Second,
we need to show that the Rademacher complexity of a $(\mu,c)$-RC model set are
bounded in terms of $\mu$ and $c$. We start with the first one.

###### Lemma 13

Let $\mathcal{W}_{\text{Enc}}$, $\mathcal{W}_{\text{Dec}}$, and $\mathcal{E}$
denote some sets of parameters of some fixed Encoder, Decoder and SSM layers,
respectively. The corresponding function sets are

  * •

$\mathcal{F}_{\text{Enc}}=\\{f^{\text{Enc}}=\langle
W^{\text{Enc}},\cdot\rangle\mid W\in\mathcal{W}_{\text{Enc}}\\}$,

  * •

$\mathcal{F}_{\text{Dec}}=\\{f^{\text{Dec}}=\langle
W^{\text{Dec}},\cdot\rangle\mid W\in\mathcal{W}_{\text{Dec}}\\}$,

  * •

$\mathcal{F}_{\text{SSM}}=\\{\mathcal{S}_{\Sigma}\mid\Sigma\in\mathcal{E}\\}$,

where $\mathcal{S}_{\Sigma}$ denotes the input-output map of the dynamical
system $\Sigma$. Then all of these function sets are $(\mu,c)$-RC according to
the following table, where for any Banach space $\mathcal{X}$,
$B_{\mathcal{X}}(t)=\\{x\in\mathcal{X}\mid\left\lVert
x\right\rVert_{\mathcal{X}}\leq r\\}$ denotes the ball of radius $r$ centered
in zero for arbitrary $r$.

| $\mu$ | $c$ | $X_{1}$ | $X_{2}$
---|---|---|---|---
$\mathcal{F}_{\text{Enc}}$ | $\sup\limits_{W^{\text{Enc}}\in\mathcal{W}_{\text{Enc}}}\left\lVert W^{\text{Enc}}\right\rVert_{2,2}<K_{\text{Enc}}$ | 0 | $B_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}(r)$ | $B_{\ell^{2,2}(\mathbb{R}^{n_{u}})}(K_{\text{Enc}}r)$
$\mathcal{F}_{\text{Dec}}$ | $\sup\limits_{W^{\text{Dec}}\in\mathcal{W}_{\text{Dec}}}\left\lVert W^{\text{Dec}}\right\rVert_{\infty,\infty}<K_{\text{Dec}}$ | 0 | $B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$ | $B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{\text{out}}})}(K_{\text{Dec}}r)$
| $\sup\limits_{W^{\text{Dec}}\in\mathcal{W}_{\text{Dec}}}\left\lVert W^{\text{Dec}}\right\rVert_{\infty,\beta}<K_{\text{Dec}}$ | 0 | $B_{(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{\infty})}(r)$ | $B_{(\mathbb{R}^{n_{\text{out}}},\left\lVert\cdot\right\rVert_{\beta})}(K_{\text{Dec}}r)$
$\mathcal{F}_{\text{SSM}}$ | $\sup\limits_{\Sigma\in\mathcal{E}}\left\lVert\Sigma\right\rVert_{2}<K_{2}$ | 0 | $B_{\ell^{2,2}(\mathbb{R}^{n_{u}})}(r)$ | $B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{y}})}(K_{2}r)$
| $\sup\limits_{\Sigma\in\mathcal{E}}\left\lVert\Sigma\right\rVert_{1}<K_{1}$ | 0 | $B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$ | $B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{y}})}(K_{1}r)$

Furthermore, the operation of $f^{\text{Pool}}$, defined in Definition 6, is
$(1,0)$-RC between $X_{1}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$ and
$X_{2}=B_{(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{\infty})}(r)$.

The proof is in Appendix B. We can see that the SSM layer can only increase
the input’s complexity by the factor $\left\lVert\Sigma\right\rVert_{p}$,
$p=1,2$, a quantity that gets smaller as the system gets more stable. This
gets even more crucial when dealing with long range sequences, because the
Neural Network layers are constant in time.

###### Remark 14

The results of of Lemma 13 hold for unbounded input spaces as well. The reason
for restricting the input space to a ball of radius $r$ is the composition
with MLPs or GLU layers, as discussed in the interpretation of Definition 10.

The last factor that influences the complexity are the Neural Network layers
that follow the SSM layers in each SSM block (Definition 5). There are several
results in the literature establishing upper bounds on the Rademacher
complexity of MLPs and its variants. Additionally, in some cases the proof
techniques directly imply the $(\mu,c)$-RC property of these models. As a
result, we do not pay special attention to the MLP layers. We prove the
$(\mu,c)$-RC property of GLU layers as they are commonly used in deep SSM
structures, and deduct the values of $\mu$ and $c$ from previously known
results in case of deep MLPs.

###### Lemma 15

Let $\mathcal{F}_{\text{GLU}}$ denote a set of GLU layers, i.e.
$\mathcal{F}_{\text{GLU}}=\\{GLU_{W}(\mathbf{u})=(GELU[\mathbf{u}])\odot\sigma(W(GELU(\mathbf{u})))\mid
W\in\mathcal{W}\\}$. Under the Bounded Input assumption in Assumption 9 we
have that $\mathcal{F}_{\text{GLU}}$ is $(\mu,0)$-RC w.r.t. the spaces
$X_{1}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(K_{\mathbf{u}})=X_{2}$,
where
$\mu=16\left(K_{\mathbf{u}}\cdot\max\left\\{\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty},1\right\\}+1\right)\left(\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}+1\right)$.

The proof is in Appendix B.

###### Lemma 16

Let $\mathcal{F}^{\rho}$ denote a set of hidden layers, i.e.
$\mathcal{F}=\\{f_{W,b}(\mathbf{u})=\rho(W\mathbf{x}+\mathbf{b})\mid(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}\\}$
and $\rho$ is either the sigmoid or the ReLU activation function. Let us
assume that there exist $K_{W}>0$ and $K_{\mathbf{b}}>0$ such that
$\sup\limits_{W\in\mathcal{W}}\left\lVert W\right\rVert_{\infty,\infty}<K_{W}$
and
$\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{\infty}<K_{\mathbf{b}}$.
Under the Bounded Input assumption in Assumption 9 we have that
$\mathcal{F}^{ReLU}$ is $(\mu,c)$-RC w.r.t. the spaces
$X_{1}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$,
$X_{2}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}(K_{W}r+K_{\mathbf{b}})$,
$\mu=4K_{W}$ and $c=4K_{W}K_{\mathbf{b}}$.
Under the extra assumption that the parameter set is symmetric to the origin,
meaning that $(W,b)\in\mathcal{W}\times\mathcal{B}$ implies
$(-W,-b)\in\mathcal{W}\times\mathcal{B}$, we have that $\mathcal{F}^{sigmoid}$
is $(\mu,c)$-RC w.r.t. the spaces
$X_{1}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$,
$X_{2}=B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}(1)$, $\mu=K_{W}$ and
$c=K_{W}(K_{\mathbf{b}}+0.5)$.

The proof is in Appendix B. Combining the previous Lemma with Lemma 11 and
Lemma 21 we get the following for deep networks.

###### Corollary 17

Let $g_{W,\mathbf{b}}(x)=W\mathbf{x}+\mathbf{b}$ represent an affine
transformation and consider a set of deep networks
$\mathcal{F}^{\rho}=\\{f=f^{\rho}_{W_{1},\mathbf{b}_{1}}\circ\ldots\circ
f^{\rho}_{W_{L},\mathbf{b}_{L}}\circ
g_{W_{L+1},\mathbf{b}_{L+1}}\mid(W_{i},\mathbf{b}_{i})\in\mathcal{W}_{i}\times\mathcal{B}_{i},1\leq
i\leq L+1\\}$, where $f^{\rho}_{W_{i},\mathbf{b}_{i}}$ are hidden layers with
the same activations $\rho$ equal to either sigmoid or ReLU. Let $K_{W}>0$ and
$K_{\mathbf{b}}>0$ such that $\sup\limits_{W\in\mathcal{W}_{i}}\left\lVert
W\right\rVert_{\infty,\infty}<K_{W}$ and
$\sup\limits_{\mathbf{b}\in\mathcal{B}_{i}}\left\lVert\mathbf{b}\right\rVert_{\infty}<K_{\mathbf{b}}$
hold for all $1\leq i\leq L+1$. Under the assumptions of Lemma 16 we have that
$\mathcal{F}^{ReLU}$ is $(\mu,c)$-RC w.r.t. with $\mu=4(L+1)K_{W}$ and
$c=4(L+1)K_{W}K_{\mathbf{b}}\frac{L(L+1)}{2}$ and $\mathcal{F}^{sigmoid}$ is
$(\mu,c)$-RC w.r.t. with $\mu=(L+1)K_{W}$ and
$c=(L+1)K_{W}(K_{\mathbf{b}}+0.5)\frac{L(L+1)}{2}$.

So far we showed that each component of a deep SSM model satisfies Definition
10. We also proved that the composition of such components also satisfies the
definition. The main theorem summarizes these results and exploits the fact
that the Rademacher complexity of a $(\mu,c)$-RC set of models is upper
bounded by terms containing $\mu$ and $c$.

###### Theorem 18

Let $\mathcal{F}$ be a set of deep SSM models, namely let $f\in\mathcal{F}$
has the form $f=f^{\text{Dec}}\circ f^{\text{Pool}}\circ
f^{\text{B}_{L}}\circ\ldots\circ f^{\text{B}_{1}}\circ f^{\text{Enc}}$ with
layer parameter sets $\mathcal{W}_{\text{Dec}}$,
$\mathcal{W}_{\text{B}_{L}},\ldots,\mathcal{W}_{\text{B}_{1}}$ and
$\mathcal{W}_{\text{Enc}}$ respectively, where $f^{\text{B}_{i}}$ is an SSM
block for all $i$, i.e.
$f^{\text{B}_{i}}(\mathbf{z})=g_{i}(\mathcal{S}_{\Sigma_{i}}(\mathbf{z})[k])+\alpha_{i}\mathbf{z}[k]$
and $\mathcal{W}_{\text{B}_{i}}=\mathcal{E}_{i}\times\mathcal{W}_{g_{i}}$. If
Assumption 9 holds and each set of nonlinearities
$g_{i}:X_{i}\rightarrow\hat{X}_{i}$ is $(\mu_{g_{i}},c_{g_{i}})$-RC, with
$X_{1}=B_{\left(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{2}\right)}(K_{2}K_{\mathbf{u}}K_{\text{Enc}})$
$\hat{X}_{i}=B_{\left(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{\infty}\right)}(\hat{r}_{i})$
$X_{i+1}=B_{\left(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{\infty}\right)}(r_{i+1})$,
$r_{i+1}\geq K_{1}(\hat{r}_{i}+|\alpha_{i}|r_{i})$, where
$r_{1}=K_{\mathbf{u}}$, $i=1,\ldots,L$, then the following holds with
probability at least $1-\delta$.

$\mathbb{P}_{S\sim\mathcal{D}^{N}}\left[\forall
f\in\mathcal{F}\quad\mathcal{L}(f)-\mathcal{L}_{emp}^{S}(f)\leq\frac{\mu
K_{\mathbf{u}}L_{l}+cL_{l}}{\sqrt{N}}+K_{l}\sqrt{\frac{2\log(4/\delta)}{N}}\right],$
(3)

$\mu\leq
K_{\text{Enc}}K_{\text{Dec}}\left(\mu_{g_{1}}K_{2}+\alpha_{1}\right)\prod\limits_{i=2}^{L}\left(\mu_{g_{i}}K_{1}+\alpha_{i}\right)$,
$c\leq
K_{\text{Dec}}\sum\limits_{j=1}^{L}\left[\prod\limits_{i=j+1}^{L}\left(\mu_{g_{i}}K_{1}+\alpha_{i}\right)\right]c_{g_{j}}$
and $K_{l}>0$ such that $|l(\cdot,\cdot)|\leq K_{l}$. In particular, we obtain
$K_{l}\leq 2L_{l}\max\\{K_{\text{Dec}}r_{L+2},K_{y}\\}$.

The proof can be found in Appendix B.

##  Appendix A Rademacher complexity

###### Definition 19

(Shalev-Shwartz and Ben-David, 2014, Def. 26.1) The Rademacher complexity of a
bounded set $\mathcal{A}\subset\mathbb{R}^{m}$ is defined as

$\displaystyle
R(\mathcal{A})=\mathbb{E}_{\mathbf{\sigma}}\Bigg{[}\sup_{a\in\mathcal{A}}\frac{1}{m}\sum\limits_{i=1}^{m}\sigma_{i}a_{i}\Bigg{]},$

where the random variables $\mathbf{\sigma}_{i}$ are i.i.d such that
$\mathbb{P}[\sigma_{i}=1]=\mathbb{P}[\sigma=-1]=0.5$. The Rademacher
complexity of a set of functions $\mathcal{F}$ over a set of samples
$S=\\{s_{1}\dots s_{m}\\}$ is defined as
$R_{S}(\mathcal{F})=R(\left\\{(f(s_{1}),\dots,f(s_{m}))\mid
f\in\mathcal{F}\right\\}).$

The following is a standard theorem we use in the proof.

###### Theorem 20

(Shalev-Shwartz and Ben-David, 2014, Thm. 26.5) Let $L_{0}$ denote the set of
functions of the form $(\mathbf{u},y)\mapsto l(f(\mathbf{u}),y)$ for
$f\in\mathcal{F}$. Let $K_{l}$ be such that the functions from $L_{0}$ all
take values from the interval $[0,K_{l}]$. Then for any $\delta\in(0,1)$ we
have

$\displaystyle\mathbb{P}_{\mathbf{S}\sim\mathcal{D}^{N}}\Bigg{(}\forall
f\in\mathcal{F}:\mathcal{L}(f)-\mathcal{L}^{S}_{emp}(f)\leq
2R_{S}(L_{0})+K_{l}\sqrt{\frac{2\log(4/\delta)}{N}}\Bigg{)}\geq 1-\delta.$

##  Appendix B Proofs

In this section we need to prove $(\mu,c)$-RC property for linear (or affine)
transformations which are constant in time, in many cases. For better
readibility, we only do the calculations once and use it as a lemma.

###### Lemma 21

Let $\mathbf{u}\in\ell^{p,p}(\mathbb{R}^{n_{u}})=:X_{1}$ and let
$f(\mathbf{u})=f_{W,\mathbf{b}}(\mathbf{u}):=W\mathbf{u}+\mathbf{b}\in\ell^{q,q}(\mathbb{R}^{n_{v}})=:X_{2}$,
where $W\in\mathbb{R}^{n_{v}\times n_{u}},\mathbf{b}\in\mathbb{R}^{n_{v}}$,
and by definition $W\mathbf{u}\in X_{2}$ such that
$(W\mathbf{u}+b)[k]=W\mathbf{u}[k]+\mathbf{b}$, i.e. it is an affine
transformation constant in time. We consider the cases

  * a)

$p=q=2$,

  * b)

$p=2,q=\infty$,

  * c)

$p=q=\infty$.

Let us assume that there exist constants $K_{W}$ and $K_{\mathbf{b}}$ such
that $\sup\limits_{W\in\mathcal{W}}\left\lVert W\right\rVert_{p,q}\leq K_{W}$
and
$\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{q}\leq
K_{\mathbf{b}}$. Then the set of transformation
$\mathcal{F}=\\{f_{W,\mathbf{b}}\mid
W\in\mathcal{W},\mathbf{b}\in\mathcal{B}\\}$ is $(K_{W},K_{\mathbf{b}})$-RC
w.r.t. $X_{1}$ and $X_{2}$. Furthermore, the image of the ball $B_{X_{1}}(r)$
under $f\in\mathcal{F}$ is contained in $B_{X_{2}}(K_{W}r+K_{\mathbf{b}})$,
and therefore $\mathcal{F}|_{B_{X_{1}}(r)}$ is also
$(K_{W},K_{\mathbf{b}})$-RC w.r.t the spaces $B_{X_{1}}(r)$ and
$B_{X_{2}}(K_{W}r+K_{\mathbf{b}})$.

Proof  First let us prove a simple fact about Rademacher random variables that
we will need, namely if $\sigma=\\{\sigma_{i}\\}_{i=1}^{N}$ is a sequence of
i.i.d. Rademacher variables, then

$\mathbb{E}_{\sigma}\left[\left|\sum\limits_{i=1}^{N}\sigma_{i}\right|\right]\leq\sqrt{N}.$
(4)

This is true, because

$\displaystyle\mathbb{E}_{\sigma}\left[\left|\sum\limits_{i=1}^{N}\sigma_{i}\right|\right]=\sqrt{\left(\mathbb{E}_{\sigma}\left[\left|\sum\limits_{i=1}^{N}\sigma_{i}\right|\right]\right)^{2}}\leq\sqrt{\mathbb{E}_{\sigma}\left[\left|\sum\limits_{i=1}^{N}\sigma_{i}\right|^{2}\right]}$
$\displaystyle=\sqrt{\mathbb{E}_{\sigma}\left[\sum\limits_{i=1}^{N}\sigma^{2}_{i}+2\sum\limits_{i,j=1}^{N}\sigma_{i}\sigma_{j}\right]}=\sqrt{\sum\limits_{i=1}^{N}\mathbb{E}_{\sigma}\left[\sigma^{2}_{i}\right]+2\sum\limits_{i,j=1}^{N}\mathbb{E}_{\sigma}\left[\sigma_{i}\sigma_{j}\right]}=\sqrt{N},$

where the first inequality follows from Jensen’s inequality and the last
equality follows from the linearity of the expectation, and the facts that
$\sigma_{i}$ are Rademacher variables and form and i.i.d sample.

Let $Y\in\\{X_{1},B_{X_{1}}(r)\\}$.

a) Let $\underline{\mathbf{b}}\in Y$ denote the sequence for which
$\underline{\mathbf{b}}[k]=\mathbf{b}$ for all $k\in[T]$. For any $Z\subseteq
Y$ we have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}(W\mathbf{u}_{i}+\mathbf{b})\right\rVert_{Y}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}\right\rVert_{Y}\right]+\mathbb{E}_{\sigma}\left[\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\underline{\mathbf{b}}\right\rVert_{Y}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sqrt{\sum\limits_{k=1}^{T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}[k]\right\rVert_{2}^{2}}\right]+\mathbb{E}_{\sigma}\left[\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\right|\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\underline{\mathbf{b}}\right\rVert_{Y}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sqrt{\sum\limits_{k=1}^{T}\left\lVert
W\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right)\right\rVert_{2}^{2}}\right]+\frac{1}{\sqrt{N}}\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{2}$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert
W\right\rVert_{2,2}\sqrt{\sum\limits_{k=1}^{T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert_{2}^{2}}\right]+\frac{1}{\sqrt{N}}\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{2}$
$\displaystyle=\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{2,2}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{Y}\right]+\frac{1}{\sqrt{N}}\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{2},$

where the first inequality follows from the triangle inequality, the first
equality is the definition of the norm, the second inequality follows from the
equation (4) and the linearity of $W$, and the last inequality is a standard
inequality for matrix norms.

b) The first inequalities referring to the bias term are exactly the same and
hold for the infinity norm as well as in case a). We only have to deal with
the term

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}\right\rVert_{Y}\right],$

but now $\mathbf{u}_{i}\in\ell^{2,2}(\mathbb{R}^{n_{u}})$ and
$W\mathbf{u}_{i}\in\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})$. We have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}\right\rVert_{Y}\right]=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert
W\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right)\right\rVert_{Y}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\left\lVert
W\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right)\right\rVert_{\infty}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\left\lVert
W\right\rVert_{2,\infty}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert_{2}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{2,\infty}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sqrt{\sup\limits_{1\leq k\leq
T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert_{2}^{2}}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{2,\infty}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sqrt{\sum\limits_{k=1}^{T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert_{2}^{2}}\right]$
$\displaystyle\leq\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{2,\infty}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\ell^{2,2}(\mathbb{R}^{n_{u}})}\right],$

where the second equality is the definition of the norm, the first inequality
is the standard inequality for induced matrix norms.

c) Again, we only need to deal with the term

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}\right\rVert_{Y}\right],$

but now $\mathbf{u}_{i}\in\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ and
$W\mathbf{u}_{i}\in\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})$. We have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W\mathbf{u}_{i}\right\rVert_{Y}\right]=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert
W\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right)\right\rVert_{Y}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\left\lVert
W\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right)\right\rVert_{\infty}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\left\lVert
W\right\rVert_{\infty,\infty}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert_{\infty}\right]$
$\displaystyle=\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right],$

where the inequality is again the standard inequality for induced matrix
norms.

We can see that the calculactions hold if the transformations are restricted
to the ball $B_{X_{1}}(r)$ for any choice of $X_{1}$ we consider. The radius
can grow as

$\displaystyle\left\lVert
W\mathbf{u}+\mathbf{b}\right\rVert_{\ell^{q,q}(\mathbb{R}^{n_{v}})}\leq\left\lVert
W\mathbf{u}\right\rVert_{\ell^{q,q}(\mathbb{R}^{n_{v}})}+\left\lVert\underline{\mathbf{b}}\right\rVert_{\ell^{q,q}(\mathbb{R}^{n_{v}})}\leq\left\lVert
W\right\rVert_{p,q}\left\lVert\mathbf{u}\right\rVert_{\ell^{p,p}(\mathbb{R}^{n_{u}})}+\left\lVert\mathbf{b}\right\rVert_{q}.$

Proof [Proof of Lemma 11] Let $Z\subseteq X_{1}^{N}$ and
$\tilde{Z}=\\{\\{\varphi_{1}(\mathbf{u}_{i})\\}_{i=1}^{N}\mid\varphi_{1}\in\Phi_{1}\\}$.
We have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{\varphi_{2}\in\Phi_{2}}\sup\limits_{\varphi_{1}\in\Phi_{1}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\varphi_{2}(\varphi_{1}(\mathbf{u}_{i}))\right\rVert_{X_{3}}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{\varphi_{2}\in\Phi_{2}}\sup\limits_{\\{\mathbf{v}_{i}\\}_{i=1}^{N}\in\tilde{Z}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\varphi_{2}(\mathbf{v}_{i})\right\rVert_{X_{3}}\right]$
$\displaystyle\leq\mu_{2}\mathbb{E}_{\sigma}\left[\sup\limits_{\varphi_{1}\in\Phi_{1}}\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\varphi_{1}(\mathbf{u}_{i})\right\rVert_{X_{2}}\right]+\frac{c_{2}}{\sqrt{N}}$
$\displaystyle\leq\mu_{2}\mu_{1}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{u}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{X_{1}}\right]+\mu_{2}\frac{c_{1}}{\sqrt{N}}+\frac{c_{2}}{\sqrt{N}}$

Proof [Proof of Lemma 13]

Encoder and Decoder. The Encoder is case a), while the Decoder is case b) in
Lemma 21.

SSM. As discussed in Section 3.1, an SSM is equivalent to a linear
transformation called its input-output map. Therefore, by Lemma 21, the SSM is
$(\mu,0)$-RC in both cases, where $\mu$ is the operator norm of the input-
output map. Combining this with Lemma 3 yields the result.

###### Remark 22

As the value of $T$ is fixed, the input-output map can be described by the so-
called Toeplitz matrix of the system. In this case, the operator norm equals
to the appropriate induced matrix norm of the Toeplitz matrix. For the case of
$T=\infty$, the input-output map still exists and is a linear operator. The
proof of Lemma 21 holds in this case as well for operator norms.

Pooling. For any $Z\subseteq\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ we have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}f^{\text{Pool}}(\mathbf{z}_{i})\right\rVert_{\infty}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\left(\frac{1}{T}\sum\limits_{k=1}^{T}\mathbf{z}_{i}^{(j)}[k]\right)\right|\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{T}\sum\limits_{k=1}^{T}\left(\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}^{(j)}[k]\right)\right|\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\frac{1}{T}\sum\limits_{k=1}^{T}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}^{(j)}[k]\right|\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\frac{1}{T}\sum\limits_{k=1}^{T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}[k]\right\rVert_{\infty}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$

Proof [Proof of Lemma 15] First of all, we show that the function
$h:(\mathbb{R}^{2},\left\lVert\cdot\right\rVert_{2})\to(\mathbb{R},|\cdot|)$
defined as $h(\mathbf{x})=x_{1}\cdot\sigma(x_{2})$ is
$\sqrt{2}(K+1)$-Lipschitz on a bounded domain, where $|x_{i}|\leq K$ for all
$\mathbf{x}\in\mathbb{R}^{2}$ we consider. We will later specify the value of
$K$ in relation to Assumption 9. By the sigmoid being 1-Lipschitz, we have

$\displaystyle|h(\mathbf{x})-h(\mathbf{y})|=|x_{1}\sigma(x_{2})-y_{1}\sigma(x_{2})+y_{1}\sigma(x_{2})-y_{1}\sigma(y_{2})|\leq$
$\displaystyle|(x_{1}-y_{1})\sigma(x_{2})|+|y_{1}(\sigma(x_{2})-\sigma(y_{2}))|\leq|x_{1}-y_{1}|+|y_{1}||x_{2}-y_{2}|$
$\displaystyle\leq\sqrt{2}(K+1)\left\lVert\mathbf{x}-\mathbf{y}\right\rVert_{2}$

Second, we recall Corollary 4 in Maurer (2016).

######  Theorem 23 (Maurer (2016))

Let $\mathcal{X}$ be any set,
$(\mathbf{x}_{1},\ldots,\mathbf{x}_{N})\in\mathcal{X}^{N}$, let $\mathcal{F}$
be a set of functions $f:\mathcal{X}\to\ell^{2}(\mathbb{R}^{m})$ and let
$h:\ell^{2}(\mathbb{R}^{m})\to\mathbb{R}$ be an $L$-Lipschitz function. Under
$f_{k}$ denoting the $k$-th component function of $f$ and $\sigma_{ik}$ being
a doubly indexed Rademacher variable, we have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\sum\limits_{i=1}^{N}\sigma_{i}h(f(\mathbf{x}_{i}))\leq\sqrt{2}L\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{m}\sigma_{ik}f_{k}(\mathbf{x}_{i})\right]\right].$

We wish to apply Theorem 23 to GLU layers. For any
$Z\subseteq\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ we have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}(\mathbf{z}_{i})\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}^{(j)}(\mathbf{z}_{i})[k]\right|\right]$

Now this is an alternative version of the Rademacher complexity, where we take
the absolute value of the Rademacher average. In order to apply Theorem 23, we
reduce the problem to the usual Rademacher complexity. In turn, we can apply
the last chain of inequalities in the proof of Proposition 6.2 in Hajek and
Raginsky (2019). Concretely, by denoting
$\mathbf{O}=\\{\mathbf{0}\\}_{i=1}^{N}$ and noticing that $GLU_{W}(0)=0$, we
have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}^{(j)}(\mathbf{z}_{i})[k]\right|\right]$
$\displaystyle\leq
2\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z\cup\\{\mathbf{O}\\}}\sup\limits_{1\leq k\leq T}\sup\limits_{1\leq j\leq
n_{u}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}^{(j)}(\mathbf{z}_{i})[k]\right]$

Let $\mathbf{x}_{i}=i$, $i=1,\ldots,N$ and let
$\mathcal{F}=\\{f_{W,\underline{z},k,j}\mid(W,\underline{z},k,j)\in\mathcal{W}\times(Z\cup\\{0\\})\times[T]\times[n_{u}]\\}$
such that
$f_{W,\underline{z},k,j}(\mathbf{x}_{i})=\begin{bmatrix}GELU(\mathbf{z}_{i}[k])^{(j)}&(W(GELU(\mathbf{z}_{i}[k])))^{(j)}\end{bmatrix}^{T}$
for $\underline{z}=\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in Z$. Since
$Z\subseteq(B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(K_{\mathbf{u}}))^{N}$,
it follows for all $\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in Z$ and for all
$k\in\mathbb{N}$ that $\|\mathbf{z}_{i}[k]\|_{\infty}\leq K_{\mathbf{u}}$, and
hence $|GELU(\mathbf{z}_{i}[k])^{(j)}|<K_{\mathbf{u}}$, leading to
$|W(GELU(\mathbf{z}_{i}[k]))^{(j)}|<\sup\limits_{W\in\mathcal{W}}\|W\|_{\infty,\infty}\cdot
K_{\mathbf{u}}$. In particular,
$GLU^{(j)}_{W}(\mathbf{z}_{i})[k]=h(f_{W,\underline{z},k,j}(\mathbf{x}_{i}))=h|_{B}(f_{W,\underline{z},k,j}(\mathbf{x}_{i}))$,
where $h|_{B}$ is the restriction of $h$ to
$B=\\{x\in\mathbb{R}^{2}\mid\|x\|_{\infty}<K\\}$, and hence $h|_{B}$ is
$\sqrt{2}(K+1)$-Lipschitz. Therefore we can set
$K=\max\\{K_{\mathbf{u}},\sup\limits_{W\in\mathcal{W}}\|W\|_{\infty,\infty}\cdot
K_{\mathbf{u}}\\}$.

We are ready to apply Theorem 23, together with the GLU definition and its
$\sqrt{2}(K+1)$-Lipschitzness, we have

$\displaystyle
2\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z\cup\\{\mathbf{O}\\}}\sup\limits_{1\leq k\leq T}\sup\limits_{1\leq j\leq
n_{u}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}^{(j)}(\mathbf{z}_{i})[k]\right]$
$\displaystyle=2\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}f(\mathbf{x}_{i})\right]\leq
4(K+1)\underbrace{\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GELU(\mathbf{z}_{i}[k])^{(j)}\right]}_{A}$
$\displaystyle+4(K+1)\underbrace{\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W(GELU(\mathbf{z}_{i}))^{(j)}[k]\right]}_{B}$

Due to the definition of GELU, its 2-Lipschitzness Qi et al. (2023) and
(Ledoux and Talagrand, 1991, Theorem 4.12) we have

$\displaystyle
A=\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z\cup\\{\mathbf{O}\\}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GELU(\mathbf{z}_{i})\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]=$
$\displaystyle\leq
4\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z\cup\\{\mathbf{O}\\}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]=4\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$

and

$\displaystyle
B=\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in\\{\mathbf{O}\\}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}W(GELU(\mathbf{z}_{i}))\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$
$\displaystyle\leq 4\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z\\{\mathbf{O}\\}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$
$\displaystyle=4\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$

Here we used the linearity of $W$ and the exact same calculation as in the
proof of Lemma 21.

By combining the inequalities above, it follows that

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{W\in\mathcal{W}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq T}\sup\limits_{1\leq j\leq
n_{u}}\left|\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}GLU_{W}^{(j)}(\mathbf{z}_{i})[k]\right|\right]\leq$
$\displaystyle 16(K+1)\left(\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}+1\right)\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$

Substituting the value of $K$ gives the result.

Proof [Proof of Lemma 16]

MLP with sigmoid activations. Consider a single hidden layer
$f(\mathbf{x})=\rho(g(\mathbf{x}))$, where $g(x)=W\mathbf{x}+\mathbf{b}$ is
the preactivation and let $\mathcal{G}=\left\\{g(x)=W\mathbf{x}+\mathbf{b}\mid
W\in\mathcal{W},\mathbf{b}\in\mathcal{B}\right\\}$ denote the set of possible
preactivation functions. As compared to Definition 7, we omit the subscript
from the notation of $g$. For an input sequence
$\mathbf{z}\in\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})$ let
$g(\mathbf{z})\in\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})$ mean that we apply
$g$ for each timestep independently, i.e. $g(\mathbf{z})[k]=g(\mathbf{z}[k])$.
We have

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{g\in\mathcal{G}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\rho(g(\mathbf{z}_{i}))\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq
T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\rho(W\mathbf{z}_{i}[k]+\mathbf{b})\right\rVert_{\infty}\right]$

Let $\mathbf{x}_{i}=i$, $i=1,\ldots,N$ and let
$\mathcal{H}=\\{h_{W,\mathbf{b},\underline{z},k}\mid(W,\mathbf{b},\underline{z},k)\in\mathcal{W}\times\mathcal{B}\times(Z\cup\\{0\\})\times[T]\\}$
such that
$h_{W,\mathbf{b},\underline{z},k}(\mathbf{x}_{i})=g(\mathbf{z}_{i}[k])$. Under
the assumption that $\mathcal{H}$ is symmetric to the origin, meaning that
$h\in\mathcal{H}$ implies $-h\in\mathcal{H}$ (equivalently
$(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}$ implies
$(-W,-\mathbf{b})\in\mathcal{W}\times\mathcal{B}$), we can apply (Truong,
2022b, Theorem 9) for the sigmoid activation and hence $\rho-\rho(0)$ being
odd, as follows.

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq
T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\rho(W\mathbf{z}_{i}[k]+\mathbf{b})\right\rVert_{\infty}\right]$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{h\in\mathcal{H}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\rho(h(\mathbf{x}_{i}))\right\rVert_{\infty}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma}\left[\sup\limits_{h\in\mathcal{H}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}h(\mathbf{x}_{i})\right\rVert_{\infty}\right]+\frac{1}{2\sqrt{N}}$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\sup\limits_{1\leq k\leq
T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}(W\mathbf{z}_{i}[k]+\mathbf{b})\right\rVert_{\infty}\right]+\frac{1}{2\sqrt{N}}$
$\displaystyle=\mathbb{E}_{\sigma}\left[\sup\limits_{(W,b)\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}(W\mathbf{z}_{i}+\mathbf{b})\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}\right]+\frac{1}{2\sqrt{N}},$

because the sigmoid is 1-Lipschitz and $\rho(0)=0.5$. Now we can apply Lemma
21 to get that

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{(W,\mathbf{b})\in\mathcal{W}\times\mathcal{B}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}(W\mathbf{z}_{i}+\mathbf{b})\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}\right]+\frac{1}{2\sqrt{N}}$
$\displaystyle\leq\sup\limits_{W\in\mathcal{W}}\left\lVert
W\right\rVert_{\infty,\infty}\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}\in
Z}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]+\frac{1}{\sqrt{N}}\sup\limits_{\mathbf{b}\in\mathcal{B}}\left\lVert\mathbf{b}\right\rVert_{\infty}+\frac{1}{2\sqrt{N}}$

Therefore, the sigmoid MLP layer is $(K_{W},K_{\mathbf{b}}+0.5)$-RC. The
restriction of an MLP to the ball
$B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$ maps to the ball
$B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}(1)$, because of the elementwise
sigmoid activation.

MLP with ReLU activations. Similarly to the sigmoid case, we assume the upper
bounds $K_{W}$ and $K_{\mathbf{b}}$ exist, but we don’t assume the symmetry of
the parameter set. The proof is the same as in the sigmoid case up to the
first inequality. Here we can apply (Ledoux and Talagrand, 1991, Equation
4.20) (this is the same idea as in the proof of (Golowich et al., 2018, Lemma
2)) to get

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{h\in\mathcal{H}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\rho(h(\mathbf{x}_{i}))\right\rVert_{\infty}\right]\leq
4\mathbb{E}_{\sigma}\left[\sup\limits_{h\in\mathcal{H}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}h(\mathbf{x}_{i})\right\rVert_{\infty}\right],$

where we used that $\rho(x)=ReLU(x)$ is 1-Lipschitz and the same logic for the
alternative definition of the Rademacher complexity as in the proof of Lemma
15, which results in a constant factor of 2. The constant 4 is then obtained
by the additional constant factor 2 from Talagrand’s lemma. The rest of proof
is identical to the sigmoid case.

The restriction of an MLP to the ball
$B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r)$ maps to the ball
$B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{v}})}(K_{W}r+K_{\mathbf{b}})$, because
the elementwise ReLU does not increase the infinity norm, hence we can apply
Lemma 21.

Proof [Proof of Theorem 18] We wish to apply Theorem 20 to the set of deep SSM
models $\mathcal{F}$. Let us fix a random sample
$S=\\{\mathbf{u}_{1},\ldots,\mathbf{u}_{N}\\}\subset\left(\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})\right)^{N}$.
As the loss function is Lipschitz according to Assumption 9, we have that for
any $f\in\mathcal{F}$

$\displaystyle|l(f(\mathbf{u}),y)|\leq 2L_{l}\max\\{f(\mathbf{u}),y\\}\leq
2L_{l}\max\\{K_{\text{Dec}}r_{L+2},K_{y}\\},$

thus $K_{l}\leq 2L_{l}\max\\{K_{\text{Dec}}r_{L+2},K_{y}\\}$.

Again by the Lipschitzness of the loss and the Contraction lemma (Shalev-
Shwartz and Ben-David, 2014, Lemma 26.9) we have

$\displaystyle R_{S}(L_{0})\leq L_{l}\cdot R_{S}(\mathcal{F}).$

It is enough to bound the Rademacher complexity of $\mathcal{F}$ to conclude
the proof. Let us consider the deep SSM models as a composite of mappings as

$\displaystyle
B_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}(K_{\mathbf{u}})\xrightarrow{\text{Encoder}}B_{\ell^{2,2}(\mathbb{R}^{n_{u}})}(K_{\mathbf{u}}K_{\text{Enc}})\xrightarrow{\text{B}_{1}}B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r_{1})\xrightarrow{\text{B}_{2}}\ldots\xrightarrow{\text{B}_{L}}$
$\displaystyle
B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r_{L+1})\xrightarrow{\text{Pooling}}(\mathbb{R}^{n_{u}},\left\lVert\cdot\right\rVert_{\infty})\xrightarrow{\text{Decoder}}(\mathbb{R},|\cdot|)$

Therefore, the SSM layer in the first SSM block is considered as a map
$B_{\ell^{2,2}(\mathbb{R}^{n_{u}})}(K_{\text{Enc}}K_{\mathbf{u}})\to
B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r_{1})$, while the rest of the
SSM layers in the SSM blocks are considered as a map
$B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r_{i})\to
B_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}(r_{i+1})$.This is needed, because
the Encoder is constant in time, therefore the Composition Lemma wouldn’t be
able to carry the $\ell^{2,2}$ norm of the input through the chain of
estimation along the entire model. This is one of the key technical points
which makes it possible to establish a time independent bound.

By the conditions of the Theorem and the stability assumption in Assumption 9
we have that the Encoder, Decoder, Pooling, SSM and MLP layers are each
$(\mu,c)$-RC for some $\mu$ and $c$ from Lemma 13. By Lemma 11 we have that
the composition of an SSM layer and an MLP is $(\mu,c)$-RC. A residual SSM
block is then $(\mu+\alpha,c)$-RC, because

$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{g\circ\mathcal{S}_{\Sigma}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}(g(\mathcal{S}_{\Sigma}(\mathbf{z}_{i}))+\alpha\mathbf{z}_{i})\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]\leq$
$\displaystyle\mathbb{E}_{\sigma}\left[\sup\limits_{g\circ\mathcal{S}_{\Sigma}}\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}g(\mathcal{S}_{\Sigma}(\mathbf{z}_{i}))\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]+\alpha\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]$
$\displaystyle\leq(\mu+\alpha)\mathbb{E}_{\sigma}\left[\sup\limits_{\\{\mathbf{z}_{i}\\}_{i=1}^{N}}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{z}_{i}\right\rVert_{\ell^{\infty,\infty}(\mathbb{R}^{n_{u}})}\right]+\frac{c}{\sqrt{N}}$

Hence, by Corollary 12, the whole deep SSM model is $(\mu,c)$-RC as a map
between $X_{1}=B_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}(K_{\mathbf{u}})$ and
$X_{2}=(\mathbb{R},|\cdot|)$. The Theorem is then a direct corollary of the
following Lemma.

###### Lemma 24

Let $\mathcal{F}$ be a set of functions that is $(\mu,c)$-RC w.r.t.
$X_{1}=B_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}(K_{\mathbf{u}})$ and
$X_{2}=(\mathbb{R},|\cdot|)$. The Rademacher complexity of $\mathcal{F}$
w.r.t. some dataset $S$ for which Assumption 9 holds, admits the following
inequality.

$\displaystyle R_{S}(\mathcal{F})\leq\frac{\mu K_{\mathbf{u}}+c}{\sqrt{N}}.$

Proof

$\displaystyle
R_{S}(\mathcal{F})=R(\left\\{(f(\mathbf{u}_{1}),\dots,f(\mathbf{u}_{N}))^{T}\mid
f\in\mathcal{F}\right\\})=\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{F}}\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}f(\mathbf{u}_{i})\right]$
$\displaystyle\leq\mu\mathbb{E}_{\sigma}\left[\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}\right]+\frac{c}{\sqrt{N}}$

By definition

$\displaystyle\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}=\sqrt{\sum\limits_{k=1}^{T}\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k]\right\rVert^{2}_{2}}$
$\displaystyle=\sqrt{\sum\limits_{k=1}^{T}\left\langle\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}[k],\frac{1}{N}\sum\limits_{j=1}^{N}\sigma_{j}\mathbf{u}_{j}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}}$
$\displaystyle=\sqrt{\sum\limits_{k=1}^{T}\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\sigma_{i}\sigma_{j}\left\langle\mathbf{u}_{i}[k],\mathbf{u}_{j}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}}$

Therefore

$\displaystyle\mathbb{E}_{\sigma}\left[\left\lVert\frac{1}{N}\sum\limits_{i=1}^{N}\sigma_{i}\mathbf{u}_{i}\right\rVert_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}\right]=\mathbb{E}_{\sigma}\left[\sqrt{\sum\limits_{k=1}^{T}\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\sigma_{i}\sigma_{j}\left\langle\mathbf{u}_{i}[k],\mathbf{u}_{j}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}_{\sigma}\left[\sum\limits_{k=1}^{T}\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\sigma_{i}\sigma_{j}\left\langle\mathbf{u}_{i}[k],\mathbf{u}_{j}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}\right]}$
$\displaystyle=\sqrt{\sum\limits_{k=1}^{T}\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\mathbb{E}_{\sigma}\left[\sigma_{i}\sigma_{j}\right]\left\langle\mathbf{u}_{i}[k],\mathbf{u}_{j}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}}$
$\displaystyle=\sqrt{\sum\limits_{k=1}^{T}\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\mathbb{E}_{\sigma}\left[\sigma_{i}^{2}\right]\left\langle\mathbf{u}_{i}[k],\mathbf{u}_{i}[k]\right\rangle_{\mathbb{R}^{n_{\text{in}}}}}$
$\displaystyle=\sqrt{\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{T}\left\lVert\mathbf{u}_{i}[k]\right\rVert_{2}^{2}}=\sqrt{\frac{1}{N^{2}}\sum\limits_{i=1}^{N}\left\lVert\mathbf{u}_{i}\right\rVert^{2}_{\ell^{2,2}(\mathbb{R}^{n_{\text{in}}})}}\leq\sqrt{\frac{1}{N^{2}}NK_{\mathbf{u}}^{2}}\leq\frac{K_{\mathbf{u}}}{\sqrt{N}}$

Hence we have

$\displaystyle R_{S}(\mathcal{F})\leq\frac{\mu K_{\mathbf{u}}+c}{\sqrt{N}}$

The constants $\mu$ and $c$ are obtained by substituting the results of Lemma
13 into the Corollary 12.

## References

  * Akpinar et al. (2020) Nil-Jana Akpinar, Bernhard Kratzwald, and Stefan Feuerriegel.  Sample complexity bounds for rnns with application to combinatorial graph problems (student abstract).  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(10):13745–13746, 4 2020.  doi: 10.1609/aaai.v34i10.7144.  URL https://ojs.aaai.org/index.php/AAAI/article/view/7144.
  * Alquier et al. (2013) P. Alquier, X Li, and O. Wintenberger.  Prediction of time series by statistical learning: general losses and fast rates.  _Dependence Modeling_ , 1(2013):65–93, 2013.
  * Alquier and Wintenberger (2012) Pierre Alquier and Olivier Wintenberger.  Model selection for weakly dependent time series forecasting.  _Bernoulli_ , 18(3):883 – 913, 2012.
  * Antoulas (2005) Athanasios C Antoulas.  _Approximation of large-scale dynamical systems_.  SIAM, 2005.
  * Bartlett et al. (2017) Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  In _Advances in Neural Information Processing Systems_ , pages 6240–6249, 2017.
  * Chellaboina et al. (1999) VS Chellaboina, WM Haddad, DS Bernstein, and DA Wilson.  Induced convolution operator norms for discrete-time linear systems.  In _Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No. 99CH36304)_ , volume 1, pages 487–492. IEEE, 1999.
  * Chen et al. (2020) Minshuo Chen, Xingguo Li, and Tuo Zhao.  On generalization bounds of a family of recurrent neural networks.  In _Proceedings of AISTATS 2020_ , volume 108 of _PMLR_ , pages 1233–1243, 8 2020.
  * Dauphin et al. (2017) Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier.  Language modeling with gated convolutional networks.  In _International conference on machine learning_ , pages 933–941. PMLR, 2017.
  * Devroye et al. (2013) Luc Devroye, László Györfi, and Gábor Lugosi.  _A probabilistic theory of pattern recognition_ , volume 31.  Springer Science & Business Media, 2013.
  * Edelman et al. (2022) Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang.  Inductive biases and variable creation in self-attention mechanisms.  In _International Conference on Machine Learning_ , pages 5793–5831. PMLR, 2022.
  * Golowich et al. (2018) Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  In _Conference On Learning Theory_ , pages 297–299. PMLR, 2018.
  * Gu and Dao (2023) Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces, 2023\.
  * Gu et al. (2021) Albert Gu, Karan Goel, and Christopher Ré.  Efficiently modeling long sequences with structured state spaces.  _arXiv preprint arXiv:2111.00396_ , 2021.
  * Gu et al. (2022) Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré.  On the parameterization and initialization of diagonal state space models.  _Advances in Neural Information Processing Systems_ , 35:35971–35983, 2022.
  * Haddouche and Guedj (2022) Maxime Haddouche and Benjamin Guedj.  Online pac-bayes learning.  _Advances in Neural Information Processing Systems_ , 35:25725–25738, 2022.
  * Hajek and Raginsky (2019) Bruce Hajek and Maxim Raginsky.  Ece 543: Statistical learning theory.  _University of Illinois lecture notes_ , 2019.
  * Hanson and Raginsky (2024) Joshua Hanson and Maxim Raginsky.  Rademacher complexity of neural odes via chen-fliess series.  _arXiv preprint arXiv:2401.16655_ , 2024.
  * Hanson et al. (2021) Joshua Hanson, Maxim Raginsky, and Eduardo Sontag.  Learning recurrent neural net models of nonlinear systems.  In _Proceedings of the 3rd Conference on Learning for Dynamics and Control_ , volume 144 of _PMLR_ , pages 425–435. PMLR, 6 2021.
  * Haussmann et al. (2021) Manuel Haussmann, Sebastian Gerwinn, Andreas Look, Barbara Rakitsch, and Melih Kandemir.  Learning partially known stochastic dynamics with empirical pac bayes.  _arXiv:2006.09914_ , 2021.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel.  Gaussian error linear units (gelus).  _arXiv preprint arXiv:1606.08415_ , 2016.
  * Joukovsky et al. (2021) Boris Joukovsky, Tanmoy Mukherjee, Huynh Van Luong, and Nikos Deligiannis.  Generalization error bounds for deep unfolding rnns.  In _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ , volume 161 of _PMLR_ , pages 1515–1524. PMLR, 7 2021.
  * Koiran and Sontag (1998) Pascal Koiran and Eduardo D. Sontag.  Vapnik-chervonenkis dimension of recurrent neural networks.  _Discrete Applied Mathematics_ , 86(1):63–79, 1998.
  * Ledoux and Talagrand (1991) Michel Ledoux and Michel Talagrand.  _Probability in Banach Spaces: Isoperimetry and Processes_ , volume 23.  Springer Science & Business Media, 1991.
  * Liang et al. (2019) Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes.  Fisher-rao metric, geometry, and complexity of neural networks.  In _The 22nd international conference on artificial intelligence and statistics_ , pages 888–896. PMLR, 2019.
  * Marion (2023) Pierre Marion.  Generalization bounds for neural ordinary differential equations and deep residual networks.  _arXiv preprint arXiv:2305.06648_ , 2023.
  * Maurer (2016) Andreas Maurer.  A vector-contraction inequality for rademacher complexities.  In _Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27_ , pages 3–17. Springer, 2016.
  * Orvieto et al. (2023) Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De.  Resurrecting recurrent neural networks for long sequences.  _arXiv preprint arXiv:2303.06349_ , 2023.
  * Qi et al. (2023) Xianbiao Qi, Jianan Wang, Yihao Chen, Yukai Shi, and Lei Zhang.  Lipsformer: Introducing lipschitz continuity to vision transformers.  _arXiv preprint arXiv:2304.09856_ , 2023.
  * Shalaeva et al. (2020) V. Shalaeva, A. F. Esfahani, P. Germain, and M. Petreczky.  Improved PAC-bayesian bounds for linear regression.  _Proceedings of the AAAI Conference_ , 34:5660–5667, 4 2020\.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Smith et al. (2022) Jimmy TH Smith, Andrew Warrington, and Scott W Linderman.  Simplified state space layers for sequence modeling.  _arXiv preprint arXiv:2208.04933_ , 2022.
  * Sontag (1998) Eduardo D Sontag.  A learning result for continuous-time recurrent neural networks.  _Systems & control letters_, 34(3):151–158, 1998.
  * Trauger and Tewari (2024) Jacob Trauger and Ambuj Tewari.  Sequence length independent norm-based generalization bounds for transformers.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1405–1413. PMLR, 2024.
  * Truong (2022a) Lan V Truong.  Generalization error bounds on deep learning with markov datasets.  _Advances in Neural Information Processing Systems_ , 35:23452–23462, 2022a.
  * Truong (2022b) Lan V Truong.  On rademacher complexity-based generalization bounds for deep learning.  _arXiv preprint arXiv:2208.04284_ , 2022b.
  * Wei and Ma (2019) Colin Wei and Tengyu Ma.  Data-dependent sample complexity of deep neural networks via lipschitz augmentation.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.
  * Zhang et al. (2018) Jiong Zhang, Qi Lei, and Inderjit Dhillon.  Stabilizing gradients for deep neural networks via efficient SVD parameterization.  In _35th ICML_ , volume 80 of _PMLR_ , pages 5806–5814. PMLR, 7 2018.