In decentralized machine learning, a network of independent agents collaborates to minimize a global objective function without relying on a central coordinator. When the objective functions are smooth and differentiable, agents can compute local gradients, share parameters with their immediate neighbors, and smoothly track the global average to reach a consensus.
However, modern statistical learning frequently requires solving composite optimization problems. In these scenarios, the global objective combines smooth, agent-specific loss functions with a non-smooth, non-differentiable regularizer:
$$\min_{x} \frac{1}{n} \sum_{i=1}^n f_i(x) + g(x)$$
Here, each $f_i(x)$ represents a local differentiable loss (such as a logistic regression or least-squares loss), while $g(x)$ represents a global non-smooth penalty (such as the $L_1$ norm for feature sparsity or the nuclear norm for low-rank matrix structures). As highlighted by Yajie Bao et al. in Fast Composite Optimization and Statistical Recovery in Federated Learning, embedding these non-smooth regularizers into distributed environments is critical for high-dimensional statistical recovery, yet it introduces a fundamental mathematical conflict with network consensus.
The Core Conflict: Non-Commutativity of Consensus and Proximity
To understand why non-smoothness breaks standard decentralized optimization, consider how a single centralized machine handles a non-smooth term $g(x)$. Instead of standard gradient descent, it uses a proximal gradient step. After taking a step along the gradient of the smooth term, it applies the proximal operator associated with $g(x)$:
$$\text{prox}_{\gamma g}(v) = \arg\min_{x} \left( g(x) + \frac{1}{2\gamma} \|x - v\|^2 \right)$$
The proximal operator acts as a generalized projection, mapping the continuous parameter space toward structural configurations like exact sparsity.
In a decentralized network, agents must simultaneously minimize their local functions and force their local parameters into agreement ($x_1 = x_2 = \dots = x_n$). If we naively combine consensus with proximal steps—for instance, by having each agent average its neighbors' parameters and then apply $\text{prox}_{\gamma g}$ locally—the algorithm fails to converge to the true global optimum.
The mathematical bottleneck is that the proximal operator is non-linear and does not commute with the network's consensus matrix. As explained by Kun Yuan et al. in A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization, averaging the results of local proximal operations is fundamentally different from applying a proximal operation to the average of the states:
$$\frac{\text{prox}(v_1) + \text{prox}(v_2)}{2} \neq \text{prox}\left(\frac{v_1 + v_2}{2}\right)$$
This non-commutativity introduces a persistent bias at every iteration. If agents use a fixed step size, they will stabilize around an incorrect solution; if they use a diminishing step size to eliminate the bias, their convergence rate plummets from linear to a much slower sub-linear rate.
Resolving the Conflict via Operator Splitting
To achieve fast, linear convergence rates, decentralized algorithms must mathematically decouple the network consensus step from the non-smooth proximal step. This is accomplished by reformulating the problem using operator splitting and primal-dual tracking.
Instead of forcing the primal variables to satisfy both consensus and regularization simultaneously in a single step, algorithms introduce dual variables that track the disagreement between neighboring nodes over time. This dual tracking acts as a memory mechanism, compensating for the non-commutativity of the proximal operator by dynamically adjusting the local inputs to the proximal step.
Jinming Xu et al. established a unified framework in Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis (building on A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization), demonstrating that popular smooth decentralized algorithms (such as EXTRA and NIDS) can be viewed as specific instances of monotone operator splitting. By treating consensus and proximity as separate operators in an augmented primal-dual space, this framework allows step-size selections to be completely decoupled from the network topology, enabling decentralized networks to match the linear convergence rates of centralized proximal gradient methods.
Smooth Step (Gradients) ──> Dual Tracking (Consensus Correction) ──> Proximal Step (Non-Smooth Structure)
│ │
└─────────────────────────── Next Iteration Loop ─────────────────────────────┘
However, there is a strict theoretical limit to this acceleration. Ernest K. Ryu et al. proved in Decentralized Proximal Gradient Algorithms With Linear Convergence Rates that while a shared global non-smooth penalty $g(x)$ permits linear convergence, it is theoretically impossible to maintain a linear rate in the worst case if each agent has its own unique, heterogeneous non-smooth term $g_i(x)$. When constraints are localized to specific subsets of nodes, specialized architectures—such as the dual coupled diffusion strategy proposed by Kun Yuan et al. in A Proximal Diffusion Strategy for Multiagent Optimization With Sparse Affine Constraints—must be used to restrict dual communication exclusively to the nodes bound by those specific constraints.
Adapting to Asymmetric and Dynamic Networks
Real-world decentralized systems rarely feature static, bidirectional communication. Algorithms must remain robust under two challenging network topologies: directed graphs and time-varying connections.
Directed Graphs and Asymmetric Bias
In directed networks, Node A can send data to Node B, but Node B cannot reply. This asymmetry breaks the conservation of mass in standard consensus, causing information to pool heavily in highly connected nodes. To fix this, the authors of ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks combined gradient tracking with a push-sum protocol, which uses auxiliary variables to track and divide out the network's asymmetric weights.
To handle non-smooth terms in these environments, Jinshan Zeng et al. developed PG-ExtraPush in A Fast Proximal Gradient Algorithm for Decentralized Composite Optimization over Directed Networks. This method integrates the proximal operator directly into the push-sum consensus loop, allowing agents to solve non-smooth composite problems over directed graphs with a fixed step size.
Time-Varying Networks and Fundamental Lower Bounds
When network connections drop and shift dynamically over time, maintaining consensus becomes even harder. Early approaches, such as the one proposed by Annie I. Chen in A Fast Distributed Proximal-Gradient Method, paired Nesterov-type acceleration with multi-step consensus phases that expanded over time to ensure convergence. Later, Haishan Ye et al. optimized this balance in Decentralized Accelerated Proximal Gradient Descent, achieving near-optimal communication overhead on ill-conditioned problems.
Despite these algorithmic advances, time-varying networks face strict physical limits. Dmitry Kovalev et al. established the first tight theoretical lower bounds for non-smooth optimization over changing topologies in Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks. They proved that while fixed networks allow communication to scale with the square root of the network condition number, time-varying networks are fundamentally harder, requiring communication that scales linearly with network connectivity. To achieve an optimal algorithm for this setting, the authors mapped the decentralized problem into a monotone inclusion problem via a saddle-point reformulation, allowing proximal-point updates to handle non-smoothness robustly despite shifting network paths.
Pushing into Non-Convex and Gradient-Free Domains
The frontier of decentralized non-smooth optimization extends beyond convex objectives into non-convex landscapes (such as deep neural networks with non-smooth ReLU activations) and zero-order settings where explicit gradients cannot be calculated.
When explicit gradients are unavailable, standard proximal-gradient steps cannot be computed. To overcome this, Zhenwei Lin et al. in Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization leverage randomized smoothing. This technique convolves the non-smooth, non-convex objective function with a continuous noise distribution, transforming a jagged, non-differentiable surface into a smooth approximation whose pseudo-gradients can be tracked across the network.
Jagged Non-Smooth Surface ──(Convolved with Noise)──> Smoothed Differentiable Surface
Alternatively, Emre Sahinoglu et al. addressed this challenge from an online learning perspective in An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization. By framing decentralized optimization as a multi-epoch online learning problem, the authors established finite-time convergence guarantees for both first-order and zero-order stochastic settings, matching the sample complexities typically restricted to centralized systems.
Key Foundational Work
A Fast Distributed Proximal-Gradient Method (2012) — contributed 2 concept elements to this direction.
A stochastic primal-dual algorithm for distributed asynchronous composite optimization (2014) — contributed 1 concept elements to this direction.