  In this paper, we consider distributed optimization problems where $n$
agents, each possessing a local cost function, collaboratively minimize the
average of the local cost functions over a connected network. To solve the
problem, we propose a distributed random reshuffling (D-RR) algorithm that
invokes the random reshuffling (RR) update in each agent. We show that D-RR
inherits favorable characteristics of RR for both smooth strongly convex and
smooth nonconvex objective functions. In particular, for smooth strongly convex
objective functions, D-RR achieves $\mathcal{O}(1/T^2)$ rate of convergence
(where $T$ counts epoch number) in terms of the squared distance between the
iterate and the global minimizer. When the objective function is assumed to be
smooth nonconvex, we show that D-RR drives the squared norm of gradient to $0$
at a rate of $\mathcal{O}(1/T^{2/3})$. These convergence results match those of
centralized RR (up to constant factors) and outperform the distributed
stochastic gradient descent (DSGD) algorithm if we run a relatively large
number of epochs. Finally, we conduct a set of numerical experiments to
illustrate the efficiency of the proposed D-RR method on both strongly convex
and nonconvex distributed optimization problems.
