Abstract
In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.
Introduction
Distributed optimization is the backbone of modern machine learning, where massive datasets are spread across clusters of computing nodes. While the field has established "optimal" recipes for functions that are both smooth and strongly convex, many real-world applications rely on non-smooth functions. Examples include $L_1$ regularization in Lasso or hinge loss in Support Vector Machines (SVMs).
In these decentralized scenarios, nodes must balance local computation (calculating subgradients) with communication (exchanging information with neighbors). The fundamental challenge lies in identifying the theoretical limits of convergence and designing algorithms that achieve these bounds. This paper addresses this by exploring two distinct regularity assumptions: Local Regularity, where each node's individual function is Lipschitz continuous, and Global Regularity, where only the average of all functions is well-behaved.
Algorithmic Frameworks
Multi-Step Primal-Dual (MSPD)
For the local regularity setting, the authors introduce the Multi-Step Primal-Dual (MSPD) algorithm. This approach treats the distributed optimization as a saddle-point problem within a primal-dual framework. To overcome the communication bottlenecks inherent in decentralized networks, MSPD incorporates Chebyshev acceleration (also known as accelerated gossip). This allows the algorithm to "over-communicate" strategically, ensuring that the network topology does not become the primary bottleneck for convergence.
Distributed Randomized Smoothing (DRS)
In the more restrictive global regularity setting, the authors propose Distributed Randomized Smoothing (DRS). Because the global objective is non-smooth, DRS "blurs" the function by adding Gaussian noise to the parameters before calculating gradients. This transformation converts a jagged, non-smooth landscape into a smooth approximation, enabling the use of high-speed accelerated gradient methods originally designed for smooth optimization.
Key Insights: The Separation of Concerns
The most significant theoretical contribution is the discovery of a "separation of concerns" in non-smooth distributed optimization. The authors prove that the error term decomposes into two parts:
- Computation Error: Decreases at a rate of $O(1/\sqrt{t})$.
- Communication Error: Decreases at a rate of $O(1/t)$.
Because the communication-related error vanishes much faster than the computation-related error, the specific structure of the network (its spectral gap or connectivity) eventually becomes a negligible factor in overall performance. This suggests that decentralized systems are remarkably robust; whether a network is a simple line or a highly connected graph, the long-term convergence is dominated by the local subgradient calculations rather than the network topology.
Results and Complexity
- Optimality of MSPD: Under local regularity, MSPD is the first algorithm to match the theoretical lower bounds for both communication and computation complexity in non-smooth decentralized settings.
- Efficiency of DRS: Under global regularity, the DRS algorithm achieves a rate within a factor of $d^{1/4}$ (where $d$ is the problem dimension) of the optimal rate. This highlights that knowing local regularity makes the optimization task significantly easier than only knowing global regularity.
- Decentralized vs. Centralized: The paper demonstrates that decentralized gossip-based approaches can be just as efficient as, or even superior to, traditional master/slave architectures for non-smooth problems, as the network limitations are effectively "outrun" by the $O(1/t)$ convergence of the communication term.
Conclusion and Future Work
This work provides a definitive theoretical foundation for non-smooth distributed optimization. While MSPD achieves optimality for local regularity, a small gap remains for the global regularity setting due to the $d^{1/4}$ dimensional factor in DRS. Future research may focus on closing this gap, extending these results to time-varying or asynchronous network topologies, and exploring the behavior of these algorithms in infinite-dimensional settings, such as those found in kernel methods.
Summary updated