# Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 24 references that are in the map.
- First posted on arXiv 9 Jun 2026.

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

- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Double Quantization for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1805.10111/) (2018)
- [Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication](https://mlsanity.com/paper/1401.4432/) (2014)
- [Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Condition](https://mlsanity.com/paper/1909.03282/) (2019)
- [Provable Privacy Advantages of Decentralized Federated Learning via Distributed Optimization](https://mlsanity.com/paper/2407.09324/) (2024)
- [Quantized Consensus ADMM for Multi-Agent Distributed Optimization](https://mlsanity.com/paper/1510.08736/) (2015)
- [Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy](https://mlsanity.com/paper/1810.11507/) (2018)
- [Quantization Design for Distributed Optimization](https://mlsanity.com/paper/1504.02317/) (2015)
- [Distributed Optimization with Quantized Gradient Descent](https://mlsanity.com/paper/2211.10855/) (2022)
- [Quantized Primal-Dual Algorithms for Network Optimization with Linear Convergence](https://mlsanity.com/paper/2111.08180/) (2021)

## Abstract (arXiv)

We study distributed optimization with stochastic gradients and finite-bit communication modeled by random (unbiased) quantization. We propose q-PDGD, a quantized stochastic primal-dual method, and analyze it under relaxed global geometry. Under restricted secant inequality (RSI), a constant step-size yields linear contraction to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity, while a diminishing step-size achieves O(1/k) convergence without shared-minimizer assumptions. Under Polyak-Lojasiewicz (PL) inequality, we obtain linear-to-neighborhood convergence in the same stochastic quantized setting. Our results match the best-known centralized stochastic rates in oracle complexity, and are supported by experiments demonstrating the predicted tradeoffs between quantization level, step-size choice, and graph structure.