2021/02/12 by Konstantin Mishchenko, Mishchenko, Konstantin, Ahmed Khaled +3 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC
paper · pdf · doi:10.48550/arxiv.2102.06704
21 pages, 2 figures, 3 algorithms
arxiv created 2021/02/12 · openalex publication_date 2021/02/12 · arxiv updated 2021/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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.