Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
复制标题
DOI：
10.1109/tsp.2020.3018317
复制
发表时间：
2018-10
影响因子：
5.4
通讯作者：
Huan Li;Cong Fang;W. Yin;Zhouchen Lin
中科院分区：
文献类型：
--
作者：
Huan Li;Cong Fang;W. Yin;Zhouchen Lin
In this article, we study the communication, and (sub)gradient computation costs in distributed optimization. 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(\sqrt{\frac{L}{\epsilon (1-\sigma _2(W))}}\log \frac{1}{\epsilon })$ communication complexity, and the optimal $O(\sqrt{\frac{L}{\epsilon }})$ 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(\sqrt{\frac{L}{\mu (1-\sigma _2(W))}}\log ^2\frac{1}{\epsilon })$ complexity for communications, and the optimal $O(\sqrt{\frac{L}{\mu }}\log \frac{1}{\epsilon })$ complexity for gradient computations. Our communication complexities are only worse by a factor of $(\log \frac{1}{\epsilon })$ than the lower bounds. Our second algorithm is designed for nonsmooth distributed optimization, and it achieves both the optimal $O(\frac{1}{\epsilon \sqrt{1-\sigma _2(W)}})$ communication complexity, and $O(\frac{1}{\epsilon ^2})$ subgradient computation complexity, which match the lower bounds for nonsmooth distributed optimization.
In this article, we study the communication, and (sub)gradient computation costs in distributed optimization. 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(\sqrt{\frac{L}{\epsilon (1-\sigma _2(W))}}\log \frac{1}{\epsilon })$ communication complexity, and the optimal $O(\sqrt{\frac{L}{\epsilon }})$ 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(\sqrt{\frac{L}{\mu (1-\sigma _2(W))}}\log ^2\frac{1}{\epsilon })$ complexity for communications, and the optimal $O(\sqrt{\frac{L}{\mu }}\log \frac{1}{\epsilon })$ complexity for gradient computations. Our communication complexities are only worse by a factor of $(\log \frac{1}{\epsilon })$ than the lower bounds. Our second algorithm is designed for nonsmooth distributed optimization, and it achieves both the optimal $O(\frac{1}{\epsilon \sqrt{1-\sigma _2(W)}})$ communication complexity, and $O(\frac{1}{\epsilon ^2})$ subgradient computation complexity, which match the lower bounds for nonsmooth distributed optimization.