DocumentCode :
3785212
Title :
On the almost sure rate of convergence of linear stochastic approximation algorithms
Author :
V.B. Tadic
Author_Institution :
Dept. of Autom. Control & Syst. Eng., Univ. of Sheffield, UK
Volume :
50
Issue :
2
fYear :
2004
Firstpage :
401
Lastpage :
409
Abstract :
The almost sure rate of convergence of linear stochastic approximation algorithms is analyzed. As the main result, it is demonstrated that their almost sure rate of convergence is equivalent to the almost sure rate of convergence of the averages of their input data sequences. As opposed to most of the existing results on the rate of convergence of stochastic approximation which cover only algorithms with the noise decomposable as the sum of a martingale difference, vanishing and telescoping sequence, the main results of this paper hold under assumptions not requiring the input data sequences to admit any particular decomposition. Although no decomposition of the input data sequences is required, the results on the almost sure rate of convergence of linear stochastic approximation algorithms obtained in this correspondence are as tight as the rate of convergence in the law of iterated logarithm. Moreover, the main result of this correspondence yields the law of iterated logarithm for linear stochastic approximation if the law of iterated logarithm holds for the input data sequences. The obtained general results are illustrated with two (nontrivial) examples where the input data sequences are strongly mixing strictly stationary random processes or functions of a uniformly ergodic Markov chain. These results are also applied to the analysis of least mean square (LMS) algorithms.
Keywords :
"Convergence","Stochastic processes","Linear approximation","Approximation algorithms","Least squares approximation","Signal processing algorithms","Algorithm design and analysis","Stochastic resonance","Random processes","Machine learning algorithms"
Journal_Title :
IEEE Transactions on Information Theory
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2003.821971
Filename :
1266818
Link To Document :
بازگشت