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

Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti, Mayank Baranwal
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:5967-5996, 2026.

Abstract

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 $\mathcal{O}(1/k)$ convergence without shared-minimizer assumptions. Under Polyak–{Ł}ojasiewicz (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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-sarkar26a, title = {Quantized Stochastic Primal–Dual Methods for Distributed Optimization under Relaxed Global Geometry}, author = {Sarkar, Susmit and Raghuvanshi, Abhinav and Chakrabarti, Kushal and Baranwal, Mayank}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {5967--5996}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/sarkar26a/sarkar26a.pdf}, url = {https://proceedings.mlr.press/v337/sarkar26a.html}, abstract = {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 $\mathcal{O}(1/k)$ convergence without shared-minimizer assumptions. Under Polyak–{Ł}ojasiewicz (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.} }
Endnote
%0 Conference Paper %T Quantized Stochastic Primal–Dual Methods for Distributed Optimization under Relaxed Global Geometry %A Susmit Sarkar %A Abhinav Raghuvanshi %A Kushal Chakrabarti %A Mayank Baranwal %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-sarkar26a %I PMLR %P 5967--5996 %U https://proceedings.mlr.press/v337/sarkar26a.html %V 337 %X 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 $\mathcal{O}(1/k)$ convergence without shared-minimizer assumptions. Under Polyak–{Ł}ojasiewicz (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.
APA
Sarkar, S., Raghuvanshi, A., Chakrabarti, K. & Baranwal, M.. (2026). Quantized Stochastic Primal–Dual Methods for Distributed Optimization under Relaxed Global Geometry. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:5967-5996 Available from https://proceedings.mlr.press/v337/sarkar26a.html.

Related Material