Scholarlink

<p>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 estimators and bounded objective functions, which do 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 employs the Markov chain Monte Carlo (MCMC) estimator to compute the gradient, called MCMC-SGD. Since MCMC reduces the sampling complexity significantly, it provides an asymptotically convergent biased estimator in practice. Moreover, when a general class of unbounded functions is incorporated, 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, the MCMC-SGD is proven to have a first-order convergence rate <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(\log\ K/\sqrt{n|K})\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo /> <mspace width="thinmathspace" /> <mi>K</mi> <mrow> <mo>/</mo> </mrow> <msqrt> <mi>n</mi> <mrow> <mo stretchy="false">|</mo> </mrow> <mi>K</mi> </msqrt> <mo stretchy="false">)</mo> </math></EquationSource> </InlineEquation> with <i>K</i> iterations and a sample size <i>n</i>. 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 the MCMC-SGD escapes from saddle points and reaches approximate second-order stationary points or <i>ϵ</i><sup>1/2</sup>-variance points at least <i>O</i>(<i>ϵ</i><sup>−11/2</sup> log<sup>2</sup>(1/<i>ϵ</i>)) steps with high probability. Our analysis unveils the convergence pattern of the MCMC-SGD across a broad class of stochastic optimization problems and helps interpret the convergence phenomena observed with practical applications.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Convergence analysis of stochastic gradient descent with MCMC estimators

  • 期刊论文

  • 发表日期：

    2026年5月6日

查看全文
  • Tianyou Li,
  • Fan Chen,
  • Huajie Chen,
  • Zaiwen Wen

摘要

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 estimators and bounded objective functions, which do 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 employs the Markov chain Monte Carlo (MCMC) estimator to compute the gradient, called MCMC-SGD. Since MCMC reduces the sampling complexity significantly, it provides an asymptotically convergent biased estimator in practice. Moreover, when a general class of unbounded functions is incorporated, 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, the MCMC-SGD is proven to have a first-order convergence rate \(O(\log\ K/\sqrt{n|K})\) 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 the MCMC-SGD escapes from saddle points and reaches approximate second-order stationary points or ϵ1/2-variance points at least O(ϵ−11/2 log2(1/ϵ)) steps with high probability. Our analysis unveils the convergence pattern of the MCMC-SGD across a broad class of stochastic optimization problems and helps interpret the convergence phenomena observed with practical applications.