A stopping rule for stochastic approximation. (October 2015)

• Record Type: Journal Article
• Authors: Wada, Takayuki; Fujisaki, Yasumasa
• Is Part Of: Automatica. Volume 60(2015)
• Page Start: 1
• Page End: 6
• Publication Date: 2015-10
• Subjects: Stochastic approximation -- Randomized algorithms -- Adaptive control -- System identification; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2015.06.029
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: A stochastic approximation algorithm is a recursive procedure to find the solution to an unknown nonlinear equation via noisy measurements. In this paper, we present a stopping rule for a stochastic approximation. We show that there is a high probability that the distance between the exact solution and the candidate solution is less than a specified tolerance level when the stochastic approximation stops according to our stopping rule. Furthermore, the number of recursions required by the stopping rule is a polynomial function of the problem size.