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.

arXiv commentAccepted to COLT 2019; 32 pages. Minor updates in Section 3.2

References in corpus (4)

• Online EM Algorithm for Latent Data Models
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Stochastic Variance-Reduced Policy Gradient

Cited by in corpus (14)

• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Full error analysis for the training of deep neural networks
• Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization
• A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part I: Methodology and Experiments
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• Online Robust and Adaptive Learning from Data Streams
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias