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. Furthermore, we investigate the
heterogeneous majority vote in distributed settings and introduce two novel
algorithms that attain improved convergence rates of
$\mathcal{O}(d^{1/2}T^{-1/2} + dn^{-1/2})$ and $\mathcal{O}(d^{1/4}T^{-1/4})$
respectively, outperforming the previous results of $\mathcal{O}(dT^{-1/4} +
dn^{-1/2})$ and $\mathcal{O}(d^{3/8}T^{-1/8})$, where $n$ represents the number
of nodes. Numerical experiments across different tasks validate the
effectiveness of our proposed methods.

本文介绍了 signSGD 方法及其收敛速率的改进，并引入了基于符号的随机方差缩减（SSVR）方法，通过引入方差缩减估计器来跟踪梯度并利用其符号进行更新；此外，还研究了分布式环境中的异构多数投票，引入了两种新算法以获得更好的收敛速率，通过数值实验验证了所提方法的有效性。