Optimal Algorithms for Non-Smooth Distributed Optimization in Networks

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.

arXiv comment17 pages

References in corpus (3)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation

Cited by in corpus (29)

• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
• Decentralized Deep Learning with Arbitrary Communication Compression
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Recent theoretical advances in decentralized distributed convex optimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Consensus Control for Decentralized Deep Learning
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Robust and Communication-Efficient Collaborative Learning
• On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
• Cooperative Online Learning: Keeping your Neighbors Updated
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques
• Achieving Optimal Output Consensus for Discrete-time Linear Multi-agent Systems with Disturbance Rejection
• Distributed Zeroth-Order Stochastic Optimization in Time-varying Networks
• Accelerating Gossip SGD with Periodic Global Averaging
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• Extrapolation for Large-batch Training in Deep Learning
• Decentralized Distributed Optimization for Saddle Point Problems
• Accelerated Sparsified SGD with Error Feedback
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
• Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence
• Newton Method over Networks is Fast up to the Statistical Precision