Proximal and Federated Random Reshuffling
This work addresses optimization challenges in machine learning, particularly for composite convex problems and federated settings, but it appears incremental as it builds on Random Reshuffling with proximal and federated extensions.
The paper tackles the problem of finite-sum minimization by proposing Proximal and Federated Random Reshuffling (ProxRR and FedRR), which show superior convergence properties and complexities compared to existing methods like Proximal and Local SGD, with ProxRR being up to n times faster in cases where the proximal operator is expensive to compute.
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.