Exponential Concentration in Stochastic Approximation
研究了随机逼近算法在非消失梯度条件下的指数集中性，证明PSGD、Kiefer-Wolfowitz和Frank-Wolfe算法在最优解附近具有指数集中性，从而获得更快的线性收敛和O(1/t)速率。
We analyze the convergence rates of stochastic approximation algorithms under nonvanishing gradient conditions. For these sharp (V-shaped) functions, standard Gaussian approximations fail, making tighter exponential concentration bounds more suitable. We prove that stochastic approximation algorithms, including Projected Stochastic Gradient Descent (PSGD), Kiefer-Wolfowitz, and Frank-Wolfe algorithms, exhibit exponential concentration near an optimum. A consequence is faster convergence rates, notably linear convergence, and O(1/t) rates. The paper leverages techniques from Markov chain theory, specifically geometric ergodicity and Lyapunov drift analysis, thereby extending previous results by Hajek (1982) .