Decentralized optimization has wide applications in machine learning, signal processing, and control. In this paper, we study the decentralized composite optimization problem with a non-smooth regularization term. Many proximal gradient based decentralized algorithms have been proposed in the past. However, these algorithms do not achieve near optimal computational complexity and communication complexity. In this paper, we propose a new method which establishes the optimal computational complexity and a near optimal communication complexity. Our empirical study shows that the proposed algorithm outperforms existing state-of-the-art algorithms.

Additional Feedback: edit I have read the rebuttal, and I would have liked the authors to point out precisely *what* technical points change and are difficult to handle. I think it would be great to actually highlight them in a revision of the paper. On a side note, I still believe that it is possible to get rid of the consensus step on y_t, and closeness between y_t and \bar{y}_t should be enforceable by the consensus step on x_t. This should be better in practice, since the consensus steps that are currently performed on y_t would also benefit x_t. A comparison with higher values of K would also have been welcome.

The paper gives an accelerated gradient method for decentralized optimization on composite objectives. It achieves this by mimicking centralized accelerated proximal gradient descent. Slight concerns remained about the level of novelty over the Mudag algorithm, which should be expanded in the discussion more precisely, as well as the (theory) requirement of K 1 communications after every step and the not yet fully explained dependence of K on the graph parameter. We expect the authors to incorporate the feedback and improvement suggestions from the 4 reviews in the camera ready version.

Decentralized optimization has wide applications in machine learning, signal processing, and control. In this paper, we study the decentralized composite optimization problem with a non-smooth regularization term. Many proximal gradient based decentralized algorithms have been proposed in the past. However, these algorithms do not achieve near optimal computational complexity and communication complexity. In this paper, we propose a new method which establishes the optimal computational complexity and a near optimal communication complexity.