Tracking capability of stochastic gradient algorithm with constant gain

The stochastic gradient (SG) method has been widely applied in unconstrained stochastic optimization, and is particularly useful in sequential processing such as online learning. Core SG theories on convergence and asymptotic normality are developed on the basis of a stationary and unique optimizer. However, many real-world applications are often nonstationary in nature. In dynamic control systems and other time-varying problems, the true target parameter and/or the true loss function may drift over time, so there is no convergence per se. When drift occurs, SG with constant gain is often used to keep up with the nonstationary target. Several existing works on the tracking capability of recursive algorithms with a constant gain provide asymptotic stochastic big-O bounds of the tracking error. There are also some finite-iteration error bounds developed under fairly strong assumptions. In contrast, this paper builds a computable tracking error bound for SG, which is useful in both the finite-sample performance and the asymptotic analysis. The case of interest requires the strong convexity of the time-varying loss function, but with a mild restriction imposed on the drift associated with the nonstationary evolution. Our result complements existing big-O bound, and delivers a computable bound for practical use.