mlsanityData to 7 Oct 2026

Convergence Analysis of Stochastic Gradient Descent with MCMC Estimators

arXiv 2303.10599 ↗First posted 19 Mar 2023stat.ML math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

Understanding stochastic gradient descent (SGD) and its variants is essential for machine learning. However, most of the preceding analyses are conducted under amenable conditions such as unbiased gradient estimator and bounded objective functions, which does not encompass many sophisticated applications, such as variational Monte Carlo, entropy-regularized reinforcement learning and variational inference. In this paper, we consider the SGD algorithm that employ the Markov Chain Monte Carlo (MCMC) estimator to compute the gradient, called MCMC-SGD. Since MCMC reduces the sampling complexity significantly, it is an asymptotically convergent biased estimator in practice. Moreover, by incorporating a general class of unbounded functions, it is much more difficult to analyze the MCMC sampling error. Therefore, we assume that the function is sub-exponential and use the Bernstein inequality for non-stationary Markov chains to derive error bounds of the MCMC estimator. Consequently, MCMC-SGD is proven to have a first order convergence rate O(log K/√n K) with K iterations and a sample size n. It partially explains how MCMC influences the behavior of SGD. Furthermore, we verify the correlated negative curvature condition under reasonable assumptions. It is shown that MCMC-SGD escapes from saddle points and reaches (ε,ε1/4) approximate second order stationary points or ε1/2-variance points at least O(ε-11/2log2(1/ε) ) steps with high probability. Our analysis unveils the convergence pattern of MCMC-SGD across a broad class of stochastic optimization problems, and interprets the convergence phenomena observed in practical applications.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 16 of its 50 references that are in the map. First posted on arXiv 19 Mar 2023.

Builds on

16 of 50 references.

References · 16

  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  2. 2016Variational Inference: A Review for Statisticianscited by 1,466
  3. 2013Black Box Variational Inferencecited by 317
  4. 2017How to Escape Saddle Points Efficientlycited by 284
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2019Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networkscited by 195
  7. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  8. 2019Deep neural network solution of the electronic Schr"odinger equationcited by 124
  9. 2017Filtering Variational Objectivescited by 91
  10. 2020On the Convergence of SGD with Biased Gradientscited by 79
  11. 2018Escaping Saddles with Stochastic Gradientscited by 66
  12. 2018On Markov Chain Gradient Descentcited by 63
4 more
  1. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  2. 2017Neural-Network Quantum States, String-Bond States, and Chiral Topological Statescited by 31
  3. 2017Approximate Inference with Amortised MCMCcited by 22
  4. 2017Learning hard quantum distributions with variational autoencoderscited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Accurate Ab-initio Neural-network Solutions to Large-Scale Electronic Structure Problemscited by 8
  2. 2025DIPLI: Deep Image Prior Lucky Imaging for Blind Astronomical Image Restorationcited by 0
  3. 2026Is Variational Monte Carlo Robust? Sharp Moment Thresholds and Heavy-tailed Stochastic Optimizationcited by 0