Universal Learning of Nonlinear Dynamics

arXiv:2508.11990 · cs.LG, math.OC, stat.ML · Submitted 2025-08-16 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Universal Learning of Nonlinear Dynamics".

Jane: The gist We study a fundamental problem of learning a marginally stable unknown nonlinear dynamical system by describing an algorithm based on spectral filtering that learns a mapping from past…

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're diving into this paper, "Universal Learning of Nonlinear Dynamics." It looks like they're tackling a really fundamental problem: how to learn a nonlinear system when you don't know its exact rules, and the system itself is only marginally stable.

Jane: That sounds tough. What do you mean by "marginally stable"? Is that some fancy term for systems that are on the edge of not blowing up?

Tom: Exactly. It means the dynamics are tricky because they aren't strictly stable, which makes learning them really hard with standard methods, so this paper describes an algorithm based on spectral filtering to learn a mapping from past observations to what happens next.

Lu: The core idea here is moving away from trying to figure out the true system dynamics directly and instead competing against idealized predictors that we can actually control.

Meng: Competing against something sounds interesting, but what does that actually mean for deployment? Like, if I'm running this on a server, what's the practical cost of this approach?

Jane: Well, they frame it as an improper learning paradigm where the goal isn't to recover the true system dynamics but to minimize regret against a class of well-behaved predictors.

Tom: Right. And instead of just picking any predictor, they leverage control theory structure to define that comparator class itself. They design an algorithm that performs as well as the best possible high-dimensional linear observer for the sequence we're observing.

Lu: That's a big conceptual leap because it takes tools from control theory and uses them not to build a controller, but just to define what makes a good predictor in this context.

Meng: So, if I'm looking at this from an engineering standpoint, does defining the comparator class make the optimization problem easier or harder to solve on my end?

Tom: It shifts the focus from the hard nonconvex system identification problem to a more manageable, often convex, problem of minimizing regret against that chosen class. They use online convex optimization for this.

Jane: That makes sense. So, what's the main algorithm they introduce? Is it something we can just plug into our existing ML pipeline?

Tom: The main component is Observation Spectral Filtering or OSF. It's an efficient algorithm based on online convex optimization that they guarantee will learn any observable nonlinear dynamical system that has finitely many marginally stable modes.

Lu: They make it improper because it doesn't explicitly estimate the hidden states or the dynamics; it directly constructs this mapping from past observations to future predictions. That’s a key feature for handling these complex systems.

Meng: So, if I have noisy data, does OSF handle that noise well? Because in production, data is never perfect.

Tom: The paper states that their main technical component is a new spectral filtering algorithm for linear dynamical systems which incorporates past observations and applies to general noisy and marginally stable systems. It's designed to handle noise correction as well.

Title and authors: Jane: That's reassuring about the noise aspect, but what are the specific guarantees they give us? What kind of performance are we looking at in terms of prediction error?

Tom: They have an LDS guarantee, which is the core technical engine for OSF. This applies to asymmetric dynamics under adversarial noise with performance guarantees that are independent of the system’s hidden dimension.

Lu: That independence from the hidden dimension is significant because it means the performance bounds don't get worse just because we can't fully resolve every tiny detail of the true system.

Meng: Independent of the hidden dimension, that sounds like a solid guarantee for scaling up our models, doesn't it?

Jane: It does, but there are also these control-theoretic insights into how hard it is to learn the system from its outputs. They formalize this through a "Luenberger program," which quantifies the inherent difficulty of learning by defining a value called Q star.

Tom: That Q star value appears directly in the data-dependent learning bounds, which is what really links control theory to machine learning here. It shows the learnability is tied directly to how observable the system is from its outputs.

Lu: It provides a quantitative link between the control-theoretic concept of observability and the machine learning concept of learnability through this Luenberger program. That framework helps us judge if a system is even amenable to learning from its outputs, which is crucial for theory.

Meng: So, if we want to know upfront if a new system class will be feasible for this method, we look at Q star derived from that program?

Jane: Exactly. And they also introduce a simple way to handle nonlinear systems by using a global linearization based on state-space discretization to create a high-dimensional linear dynamical system approximation.

Tom: That's the simple construction they use to approximate any bounded, Lipschitz nonlinear system with a high-dimensional LDS. It trades an increase in dimensionality, which our learning algorithm is immune to, for guaranteed linearity and approximation accuracy.

Lu: This technique allows us to apply their linear systems algorithm rigorously to the nonlinear case by providing that foundation of a linear system approximation.

Meng: So we're trading complexity for a known structure, even if that structure is just an approximation? What's the trade-off on practical computation time for that discretization?

Tom: The paper mentions this technique provides a rigorous foundation, but it doesn't detail the exact computational cost of the state-space discretization itself. It focuses more on how it enables applying their linear systems algorithm to the nonlinear case.

Jane: Moving toward the results, they show that the regret scaling is determined only by this robust observability constant Q star. Theorem three point one gives a prediction error bound where X t equals one, showing something like X t squared less than or equal to O Q star squared log(Q star) times some other terms involving T and m over T.

Title and authors: Tom: That bound shows that the prediction error scales with the system's robust observability constant Q star, which is a key metric. It involves log terms related to the time horizon T and maybe some dimension m squared.

Lu: The analysis connects this entire learning process back to the Luenberger program, which defines Q star, giving us a complete picture of how the system's structure dictates the final performance bounds.

Meng: So what does this mean for running things at scale? If I have a system with a very high Q star value, does that mean my required resources explode instantly?

Jane: Not necessarily an instant explosion, but the bound shows that performance depends sharply on those Q star values. For physical systems satisfying detailed balance conditions, where the Koopman operator can be made self-adjoint, there are sublinear regret bounds because Q star becomes small.

Tom: That's important because if a system satisfies those detailed balance conditions, like in Langevin dynamics, Algorithm one can learn it provably and efficiently with few parameters <ref:2508.11990#pg1>.

Lu: It’s a strong statement about the conditions under which we can achieve good results without needing an infinite number of parameters to capture the dynamics.

Meng: So if I'm working on a physical simulation where I know those balance conditions hold, this paper suggests we have a provable path to learn it efficiently.

Jane: That's a major implication for physical modeling that you can actually learn from data without needing perfect knowledge of the underlying physics upfront.

Tom: Overall, "Universal Learning of Nonlinear Dynamics" provides a principled lens—the Luenberger program—to analyze dynamical systems by characterizing their Q star values, which gives us principled judgments about how amenable they are to learning from partial observations using improper methods.

Lu: The paper is really about repurposing control theory tools to define a robust comparator class for an online convex optimization algorithm. That's the main mechanism here.

Meng: It feels like they've given us a way to stop chasing the true, complex dynamics and just focus on being better than a well-defined linear observer.

Jane: It is certainly a way to measure how much information we actually need from our data sequence without trying to perfectly reconstruct the hidden state space of the system.

Tom: So, if you're dealing with a complex nonlinear system, this paper gives you a formal framework that connects control theory to online learning guarantees through Q star values.

Lu: It’s about establishing provable performance bounds based on structural properties derived from control theory rather than just empirical testing.

Meng: For production, it points toward using these structural properties to select the right learning approach instead of just throwing a big black-box architecture at the problem hoping for the best.

Jane: So, we have a formal tool now to judge the feasibility of learning nonlinear systems based on their inherent observability structure.

Tom: It’s a new lens for analyzing these systems that moves beyond just fitting data to finding structural guarantees about what's learnable.

The paper's summary: Tom: So, to recap, this paper is about using spectral filtering to learn a nonlinear dynamical system when you don't know its exact rules and it’s only marginally stable.

Jane: That’s right, and what they do differently is they aren't trying to find the true system dynamics directly. Instead, they frame it as competing against a class of idealized predictors that we can control.

Lu: The core mechanism is Observation Spectral Filtering, or OSF. It constructs a direct mapping from past observations to future predictions without ever estimating the hidden states or the dynamics explicitly.

Meng: So, if I’m looking at this from an engineering standpoint, it means we’re not trying to build a perfect simulator; we’re building something that predicts based on what we see online.

Tom: Exactly. And they use a new spectral filtering algorithm for linear systems as the technical engine for this whole thing, which works even with noisy and marginally stable systems.

Jane: They introduce this idea of an improper learning paradigm where the goal is minimizing regret against a carefully chosen comparator class instead of trying to identify the system itself.

Lu: The really interesting part is how they connect control theory to this. They use a concept called the Luenberger program to define a measure, Q star, that quantifies exactly how hard it is for the system to learn from its outputs.

Tom: That Q star value shows up directly in their learning bounds, which links the physical property of observability to the machine learning performance.

Jane: It’s like they’re giving us a quantitative way to judge if a system is even worth trying to learn from its observations before we start training models.

Meng: That sounds useful for deployment because it gives us a structural metric instead of just relying on arbitrary accuracy scores on some benchmark.

Tom: And they handle the nonlinear part by using this simple global linearization, which turns the nonlinear system into a high-dimensional linear dynamical system approximation that our algorithm can actually process.

Lu: That trades an increase in dimension for guaranteed linearity and approximation accuracy, so we get to use our powerful linear systems tools on something close enough to the real thing.

Jane: They show that for physical systems with certain detailed balance conditions, like those in Langevin dynamics, you can get sublinear regret bounds because Q star becomes small.

Tom: So if your physics follow those specific detailed balance rules, this algorithm can learn the system provably and efficiently with a few parameters.

Lu: It’s about establishing a provable path to learning physical systems without needing an infinite number of parameters to capture everything.

Jane: This paper really gives us a framework to judge the feasibility of learning nonlinear systems based on their inherent observability structure derived from control theory.

The paper's improvements: Tom: So, we’re looking at how they suggest improving this universal learning framework for nonlinear dynamics by adding some specific structural insights.

Jane: What kind of improvements are they talking about now? I want to know if they’re fixing the scaling issues Meng was worried about earlier.

Lu: They suggest removing the need for a square root spectral gap in the observer system because we don't see much effect from that in practice.

Meng: So, if we can skip that spectral gap requirement, it simplifies deployment and makes things faster on real hardware, I guess?

Tom: Yeah. And they say they’ve already done the work for spectral filtering itself; they just need to construct a high-dimensional linear dynamical system approximation that works for systems with small RC and Rxzero constants.

Jane: That’s good because it means we can move forward using standard tools like the Koopman operator methodology to build that approximation.

Lu: They also flag something important: the most significant extension would be allowing open-loop inputs in the nonlinear system, which is a big step for real-world control problems.

Tom: Open-loop inputs—that means we’re not just reacting to what happened before but maybe we can feed in some external commands to steer the system.

Jane: That opens up a whole new kind of prediction problem where the system isn't totally self-contained. It moves it closer to how we model physical systems that are actively controlled.

Lu: They also note that they have already addressed the case where they use rho equals zero in Lemma five point four, which is related to spectral filtering, so the math for those cases is already there.

Meng: So, while the main theoretical path forward involves a higher dimension approximation and open-loop inputs, the core filtering mechanism is actually quite mature right now?

Tom: Exactly. The idea isn't that we have a totally finished system; it's more about refining the tools to make those high-dimensional approximations work better for specific physical constraints.

Jane: So, while they haven’t solved every problem, they’ve pointed us toward the next steps: making those approximations tighter and handling external inputs.

Lu: And if we look at the broader context of what else is happening in AI research today—like how models learn to explore three dee worlds or how vision-language models understand agriculture better than they show—this paper provides a structural foundation for learning dynamics in a much more complex setting.

Conclusion: Tom: So, to wrap up, this paper, "Universal Learning of Nonlinear Dynamics," shows how we can use observation spectral filtering to learn complex nonlinear systems without needing to know the true rules upfront.

Jane: It gives us a structured way—the Luenberger program—to decide if a system is even learnable from its outputs based on its observability properties.

Lu: The main idea is leveraging control theory concepts to define a robust comparator class for an online optimization algorithm, which simplifies the learning problem significantly.

Meng: For deployment, this means we get provable performance guarantees tied to the system's Q star value rather than just hoping the model performs okay on some test set.

Tom: And they handle nonlinearity by using a high-dimensional linear dynamical system approximation based on state-space discretization, which is a solid way to make it work.

Jane: It’s about moving from trying to perfectly guess the physics to being guaranteed to perform well against the best possible linear predictor.

Lu: The future work points toward refining those approximations and opening up the framework to handle open-loop inputs in real control scenarios.

Meng: So, if we think about this in terms of what breaks at scale, it’s less about massive data and more about ensuring the underlying system structure aligns with these theoretical bounds.

Tom: Right. The implication is that for certain physical systems satisfying specific conditions like detailed balance, we can learn them efficiently with few parameters using Algorithm one.

Jane: It means we have a formal way to judge the feasibility of learning nonlinear signals based on how observable those signals are from its outputs.

Lu: This approach connects the control-theoretic concept of observability directly to the machine learning concept of learnability through that Q star value.

Meng: It’s about using structure to constrain complexity, which is exactly what we need when we want something reliable for production systems.

Tom: So, "Universal Learning of Nonlinear Dynamics" provides a principled lens—the Luenberger program—to analyze dynamical systems by characterizing their Q star values.

Jane: That’s the big picture here: using control theory to give us principled judgments about how amenable these systems are to learning from partial observations with improper methods.

Lu: The work is very solid in establishing these theoretical guarantees for the general case, especially regarding asymmetric dynamics and adversarial noise.

Meng: I’m just curious what comes next; I’m interested if they can make those high-dimensional approximations even more computationally light for our hardware constraints.

Tom: That seems like the natural next step, focusing on making that approximation practical for real-time inference.

Courant Institute of Mathematical Sciences, New York University · Princeton University

cs.LG, math.OC, stat.ML

Submitted: 2025-08-16

Updated: 2026-10-19

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: The gist We study a fundamental problem of learning a marginally stable unknown nonlinear dynamical system by describing an algorithm based on spectral filtering that learns a mapping from past

Key concepts

Improper Learning Paradigm: Instead of trying to find the true nonlinear dynamics directly, this approach frames learning as a competition against well-behaved linear predictors. This shifts the focus from solving a difficult system identification problem to minimizing regret against these comparators, which is often easier mathematically.
Observation Spectral Filtering (OSF): This is an efficient algorithm based on online convex optimization that learns nonlinear systems by constructing a direct mapping from past observations to future predictions. Crucially, it does not explicitly estimate hidden states or dynamics; it focuses solely on prediction accuracy.
Luenberger Program: This is a control-theoretic optimization problem used to analyze system learnability. Its solution quantifies the inherent difficulty of learning a nonlinear system from its outputs by connecting observability properties to machine learning regret bounds.

Summary

The gist We study a fundamental problem of learning a marginally stable unknown nonlinear dynamical system by describing an algorithm based on spectral filtering that learns a mapping from past observations to the next.

Improper Learning Paradigm

This work advocates for a third paradigm: improper learning for dynamical systems, which reframes the problem as competing in hindsight against idealized, well-behaved predictors rather than attempting to learn the true system dynamics directly <ref:2508.11990#pg3> This reframing of the problem is a key conceptual leap <ref:2508.11990#pg3> It shifts the focus from the difficult, nonconvex problem of system identification to the more manageable, often convex, problem of regret minimization against a carefully chosen comparator class <ref:2508.11990#pg3> The central idea of this work is to leverage the rich mathematical structure of control theory not for designing a controller, but for defining this very comparator class <ref:2508.11990#pg3> Instead of attempting to learn the true nonlinear system, we design an algorithm that is guaranteed to perform as well as the best possible high-dimensional linear observer system for the given observation sequence <ref:2508.11990#pg3>

Observation Spectral Filtering (OSF)

We introduce Observation Spectral Filtering (OSF), an efficient algorithm based on online convex optimization that is guaranteed to learn any observable nonlinear dynamical system with finitely many marginally stable modes <ref:2508.11990#pg3> The algorithm is ”improper” in that it does not explicitly estimate the system’s hidden states or dynamics; instead, it directly constructs a mapping from past observations to future predictions <ref:2508.11990#pg3> Our main technical component of our method is a new spectral filtering algorithm for linear dynamical systems, which incorporates past observations and applies to general noisy and marginally stable systems <ref:2508.11990#pg2>

Key Contributions

The paper makes several contributions to the theory and practice of learning dynamical systems <ref:2508.11990#pg3>:

We introduce Observation Spectral Filtering (OSF), an efficient algorithm based on online convex optimization that is guaranteed to learn any observable nonlinear dynamical system with finitely many marginally stable modes <ref:2508.11990#pg3>
An LDS guarantee: The core technical engine of OSF is a learning guarantee for linear dynamical systems (LDS) <ref:2508.11990#pg3> This method applies to asymmetric dynamics under adversarial noise with performance guarantees that are independent of the system’s hidden dimension <ref:2508.11990#pg2>
A control-theoretic analysis: We provide a novel analytical framework that connects the learnability of a nonlinear system to the properties of its best possible high-dimensional linear observer <ref:2508.11990#pg3> This connection is formalized through a ”Luenberger program,” an optimization problem whose solution quantifies the inherent difficulty of learning the system from its outputs <ref:2508.11990#pg3>
A simple global linearization: We introduce a simple construction to approximate any bounded, Lipschitz nonlinear system with a high-dimensional LDS <ref:2508.11990#pg3> This technique, based on state-space discretization, provides a rigorous foundation for applying our linear systems algorithm to the nonlinear case <ref:2508.11990#pg3>

Theoretical Guarantees and Analysis

The main result shows that the regret scaling is determined only by the system’s robust observability constant Q⋆ <ref:2508.11990#pg3> Theorem 3.1 states that running Algorithm 1 with specific parameters produces a sequence of predictions yˆ1,..., yˆT for which X T t=1∥yˆt − yt∥ ≤ O Q 2⋆ log(Q⋆) · dX R log(RT)m2 log7(mT) · √T <ref:2508.11990#pg3> The analysis connects the learnability of a nonlinear system to the properties of its best possible high-dimensional linear observer through the Luenberger program, which defines Q⋆ <ref:2508.11990#pg2>

Performance on Nonlinear Systems

The performance of various algorithms is tested on several nonlinear systems, including the Lorenz system and the double pendulum <ref:2508.11990#pg8> The SFeDMD method is able to outperform eDMD with fewer parameters in the fully observed setting, despite both using the same dictionary of observables <ref:2508.11990#pg8> In contrast, a filtering-based predictor is able to aggregate information across time in a way that can handle partial observations naturally, whereas eDMD cannot <ref:2508.11990#pg8>

Conclusion

The Luenberger program provides a new lens through which to analyze dynamical systems by characterizing their Q⋆ values, making principled judgments about their amenability to learning from partial observations with improper methods <ref:2508.11990#pg2> Algorithm 1 is a very good general choice for such a method, since it can efficiently and provably learn to predict systems that are either physical or strongly stable <ref:2508.11990#pg2> The ability of these algorithms to learn a nonlinear signal depends sharply on the corresponding Q⋆ values of the generating system via our regret bounds <ref:2508.11990#pg2> It is possible to learn physical systems provably and efficiently with few parameters if they satisfy certain detailed balance conditions, such as those found in Langevin dynamics <ref:2508.11990#pg2>

Lower Bounds

The lower bound for any algorithm that does not see w t when predicting yˆt+1 suffers a linear cost in terms of the disturbance sizes and ambient dimension up to constant factors <ref:2508.11990#pg4> The computational lower bound sketch based on cryptographic hardness assumptions shows that for deterministic nonlinear dynamical systems, the expected l1 loss per step is 1 − o(1), matching the loss of a random ±1 guess <ref:2508.11990#pg4>

Future Work

The most natural next step is to remove the need for a √T spectral gap in the observer system (since we don’t see its effect much in practice) <ref:2508.11990#pg5> The work is already done in terms of spectral filtering (we can use the ρ = 0 case of Lemma 5.4), and the only thing to be done is to construct a high-dimensional LDS which approximates the original nonlinear system for which both RC and Rx0 can be small <ref:2508.11990#pg2> We anticipate this to be achievable using the more standard Koopman operator methodology <ref:2508.11990#pg2> The most significant extension would be to allow for the presence of open-loop inputs in the nonlinear system <ref:2508.11990#pg2>

References

[1] Naman Agarwal, Xinyi Chen, Evan Dogariu, Vlad Feinberg, Daniel Suo, Peter Bartlett, and Elad Hazan. Futurefill: Fast generation from convolutional sequence models <ref:2508.11990#pg3>

[2] Naman Agarwal, Daniel Suo, Xinyi Chen, and Elad Hazan. Spectral state space models <ref:2508.11990#pg3>

[3] Oren Anava, Elad Hazan, Shie Mannor, and Ohad Shamir. Online learning for time series prediction <ref:2508.11990#pg3>

[4] BDO Anderson and JB Moore. Kalman filtering: Whence, what and whither? Mathematical system theory: the influence of RE Kalman <ref:2508.11990#pg4>

[5] Sanjeev Arora, Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Towards provable control for unknown linear dynamical systems <ref:2508.11990#pg3>

[6] Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions <ref:2508.11990#pg4>

[7] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. A new approach to learning linear dynamical systems <ref:2508.11990#pg3>

[8] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Morris Yau. Tensor decompositions meet control theory: learning general mixtures of linear dynamical systems <ref:2508.11990#pg3>

[9] George EP Box and Gwilym M Jenkins. Time series analysis <ref:2508.11990#pg4>

[10] Anand Brahmbhatt, Gon Buzaglo, Sofiia Druchyna, and Elad Hazan. A new approach to controlling linear dynamical systems <ref:2508.11990#pg4>

[11] Lucas Brivadis, Vincent Andrieu, and Ulysse Serres. Luenberger observers for discrete-time nonlinear systems <ref:2508.11990#pg4>

[12] Steven L. Brunton, Marko Budisiˇ c, Eurika Kaiser, and J. Nathan Kutz. Modern koopman theory for ´ dynamical systems <ref:2508.11990#pg3>

[13] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems <ref:2508.11990#pg3>

[14] Sinho Chewi. Log-Concave Sampling <ref:2508.11990#pg4>

[15] Marco Cuturi and Arnaud Doucet. Autoregressive kernels for time series <ref:2508.11990#pg3>

[16] L. Elsner and M.H.C. Paardekooper. On measures of nonnormality of matrices <ref:2508.11990#pg3>

[17] C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. Brax – a differentiable physics engine for large scale rigid body simulation <ref:2508.11990#pg8>

[18] Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. No-regret prediction in marginally stable systems <ref:2508.11990#pg4>

[19] Calin-Ioan Gheorghiu. On the scalar measure of non-normality of matrices – dimension vs. structure <ref:2508.11990#pg4>

[20] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces <ref:2508.11990#pg3>

[21] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems <ref:2508.

Improvements for AI systems

Bold Header: Universal Learning of Nonlinear Dynamics Improvement

The improved system can learn any observable nonlinear dynamical system with finitely many marginally stable modes by directly constructing a mapping from past observations to future predictions using Observation Spectral Filtering (OSF). This algorithm is improper in that it does not explicitly estimate the system’s hidden states or dynamics; instead, it directly constructs a mapping from past observations to future predictions.

Bold Header: Robust Learning of Asymmetric Systems

The improved system can learn asymmetric linear dynamical systems under adversarial noise with performance guarantees that are independent of the system’s hidden dimension, significantly generalizing prior spectral filtering methods. This is achieved by leveraging the LDS guarantee which applies to asymmetric dynamics under adversarial noise, aligning with efforts to extend these techniques to broader system classes.

Bold Header: Control-Theoretic Learnability Assessment

The improved system can quantify the inherent difficulty of learning a system from its outputs by calculating the Luenberger program, whose optimal value, denoted as Q⋆, appears directly in data-dependent learning bounds. This framework establishes a quantitative link between the control-theoretic concept of observability and the machine learning concept of learnability.

Bold Header: Scalable Approximation via Global Linearization

The system can handle general bounded, Lipschitz nonlinear systems by using a simple global linearization based on state-space discretization to approximate them with a high-dimensional LDS. This trades an increase in dimensionality—to which the learning algorithm is immune—for guaranteed linearity and approximation accuracy.

Bold Header: Sublinear Regret Guarantees for Physical Systems

For physical systems satisfying certain detailed balance conditions, the improved system can achieve sublinear regret bounds on prediction error because the Koopman operator can be made self-adjoint, implying a small Q⋆ and so strong performance of Algorithm 1 due to Theorem 3.1.

Bold Header: Adaptive Learning Strategy Based on System Structure

The system can automatically determine the most efficient learning strategy by leveraging the control-theoretic properties of the underlying dynamics, as spectral filtering naturally competes against real-diagonalizable LDS’s (Σ ⊆ [−1, 1], i.e., physical systems with detailed balance) and regression naturally competes against stable LDS’s (Σ ⊆ D1−γ).

Bold Header: Data-Driven Approximation of Nonlinear Dynamics

The system can approximate any bounded and marginally stable nonlinear system via a space-discretized Markov chain argument that achieves the same goal as the Koopman operator, allowing for a prediction error bound derived from the discretization error of Lemma 5.5.

Abstract

We study the fundamental problem of one-step prediction of a marginally stable unknown nonlinear dynamical system. We describe an algorithm for this problem, based on the technique of spectral filtering, which learns a mapping from past observations to the next based on a spectral representation of the system. Using techniques from online convex optimization, we prove vanishing prediction error for any nonexpansive nonlinear dynamical system with finitely many marginally stable modes, with rates governed by a novel quantitative control-theoretic notion of learnability. The main technical component of our method is a new spectral filtering algorithm for linear dynamical systems, which incorporates past observations and applies to general noisy and marginally stable systems. This generalizes the original spectral filtering algorithm to both asymmetric dynamics as well as incorporating noise correction, and is of independent interest.