mlsanityData to 7 Oct 2026

Optimal Algorithms for Decentralized Stochastic Variational Inequalities

arXiv 2202.02771 ↗First posted 6 Feb 2022math.OC cs.DC cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

Variational inequalities are a formalism that includes games, minimization, saddle point, and equilibrium problems as special cases. Methods for variational inequalities are therefore universal approaches for many applied tasks, including machine learning problems. This work concentrates on the decentralized setting, which is increasingly important but not well understood. In particular, we consider decentralized stochastic (sum-type) variational inequalities over fixed and time-varying networks. We present lower complexity bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available literature not only in the decentralized stochastic case, but also in the decentralized deterministic and non-distributed stochastic cases. Experimental results confirm the effectiveness of the presented algorithms.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 32 of its 76 references that are in the map. First posted on arXiv 6 Feb 2022.

Builds on

32 of 76 references.

References · 32

  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. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,609
  5. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  6. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  7. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  8. 2019FreeLB: Enhanced Adversarial Training for Natural Language Understandingcited by 261
  9. 2017Training GANs with Optimismcited by 217
  10. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  11. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  12. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
20 more
  1. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  2. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  3. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  4. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  5. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  7. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  8. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  9. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  10. 2019Variance Reduction for Matrix Gamescited by 37
  11. 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 37
  12. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  13. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  14. 2020An Optimal Algorithm for Decentralized Finite Sum Optimizationcited by 19
  15. 2021Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networkscited by 19
  16. 2019Training GANs with Centripetal Accelerationcited by 13
  17. 2021On Accelerated Methods for Saddle-Point Problems with Composite Structurecited by 13
  18. 2021Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimizationcited by 11
  19. 2021A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problemscited by 9
  20. 2021Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networkscited by 7

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 7; 2024: 2; 2025: 1.

14 papers.

Sort:

  1. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  2. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  3. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  4. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  5. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  6. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  7. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  8. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  9. 2022On Scaled Methods for Saddle Point Problemscited by 3
  10. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  11. 2024Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networkscited by 1
  12. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
2 more
  1. 2023Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problemscited by 0
  2. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0