A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates

摘要

This paper considers the problem of decentralized optimization with acomposite objective containing smooth and non-smooth terms. To solve theproblem, a proximal-gradient scheme is studied. Specifically, the smooth andnonsmooth terms are dealt with by gradient update and proximal update,respectively. The studied algorithm is closely related to a previousdecentralized optimization algorithm, PG-EXTRA [37], but has a few advantages.First of all, in our new scheme, agents use uncoordinated step-sizes and thestable upper bounds on step-sizes are independent from network topology. Thestep-sizes depend on local objective functions, and they can be as large asthat of the gradient descent. Secondly, for the special case without non-smoothterms, linear convergence can be achieved under the strong convexityassumption. The dependence of the convergence rate on the objective functionsand the network are separated, and the convergence rate of our new scheme is asgood as one of the two convergence rates that match the typical rates for thegeneral gradient descent and the consensus averaging. We also provide somenumerical experiments to demonstrate the efficacy of the introduced algorithmsand validate our theoretical discoveries.