Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization
This work addresses a theoretical gap for practitioners using sign-based optimization in machine learning, though it is incremental as it builds on existing signSGD methods.
The paper tackles the lack of theoretical understanding for signSGD with random reshuffling (SignRR), a practical nonconvex optimization method, by developing the first convergence analysis showing an expected gradient norm bound of O(log(nT)/√(nT) + σ). It introduces two improved algorithms, SignRVR and SignRVM, which achieve faster rates of O(log(nT)/√(nT) + log(nT)√n/√T), and extends these to distributed settings with experimental validation.
signSGD is popular in nonconvex optimization due to its communication efficiency. Yet, existing analyses typically assume data are sampled with replacement in each iteration, contradicting a common practical implementation where data are randomly reshuffled and sequentially fed into the algorithm. This gap leaves the theoretical understanding of the more practical algorithm, signSGD with random reshuffling (SignRR), largely unexplored. We develop the first analysis of SignRR to identify the core technical challenge that prevents a thorough convergence analysis of this method. In particular, given a dataset of size $n$ and $T$ epochs, we show that the expected gradient norm of SignRR is upper bounded by $O(\log(nT)/\sqrt{nT} + σ)$, where $σ$ is the averaged conditional mean square error that may not vanish. To tackle this limitation, we develop two new sign-based algorithms under random reshuffling: SignRVR, which incorporates variance-reduced gradients, and SignRVM, which integrates momentum-based updates. Both algorithms achieve a faster convergence rate of ${O}(\log(nT)/\sqrt{nT} +\log(nT)\sqrt{n}/\sqrt{T})$. We further extend our algorithms to a distributed setting, with a convergence rate of ${O}(\log(n_0T)/\sqrt{n_0T} +\log (n_0T)\sqrt{n_0}/\sqrt{T})$, where $n_0$ is the size of the dataset of a single machine. These results mark the first step towards the theoretical understanding of practical implementation of sign-based optimization algorithms. Finally, we back up our theoretical findings through experiments on simulated and real-world problems, verifying that randomly reshuffled sign methods match or surpass existing baselines.