A Koopman framework for rare event simulation in stochastic differential equations

Benjamin J. Zhang, Tuhin Sahai, Youssef M. MarzoukJournal of Computational Physics 2022 · DOI · OpenReview

Introduction

Rare events, often termed "black swans," represent low-probability, high-impact occurrences in dynamical systems, such as material failures, financial crashes, or extreme weather events. While these events are infrequent, their consequences necessitate rigorous modeling and simulation. Engineers typically employ Stochastic Differential Equations (SDEs) to model such systems; however, simulating rare events poses a significant computational challenge. Standard Monte Carlo methods require prohibitive amounts of compute time to observe even a single rare event. To address this, Importance Sampling (IS) is used to "nudge" simulations toward rare outcomes. The theoretical optimum for IS is the Doob $h$-transform, a biasing function that yields a zero-variance estimator. However, calculating this transform requires solving the Kolmogorov Backward Equation (KBE), a partial differential equation that is often intractable in high-dimensional or highly nonlinear systems.

Methodology

This research introduces a data-driven framework that bridges dynamical systems theory and rare event simulation by leveraging the Stochastic Koopman Operator (sKO). The Koopman operator shifts the focus from state evolution to the evolution of functions of those states. Crucially, the generator of the sKO is mathematically identical to the operator used in the KBE, providing a direct link between Koopman theory and the Doob $h$-transform.

Eigenfunction Approximation and gEDMD

The authors propose that the solution to the KBE can be approximated as a linear combination of the sKO’s eigenfunctions. To extract these eigenfunctions from data, the framework utilizes Generator Extended Dynamic Mode Decomposition (gEDMD). Unlike standard DMD, which relies on temporal snapshots, gEDMD leverages the analytical form of the SDE—specifically its drift and diffusion terms—to project the operator onto a predefined set of basis functions, such as polynomials.

The Simulation Workflow

The proposed workflow consists of four primary stages:

  1. Data Collection: Execute "bulk" simulations of the system where rare events do not occur.
  2. Operator Extraction: Apply gEDMD to the bulk data to identify the system's eigenfunctions.
  3. Representation: Represent the rare-event indicator function within this identified eigen-basis.
  4. Biased Simulation: Use the resulting approximation to bias a new, highly efficient importance sampling simulation.

Experimental Evaluation

The framework was evaluated across several classic dynamical "stress-test" systems:

  • Ornstein-Uhlenbeck (OU) Process: A fundamental linear stochastic model.
  • Non-normal Linear Systems: 2D systems exhibiting transient growth where states deviate from equilibrium before returning.
  • Brownian Oscillator: A system characterized by complex eigenvalues and rank-deficient noise.
  • Van der Pol & Duffing Oscillators: Nonlinear systems used to model limit cycles and transitions between stable basins of attraction.
  • Stochastic Advection-Diffusion: An infinite-dimensional PDE system representing fluid flow.

Key Insights and Results

A primary finding of this work is the ability to "learn from the commonplace." Bulk trajectories contain sufficient global information about the Koopman operator to allow the model to extrapolate into the tails of the distribution, meaning rare events do not need to be observed in the training data. Furthermore, unlike many existing methods that are restricted to gradient systems (sliding down an energy landscape), this Koopman-based approach is agnostic to the system type, effectively handling oscillatory and non-normal dynamics.

Performance Gains

The framework demonstrated substantial variance reduction across all test cases:

  • Duffing Oscillator: The IS estimator reduced variance by a factor of nearly 5,000 compared to simple Monte Carlo.
  • Van der Pol Oscillator: In scenarios involving escape from a limit cycle, the method achieved a variance reduction factor of over 400.
  • Non-normal Systems: The approach successfully identified the "slowest-decaying left eigenvector," which represents the optimal direction to trigger a rare escape.

Limitations and Future Directions

While powerful, the method faces the "curse of dimensionality," as gEDMD requires a predefined basis that grows exponentially with the number of state variables. Future research may integrate neural networks or kernel methods to handle higher-dimensional spaces. Additionally, the current requirement for eigenfunction gradients to determine the biasing "push" can be difficult to satisfy with some data-driven DMD variants. Finally, the authors suggest that combining Koopman-based biasing with Multilevel Splitting could result in a more robust, hybrid rare-event algorithm.

Summary updated

Abstract

Highlights•We develop a systematic framework for computing rare event probabilities in stochastic differential equations.•Stochastic Koopman eigenfunctions are used to develop importance sampling estimators.•Stochastic Koopman eigenfunctions are computed using dynamic mode decomposition.•Non-rare trajectories are used to inform how rare events occur.•Even crude approximations of eigenfunctions can yield efficient estimators.
BibTeX
@article{zhang2022koopman,
  author = {Benjamin J. Zhang and Tuhin Sahai and Youssef M. Marzouk},
  title = {{A Koopman framework for rare event simulation in stochastic differential equations}},
  journal = {Journal of Computational Physics},
  year = {2022},
  doi = {10.1016/j.jcp.2022.111025},
}
Figure