Exponential Concentration in Stochastic Approximation

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) .