Exponential Concentration of Stochastic Approximation with Non-vanishing Gradient

We consider stochastic approximation algorithms where the expected progress toward the optimum is proportional to the algorithm's step size. For instance, a stochastic gradient descent algorithm applied to a convex function will satisfy this property when bounded away from the optimum. This property can continue to hold when the optimum is on the corner of a convex constraint set or when the function is not smooth at the optimum or when the objective function lies within a cone. In such settings, we will show that a projected stochastic gradient descent algorithm can have a different rate of convergence than would be anticipated by standard results for stochastic gradient descent with a smooth objective and smooth constraints. We develop new results whose methods are typically used in probability to analyze random walks or in applied probability to analyze queueing networks. For stochastic approximation, our results establish new exponential concentration bounds. We now summarize the background and problems where our results apply.