aiqbench analysis
This paper introduces q-PDGD, a distributed optimization algorithm that achieves convergence rates matching centralized benchmarks despite finite-bit communication and relaxed geometric assumptions. By explicitly modeling quantization distortion and network connectivity, the method offers theoretical guarantees for both constant and diminishing step-sizes, providing a rigorous framework for efficient training in bandwidth-constrained environments. The results are validated through experiments that map the tradeoffs between quantization levels, step-size strategies, and graph topology.
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
arXiv:2606.11339v1 Announce Type: cross 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 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.
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 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.
Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Systems and Control (eess.SY); Machine Learning (stat.ML)
arXiv:2606.11339 [math.OC]
(or arXiv:2606.11339v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2606.11339 arXiv-issued DOI via DataCite (pending registration)
Full text under the publisher's open licence · 138 words
Related coverage
Scaling Decision Optimization to 100 Million Variables and Beyond with mPDLP in NVIDIA cuOpt
NVIDIA · Oct 7, 2026
On the Computational and Statistical Efficiency of the Empirical Maximum Entropy on the Mean Method
arXiv · Aug 31, 2026
Efficient Preconditioned Optimization Methods with Frequent Directions
arXiv · Oct 14, 2026
Distributed Optimization via Energy Conservation Laws in Dilated Coordinates
arXiv · Jul 23, 2026