Technical Note—On the Convergence Rate of Stochastic Approximation for Gradient-Based Stochastic Optimization

We consider stochastic optimization via gradient-based search. Under a stochastic approximation framework, we apply a recently developed convergence rate analysis to provide a new finite-time error bound for a class of problems with convex differentiable structures. For noisy black-box functions, our main result allows us to derive finite-time bounds in the setting where the gradients are estimated via finite-difference estimators, including those based on randomized directions such as the simultaneous perturbation stochastic approximation algorithm. In particular, the convergence rate analysis sheds light on when it may be advantageous to use such randomized gradient estimates in terms of problem dimension and noise levels.