On conditions for convergence rates of stochastic approximation algorithms

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

Research output: Contribution to journalConference article

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.

Original languageEnglish (US)
Pages (from-to)2279-2280
Number of pages2
JournalProceedings of the IEEE Conference on Decision and Control
Volume3
StatePublished - Dec 1 1997
Externally publishedYes
EventProceedings of the 1997 36th IEEE Conference on Decision and Control. Part 1 (of 5) - San Diego, CA, USA
Duration: Dec 10 1997Dec 12 1997

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'On conditions for convergence rates of stochastic approximation algorithms'. Together they form a unique fingerprint.

  • Cite this