New q-PDGD method matches centralized rates in distributed optimization with quantized communication

Distributed optimization faces a critical bottleneck: nodes must communicate gradients or parameters over bandwidth-limited channels. Sarkar et al. tackle this by introducing q-PDGD, a primal-dual method that combines stochastic gradients with random (unbiased) quantization to model finite-bit communication. The method operates under relaxed global geometry—specifically, restricted secant inequality (RSI) and Polyak-Lojasiewicz (PL) conditions, both weaker than strong convexity. With a constant step-size, q-PDGD contracts linearly to an explicit neighborhood determined by gradient noise, quantization distortion, and network connectivity. With diminishing step-sizes, it achieves O(1/k) convergence without requiring a shared minimizer across agents, making it practical for heterogeneous data distributions.

Under the PL inequality, q-PDGD also yields linear-to-neighborhood convergence in the same stochastic quantized setting. Notably, the oracle complexity matches the best-known centralized stochastic rates—meaning the method loses no theoretical efficiency despite the finite-bit communication limitation. Experiments confirm the predicted tradeoffs: coarser quantization slows convergence but reduces per-iteration bits, while step-size tuning and graph structure significantly affect the final accuracy. The work, accepted to UAI 2026, provides a rigorous foundation for deploying distributed learning systems where communication efficiency is paramount, such as federated learning on edge devices or multi-robot coordination.