SMC Is All You Need: Parallel Strong Scaling

• URL: http://arxiv.org/abs/2402.06173v2
• Date: Sun, 2 Jun 2024 19:19:23 GMT
• Title: SMC Is All You Need: Parallel Strong Scaling
• Authors: Xinzhu Liang, Joseph M. Lukens, Sanjaya Lohani, Brian T. Kirby, Thomas A. Searles, Kody J. H. Law,
• Abstract summary: We develop a fully parallel sequential Monte Carlo (pSMC) method which provably delivers parallel strong scaling. The pSMC converges to infinitesimal accuracy MSE$=O(varepsilon2)$ with a fixed finite time-complexity Cost$=O(1)$ and with no efficiency leakage.
• Score: 0.695967916921061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Bayesian posterior distribution can only be evaluated up-to a constant of proportionality, which makes simulation and consistent estimation challenging. Classical consistent Bayesian methods such as sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC) have unbounded time complexity requirements. We develop a fully parallel sequential Monte Carlo (pSMC) method which provably delivers parallel strong scaling, i.e. the time complexity (and per-node memory) remains bounded if the number of asynchronous processes is allowed to grow. More precisely, the pSMC has a theoretical convergence rate of Mean Square Error (MSE)$ = O(1/NP)$, where $N$ denotes the number of communicating samples in each processor and $P$ denotes the number of processors. In particular, for suitably-large problem-dependent $N$, as $P \rightarrow \infty$ the method converges to infinitesimal accuracy MSE$=O(\varepsilon^2)$ with a fixed finite time-complexity Cost$=O(1)$ and with no efficiency leakage, i.e. computational complexity Cost$=O(\varepsilon^{-2})$. A number of Bayesian inference problems are taken into consideration to compare the pSMC and MCMC methods.

Related papers

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known. Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables. In this paper, we propose a method to divide $U_X(t)$ based on orthogonal series density estimation. Our method achieves the circuit depth and total query complexity scaling as $O(sqrtN)$ and $O(N3/2)$, respectively.
  arXiv  Detail & Related papers  (2024-06-04T01:50:21Z)
• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition [6.872242798058046]
  We prove bounds on the variance of a function $f$ under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm. We show that bounds can be obtained in the truly multi-modal setting, with mixing times that depend on local MCMC dynamics.
  arXiv  Detail & Related papers  (2024-05-29T22:43:45Z)
• Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
  In practical distributed systems, workers typically not homogeneous, and can have highly varying processing times. We introduce a new parallel method Freya to handle arbitrarily slow computations. We show that Freya offers significantly improved complexity guarantees compared to all previous methods.
  arXiv  Detail & Related papers  (2024-05-24T13:33:30Z)
• 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)
• More Quantum Speedups for Multiproposal MCMC [9.09160682938666]
  Multiproposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple proposals at each iteration in order to sample from challenging target distributions more efficiently. Recent work demonstrates the possibility of quadratic quantum speedups for one such multiproposal MCMC algorithm. We present a fast new quantum multiproposal MCMC strategy, QPMCMC2, that only requires $mathcalO(1)$ target evaluations and $mathcalO(log P)$ qubits.
  arXiv  Detail & Related papers  (2023-12-03T14:05:08Z)
• Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators [8.493584276672971]
  gradient descent (SGD) and its variants is essential for machine learning. In this paper, we consider the SGD algorithm that employ the Markov Chain Monte Carlo (MCMC) estimator to compute the gradient. It is shown that MCMC-SGD escapes from saddle points and reaches $(epsilon,epsilon1/4)$ approximate second order stationary points.
  arXiv  Detail & Related papers  (2023-03-19T08:29:49Z)
• 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)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  Monte Carlo Tree Search (MCTS) is computationally expensive as it requires a substantial number of rollouts to construct the search tree. How to design effective parallel MCTS algorithms has not been systematically studied and remains poorly understood. We demonstrate how proposed necessary conditions can be adopted to design more effective parallel MCTS algorithms.
  arXiv  Detail & Related papers  (2020-06-15T21:36:00Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

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.