A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates
By Zhi Li, W. Shi, Ming Yan. 2017
272 citations recorded by the source corpus.
This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and nonsmooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA (W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Trans. Signal Process., vol. 63, no. 22, pp. 6013–6023, 2015), but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Second, for the special case without nonsmooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries.
Subfields: Computational Mechanics, Computer Networks and Communications
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Mechanics
In Computer Networks and Communications
Citations in the corpus
- D2: Decentralized Training over Decentralized Data (2018, background): “In NIDS [Li and Yan, 2017], the term depends on ζ 0 in the convergence rate is T + σ 2 T 2 , which indicates when our algorithm is consistent with NIDS because in NIDS σ is consideblack to be 0.”
- Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “Nair and Gupta [2017] proposed another distributed stochastic algorithm, but it requires a centralized arbitrator to decide which two workers are exchanging weights and it lacks convergence analysis.”
- Communication Compression for Decentralized Training (2018, methodology): “Two methods [Li et al., 2017, Shi et al., 2015] were proposed to blackuce the steady point error in decentralized gradient descent convex optimization.”
- Decentralization Meets Quantization (2018, methodology): “Two methods [Li et al., 2017, Shi et al., 2015] were proposed to blackuce the steady point error in decentralized gradient descent convex optimization.”
- Balancing Communication and Computation in Distributed Optimization (2017, background): “Recently, there have been many new distributed algorithms [29], [47], [58]–[61] that can achieve exact convergence with a constant stepsize.”
- Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, background): “Work in [28], [29] investigates proximal-gradient methods which can tackle (1) with proximal friendly component functions.”
- Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “Our work is closely related to a few lines of research that we delineate below: 1) distributed first-order primal algorithms [9]–[11], [29]–[32]: methods that use only gradient information, 2) nested [11], [33]–[35]: methods that decompose the communication and computation steps, 3) communication ef”
- A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization (2017, background): “For details about decentralized consensus optimization, please see [17,18,15] and references therein.”