Accelerated Stochastic Approximation

Using a stochastic approximation procedure \Xₙ\, n = 1, 2, , for a value, it seems likely that frequent fluctuations in the sign of (Xₙ -) - (X₍ - ₁ -) = Xₙ - X₍ - ₁ indicate that |Xₙ - | is small, whereas few fluctuations in the sign of Xₙ - X₍ - ₁ indicate that Xₙ is still far away from. In view of this, certain approximation procedures are considered, for which the magnitude of the nth step (i. e. , X₍ + ₁ - Xₙ) depends on the number of changes in sign in (Xᵢ - X₈ - ₁) for i = 2, , n. In theorems 2 and 3, X₍ + ₁ - Xₙ is of the form bₙZₙ, where Zₙ is a random variable whose conditional expectation, given X₁, , Xₙ, has the opposite sign of Xₙ - and bₙ is a positive real number. bₙ depends in our processes on the changes in sign of Xᵢ - X₈ - ₁ (i n) in such a way that more changes in sign give a smaller bₙ. Thus the smaller the number of changes in sign before the nth step, the larger we make the correction on Xₙ at the nth step. These procedures may accelerate the convergence of Xₙ to, when compared to the usual procedures (3 and 5). The result that the considered procedures converge with probability one may be useful for finding optimal procedures. Application to the Robbins-Monro procedure (Theorem 2) seems more interesting than application to the Kiefer-Wolfowitz procedure (Theorem 3).