mlsanityData to 7 Oct 2026

Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities

arXiv 2302.07615 ↗First posted 15 Feb 2023math.OC cs.DC cs.GTcited by 7

Not on the map. Why?

Abstract (arXiv)

Variational inequalities are a broad and flexible class of problems that includes minimization, saddle point, and fixed point problems as special cases. Therefore, variational inequalities are used in various applications ranging from equilibrium search to adversarial learning. With the increasing size of data and models, today's instances demand parallel and distributed computing for real-world machine learning problems, most of which can be represented as variational inequalities. Meanwhile, most distributed approaches have a significant bottleneck - the cost of communications. The three main techniques to reduce the total number of communication rounds and the cost of one such round are the similarity of local functions, compression of transmitted information, and local updates. In this paper, we combine all these approaches. Such a triple synergy did not exist before for variational inequalities and saddle problems, nor even for minimization problems. The methods presented in this paper have the best theoretical guarantees of communication complexity and are significantly ahead of other methods for distributed variational inequalities. The theoretical results are confirmed by adversarial learning experiments on synthetic and real datasets.

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

Builds on

60 of 90 references.

References · 60

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  5. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  7. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  8. 2018Sparsified SGD with Memorycited by 373
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  10. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  11. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  12. 2018The Convergence of Sparsified Gradient Methodscited by 228
38 more
  1. 2017Training GANs with Optimismcited by 217
  2. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  3. 2019A Survey on Distributed Machine Learningcited by 187
  4. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  5. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  6. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  7. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  8. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  9. 2020On Biased Compression for Distributed Learningcited by 140
  10. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  12. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  13. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  14. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  15. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  16. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  17. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  18. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  19. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  20. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  21. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  22. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  23. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  24. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  25. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  26. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  27. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  28. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  29. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  30. 2013On the Convergence Properties of Non-Euclidean Extragradient Methods for Variational Inequalities with Generalized Monotone Operatorscited by 29
  31. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  32. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  33. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  34. 2022Near-Optimal Sparse Allreduce for Distributed Deep Learningcited by 23
  35. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  36. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  37. 2019On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyondcited by 18
  38. 2019A Decentralized Proximal Point-type Method for Saddle Point Problemscited by 17

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 0; 2026: 2.

7 papers.

  1. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  2. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 6
  3. 2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
  4. 2024Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similaritycited by 2
  5. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  6. 2026Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problemscited by 0
  7. 2026Byzantine-Robust Optimization under (L0, L1)-Smoothnesscited by 0