Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction
<|reference_start|>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. 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.<|reference_end|>
@article{jiang2024efficient,
    title={Efficient Sign-Based Optimization: Accelerating Convergence via Variance
  Reduction},
    author={Wei Jiang, Sifan Yang, Wenhao Yang, Lijun Zhang},
    journal={arXiv preprint arXiv:2406.00489},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.00489},
    primaryClass={cs.LG math.OC}
}