Non-asymptotic Analysis Of Biased Stochastic Approximation Scheme

Abstract

Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykarimi2019non

Related papers

• Asynchronous Stochastic Approximations With Asymptotically Biased Errors And Deep Multi-agent Learning (2018)0.00
• Asymptotic Bias Of Stochastic Gradient Search (2017)0.00
• On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias (2020)0.00
• Finite-sample Analysis Of Stochastic Approximation Using Smooth Convex Envelopes (2020)0.00
• Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
• Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
• Stochastic Approximation With Delayed Updates: Finite-time Rates Under Markovian Sampling (2024)0.00
• Finite-sample Analysis For SARSA With Linear Function Approximation (2019)0.00