On conditions for convergence rates of stochastic approximation algorithms

Edwin K P Chong; I. Jeng Wang; Sanjeev R. Kulkarni

On conditions for convergence rates of stochastic approximation algorithms

Edwin K P Chong, I. Jeng Wang, Sanjeev R. Kulkarni

Research output: Contribution to journal › Conference article › peer-review

Abstract

We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {ρ_n} is a given positive sequence converging monotonically to 0. Consider a stochastic approximation algorithm x_n+1 = x_n-a_n(A_nx_n-b_n)+a_ne_n, where {x_n} is the iterate sequence, {a_n} is the step size sequence, {e_n} is the noise sequence, and x* is the desired zero of the function f(x) = Ax-b. We show that x_n-z* = o(ρ_n) if and only if the sequence {e_n} satisfies one of five equivalent conditions. These conditions are based on well known for formulas for noise sequences found in the literature.

Original language	English (US)
Pages (from-to)	2279-2280
Number of pages	2
Journal	Proceedings of the IEEE Conference on Decision and Control
Volume	3
State	Published - 1997
Externally published	Yes
Event	Proceedings of the 1997 36th IEEE Conference on Decision and Control. Part 1 (of 5) - San Diego, CA, USA Duration: Dec 10 1997 → Dec 12 1997

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Cite this

@article{4239c037f7574cbba50c13c78b41ec7c,

title = "On conditions for convergence rates of stochastic approximation algorithms",

abstract = "We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {ρn} is a given positive sequence converging monotonically to 0. Consider a stochastic approximation algorithm xn+1 = xn-an(Anxn-bn)+anen, where {xn} is the iterate sequence, {an} is the step size sequence, {en} is the noise sequence, and x* is the desired zero of the function f(x) = Ax-b. We show that xn-z* = o(ρn) if and only if the sequence {en} satisfies one of five equivalent conditions. These conditions are based on well known for formulas for noise sequences found in the literature.",

author = "Chong, {Edwin K P} and Wang, {I. Jeng} and Kulkarni, {Sanjeev R.}",

year = "1997",

language = "English (US)",

volume = "3",

pages = "2279--2280",

journal = "Proceedings of the IEEE Conference on Decision and Control",

issn = "0191-2216",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the 1997 36th IEEE Conference on Decision and Control. Part 1 (of 5) ; Conference date: 10-12-1997 Through 12-12-1997",

}

TY - JOUR

T1 - On conditions for convergence rates of stochastic approximation algorithms

AU - Chong, Edwin K P

AU - Wang, I. Jeng

AU - Kulkarni, Sanjeev R.

PY - 1997

Y1 - 1997

N2 - We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {ρn} is a given positive sequence converging monotonically to 0. Consider a stochastic approximation algorithm xn+1 = xn-an(Anxn-bn)+anen, where {xn} is the iterate sequence, {an} is the step size sequence, {en} is the noise sequence, and x* is the desired zero of the function f(x) = Ax-b. We show that xn-z* = o(ρn) if and only if the sequence {en} satisfies one of five equivalent conditions. These conditions are based on well known for formulas for noise sequences found in the literature.

AB - We develop deterministic necessary and sufficient conditions on individual noise sequences of a stochastic approximation algorithm for the error of the iterates to converge at a given rate. Specifically, suppose {ρn} is a given positive sequence converging monotonically to 0. Consider a stochastic approximation algorithm xn+1 = xn-an(Anxn-bn)+anen, where {xn} is the iterate sequence, {an} is the step size sequence, {en} is the noise sequence, and x* is the desired zero of the function f(x) = Ax-b. We show that xn-z* = o(ρn) if and only if the sequence {en} satisfies one of five equivalent conditions. These conditions are based on well known for formulas for noise sequences found in the literature.

UR - http://www.scopus.com/inward/record.url?scp=0031347604&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031347604&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0031347604

SN - 0191-2216

VL - 3

SP - 2279

EP - 2280

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

T2 - Proceedings of the 1997 36th IEEE Conference on Decision and Control. Part 1 (of 5)

Y2 - 10 December 1997 through 12 December 1997

ER -

On conditions for convergence rates of stochastic approximation algorithms

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this