Rate of convergence of moments of Spall´s SPSA method

It is proved that the sequence of recursive estimators for function minimization generated by Spall´s method combined with a suitable restarting mechanism converges under certain conditions with rate O(n^-β/2) with some β > 0, the best value being β = 2/3, where the rate is measured by the L_q-norm of the estimation error for any I ≤ q <; ∞. Using a higher order approximation scheme for the derivative, β can be made arbitrarily close to 1/2. The method has potential applications in direct stochastic adaptive control.