Tracking Nonstationary Streaming Data via Exponentially Weighted Moving Average Stochastic Gradient Descent

In many applications involving data streams, the sequences of data arise from highly dynamic and often unstable real-life processes, rendering untenable the standard assumption that current and future data come from the same distribution. In response, new methodologies, such as dynamic online learning, have been proposed in order to account for the nonstationary features in the data-generating process. Motivated by the stability and statistical efficiency of the notable stochastic approximation method, average stochastic gradient descent (ASGD) in time-invariant systems, the authors propose an exponentially weighted moving average (EWMA)-based stochastic gradient descent (SGD) which accommodates the dynamic structure by introducing a forgetting factor and replacing the simple averaging step in ASGD with an EWMA step. Provided that the dynamic drift is Lipschitz continuous, the mean squared tracking error rate of the proposed method achieves the optimal rate in the nonparametric statistical paradigm. The proposed framework also allows us to derive the dynamic regret bound and asymptotic normality with a path variation constraint in a natural manner. Numerical analysis has been conducted to verify the performance of the proposed method. In particular, the proposed method is much more robust to the selection of learning rates compared with the ordinary SGD method.