Skip to yearly menu bar Skip to main content


Poster

Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction

Wei Jiang · Sifan Yang · Wenhao Yang · Lijun Zhang

West Ballroom A-D #6011
[ ]
[ Paper [ Poster [ OpenReview
Wed 11 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: 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 O(d1/2T1/4), where d represents the dimension and T is the iteration number. In this paper, we improve this convergence rate to O(d1/2T1/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 O(m1/4d1/2T1/2), where m denotes the number of component functions. Furthermore, we investigate the heterogeneous majority vote in distributed settings and introduce two novel algorithms that attain improved convergence rates of O(d1/2T1/2+dn1/2) and O(d1/4T1/4) respectively, outperforming the previous results of O(dT1/4+dn1/2) and O(d3/8T1/8), where n represents the number of nodes. Numerical experiments across different tasks validate the effectiveness of our proposed methods.

Chat is not available.