Novelty of Our Bounds

We appreciate the references to generalization bounds for hypotheses trained on non-i.i.d. data and have incorporated them into our revised version to clarify the unique contribution of our work.

Existing results focus on convergence rates for generalization in non-i.i.d. settings but lack explicit constants. Deriving such constants requires computing a Lipschitz (or Sobolev) bound for transformer classes—a technically complex task that forms the core of Theorem 2 in our paper. This theorem, detailed in Appendix Sections 27–31 and 33–44, represents the most technically demanding part of our analysis.

We address the mentioned literature explicitly here, with additional context in the general rebuttal and our response to reviewer 4UED.

Ziemann, Ingvar, and Stephen Tu. "Learning with little mixing."

To apply Theorem 4.1 of [1], one (at least) needs to compute the cardinality ($|T_r|$) of an $r/\sqrt{8}$-net over the hypothesis class in the $L^2$-norm, otherwise, they do not have access to an explicit constant. Since our transformers are smooth, they are contained in some $C^s$ norm-ball $B(s,ρ)$ about some $f\in C(\mathbb{R}^{Md},\mathbb{R}^D)$ with minimal radius

which we denote by $B(f,r)$ and is computed in our Theorem 2 (main technical result). As we see in Theorem 2.7.4 in [4], together with the identity in Equation (15.1.8) of [5], this requires computing the worst-case $C^s$-norm over our entire hypothesis class ($T$) of our class of smooth transformers which is of the form

Thus, their result does not give an explicit constant depending on the transformer class T without the use of our main technical result: Theorem $2$. Moreover, Theorem 1 is not a concentration inequality, and applying a basic result such as Markov's inequality may yield a loose concentration estimate.

Mohri, Mehryar, and Afshin Rostamizadeh. "Stability Bounds for Stationary φ-mixing and β-mixing Processes."

Theorem 11 of [2] does not apply in our setting, due to the assumption that the loss/cost function is uniformly bounded (by $M$), which significantly simplifies matters due to access to tools such as Martingale difference inequalities (e.g. McDiarmid with non-i.i.d. data). We make no such restrictions.

Foster, Dylan, Tuhin Sarkar, and Alexander Rakhlin. "Learning nonlinear dynamical systems from a single trajectory."

Theorem 4 of [3] does not apply to our framework, as we are not assuming that the latent process assumes the form of Equation (1) nor that the latent function being learned is a contraction (Definition 3 in [3]).

Relevance of Our Generalization Bound

Our generalization bound (Theorem 1) is novel due to its foundation in an optimal transport-based concept of exponential ergodicity. This condition is widely applicable, being either easy to verify or already established for many data-generating processes such as classical SDEs, McKean–Vlasov equations, and reflected SDEs. Additional details can be found in Section 2 and the general rebuttal.

Non-Realizability in for Non-I.i.d. Data is Encoded via Stochastic Calculus

By accommodating non-i.i.d. data, if f is twice continuously differentiable and our data is sampled from a strong solution $X_{\cdot}$ to a stochastic differential equation (or any Markovian semi-martingale), Ito's Lemma implies

Thus, the Markov-setting with our assumptions always permits a "signal + noise" decomposition of the input data (as does the classical non-realizable i.i.d. case). In this way, we cover the non-realizable case.

We note that these remarks were given in appendix G. Note also that, for lower regularity functions one can use Tannaka's variant of Ito's lemma and for path-dependant functionals Dupire's functional Ito calculus; in each case, there is a similar "signal + noise decomposition" of $f(X_t)$ which requires non-i.i.d. semi-Martingality of the data.

References

[1] Ziemann, Ingvar, and Stephen Tu. "Learning with little mixing." Advances in Neural Information Processing Systems 35 (2022): 4626-4637.

[2] Mohri, Mehryar, and Afshin Rostamizadeh. "Stability Bounds for Stationary φ-mixing and β-mixing Processes." Journal of Machine Learning Research 11.2 (2010).

[3] Foster, Dylan, Tuhin Sarkar, and Alexander Rakhlin. "Learning nonlinear dynamical systems from a single trajectory." Learning for Dynamics and Control. PMLR, 2020.

[4] Vaart, AW van der, and Jon A. Wellner. "Empirical processes." Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, 2023. 127-384.

[5] Lorentz, George G., Manfred von Golitschek, and Yuly Makovoz. Constructive approximation: advanced problems. Vol. 304. Berlin: Springer, 1996.

Many thanks to the authors for their reply but my assessment remains unchanged.

We are a bit concerned about the validity behind your claim that our work lacks novelty as

• There are no available bounds on the $C^k$ norms of a transformer (or even an MLP) elsewhere in the literature (other than our Theorem 2)

• The perturbation analysis of Neyshabur et al. (2017/2018) considers the Lipschitz regularity of the MLP model as a function of its parameters and uses this to bind the covering number. Their work on pathnorm bounds (2015) for the worst-case Lipschitz constant ($C^1$) is simply that; namely, they do not consider the $C^k$ regularity of either of these classes for $k>1$. Thus, Theorem 2 is completely novel (and highly non-trivial as the proof requires new techniques such as combinatorial bounds on the coefficients resulting from Faa di Bruno, totally in ~30 pages).

Consequentially, your claim that Neyshabur et al. have previously done this is verifiably false.

Our main point/reply is that: bounds on higher-order perturbations $k>1$ are much more involved to derive than Lipschitz-type perturbations ($k=1$) as they require new proof techniques and technical tools. So, in this way, our results are not incremental modifications of Neyshabur's technique, but they require genuinely new technical machinery.

So it's not only about the passage from $k=1$ to $k>1$ but how that can actually be proven; and, later, how that translates into generalization bounds...

To clarify the non-strawman fallacy comment: We are, of course, not relying on the existence of an exact version of our results in the literature, but rather emphasizing that the conclusion and the proof technique are novel.

The Markovianity Assumption

Our analysis naturally extends to cases where the data-generating process becomes Markovian in an extended, but finite, state space by setting $Md$ as the dimension of that extended space. This extension aligns seamlessly with our main technical result, Theorem 2, which allows for arbitrary finite $M$.

We believe this assumption is reasonable for most real-world data sources, ranging from NLP to mathematical finance, as these processes are often Markovian in an extended state space or approximately so. This approximation aligns with the quantitative version of the Echo-State property in reservoir computing (e.g., [1, 2]), as defined in Definitions 4.4 and 4.9 of [3], which is satisfied by many non-Markovian "general" SDEs (see Proposition 4.2 in [3]).

To reflect this, we have updated the draft to include this extension, which required minimal adjustments since the core technical framework was already established in Theorem 2. These revisions, highlighted in the updated manuscript, extend the state space of our process from $d$ to $Md$. However, we initially excluded this scenario because the resulting bounds become significantly more complex when $M$ is infinite—an avenue we aim to explore in future work.

Phase transitions and definition of $C^s$

Thank you for pointing that this needs further explanation, we have clarified the relevant passages in our revised manuscript. Note that the $C^s$-norm, a special case of the Sobolev norm, is often assumed to be known due to its frequent use in analysis. Before we use it (above Definition 2), we point the reader to a detailed definition in the appendix.

Regarding the phase transition, we explained the meaning of $s$ in Section 3.1 (Model Complexity Term). The parameter $s$ represents the order of derivatives within the smoothness class $C^s$. Loosely speaking, our result provides $s \in \mathbb{N}$ distinct bounds, each corresponding to a different level of smoothness. As the sample size increases, the tightest bound is associated as the one with a higher derivative order $s$. When a tighter bound replaces a previous one, we refer to this transition as a "phase transition."

Schwartz functions and Schwartz space

The Schwartz class, denoted as $\mathcal{S}$, consists of functions that are infinitely differentiable and rapidly decreasing along with all their derivatives. This means that both the functions and their derivatives decay faster than any polynomial as the input approaches infinity. Schwartz functions are popular in mathematical analysis, particularly in Fourier analysis, where they ensure smoothness and rapid decay in both the spatial and frequency domains [4, 5]. In our manuscript, they simply serve as an exemplary class of loss functions satisfying Definition 2.

References

[1] Gonon, Lukas, and Juan-Pablo Ortega. "Fading memory echo state networks are universal." Neural Networks 138 (2021): 10-13.

[2] Grigoryeva, Lyudmila, and Juan-Pablo Ortega. "Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systems." Journal of Machine Learning Research 19.24 (2018): 1-40.

[3] Acciaio, Beatrice, Anastasis Kratsios, and Gudmund Pammer. "Designing universal causal deep learning models: The geometric (hyper) transformer." Mathematical Finance 34.2 (2024): 671-735.

[4] Hörmander, L. (1990). The Analysis of Linear Partial Differential Operators I, (Distribution theory and Fourier Analysis) (2nd ed.). Berlin: Springer-Verlag. ISBN 3-540-52343-X.

[5] Trèves, François (1967). Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1

Convergence Rate of the Model Complexity Term

The slow convergence rate $O(\log(N)^r / \sqrt{N})$ for the Model Complexity Term reflects a dependence on higher-order sensitivities, which can be challenging in high-dimensional settings. This trade-off is inherent in controlling the complexity of flexible models like transformers, and we kept the theoretical bounds as tight as possible under the stated assumptions.

The curse of dimensionality in transformers is, however, well-documented in the literature (see, e.g., [1]), making this property of our bound unsurprising.

Nevertheless, we argue that our article--by explicitly computing the bound and detailing the influence of various architectural choices (e.g., width, depth, activation function)--serves as a practical guide for users that are aware of the curse of dimensionality in transformers but seeking strategies to mitigate its impact on generalization.

Continuous Partial Derivatives of All Orders

Practical transformer implementations often rely on activation functions (e.g., Swish, GeLU) with continuous first- and second-order derivatives. While higher-order smoothness is not always necessary for stable training, it is critical for our theoretical guarantees to control sensitivities in high-dimensional spaces. Examples of architectures meeting these criteria include those using Swish or GeLU activations. For cases where these assumptions are relaxed, the generalization bounds would weaken correspondingly, as they depend on bounding the higher-order derivatives. In such cases, focusing on the most dominant terms (e.g., first or second derivatives) could yield approximate bounds that remain informative.

Experiments

As our paper focuses on theoretical questions and is already content-heavy, we prefer to explain our results in detail, instead of adding additional complexity by introducing experiments. We agree, however, that experiments can be very insightful, and we hope that our paper poses a good basis for a work with a more practical focus.

Formal Explanation of Parameter s

Thank you for pointing this out, we clarify the corresponding passages in our revised version. In our initial manuscript we explained the meaning of $s$ in Section 3.1 (Model Complexity Term). The parameter $s$ represents the order of derivatives considered in the smoothness class $C^s$. Intuitively speaking, our result yields $s \in \mathbb N$ different bounds, each for a different level of smoothness, and as the sample size grows, the tightest bound is of higher derivative level. When one bound is superseded by the next in terms of "tightness", we call this a phase transition.

Markovianity

We changed the formulation of our manuscript to take into account transformer models with finite sequence length $M \in \mathbb N$. We detailed this change (which is done via a Markovian lift) in the general rebuttal, please refer to it for more details.

We would expect that most real-life data sources from those in NLP to mathematical finance are Markovian in an extended state-space, or at least approximately so (in the sense of the quantitative version of the Echo-State property in reservoir computing (e.g. [2] and [3]) defined in Definitions 4.4 and 4.9 in [4], which are approximately satisfied by a broad range of non-Markovian "general" SDEs; see Proposition 4.2 [4]).

References

[1] Borde, Haitz Sáez de Ocáriz, et al. "Scalable Message Passing Neural Networks: No Need for Attention in Large Graph Representation Learning." arXiv preprint arXiv:2411.00835 (2024).

[2] Gonon, Lukas, and Juan-Pablo Ortega. "Fading memory echo state networks are universal." Neural Networks 138 (2021): 10-13.

[3] Grigoryeva, Lyudmila, and Juan-Pablo Ortega. "Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systems." Journal of Machine Learning Research 19.24 (2018): 1-40.

[4] Acciaio, Beatrice, Anastasis Kratsios, and Gudmund Pammer. "Designing universal causal deep learning models: The geometric (hyper) transformer." Mathematical Finance 34.2 (2024): 671-735.

Scalability

We understand that transformers do not scale well, indeed this is well-known in the literature, see e.g. [1] for a discussion. However the curse of dimensionality is necessarily there both in worst-case learning and approximation guarantees, such as those which are the object of study in our paper.

Nevertheless, we argue that our article--by explicitly computing the bound and detailing the influence of various architectural choices (e.g., width, depth, activation function)--serves as a practical guide for users that are aware of the curse of dimensionality in transformers but seeking strategies to mitigate its impact on generalization.

Generalization Bound for Finite-Sequence Transformers via Markovian Lift

We greatly appreciate your suggestion regarding the Markovian lift and have incorporated it into our revised manuscript. Specifically, we extended our generalization bound to cover arbitrary finite sequence lengths $M \in \mathbb{N}$, beyond the case $M = 1$ presented in the initial submission.

This extension is realized by employing the Markovian lift of the process, as you proposed, increasing the state space from $d$ to $Md$. Fortunately, this adaptation aligns seamlessly with our primary technical contribution, Theorem 2, which holds for arbitrary $M$. Detailed explanations are provided in our updated manuscript.

We initially excluded this generalization to focus the submission, as we plan to extend these results further to the case of infinite memory $M \to \infty$. While extending to infinite memory presents significant technical challenges, we believe that the current finite-memory results establish a robust foundation for this future work, which we aim to address in a separate paper.

Your insights have been invaluable in improving the scope and clarity of our work. Thank you once again for your thoughtful comments!

Typos

Thank you for pointing out those typos, we corrected them in the revised version. Line 2462, was unnecessarily convoluted and simply intended to show that boundedness and Markovianity of the process are fulfilled by definition of the process and the Markov property of the Brownian motion.

References

[1] Borde, Haitz Sáez de Ocáriz, et al. "Scalable Message Passing Neural Networks: No Need for Attention in Large Graph Representation Learning." arXiv preprint arXiv:2411.00835 (2024).

The Markovianity Assumption

Indeed our analysis can easily be extended to the case where the data-generating process becomes Markovian in an extended, but finite, state-space but setting $Md$ to be the dimension of that state-space. This can easily be done since our main Technical result, Theorem 2, allows for general finite $M$.

We would expect that most real-life data sources from those in NLP to mathematical finance are Markovian in an extended state-space, or at least approximately so (in the sense of the quantitative version of the Echo-State property in reservoir computing (e.g. [1] and [2]) defined in Definitions 4.4 and 4.9 in [3], which are approximately satisfied by a broad range of non-Markovian "general" SDEs; see Proposition 4.2 [3]).

We have updated our draft accordingly, which can be realized with minimal changes, as the core technical work is already addressed in Theorem 2. We highlighted the changes in the revised article. The case where $M$ is finite follows directly by extending the state space of our process from $d$ to $Md$. We initially excluded this because the resulting bounds become highly non-trivial when $M$ is infinite, a direction we intend to explore in future research.

Experiments

As our paper focuses on theoretical questions and is already content-heavy, we prefer to explain our results rather than delve into experiments.

Though we agree that experiments can be insightful, and we would like to highlight that we do provide numerical illustrations both on page $8$, explaining the role of each component in our bounds, and throughout Appendix B, which numerically computes our bounds and shows how various components of the transformer affect them: from the number of multi-head attention layers used to the choice of activation function.

References

[1] Gonon, Lukas, and Juan-Pablo Ortega. "Fading memory echo state networks are universal." Neural Networks 138 (2021): 10-13.

[2] Grigoryeva, Lyudmila, and Juan-Pablo Ortega. "Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systems." Journal of Machine Learning Research 19.24 (2018): 1-40.

[3] Acciaio, Beatrice, Anastasis Kratsios, and Gudmund Pammer. "Designing universal causal deep learning models: The geometric (hyper) transformer." Mathematical Finance 34.2 (2024): 671-735.

Novelty of our bounds

We thank you for providing references to generalization bounds for hypothesis trained with non-i.i.d. data. We have now incorporated these references in our revised version, highlighting how they clarify the gap our work addresses.

While these results provide convergence rates for transformer generalization in non-i.i.d. settings, they do not directly yield explicit constants. As we will demonstrate, deriving such constants requires computing a Lipschitz (or Sobolev) bound for transformer classes—a technically challenging task that we address in Theorem 2 of our paper. This result, detailed in pages 27-31 and 33-44 of our appendix, represents the most challenging technical component of our analysis.

We elaborated this point in the general rebuttal, and will comment here explicitly on the literature you mentioned. Please find further examples in our response to reviewer cDpD.

Mohri, Mehryar, and Afshin Rostamizadeh. "Rademacher complexity bounds for non-iid processes."

Whilst our claim holds true for all articles referenced, [1] is arguably the closest to our work. Here, Theorem 2 of [1] bounds the generalization of the class $T$ trained on non i.i.d. data using the empirical Rademacher complexity. In order to apply their result concretely to a transformer class $T$, one needs to apply a chaining argument (as mentioned in lines 143-150 of our paper), e.g. using Proposition 5.17 of [2]. In order to do so explicitly, one again needs to bound the covering number of $B_s(f_0,\rho)$ and which can only be done by computing $\rho$; the computation of which is performed in Theorem 2 of our paper.

Relevance of our generalization bound

In light of the existence of the results you mentioned, we would like to point out that our generalization bound, as presented in Theorem 1, is novel in the sense that it is based on a optimal transport-theoretic concept of exponential ergodicity. This condition is straightforward to verify or already established for many data-generating processes, as confirmed by a growing body of literature. Examples include classical SDEs, McKean-Vlasov equations, and reflected SDEs. Please refer to the general rebuttal and Section 2 of our paper for more details.

The Markovianity Assumption

We rely on Markovianity in our Wasserstein concentration of measure argument.

As we pointed out in the general rebuttal, we changed the notation of our draft to include models of finite sequence length $M \in \mathbb N$. This constitutes only a marginal change and can be easily realized by requiring that the Markovian lift of the underlying process fulfils our assumptions. Our main technical tool, namely Theorem 2, was already framed for the case where $M$ is positive but finite.

In principle, one can also consider processes which become Markovian when lifted to infinite dimensions, i.e. when their entire history is included. Though one can notify our results using the concentration of measure arguments in [3], in this case, the only Wasserstein concentration of measure results that we are aware of in infinite dimensions are for i.i.d. or Gaussian data, and thus they do not cover the non i.i.d. case. Thus, though developing such a concentration of measure results is interesting, it is beyond the scope of our paper as it would not apply solely to transformers.

Conditioning in Future Expectation

No, the future is defined with respect to the law of $X_t$, not its conditional law. This way, the future risk is a (deterministic) number; otherwise, it would be random and estimating it would be highly challenging (similar issues to the presence of common noise in mean field games would appear, which would obscure the main point of our paper).

Minor comments and typos

We thank you for identifying these typos, and we have corrected them accordingly. Thanks!

References

[1] Mohri, Mehryar, and Afshin Rostamizadeh. "Rademacher complexity bounds for non-iid processes." Advances in neural information processing systems 21 (2008). [2] Wainwright, Martin J. High-dimensional statistics: A non-asymptotic viewpoint. Vol. 48. Cambridge university press, 2019. [3] Benitez, Jose Antonio Lara, et al. "Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation." Journal of Computational Physics (2024): 113168.