# Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters

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

## Key facts

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

## Built on by (most cited first, 8 of 8)

- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Differentiable Arbitrating in Zero-sum Markov Games](https://mlsanity.com/paper/2302.10058/) (2023)
- [Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks](https://mlsanity.com/paper/2405.18031/) (2024)
- [Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization](https://mlsanity.com/paper/2606.07496/) (2026)
- [On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality](https://mlsanity.com/paper/2310.00419/) (2023)
- [Distributed Optimization via Energy Conservation Laws in Dilated Coordinates](https://mlsanity.com/paper/2409.19279/) (2024)

## Abstract (arXiv)

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 Oleft(√fracLε(1-σ2(W))logfrac1εright) communication complexity and the optimal Oleft(√fracLεright) gradient computation complexity for L-smooth convex problems, where σ2(W) denotes the second largest singular value of the weight matrix W associated to the network and ε is the target accuracy. When the problem is μ-strongly convex and L-smooth, our algorithm has the near optimal Oleft(√fracLμ(1-σ2(W))log2frac1εright) complexity for communications and the optimal Oleft(√fracLμlogfrac1εright) complexity for gradient computations. Our communication complexities are only worse by a factor of left(logfrac1ε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 Oleft(frac1ε√1-σ2(W)right) communication complexity and Oleft(frac1ε2right) subgradient computation complexity, which match the communication and subgradient computation complexity lower bounds for non-smooth distributed optimization.