Particle exchange Monte Carlo methods for eigenfunction and related nonlinear problems
Paul Dupuis, Benjamin J. Zhang · 2025
Read Particle exchange Monte Carlo methods for eigenfunction and related nonlinear problems by Paul Dupuis, Benjamin J. Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23456.txt.
Introduction
Paul Dupuis and Benjamin J. Zhang introduce a Monte Carlo method for eigenvalue problems where the key value is not known in advance, in a 2025 paper. Existing particle exchange methods handle cases where that value is already given, such as averages under a Gibbs measure. Many real problems, though, ask for both the eigenfunction and its unknown eigenvalue at once.
The new method derives its exchange rule from a pair of processes, one running forward in time and the other backward. The authors develop the theory and show how it applies to two problem families: distributions of long-lived states in systems that eventually get absorbed, and optimal control of systems with ongoing costs. Both settings need the eigenvalue found, not assumed.
Catalog record
| CREATOR | Paul Dupuis, Benjamin J. Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Particle exchange Monte Carlo methods for eigenfunction and related nonlinear problems Thanks: Division of Applied Mathematics, Brown University. Research supported in part by the the Air Force Office of Scientific Research (FA9550-21-1-0354). Paul Dupuis, Benjamin J. Zhang Abstract We introduce and develop a novel particle exchange Monte Carlo method. Whereas existing methods apply to eigenfunction problems where the eigenvalue is known (e.g., integrals with respect to a Gibbs measure, which can be interpreted as corresponding to eigenvalue zero), here the focus is on problems where the eigenvalue is not known a priori . To obtain an appropriate particle exchange rule we must consider a pair of processes, with one evolving forward in time and the other backward. Applications to eigenfunction problems corresponding to quasistationary distributions and ergodic stochastic control are discussed. Key words. Monte Carlo, nonlinear Markov process, infinite swapping limit, interacting particle systems, eigenvalue problems, ergodic control, quasistationary distributions, replica exchange, Fleming-Viot process AMS subject classifications. 65C05, 65C35, 60K35, 65N25, 93E20 1 Introduction Markov chain Monte Carlo is widely used for approximations in linear problems, such as computing integrals with respect to a Gibbs measure. The method can be effective even when a straightforward implementation suffers from the “rare event sampling problem,” which means that different parts of the state space over which integration takes place do not communicate well under the Markov chain whose stationary distribution is the target measure. Here one can make use of interacting particle methods such as parallel tempering to mitigate the communication problem, by linking the chain responsible for sampling from the target distribution with chains that sample from related distributions which suffer less from rare event issues [ 5 , 12 ] . A simple example is the problem where the target measure is \mu^{\varepsilon}(dx)=\frac{1}{Z_{\varepsilon}}e^{-\frac{2}{\varepsilon}V(x)}dx. Here Z_{\varepsilon} is the normalization constant that makes the measure a probability, V:\mathbb{R}^{d}\rightarrow\mathbb{R} is some smooth potential that tends to \infty as \left\|x\right\|\rightarrow\infty , so as to make Z_{\varepsilon} finite, and \varepsilon is a parameter proportional to temperature in physical models. Let DV(x) denote the gradient of V . One easily checks that the diffusion dX^{\varepsilon}=-DV(X^{\varepsilon})dt+\sqrt{\varepsilon}dW, (1.1) where W is a standard Brownian motion on \mathbb{R}^{d} , is reversible with respect to \mu^{\varepsilon} , and hence the empirical measure \frac{1}{T}\int_{0}^{T}\delta_{X_{t}^{\varepsilon}}(dx)dt converges by the ergodic theorem to \mu^{\varepsilon}(dx) as T\rightarrow\infty . However, when \varepsilon>0 is small and V has multiple local minima, it takes X_{t}^{\varepsilon} a long time to move between the local minima, and so convergence is slow. In the most common formulation of particle exchange Monte Carlo methods, temperature is used to identify the dynamics of the other particle system. For example, if there are only two particles, one would take \tau>\varepsilon and dynamics dX^{\tau}=-DV(X^{\tau})dt+\sqrt{2\tau}d\bar{W} , with the corresponding stationary distribution \mu^{\tau} , and Brownian motion \bar{W} independent of W . The distribution \mu^{\tau} is “flatter,” and the higher diffusivity of X^{\tau} allows it to wander around the state space more easily. The stationary distribution of the pair (X^{\varepsilon},X^{\tau}) is of course the product measure. Then additional randomness is introduced by allowing the particles to swap locations at random times. A Metropolis–type swap mechanism between the higher and lower temperature dynamics that preserves the invariant distribution is used. One intuitively expects that the higher temperature dynamics, linked to those of the lower temperature in this way, to speed up the convergence of the low temperature marginal of the empirical measure. This expectation is true, and rigorous statements regarding the improvement can be made [ 3 , 4 ] . We previously remarked that the problems to which such parallel tempering methods apply are linear , and that the methods exploit a reversibility structure. By linear, we mean that the algorithms compute approximations to the solution to the eigenfunction problem -\mathcal{L}^{\varepsilon,\ast}\rho^{\varepsilon}(x)=0\text{ for }x\in\mathbb{R}^{d}, (1.2) where \mathcal{L}^{\varepsilon,\ast} is the adjoint of the generator of X^{\varepsilon} , and \rho^{\varepsilon}(x) is normalized to be a probability density. Although an eigenfunction problem, it is linear since the eigenvalue is known. Among several goals of the the present paper, perhaps the most important is to introduce a computational approach to a class of nonlinear problems that in some sense generalizes parallel tempering. Although the class of nonlinear problems that can be so treated is more general (as will be discussed later), to connect most directly to the previous discussion we use as an example an eigenfunction problem of the form -\mathcal{L}^{\varepsilon,\ast}\psi^{\varepsilon}(x)+c(x)\psi^{\varepsilon}(x)=\lambda^{\varepsilon}\psi^{\varepsilon}(x)\text{ for }x\in\mathbb{R}^{d}, (1.3) where c:\mathbb{R}^{d}\rightarrow[0,\infty) . Under suitable conditions, there will be a real-valued eigenvalue with the largest real part among all eigenvalues, and the eigenfunction of interest is positive, unique up to a multiplicative constant, and corresponds to this largest eigenvalue. Our interest is to approximate \lambda^{\varepsilon} and \psi^{\varepsilon} through Monte Carlo methods. The most straightforward stochastic interpretation for (\psi^{\varepsilon}(\cdot),\lambda^{\varepsilon}) that might serve as a basis for Monte Carlo is the following. Under appropriate conditions one has, for any initial condition X_{0}^{\varepsilon} , \psi^{\varepsilon}(x)dx=\lim_{T\rightarrow\infty}\frac{Ee^{-\int_{0}^{T}c(X_{t}^{\varepsilon})dt}1_{\{dx\}}(X_{T}^{\varepsilon})}{Ee^{-\int_{0}^{T}c(X_{t}^{\varepsilon})dt}} (1.4) and \lambda^{\varepsilon}=-\lim_{T\rightarrow\infty}\frac{1}{T}\log Ee^{-\int_{0}^{T}c(X_{t}^{\varepsilon})dt}. One can interpret the discounting term e^{-c(X_{t}^{\varepsilon})} as killing of the process at rate c(X_{t}^{\varepsilon}) , and thus \psi^{\varepsilon}(x)dx is the asymptotic (as T\rightarrow\infty ) limit of the distribution of X_{T}^{\varepsilon} , conditioned on not having been killed by time T . Also, the eigenvalue is the asymptotic killing rate, conditioned on survival. Although this is perhaps the simplest stochastic representation, we will use as the starting point a representation in terms of a closely related process that does not die out. In probability, \psi^{\varepsilon}(x)dx is called the quasi-stationary distribution for these dynamics with killing rate c(x) . 1 1 1 More precisely, this is “soft” killing, to be contrasted with the case of “hard” killing, in which the process is killed the first time it exits a given set. Stochastic methods used to solve eigenfunction problems of this sort generally suffer from the same difficulties as those used for stationary distributions when there is a rare event sampling problem. Hence one may ask if there is any analogue to parallel tempering for Monte Carlo schemes that might be used for their approximation. It turns out that this is possible, and the key insight needed to make this work is that one cannot use just the process X_{t}^{\varepsilon}\penalty\ and qualitatively similar processes, such as the higher temperature variants used in parallel tempering’s most common implementation. Rather, there is a “dual” dynamic based on time reversal that must be first linked to the original dynamic, and one can then work with the forward/backward pair to obtain a reversibility structure and a consistent Metropolis type swapping rule. In fact, once one understands how to swap the forward/backward pair one can then couple to other forward/backward pairs that are related to the first one, for example by a change in a temperature parameter. The main task of the paper is to elucidate the structure of the forward/backward pair, and show how it is used in developing the analogue of parallel tempering for nonlinear problems. To illustrate the ideas we focus on a diffusion model. However, the approach generalizes without difficulty, and in particular can also be used for countable state and finite state jump Markov processes. We conclude this introduction by mentioning various issues and objects that will be needed for or which will appear