Asymptotic bias of stochastic gradient search

The asymptotic behavior of the stochastic gradient algorithm with a biased gradient estimator is analyzed. Relying on arguments based on differential geometry (Yomdin theorem and Lojasiewicz inequality), relatively tight bounds on the asymptotic bias of the iterates generated by such an algorithm are derived. The obtained results hold under mild and verifiable conditions and cover a broad class of complex stochastic gradient algorithms. Using these results, the asymptotic properties of the actor-critic reinforcement learning are studied.

• Publication year

  2011

• Venue

  IEEE Conference on Decision and Control and European Control Conference

• Publication date

  2011-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CDC.2011.6160812arXiv 1709.00291
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimization of Stochastic Models: The Interface Between Simulation and Optimization

  2012cited by this paper
• System Identification: Theory for the User, 2nd Edition (Ljung, L.; 1999) [On the Shelf]

  2012influential reference
• Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory

  2012cited by this paper
• Particle approximations of the score and observed information matrix in state space models with application to parameter estimation

  2011cited by this paper
• Inference in hidden Markov models

  2010cited by this paper
• Neuro-Dynamic Programming

  2009cited by this paper
• Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema

  2009cited by this paper
• An overview of sequential Monte Carlo methods for parameter estimation in general state-space models

  2009influential reference
• Analyticity, Convergence, and Convergence Rate of Recursive Maximum-Likelihood Estimation in Hidden Markov Models

  2009cited by this paper
• Stochastic Approximation: A Dynamical Systems Viewpoint

  2008cited by this paper
• Stochastic Learning and Optimization

  2007cited by this paper
• Approximate Dynamic Programming

  2007influential reference
• Convergence of adaptive mixtures of importance sampling schemes

  2007influential reference
• Adaptive importance sampling in general mixture classes

  2007influential reference
• Inference in Hidden Markov Models

  2006cited by this paper
• Simulation and Monte Carlo Methods

  2006cited by this paper
• Maximum Likelihood Parameter Estimation in General State-Space Models using Particle Methods

  2005influential reference
• Exponential forgetting and geometric ergodicity for optimal filtering in general state-space models

  2005cited by this paper
• Stochastic Approximations and Differential Inclusions

  2005cited by this paper
• On-Line Parameter Estimation in General State-Space Models

  2005cited by this paper
• Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control:Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control

  2004cited by this paper
• Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control

  2004cited by this paper
• Particle methods for change detection, system identification, and control

  2004cited by this paper
• Population Monte Carlo

  2004influential reference
• Convergence of Adaptive Sampling Schemes

  2004cited by this paper
• Performance Evaluation and Policy Selection in Multiclass Networks

  2003cited by this paper
• Introduction to stochastic search and optimization - estimation, simulation, and control

  2003cited by this paper
• Sequential Monte Carlo Methods in Practice

  2003cited by this paper
• Stochastic Approximation and Recursive Algorithms and Applications

  2003cited by this paper
• Adaptive blind signal and image processing

  2002cited by this paper
• Stochastic approximation and its applications

  2002cited by this paper
• Adaptive Blind Signal and Image Processing - Learning Algorithms and Applications

  2002cited by this paper
• Infinite-Horizon Policy-Gradient Estimation

  2001influential reference
• Sequential Monte Carlo Methods in Practice

  2001cited by this paper
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning

  2000influential reference
• Introduction to Discrete Event Systems

  1999cited by this paper
• Actor-Critic Algorithms

  1999influential reference
• Dynamics of stochastic approximation algorithms

  1999influential reference
• Gradient Convergence in Gradient methods with Errors

  1999cited by this paper
• Stochastic approximation with random truncations, state-dependent noise and discontinuous dynamics

  1998influential reference
• On gradients of functions definable in o-minimal structures

  1998cited by this paper
• On recursive estimation for hidden Markov models

  1997influential reference
• A Dynamical System Approach to Stochastic Approximations

  1996cited by this paper
• Optimization of Stochastic Models

  1996cited by this paper
• Chain recurrence, semiflows, and gradients

  1995cited by this paper
• Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method

  1995cited by this paper
• Consistent and Asymptotically Normal Parameter Estimates for Hidden Markov Models

  1994influential reference
• Markov Chains and Stochastic Stability

  1993cited by this paper
• Sur la géométrie semi- et sous- analytique

  1993cited by this paper
• Adaptive Algorithms and Stochastic Approximations

  1990influential reference
• Robustness analysis for stochastic approximation algorithms

  1989cited by this paper
• Semianalytic and subanalytic sets

  1988influential reference
• Introduction to optimization

  1987cited by this paper
• Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds

  1987cited by this paper
• Applications of a Kushner and Clark lemma to general classes of stochastic algorithms

  1984cited by this paper
• Differential inclusions set-valued maps and viability theory

  1984cited by this paper
• The geometry of critical and near-critical values of differentiable mappings

  1983cited by this paper
• Sur le problème de la division

  1959cited by this paper
• On gradients of functions definable in o-minimal structures

  year unknowncited by this paper

• Distributionally robust optimization via regularized robust optimization

  2026cites this paper
• Bilevel gradient methods and the Morse parametric qualification condition

  2025influential citation
• Structural bias in metaheuristic algorithms: Insights, open problems, and future prospects

  2025cites this paper
• Derivatives of Stochastic Gradient Descent

  2024cites this paper
• Equivariant Denoisers for Image Restoration

  2024influential citation
• Unbiased Markov Chain Monte Carlo: what, why, and how

  2024cites this paper
• Plug-and-Play image restoration with Stochastic deNOising REgularization

  2024cites this paper
• Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation

  2024cites this paper
• Inexact subgradient methods for semialgebraic functions

  2024influential citation
• Stochastic Approximation with Biased MCMC for Expectation Maximization

  2024influential citation
• Implicit Diffusion: Efficient Optimization through Stochastic Sampling

  2024cites this paper
• Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning

  2023influential citation
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications

  2023cites this paper
• Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients

  2022cites this paper
• On Maximum a Posteriori Estimation with Plug & Play Priors and Stochastic Gradient Descent

  2022influential citation
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data

  2022cites this paper
• Regularized R\'enyi divergence minimization through Bregman proximal gradient algorithms

  2022cites this paper
• Deterministic policy gradient: Convergence analysis

  2022cites this paper
• Iteration Complexity of Variational Quantum Algorithms

  2022cites this paper
• Stability and Generalization for Markov Chain Stochastic Gradient Methods

  2022cites this paper
• A Repeated Unknown Game: Decentralized Task Offloading in Vehicular Fog Computing

  2022influential citation
• BR-SNIS: Bias Reduced Self-Normalized Importance Sampling

  2022cites this paper
• Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data

  2022cites this paper
• Unbiased Multilevel Monte Carlo methods for intractable distributions: MLMC meets MCMC

  2022cites this paper
• State Dependent Performative Prediction with Stochastic Approximation

  2021cites this paper
• Asymptotic Properties of Recursive Particle Maximum Likelihood Estimation

  2021cites this paper
• Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie

  2021cites this paper
• On Unbiased Score Estimation for Partially Observed Diffusions

  2021cites this paper
• Discrepancy-based inference for intractable generative models using Quasi-Monte Carlo

  2021cites this paper
• Stochastic approximation with discontinuous dynamics, differential inclusions, and applications

  2021influential citation
• Conditional Gaussian PAC-Bayes

  2021cites this paper
• Conditionally Gaussian PAC-Bayes

  2021cites this paper
• Recent advances in stochastic approximation with applications to optimization and fixed point problems

  2021cites this paper
• Maximum Likelihood Estimation of Regularization Parameters in High-Dimensional Inverse Problems: An Empirical Bayesian Approach. Part II: Theoretical Analysis

  2020cites this paper
• Continuous and Discrete-Time Analysis of Stochastic Gradient Descent for Convex and Non-Convex Functions.

  2020cites this paper
• Policy-Aware Model Learning for Policy Gradient Methods

  2020cites this paper
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling

  2020cites this paper
• Unbiased Markov chain Monte Carlo methods with couplings

  2020cites this paper
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms

  2020cites this paper
• Improving Sample Complexity Bounds for Actor-Critic Algorithms

  2020cites this paper
• Non-Convex Optimization for Latent Data Models : Algorithms, Analysis and Applications

  2019cites this paper
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

  2019influential citation
• Recursive Maximum Likelihood Algorithm for Dependent Observations

  2019cites this paper
• Asymptotic Properties of Recursive Particle Maximum Likelihood Estimation

  2019cites this paper
• Convergence rates for optimised adaptive importance samplers

  2019cites this paper
• A Stochastic Gradient Method with Biased Estimation for Faster Nonconvex Optimization

  2019cites this paper
• AutoAssist: A Framework to Accelerate Training of Deep Neural Networks

  2019cites this paper
• Bayesian Variational Inference for Exponential Random Graph Models

  2018cites this paper
• PR ] 1 A ug 2 01 8 Stability of Optimal Filter Higher-Order Derivatives

  2018influential citation
• Bias of Particle Approximations to Optimal Filter Derivative

  2018cites this paper
• Stability of Optimal Filter Higher-Order Derivatives

  2018influential citation
• Analyticity of Entropy Rates of Continuous-State Hidden Markov Models

  2018cites this paper
• Particle-based online estimation of tangent filters with application to parameter estimation in nonlinear state-space models

  2017cites this paper
• Bridging the gap between constant step size stochastic gradient descent and Markov chains

  2017cites this paper
• Unbiased Markov chain Monte Carlo with couplings

  2017cites this paper
• Analysis of Gradient Descent Methods With Nondiminishing Bounded Errors

  2016influential citation
• Gradient Estimation with Simultaneous Perturbation and Compressive Sensing

  2015cites this paper
• Online Sequential Optimization with Biased Gradients: Theory and Applications to Censored Demand

  2014cites this paper
• Maximum marginal likelihood estimation of the granularity coefficient of a Potts-Markov random field within an MCMC algorithm

  2014cites this paper
• Recent Advances in Stochastic Approximation with Applications to Optimization and Reinforcement Learning

  year unknowncites this paper