mlsanityData to 14 Oct 2026

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

arXiv 2606.11339 ↗First posted 9 Jun 2026math.OC cs.AI cs.LGcited by 0

Not on the map. Why?

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.

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

17 of 24 references.

References · 17

  1. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  4. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  5. 2013On the Convergence of Decentralized Gradient Descentcited by 159
  6. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  7. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  8. 2019Decentralized Deep Learning with Arbitrary Communication Compressioncited by 111
  9. 2018Double Quantization for Communication-Efficient Distributed Optimizationcited by 19
  10. 2014Distributed convex optimization via continuous-time coordination algorithms with discrete-time communicationcited by 11
  11. 2019Exponential Convergence for Distributed Smooth Optimization Under the Restricted Secant Inequality Conditioncited by 6
  12. 2024Provable Privacy Advantages of Decentralized Federated Learning via Distributed Optimizationcited by 6
5 more
  1. 2015Quantized Consensus ADMM for Multi-Agent Distributed Optimizationcited by 5
  2. 2018Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategycited by 5
  3. 2015Quantization Design for Distributed Optimizationcited by 4
  4. 2022Distributed Optimization with Quantized Gradient Descentcited by 3
  5. 2021Quantized Primal-Dual Algorithms for Network Optimization with Linear Convergencecited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2021Communication-Efficient Distributed Optimization with Quantized Preconditioners
  2. 2024Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance
  3. 2024Quantization Avoids Saddle Points in Distributed Optimization
  4. 2024Truncated Non-Uniform Quantization for Distributed SGD
  5. 2023Q-SHED: Distributed Optimization at the Edge via Hessian Eigenvectors Quantization
  6. 2021Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget
  7. 2021Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
  8. 2021Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques