Random Coordinate Underdamped Langevin Monte Carlo

• URL: http://arxiv.org/abs/2010.11366v1
• Date: Thu, 22 Oct 2020 01:12:13 GMT
• Title: Random Coordinate Underdamped Langevin Monte Carlo
• Authors: Zhiyan Ding and Qin Li and Jianfeng Lu and Stephen J. Wright
• Abstract summary: Underdamped Langevin Monte Carlo (ULMC) is a popular Markov chain Monte Carlo sampling method. We propose a sampling method called Random Coordinate ULMC (RC-ULMC), which selects a single coordinate at each iteration to be updated and leaves the other coordinates untouched. We show that RC-ULMC is always cheaper than the classical ULMC, with a significant cost reduction when the problem is highly skewed and high dimensional.
• Score: 20.423417125810868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Underdamped Langevin Monte Carlo (ULMC) is a popular Markov chain Monte Carlo sampling method. It requires the computation of the full gradient of the log-density at each iteration, an expensive operation if the dimension of the problem is high. We propose a sampling method called Random Coordinate ULMC (RC-ULMC), which selects a single coordinate at each iteration to be updated and leaves the other coordinates untouched. We investigate the computational complexity of RC-ULMC and compare it with the classical ULMC for strongly log-concave probability distributions. We show that RC-ULMC is always cheaper than the classical ULMC, with a significant cost reduction when the problem is highly skewed and high dimensional. Our complexity bound for RC-ULMC is also tight in terms of dimension dependence.

Related papers

• AutoStep: Locally adaptive involutive MCMC [51.186543293659376]
  We present a novel class of involutive MCMC methods -- AutoStep MCMC -- that selects an appropriate step size at each iteration adapted to the local geometry of the target distribution.<n>We show that AutoStep MCMC is competitive with state-of-the-art methods in terms of effective sample size per unit cost on a range of challenging target distributions.
  arXiv  Detail & Related papers  (2024-10-24T17:17:11Z)
• SMC Is All You Need: Parallel Strong Scaling [0.695967916921061]
  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.
  arXiv  Detail & Related papers  (2024-02-09T04:13:38Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  Diffusion-based Monte Carlo (DMC) is a method to sample from a general target distribution beyond the isoperimetric condition. DMC encountered high gradient complexity, resulting in an exponential dependency on the error tolerance $epsilon$ of the obtained samples. We propose RS-DMC, based on a novel recursion-based score estimation method. Our algorithm is provably much faster than the popular Langevin-based algorithms.
  arXiv  Detail & Related papers  (2024-01-12T02:33:57Z)
• On the Parallel Complexity of Multilevel Monte Carlo in Stochastic Gradient Descent [0.8158530638728501]
  In neural differential equations, the Multilevel Carlo (MLMC) method is known to offer better theoretical complexity than the naive Monte Carlo approach. We propose a delayed gradient estimator that drastically reduces the parallel complexity of sequentialC recycling by previously computed components. The proposed estimator provably reduces the average parallel complexity per gradient at the cost of a slightly worse periteration convergence rate.
  arXiv  Detail & Related papers  (2023-10-03T19:53:12Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
  arXiv  Detail & Related papers  (2023-01-28T04:12:56Z)
• Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions [0.0]
  We prove finite sample complexities for sequential Monte Carlo (SMC) algorithms which require only local mixing times of the associated kernels. Our bounds are particularly useful when the target distribution is multimodal and global mixing of the kernel is slow.
  arXiv  Detail & Related papers  (2022-08-13T15:06:03Z)
• Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
  We describe a pipeline approach to decoding the surface code using minimum weight perfect matching. An independent no-communication parallelizable processing stage reweights the graph according to likely correlations. A later general stage finishes the matching. We validate the new algorithm on the fully fault-tolerant toric, unrotated, and rotated surface codes.
  arXiv  Detail & Related papers  (2022-05-19T19:58:02Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) considers the setting where the agent does not have access to a reward function during exploration. We show that this separation does not exist in the setting of linear MDPs. We develop a computationally efficient algorithm for reward-free RL in a $d$-dimensional linear MDP.
  arXiv  Detail & Related papers  (2022-01-26T22:09:59Z)
• Random Coordinate Langevin Monte Carlo [20.423417125810868]
  Langevin Monte Carlo (LMC) is a popular Markov chain Monte Carlo sampling method. We propose a new sampling method: Random Coordinate LMC.
  arXiv  Detail & Related papers  (2020-10-03T18:18:11Z)
• On Thompson Sampling with Langevin Algorithms [106.78254564840844]
  Thompson sampling for multi-armed bandit problems enjoys favorable performance in both theory and practice. It suffers from a significant limitation computationally, arising from the need for samples from posterior distributions at every iteration. We propose two Markov Chain Monte Carlo (MCMC) methods tailored to Thompson sampling to address this issue.
  arXiv  Detail & Related papers  (2020-02-23T22:35:29Z)

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.