Convergence rate of moments in stochastic approximation withsimultaneous perturbation gradient approximation and resetting

摘要

The sequence of recursive estimators for function minimization generated by Spall's (1998) simultaneous perturbation stochastic approximation (SPSA) method, combined with a suitable restarting mechanism is considered. It is proved that this sequence converges under certain conditions with rate O(n-β/2) for some β>0, the best value being β=2/3, where the rate is measured by the Lq-norm of the estimation error for any 1⩽q<∞. The authors also present higher order SPSA methods. It is shown that the error exponent β/2 can be arbitrarily close to 1/2 if the Hessian matrix of the cost function at the minimizing point has all its eigenvalues to the right of 1/2, the cost function is sufficiently smooth, and a sufficiently high-order approximation of the derivative is used