  signSGD is popular in nonconvex optimization due to its communication
efficiency. Yet, existing analyses of signSGD rely on assuming that data are
sampled with replacement in each iteration, contradicting the practical
implementation where data are randomly reshuffled and sequentially fed into the
algorithm. We bridge this gap by proving the first convergence result of
signSGD with random reshuffling (SignRR) for nonconvex optimization. Given the
dataset size $n$, the number of epochs of data passes $T$, and the variance
bound of a stochastic gradient $\sigma^2$, we show that SignRR has the same
convergence rate $O(\log(nT)/\sqrt{nT} + \|\sigma\|_1)$ as signSGD
\citep{bernstein2018signsgd}. We then present SignRVR and SignRVM, which
leverage variance-reduced gradients and momentum updates respectively, both
converging at $O(\log (nT)/\sqrt{nT} + \log (nT)\sqrt{n}/\sqrt{T})$. In
contrast with the analysis of signSGD, our results do not require an extremely
large batch size in each iteration to be of the same order as the total number
of iterations \citep{bernstein2018signsgd} or the signs of stochastic and true
gradients match element-wise with a minimum probability of 1/2
\citep{safaryan2021stochastic}. We also extend our algorithms to cases where
data are distributed across different machines, yielding dist-SignRVR and
dist-SignRVM, both converging at $O(\log (n_0T)/\sqrt{n_0T} + \log
(n_0T)\sqrt{n_0}/\sqrt{T})$, where $n_0$ is the dataset size of a single
machine. 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.
