Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness

Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, Justin Romberg

Type: Preprint

Publication Date: 2020-01-01

Citations: 11

DOI: https://doi.org/10.48550/arxiv.2003.10973

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Finite-Time Analysis of Markov Gradient Descent	2022	Thinh T. Doan
+	Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning	2020	Thinh T. Doan Lam M. Nguyen Nhan H. Pham Justin Romberg
+	Stochastic Gradient Descent under Markovian Sampling Schemes	2023	Mathieu Even
+ PDF Chat	Stochastic Variance-Reduced Policy Gradient	2018	Matteo Papini Damiano Binaghi Giuseppe Canonaco Matteo Pirotta Marcello Restelli
+	Stochastic Variance-Reduced Policy Gradient	2018	Matteo Papini Damiano Binaghi Giuseppe Canonaco Matteo Pirotta Marcello Restelli
+ PDF Chat	Stochastic First-Order Methods for Average-Reward Markov Decision Processes	2024	Tianjiao Li Feiyang Wu Guanghui Lan
+	Online covariance estimation for stochastic gradient descent under Markovian sampling	2023	Abhishek Roy Krishnakumar Balasubramanian
+ PDF Chat	Strongly-Polynomial Time and Validation Analysis of Policy Gradient Methods	2024	Caleb Ju Guanghui Lan
+	Stochastic first-order methods for average-reward Markov decision processes	2022	Tianjiao Li Feiyang Wu Guanghui Lan
+	A variational analysis of stochastic gradient algorithms	2016	Stephan Mandt Matthew D. Hoffman David M. Blei
+	A Variational Analysis of Stochastic Gradient Algorithms	2016	Stephan Mandt Matthew D. Hoffman David M. Blei
+	Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles	2020	Nirav Bhavsar Prashanth L. A
+	An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient	2019	Pan Xu Felicia Gao Quanquan Gu
+	Non-asymptotic Analysis of Biased Stochastic Approximation Scheme	2019	Belhal Karimi Błażej Miasojedow Éric Moulines Hoi-To Wai
+ PDF Chat	Nonasymptotic Bounds for Stochastic Optimization With Biased Noisy Gradient Oracles	2022	Nirav Bhavsar L. A. Prashanth
+	An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient	2019	Pan Xu Felicia Gao Quanquan Gu
+	The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise	2024	Shuze Liu Shuhang Chen Shangtong Zhang
+	Understanding the Effect of Stochasticity in Policy Optimization	2021	Jincheng Mei Bo Dai Chenjun Xiao Csaba Szepesvári Dale Schuurmans
+	Understanding the Effect of Stochasticity in Policy Optimization	2021	Jincheng Mei Bo Dai Chenjun Xiao Csaba Szepesvári Dale Schuurmans
+	Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes	2019	Alekh Agarwal Sham M. Kakade Jason D. Lee Gaurav Mahajan

Works That Cite This (11)

Action	Title	Year	Authors
+	On the Decentralized Stochastic Gradient Descent With Markov Chain Sampling	2023	Tao Sun Dongsheng Li Bao Wang
+	Finite-Time Analysis of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learning.	2020	Sihan Zeng Thinh T. Doan Justin Romberg
+ PDF Chat	On the Convergence of Consensus Algorithms with Markovian noise and Gradient Bias	2020	Hoi-To Wai
+	On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias	2020	Hoi-To Wai
+	Distributed TD(0) with Almost No Communication	2021	Rui Liu Alex Olshevsky
+	Federated Learning Under Heterogeneous and Correlated Client Availability	2023	Angelo Rodio Francescomaria Faticanti Othmane Marfoq Giovanni Neglia Emilio Leonardi
+	Federated Learning under Heterogeneous and Correlated Client Availability	2023	Angelo Rodio Francescomaria Faticanti Othmane Marfoq Giovanni Neglia Emilio Leonardi
+	A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning	2021	Sihan Zeng Thinh T. Doan Justin Romberg
+	State Dependent Performative Prediction with Stochastic Approximation	2021	Q. Li Hoi-To Wai
+	Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes	2021	Sihan Zeng Thinh T. Doan Justin Romberg

Works Cited by This (15)

Action	Title	Year	Authors
+ PDF Chat	Incremental Stochastic Subgradient Algorithms for Convex Optimization	2009	S. Sundhar Ram A. Nedić Venugopal V. Veeravalli
+	A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems	2009	Björn Johansson Maben Rabi Mikael Johansson
+	Error bounds and convergence analysis of feasible descent methods: a general approach	1993	Zhi-Quan Luo Paul Tseng
+ PDF Chat	The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth	2016	Hui Zhang
+	Linear Convergence of Descent Methods for the Unconstrained Minimization of Restricted Strongly Convex Functions	2016	Frank Schöpfer
+ PDF Chat	From error bounds to the complexity of first-order descent methods for convex functions	2016	Jérôme Bolte Trong Phong Nguyen Juan Peypouquet Bruce W. Suter
+ PDF Chat	Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition	2016	Hamed Karimi Julie Nutini Mark Schmidt
+	Optimization Methods for Large-Scale Machine Learning	2018	Léon Bottou Frank E. Curtis Jorge Nocedal
+ PDF Chat	Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming	2013	Saeed Ghadimi Guanghui Lan
+	On Markov Chain Gradient Descent	2018	Tao Sun Yuejiao Sun Wotao Yin