Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters

Abstract

In this paper, we study the communication and (sub)gradient computation costs in distributed optimization and give a sharp complexity analysis for the proposed distributed accelerated gradient methods. We present two algorithms based on the framework of the accelerated penalty method with increasing penalty parameters. Our first algorithm is for smooth distributed optimization and it obtains the near optimal $O\left(\sqrt{\frac{L}{\epsilon (1-{\sigma }_2(W))}}\log \frac{1}{\epsilon }\right)$ communication complexity and the optimal $O\left(\sqrt{\frac{L}{\epsilon }}\right)$ gradient computation complexity for $L$-smooth convex problems, where ${\sigma }_2(W)$ denotes the second largest singular value of the weight matrix $W$ associated to the network and $\epsilon$ is the target accuracy. When the problem is $\mu$-strongly convex and $L$-smooth, our algorithm has the near optimal $O\left(\sqrt{\frac{L}{\mu (1-{\sigma }_2(W))}}{\log }^2\frac{1}{\epsilon }\right)$ complexity for communications and the optimal $O\left(\sqrt{\frac{L}{\mu }}\log \frac{1}{\epsilon }\right)$ complexity for gradient computations. Our communication complexities are only worse by a factor of $\left(\log \frac{1}{\epsilon }\right)$ than the lower bounds for the smooth distributed optimization. %As far as we know, our method is the first to achieve both communication and gradient computation lower bounds up to an extra logarithm factor for smooth distributed optimization. Our second algorithm is designed for non-smooth distributed optimization and it achieves both the optimal $O\left(\frac{1}{\epsilon \sqrt{1-{\sigma }_2(W)}}\right)$ communication complexity and $O\left(\frac{1}{{\epsilon }^2}\right)$ subgradient computation complexity, which match the communication and subgradient computation complexity lower bounds for non-smooth distributed optimization.

arXiv commentThe previous name of this paper was "A Sharp Convergence Rate Analysis for Distributed Accelerated Gradient Methods". The contents are consistent

References in corpus (6)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Optimal Distributed Online Prediction using Mini-Batches
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
• Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting

Cited by in corpus (8)

• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• Revisiting EXTRA for Smooth Distributed Optimization
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning