mlsanityData to 14 Oct 2026

Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems

arXiv 2309.00997 ↗First posted 2 Sep 2023cs.LG cs.DC cs.DScited by 0

Not on the map. Why?

Abstract (arXiv)

We consider a class of non-smooth strongly convex-strongly concave saddle point problems in a decentralized setting without a central server. To solve a consensus formulation of problems in this class, we develop an inexact primal dual hybrid gradient (inexact PDHG) procedure that allows generic gradient computation oracles to update the primal and dual variables. We first investigate the performance of inexact PDHG with stochastic variance reduction gradient (SVRG) oracle. Our numerical study uncovers a significant phenomenon of initial conservative progress of iterates of IPDHG with SVRG oracle. To tackle this, we develop a simple and effective switching idea, where a generalized stochastic gradient (GSG) computation oracle is employed to hasten the iterates' progress to a saddle point solution during the initial phase of updates, followed by a switch to the SVRG oracle at an appropriate juncture. The proposed algorithm is named Decentralized Proximal Switching Stochastic Gradient method with Compression (C-DPSSG), and is proven to converge to an ε-accurate saddle point solution with linear rate. Apart from delivering highly accurate solutions, our study reveals that utilizing the best convergence phases of GSG and SVRG oracles makes C-DPSSG well suited for obtaining solutions of low/medium accuracy faster, useful for certain applications. Numerical experiments on two benchmark machine learning applications show C-DPSSG's competitive performance which validate our theoretical findings. The codes used in the experiments can be found hrefhttps://github.com/chhavisharma123/C-DPSSG-CDC2023here.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 20 of its 36 references that are in the map. First posted on arXiv 2 Sep 2023.

Builds on

20 of 36 references.

References · 20

  1. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 478
  2. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  3. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 221
  4. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  5. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
  6. 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 43
  7. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  8. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  9. 2020Linear Convergent Decentralized Optimization with Compressioncited by 22
  10. 2019Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structurecited by 15
  11. 2015Stop Wasting My Gradients: Practical SVRGcited by 14
  12. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
8 more
  1. 2022Decentralized Stochastic Gradient Descent Ascent for Finite-Sum Minimax Problemscited by 11
  2. 2021Decentralized Distributed Optimization for Saddle Point Problemscited by 10
  3. 2022Communication-Efficient Distributionally Robust Decentralized Learningcited by 10
  4. 2021Distributed Saddle-Point Problems Under Similaritycited by 8
  5. 2021Decentralized Composite Optimization with Compressioncited by 7
  6. 2015Distributed saddle-point subgradient algorithms with Laplacian averagingcited by 5
  7. 2022Distributed saddle point problems for strongly concave-convex functionscited by 3
  8. 2022Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problemscited by 1

Built on by

Not cited yet.