Nonparametric Sparse Online Learning of the Koopman Operator

Boya Hou, Sina Sanjari, Alec Koppel, Subhonmesh Bose, Bose, Subhonmesh

Abstract

The Koopman operator provides a powerful framework for representing the dynamics of general nonlinear dynamical systems. However, existing data-driven approaches to learning the Koopman operator rely on batch data. In this work, we present a sparse online learning algorithm that learns the Koopman operator iteratively via stochastic approximation, with explicit control over model complexity and provable convergence guarantees. Specifically, we study the Koopman operator via its action on the reproducing kernel Hilbert space (RKHS), and address the mis-specified scenario where the dynamics may escape the chosen RKHS. In this mis-specified setting, we relate the Koopman operator to the conditional mean embeddings (CME) operator. We further establish both asymptotic and finite-time convergence guarantees for our learning algorithm in mis-specified setting, with trajectory-based sampling where the data arrive sequentially over time. Numerical experiments demonstrate the algorithm's capability to learn unknown nonlinear dynamics.

Introduction

The Koopman operator is often considered a "holy grail" in dynamical systems research. It offers a way to take a complex nonlinear system—such as weather patterns or robotic movements—and "lift" it into an infinite-dimensional space where the dynamics become linear. Because linear systems are far easier to analyze, predict, and control, this transformation is highly desirable.

However, two major hurdles have historically limited its practical application. First, the Batch Bottleneck requires all data to be collected upfront, which is impractical for real-time systems. Second, the Closedness Assumption assumes that the system's evolution stays within a pre-defined set of functions. In reality, dynamics often "escape" the chosen function space, a problem known as mis-specification. This paper introduces a sparse online learning algorithm that overcomes both obstacles.

Methodology: Bridging the Gap in Mis-specified Models

The proposed algorithm is based on Stochastic Operator Gradient Descent (SOGD) and operates within Reproducing Kernel Hilbert Spaces (RKHS). To handle the challenge of mis-specification, the authors establish a theoretical bridge between the Koopman operator and Conditional Mean Embeddings (CME).

Mapping the Koopman operator in a mis-specified setting.

As illustrated in the figure above, the Koopman operator $K$ is analyzed through its action on the RKHS $\mathcal{H}$. Theorem 3.1 in the paper proves that the Koopman operator is essentially the adjoint of the CME operator. This allows the researchers to treat operator learning as a regression problem in a vector-valued RKHS, effectively bypassing the need for the function space to be "closed" under the dynamics.

To ensure the model remains computationally efficient as data streams in, the algorithm employs a sparsification technique. Using a "dictionary" approach inspired by kernel matching pursuit, the model only incorporates a new data point if it provides information that cannot be sufficiently approximated by existing points. This prevents the model complexity from exploding over time.

Key Insights and Theoretical Guarantees

One of the most surprising theoretical findings is that sparsification is "free" asymptotically. While reducing the number of data points in the dictionary introduces a small bias in the short term, the natural "mixing" of the dynamical process eventually corrects these errors. Consequently, the sparsification budget does not degrade the ultimate quality of the learned operator.

Furthermore, the algorithm's convergence rate is dimension-independent. The number of samples required for the model to converge depends on the complexity of the underlying dynamics rather than the dimensionality of the state space. This makes the method uniquely suited for high-dimensional systems that would otherwise suffer from the curse of dimensionality.

Experimental Results

The algorithm was rigorously tested across three benchmarks:

  1. Langevin Dynamics: The algorithm successfully identified "metastable sets"—regions where the system tends to linger.
  2. Duffing Oscillator: The learner correctly identified distinct "Regions of Attraction" even when the model dictionary was compressed to just 8% of the total data points.
  3. Pendulum Environment (OpenAI Gym): In a reinforcement learning task, the sparse online learner achieved performance comparable to a full-knowledge Dynamic Programming reference while requiring 25% fewer data points than the full dataset.

Conclusion and Future Work

This work provides the first finite-time convergence rates for Koopman operator learning under Markovian sampling, where data arrives sequentially along a single trajectory. While the current framework relies on the system being "exponentially ergodic" (moving through the state space quickly enough to forget its starting point), it sets a new standard for online dynamical modeling. Future research will look toward applying these methods to agents that must reason and act across a variety of different, evolving environments.

Summary updated

Abstract

The Koopman operator provides a powerful framework for representing the dynamics of general nonlinear dynamical systems. However, existing data-driven approaches to learning the Koopman operator rely on batch data. In this work, we present a sparse online learning algorithm that learns the Koopman operator iteratively via stochastic approximation, with explicit control over model complexity and provable convergence guarantees. Specifically, we study the Koopman operator via its action on the reproducing kernel Hilbert space (RKHS), and address the mis-specified scenario where the dynamics may escape the chosen RKHS. In this mis-specified setting, we relate the Koopman operator to the conditional mean embeddings (CME) operator. We further establish both asymptotic and finite-time convergence guarantees for our learning algorithm in mis-specified setting, with trajectory-based sampling where the data arrive sequentially over time. Numerical experiments demonstrate the algorithm's capability to learn unknown nonlinear dynamics.
BibTeX
@misc{hou2025nonparametric,
  author = {Boya Hou and Sina Sanjari and Alec Koppel and Subhonmesh Bose and Bose, Subhonmesh},
  title = {{Nonparametric Sparse Online Learning of the Koopman Operator}},
  year = {2025},
  eprint = {2501.16489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.16489},
}
Figure