Adaptive power method for estimating large deviations in Markov chains

Abstract

We study the performance of a stochastic algorithm based on the power method that adaptively learns the large deviation functions characterizing the fluctuations of additive functionals of Markov processes, used in physics to model nonequilibrium systems. This algorithm was introduced in the context of risk-sensitive control of Markov chains and was recently adapted to diffusions evolving continuously in time. Here we provide an in-depth study of the convergence of this algorithm close to dynamical phase transitions, exploring the speed of convergence as a function of the learning rate and the effect of including transfer learning. We use as a test example the mean degree of a random walk on an Erdös-Rényi random graph, which shows a transition between high-degree trajectories of the random walk evolving in the bulk of the graph and low-degree trajectories evolving in dangling edges of the graph. The results show that the adaptive power method is efficient close to dynamical phase transitions, while having many advantages in terms of performance and complexity compared to other algorithms used to compute large deviation functions.

arXiv commentv1: 12 pages, 7 figures; v2: typos corrected, references updated, close to published version

References in corpus (50)

• The large deviation approach to statistical mechanics
• Dynamical Ensembles in Nonequilibrium Statistical Mechanics
• A Gallavotti-Cohen Type Symmetry in the Large Deviation Functional for Stochastic Dynamics
• Fluctuation theorem for stochastic dynamics
• Thermodynamic uncertainty relation for biomolecular processes
• Non equilibrium steady states: fluctuations and large deviations of the density and of the current
• Dissipation bounds all steady-state current fluctuations
• Macroscopic fluctuation theory
• Dynamic first-order phase transition in kinetically constrained models of glasses
• Fluctuation theorems for stochastic dynamics
• First-order dynamical phase transition in models of glasses: an approach based on ensembles of histories
• Direct evaluation of large-deviation functions
• Nonequilibrium Markov processes conditioned on large deviations
• Thermodynamics of Quantum Jump Trajectories
• Universal bounds on current fluctuations
• Nonequilibrium microcanonical and canonical ensembles and their equivalence
• Quantifying dissipation using fluctuating currents
• Stochastic interacting particle systems out of equilibrium
• Introduction to dynamical large deviations of Markov processes
• Inferring dissipation from current fluctuations
• A numerical approach to large deviations in continuous-time
• Variational and optimal control representations of conditioned and driven processes
• Stochastic thermodynamics: From principles to the cost of precision
• Population dynamics method with a multi-canonical feedback control
• A minimal model of dynamical phase transition
• Dynamical phase transition for current statistics in a simple driven diffusive system
• Using matrix product states to study the dynamical large deviations of kinetically constrained models
• DMRG-study of current and activity fluctuations near non-equilibrium phase transitions
• Exact fluctuations of nonequilibrium steady states from approximate auxiliary dynamics
• Generic Dynamical Phase Transition in One-Dimensional Bulk-Driven Lattice Gases with Exclusion
• Rare behavior of growth processes via umbrella sampling of trajectories
• Importance sampling large deviations in nonequilibrium steady states. I
• A reinforcement learning approach to rare trajectory sampling
• Adaptive sampling of large deviations
• Learning nonequilibrium control forces to characterize dynamical phase transitions
• Sampling rare events across dynamical phase transitions
• Reinforcement learning of rare diffusive dynamics
• Large deviations of random walks on random graphs
• Cusp singularities in boundary-driven diffusive systems
• Optimal sampling of dynamical large deviations via matrix product states
• Variational design principles for nonequilibrium colloidal assembly
• Dynamical large deviations of two-dimensional kinetically constrained models using a neural-network state ansatz
• A Deep Learning Functional Estimator of Optimal Dynamics for Sampling Large Deviations
• Application of importance sampling to the computation of large deviations in non-equilibrium processes
• Constructing Auxiliary Dynamics for Nonequilibrium Stationary States by Variance Minimization
• On a new class of score functions to estimate tail probabilities of some stochastic processes with Adaptive Multilevel Splitting
• Rare event simulation for stochastic dynamics in continuous time
• Efficient large deviation estimation based on importance sampling
• Delocalization-localization dynamical phase transition of random walks on graphs
• Maximal dispersion of adaptive random walks

Cited by in corpus (5)

• Dynamical large deviations of linear diffusions
• Convergence of the Integral Fluctuation Theorem estimator for nonequilibrium Markov systems
• Understanding random-walk dynamical phase coexistence through waiting times
• Making rare events typical in $d$-dimensional chaotic maps
• Self-interacting processes via Doob conditioning