mlsanityData to 7 Oct 2026

Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis

arXiv 2304.07504 ↗First posted 15 Apr 2023cs.LG math.OC stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We study finite-sum distributed optimization problems involving a master node and n-1 local nodes under the popular δ-similarity and μ-strong convexity conditions. We propose two new algorithms, SVRS and AccSVRS, motivated by previous works. The non-accelerated SVRS method combines the techniques of gradient sliding and variance reduction and achieves a better communication complexity of tildeO(n + √nδ/μ) compared to existing non-accelerated algorithms. Applying the framework proposed in Katyusha X, we also develop a directly accelerated version named AccSVRS with the tildeO(n + n3/4√δ/μ) communication complexity. In contrast to existing results, our complexity bounds are entirely smoothness-free and exhibit superiority in ill-conditioned cases. Furthermore, we establish a nearly matched lower bound to verify the tightness of our AccSVRS method.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 48 of its 63 references that are in the map. First posted on arXiv 15 Apr 2023.

Builds on

48 of 63 references.

References · 48

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  3. 2021Federated Learning for Smart Healthcare: A Surveycited by 182
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  5. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  6. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  7. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  8. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  9. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  10. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  11. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  12. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
36 more
  1. 2021Acceleration Methodscited by 48
  2. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  3. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  4. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
  5. 2021Federated Learning Meets Natural Language Processing: A Surveycited by 42
  6. 2015An optimal randomized incremental gradient methodcited by 32
  7. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  8. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  9. 2022A Multi-agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learningcited by 28
  10. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  11. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 19
  12. 2021Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reductioncited by 19
  13. 2016A Simple Practical Accelerated Method for Finite Sumscited by 18
  14. 2016Faster Eigenvector Computation via Shift-and-Invert Preconditioningcited by 18
  15. 2019On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyondcited by 18
  16. 2022Faster federated optimization under second-order similaritycited by 18
  17. 2021Acceleration in Distributed Optimization under Similaritycited by 17
  18. 2018Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimizationcited by 15
  19. 2014Gradient Sliding for Composite Optimizationcited by 14
  20. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
  21. 2014A Lower Bound for the Optimization of Finite Sumscited by 13
  22. 2019On the Convergence of SARAH and Beyondcited by 10
  23. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  24. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  25. 2016Accelerated gradient sliding for structured convex optimizationcited by 7
  26. 2021Newton Method over Networks is Fast up to the Statistical Precisioncited by 7
  27. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  28. 2021An Accelerated Second-Order Method for Distributed Stochastic Optimizationcited by 6
  29. 2018Breaking the Span Assumption Yields Fast Finite-Sum Minimizationcited by 5
  30. 2019Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimizationcited by 4
  31. 2020Oracle Complexity Separation in Convex Optimizationcited by 4
  32. 2022Adaptive Third-Order Methods for Composite Convex Optimizationcited by 4
  33. 2023SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimizationcited by 4
  34. 2020On the Optimal Combination of Tensor Optimization Methodscited by 3
  35. 2021High-order methods beyond the classical complexity bounds, II: inexact high-order proximal-point methods with segment searchcited by 3
  36. 2021One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 2; 2026: 1.

11 papers.

  1. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
  2. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 6
  3. 2024SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learningcited by 3
  4. 2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
  5. 2024Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similaritycited by 2
  6. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 1
  7. 2024Fully First-Order Methods for Decentralized Bilevel Optimizationcited by 1
  8. 2025Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimizationcited by 1
  9. 2025Non-Convex Federated Optimization under Cost-Aware Client Selectioncited by 1
  10. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  11. 2026Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problemscited by 0