COVER: A Cluster-based Variance Reduced Method for Online Learning
Kun Yuan, Bicheng Ying, Ali H. Sayed · 2019
In this paper, we develop a stochastic-gradient learning algorithm for situations involving streaming data that arise from an underlying clustered structure. In such settings, the variance of gradient noise can be decomposed into the in-cluster variance σin2plus the between-cluster variance σbet2. We develop a cluster-based online variancereduced method (COVER) to eliminate σbet2and improve the MSD performance of stochastic-gradient descent (SGD) to the order of O(σin2). We establish the convergence property of COVER and derive a tight closed-form mean-square deviation (MSD) performance expression. Our simulations illustrate the improved performance of COVER in terms of steady-state performance.