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

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

Problem Statement
The paper addresses the challenge of distributed optimization in large-scale networked systems where agents cooperatively minimize a global objective function while maintaining local data and computation. The study focuses on two critical practical constraints: (1) the use of stochastic gradients (introducing gradient noise), and (2) finite-bit communication modeled by random, unbiased quantization. Existing methods often rely on restrictive assumptions such as strong convexity, shared minimizers across agents, or server-based architectures. Furthermore, prior work on quantized distributed optimization frequently yields only neighborhood convergence under constant step-sizes or requires specific structural assumptions for exact convergence. The authors aim to develop a decentralized algorithm that provides convergence guarantees under relaxed global geometry (specifically Restricted Secant Inequality and Polyak–Łojasiewicz conditions) without assuming a shared minimizer or strong convexity.

Methodology: q-PDGD
The authors propose q-PDGD, a quantized stochastic primal–dual gradient descent algorithm. The method operates over a connected, undirected weighted graph where agents communicate quantized versions of their primal variables.

• Algorithm Dynamics: At each iteration, agents update primal variables ($x_i$) and dual variables ($v_i$). The primal update incorporates a local stochastic gradient, a consensus term driven by the Laplacian of the network, and the dual variable. The dual variable acts as a disagreement-tracking mechanism, accumulating consensus errors caused by quantized mixing and feeding them back into the primal dynamics to mitigate persistent disagreement.
• Quantization Model: The communication is modeled using a stochastic quantizer that is unbiased and has bounded variance. This introduces a specific quantization noise term distinct from stochastic gradient noise.
• Geometric Assumptions: The analysis relies on two relaxed conditions weaker than strong convexity:
  1. Restricted Secant Inequality (RSI): Ensures a relationship between the gradient and the distance to the optimal set.
  2. Polyak–Łojasiewicz (PL) Inequality: A condition sufficient for linear convergence in deterministic settings, even for non-convex functions.

Key Contributions

1. Convergence under RSI without Shared Minimizers: The paper establishes convergence for q-PDGD under the RSI condition without assuming that the global minimizer is unique or that it minimizes each local function $f_i$. This contrasts with prior work (e.g., Dutta and Doan [2024]) which often required shared minimizers.
2. Explicit Tradeoffs with Step-Size Regimes:
   • Constant Step-Size: The authors prove that the algorithm converges linearly to an explicit neighborhood of the optimal solution. The size of this neighborhood is determined by a linear combination of gradient noise variance, quantization distortion, and network connectivity properties (specifically the spectral gap of the Laplacian).
   • Diminishing Step-Size: Under the RSI condition, a diminishing step-size ($O(1/k)$) achieves an $O(1/k)$ convergence rate for the mean squared error, matching the best-known rates for centralized stochastic optimization in oracle complexity, while guaranteeing exact consensus and convergence to an optimal solution.
3. PL Regime Analysis: Under the weaker PL inequality, the authors demonstrate linear convergence to a noise-dominated neighborhood. They explicitly characterize how network structure and compression affect the steady-state error.
4. Network Scaling Analysis: The paper derives how the residual error constants scale with the number of agents ($n$) and the network condition number ($\kappa_L$). It reveals that quantization error propagation is sensitive to network spectral properties, while gradient noise benefits from variance reduction via larger networks.

Experimental Results
The theoretical predictions are validated through simulations on non-convex objectives and distributed least squares problems:

• Convergence Behavior: Experiments confirm that constant step-sizes lead to linear convergence followed by a plateau at a noise-dependent neighborhood, while diminishing step-sizes drive the error to zero at an $O(1/k)$ rate.
• Network Scaling: The steady-state error scales as predicted with respect to network size and spectral properties.
• Baseline Comparison: On distributed least squares, q-PDGD significantly outperforms baselines like Quantized Distributed Gradient Descent (q-DGD), CHOCO-SGD, and DCSG, reaching target optimality thresholds in fewer iterations.
• Deep Learning Robustness: In experiments on image classification (MNIST and Fashion-MNIST) using 4-bit quantization, q-PDGD demonstrates superior consensus stability (lower disagreement among agents) compared to other quantized decentralized methods, even though the global geometry assumptions (RSI/PL) are not formally satisfied by the non-convex deep learning loss landscapes.

Significance and Claims
The paper positions q-PDGD as a principled tool for communication-constrained distributed learning. Its primary significance lies in providing provable guarantees for stochastic, quantized, decentralized optimization under relaxed geometric assumptions (RSI/PL) that do not require strong convexity or shared minimizers. The authors claim that the primal-dual tracking mechanism effectively absorbs and mitigates consensus errors induced by random quantization, allowing the method to maintain robust convergence rates even in regimes where theoretical assumptions are formally violated. The results offer a clear decomposition of how quantization distortion, stochastic variance, and graph connectivity jointly determine the final accuracy of distributed learning systems.