Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains

2017-07-20 · Aymeric Dieuleveut, Alain Durmus, Francis Bach

We consider the minimization of an objective function given access to unbiased estimates of its gradient through stochastic gradient descent (SGD) with constant step-size. While the detailed analysis was only performed for quadratic functions, we provide an explicit asymptotic expansion of the moments of the averaged SGD iterates that outlines the dependence on initial conditions, the effect of noise and the step-size, as well as the lack of convergence in the general (non-quadratic) case. For this analysis, we bring tools from Markov chain theory into the analysis of stochastic gradient. We then show that Richardson-Romberg extrapolation may be used to get closer to the global optimum and we show empirical improvements of the new extrapolation scheme.

📄 PDF Abstract BibTeX arXiv:1707.06386

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization

2019-02-15 · Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, Quoc Tran-Dinh

We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator…

Linear Stochastic Approximation: Constant Step-Size and Iterate Averaging

2017-09-12 · Chandrashekar Lakshminarayanan, Csaba Szepesvári

We consider $d$-dimensional linear stochastic approximation algorithms (LSAs) with a constant step-size and the so called Polyak-Ruppert (PR) averaging of iterates. LSAs are widely applied in machine learning and reinfor…

Reinforcement Learning Reinforcement Learning (RL)

Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes

2024-09-06 · Vishesh Mittal, Rahul Meshram, Surya Prakash

We study the Whittle index learning algorithm for restless multi-armed bandits. We consider index learning algorithm with Q-learning. We first present Q-learning algorithm with exploration policies -- epsilon-greedy, sof…

Multi-Armed Bandits Q-Learning

Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way

2024-10-16 · Jeongyeol Kwon, Luke Dotson, Yudong Chen, Qiaomin Xie

Previous studies on two-timescale stochastic approximation (SA) mainly focused on bounding mean-squared errors under diminishing stepsize schemes. In this work, we investigate {\it constant} stpesize schemes through the …

On the Influence of Momentum Acceleration on Online Learning

2016-03-14 · Kun Yuan, Bicheng Ying, Ali H. Sayed

The article examines in some detail the convergence rate and mean-square-error performance of momentum stochastic gradient methods in the constant step-size and slow adaptation regime. The results establish that momentum…