Non-asymptotic Analysis of Biased Stochastic Approximation Scheme - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

(1, 2) , (3) , (1, 2) , (4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
colt_Revised.pdf (455.74 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02127750 , version 1 (13-05-2019)

Identifiers

  • HAL Id : hal-02127750 , version 1

Cite

Belhal Karimi, Blazej Miasojedow, Éric Moulines, Hoi-To Wai. Non-asymptotic Analysis of Biased Stochastic Approximation Scheme. COLT 2019 - 32nd Annual Conference on Conference on Learning Theory, Jun 2019, Phoenix, United States. pp.1 - 33. ⟨hal-02127750⟩
135 View
120 Download

Share

Gmail Facebook Twitter LinkedIn More