  Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD)
without replacement, is a popular and theoretically grounded method for
finite-sum minimization. We propose two new algorithms: Proximal and Federated
Random Reshuffing (ProxRR and FedRR). The first algorithm, ProxRR, solves
composite convex finite-sum minimization problems in which the objective is the
sum of a (potentially non-smooth) convex regularizer and an average of $n$
smooth objectives. We obtain the second algorithm, FedRR, as a special case of
ProxRR applied to a reformulation of distributed problems with either
homogeneous or heterogeneous data. We study the algorithms' convergence
properties with constant and decreasing stepsizes, and show that they have
considerable advantages over Proximal and Local SGD. In particular, our methods
have superior complexities and ProxRR evaluates the proximal operator once per
epoch only. When the proximal operator is expensive to compute, this small
difference makes ProxRR up to $n$ times faster than algorithms that evaluate
the proximal operator in every iteration. We give examples of practical
optimization tasks where the proximal operator is difficult to compute and
ProxRR has a clear advantage. Finally, we corroborate our results with
experiments on real data sets.
