SGD-rα: A real-time α-suffix averaging method for SGD with biased gradient estimates

摘要

Stochastic gradient descent (SGD) is a simple and efficient method for solving large-scale stochastic optimization problems in machine learning. It has been shown that the convergence rate of SGD can be improved by alpha-suffix averaging technique, abbreviated as SGD-alpha. Classic analysis usually requires the assumption of unbiased gradient estimates, which is not suitable for many practical applications of SGD-alpha such as non-independently and identically distributed (non-i.i.d.) scenarios. Another limitation is that SGD-alpha needs to store all iterates in memory and thus cannot be implemented on-the-fly. To address the issues, we employ rounding technique to propose a real-time version of SGD-alpha (named SGD-r alpha), which can iteratively calculate the alpha-suffix averaging and has the same convergence rate as that of SGD-alpha. In particular, SGD-r alpha with biased gradient estimates can obtain sublinear convergence rate for strongly convex objectives. Numerical experiments on the benchmark datasets have shown the characteristics of SGD-r alpha and corroborated the theoretical results. The implementation of SGD-r alpha is available at:https://github.com/xudp100/SGD-ra. (C) 2022 Elsevier B.V. All rights reserved.