# Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization

arXiv: https://arxiv.org/abs/2310.15976 · HTML: https://mlsanity.com/paper/2310.15976/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 68 references that are in the map.
- First posted on arXiv 24 Oct 2023.

## Builds on (most cited first, 30 of 41)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients](https://mlsanity.com/paper/1705.07774/) (2017)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)

## Built on by (most cited first, 2 of 2)

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)

## Abstract (arXiv)

signSGD is attractive in nonconvex optimization because it communicates sign-valued rather than full-precision gradients. Several standard analyses assume independent stochastic-gradient samples, whereas a common finite-sum implementation reshuffles the data and processes them sequentially. We study this variant, signSGD with random reshuffling (SignRR), and show that reshuffling does not in general repair the bias created by discarding gradient magnitudes. In particular, on a one-dimensional two-component strongly convex quadratic, the expected gradient norm at every SignRR inner iterate equals 1/2. We complement this impossibility result with an alignment-explicit finite-time bound O(log(nT)/√nT+varepsilonalign), where varepsilonalign measures the averaged loss of descent caused by component-sign misalignment. A horizon-tuned constant stepsize improves the vanishing term to O(1/√nT), and a remaining-set alignment condition yields a residual-free O(1/√nT) guarantee. The alignment term is upper bounded by twice the averaged mean absolute gradient error and, in turn, by twice an averaged coordinatewise conditional root-mean-square error. As a variance-reduced alternative, we analyze SignRVR, which signs an SVRG estimator anchored at the beginning of every epoch. A pathwise argument gives a residual-free guarantee with an O(√d/T) averaged ℓ1-stationarity bound.