PaperlayerView exact revision on arXiv

Source-linked AI summary

Numerical computation of rare events via large deviation theory

Tobias Grafke, Eric Vanden-Eijnden

arXiv:1812.00681v1cond-mat.stat-mech

TL;DR

Rare-event analysis quantifies the likelihood of extreme observable values and can characterize the most likely configuration or evolution into an extreme event. The review surveys algorithms that compute large-deviation minimizers, including a simplified geometric minimum action method and connections to optimal control and importance sampling. The review presents two algorithm categories: global rate-function minimization, including a simplified gMAM with reduced derivative requirements, and instanton-equation methods interpreted through adjoint optimization.

  • Problem

    Rare-event analysis quantifies the likelihood of extreme observable values and can characterize the most likely configuration or evolution into an extreme event.

    Source: A. Instantons for expectations and… · p. 9

  • Method

    The review surveys algorithms that compute large-deviation minimizers, including a simplified geometric minimum action method and connections to optimal control and importance sampling.

    Source: A. A simplified geometric minimum… · p. 5, D. Connections to optimal control · p. 13, §VII · p. 22

  • Results

    The review presents two algorithm categories: global rate-function minimization, including a simplified gMAM with reduced derivative requirements, and instanton-equation methods interpreted through adjoint optimization.

    Source: §VII · p. 22

  • Takeaways & Limitations

    The minimizing trajectories characterize rare-event pathways and can be used to estimate event probabilities and properties.

    Source: §VII · p. 22

Abstract

from arXiv · show

An overview of rare events algorithms based on large deviation theory (LDT) is presented. It covers a range of numerical schemes to compute the large deviation minimizer in various setups, and discusses best practices, common pitfalls, and implementation trade-offs. Generalizations, extensions, and improvements of the minimum action methods are proposed. These algorithms are tested on example problems which illustrate several common difficulties which arise e.g. when the forcing is degenerate or multiplicative, or the systems are infinite-dimensional. Generalizations to processes driven by non-Gaussian noises or random initial data and parameters are also discussed, along with the connection between the LDT-based approach reviewed here and other methods, such as stochastic field theory and optimal control. Finally, the integration of this approach in importance sampling methods using e.g. genealogical algorithms is explored.

I. INTRODUCTION

The review uses large deviation theory to identify the least unlikely trajectories that realize rare events, turning their computation into an action-minimization problem. It develops this framework for low-noise dynamics and outlines its extensions and links to importance sampling.

I. INTRODUCTION

  • LDT-based computation minimizes the action over paths realizing an event, while importance sampling instead makes rare events more likely through controlled system manipulation.The review focuses mainly on action minimization and discusses its interplay with importance sampling later.Source: §I · p. 2, A. Freidlin-Wentzell theory of large… · p. 3
  • The review covers action-minimization algorithms, rare-expectation tail statistics, non-Gaussian noise, random initial data and parameters, and importance-sampling connections.It focuses on low-amplitude-noise Freidlin-Wentzell theory in the section's background discussion.Source: §I · p. 2

A. Freidlin-Wentzell theory of large deviations

  • For small-noise dynamics, LDT gives a log-asymptotic estimate of path probabilities through an action functional; the least-action admissible path dominates the event probability.The setup assumes additive Gaussian white noise for simplicity, while noting that multiplicative noise is discussed through examples.Source: A. Freidlin-Wentzell theory of large… · pp. 2–3
  • The least-action path is the instanton: in the low-noise limit, conditioned paths concentrate near it, and it characterizes how the rare event occurs.The minimizer can also support estimates of event probabilities, recurrence times, and relative likelihoods of stable states.Source: A. Freidlin-Wentzell theory of large… · p. 3
  • Minimizing over transition time yields the quasipotential, which characterizes long-time behavior and supports estimates of transition times and rates between stable states.For multiple stable fixed points, the resulting rates can describe long-time dynamics as a Markov jump process.Source: A. Freidlin-Wentzell theory of large… · p. 3

B. Hamiltonian principle and connections to classical mechanics and field theory

The action-minimization problem can be formulated through Euler–Lagrange or Hamiltonian equations, connecting instantons to classical mechanics and stochastic field theory. In detailed balance, the minimizing paths simplify to deterministic or time-reversed dynamics.

B. Hamiltonian principle and connections to classical mechanics and field theory

  • The conjugate momentum and Hamiltonian arise from the Lagrangian formulation, and the Hamiltonian is conserved along a minimizing trajectory.When a path starts at rest at a deterministic fixed point over infinite time, the Hamiltonian vanishes and the action can be rewritten using the Maupertuis principle.Source: B. Hamiltonian principle and… · pp. 3–4
  • The action minimizer satisfies Hamilton’s equations, also called instanton equations; solving them requires boundary conditions suited to the rare event.The variational problem also yields a second-order Euler–Lagrange equation, which algorithms can solve.Source: B. Hamiltonian principle and… · pp. 3–4
  • In stochastic field theory, the conjugate momentum corresponds to an auxiliary field, and the instanton is the saddle-point approximation of the action functional.The passage also notes that the Doi-Peliti formalism follows a similar route for dominant reaction pathways.Source: B. Hamiltonian principle and… · p. 4

C. Detailed balance and gradient flows

  • In detailed-balance potential diffusions, minimizers between adjacent minima can be built from deterministic downhill and time-reversed uphill paths meeting at a minimum-potential saddle.This time-reversal symmetry follows from the process being in detailed balance.Source: C. Detailed balance and gradient flows · p. 4
  • For gradient flows, these minimizers are heteroclinic orbits and are numerically accessible with the string method.For general detailed-balance systems, they are heteroclinic orbits of an associated generalized gradient flow, not necessarily a traditional gradient flow.Source: C. Detailed balance and gradient flows · p. 4

II. RARE EVENT ALGORITHMS FOR NOISE-INDUCED TRANSITIONS

For noise-induced transitions, the review computes minimum-action paths between stable states and uses minimization over transition time to obtain the quasipotential. Its simplified geometric method works with reparametrized curves, including when transition times diverge.

II. RARE EVENT ALGORITHMS FOR NOISE-INDUCED TRANSITIONS

  • The instanton is the maximum-likelihood transition path between deterministically stable states; minimizing over transition time gives the quasipotential.The minimum action method discretizes the action and uses its finite-dimensional gradient in numerical minimization.Source: §II · pp. 4–5

A. A simplified geometric minimum action method

  • The simplified geometric minimum action method minimizes over arc-length-parametrized curves, allowing finite representations when the minimizing transition time diverges.The action is invariant under reparametrization, so a path with an infinite physical-time interval can be represented with finitely many discretization points.Source: A. A simplified geometric minimum… · p. 5
  • The geometric method nests an inner constrained optimization for the momentum with an outer path minimization, iterating through descent directions until convergence.For small-noise Gaussian SDEs, the inner momentum optimization can be solved analytically.Source: A. A simplified geometric minimum… · pp. 5–6
  • The arc-length Lagrange multiplier corresponds to the change from physical time to arc-length parametrization.The passage identifies μ = dt/ds.Source: A. A simplified geometric minimum… · p. 5
  • Arc length is enforced by interpolation to avoid stiff parametrization terms, while preconditioning is needed for good convergence and norm choice trades simplicity against derivative cost.Preconditioning by μ^-1 supports convergence around fixed points; using the Hamiltonian Hessian can help but requires higher derivatives.Source: A. A simplified geometric minimum… · p. 6

B. Example: Metastability in a simple climate model

The review illustrates minimum-action methods on a metastable climate model and on stochastic partial differential equations. The climate transitions reveal broken time-reversal symmetry and unequal actions, while the SPDE discussion notes mathematical caveats and demonstrates an asymmetric nucleation pathway.

B. Example: Metastability in a simple climate model

  • The climate example applies the algorithm to a six-mode projection of the barotropic vorticity equation with additive Gaussian noise and two metastable states.Those states are called zonal and blocked configurations.Source: B. Example: Metastability in a simple… · pp. 6–7
  • The action toward the blocked climate state is much larger than toward the zonal state, so the zonal state is exponentially preferred in the low-noise limit.The backward transition is not the time reversal of the forward transition, indicating broken time-reversal symmetry and non-equilibrium behavior.Source: B. Example: Metastability in a simple… · p. 7, Figure 2 · p. 7, Figure 1 · p. 7

C. Instantons for stochastic partial differential equations

  • Applying finite-dimensional action minimization to SPDEs is done in practice, but its mathematical foundation is less clear.The discussion proceeds by assuming the proposed rate function is valid; nonlinear terms with rough noise can require renormalization.Source: C. Instantons for stochastic partial… · p. 8
  • When the rate function has the assumed SPDE form, the finite-dimensional descent approach transfers by replacing vector gradients with functional derivatives.For SPDEs, high spatial derivatives can impose CFL time-step limits on descent and slow convergence.Source: C. Instantons for stochastic partial… · p. 8
  • The bi-stable Burgers-Huxley model transitions from u = −1 to u = 1 through Allen-Cahn-like nucleation, with the critical nucleus forming as a steepening, asymmetric shock wave.Source: Figure 3 · p. 8

D. Example: The stochastic Burgers-Huxley equation

This section presents instanton methods for expectations and extreme events, then illustrates their use in a stochastic Burgers-Huxley model. In that example, the computed nucleation is spatially asymmetric and travels.

D. Example: The stochastic Burgers-Huxley equation

  • For small enough κ, the Burgers-Huxley numerics show an asymmetric nucleating seed that travels through space.The model combines nonlinear advection, diffusion, and a double-well reaction term; the computation uses Nx = 256 and Ns = 100.Source: D. Example: The stochastic… · pp. 8–9

III. RARE EVENT ALGORITHMS FOR EXPECTATIONS AND EXTREME EVENTS

  • The section reviews instanton equations for cases where the minimizer can be found by integrating coupled equations of motion, including multiplicative-noise and infinite-dimensional examples.It also introduces a geometric variant and discusses connections to other fields and numerical details.Source: §III · p. 9

A. Instantons for expectations and extreme events

  • For extreme observables, the method minimizes a dual problem indexed by λ, replacing fixed endpoint constraints with a terminal momentum condition tied to the observable.The method integrates the trajectory forward and conjugate momentum backward; forward integration of the momentum can be unstable or ill-posed.Source: A. Instantons for expectations and… · pp. 9–10
  • The dual formulation yields the observable value z only after solving for λ, although adjusting λ on the fly can target a desired z.A range of λ values can also cover a range of z values when the full distribution is of interest.Source: A. Instantons for expectations and… · p. 10

B. Example: Extreme concentration of prey in the Lotka-Volterra model

The Lotka-Volterra example applies instanton equations to rare high-prey events in a stochastic predator-prey model. Monte Carlo trajectories cluster around the predicted instanton, while event duration changes the likely route and predator concentration at the endpoint.

B. Example: Extreme concentration of prey in the Lotka-Volterra model

  • For T = 10, trajectories cluster around the instanton near a(T) = 0.35; for T = 1, the likely route differs and reaches the event at higher predator concentration.Some states, including (a, b) = (0.25, 0.3), are almost never visited at T = 10 but are likely at T = 1.Source: Figure 4 · p. 11, B. Example: Extreme concentration of… · p. 11
  • The example uses multiplicative Gaussian noise, but the authors caution that this approximation need not preserve large-deviation behavior of the underlying Poisson reaction process.The Gaussian model is treated as given here; the paper discusses correct treatment of non-Gaussian systems separately.Source: B. Example: Extreme concentration of… · p. 11
  • The model starts at a unique predator-prey fixed point and targets high final prey concentration regardless of the predator concentration.The migration reactions prevent forcing degeneracy at extinct population levels and avoid absorbing-boundary difficulties.Source: B. Example: Extreme concentration of… · pp. 10–11

C. Example: Extreme amplitudes in the Korteweg-de Vries equation

The Korteweg-de Vries example shows how instanton equations handle degenerate forcing and identify a likely way to form an extreme wave amplitude. The optimal-control connection recasts the iterative instanton algorithm as gradient descent and suggests practical improvements.

C. Example: Extreme amplitudes in the Korteweg-de Vries equation

  • Hamilton’s-equation methods treat degenerate forcing without extra effort because they never invert the noise correlation.By contrast, global-minimization methods face stiff constraints for unforced modes.Source: C. Example: Extreme amplitudes in the… · p. 12
  • With forcing restricted to the largest mode, nonlinear advection and dispersion produce a high amplitude near the origin while cascading energy into higher modes.The rest of the waveform is unconstrained and takes its most likely form.Source: C. Example: Extreme amplitudes in the… · p. 12

D. Connections to optimal control

  • The conjugate momentum is the optimal-control adjoint variable, making the instanton iteration gradient descent on the control cost.Line search, preconditioning, nonlinear conjugate gradient, and quasi-Newton methods are proposed to improve stability or convergence.Source: D. Connections to optimal control · p. 13

E. Improvements and implementation considerations

The section discusses implementation choices for Hamiltonian instanton methods, their geometric-time extension, and examples involving stochastic Burgers and non-Gaussian processes. It also outlines how a WKB approximation yields large-deviation Hamiltonians for Markov jump processes.

E. Improvements and implementation considerations

  • The forward and adjoint equations require storing the trajectory, while available forward solvers and adjoints can make the outer instanton computation nearly black-box.For many-dimensional SPDEs, storing the full trajectory can be prohibitive.Source: E. Improvements and implementation… · p. 13
  • Checkpointing can reduce trajectory-storage requirements from O(Nt) to O(log Nt) for instanton computations.It retains checkpoints rather than the full trajectory, reconstructing later states as needed.Source: E. Improvements and implementation… · p. 13
  • The adjoint integrator must match the forward integrator’s adjoint; using an incorrect pair generally prevents convergence to the minimum cost.Selfadjoint time integrators can serve both equations.Source: E. Improvements and implementation… · p. 13

F. Geometric version of the Hamilton’s equations

  • The geometric Hamiltonian formulation reparametrizes trajectories, avoiding explicit minimization over duration when computing long-time quantities such as the quasi-potential.Its simpler multiplier expression applies only to Gaussian additive noise.Source: F. Geometric version of the Hamilton’s… · p. 14

G. Example: Extreme gradients of the stochastic Burgers equation

  • The geometric Burgers example targets strong negative gradients at the origin under spatially correlated, white-in-time forcing.The geometric formulation probes the invariant-measure regime by taking T toward infinity.Source: G. Example: Extreme gradients of the… · p. 14
  • Roughly 10^4 times greater accuracy in max(|H|) is obtained by the geometric variant than by physical-time parametrization at the same time discretization.For T=10 or T=100, the instanton has unphysical secondary maxima; they disappear for T=1000 and in the infinite-time geometric limit.Source: G. Example: Extreme gradients of the… · p. 14, Figure 6 · p. 14

IV. GENERALIZATIONS TO THE NON-GAUSSIAN CASE

  • For non-Gaussian processes such as limits of Markov jump processes, the large-deviation Hamiltonian is generally non-quadratic in conjugate momentum.The algorithms are formulated using a generic large-deviation Hamiltonian.Source: §IV · p. 15

A. Large deviation principles as WKB approximation

  • A WKB approximation of the rescaled Markov-jump generator yields a Hamilton-Jacobi equation and the large-deviation Hamiltonian.The rate function is the time integral of the Hamiltonian’s Fenchel-Legendre transform.Source: A. Large deviation principles as WKB… · p. 15

B. Example: Genetic switch

The genetic-switch example computes an instanton for a transition between protein-dominance states. The following sections extend rare-event optimization to random parameters, using adjoint gradients and an example that identifies an initial condition for an extreme excursion.

B. Example: Genetic switch

V. SYSTEMS WITH RANDOM PARAMETERS AND EXTREME EVENTS

A. Large deviations for systems with random parameters

  • An adjoint formulation avoids the costly parameter Jacobian when computing gradients for random-parameter optimization.The gradient procedure integrates the forward equation, computes the adjoint field, and then evaluates the gradient.Source: A. Large deviations for systems with… · p. 17
  • In the FitzHugh–Nagumo example, the initial condition at the objective minimum yields the maximal excursion in the x-direction before the trajectory decays to a fixed point.The objective jumps across the separatrix, where trajectories begin showing large excursions.Source: Figure 8 · p. 17

B. Example: Optimal excitation of the Fitzhugh-Nagumo model

The example seeks the most likely initial condition for a large excursion in an excitable Fitzhugh–Nagumo system. The minimizer identifies the initial condition whose trajectory achieves the maximal x-excursion.

B. Example: Optimal excitation of the Fitzhugh-Nagumo model

  • The system has a unique fixed point, but small perturbations can trigger large excursions before it returns to steady state.The initial-condition distribution is Gaussian and centered at the fixed point.Source: B. Example: Optimal excitation of the… · p. 18
  • The target event is an initial condition and trajectory producing an excursion at least as large as a specified threshold.The observable is the maximal excursion in the x-component.Source: B. Example: Optimal excitation of the… · p. 18
  • The calculation uses forward and backward equations to obtain the gradient with respect to the initial condition.At the first local maximum, which is necessarily global for these dynamics, the time-dependence term vanishes because the trajectory derivative is zero.Source: B. Example: Optimal excitation of the… · p. 18
  • The trajectory from the minimizing initial condition maximizes the x-excursion before decaying to the fixed point.For Δ = 2, λ = 1, a = 1.1, and ν = 10^-1, the objective has a jump across the separatrix.Source: B. Example: Optimal excitation of the… · p. 18

VI. INSTANTONS AS PART OF OTHER RARE EVENT ALGORITHMS

The section explores instantons as a way to bias rare-event sampling, where naive Monte Carlo can have exponentially increasing relative error as noise decreases. It describes importance-sampling biases based on the instanton and notes that on-the-fly recomputation can address their variance limitations.

A. Instantons for importance sampling

  • For fixed sample size, the naive estimator’s relative error increases exponentially as ε → 0, making rare-event estimation impractical.Importance sampling changes the process so the rare event becomes typical and corrects for the measure change with a Girsanov factor.Source: A. Instantons for importance sampling · pp. 18–19
  • An instanton-based bias steers the sampling dynamics toward the path dominating the expectation.The section describes two candidate biased processes and relates this strategy to stochastic field theory approaches that sample fluctuations around an instanton.Source: A. Instantons for importance sampling · p. 19
  • An instanton bias need not reduce variance and may perform worse than naive sampling as ε → 0.Recomputing the instanton trajectory on-the-fly can achieve optimal variance decay.Source: A. Instantons for importance sampling · p. 19

B. Instantons for cloning algorithms

The section incorporates instanton information into cloning algorithms by using trajectory weights to guide periodic resampling. It describes an estimator based on the resulting particle ensemble and notes both variance caveats and an extension to adaptive multilevel splitting.

B. Instantons for cloning algorithms

  • Genealogical algorithms evolve an ensemble of trajectories and remove or duplicate particles according to ratings favoring the event of interest.The presented approach uses the instanton-informed process requiring the least modification of the drift.Source: B. Instantons for cloning algorithms · p. 19
  • The algorithm evolves particle positions and weights between selection steps, then resamples particles according to accumulated weights.After resampling, the copies have nearly uniform weights, and their values can form an estimator directly or across repeated runs.Source: B. Instantons for cloning algorithms · pp. 19–20
  • The estimator based on resampling may not behave better than direct weighting, though algorithm modifications can systematically improve its variance.The variance and resampling variants are discussed in, with further details referenced in.Source: B. Instantons for cloning algorithms · p. 20
  • Adaptive multilevel splitting can also use instanton dynamics as input for its reaction coordinate.The reaction coordinate rates behaviors across multiple copies to evaluate performance.Source: B. Instantons for cloning algorithms · p. 20

C. Example: Epidemiology and vaccination at birth

The epidemiology example compares naive and cloning estimates of an unusually high infection rate in a vaccination model. The conclusion groups instanton-computation algorithms into global rate-function minimization and Hamilton-equation approaches.

C. Example: Epidemiology and vaccination at birth

  • The vaccination model has disease-free or endemic long-term behavior depending on vaccination rate; its S and I dynamics suffice to determine eradication.The example sets q = 0.1 below the critical rate q* = 0.625, giving an endemic equilibrium (S̄, Ī) = (0.375, 0.175).Source: C. Example: Epidemiology and… · pp. 20–21
  • The stochastic model uses multiplicative Gaussian noise as a large-population approximation, while a reaction-network interpretation would instead yield Poisson noise.The Gaussian formulation uses independent Wiener processes for S and I.Source: C. Example: Epidemiology and… · pp. 20–21
  • The example estimates the probability that the infected fraction reaches at least 20% after T = 100, comparing naive and cloning estimators.The figure shows the logarithm of the (S(t), I(t)) histogram, deterministic streamlines, the instanton, and the infection threshold.Source: C. Example: Epidemiology and… · p. 21, Figure 9 · p. 21
  • At ε = 10−2, naive sampling produced no threshold-reaching samples, while cloning samples tracked the instanton; as ε decreases, naive variance grows and cloning variance remains largely unchanged.At ε = 1, the event is not rare and cloning performs equally or worse than naive sampling.Source: C. Example: Epidemiology and… · pp. 21–22

VII. CONCLUSION

  • The review presents simplified gMAM, which optimizes arc-length-parametrized curves with fewer required Hamiltonian derivatives, reducing runtime or implementation complexity.Global rate-function minimization methods are particularly suited to transition trajectories between two sets or points.Source: §VII · p. 22
  • A second algorithm category solves Hamilton’s or instanton equations; the review interprets these methods through the adjoint formulation of the optimization problem.Source: §VII · p. 22
Loading 1812.00681v1…