Asymptotic bias of stochastic gradient search

DOI10.1214/16-AAP1272zbMATH Open1387.49044arXiv1709.00291OpenAlexW2591423585MaRDI QIDQ1704136FDOQ1704136

Authors: Vladislav B. Tadić, Arnaud Doucet 

Publication date: 8 March 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: The asymptotic behavior of the stochastic gradient algorithm with a biased gradient estimator is analyzed. Relying on arguments based on the dynamic system theory (chain-recurrence) and the differential geometry (Yomdin theorem and Lojasiewicz inequality), tight bounds on the asymptotic bias of the iterates generated by such an algorithm are derived. The obtained results hold under mild conditions and cover a broad class of high-dimensional nonlinear algorithms. Using these results, the asymptotic properties of the policy-gradient (reinforcement) learning and adaptive population Monte Carlo sampling are studied. Relying on the same results, the asymptotic behavior of the recursive maximum split-likelihood estimation in hidden Markov models is analyzed, too.

Full work available at URL: https://arxiv.org/abs/1709.00291

Recommendations

• scientific article; zbMATH DE number 7625177
• Nonasymptotic Bounds for Stochastic Optimization With Biased Noisy Gradient Oracles
• Exploration of the (non-)asymptotic bias and variance of stochastic gradient Langevin dynamics
• Analysis of biased stochastic gradient descent using sequential semidefinite programs
• Asymptotic and finite-sample properties of estimators based on stochastic gradients
• Non-asymptotic guarantees for sampling by stochastic gradient descent
• scientific article; zbMATH DE number 6860839
• scientific article; zbMATH DE number 7306890
• On the steplength selection in stochastic gradient methods
• Asymptotic optimality in stochastic optimization

zbMATH Keywords

chain-recurrenceLojasiewicz inequalitiesstochastic gradient searchbiased gradient estimationYomdin theorem

Mathematics Subject Classification ID

Stochastic approximation (62L20) Stochastic programming (90C15) Identification in stochastic control theory (93E12) Stochastic learning and adaptive control (93E35) Numerical methods based on necessary conditions (49M05)

Cites Work

• Markov Chains and Stochastic Stability
• Inference in hidden Markov models.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Particle approximations of the score and observed information matrix in state space models with application to parameter estimation
• Nonlinear time series. Theory, methods and applications with R examples
• Introduction to Stochastic Search and Optimization
• Stochastic approximation. A dynamical systems viewpoint.
• Semianalytic and subanalytic sets
• Stochastic approximation and its applications
• Chain recurrence, semiflows, and gradients
• Nonlinear systems.
• Title not available (Why is that?)
• Applications of a Kushner and Clark lemma to general classes of stochastic algorithms
• Title not available (Why is that?)
• On semi- and subanalytic geometry
• The geometry of critical and near-critical values of differentiable mappings
• Gradient Convergence in Gradient methods with Errors
• Sur le problème de la division
• On gradients of functions definable in o-minimal structures
• Approximate Dynamic Programming
• OnActor-Critic Algorithms
• The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
• Stochastic Approximations and Differential Inclusions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perturbations of set-valued dynamical systems, with applications to game theory
• A Dynamical System Approach to Stochastic Approximations
• Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds
• Robustness analysis for stochastic approximation algorithms
• Analyticity, Convergence, and Convergence Rate of Recursive Maximum-Likelihood Estimation in Hidden Markov Models

Cited In (17)

• Stochastic approximation with discontinuous dynamics, differential inclusions, and applications
• Asymptotic and finite-sample properties of estimators based on stochastic gradients
• Stability of optimal filter higher-order derivatives
• Gradient estimation with simultaneous perturbation and compressive sensing
• On maximum a posteriori estimation with Plug \& Play priors and stochastic gradient descent
• Discrepancy-based inference for intractable generative models using quasi-Monte Carlo
• Convergence rates for optimised adaptive importance samplers
• Title not available (Why is that?)
• Bias of particle approximations to optimal filter derivative
• Maximum likelihood estimation of regularization parameters in high-dimensional inverse problems: an empirical Bayesian approach. II: Theoretical analysis
• Bridging the gap between constant step size stochastic gradient descent and Markov chains
• Convergence rates for stochastic approximation: biased noise with unbounded variance, and applications
• Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema
• Title not available (Why is that?)
• Particle-based online estimation of tangent filters with application to parameter estimation in nonlinear state-space models
• Bayesian Variational Inference for Exponential Random Graph Models
• Analysis of biased stochastic gradient descent using sequential semidefinite programs

This page was built for publication: Asymptotic bias of stochastic gradient search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704136)