A stopping rule for linear stochastic approximation
Takayuki Wada, Takamitsu Itani, Yasumasa Fujisaki · 2010
A stopping rule is developed for multidimensional stochastic approximation which seeks for a solution of an unknown equation based on random noise corrupted residuals. It is assumed that the equation is linear, and the noise is independent and identically distributed random vectors with a bounded covariance. Then, it is shown that the necessary number of iterations is bounded by a polynomial of the covariance and parameters which specify probabilistic precision on the resultant candidate of the solution.