Noise conditions for prespecified convergence rates of stochastic approximation algorithms

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 =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. Then, under appropriate assumptions, we show that x_n -x* =o(ρ_n) if and only if the sequence {e_n} satisfies one of five equivalent conditions. These conditions are based on well-known formulas for noise sequences: Kushner and Clark's condition, Chen's condition, Kulkarni and Horn's condition, a decomposition condition, and a weighted averaging condition. Our necessary and sufficient condition on {e_n} to achieve a convergence rate of {ρ_n} is basically that the sequence {e_n/ρ_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 a_n = a/_n and {e_n} is a martingale difference process with bounded variance, then x_n -x* = o(n ^1/2(log(n))β) for any β>1/2.