mlsanityData to 7 Oct 2026

Proximal and Federated Random Reshuffling

arXiv 2102.06704 ↗First posted 12 Feb 2021cs.LG math.OCcited by 33

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 27 of its 54 references that are in the map. First posted on arXiv 12 Feb 2021.

Builds on

27 of 54 references.

References · 27

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  8. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  9. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  10. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  11. 2014Stochastic Optimization with Importance Samplingcited by 91
  12. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
15 more
  1. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  2. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  3. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  4. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  5. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  6. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  7. 2020Federated Composite Optimizationcited by 49
  8. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  9. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  10. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  11. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 34
  12. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  13. 2019The Practicality of Stochastic Optimization in Imaging Inverse Problemscited by 9
  14. 2014A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimizationcited by 3
  15. 2018ASVRG: Accelerated Proximal SVRGcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 11; 2023: 4; 2024: 9; 2025: 2; 2026: 3.

33 papers.

Sort:

  1. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  2. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  3. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  4. 2022FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learningcited by 23
  5. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  6. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  7. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  8. 2022Faster federated optimization under second-order similaritycited by 18
  9. 2021Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orderscited by 13
  10. 2023Federated Learning with Regularized Client Participationcited by 13
  11. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  12. 2022Federated Random Reshuffling with Compression and Variance Reductioncited by 11
21 more
  1. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  2. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  3. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  4. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  5. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  6. 2025Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Accelerationcited by 7
  7. 2023A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimizationcited by 4
  8. 2024A Unified Theory of Stochastic Proximal Point Methods without Smoothnesscited by 4
  9. 2024Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learningcited by 3
  10. 2021Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimizationcited by 2
  11. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 1
  12. 2022Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneitycited by 0
  13. 2022Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothnesscited by 0
  14. 2023Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraintscited by 0
  15. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  16. 2024Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimizationcited by 0
  17. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0
  18. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 0
  19. 2026Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learningcited by 0
  20. 2026Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensionscited by 0
  21. 2026Beyond Class Marginals: Bounding Rehearsal Gaps without Freezing Class Co-occurrencecited by 0