Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization

arXiv:2310.15976v4 Announce Type: replace Abstract: 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)/sqrt{nT}+arepsilon_{align}), where arepsilon_{align} measures the averaged loss of descent caused by component-sign misalignment. A horizon-tuned constant stepsize improves the vanishing term to O(1/sqrt{nT}), and a remaining-set alignment condition yields a residual-free O(1/sqrt{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(sqrt{d/T}) averaged ell_1-stationarity bound.

Source: arXiv cs.LG | 2026-08-12