Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction

Sign stochastic gradient descent (signSGD) is a communication-efficient method that transmits only the sign of stochastic gradients for parameter updating. Existing literature has demonstrated that signSGD can achieve a convergence rate of \mathcal{O}(d {1/2}T {-1/4}), where d represents the dimension and T is the iteration number. In this paper, we improve this convergence rate to \mathcal{O}(d {1/2}T {-1/3}) by introducing the Sign-based Stochastic Variance Reduction (SSVR) method, which employs variance reduction estimators to track gradients and leverages their signs to update. For finite-sum problems, our method can be further enhanced to achieve a convergence rate of \mathcal{O}(m {1/4}d {1/2}T {-1/2}), where m denotes the number of component functions. Numerical experiments across different tasks validate the effectiveness of our proposed methods.