Particle-MALA and Particle-mGRAD: Gradient-based MCMC methods for high-dimensional state-space models

• URL: http://arxiv.org/abs/2401.14868v1
• Date: Fri, 26 Jan 2024 13:52:40 GMT
• Title: Particle-MALA and Particle-mGRAD: Gradient-based MCMC methods for high-dimensional state-space models
• Authors: Adrien Corenflos and Axel Finke
• Abstract summary: State-of-the-art methods for Bayesian inference in state-space models are conditional sequential Monte Carlo (CSMC) algorithms. We introduce methods which combine the strengths of both approaches. We prove that Particle-mGRAD interpolates between CSMC and Particle-MALA, resolving the 'tuning problem' of choosing between CSMC and Particle-MALA.
• Score: 3.3489861768576197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-of-the-art methods for Bayesian inference in state-space models are (a) conditional sequential Monte Carlo (CSMC) algorithms; (b) sophisticated 'classical' MCMC algorithms like MALA, or mGRAD from Titsias and Papaspiliopoulos (2018, arXiv:1610.09641v3 [stat.ML]). The former propose $N$ particles at each time step to exploit the model's 'decorrelation-over-time' property and thus scale favourably with the time horizon, $T$ , but break down if the dimension of the latent states, $D$, is large. The latter leverage gradient-/prior-informed local proposals to scale favourably with $D$ but exhibit sub-optimal scalability with $T$ due to a lack of model-structure exploitation. We introduce methods which combine the strengths of both approaches. The first, Particle-MALA, spreads $N$ particles locally around the current state using gradient information, thus extending MALA to $T > 1$ time steps and $N > 1$ proposals. The second, Particle-mGRAD, additionally incorporates (conditionally) Gaussian prior dynamics into the proposal, thus extending the mGRAD algorithm to $T > 1$ time steps and $N > 1$ proposals. We prove that Particle-mGRAD interpolates between CSMC and Particle-MALA, resolving the 'tuning problem' of choosing between CSMC (superior for highly informative prior dynamics) and Particle-MALA (superior for weakly informative prior dynamics). We similarly extend other 'classical' MCMC approaches like auxiliary MALA, aGRAD, and preconditioned Crank-Nicolson-Langevin (PCNL) to $T > 1$ time steps and $N > 1$ proposals. In experiments, for both highly and weakly informative prior dynamics, our methods substantially improve upon both CSMC and sophisticated 'classical' MCMC approaches.

Related papers

• Enhanced SMC$^2$: Leveraging Gradient Information from Differentiable Particle Filters Within Langevin Proposals [41.95156859549931]
  Sequential Monte Carlo Squared (SMC$2$) is a Bayesian method which can infer the states and parameters of non-linear, non-Gaussian state-space models. Standard random-walk proposal in SMC$2$ faces challenges, particularly with high-dimensional parameter spaces. This study outlines a novel approach by harnessing first-order gradients derived from a Common Random Numbers - Particle Filter (CRN-PF) using PyTorch.
  arXiv  Detail & Related papers  (2024-07-24T14:05:44Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Quantum Speedups for Multiproposal MCMC [8.580097282861725]
  We present a new, faster quantum multiproposal MCMC strategy, QPMCMC2. QPMCMC2 requires only $mathcalO(P)$ target evaluations and $mathcalO(log P)$ qubits when computing over a large number of proposals $P$. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks.
  arXiv  Detail & Related papers  (2023-12-03T14:05:08Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• De-Sequentialized Monte Carlo: a parallel-in-time particle smoother [3.97478982737167]
  We propose dSMC (de-Sequentialized Monte Carlo), a new particle smoother that is able to process $T$ observations in $mathcalO(log T)$ time. This compares favourably with standard particle smoothers, the complexity of which is linear in $T$. We also design a particle Gibbs sampler based on dSMC, which is able to perform parameter inference in a state-space model at a $mathcalO(log(T))$ cost on parallel hardware.
  arXiv  Detail & Related papers  (2022-02-04T17:46:32Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC) methods for sampling from an $L$-smooth and $m$-strongly log-concave distribution. We show that the unbiased gradient estimators, including SAGA and SVRG, based HMC methods achieve highest gradient efficiency with small batch size. Experimental results on both synthetic and real-world benchmark data show that our new framework significantly outperforms the full gradient and gradient HMC approaches.
  arXiv  Detail & Related papers  (2021-02-09T02:44:24Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  In this paper, we study reinforcement learning for discounted Decision (MDP) We propose a novel algorithm that makes use of the feature mapping and obtains a $tilde O(dsqrtT/ (1-gamma)2)$ regret. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $ (1-gamma)-0.5$ factor.
  arXiv  Detail & Related papers  (2020-06-23T17:08:54Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• Generally covariant $N$-particle dynamics [0.10427337206896375]
  A simultaneous description of the dynamics of multiple particles requires a configuration space approach with an external time parameter. Here we show, however, that the two attitudes toward modelling $N$-particle dynamics can be conciliated within a generally covariant framework. The dynamics of multi-particle systems is modelled at the level of Borel probability measures over $mathcalM_scriptscriptstyle (N)$ with the help of the global time parameter.
  arXiv  Detail & Related papers  (2020-04-15T11:27:18Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)
• Newtonian Monte Carlo: single-site MCMC meets second-order gradient methods [1.6042895233470602]
  Single-site Markov Chain Monte Carlo (MCMC) is a variant of MCMC in which a single coordinate in the state space is modified in each step. Newtonian Monte Carlo (NMC) is a method to improve MCMC convergence by analyzing the first and second order gradients of the target density. NMC is similar to the Newton-Raphson update in optimization where the second order gradient is used to automatically scale the step size in each dimension.
  arXiv  Detail & Related papers  (2020-01-15T21:40:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.