Random Coordinate Langevin Monte Carlo

• URL: http://arxiv.org/abs/2010.01405v1
• Date: Sat, 3 Oct 2020 18:18:11 GMT
• Title: Random Coordinate Langevin Monte Carlo
• Authors: Zhiyan Ding and Qin Li and Jianfeng Lu and Stephen J. Wright
• Abstract summary: Langevin Monte Carlo (LMC) is a popular Markov chain Monte Carlo sampling method. We propose a new sampling method: Random Coordinate LMC.
• Score: 20.423417125810868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Langevin Monte Carlo (LMC) is a popular Markov chain Monte Carlo sampling method. One drawback is that it requires the computation of the full gradient at each iteration, an expensive operation if the dimension of the problem is high. We propose a new sampling method: Random Coordinate LMC (RC-LMC). At each iteration, a single coordinate is randomly selected to be updated by a multiple of the partial derivative along this direction plus noise, and all other coordinates remain untouched. We investigate the total complexity of RC-LMC and compare it with the classical LMC for log-concave probability distributions. When the gradient of the log-density is Lipschitz, RC-LMC is less expensive than the classical LMC if the log-density is highly skewed for high dimensional problems, and when both the gradient and the Hessian of the log-density are Lipschitz, RC-LMC is always cheaper than the classical LMC, by a factor proportional to the square root of the problem dimension. In the latter case, our estimate of complexity is sharp with respect to the dimension.

Related papers

• 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)
• 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)
• 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)
• Gaussian process regression and conditional Karhunen-Lo\'{e}ve models for data assimilation in inverse problems [68.8204255655161]
  We present a model inversion algorithm, CKLEMAP, for data assimilation and parameter estimation in partial differential equation models. The CKLEMAP method provides better scalability compared to the standard MAP method.
  arXiv  Detail & Related papers  (2023-01-26T18:14:12Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• 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)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Random Coordinate Underdamped Langevin Monte Carlo [20.423417125810868]
  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.
  arXiv  Detail & Related papers  (2020-10-22T01:12:13Z)
• Langevin Monte Carlo: random coordinate descent and variance reduction [7.464874233755718]
  Langevin Monte Carlo (LMC) is a popular Bayesian sampling method. We investigate how to enhance computational efficiency through the application of RCD (random coordinate descent) on LMC.
  arXiv  Detail & Related papers  (2020-07-26T18:14:36Z)
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo [7.464874233755718]
  Langevin Monte Carlo (LMC) that provides fast convergence requires computation of gradient approximations. In practice one uses finite-differencing approximations as surrogates, and the method is expensive in high-dimensions. We introduce a new variance reduction approach, termed Coordinates Averaging Descent (RCAD), and incorporate it with both overdamped and underdamped LMC.
  arXiv  Detail & Related papers  (2020-06-10T21:08:38Z)
• 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.