Technical Note—On the Convergence Rate of Stochastic Approximation for Gradient-Based Stochastic Optimization
为凸可微结构下随机逼近算法提供了新的误差界，通过分析梯度估计的偏差和方差刻画有限时间性能，并比较了传统Kiefer-Wolfowitz算法与随机方向有限差分梯度估计方法的效率。
Finite-Time Performance of Gradient-Based Stochastic Approximation Algorithms Stochastic approximation (SA) algorithms are among the most commonly used methods for addressing stochastic optimization problems. In “Technical Note: On the Convergence Rate of Stochastic Approximation for Gradient-Based Stochastic Optimization,” J. Hu and M. C. Fu provide a new error bound for SA algorithms when applied to a class of problems with convex differentiable structures. The bound allows a detailed characterization of an algorithm’s finite-time performance through directly analyzing the bias and variance of the employed gradient estimator. The main result is then applied to study and compare the efficiency of traditional Kiefer-Wolfowitz algorithms and those based on random direction finite-difference gradient estimators such as simultaneous perturbation SA. The analysis leads to new insights into when it may be advantageous to use such randomized gradient estimates under various problem and algorithm parameter settings.