  In this paper, we focus on the decentralized composite optimization for
convex functions. Because of advantages such as robust to the network and no
communication bottle-neck in the central server, the decentralized optimization
has attracted much research attention in signal processing, control, and
optimization communities. Many optimal algorithms have been proposed for the
objective function is smooth and (strongly)-convex in the past years. However,
it is still an open question whether one can design an optimal algorithm when
there is a non-smooth regularization term. In this paper, we fill the gap
between smooth decentralized optimization and decentralized composite
optimization and propose the first algorithm which can achieve both the optimal
computation and communication complexities. Our experiments also validate the
effectiveness and efficiency of our algorithm both in computation and
communication.
