Single-ensemble multilevel Monte Carlo for discrete interacting-particle methods

To solve problems in domains such as filtering, optimization, and posterior sampling, interacting-particle methods have recently received much attention. These parallelizable and often gradient-free algorithms use an ensemble of particles that evolve in time, based on a combination of well-chosen dynamics and interaction between the particles. For computationally expensive dynamics -- for example, dynamics that solve inverse problems with an expensive forward model -- the cost of attaining a high accuracy quickly becomes prohibitive. We exploit a hierarchy of approximations to this forward model and apply multilevel Monte Carlo (MLMC) techniques, improving the asymptotic cost-to-error relation. More specifically, we use MLMC at each time step to estimate the interaction term within a single, globally-coupled ensemble. This technique was proposed by Hoel et al. in the context of the ensemble Kalman filter; the goal of the present paper is to study its applicability to a general framework of interacting-particle methods. After extending the algorithm and its analysis to a broad set of methods with fixed numbers of time steps, we motivate the application of the method to the class of algorithms with an infinite time horizon, which includes popular methods such as ensemble Kalman algorithms for optimization and sampling. Numerical tests confirm the improved asymptotic scaling of the multilevel approach.