# Optimal Algorithms for Non-Smooth Distributed Optimization in Networks

arXiv: https://arxiv.org/abs/1806.00291 · HTML: https://mlsanity.com/paper/1806.00291/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2018.

## Built on by (most cited first, 30 of 41)

- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [Cross-Gradient Aggregation for Decentralized Learning from Non-IID data](https://mlsanity.com/paper/2103.02051/) (2021)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)
- [Accelerating Gossip SGD with Periodic Global Averaging](https://mlsanity.com/paper/2105.09080/) (2021)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks](https://mlsanity.com/paper/2106.07243/) (2021)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Compression with Exact Error Distribution for Federated Learning](https://mlsanity.com/paper/2310.20682/) (2023)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization](https://mlsanity.com/paper/2102.04259/) (2021)
- [Communication Efficient Federated Learning via Ordered ADMM in a Fully Decentralized Setting](https://mlsanity.com/paper/2202.02580/) (2022)
- [Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networks](https://mlsanity.com/paper/2211.00533/) (2022)
- [Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2406.01484/) (2024)
- [Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers](https://mlsanity.com/paper/2102.06280/) (2021)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates](https://mlsanity.com/paper/2306.06559/) (2023)
- [Personalized On-Device E-health Analytics with Decentralized Block Coordinate Descent](https://mlsanity.com/paper/2112.09341/) (2021)
- [Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batches](https://mlsanity.com/paper/2211.00889/) (2022)
- [Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networks](https://mlsanity.com/paper/2401.13779/) (2024)
- [PDSL: Privacy-Preserved Decentralized Stochastic Learning with Heterogeneous Data Distribution](https://mlsanity.com/paper/2503.23726/) (2025)
- [Decentralized Online Regularized Learning Over Random Time-Varying Graphs](https://mlsanity.com/paper/2206.03861/) (2022)

## Abstract (arXiv)

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/√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 d1/4 multiplicative factor of the optimal convergence rate, where d is the underlying dimension.