Convergence of markovian stochastic approximation with discontinuous dynamics

G. Fort; E. Moulines; A. Schreck; M. Vihola

doi:10.1137/140962723

Convergence of markovian stochastic approximation with discontinuous dynamics

G. Fort
, E. Moulines
, A. Schreck
, M. Vihola

Research output: Contribution to journal › Article › peer-review

Abstract

This paper is devoted to the convergence analysis of stochastic approximation algorithms of the form θ_n+1 = θ_n + γ_n+1H_θn(X_n+1), where {θ_n, n ϵ ℕ} is an Rd-valued sequence, {γ_n, n ϵ N} is a deterministic stepsize sequence, and {X_n, n ϵ N} is a controlled Markov chain. We study the convergence under weak assumptions on smoothness-in-θ of the function θ → H_θ(x). It is usually assumed that this function is continuous for any x; in this work, we relax this condition. Our results are illustrated by considering stochastic approximation algorithms for (adaptive) quantile estimation and a penalized version of the vector quantization.

Original language	English
Pages (from-to)	866-893
Number of pages	28
Journal	SIAM Journal on Control and Optimization
Volume	54
Issue number	2
DOIs	https://doi.org/10.1137/140962723
Publication status	Published - 1 Jan 2016
Externally published	Yes

Keywords

Controlled Markov chain
Discontinuous dynamics
State-dependent noise
Stochastic approximation

Access to Document

10.1137/140962723

Cite this

@article{7374cd9f909a44e78af7c68d30c3dbe6,

title = "Convergence of markovian stochastic approximation with discontinuous dynamics",

abstract = "This paper is devoted to the convergence analysis of stochastic approximation algorithms of the form θn+1 = θn + γn+1Hθn(Xn+1), where \{θn, n ϵ ℕ\} is an Rd-valued sequence, \{γn, n ϵ N\} is a deterministic stepsize sequence, and \{Xn, n ϵ N\} is a controlled Markov chain. We study the convergence under weak assumptions on smoothness-in-θ of the function θ → Hθ(x). It is usually assumed that this function is continuous for any x; in this work, we relax this condition. Our results are illustrated by considering stochastic approximation algorithms for (adaptive) quantile estimation and a penalized version of the vector quantization.",

keywords = "Controlled Markov chain, Discontinuous dynamics, State-dependent noise, Stochastic approximation",

author = "G. Fort and E. Moulines and A. Schreck and M. Vihola",

note = "Publisher Copyright: {\textcopyright} 2016 Society for Industrial and Applied Mathematics.",

year = "2016",

month = jan,

day = "1",

doi = "10.1137/140962723",

language = "English",

volume = "54",

pages = "866--893",

journal = "SIAM Journal on Control and Optimization",

issn = "0363-0129",

number = "2",

}

TY - JOUR

T1 - Convergence of markovian stochastic approximation with discontinuous dynamics

AU - Fort, G.

AU - Moulines, E.

AU - Schreck, A.

AU - Vihola, M.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - This paper is devoted to the convergence analysis of stochastic approximation algorithms of the form θn+1 = θn + γn+1Hθn(Xn+1), where {θn, n ϵ ℕ} is an Rd-valued sequence, {γn, n ϵ N} is a deterministic stepsize sequence, and {Xn, n ϵ N} is a controlled Markov chain. We study the convergence under weak assumptions on smoothness-in-θ of the function θ → Hθ(x). It is usually assumed that this function is continuous for any x; in this work, we relax this condition. Our results are illustrated by considering stochastic approximation algorithms for (adaptive) quantile estimation and a penalized version of the vector quantization.

AB - This paper is devoted to the convergence analysis of stochastic approximation algorithms of the form θn+1 = θn + γn+1Hθn(Xn+1), where {θn, n ϵ ℕ} is an Rd-valued sequence, {γn, n ϵ N} is a deterministic stepsize sequence, and {Xn, n ϵ N} is a controlled Markov chain. We study the convergence under weak assumptions on smoothness-in-θ of the function θ → Hθ(x). It is usually assumed that this function is continuous for any x; in this work, we relax this condition. Our results are illustrated by considering stochastic approximation algorithms for (adaptive) quantile estimation and a penalized version of the vector quantization.

KW - Controlled Markov chain

KW - Discontinuous dynamics

KW - State-dependent noise

KW - Stochastic approximation

U2 - 10.1137/140962723

DO - 10.1137/140962723

M3 - Article

AN - SCOPUS:84964916966

SN - 0363-0129

VL - 54

SP - 866

EP - 893

JO - SIAM Journal on Control and Optimization

JF - SIAM Journal on Control and Optimization

IS - 2

ER -

Convergence of markovian stochastic approximation with discontinuous dynamics

Abstract

Keywords

Access to Document

Fingerprint

Cite this