# Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems

arXiv: https://arxiv.org/abs/2205.14452 · HTML: https://mlsanity.com/paper/2205.14452/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 28 May 2022.

## Builds on (most cited first, 26 of 26)

- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems](https://mlsanity.com/paper/1810.10207/) (2018)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Linear Convergent Decentralized Optimization with Compression](https://mlsanity.com/paper/2007.00232/) (2020)
- [Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structure](https://mlsanity.com/paper/1904.10112/) (2019)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Decentralized Distributed Optimization for Saddle Point Problems](https://mlsanity.com/paper/2102.07758/) (2021)
- [A new primal-dual algorithm for minimizing the sum of three functions with a linear operator](https://mlsanity.com/paper/1611.09805/) (2016)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Distributed saddle-point subgradient algorithms with Laplacian averaging](https://mlsanity.com/paper/1510.05169/) (2015)
- [A primal-dual fixed-point algorithm for minimization of the sum of three convex separable functions](https://mlsanity.com/paper/1512.09235/) (2015)
- [A generic adaptive restart scheme with applications to saddle point algorithms](https://mlsanity.com/paper/2006.08484/) (2020)

## Built on by (most cited first, 1 of 1)

- [Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems](https://mlsanity.com/paper/2309.00997/) (2023)

## Abstract (arXiv)

We develop two compression based stochastic gradient algorithms to solve a class of non-smooth strongly convex-strongly concave saddle-point problems in a decentralized setting (without a central server). Our first algorithm is a Restart-based Decentralized Proximal Stochastic Gradient method with Compression (C-RDPSG) for general stochastic settings. We provide rigorous theoretical guarantees of C-RDPSG with gradient computation complexity and communication complexity of order O( (1+δ)4 frac1L2kappaf2kappag2 frac1ε ), to achieve an ε-accurate saddle-point solution, where δ denotes the compression factor, kappaf and kappag denote respectively the condition numbers of objective function and communication graph, and L denotes the smoothness parameter of the smooth part of the objective function. Next, we present a Decentralized Proximal Stochastic Variance Reduced Gradient algorithm with Compression (C-DPSVRG) for finite sum setting which exhibits gradient computation complexity and communication complexity of order O left((1+δ) max kappaf2, √δkappa2fkappag,kappag  logleft(frac1εright) right). Extensive numerical experiments show competitive performance of the proposed algorithms and provide support to the theoretical results obtained.