Name
Title | ||
|---|---|---|
Noise conditions for prespecified 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 zero. Consider a stochastic approximation algorithm x n+1=xn-an(Anxn-b n)+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. Then, under appropriate assumptions, we show that x n-x*=o(ρn) if and only if the sequence {en} satisfies one of five equivalent conditions. These conditions are based on well-known formulas for noise sequences: Kushner and Clark's (1978) condition, Chen's (see Proc. IFAC World Congr., p.375-80, 1996) condition, Kulkarni and Horn's (see IEEE Trails Automat. Contr., vol.41, p.419-24, 1996) condition, a decomposition condition, and a weighted averaging condition. Our necessary and sufficient condition on {en} to achieve a convergence rate of {ρn} is basically that the sequence {en/ρ n} satisfies any one of the above five well-known conditions. We provide examples to illustrate our result. In particular, we easily recover the familiar result that if an=a/n and {en} is a martingale difference process with bounded variance, then xn-x*=o(n-1/2(log(n))β ) for any β>1/2 |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/18.749035 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
sufficient condition,necessary and suf- ficient conditions,iterate sequence,stochastic approximation algorithm,step size sequence,noise sequences,then for any . index terms— convergence rate,robbins-monro,equivalent condition,kiefer-wolfowitz,individual noise sequence,positive sequence,weighted averaging condition,stochastic approxi- mation.,noise condition,noise sequence,process with bounded variance,decomposition condition,prespecified convergence rate,hilbert space,stochastic resonance,writing,physics,convergence rate,approximation algorithms,indexing terms,noise,neural networks,approximation theory,satisfiability,stochastic processes,sequences,convergence | Monotonic function,Discrete mathematics,Martingale difference sequence,Combinatorics,Stochastic process,Approximation theory,Algorithm,Rate of convergence,Iterated function,Stochastic approximation,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
45 | 2 | 0018-9448 |
Citations | PageRank | References |
8 | 1.19 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. K.P. Chong | 1 | 459 | 48.00 |
| I-Jeng Wang | 2 | 277 | 31.46 |
| S. R. Kulkarni | 3 | 8 | 1.19 |