📊 statistics

Learning Ergodic Dynamical Systems from a Finite Trajectory

This paper presents a statistical learning framework for estimating optimal prediction functions and Koopman operators from a single finite trajectory of an ergodic stochastic dynamical system, providing high-probability guarantees by combining tools from statistical learning theory with concentration inequalities for geometrically ergodic Markov chains.

Original authors: Oleksii Kachaiev, Silvia Villa, Lorenzo Rosasco

Published 2026-07-27

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Oleksii Kachaiev, Silvia Villa, Lorenzo Rosasco

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to predict the future of a chaotic system, like the weather, the stock market, or even the next word in a text message. In the world of science, this is called learning a "dynamical system." Usually, when scientists try to learn these patterns, they rely on a golden rule of statistics: the data points must be independent. Think of it like flipping a coin; if you flip it heads, it doesn't change the odds of the next flip being tails. Each flip is a fresh start. But the real world rarely works that way. In a dynamical system, the next state depends entirely on the current one. If it's raining today, it's more likely to rain tomorrow. The data is a chain of events, a single, unbroken thread where every knot is tied to the one before it.

This is the tricky puzzle this paper tackles: How do you learn the rules of a system when you only have one long, continuous story to read, and every sentence depends on the last? The authors focus on "ergodic" systems. In plain English, an ergodic system is one that, if you watch it long enough, eventually visits every possible state it can be in, and the time it spends in each state matches the long-term probability of being there. It's like a drunkard walking around a park; if you watch him long enough, he will eventually step on every patch of grass, and the amount of time he lingers on any specific patch will tell you how much he likes that spot. The paper asks: Can we build a reliable crystal ball for such a system using just one of these long, wandering walks?

The paper, titled "Learning ergodic dynamical systems from a finite trajectory," dives into this problem by treating the system as a "Markov process." Think of a Markov process as a game of "follow the leader" where the leader's next move depends only on where they are standing right now, not on where they were five minutes ago. The authors propose a method called "nonlinear least squares" to guess the rules of this game. Imagine you are trying to guess the next move of a dancer. You watch them for a while, record their moves, and then try to draw a line (or a curve) that best predicts where they will step next. The authors show that even though the data is "sticky" (dependent on the past) and you only have one long recording, you can still make very good predictions. They prove mathematically that their method works, provided the system is "ergodic" and mixes well (meaning it doesn't get stuck in a corner forever). They also show how this method can be upgraded to handle more complex situations, like predicting multiple numbers at once, systems that remember the last few steps, and even the "Koopman operator," which is a fancy mathematical tool that describes how the entire system evolves over time. The result is a set of guarantees that tell us how accurate our predictions will be, depending on how long our single recording was and how "chaotic" or "sticky" the system's behavior is.

The Story of the Single Trajectory

The authors start by setting the stage with a simple but powerful idea: instead of trying to gather thousands of separate, independent snapshots of a system (which is often impossible), they focus on learning from a single, continuous movie of the system's life. They call this a "finite trajectory." In the real world, we often only have one history to study—like a single stock market crash or one season of a sports team. The paper argues that we can learn the rules of the game from this single history, but we have to be careful because the data isn't independent.

To make this work, the authors rely on a concept called "uniform geometric ergodicity." This is a mouthful, but think of it as a measure of how quickly a system forgets its past. If a system is "uniformly geometrically ergodic," it means that no matter where you start the system, it will quickly settle into a stable pattern of behavior. It's like a spinning top; no matter how you flick it, it eventually settles into a steady wobble. The authors prove that if the system behaves like this, the "memory" of the starting point fades away fast enough that we can treat the long-term average of the data as a reliable guide to the system's true nature.

The core of their work is a method called "nonlinear least squares." Imagine you are trying to teach a robot to predict the next step of a dance. You show the robot a video of the dance (the trajectory). The robot tries to guess the next move based on the current pose. The "least squares" part means the robot tries to minimize the total error between its guesses and the actual moves it sees. The authors show that even though the robot is learning from a single, connected video where every frame is linked to the next, it can still learn the dance perfectly well if the video is long enough and the dance is ergodic.

They derive "high-probability guarantees." This means they don't just say "it works"; they calculate exactly how likely it is to work and how close the prediction will be to the truth. They find that the accuracy depends on two main things: how long the trajectory is (more data is better) and how "sticky" the system is (how fast it forgets its past). If the system forgets its past quickly (high ergodicity), the learning is fast. If it holds onto its past for a long time (low ergodicity), you need a much longer video to get the same level of accuracy.

Going Beyond the Basics

The paper doesn't stop at simple, one-number predictions. The authors show that their method is flexible enough to handle more complex scenarios:

Vector-Valued States: Instead of predicting just one number (like temperature), the system might need to predict a whole vector of numbers (like temperature, humidity, and wind speed all at once). The authors show that their math works just as well for these multi-dimensional predictions, treating the whole vector as a single object in a high-dimensional space.
Higher-Order Systems: Sometimes, the next step doesn't just depend on the current step, but on the last few steps too. Think of a car: its next position depends on where it is and how fast it was going a moment ago. The authors show how to "lift" these higher-order systems into a new format where they look like simple, first-order systems, allowing their method to work on them as well.
Finite-State Spaces: What if the system can only be in a few specific states, like a board game where you can only be on squares 1 through 100? The authors adapt their method to this setting, showing it connects nicely to problems like predicting the next word in a sentence (where the "states" are words). They use a clever trick called a "surrogate least squares approach," which turns the problem of predicting a specific state into a problem of predicting a vector of probabilities, making it easier to solve.
Koopman Operators: Finally, the authors tackle the "Koopman operator." If the previous methods were about predicting the next step, the Koopman operator is about predicting the entire future evolution of any observable property of the system. It's like having a master key that can unlock the future behavior of any aspect of the system, not just the position. They show that their least squares method is actually a way to learn this master key, providing guarantees on how well the key fits the lock.

The Bottom Line

The paper concludes that learning from a single, finite trajectory is not only possible but can be done with rigorous mathematical guarantees, provided the system is ergodic. The authors provide a toolkit for doing this, complete with formulas that tell you how much data you need and how accurate your predictions will be. They emphasize that while the data is dependent (not independent), the "forgetting" nature of ergodic systems allows us to overcome this challenge. The results are proven mathematically, not just guessed or simulated, giving us a solid foundation for understanding and predicting complex, real-world systems from a single history. The paper leaves the door open for future work, suggesting that while they focused on specific norms and settings, the core ideas could be extended to even more complex scenarios, but for now, they have firmly established that a single story is enough to learn the rules of the game.

Technical Summary: Learning Ergodic Dynamical Systems from a Finite Trajectory

Problem Statement
This paper addresses the problem of learning stochastic dynamical systems from a single, finite trajectory. Unlike classical statistical learning theory, which assumes independent and identically distributed (i.i.d.) data, the data in this setting are generated by a time-homogeneous Markov process. The authors focus on discrete-time autonomous stochastic systems where the observations exhibit temporal dependence and are not necessarily initialized at the stationary distribution. The primary objective is to estimate the optimal one-step prediction function (the conditional expectation of the next state given the current state) and, subsequently, the Koopman operator, while providing non-asymptotic learning guarantees measured with respect to the process's invariant measure.

Methodology
The proposed framework combines tools from statistical learning theory (specifically kernel methods and regularized least squares) with quantitative ergodic theory for Markov chains.

Ergodic Assumption: The analysis relies on the assumption of Uniform Geometric Ergodicity (UGE). This condition ensures the existence of a unique invariant measure $\pi$ and guarantees that the distribution of the process converges to $\pi$ at a geometric rate, regardless of the initial distribution. This allows the authors to define the population risk with respect to $\pi$ and quantify the deviation between empirical averages along the trajectory and the true expectations.
Estimation Approach:
- Scalar and Vector-Valued States: The authors formulate the learning task as a regularized nonlinear least squares problem. They consider estimators linearly parametrized in a separable Hilbert space (potentially infinite-dimensional), such as those defined by Reproducing Kernel Hilbert Spaces (RKHS). The estimator minimizes the empirical risk plus a regularization term.
- Higher-Order Systems: For systems where the next state depends on the previous $p$ states (order- $p$ Markov processes), the authors reduce the problem to a first-order Markov process on the space of state tuples (lifted process).
- Finite-State Spaces: For finite state spaces, the authors employ a surrogate least squares approach. They encode states into a vector space (e.g., one-hot encoding) and learn a regression function in this space. The final prediction is obtained by decoding the regression output. This connects the problem to multi-category classification and structured prediction.
- Koopman Operators: The framework is extended to learning the Koopman operator, which describes the evolution of observables. The authors show that learning the Koopman operator is equivalent to kernel Koopman regression, deriving guarantees in the operator norm.
Concentration Analysis: A central technical contribution is the derivation of concentration inequalities for Hilbert-space-valued additive functionals of uniformly geometrically ergodic Markov chains. The proof strategy involves:
- Decomposing the error into approximation and estimation components.
- Utilizing the Poisson equation to decompose the additive functional into a martingale part and a boundary term.
- Applying Pinelis-Bernstein inequalities for Hilbert-space-valued martingales to bound the martingale part.
- Explicitly accounting for the "burn-in" period and the transient phase before convergence to stationarity.

Key Contributions

Non-Asymptotic Learning Guarantees: The paper derives high-probability finite-sample bounds for the prediction error. These bounds hold for a single trajectory starting from an arbitrary initial distribution, without assuming the process is initialized at stationarity.
Explicit Dependence on Ergodicity: The derived bounds explicitly feature a multiplicative constant factor of the form $(C / (1-\rho))^2$ , where $\rho$ is the geometric convergence rate and $C$ is a constant from the UGE assumption. This highlights how the mixing time of the system influences the sample complexity.
Generalization to Diverse Settings: The methodology is shown to extend naturally to:
- Vector-valued and infinite-dimensional state spaces.
- Higher-order Markov processes (via state lifting).
- Finite-state spaces (via surrogate loss functions).
- Learning the Koopman operator in operator norm.
Concentration Inequalities: The authors provide a novel concentration inequality for Hilbert-space-valued observables of uniformly ergodic Markov chains, leveraging martingale decompositions and Poisson equation solutions.

Results

Universal Consistency: Under the assumption of universal models (e.g., using universal kernels), the least squares estimator is shown to be universally consistent; the prediction error converges to zero almost surely as the trajectory length $T \to \infty$ .
Convergence Rates: For well-specified models (where the true function lies within the hypothesis class), the paper establishes convergence rates of order $O(T^{-1/2})$ (up to logarithmic factors). This matches the optimal rates known for i.i.d. data under similar assumptions.
Error Decomposition: The error analysis reveals two distinct sources of deviation from the i.i.d. case:
1. A multiplicative constant depending on the mixing properties of the chain ( $C/(1-\rho)$ ).
2. A boundary term of order $O(1/(\lambda T^2))$ arising from the truncation of the martingale decomposition, which decays faster than the leading estimation error term.
Finite-State Specifics: In the finite-state setting, the error bounds depend on the margin condition (the gap between the highest and second-highest transition probabilities) and the norm of the transition matrix, but notably do not depend on the minimum invariant probability or the cover time of the trajectory.

Significance and Claims
The authors position this work as a bridge between statistical learning theory and the analysis of dynamical systems. They claim that by explicitly accounting for the non-i.i.d. nature of trajectory data through the lens of uniform geometric ergodicity, one can derive rigorous learning guarantees that are comparable to those in the i.i.d. setting, despite the presence of temporal dependence.

The paper emphasizes that the approach avoids the need for explicit parametric modeling of the transition rule, instead treating the problem as a nonparametric regression task. The derivation of learning guarantees for the Koopman operator from a single trajectory is presented as a natural extension of the one-step prediction framework, offering a simplified derivation based on feature maps rather than full RKHS machinery.

The authors modestly note that while they focus on operator-norm estimates and specific concentration techniques, other norms and developments (such as benign overfitting regimes or more complex dependency structures) are left for future work. The primary contribution is the establishment of a theoretical foundation for learning from single trajectories in ergodic systems, highlighting the specific role of the mixing time in determining sample complexity.

The Story of the Single Trajectory

Going Beyond the Basics

The Bottom Line

More like this