Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization¶

🕒 Published (v1): 2026-07-02 06:11 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper proposes DESC, a unified framework for decentralized stochastic subgradient methods with communication compression that handles nonsmooth, non-Clarke-regular objective functions (e.g., ReLU networks). By linking discrete iterates to continuous-time differential inclusions via conservative fields, it establishes the first global convergence guarantees for compressed decentralized optimization in this nonsmooth nonconvex setting. New compressed variants of momentum SGD and SignSGD are derived within the framework.

Problem¶

Existing convergence analyses for decentralized compressed optimization (CHOCO-SGD, BEER, C-GT, QDGD, etc.) assume objectives are either convex or smooth nonconvex (differentiable). Neural networks with ReLU/leaky-ReLU activations produce loss functions that are nonsmooth and lack Clarke regularity, meaning the chain rule fails for the Clarke subdifferential and the outputs of automatic differentiation (AD) algorithms lie outside $\partial f$. No prior work established convergence for decentralized compression-based methods under these non-Clarke-regular conditions.

Method¶

The paper introduces the DESC (Decentralized Stochastic Subgradient with Compression) framework as a single unified update: $$Z_{k+1} = (1-\theta_k)Z_k + \theta_k Z_k W + \theta_k E_{k+1}(W - \Sigma) - \eta_k(H_k + \Xi_{k+1})$$ where $Z_k \in \mathbb{R}^{m \times d}$ stacks local variables, $W$ is a doubly stochastic mixing matrix, $E_{k+1}$ captures compression error, $\Xi_{k+1}$ is stochastic gradient noise, and $\{\eta_k, \theta_k\}$ are two-timescale step-sizes with $\eta_k/\theta_k \to 0$.

Two sub-frameworks specialize DESC: - DESC-Unb: unbiased compression ($\mathbb{E}_\omega[\mathcal{C}(x,\omega)] = x$), covering nonsmooth extensions of QDGD. - DESC-Con: contractive compression ($\mathbb{E}[\|\mathcal{C}(x,\omega)-x\|^2] \le (1-\alpha)\|x\|^2$) with error-compensation via auxiliary copies $\hat{Z}_k$, covering nonsmooth CHOCO-SGD, BEER, C-GT.

Convergence is established by: 1. Replacing Clarke subdifferentials with conservative fields $D_f$ (which contain AD outputs for path-differentiable, e.g., definable, functions). 2. Constructing a noiseless differential inclusion whose trajectories track both the consensus-error iterates and the averaged iterates. 3. Applying a Lyapunov function argument (Lemma 2.14) to show convergence to the stable set $\mathcal{B}$ of $D_f$-critical points.

Step-sizes follow a three-timescale schedule $\{\eta_k, \theta_k, \gamma_k\}$ with $\eta_k = o(1/\log k)$.

Key Contributions¶

Unification: DESC subsumes gradient descent, gradient tracking, and momentum variants under both unbiased and contractive compression paradigms in a single scheme.
Convergence theory: First rigorous global convergence proof to $D_f$-critical points for a wide class of decentralized compressed methods on nonsmooth non-Clarke-regular objectives, including nonsmooth neural network training.
New methods: Compressed decentralized variants of momentum SGD and sign-based (SignSGD) methods with formal convergence guarantees, enabled by the framework.
ODE/differential-inclusion analysis extended to multi-agent consensus settings with compression noise.

Results¶

No quantitative benchmark numbers are reported in the provided text; results are described as "preliminary numerical experiments."
Experiments "empirically support theoretical results and highlight the communication-accuracy trade-off" of the new methods.
Theoretical rate: step-sizes satisfy $\eta_k = o(1/\log k)$ with two diminishing scales $\alpha = \Theta(K^{-(1-\delta)/4})$, $\varepsilon = \Theta(K^{-3(1-\delta)/4})$ for unbiased compression (Table 1).
Global convergence is established for all methods in the framework; prior methods (CHOCO-SGD, BEER, C-GT, QDGD) are shown as special cases with newly proved nonsmooth convergence.

Limitations¶

Step-sizes must satisfy a three-timescale decay schedule ($\eta_k = o(1/\log k)$), which is significantly slower than standard SGD rates and may be impractical for large-scale training.
Only convergence to critical points is guaranteed; no convergence rate (e.g., $\epsilon$-critical point complexity) is provided in the nonsmooth case.
Numerical experiments are preliminary; no large-scale deep learning benchmarks (e.g., ResNet, transformer training) are reported.
Requires objectives to be path-differentiable and coercive; does not cover unbounded loss landscapes without modification.
Analysis assumes undirected connected graphs; directed graph settings are left as future work.

Relevance to Agentic AI / LLM Agents¶

Multi-agent LLM systems and distributed RL agents increasingly require on-device or federated training where bandwidth is constrained, making communication-compressed decentralized optimization directly applicable. This work provides the first theoretical underpinning for training nonsmooth neural networks (the kind used in all modern LLM-based agents) in a decentralized compressed setting, filling a critical gap. For agentic RL with heterogeneous agents learning locally and synchronizing over limited channels, DESC offers a principled basis for sign-compressed or quantized gradient exchange without sacrificing convergence. The conservative-field framework is also notable as it precisely characterizes what AD computes in practice, making the theory actionable for PyTorch/JAX-based agent training pipelines.