Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints
Authors: Dániel Rácz
Mihaly Petreczky
Balint Daroczy
Venue: Accepted by TMLR ()

Abstract: Deep SSM models like S4, S5, and LRU are made of sequential blocks that combine State-Space Model (SSM) layers with neural networks, achieving excellent performance on learning representations of long-range sequences. In this paper we provide a PAC bound on the generalization error of non-selective architectures with stable SSM blocks, that 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.

Published in Transactions on Machine Learning Research (10/2025)
Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability con- straints
Dániel Rácz
HUN-REN SZTAKI and ELTE, Budapest, Hungary
Mihály Petreczky
Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, France
Bálint Daróczy
deroczy, hww.:aa..aaann@@sssaiii.....eee
HUN-REN SZTAKI, Budapest, Hungary
Reviewed on OpenReview: https: // openreview. net/ forum? id= Vo6uHBv07k
Abstract
Deep SSM models like S4, $5, and LRU made of sequential blocks that combine State- Space Model (SSM) layers with neural networks, achieving excellent performance learning representations of long-range sequences. In this paper we provide PAC bound on the generalization error of non-selective architectures with stable SSM blocks, that does not depend on the length the imput sequence. Imposing stability the SSM blocks a standard practice in the literature, and known to help performance. Our results provide a thcoretical justification for the use of stable SSM blocks as the proposed PAC bound decreases as the degree of stability of the SSM blocks increases.
1 Introduction
The challenge of learning rich represenlations for long-range sequences (time series, text, video) has persisted for decades. RNNs, including LSTMs (Hochreiter) 1997) and GRUs (Cho 2014), struggled with long-term dependencies, while Transformers, despite improvements, still perform poorly on difficult tasks (Huang et al.
2024 Amos al. 2024
Recently, several novel architectures have been proposed which outperform previous models by a significant margin, for an overview see Huang et al. (2024 Amos et al. (2024). One notable class of such architectures are the so-called deep State-Space Models (deep SSMs), which typically contain several layers made of the composition of dynamical systems of either contimuous or discrete time, and non-linear transformatio
(e.g. Multilayer Perceptron (MLP), defined in Definition 4.4] (Gu et al. 2021b 2023 Gu & Dao 2023 Wang et al.) 2024 Gu et al. 2021a 2022 Smith et al. 2022 Fu et al. 2022 Orvieto et al. 2023). While SSM architectures
have been extensively validated empirically ly, the theoretical loundations of SSMs are less understood. One key point of these models that they are often implicitly equippod with some form of stability constraints for the SSM components. This motivates the question:
What is the role of stability in the success of deep SSM architectures for long-range sequences?
We partially address this problem by leveraging stability to derive a PAC bound which is independent of input sequence length. Our contributions are:
Stability related system norms for bounding the Rademacher complexity. We show that the Rademacher complexity of SSMs can be upper bounded by their system norms, such as the H2 and & norms (Chellaooia)
et al. 1999), which are well-known in control theory and linked to quadratic stability. This highlights stability

---

Published in Transactions on Machine Learning Research (10/2025)
not just a practical necessity, but as fundamental aspect of SSM architectures, making it the key takeaway of our work.
Rademacher Contractions. We upper bound the Rademacher complexity of multilayer deep SSM models, encompassing many popular architectures, by introducing the concept of Rademacher Contraction (RC), which, similarly to the celebrated Talagrand's Contraction Lemma (Ledoux & Talagrand] 1991p. allows us to directly bound the Rademacher complexity of deep models that employ nonlinearities. However, in contrast to Talagrand's contraction lemma which requires these nonlincarities to be fixed, i... to be independent of the model parameters, RC also handles the case when these nonlinearities are parametrised. Instead, we use a weaker assumption regarding bounded system norms that mcasure the degree of stability of dynamical systems and are widely used in control theory. In other words, the concept of Rademacher Contractions links a handy tool from the control literature to machine learning.
PAC bound for stable deep SSMs. Using the concept of Rademacher Contraction we establish a PAC-bound on the generalization error of deep SSMs. The resulting bound is independent of the input sequence length due to stability, and depends only implicitly on the depth of the model. Our results cover both classification and regression tasks for most of the popular deep SSM architectures.
Outline of the paper. In Section 2 we present the related literature, then we set some notation and present an informal statement of our result in Section 3 The formal problem statement along with the remaining notation and our assumptions are in Section 4
We propose our main result and a sketch of the proof in Section 5 A numerical example illustrating the result is in Section G The majority of the proofs and some additional details are shown in the Appendix.
2 Related work
Apart from Liu & Li 2024 Nishikawa & Suzuki (2024), SSM research primarily addresses modeling power, parametrization, and computational complexity, with limited focus on generalization bounds.
Theoretical analysis of SSMs. SSM modeling power has been studied via approximation capabilities
CCrone et al. 2024 Wang & Li 2024 Orvieto et al. 2024). with a survey in Tiezzi et al. 2024 This
paper, however, focuses on statistical generalization bounds. Nishikawa Suzuki (2024) derives statistical bounds on SSM approximation error, but only for a specific learning algorithm and parametrization, whereas our PAC bound is algorithm-agnostic. Experimental results suggest stable SSM parametrizations improve
learning (Wang& & Li 2024 Parnichkun al. 2024 Gu et al. 2021a Smith et al. 2022 Fu ct al. 2022 Gu
& Dao 2023 Smékal et al. 2024). Compulations complexity of inference and learning has been analyzed in
Massaroli et al. (2023): ; Gu et al. (2021b 2023). while Gu et al. 20023 | Yu et al. (2024) Wang & Li (2024)
investigated initialization techniques.
PAC bounds for single-layer SSMs. Liu & Li 2024) derived a PAC bound for a single continuus-timm LTI SSM using Rademacher complexity. In this context, LTI refers to Linear Tive-invariant systems and is defined in discrete time in equation [ In contrast, their result applies only to single SSM block without nonlinear elements, their bound grows with sequence length, and it does not account for discretization effects. Moreover, their constants are not directly linked to control-theoretic quantities like H2/61 norms. Their input assumptions also differ: while we assume bounded l2 norm inputs, they allow unbounded inputs, but require subgaussianity and continuity, the latter being inapplicable in discrete time and potentially imposing constraints on the sampling mechanism.
PAC bounds for RNNs. Since LTIs are core components of deep SSMs and a subclass of RNNs, RNN generalization bounds are somewhat relevant. Note however, that deep SSMs and simple RNNs are
theoretically different models and we do not see any trivial way to formulate deep SSM
simple RNN
vice verse, see Remark 4.9 Prior PAC bounds for RNNs use VC-dimension or covering numbers Koiran
& Sontag] 1998 Sontag 1998
Hanson et al.] 2021b), Radernacher complexity (Wei & Ma 2019 Akpinar
et al. 2020 Joukovsky et al.) 2021 Chen et al.] 2020 Tu et al. 2020), or BAC-Bayesian methods (Zhang
ct al. 2018 . However, prior PAC bounds grow with integration time (contimuous) or time steps (discreto),
limiting their use for long-range sequences. The bound for single vanilla RNNs in Chen et al. 22220) assumes
that the state matrix represents contraction and upper-bounds the E norm used here. In contrast, our
2

---

Published in Transactions on Machine Learning Research (10/2025)
bound is independent of state-space dimension, assumes only that the state matrix is Schur and assumes only bounded & H2 norms. The work Mitarchuk et al. (022)) also assumees that the state matrix is a contraction, works with tanh activation and prove a PAC-Bayesian bound for RNNs under a special saturation condition, however it is unclear under what conditions they hold for the considered RNN class, not to mention deep
SSMs considered the paper at hand. The proof techniques both in Chen el al. (2020) and Mitarchuk et al. (2024) are different to what we employ.
PAC bounds for Neural Ordinary Differential Equations. PAC bounds for NODEs have been developed in Hanson et al. (2021a); Hanson & Raginsky (0224) Marion (2023): ; Fermanian et al. (2021) These results are based on Rademacher complexity and they are either affine in inputs or defined in the
rough path sense. While a single block SSM interpreted in continuous time is affine in the input, general multi-block SSMs do not fall into this category. Moreover, these bounds are still exponential in the length of the integration interval, i.c., the length of the time series if fixed sampling time is used.
PAC bounds for deep networks and transformers. Trauger& & Tewari (2024) derive a sequence-length independent Rademacher complexity bound for single-layer transformers, improving slightly on [Edelman| et al. (022)) for multi-layer cases, though their bound grows logarithmically with the sequence length.
However, their results do not apply to SSMs and involve matrix norms that may scale with the attention matrix size. Maintaining norm stability for longer sequences requires reducing certain matrix entries. In contrast, the H2/l1 norms in this paper depend only on state-space matrices and remain invariant to the input length.
Generalization bounds for deep neural networks (DNNs) extend beyond RNNs and dynamical systems Bartlett et al. 2017 Liang et al. 2019 Golowich et al. 2018 Truong 2022b). Since deep SSMs can simulate DNNs and resemble feedforward networks with fixed input length, their bounds should align with DNN results. Golowich et al. (2018) provide depth-independen. bound under bounded Schatten p-norm and a polynomial-depth bound for ReLU networks via contraction. Other works use spectral (Bartlett et al., 2017) or Fisher-Rao norms (Liang et al., 2019) to mitigate depth dependence. [Trong (2022b) further refine Golowich et al. (2018) to a depil--independeell, non-vacuous bound for non-ReLU activations. When applied to deep SSMs with trivial state-space components, the bounds of the present paper are more conservative than those of Golowich al. (2018) for general activation functions, but are consistent with Golowich et al.
2018 Truong 2022bb for ReLU activation functions.
PAC-Bayesian bounds for dynamical systems. PAC-Bayesian bounds for various classes of dynamical
systems were developed in Alquier & Wintenberger (0112) ; Alquier et al. (2013); Shalaeva et al. (2020); ;
Haddouche & Guedj (2022a]: Haussmann et al. (2021): Haddouche & Guedj (022b); Seldin et al. 2012
Abeles et al. (2024h). The main difference between the cited papers and the present one are as follows.
1. Single time-series us. multiple independently sampled time-series. All the cited papers assumee that the data used for computing the empirical error is sampled from one single time series. The latter assumption required the use of various extensions of well-known concentration inequalities to the non-i.i.d. case. In particular, the obtained bounds all depend on some mixing coefficients. In contrast. to the cited papers, the present paper assumess multiple i.i.d. samples of time-series', so formally, the learning problem of the present paper is completely different from the one of the papers cited above.
PAC-Bayesian us. PAC bounds. The present paper presents a PAC bound, not a PAC-Bayesian one. PAC bounds have the advantage that they tend to be simpler to use and interpret, and they provide a uniform bound on the generalization gap, but they also tend to be fairly conservative. PAC-Bayesian bounds are more involved, they are sensitive to priors and they only bound the average (w.r.t. some posterior) generalization gap. However, they are potentially less conservative. This means that PAC bounds might actually be competitive with PAC-Bayesian ones in situations where the former is easy to evaluate and there are no obvious candidates for suitable priors. We believe that SSMs might fall in this category: the proposed PAC bound is easy to evaluate, and the choice of a suitable prior is far from obvious.
3. Different model classes. The classes of dynamical systems in Alquier & Wintenberger (012)) Alquier et al. (2013): Shalaeva et al. (2020): Haddouche & Guedi 2022a); Haussmann et al. 2022 do not.
3

---

Published in Transactions on Machine Learning Research (10/2025)
include state-space processes with partially observed state. The bound in Eringis et al. (0224] could, in principle, be applied to one block SSM without non-linearities, and Eringis et. al. (2023) can
be applicable to multi-block SSMs in case the latter satisfies some stability conditions which are
more stringent than the one in this paper. However, the application of Eringis ct al. (2023 2024 is possible only if the data used for learning is sampled from a single time series. The same is true for Abeles et al. (2024).
Finitc-sample bounds for dynamical systems. In recent years there has been significant interest in deriving bounds on the true loss for dynamical systems for particular learning algorithms (Oymak et al.
2019
Oymak& & Ozay 2022
Simchowitz et al.) 2019 Lale et al. 2020; Foster & Simchowitz) 2020 Ziemann
& Tu 2022 Ziemann et al. 2022 Tsiamis & Pappas 2019 Ziemann et al.) 2024). However, most of these
papers consider learning from one single time-series. Notable exceptions are Tu et al. (2024); Zheng & Li
(2020) Sun et al. 20200. where bounds for the true risk for linear State-Space Models were derived. However, there the derived bound does not relate the empirical loss to the true one, and it applicable only for linear dynamical systems, i.e., one block SSM. Moreover, the derived bound is specific to the learning algorithm employed. The latter is based on least-squares solution to linear regression, and it does not seem to be directly applicable to deep SSMs with non-linear blocks. In contrast, the results of the present paper are applicable to deep SSMs and to any learning algorithms.
PAC bounds for non i.i.d. data, There is a significant body of literature on PAC bounds involving Rademacher complexity (MeDonald Shalizi 2017 Mohri & Rostamizadchi 2008 Kuznetsov Mohri 2017] or other complexity measures for non i.idd data, including data chosen from single time-scries. As was mentioned above, in this paper we consider different learning problem, namely, learning from multiple independently sampled time series, as opposed to one single time series. Moreover, the cited papers propose PAC bounds which involve various measures of the complexity of the parameterization, e.g., Rademacher complexity, but they do not dwell on estimating those measures for various classes of dynamical systems, such as SSMs.
We argue that existing methods and techniques used in proofs for simple RNNs or single layer SSMs are not sufficient to handle deep SSM architectures, see Remark 5.6 and 5.7 for the details.
3 Informal statement of the result
Notation. Unless stated otherwise, we denote scalars with lowercase characters, vectors with lowercase bold characters and matrices with uppercase characters. The symbol @ denotes the elementwise product of vectors, for all x = "I,....,,,))) y = (V1...., vT.)² ,,.) E IR.. We use [n| to denote the set
i.., x Gg = (#. Dn (, (1,2,...,n} for n E N. For a vector v we denote by vl5) its jth coordinate. For vector valued time function u, the notation (()((t] refers to the jth coordinate of the value of function at time t. Furthermore, we use Σ to denote a dynamical system specified the context. The constant Tin refers to the dimension of the input sequence, T refers to its length in time, while Nout is the dimension of the output (not necessarily a sequence). Denote by (B.) and e7 (R") the mhite-dimensional Banach spaces generated by the all finite sequences over R of length T', viewed as vectors of RT,, with the Eucledian norm 11-I12 and the supremum norm || over T respectively. If X is a Banach space, we denote its norm by || llx-- In particular, ||u| ||u|] (R.))) E [|][ and |||||| (2+)) S[P [K]] For Banach space X, B (r) (x X || I <r) denotes the ball of radius r r>0 0 centered at zero.
2
Learning problem. We consider the usual supervised learning framework for sequential input data. That is, we consider a family F of models, each model f F is function which maps sequences of elements u of the input space Th to outputs (labels) in Y C Rous, We fix the length of the sequences to T and we denote by U the set of all sequences of elements of 1 of length T. That is, f E F can be viewed as a function ::l :u= > y.
from some probability distribution D, where u, E u is a sequence of length T' having elements in Ti, and y, belongs to y. The probability measure determinod by D is defined on the o-algebra generated by the Borel sets of l x y R ), where the set U of
A datasot is an i.i.d sample of the form S =
4

---

Published in Transactions on Machine Learning Research (10/2025)
sequences of elements of R of length T is identified with RT="" We use the symbols E(uy))D: P(nyy)D ESDDN and SSDDN to denote expectations and probabilities w.r.t. a probability measure 'D and its N-fold product D& respectively. The notation S ~ DN tacitly assumes that S E (U x M)y, ie. S is made of N tuples of input sequences and output labels.
An elementwise loss function a function é: :: x y + R such that ((y,y) iff y y'. Its role is to measure the discrepancy between predicted and true outputs (labels).
We define the empirical loss as (fm = * E {(f(u.), and the true loss as C(f) = Blux))=(((((u))x))) y)]. The goal of this paper is to bound the generalization error or gap, C(J) Emp (f) uniformly for all models f F.
We will be interested in model classes F, clements of which arise by combining neural networks and the so-called State-Space Models.
Model class of SSMs. A State-Space Model (SSM) is tiscrete-time, Linear Time- Invariant (LT1) dynamical system of the form
xlk + 1] = Ax[k] + Bu[k], x[1] y[k| [x + Du(A]
Σ
(1)
where A E R E R", C X", and D R x are matrices, [[kk),[[k and y[k] are the input, the state and the output signals respectively for k: 1,2..... TT where T is the number of time steps. Here n2 is the state dimension, na is the input dimesion and ny is the output dimension of the SSM (LTI system). Note that na, and My may not coincide with Rin and nout as the former ones refer to the SSM's input and output, while the latter ones refer to the actual dataset. In this paper we are interested in internally stable (stable for short) SSMs, i.c. in SSMs for which the matrix A from equation | is Schur. By definition, a matrix A is Schur if its eigenvalues are inside the complex unit disk. This is a widespread definition in control theoretic literature (Antoulas] 2005).. We remark that within other domains, matrix being Schur may be defined in different way which need not be equivalent to our definition.
Intuitively, stable SSMs are robust to perturbations, i.e., their state and output are continuous in the initial state and input, see for instance Antoulas (2005) for more details.
Remark 3.1 (Relationship between discrete- time SSMs (equation
1 and continuous-time SSMs). In the literature, the SSM layer is often defined as a contimuous-time system
(t) Axxx (t) + (tt(t), yo(t)= = (x. Dv(t), (0) =0
(2)
where E [0, oo). In order to transform equation 2 to a model mapping sequenees to sequences, discretizod
in time (Gu et al. 2021a 2022 Smith el al. 2022 Gu & Dao, 2023 Dao & Gu. 2024). That is, the following discrete-time system is considered:
x(k + 1] A(Ax)x(K) + B(A)) y[k] Cx([]] + Du(k), x[1] 0
such that the matrix valued functions A(A) and B(A) are defined as A(A) = A.A, B(A)= = for e c ()) Bds, A = A(u(k)) is a function of u(k)), and if v() = u[k] for all E (E A. E A.), then x[k] = x. (AE-1), ykk] (=(A,))), & [TT, and Ao := O. If A& equals a constant A, then equation 3 describes an LTI system given by equation D with A A(A) and B = B(A). Note that if Ag is Hurwiiz,, i.e., all its eigenvalues have negative real part, then A(2) is Schur matrix for A > O, i... the arising SSM block is stable. Also, A being Hurwitz is equivalent to equation 2 being stable Antoulas (2005)
Remark 3.2 (Selective SSMs). If A in equation 3 depends on the input as in Gu & Dao (0023): ; Dao & Gu (024)), one obtains a discrete-time Linear Parameter- Varying system (LPV) (Töth) 2010), or a so-called selective State-Space Model. In this case A and B (sometimes C as well) depend ulk at each step. While they are more general, than LTI models and widely used in practice, they present greater analytical challenges. Extending our results to such models remains future work.
An SSM given by equation I induces a linear function SE.T which maps every input sequence ufi).... u u to the output sequence y(1). y(I)...... [T.). In particular, S5,r has well-defined induced norm as a linear operator,
5

---

Published in Transactions on Machine Learning Research (10/2025)
defined in the usual way. For stable SSMs this norm can be bounded uniformly in T.
A SSSM block is residual composition of the SSM with non-linear function applied element-wise, i.e. an SSM block maps the sequence u[l]...., u[Z] to the sequence defined by (u] g(SE,r(u)(() au(k) where a E R the residual weight. deep SSM model is a composition several SSM blocks with an encoder, and a decoder transformation preceded by time-pooling layer. That i8, the input-oulput map of a deep SSM is a composition of functions of the form fDee fPool fBr. o... fBi f where denotes composition of functions. The functions fūae and fDe are linear transformations which are constant in time and are applied to sequences
tement-wise, while fB; is the imput-output map of an SSM block for all < < L, where L is the depth of the model. This definition covers many examples from the literature, e.g. S4 Gu et al. 2021a), S4D Gu et al. 2022). S5 (Smith et al. 2022) or LRU (Orvieto et al., 2023
The main result of this paper is the following PAC bound for deep SSMs:
Theorem 3.3 (Informal thcorem). Let FF be set of deep SSM models with stable SSM blocks, which satisfy number of mild regularily assumplions. There exist constants K₁ and K which depend only on the model class F, such that for any time horizon T 0, any confidence level 1 8 O, with probability at least 1 5 over the data sample S ~ DN,
K5 + 4Kg v log (3)
of (fF::(f) - Comp(f)
(4)
VN
With standard arguments on PAC bounds and Rademacher complexity, the result above also implies the following oracle incquality for the Empirical Risk Minimization framework (Shalev-Shwartz & Ben-David, 2014).
Corollary 3.4.
With the assumptions of Theorem 3.3 for fERM argmin (f), for any >> 8 8>0 0,
with probability at least 1 over the dala sample S DN
Ky + 5kg V 2 log (
((fEnm) S min L(f) +
(5)
fEF
VN
Bounds given by inequalities 4 and 5 ensure that as N grows, the empirical and true losses converge, and the Iearned model's true loss approaches the minimum possible loss.
The term Ky depends on the norms the SSM blocks and the magnitudes of non-SSM weights, but it remains independent of T. Since general, norms of SSMs decrease as their stability increases, stability makes the generalization gap insensitive sequence length, and increasing stability further decreases it. Specifically, for deep SSMs with & layers, K, ((SSM norm)* (non-SSM weight norm)*). While Ky grows exponentially with the depth unless all components are contractions, high non-SSM weights be offset by lower SSM norms. These norms decrcase as SSMs bocome more stable, though stability is not directly tied to weight magnitudes - stable SSMs can still have large weights. This exponential dependence aligns with bounds for deep neural network (Golowich et al. 2020 Truong 2022a
Depth may negatively impact the generalization gap, but this does not imply poor gencralization overall. Even if Ky is large for deep SSMs, inequality implics that if the best true error is small then the generalization gap can still be small. Additionally, N increases, the influence of K5 diminishes, suggesting deeper models require more data, which is consistent with findings deep neural networks.
4 Formal problem setup
4.1 Rademacher complexity
Our main result is essentially an upper bound on the Rademacher complexity of a set of deep SSMs with specific properties, thus we begin by recalling the definition.

---

Published in Transactions on Machine Learning Research (10/2025)
Definition 4.1 (Def. 26.1 in Shalev-Shwarrd & Ben-David 2014
The Rademacher complexity of bounded set A C m is defined as
R(A) = EE, sup
0:0
.EA
where the random variables o, are i.dd such that P(o; = 1) = P(a, = -1) = 0.5 and o = (01..... ................................ am) The Rademacher complexity of set of functions defined over u y, with respect to the sample S (uu.))))).......... E (24 V/N defined as
m Σ o,
Rs(H) R ym)) F h H() Eg
sup NEW m
Intuitively, the Rademacher complexity Rs(H) tries to capture the sensitivity of H. to overfit random noise, m The term Σ y.) can be seen as an inner product, therefore the supremum over H. has the intuitive i=1 meaning of finding the function h H that aligns best with the random vector σ. In this context, the alignment is mcasured with an inner product opposed to the usual cosine similarity, where the inner product is inversely scaled with the norm of the vectors. Practically, the ability to align with a random vector correlates with the ability to overfit the data. The expectation over o means we consider the average (over the random vectors) maximum alignment between the function outputs on the data sample and the random vector.
A different intuitive explanation of the above definition be found in Section 26.1 1 of Shalee-Shwartz & Bavid (2014). In nutshell, this second explanation is that the sum 1 Li o;h(u, 1 EE= Li=I....m. 1 h(u,, - 1 E -==...... h(,,.y;) represents the difference between the average perfor- mance of the model on the validation dalaset (data points for which = 1) and on the training datasel (dala points for which o, = -1), when the elements of both datasets are chosen randomly. Then the expectation over sigma of the supremum these sums is intuitively proportional to the worst-case generalization gaps (difference between the true loss and the empirical loss).
The following is standard generalization theorem, involving Rademacher complexity, that we build our proof on.
Theorem 4.2 (Theorem 26.5 in Shalev-Shwartz & Ben-Davit 2014 Let Lo denote the set of functions of the form y) + y( for f F. Let K₁ be such that the functions from Ln all take values from the interval [0, Ki). Then for any 8 E (0, 1) we have
2 log (+)
PSWDN Yf (fEF: C(f) Cemp()) (f) s (2)s(L)) + +KK/
2 11
N
4.2
Deep SSMs
Stable SSMs. In the sequel, we consider solutions of equation 1 on the time interval [1, [1, where the value of T' is fixed, As it was mentioned in Section 3 we consider only LTI systems given by equation [ for which the matrix A is Schur. It is well-known AAttoulas 2005) that (internal) stability equivalent to the A matrix in equation g being Schur, i.e., meaning all the eigenvalues of are inside the complex unit disk. In particular, sufficient, but not necessary condition for stability is that A is a contraction, i.e. ||Al|2 < 1. Moreover, for a system given by equation with A being Schur matrix, there exists a non-singular matrix 1s representing a linear basis transformation such that the transformed system given by A' PAP-11 B' PB, C' = CP-1 D' D'= D has the same Markov parameters as the original one (namely CA B+ C' (A''** for all k e N) and || < 1. Markov parameters of an LTT system are the members of the set uf l N} and are widely used in control theory. In fact, the output of an LTI system can be formulated as a function of the
input sequence and its Markov parameters, namely y[k] Du(k] + Σ CA Buík for O
7

---

Published in Transactions on Machine Learning Research (10/2025)
All popular architectures in the literature stable SSM blocks, Table 4.2
If equation describes stable continuous-time linear system, i.e. A. is Hurwitz matrix (all the eigenvalues of A. have a negative real part), then A(A) is a Schur matrix (Antoulas 2005 i.e., the corresponding discrete-time SSM stable.
Input-output maps of SSMs as operators on = As was mentioned in Section 3 an SSM given by equation | induces an input-output map SE,T, which maps every input sequence u|l] u to output sequence y y(T], and can be described by a convolution y(1] = (x())[i Σj=1 H j+1], where Hy = D and H3 CA B, > 0. The map Sg,r can be viewed as linear operator Sp.r Ey (R" + ET (R""), for any choice & (oo, 2). In particular, S2, has well-defined induced norm as a linear operator, defined in the usual way,
S (R)
| boo.p"
sup me (R*u)
||u| (R(W)))
Model
SSM
Block
LTI, A. - A - PQ" block-diagonal, stable
SSM +
S4
Gu et al.
2021a
nonlinear activation
LTI, A. exp(ARe) + Asm block-diagonal, stable
SSM +
S4D
Gu et al.
2022
nonlinear activation
SSM + nonlinear activation
$5
Smith et al.
2022
LTI, stable diagonal A.
SSM + MLP GLU + skip connection
LTI, diagonal A stable complex exponential parametrization
LRU
Orvieto et al.
2023
Table 1: Summary of popular deep SSM models. The SSM blocks in these models arise by discretizing a
continuous- time system, see Remark 3.1
It is a standard result in control theory that if Σ is internally stable, the supremum |Elcccp supr>o [|St,Tlooopp of these norms is finite, see Antoulas (2005). In this paper, we will use upper bounds on the induced norms [|S,,r r E {2, oo} to bound the Rademacher complexity. In turn, these norms can be upper bounded by the following two standard control-thcoretical norms defined on SSMs. For an SSM E given by equation let us define the & (Chellaboina et al. 1999) and H2 (Antoulas) 2005 norms of Σ, denoted by ||Σ|], and |X]| respectively,
|ا||| = max Isis
|Dlll + Σ ICAA
k=
|ا||| =
| +
IC
k=
Lemma 4.3 (Chellaboina et al. 19991). For system given by equation it holds that suprzo |E
||||| and supreo |S loc.0
An upper bound on the norms || = 1,2 can be easily computed by solving a suitable a linear matrix incquality (LMT), which standard tool control theory (Boyd et al. 1994). Morcover, ||]| can also be computed using Sylvester equations, for which standard numerical algorithms exist (Antoulas 2005). Alternatively, both norms be computed by taking sufficiently large finite instead of
8

---

Published in Transactions on Machine Learning Research (10/2025)
the infinite sum used in their definition. Finally, if ||A|2 < B < 1, then an easy calculation reveals that | and |اا|| S VIDII + C 1-83
||]|| < ( (IDIl2 + 1-3
Deep SSM models. In this paper,, we consider deep SSM models, which consist of layers of blocks, each block representing an SSM followed by a nonlinear transformation (MLP, Gated Linear Units (GLU), defined in Definiton 4.5). Morcover, these blocks are precoded by a linear encoder and succeoded by a pooling block and a linear decoder.
In order to define deep SSMs, first we define MLP and GLU layers. Then we define SSM blocks, which are compositions of SSMs given by equation ! with MLP and GLU layers. Finally, we define deep SSM models, where all these elements are combined.
Definition 4.4 (MLP layer). An MLP layer is a function f: f: + ET (R**) such that there exist an integer M 2 1, matrices and vectors {W b, - and activation function p IR R. such that W; P and b E R", i E [M], n1 = ny and RM+1 = Buy and
f(u) gWa fas .... bw (u(k))
where & E [T], fw..b. (x) = p(g., (x)) and gw.bb, (x) = Wix + b, for all E [M + 1]. By slightly abusing the notation, for a vector v, p(v) denotes the clementwise application of p to v.
Intuitively, a MLP layer represents a deep neural network applied to a signal at every time step. The function fW.bb, represents the ith layer of this neural network, with activation function p and weights W,, by. For the sake of simplicity, activation function assumed to be the same across all layers of the neural network.
Definition 4.5 (GLU layer (Smith et al. 2022 ). A GLU layer is a function of the form f 27 (RRV) + exp (R"x) parametrized by a matrix W such that
[(u)[}] = GFIU o o(W GFLU(u())),
(7)
where a is the sigmoid function, i.c. (xx) = (1 (1+ and GELU is the Gaussian Error Linear Unit
(Hendrycks & Gimpel 2016), namely GFLU(s)= x where ((x) = V -= ds is the cumulative distribution lunction of the Gaussian standard normal distribution. Analogously to Definition L.4 for a vector v, (v) and GELU (v) denote the elementwise application of and GELU to v, respectively.
Note that this definition of GLU layer differs from the original definition in Dauphin et al. (2017), because deep SSM models GLU is usually applicd individually for cach time step, without any time-mixing operations. See Appendix G.1 in Smith et al. (2022).
Next, define SSM block, which is composition of an SSM layer with a MLP/GLU layer. Definition 4.6. An SSM block is a function JDTB (x==) + (R o0), such that for all e [T]
pTT (n) [K] = g (x) + ou [k]
(8)
for some SSM Σ given by equation some MLP or GLU layer g: E (R*u) EF (RTx) and constant a.
We incorporate a so that the definition covers residual connections (typically a is either or 0). The definition above is inspired by the series of popular architectures mentioned in the introduction.
Finally, following the literature SSMs, we define deep SSM model as composition of SSM blocks along with linear layers
combined with time-pooling layer in case of classification.
Definition 4.7 (encoder, decoder, pooling). An encoder is function f eb (TR"..) e (R**), where P E (2, } is an integer, such that there exists matrix WFne for which f(u)[k] Wkke A decoder is a function f: Rm + Beout such that there exists matrix Wee such that f(x) = Wee A pooling layer is the function pPool ego (R..) R defined by (u) 1 Ei_ u(k)).
An encoder corresponds to applying linear transformations to each element of the input sequence. The pooling layer is typically an average pooling over the time axis.
9

---

Published in Transactions on Machine Learning Research (10/2025)
Definition 4.8. A deep SSM model is function f (R"ii) - R Mout of the form
Dee fPool pBL .... fB. B
where fluc is an encoder and fDe is a decoder, and fb. are SSM blocks for all i, and fPool is the pooling layer.
Definition 4.8 covers many important architectures from the literature, e.g. $4, S4D, S5 and LRU, Note that we did not include such commonly used normalization techniques as batch normalization the definition since they are not relevant for our results. Indeed, once the model training is finished, a batch normalization layer corresponds applying a neural network with linear activation function, i.e., it can be integrated into one of the neural network layers. Since the objective of PAC bounds is bound the generalization error for already trained models, for the purposes of PAC bounds, normalization layers can be viewed layer of neural network.
additional
Remark 4.9. The usual definition of a single layer, simple RNN (e.g. Chen et al. 2020 is
h = o + Why +b)
(10)
yk oV c)
where (U, W. V,b, c) the parameters of the RNN and 01, 02
fixed activation functions.
A single SSM block (Definition 4.6 is made of a single, linear SSM layer followed by a time independent nonlinearity. The linear SSM layer can be represented by simple RNN. However, even a special case of such a SSM block would result in an RNN for which the activation functions σ1 and 02 in equation I0 are different. Using MLPs or deep stack of such SSM blocks would result in dynamical system whose structure completely different from RNNs. Note that the MLP cannot be viewed as an activation function in equation TO unlike the fixed activation function in equation TO the MLP in the deep SSM is not part of the mimemmixing component and it is parametrized, i.e. it is learned. Furthermore, SSM layers are discrete-time LTI systems, they are invariant under lincar state-space transformations, whereas simple RNNNs are not.
4.3 Assumptions
Before moving forward discuss the main result, we summarize the assumptions we make in the paper for the sake of readability.
Assumption 4.10. We consider a family of deep SSM models of depth such that the following hold:
1. Architecture.
There exist families FEne of encoders, FDe of decoders, E SSMs, F, [L], of nonlinear blocks, and collection of residual weights {a:]_, such that if f E F given by equation then
(1) the encoder fEn belongs Frne; the decoder DDe belongs to Fren:
(2) and if the ith SSM block fB: is given by equation g then Σ E E, ag, and g belongs to F.
2. Scalar output.
Let nout =
3. Lipschitz loss function.
Let the elementwise loss l be Li-isshhitzz continuous, i.e., (()18()) -(22, v/4 - Le(ba - 32l p2|+ + v/l) for all y1, 32, Vl. v/ e R.
4. Bounded input.
There exist K, > 0 and K2 > 0 such that for any input trajectory and label y sampled from D. with probability 1 we have that [|ulle,.rem) S Kn and bol < Ky,
10

---

Published in Transactions on Machine Learning Research (10/2025)
5. Stability & bounded encoder and decoder norms.
(1) Each element Σ of & stable, i.e., if Σ is of the form equation [ then A a Schur matrix. Moreover, there exist constants K₁ and K2 such that ||اااp S Kp, p= 1,2 for each > E E.
(2) There exists constants K KDe such that if f E FEnc; and f(u)[k] WEne u[k] for matrix W WEne; then ||Wene 1|,2 < K and if J E FDee and f(x) WDxx then WDelll222 < K
6. Nonlinear blocks are either MLP or GLU.
For every e [4] Fi is either family of MLP layers family of GLU layers. In the former case, all elements of F; are MLP layers with M, layers and with the same activation functions pi which is either ReLU or a sigmoid-like function which satisfies the following: Pr(0) = 0.5, it is 1-Lipschitz, p(x) E [-1,1], pi(z) - (0) odd for any x in the domain of p. If Fi is a family of GLU layers, then each o; is the actual sigmoid function, ie. (xx) = (1 1e =---1
Bounded weights for MLP.
For every E [L] such that F; a family MLP layors, there exists K Kw., Kb such that for every f E F, given by equation with M M, and p p= Ps. the weights of satisfy
| < Kw.. MEM+
max
max ME
[b, loc < Kb,i.
8. Bounded weights for GLU.
For every i E [L] such that Fg is a family of GLUs, there exists a constant KALv, such that for every f E given by equation with o = o; Wo < KGLU,
The first assumption is standard one, the only restriction is that all deep SSMs have the same depth and all SSM blocks have the same residual connection.
Assumption 2, though being restrictive, covers key scenarios such as classification and 1-dimensional regression, which are central to theoretical analysis.
Assumption 3 requires the loss function to be Lipschitz-continmuus, which is a standard assumption machine learning and holds for most of the loss functions used in practice, including the squared loss on bounded domains, the & loss and the cross-entropy loss (see Appendix This ensures boundedness during the learning process.
Assumption 4 is also fairly standard, as input normalization is common in practice.
Assumption 5 is the key assumption enforcing SSM stability via structured parametrization. Beyond numerical benefits, stability ensures reliable predictions by preventing small input changes from cansing large output variations, crucial for learning and inference. Many prior work mentioned in Section 2 proving PAC bounds for simple RNNs assume that ||U||2 < for U in equation 10 corresponding to || < 1 in equation [ In contrast, we require the system norm be finite that is achieved by assuming that the SSM layers are stable, i.c. the state matrix A is Schur in every layer. As stated in Section 4.2 this does not necessarily imply that ||Al|2 < 1. The converse holds, namely ||A]|] 1 implies stability.
Assumptions 6 and 7 are again considered standard, requiring non-linear layers to be either all MLPs or all GLUs with specific activations and enforcing bounded weights for the encoder, decoder, and MLP MLP/GLA /GLU layers.
5 Main results
We derive Rademacher complexity-basee generalization bound for deep SSM models, independent of sequence length. The key challenges are: (1) bounding the Rademacher complexity of SSMs, (2) extending this to hybrid SSM-neural network blocks, and (3) handling deep architectures with multiple such blocks. For stable SSMs, we show their norm bounds the Rademacher complexity for any sequence length. To address the second and third challenges, we introduce Rademacher Contraction, universal framework that enables componentwise complexity estimation in deep models.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Definition 5.1 ((p, R--Radmmacher Contraction). Let X1 and X2 be subsets of Banach spaces X1, X2, with norms || 112, and || 11,, and let μ 2 0 and c 2 0. A set of functions + { X1 - X2) is said to be (u, -a-aammme Contraction, or (H, c)-RC in short, if for all N E EN+ and Z S X1 we have
N axp u;)
sup pe
sup (u.),
S BB
sup [ui),
1 N 1=1
c
(11)
N 1=1
VN
EZ
where of are ii.d. Rademacher random variables, i E [M], ie. P(o, 1) = P(o; = -1) = 0.5 and
o = (TI...... (O)....,NN)'
Rademacher Contractions in the literature. While the concept of RC is new, special cases of Definition 5.1 have been used in the literature for bounding Rademacher complexity of deep neural networks In Golowich et al. (2018) the authors considered biasless ReLU networks and proved a similar inequality using Talagrand's Contraction Lemma (Ledoux & Talagrand 1991p. In Truong (022b)), 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 in Truong (2022b) 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-chaing in Truong (2022a), however the generalization error was measured via the marginal cost and the (u, 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 incquality 11 and apply it to deep structures.
In recent work Trauger& & Tewari 2024), the authors consider Transformers and implicitly establish similar inequalities inequality [1 by bounding different kinds of operator norms of the model and managed to extend it to stack of Transformer layers. Besides these similarities, some key differences in our work are that Definition 5.1 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 the (n, cCC inequality. Inequality 11 allows relating the Rademacher complexity of a model class the Rademacher complexity of its inputs via the constants p and e. These constants depend the model class well as the domain X₁ and range X2 of the models. As shown next, the RC property is preserved under the composition of layers.
Lemma 5.2 (Composition lemma). Let + X1 + X2) be (11, and क (p2 : X2 - X3) be (22, Then the set of compositions 42 ob == fip p2 (01 E $1, b2) is (M1 1201 + c2)
The proof is in Appendix B Consequently, for deep models composed of layers that each satisfy the RC property, the entire model class is RC as well. Then inequality [Maaa be applied to bound the Rademacher complexity of the deep model by that of the input sample. The latter can often be bounded, for instance:
Lemma 5.3. ENT
Σ U:U:
<
VN
Ku for all ||ul| E Bgg(rr))) (Kaem)m(K))) (K.), ie [N).
The proof follows standard argument, e.g. see Lemma 26.10 in Shaley-Shwartz & Ben- 2014). for completeness it is presented in Appendix B
That is, in order to bound the Rademacher complexity of deep SSMs, all we need to show is that each component of a deep SSM model is (14, c)-RC for some ja and c with compatible domains and ranges. To this end, for each E [L], define the family JDTB of ith SSM blocks as the family of all SSMs blocks FDTB given by equation such that g E F,, E E E, a at In particular, for any f E F given by equation g the ith SSM block fB, belongs to F.TBB.
Lemma 5.4. For each set X of model layers interpreted as functions between Banach spaces such that X (FEnc. Fuee, F.FDTT , E [L,,E, (PP)))) the set X B(r), i.e. the elements of X restricted a ball of radius r, is (x())- in their domain, and the range of the elements of X B(r) is subset of
12

---

Published in Transactions on Machine Learning Research (10/2025)
LAYER TYPE X, X' x F.
px((r)
(x)
fx(r)
X = FEuc
KEne
0
Kyner
X F
KDec
0
KDee
DEFINED ON ef (R"
K1
0
Kir
X' = & DEFINED ON (RRU))
K₂
0
K2r
x= (SPool)
1
0
iTH SSM BLOCK x= JDIB
i=1
K2 (K2r) + +01
cx (Kar)
Ar,(K2r) + oir
i>1
Kipz, (Kir) + t.
(Kir)
(Kir) tar
Table 2: Table of (ux(r), cx(r)) and (r) constants for Lemma 5.4 The layer types each considered component of a deep SSM model as described in Section 4.2 The various constants denoted by some form of are upper bounds from Assumption 4.10 and 0; are the residual weights. The terms (r), ex, (r) and (r) are in Table 3 for each type of considered nonlinear layer.
NONLINEARITY FPTB
(r)
CF,
(r)
x=
Mr.
M.
MLP WITH RELU
(1Kw.) M,41
4Kb,² Σ (4Kw.))
MM+1 r + Kb
Σ Kia
MLP WITH SIGMOID
Wwi
(Kb, + 0.5)
Σ (Kw.a)
Kw + Kb.
16(r2² +2)
GLU
0
= KOLU, +
Table 3: Table of (FF and fr, constants for Table 2 and Lemma 5.4
the ball of radius (r(r), where (x((r,,x((1) and (r) are defined in Table 2 for each. SSM blocks and for encoder/decoles layer, i.e. Fi, E [L] and in Table for the nonlinear layers, i.e. X F,, i [L].
The proof is Appendix B The lemma implies that an SSM layer can only increase the input's complexity by the factor | p = 1,2, and the latter gets smaller as the system gets more stable. The results on the MLP layers rely on proof techniques from Truong (20226 a) used bound their Rademacher complexity. These bounds MLP layers are considered conservative, however improving existing bounds the Rademacher complexity of MLPs are out of the scope of this paper. The proof for the GLU layer is similar to that of the MLP layer, although handling the elementwise product in GLU requires some additional steps. In contrast to other layers, for GLU the values of p, depend on the magnitude of the inputs. Note that for all the considered layer types except GLU, the (μ, cC- property holds for unbounded domains. The only reason we consider bounded domains and ranges is for Lemma 5.4 to hold for GLU layers. This can be seen from the fact that for SSM blocks with MLP nonlinearities, the constants μA, (r), (r) and fr (r) independent of for all considered according to Table 3
To simplify the notation, in the rest of the paper we denote (x(r), (x() and (x(r) by p(r),c(r) and f(r) respectively, whenever X' is clear from the context, and for i E [L], we sometimes denote μo (r), f (r) by (x(r). and fr( respectively.
Using Lemma 5.4 and Lemma 5.3 and classical Rademacher complexity based PAC bounds, e.g. see Shalev Shwartz & Ben-Davie 2014 Theorem 26.5), leads to a PAC bound for deep SSMs, summarized in the main theorem below.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem 5.5 (Main). Let Assumption 4.10 hold. Then for any 8 E () have
PSNDN (SEF:
L(S) Cémp (f) s
HKuLi + chi + 4Kr
2 log (+)
1
(12)
where K; 24, M Dee Ky). The term rL+1 obtained recursively for all i [L + 1].
KEncKu
i ==1
T2
ir, (K2r1) an
i i= 2
(13)
Fr (K) - i>
where f,, (r) are as in Table 3 of Lemma 5.4 Moreover, let us define μ1 = ur, (K2r1), c1 = cF (Ker1), and for 2.... L, let us define μ4 = pas, (Kirs), C (Krr)).) Using these quantities, the constants μ and are defoned follows
I 1 Knne Dec (ez K2 o1) II (ucK + +a))
(14)
L CL
(1 (4, + and (
c= Dec
+
Σ
(g))
1=
Sketch of the proof. From standard PAC bounds involving Rademacher complexity Theorem 26.5) and the Contraction Lemma (hhlee-Shwaar & Ben-David
Shalev-Shwaid Shwartz & Ben-
David 2014
2014 Lemma 26.9), it
follows that with probability at least 1-ô, for any f E F, C(f) (
Cmmp (f) S Eo
sup sEF
N
Σ
ou,(
(R
2 (4//6) From Lemma 5.2 and Lemma 5.4 it follows that the restriction of the elements of F to the ) is (M, c)-RC with μ and as in the statement of the Theorem.
Kiy
ball
B (Bmia) (Ku) of radius Ku in lz (I
Hence, E.
sup sEF
Σ o.f(u,))
S E
Σ ouu
S
#Kute The complete proof VN
VN
(BPmm)
(Bmm))
can be found in Appendix
B
Discussion and interpretation of Thcorem 5.5 The bound vanishos as N grows and remains independent of the sequence length and state dimension an advantage over typical sequential model bounds that diverge with T.
The key constants μ and Note, that for deep SSMs with no MLP layers, is zero. Intuitively, j and are somewhat analogous to Lipschitz constants of deep networks, although the formal relationship between the two requires future work.
The bound appears exponential in depth, like in case deep neural networks (Trunng 2022b Golowich et al. 2018), , and includes MLP bounds when MLP layers are used (Golowich al. 2020 Truong 2022b b
However, SSM layer norms can mitigate this effect: SSMs are contractions, they counteract the higher Rademacher complexity of nonlinear layers. SSM norms depend on stability more stable SSMs typically have smaller norms if C' and B remain unchanged, suggesting that stability may offset depth effects in both SSM and MIP layers. Morcover, using GLU instead of MLP layers may reduce generalization gaps, as deep SSMs with GLU layers have c= 0.
As discussed in Section 4.3 for Theorem 5.5 we only require that the state matrices are Schur, which does not imply weights of the SSM layers are bounded. This intuitively suggests that regularization techniques directly penalizing the norm of the weights of the SSM layers exclude of potentially well-generalizing solutions for which the norm of the weights are further from the origin, while the system norm stays low.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Remark 5.6 (Proof techniques from prior work on simple RNNs single layer SSMs.). Prior work establishing PAC bounds on sequential models employ proof techniques that are not applicable to deep SSMs considered in the paper at hand. Comparing our proof to every relevant paper is not feasible, hence we only discuss the most common techniques.
First of all, we are not aware of any prior paper generalization bounds that hold for deep SSMs. It is not clear how formulate deep SSMs as simple RNNSs or Transformers, therefore proof techniques that hold for those models do not automatically hold for deep SSMs.
Many proofs on simple RNNs, Transformers or single layer SSMs (single LTT systems) bound the Rademacher complexity by first bounding covering numbers which serve as natural upper bounds on the Rademacher complexity. However, it is not clear how to bound covering numbers of deep SSMs, even if the covering numbers of the individual layers are known, as the behavior of covering numbers under model composition is not straightforward. One option for dealing with this problem is use the contraction lemma for covering numbers SShllv-Shwarkk & Ben-David] 2014), or alternatively to apply Talagrand's contraction lemma Ledoux & Talagrand| [991] and express the Rademacher complexity of the composition via that of the first layer, followed by covering number arguments. This technique cannot be applied directly to SSM blocks due to the nonlincarity being parametrized. Even if this was possible, the Lipschitz constant of such parametrized nonlinearity is often hard to estimate.
The required assumptions for PAC bounds on the generalization error of simple RNNss, single layer SSMs or Transformers usually employ an explicit upper bound on the parameter norm of the considered model. This is often the case when proofs based on covering numbers are used. This is stronger assumption than what require it is possible to define SSM layers with arbitrarily large parameter norm, but which are stable with uniformly bounded H2 & system norms.
Finally, majority of the generalization bounds for similar model structures often depend (exponentially) on the sequence length T and only hold for a single time-mixing layer.
Remark 5.7 (The role of Rademacher Contractions in the proof of Theorem 5.5 The use of RC allows to overcome all the obstacles from Remark 5.6 Namcly, by Lemma 5.2
5.4 it is possible to upper bound the Rademacher complexity of an arbitrarily deep model whose components satisfy the (H, c)-RC inequality. As (n. c)-RC is defined for mappings between arbitrary Banach-spaces, therefore it is a generalization of Talagrand's lemma and can be applied to time-mixing model components which act on Banach-spaces of sequences and which contain components with parametrized nonlinearities without explicit Lipschitz constraints. Additionally, (1, e)CC allows to establish time-independent bound for deep SSMs with stable LTT layers due to the μ and e terms of such model components not depending on T.
We remark that the 4th point in Assumption 4.10 requiring a bound on the l² norms of imput sequences is also necessary (but not sufficient) for deriving a time-independent bound. Without this assumption the bound would depend lincarly on T, if the stability assumption still holds. If we drop the stability assumption, then our proof technique may still be used, but will result in a bound with a possibly exponential dependence on T.
6 Numerical example
In order to illustrate our results, we trained model consisting of single SSM layer on a binary classification problem of separating the elements of two intertwined spirals, with training set containing N sequences of length T, for various values of N. Let {0iJigesT be slandard normal sample sorted in ascending order and = 7 /0. Consider the following two classes of time series, labeled by 0 and 1.
x, [t] = ((2pt + x) cos((2)) (24r + σ) sin((p:)) + x1 [t] = (-(24t + T) cos(())), - (24p + क) sin +
where 1 1<t5 $ for some T and æ are i.i.d standard normal noise vectors. The training data depicted on Figure 1
15

---

Published in Transactions on Machine Learning Research (10/2025)
1000
1000
label o
label
0.75
800
800
0.50
600
Time (Red)
600
Time (Blue)
0.00
-400
400
-0.25
-0.50
200
200
-0.75
-1.00
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
Figure 1: Dataset containing two classes of spiral curves. This dataset used in our experiment to illustrate our result
We trained linear SSM on this binary classification problem with a training set size of N, for various values of N. The resulting parameter vector therefore depends on N. We applied the Adam optimizer to the binary cross-entropy loss combined with applying a sigmoid activation to the scores outputted by the model. Theorem 5.5 states that with high probability, we can upper bound the true loss with the sum of the empirical loss and a bounding term.
Namely, let fM be the model obtained by preforming the training on an N-sized training set. Then by Theorem 5.5 with probability at least 8 over the choice of we have that for all N E N
C(SN) < Lemp ) KF + Ki 2 log(
(15)
VN
=ir(N,5)
Consequently, we can plot the left and right hand side of inequality 15 for many values of N and expect
the curve + 6(N,6) = C&mp (fN)(( K H) to roughly shaped as C(f*) + v for a constant e>> and for large enough N. Moreover, the curve N ++ L(JN) should be under the curve of + r(N, Moreover, we expect that for some values of N1 and N2, L(FN)) 6N holds, at least for some model classes and some datasets. Otherwise, the bound would be vacuous and thus not very useful. An example of vacuous bound would be one where r(N,6 8) 2 and the loss function is between [0, 1]. In this case the bound would say that the true loss is smaller than 1, which, while true, is not very useful. We show that for the example at hand, there exist N1, N₂ E N such that L((N)) > r(N2, d), and hence the bound is non-vacuous.
VN
In this case, the true loss is imated by taking the loss of the model on a very large set of samples (concretely, 150 000). It can be seen on Figure that the bound holds and in this scenario non-vacuous, i.c. there exists value of the true loss highlighted by the red broken line which is greater, than the value of the estimation at different value of N.
Morcover, it can also be seen on Figure 3 that during the lcarning process, the numerical value of the bounding term, and therefore the estimation ion of the True loss, correlates with the true performance of the model. Once the learning algorithm passed its optimum where the accuracy is close to 1, and starts to exhibit overfitting, the bounding term and the estimation start rapidly grow, while the value the loss stays consistently low. This suggests that adding the bounding term to the loss function a regularization term during training could be beneficial. We consider this as research topic its and out of the scope of this paper.
16

---

Published in Transactions on Machine Learning Research (10/2025)
True loss
Upper bound the
1.5
1.3
1.2
1.0
2500
10000
12500
17500
20000
N
Figure 2: Upper bound on the true loss by taking the empirical loss and the bounding term from Theorem 5.5 for various values of N. This is standard figure in PAC literature and illustrate the behavior of the generalizatio
bound in Theorem 5.5 The orange curve is the proposed upper bound r(N, 8) L (emp(J K=+ Kitt/i//loll
VN and the blue curve is the true loss C(f*) of the learned model yoV The model f was learned from training dataset with N data points. The true loss [(f approximated by the empirical loss on validation dataset with 150 000 data points. The fact that the orange curve above the blue one illustrates that the statement of Theorem 5.5 indeed holds, i.c., L(PN) s r(N, 8). The orange curve converges to the blue at rale O ( ), i.e., for constant and for large enough N, the bound r(N,6) is roughly L( + VN The fact that the orange line (r(N, o)) descends below the red dashed line (the maximal value maxN L( of the true loss) indicates that the bound r(N1, 6) for some N1 (N₃ is around 15 000) is strictly smaller than the true loss at 22) for some N2 (N2 is around 1250), ie., C(N)) r(N1, meaning the bound is non-vusuous in this scenario.
7 Conclusions
We derive generalization bounds for deep SSMs by decomposing the architecture into components satisfying the definition of Rademacher Contraction. Under reasonable stability conditions, the bound is sequence- independent and improves on prior results for linear RNNs as those bounds depend on the aequence-lenglee exponentially. Given that stability central to state-of-the-art SSMs (e.g., S4, S5, LRU), our work offers insight into their strong long-range performance.
We introduce the concept of Rademacher Contraction which we believe is powerful tool for determining the complexity of wide variety of stacked architectures including feedforward and recurrent elements.
Our contraction-based approach, while reasonable, may yield conservative bounds for complex SSMs or deep stacks. However, with state-of-the-ee SSMs using fewer than ten blocks, this is a minor concern. A key limitation is that all elements must be Rademacher Contractions, which may be too restrictive for complex functions.
Future work includes extending these results to learning from limited (possibly single) time-series and deriving tighter bounds, potentially using concentration inequalities for mixing processes and the PAC-Bayesian framework. Incorporating Mamba-like architectures into our framework can also be subject of future research.
17

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
1.8
True loss
Accuracy
Upper bound on the true loss
0.9
0.8
Accuracy
Lo85
1.2
0.7
1.0
0.8
0.6
25 50 75
100
125
150
175
200
Epoch
Figure 3: Behavior of the bound on the true loss during learning. The proposed PAC bound r(N, = Ce Cemp ) / (orange line) is always greater than the actual true loss L(f*) (blue line) during learning, simple consequence of Theorem 5.5 Moreover, the behavior of the bound strongly correlates with the model's true performance in accuracy (green dashed line), where by accuracy we mean the complement of the true loss ((n.))-((oo-1(0 (fN(N) (u), y)] for the 0 - binary loss function
VN
E(u.))- (u),v) y)]
4 y' y y=
lo (0-1(1.0)
This true loss approximated by the corresponding empirical loss
validation dataset with 150 000 data points. Recall that our model is a classifier and we used the cross-entropy loss function instead of the 0 1 binary loss for defining true and empirical losses for training and applying Theorem 5.5 The bound r(N,5) 5) stays low up the point where the accuracy starts decrease, where the bound starts to grow rapidly.
Acknowledgements
This research supported in part by the European Union project RRF-223311211202222000 within the Artificial Intelligence National Laboratory (MILAB); in part by the C.N.R.S. E.A.I. Project "Stabilité des algorithmes d a'apprentisagee pour les réscaux de neurones profonds et récurrents en utilisant géométric et la théorie du contrôle via la compréhension du rôle surparamétrisation (StrraeeerrsiiioosSSsaaaaaaaaaaa (StabLearnDynI") and part by the F.D.F. project FaRADAT under Grant 101103386.
References
Baptiste Abeles, Eugenio Clerico, and Gergely Neu. Generalization bounds for mixing processes via delayed online-to-pat conversions, 2024. URL http:://arrxv..rg//bb/////////
Nil-Jana Akpinar, Bernhard Kratzwald, and Stefan Feucrriegel. Sample complexity bounds for rmns with application Lo combinatorial graph problems (student abstract). Proceedings of the AAAI Conference
on Artificial Intelligence, 34(10):13745-1337 4 2020. doi: 10. v3ii.v34411..7...
URL https:
7/ojs aaai .rrg//or///o.. hete/index....
P. Alquier, X Li, and O. Wintenberger. Prediction of time series by statistical learning: general losses and fast rates. Dependence Modeling, 1(2013):65-9)) 93, 2013.
Pierre Alquier and Olivier Wintenberger. Model selection for weakly dependent time series forecasting. Bernoulli, 18(3):883 913, 2012.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Ido Amos, Jonathan Berant, and Ankit Gupta. Never train from scratch: Fair comparison of long-sequence models requires data-driven priors, 2024. URL https::/arxiv. w.tp://...r..aaa/0......2...
Athanasios Antoulas. Approrimation of large-scale dynamiool systems. SIAM, 2005.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. -peetrally-normmalzeed margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 0220--249, 2017.
S.P. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan. Lineor Matriz Inequalities in System and Control Theory. SIAM, 1994.
VS Chellaboina, WM Haddad, DS Bernstein, and DA Wilson. Induced convolution operator norms for discrcte-time linear systems. In Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No. 99CH36304), volume 1, pp. 487-492. IEFF, 1999.
Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of family of recurrent neural networks. In Proceedings of AISTATS 2020, volume 108 of PMLR, pp. 1233-1243, 8 2020.
Kyunghyun Cho. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint Xrxi::1409. 1259, 2014.
Nicola Muca Cirone, Antonio Orvicto, Benjamin Walker, Cristopher Salvi, and Terry Lyons Theoretical foundations of deep selective state-space models, 2024. URL https://arxiv.org/ wttp:a/wwww...raaa.//......... 2402../240..11 19047
Tri Dao and Albert Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. In International Conference on Machine Learning, pp- 10041-10071. PMTR, 2024.
Yann N Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. In International conference on machine learning, pp. 933 941. PMLR, 2017.
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, pp. 5793 5831. PMLR, 2022.
D. Eringis, J. Leth, Z.H. Tan, R. Wisniewski, and M. Petreczky. PAC-Bayesian bounds for learning LTI-ss systems with input from empirical loss. arXio preprint arx::22303. 16816, 2023.
Deividas Eringis, john leth, Zheng-Hua Tan, Rafal Wisniewski, and Mihaly Petreczky. PAC-bayesian bound, via rényi divergence, for a class of linear time-invariant state-space models. In Forty-first International Conference on Machine Learning, 2024. URL httts:
Adeline Fermanian, Pierre Marion, Jean- Phillppe Vert, and Gérard Biau. Framing rmn as a kernel method: A neural ode approach. Advances in Neural Information Processing Systems, 84:3121-3134 2021.
Dylan Foster and Max Sinchowitz. Logarithmic regret for adversarial online control. In Proceedings of the 37th ICML, volume 119 of PMLR, pp.
PMLR, 7 2020.
Daniel Y Fu, Tri Dao, Khaled K Saab, Armin W Thomas, Atri Rudra, and Christopher Ré. Hungry hungry hippos: Towards language modeling with state space models. arXiv preprint arXiw:2212.14052, 2022.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297 299. PMLR, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, 9(2):473 504, 2020.
Albert Gu and Tri Dao. Mamba: Linear-Lime sequence modeling with selective state spaces, 2023.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. Xix preprint ar Xiv:2111 1.00396, 2021a.
19

---

Published in Transactions on Machine Learning Research (10/2025)
Albert Gu, Isys Johnson, Karan Goel, Khaled Kamal Saab, Tri Dao, Atri Rudra, and Christopher Re. Combining recurrent, convolutional, and continuous-time models with linear state space layers. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021b. URL htttps://operreviee..
Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the paramcterization and initialization of diagonal state space models. Advances in Neural Information Processing Systems, 35:35971 -3588,, 2022.
Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Re. How to train your HIPPO: State space models with generalized orthogonal basis projections. In International Conference on Learning Representations, 2023. URL https::/openrevverr wttp://www...e..oooooo/////11100
Maxime Haddouche and Benjamin Guedj. Online pac-bayes learning. Advances in Neural Information Processing Systems, 1125725--5733 2022a.
Maxime Haddouche and Benjamin Guedj. Pac-bayes with unbounded losses through supermartingales. arXiv preprint Xiv:2220 0.00928, 2022b.
Bruce Hajek and Maxim Raginsky, Ece 543: Statistical learning theory, University of Illinois lecture notes, 2019.
Joshua Hanson and Maxim Raginsky. Rademacher complexity of neural odes via chen-fliess scries. arXiv preprinl ar Xiv:24401. 16655, 2024.
Joshua Hanson, Maxim Raginsky, and Eduardo Sontag. Learning recurrent neural net models of nonlinear systems. In Learning for Dynamics and Control, pp. 425 435-435. PMI.R, 2021a.
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, pp. 425-435. PMLR, 2021b.
Manuel Haussmann, Sebastian Gerwinn, Andreas Look, Barbara Rakitsch, and Melih Kandemir. Learning partially known stochastic dynamics with empirical pac bayes. arXic:2006. 09914, 2021.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint wrXiv:6006.08155 2016.
Hochreiter. Long short-term memory. Neural Computation MIT-Press, 1997.
Yumpeng Huang, Jingwei Xu, Junyu Lai, Zixu Jiang, Taolue Chen, Zenan Li, Yuan Yao, Xiaoxing Ma, Lijuan Yang, Hao Chen, Shupeng Li, and Penghao Zhao. Advancing transformer architecture in long-context large language models: A comprehensive survey, 2024. URL
12351
Boris Joukovsky, Tammoy Mukherjee, Huynh Van Luong, and Nikos Deligiannis. Generalization error bounds for deep unfolding rnns. In Proceedings of the Thirty--eventth Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of PMLR, pp. 1515-1524. PMLR, 7 2021.
Pascal Koiran and Eduardo D. Sontag. Vapmik-chervonenkis dimension of recurrent neural networks. Discrete Applied Malhemalics, 86(1):63 79, 1998.
Vitaly Kuznetsov and Mchryar Mohri. Generalization bounds for non-stationary mixing processes. Machine Learning, 106(1):93-11) 117, 2017.
Sahin Lale, Kamyar Avizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33: 2020.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: Isoperimetry and Processes, volume 23. Springer Science & Business Media, 1991.
20

---

Published in Transactions on Machine Learning Research (10/2025)
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. In The 22nd international conference artificial intelligence and statistics, pp. 888 896. PMLR, 2019.
Fusheng Liu and Qianxiao Li. From generalization analysis to optimization designs for state space models. In Forty-first International Conference on Machine Learning, 2024. URL http:://ppearrvveer..eeffooo
id=K]M2XXe0SS
Pierre Marion. Generalization bounds for neural ordinary differential equations and deep residual networks. arXiv preprint erXix:2355.060 06048, 2023.
Stefano Massaroli, Michael Poli, Daniel Y Fu, Hermann Kumbong, Rom Nishijima Parnichkun, David W. Romero, Aman Timalsina, Quinn Mclntyre, Beidi Chen, Atri Rudra, Ce Zhang, Christopher Re, Stefano Ermon, and Yoshua Bengio. Laughing hyema distillery: Extracting compact recurrences from convolutions. Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL httts::/ See/foorum2id-DWELccee.
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, pp- 3 17. Springer, 2016.
Daniel J. McDonald and Cosma. Rohilla Shalizi. Rademacher complexity of stationary sequences, 2017. arXiv preprint srXiv:1106.0733:
Volodimir Mitarchuk, Clara Lacroce, Rémi Eyraud, Rémi Emonet, Amaury Habrard, and Guillaume Rabusseau. Length independent. pac-bayes bounds for simple rnns. In International Conference on Artificial Intelligence and Statistics, pp. 3547 3555. PMLR, 2024.
Mchryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-i.i.d processos. In Advances in Neural Information Processing Systems, volume 21, 2008.
Naoki Nishikawa and Taiji Suzuki. State space models are comparable to transformers in estimating functions with dynamic smoothness. In ICML 2024 Workshop Theoretical Foundations of Foundation Models, 2024. URL. httpss:/ httprr//ww...eeooooor/o////.....
Antonio Orvieto, Samuel Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, pp. 26670 26698. PMLR, 2023.
Antonio Orvieto, Soham De, Caglar Gulcehre, Razvan Pascanu, and Samuel L. Smith. Universality of linear recurrences followed by non-linear projections: Finite-width guarantees and benefits of complex eigenvalues. In ICML, 2024. URL
Samet Oymak and Necmiye Ozay. Revisiting ho ho-kalman-based system identification: Robustness and finite-sample analysis. IEEE Transactions on Automatic Control, 67 67(4):1914-1928, 4 2022.
Samet Oymak, Zalan Fabian, Mingehen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural 05392, 2019.
networks via harnessing the low-rank structure of the jacobian. arXio preprint
Rom N. Parnichkun, Stefano Massaroli, Alessandro Moro, Jimmy T. H. Smith, Ramin Hasani, Mathias Lechner, Qi An, Christopher Ré, Hajime Asama, Stefano Ermon, Taiji Suzuki, Atsushi Yamashita, and Michael Poli. State-free inference of state-space models: The transfer function approach, 2024. URL
ottps://arxiyy orggabs/ 2405..2205..0 06147
Xianbiao Qi, Jianan Wang, Yihao Chen, Yukai Shi, and Lei Zhang. Lipsformer: Introducing lipschitz
continuity to vision transformers. arXiv preprint 2xXi:2304.009866 2023.
Yevgeny Seldin, François Laviolette, Nicolo DisncBiacchi, John Shawe- Shawe-Taylor, and Peter Auer. Pac-bayesian inequalities for martingales. IEFE.. Transactions Information Theory, 58(12):7086-70 -0936, 2012.
21

---

Published in Transactions on Machine Learning Research (10/2025)
V. Shalaeva, A. F. Esfahani, P. Germain, and M. Petreczky. Improved PAC-bayesian bounds for linear regression. Proceedings of the AT Conference,
4 2020.
Shai Shalev-Shwartz and Shai Ben-David. Underslanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Max Simchowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi paramearaettric least squares. In Conference on Learning Theory, pp. 2714-2802. PMLR, 2019.
Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. Simplified state space layers for sequence modeling. Xiv preprint arXiv:2208.044 049333 2022.
Jakub Smékal, Jimmy T. H. Smith, Michael Kleinman, Dan Biderman, and Scott W. Linderman. Towards a theory of learning dynamics deep stale space models, 2024. URL htttps://arxiv.orgg wtt./oo////////////// 07777
Eduardo D Sontag. A learning result for continuous-time recurrent neural networks. Systems & control letters, 34(3):151-155 1998.
Yue Sun, Samet Oymak, and Maryam Fazel. Finite sample system identificatin: Optimal rates and the role of regularization. In Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120, pp. 16 25. PMLR, 2020.
Matteo Tiezzi, Michele Casoni, Alessandro Betti, Tommaso Guidi, Marco Gori, and Stefano Melacci. On the resurgence of recurrent models for long sequences survey and research opportunities the transformer era, 2024. URL atttps:/arxxv..rg. wwwp:////////.....ooo/// 08132
Roland Tóth. Modeling and identification of lénear parameter-varying systems, volume 403. Springer, 2010.
Jacob Trauger and Ambuj Tewari. Sequence length independent norm- norm-based generalization bounds for transformers. In International Conference on Artificial Intelligence and Statistics, pp. 1405-1413. PMIR, 2024.
Lan V Truong. Generalization error bounds on deep learning with markov datasets. Advances in Neural Information Processing Systems, 35:23452 23462, 2022a.
Lan V Truong. On rademacher complexity-based generalization bounds for deep learning. arXiv preprint arXiv:2208.04280 2022b.
Anastasios Tsiamis and George J. Pappas. Finite sample analysis of stochastic system identification. In 2019 TEFE 58th Conference Decision and Control (CDC), pp. 3648 3654,, 2019.
Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi. Learning from many trajectories. Journal of Machine Learning Research, 25(216):1 109, 2024. URL http://jmlr http://rrrr.ppppre/////////-/11 html
Zhuozhuo Tu, Fengxiang He, and Dacheng Tao. Understanding generalization in recurrent neural networks In International Conference on Learning Representations, 2020.
Shida Wang and Qianxiao Li. Stablessm: Alleviating the curse of memory in state-space models through stable reparameterization. In Forty-first International Conference on Machine Learning, 2024.
Xiao Wang, Shiao Wang, Yuhe Ding, Yuehang Li, Wentao Wu, Yao Rong, Weizhe Kong, Ju Huang, Shihao Li, Haoxiang Yang, et al. State space model for new-generation network alternative to transformers: A survey. arXie preprint orXiv:2404.09516, 2024.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Annan Yu, Dongwei Lyu, Soon Hoe Lim, Michael W. Mahoney, and N. Benjamin Erichson. Tuning frequency bias of state space models, 2024. URL htttss:/aaran http::///arrd..orrraa///111 02005
22

---

Published in Transactions on Machine Learning Research (10/2025)
Jiong Zhang, Qi Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient SVD parameterization. In 35th ICML, volume 80 of PMIRR, pp. 5806-588 5814. PMLR, 2018.
Yang Zheng and Na Li. Non-asymptotic identification of linear dynamical systems using multiple trajectories. http///.rrg....000.............
IEFE Control Systems Letters, 5(5):1693-1188) 16988, 2020. doi:
Ingvar Ziemann and Stephen Tu. Learning with little mixing. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 0636-4637. Curran Associates, Inc., 2022.
Ingvar Ziemann, Stephen Tu, George J. Pappas, and Nikolai Matni. Sharp rates in dependent learning theory: Avoiding sample size deflation for the square loss. In Forty-first International Conference on Machine Learning, 2024. URL https://openrevier: wtw.:e/iiiiiieeeeouunuuuaaaaaaaa wwweet/forunidddd-teeee
Ingvar M Ziemann, Henrik Sandberg, and Nikolai Matni. Single trajectory nonparametric learning of nonlinear dynamics. In Po- Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 3333 3364. PMLR, Jul 2022. URL https://proceedings mlr. www.t/press////////ee zi
//ess//218/ziemmnn22a... emann22a. html
23

---

Published in Transactions on Machine Learning Research (10/2025)
A Lipschitzness of the cross-entropy loss
For simplicity, we consider the binary cross-entropy loss for the scalar output case as an elementwise loss function, defined as
((z,y) --y (1 y) log(1 2)).
(16)
The function defined in equation 16 without any other assumptions is not Lipschitz in the sense of Assumption 4.10 on the [0, 1] interval. However, if we bound the argument of the cross-entropy away from 0, i.e. it is
defined on [a, 1] for some positive it is Lipschitz in the sense of Assumption 4.10 with a Lipschitz constant
proportional to a1.
A more practical assumption is that the cross-entropy is combined with the softmax function. For the scalar output case, we have
-oylo(ssimooid (1 y) log(1 (1 sigmoid(z))
(17)
for y [0, 1]. If x belongs to the interval
[-a, a], i.e., the model outputs are bounded, have
de and
de ay
S
0z
hence the function defined in equation 17 is 2-Lipschilz in æ and a-Lipschitz in and it is max Lipsschiit as long E [0, 1]. We can extend to all by setting {(x, y) = E(x, 0) for y < 0 and {(x, y) = E(z, 1) for > 1, without changing the Lipschitz constant.
This argument holds for the case when the model outputs a vector and we apply softmax, in a forward manner. We omit the vector output case from the paper, because it makes the proof more technical and less readable, while all the key terms remain the same. For the vector output case, in the first half of the proof of Theorem 5.5 in Appendix B instead of applying the Contraction Lemına for the Rademacher complexily, we need to apply Maurer 2016 Corollary 4).
forward
For cross-cntropy with softmax, we can also consider the labels built into the loss function and investigate the Lipschitzness in the input variable only, ie. instead of f(x, y) we have {(x). This definition differs from what we have in the main text, however, our proof and the above argument works, while the Lipschitz constant is most without depending on a in this case.
B Proofs
In this section we need to prove (1, c)-C property for linear (or affine) transformations which are constant in time, in many cases. For better readability, we only do the calculations once and use it as a lemma.
Lemma B.1. Let X2 be two Banoch spaces with norms || 1xx and || 1xx,, and for every bounded linear operation W Xi + X2 and any b X fw. ((u) b E X2. Let denote by [| op the induced norm of bounded linear operator W X1 X2, i.e., || == supzex, T> W E W such that sup ||W llap < Kw and b E B such that sup |blx,, < Kb. Then the set of transformations WEW
[W(x)laa, Let us assume that
bEB
== (fwb WeW.be B) is (Kw, Kb)-RC, and the image of the ball Bx, (r) under f E F contained in Bx, (Kwr + KD).
Remark B.2. We are mainly interested in the cases when X; = Eg ","",, and X; = 4R*²), (q,1) e ((2,2), (2, oo), (co, oo)]. For the special case of affine transformations that are constant in time, i.e. f(u) Wu[k] + b for weight matrix W E Xn, and bias term b n. for all & E [T], the operator norm equals the corresponding matrix norm, ie ||W || In this case, b is the sequence for which blk] = b for all & E [7], thus (elle((Rm)) = ||b]lsc
24

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. First, let prove simple fact about Rademacher random variables that we will need, namely if a (N))...,ON) and are i.i.d. Rademacher variables, then
E
S N.
(18)
This is true, because
E
0
oi
E
N E. [o?] +
Eø
Σ of
2
Σ 1
0
Σ
Σ Es [o,o,] vN, 1-1=1
where the first. inequality follows from Jensen's 's inequality and the last equality follows from the linearity of the expectation, and the facts that d; are Rademacher variables and form and i.id sample.
For Z E X1 have
Eg
sup (W.))WwXB (u, EZ
sup
o (W,) +b)
X2
1
< Feg
sup
sup
o.
W(u))
+ E
sup beB
o
WEW (m.) E EZ
N
N
X2
1
Eg
sup
sup
W
o;4;
E
sup beB
WEW (u. EN
N
N
No
NN
1 Σ
Eg
sup WEW
sup ||
+ E
Σ
o
sup
b
Xx
N
N
bes
i=1
1 N
1
||Wllop E. WeW
sup
sup
+ sup bEB
|bllg
E
O
IN
E2
N i=1
N
N1
1 NN
sup
||||
E.
sup |bll
WeW
(u.
EZ
N
1=1
BEB
where the first incquality follows from the triangle incquality, the first equality is the lincarity of W, the second inequality follows from the definition of the operator norm, while the third and fourth inequalities refer only to the bias term and follow from the absolute homogeneity of the norm and inequality I8
We can see that the calculations hold if the transformations are restricted to the ball Bx, (r) for any choice of Xi we consider. The radius can grow as
(u) + bllxs < (w)ll),,, + + < [[ ||llxx + |bllas
Remark B.2 is straightforward from the definitions of the considered norms.
Proof of Lemma 5.2 Let the Banach spaces which contain X; be denoted by X, for 1,2,3. Let Z X and 7 ((pi(u,))
10 21). We have
N
Eg sup
sup
sup
P2 4i Eoh
(u IN EZ
N
15
25

---

Published in Transactions on Machine Learning Research (10/2025)
sup ErT
sup
1
Σ oipa (vi)
N
42E4a (v. (v.), E2
1g
N pup)
S pgllE
sup
sup
+
C2
pleti {u, ) 12
N
VN
N
C2
S 122/11 Bag
sup
+ 122
[n.)
N f=1
V N
VN
N2
Proof of Lemma 5.4 Encoder and decoder. The encoder is case a), while the decoder is case b) in Lemma B.1 along with Remark B.2
SSM. As discussed in Section 4.2 an SSM is equivalent to a linear transformation called its input-output map. Therefore, by Lemma B.1 the SSM is (j, 0)-RC in both cases, where j is the operator norm of the input-output map. Combining this with Lemma 4.3 yields the result.
Remark B.3. 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 = co, the input-output map still exists and is a linear operator. The proof of Lemma B.I holds in this case as well for operator norms.
Pooling. For any C E (R we have
E
sup
of Pool (i)
N
(2. N
EZ
T Σ
E
sup
sup
N
Σ
T
(
[A:]
[ E2 13isn=
f=1
k=1
Eg
sup (x EZ 13ism=
sup
1
Σ
o,
(3) [8:]
T
N
T
N
< E.
sup
1
sup
[K]]]
NN
EZ
T
k=1
ISjSnn
N
i=1
1
E.
sup
oz [k:]
(M.)) EZ
T
N
k=
< E
sup
di
(2.)
N
(R
MLP. For both type of activation functions will prove the result by first proving it for single layer networks. To this end, let p be an activation function, which is either ReLU or sigmoid with the properties stated in Assumption 4.10
Consider constants Kw,Kb > O and integers m, n, > O. We first consider the family FMLP, Ko.pmm.n of sin- gle hidden layer neural networks f Ex (R:m) + E (v) definod by f(u)[k] = p(g(u(k))) where g(x) = Wx+b is the preactivation function and g belongs to the set 9Kw Kn.mm.. {g x Wx+ Wee.b//WWWb.... W. where W (W E xm || Kw} and B (b E Rn |b]l K.).
26

---

Published in Transactions on Machine Learning Research (10/2025)
We will show that FMLP. K...PK..K....... n. is (Kw, Kb + +.5) if p is sigmoid, and it is (4Kw, 4Kb) if is ReL.U. Moreover, the elements of FMLP, K...K. map balls radius to balls of radius f(r), where f(r) = Kw + Kb if p is sigmoid, and f(r) = Kwr + Kb if p is ReLU.
From this the statement of the lemma can be derived as follows. Let Kn. be the set of all models [*] = (((k:) such that g E GKw,cKK,..man Notice that Fi contained in the composition (as defined in Lemma 5.2 Ko....K...aaa
Rg. E (2,3 ................................ M From the discussion above, FKw..Kn.., FKw.: Kb.i.n...a. for suitable integers is (Kw,a, Kb + 0.5)-RC (sigmoid) (4Kw, 4Kb)-RC (ReLU) and its elements map balls of radius to balls of radius 1 (sigmoid) or Kwr Kb (ReLU). From Lemma B.1 and Remark B.2 it follows that that WK,,, Kn. is (Kw,,, Kb,i)-C and its element map ball of radius r to balls of radius Kw,r + Kb The statement of the lemma follows now by repeated application of Lemma 5.2
It left prove the claims for single layer MLPs with sigmoid and ReLU activation functions respectively.
Single layer MLP with sigmoid activations. Let p be a sigmoid such that it is 1-Lipschitz, p(ar) [-1, 1], p(0) 0.5, p(z)- - p(0) is odd. Let G = GKw Ku.m.. {g x Wx b W e W, E B}. Recall that for an input sequence E e (I and function g E G, g(2) E e (R**) means that we apply for cach timestep independently, i.e. g [kz)[k] = g(z(k]). We have
Eg
sup
sup
Σ asp(g(z)))
g0G |= EZ
(R
N
Eg
sup
sup (Z)
sup
(W.b)EWxB
N
Lot x; =, = I.....N N and let H = f.w.b.g. (W, b, 2, k) E XWXBx (ZU U {0}) x [T]} such that A...,g,A(x;)) = ( Under our assumptions H is symmetric to the origin, meaning that h E H implies -h E H. Indeed, notice that if (W,b) E W B then (-W, b) W x B, and hence hw -ww.b... also belongs to H. We apply Theorem 2 from Truong 2022b) for the sigmoid activation p and by using that p(x) p(0) is odd, we derive the following.
N d 22 - -b)
Eg
sup (W:))
sup
sup ISAST
(
N
N
Eg
sup
a:p(h(x;))
N
hEW
N
< Eg
sup NEW
(x)
N
2/N
1
1
Ear
sup
sup { EZ I<KST
sup
o. (Wz [k] +b)
N
2/N
(W.b)EWXB
1
1
E.g
sup (x:) M EZ (W.))ExXB
sup
(W2, + +b)
N
2/N
(R
because the sigmoid is 1-Lipschitz and p(0) 0.5. Now can apply Lemma B.1 that
(see Remark B.2 to get
I N N
E
sup (W.b)EWxB
sup
a
+ b)
(z. N EZ
2VN
1=1
120 (R
27

---

Published in Transactions on Machine Learning Research (10/2025)
s sup |[W|
100,00 Bir
sup (2,),1,ZZ
oi
sup N bEB
|b
wew
N
2v
(R
Therefore, the sigmoid MLP layer is (Kw; Kb + 0.5)-RC. The restriction of an MLP to the ball (Bm) maps to the ball Beg (I), because of the clementwise sigmoid activation.
Single layer MLP with ReLU activations. We repeat the same steps as in the proof up to the first inequality. Here we can apply Equation 4.20 from Ledoux & Talagrand proof of Lemma 2 in Golowich et al. (018)) to get
[991] (this is the same idea in the
N
1
N Σ ,xx
E
sup
Σ (x((((x)))
S 4E
sup WET
hEH
N
N
where we used that p(x) (x) is 1-Lipschitz and p(0) 0, and the same logic for the alternative definition of the Rademacher complexity (without the absolute value) as in the proof of Proposition 6.2 Hajek & Raginsky (2019). 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 Beg (R= maps to the ball (RFV) (Kwr + Kb), because the clementwisc ReLU does not increase the infinity norm, hence we can apply Lemma B.1 and Remark B.2
Again, for the deep model the result. is straight forward from Lemma 5.2 along with Lemma B.1 Remark B.2
GLU. For the ease of notation, assume that Kawv = KELU and let W { g"y ||| < KoLu and let FaLu = {fow as in equation f lemma for FGLU.
WE E W}. As F; Fanu, it is enough to prove the claim of the
First of all, we show that the function h (I22, 11-112) - (R. |-. defined as h(x) = x1 (xx)) is /2(K 1)- Lipschitz on bounded domain, where |ay]| S K all x R2a we consider. We will later specily the value of K in relation to Assumption 4.10 By the sigmoid being 1-Lipschitz, we have
[x(x) - h(y) = (22) (x2) + y1o((2) g1o z ((n - (1)0 + 1y1 (a(x2) - (12)) S |an yn 22l y/2
S V22(K + || 1xx-yl, yll2
Second, we recall Corollary 4 in Maurer (2016).
Theorem B.4 (Maurer (2 Let any set, (X1, (X1...., xx) XN, let F be a set of functions f + (RR)) and led h (R. + an L--Tipschila function. Under Iu denoling the k-th component function of f and ouk being doubly indexed Rademacher variable, we have
N
N sup JEF
Eg sup Σ orh(f(xi)) JEF
I V2LE.
(x,)
We wish to apply Theorem B.4 to GLU layers. For any C (BR"), by letting GLUw(z) Saw (2) we have
E,
sup WEW (2.), EZ EZ
sup
Σ i=1
(LUw(Z
(R
N
E. sup
sup
sup ISRST 1
sup
GLU W (z,)
WEW (z. vy , EZ
15
N
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 B.4 we reduce the problem to the usual Rademacher
28

---

Published in Transactions on Machine Learning Research (10/2025)
complexity. In turn, can apply the last chain of inequalities in the proof of Proposition 6.2 in Hajek & Raginsky (019)) Concretely, by denoting O = (0) and noticing that GTU = O, we have
Bø
sup WEW
sup H
sup EZ SSSTI
sup
GLL (z.)ki
N
2
sup [WEW (z.) (2 ISkST Siinn
sup
sup
sup
Σ
G.LLL (2:)
Let = i, I....,N and let H (fweky | (W,,,,,) W (Z U (0)) x [T] [nw]] such that fwig.a(X,)) = (G)) (2GEEU(Z((A)))
for == [2,} E Z. Since Z S (Beg (x*> (x))
it follows that for all {2 Z and for all N, the inequality | ~0 S r holds. Hence, it follows that (2:))(()))) < r, leading to (2) < sup | r. In particular, GLU [R:
WeW
h(/Wa,, (x,)) = Ml (x:)), where bBB is the restriction of h to B = E ||x|oo < K}, with K = max sup || o0, In particular, h/s v2(K + 1)-Liscchitz.
Wew
We are ready apply Theorem B.4 together with the GLU definition and its V2(K + 1)-Lipschitzness, we have
2F
sup
sup ( (Z) ISKST
sup
sup
1
GLU (2)
WEW (x.)
N Σ (xxl)()))))
N
2E.
sup
< 4(K + 1)E
sup (2
(2)U())))
N
SEH i=1
N N
+ 4(K + Eg
sup
( EZU(O)
Due to the definition of GELU, its 2-Lipschitzness Qi et al. 2023) and Theorem 4.12 from Talagrand 1991 we have
Ledoux &
1 GELU
A Eg
sup {z. NN (Z EZ
N
Exp (Rmm)
1
1
S 4IE
sup
AEE
sup 12,1, EZ
022
N
N
Egp (RP=))
(R
and
N
B = Eg
sup
sup
o (GELU(()))
WEW (x. ((O)
N
(Rnu)
N
sup WEW
||W|| ESz
sup (N)),EE(((N
GFFLU(
N 1=1
(R
1 N
< sup WeW
|||| F.
sup
7
(x,)
E2
N 2=
(R
29

---

Published in Transactions on Machine Learning Research (10/2025)
Here we used the linearity of W and the exact same calculation as in the proof of Lemma B.1 By combining the inequalities above, it follows that
2 G,LLUW (z.)lk)
E
sup sup WEW
sup sup (a EZ ISKST Ssss
1=1
16(K +1
sup (WeW
| +1) Eo
sup E EZ
oi
1p (R
Substituting the value gives the result.
SSM block. By Lemma 5.2 and the proof of this lemma for SSM layers and non-linear layers Fi, we have that the composition of the SSM layer & and non-linear layer Fi is (rrrk))) it is (2r K2, ci (((K2)))-RC for i= 1 and its elements map ball of radius r to ball of radius (rr)) for i > 1 and to ball of radius ((Krr) for i == A SSM block is then (p (p((K + az c ((( where Kiaz) = K2 K(() = K1, i >>> 1 because
for i>> 1 and
Eg
sup DEE {2, 1 EZ
sup
Σ a (g((5(((2)) + tazz)
N
17p (R=u)
1 N
Eg
sup 9EFF DEE {2, ) E2
sup
+ aBo
sup
o223
N
(Bau)
epp (Row).
N
+ (r(r)
s (mi(r) K(() + Ba
sup
33
N
EZ
N
1=1
(B
Proof of Lemma
5.3
By definition
N
T
N
0
u
k
N
N
(R
i=1
T
N
uu
[k],
Σ
o [+]
k=
i=1
j=1
3:
T
N
N
(u, (M). uy [c)) R.
N
1=1
where (. denotes the standard scalar product in Rio Therefore
N
N J2a (u,(k), 1,), [+]
E
U
Er
N
1=1
G (B"in)
E
Jso (n [k]] u, [k]12))pmm
N2
A=
30

---

Published in Transactions on Machine Learning Research (10/2025)
N
B [ [u, uy gei.
i=1
E,
[o
(u: [k]. u, [k]) pm
N
1=1
N
1
S Kn
uu Juilia (
S N2 NK
N2
N2
From Lemma 5.4 follows that all maps constituting a model f JF come from families of maps which are (H, c)-RC for suitable constants μ, C, and map any ball of radius r a ball of radius P(r). Let consider the deep SSM model given by equation g which is a composite of mappings
Proof of Theorem 5.5
Beg (Ku) Encoder, (eI (KuKEne)
B1 Be (12)
B2
B2
(R=)) Pooling, (I Deender
where the constants ri, i E [L + 1] are as in equation 13 due to repeated application of Lemma 5.4 and the expressions in Table 3
Note that the first SSM block is considered as a map Beg,aR..) (KEn - Beg (Rou (12), while for (fi+1). This is needed, because the encoder is constant in time, therefore the Composition Lemma wouldn't be able carry the & 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 time independent bound.
the SSM layer in the ith SSM block considered as a map Beg (r;) (r;) + BeppRr (Fi+)(1141)......)))))))))))))))
Next, we wish to apply Theorem 4.2 to the set of deep SSM models F. Let us fix a random sample S = -ui..... .,] C (R"H)) As the loss function is Lipschitz according to Assumption 4.10 we have that for any E
((((u), x) s 24 max s 2L, max KyJ.
thus K2 2Tq max Le K,)- Again by the Lipschitzness of the loss and the Contraction Lemma Shalev-Shwarte & Ben- David 2014
Ben-David.
Lemma 26.9) have
Rs(Lo) S Rs(F),
and recall that RF(F) = ((())....... f(u))) (f F}) It is enough to bound the Rademacher com- plexity RF) of F to conclude the proof. By applying Lemina 5.4 to every layer of F and using Lemma 5.2 it follows that the family Flx, of restriction the elements F to X1 = B2g (B (Ku) is a family of maps from X1 to X, [R. 1.1 which is (n, c)RC), where μ, are as in equation 14 Next, we state lemma before we finish the proof.
Lemma B.5. Let F be set of functions between X1 = (R (Ka) (Ka)) and X₂ = (R. 1) that (1,, RC. The Rademacher complerity of F w.r.t. some dataset S for which Assumption 4.10 holds, admits the following inequalily.
Rs(F) S KKn +
VN
Proof.
Σ (a)((u))
Rs(F)= = (((F)-R(((A)
EE, sup feF
N 1=1
31

---

Published in Transactions on Machine Learning Research (10/2025)
E. S
sup fer
Σ (u))
N
S puleerr
1 N
Σ
o
c
VN
(2(mm)
By applying Lemma 5.3 it follows
uuKn +
Rs(F) S
vN
The Theorem is then a direct corollary of Lemma B.5
32


Reviews:
[{"review_id": "hYMjt8Q4H6", "reviewer": "Reviewer_nWKz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides a novel and significant result on the theoretical properties of deep SSMs, specifically their generalization error. The result appears to be technically challenging to obtain. Additionally, the result provides a relationship between stability of the SSM blocks and the overall performance. Finally, the notion of Rademacher contraction that is introduces is interesting and could be of use in other contexts.\n\nOn the downside, I believe the paper would benefit from being clearer in some parts, and aim for a broader audience in others. More specifically:\n- The abstract says deep SSMs are good for long-range sequences, but to do which tasks with those sequences? \n- The abstract says the paper provides a PAC bound, but a PAC bound on which property?\n- The introduction says stability is is key, but none of the contributions highlighted mention it;\n- \"LTIs\" are mentioned throughout without explanation; also MLP and GLU should be clarified, even though those two are more broadly understandable;\n- Almost all references should be cited between brackets, because it becomes hard to distinguish what are citations and what are the words in the sentence;\n- Can we obtain an intuitive explanation of Rademacher complexity along with the formal definition?\n- Some notation is not defined (\"n_u\", \"n_y\", \"B_L\", \"\\sigma_1\", etc.);\n- As far as I understand, it is stated that Schur matrices are equivalent to having the eigenvalues inside the unit disk. I don't see how this is true because for example 2*I (I is the identity) is clearly Schur (since 2*I = I*(2*I)*I^{-1}) and the eigenvalues are clearly not inside the disk;\n- The relation between the experimental results on the plots and the theoretical result is not clear to me. I see there is an effort to make this connection in the text, but I would appreciate if it could be made clearer, both in the text and in the figure captions;\n- What are Markov parameters?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on deep SSMs and provide a PAC bound on their generalization error, i.e., the difference between the true loss and the empirical loss. The result relates stability of the SSM blocks with performance, and does not depend on the length of the input sequences.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I believe the paper should be made clearer, and also targeting a broader audience, following for example my notes above.", "broader_impact_concerns": "I don't foresee relevant ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L7pr2zne7Y", "reviewer": "Reviewer_rrwk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. The paper is well organized and clearly written. The “informal statement of results” section motivates the work and summarizes the contributions, and the assumptions section helpfully frames the (relatively small) limits of theory. Overall I think the structure is great.\n2. The problem is well motivated: SSMs are governed by their impulse responses, whose norms are bounded by something proportional to the system’s norm, so it’s natural that generalization need not depend on sequence length; the paper presents itself as the first to make this precise.\n3. The assumptions strike me as very reasonable, which is refreshing for modern NN theory.\n4. I haven’t checked every detail, but the proofs appear sound.\n\n## Weaknesses\n\n1. I’m not a Rademacher-complexity expert, but compared with prior work the technical development doesn’t feel especially novel and seems to reuse familiar arguments. The proposed “$(\\mu,c)$-Rademacher Contraction” looks close to the standard contraction lemma (The specific case of $c=0$). I’m not convinced the level of technical novelty clears the bar set by the related literature. \n2. The length-independent generalization bounds are not surprising to me (as explained in strength number 2), which is not true in setting investigated in prior works, such as RNNs, whose behavior can intuitively vary more with length). While the problem is well motivated, my intuition is that the result mainly repackages established techniques, though I’m not expert enough to be certain.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper analyzes deep state-space architectures under standard stability assumptions and examines the Rademacher complexity of these networks to derive generalization bounds that do not scale with input length.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since, in my opnion, the paper is well structured and well motivated, I think it would most benefit from clarifying the novelty of its proof techniques: explain why prior methods don’t directly apply here and pinpoint where the proof introduces new ideas. If there is no genuine novelty, state this explicitly (I’m not sure that alone should warrant rejection.)", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "niLGlGiI3G", "reviewer": "Reviewer_NLzu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- First PAC bound for deep SSM.\n- The argument is clear and easy to follow\n\nQuestion\n\n- Could you elaborate on the following? “The bound remains independent of the sequence length, unlike the other sequential model bounds that diverge with T”. Is this a consequence of the bound on the inputs of sequence length T, K_u? \n\nI am not an expert on SSM/PAC bounds so my review is of lower confidence.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper derives an upper bound on the Rademacher complexity of a set of deep SSMs; combined with existing theorems this bound leads to a PAC generalisation bound. The proof relies on a recursive contraction argument that reduces the rademacher complexity of the SSM to the rademacher complexity of the inputs by propagating back through the layers. Empirically, the bound is shown to be non-trivial.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See question above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)