Close Search Advanced
Journals
Resources
About Us
Open Access

ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks
Read Now
Download (PDF)

Year:    2017

Author:    Jinshan Zeng, Wotao Yin

Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 383–396

Abstract

In this note, we extend the algorithms Extra [13] and subgradient-push [10] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes.
We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex.
In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.

Submit Article

Journal Article Details

Publisher Name:    Global Science Press

Language:    English

DOI:    https://doi.org/10.4208/jcm.1606-m2015-0452

Journal of Computational Mathematics, Vol. 35 (2017), Iss. 4 : pp. 383–396

Published online:    2017-01

AMS Subject Headings:   

Copyright:    COPYRIGHT: © Global Science Press

Pages:    14

Keywords:    Decentralized optimization Directed graph Consensus Non-doubly stochastic Extra.

Author Details

Jinshan Zeng

Wotao Yin

  1. Asynchronous Gradient Push

    Assran, Mahmoud S. | Rabbat, Michael G.

    IEEE Transactions on Automatic Control, Vol. 66 (2021), Iss. 1 P.168

    https://doi.org/10.1109/TAC.2020.2981035 [Citations: 28]

  2. Linear Convergence of First- and Zeroth-Order Primal–Dual Algorithms for Distributed Nonconvex Optimization

    Yi, Xinlei | Zhang, Shengjun | Yang, Tao | Chai, Tianyou | Johansson, Karl H.

    IEEE Transactions on Automatic Control, Vol. 67 (2022), Iss. 8 P.4194

    https://doi.org/10.1109/TAC.2021.3108501 [Citations: 24]

  3. Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation

    Sun, Ying | Scutari, Gesualdo | Daneshmand, Amir

    SIAM Journal on Optimization, Vol. 32 (2022), Iss. 2 P.354

    https://doi.org/10.1137/19M1259973 [Citations: 30]

  4. Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks

    Song, Zhuoqing | Shi, Lei | Pu, Shi | Yan, Ming

    IEEE Transactions on Signal Processing, Vol. 70 (2022), Iss. P.1775

    https://doi.org/10.1109/TSP.2022.3160238 [Citations: 9]

  5. A fast proximal gradient algorithm for decentralized composite optimization over directed networks

    Zeng, Jinshan | He, Tao | Wang, Mingwen

    Systems & Control Letters, Vol. 107 (2017), Iss. P.36

    https://doi.org/10.1016/j.sysconle.2017.07.005 [Citations: 12]

  6. Corrected Gradient Methods for Distributed optimization

    Qiu, Zhirong | Xie, Lihua | You, Keyou

    2019 Chinese Control Conference (CCC), (2019), P.6148

    https://doi.org/10.23919/ChiCC.2019.8866156 [Citations: 0]

  7. Exact Diffusion for Distributed Optimization and Learning—Part II: Convergence Analysis

    Yuan, Kun | Ying, Bicheng | Zhao, Xiaochuan | Sayed, Ali H.

    IEEE Transactions on Signal Processing, Vol. 67 (2019), Iss. 3 P.724

    https://doi.org/10.1109/TSP.2018.2875883 [Citations: 52]

  8. A Decentralized Primal-Dual Method for Constrained Minimization of a Strongly Convex Function

    Hamedani, Erfan Yazdandoost | Aybat, Necdet Serhat

    IEEE Transactions on Automatic Control, Vol. 67 (2022), Iss. 11 P.5682

    https://doi.org/10.1109/TAC.2021.3130082 [Citations: 4]

  9. Improved Convergence Rates for Distributed Resource Allocation

    Nedic, Angelia | Olshevsky, Alex | Shi, Wei

    2018 IEEE Conference on Decision and Control (CDC), (2018), P.172

    https://doi.org/10.1109/CDC.2018.8619322 [Citations: 35]

  10. Convergence of Distributed Accelerated Algorithm Over Unbalanced Directed Networks

    Li, Huaqing | Lu, Qingguo | Chen, Guo | Huang, Tingwen | Dong, Zhaoyang

    IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 51 (2021), Iss. 8 P.5153

    https://doi.org/10.1109/TSMC.2019.2946287 [Citations: 11]

  11. Distributed Dual Gradient Tracking for Resource Allocation in Unbalanced Networks

    Zhang, Jiaqi | You, Keyou | Cai, Kai

    IEEE Transactions on Signal Processing, Vol. 68 (2020), Iss. P.2186

    https://doi.org/10.1109/TSP.2020.2981762 [Citations: 53]

  12. A Unification and Generalization of Exact Distributed First-Order Methods

    Jakovetic, Dusan

    IEEE Transactions on Signal and Information Processing over Networks, Vol. 5 (2019), Iss. 1 P.31

    https://doi.org/10.1109/TSIPN.2018.2846183 [Citations: 71]

  13. Multi-agent constrained optimization of a strongly convex function over time-varying directed networks

    Hamedani, Erfan Yazdandoost | Aybat, Necdet Serhat

    2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), (2017), P.518

    https://doi.org/10.1109/ALLERTON.2017.8262781 [Citations: 3]

  14. A Family of Distributed Momentum Methods Over Directed Graphs With Linear Convergence

    Gao, Juan | Liu, Xinwei | Dai, Yu-Hong | Huang, Yakui | Yang, Peng

    IEEE Transactions on Automatic Control, Vol. 68 (2023), Iss. 2 P.1085

    https://doi.org/10.1109/TAC.2022.3160684 [Citations: 5]

  15. Exponential Convergence for Distributed Optimization Under the Restricted Secant Inequality Condition

    Yi, Xinlei | Zhang, Shengjun | Yang, Tao | Chai, Tianyou | H. Johansson, Karl

    IFAC-PapersOnLine, Vol. 53 (2020), Iss. 2 P.2672

    https://doi.org/10.1016/j.ifacol.2020.12.383 [Citations: 9]

  16. Distributed Optimization Methods for Multi-Robot Systems: Part 2—A Survey

    Shorinwa, Ola | Halsted, Trevor | Yu, Javier | Schwager, Mac

    IEEE Robotics & Automation Magazine, Vol. 31 (2024), Iss. 3 P.154

    https://doi.org/10.1109/MRA.2024.3352852 [Citations: 3]

  17. A Proximal Gradient Algorithm for Composite Consensus Optimization over Directed Graphs

    Zeng, Jinshan | He, Tao | Ouyang, Shikang | Wang, Mingwen | Chang, Xiangyu

    2017 IEEE 7th Annual International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER), (2017), P.825

    https://doi.org/10.1109/CYBER.2017.8446454 [Citations: 0]

  18. Decentralized Multi-Agent Policy Evaluation Over Directed Graphs

    Lin, Qifeng | Ling, Qing

    2022 41st Chinese Control Conference (CCC), (2022), P.4649

    https://doi.org/10.23919/CCC55666.2022.9902191 [Citations: 0]

  19. Accelerated Distributed Nesterov Gradient Descent

    Qu, Guannan | Li, Na

    IEEE Transactions on Automatic Control, Vol. 65 (2020), Iss. 6 P.2566

    https://doi.org/10.1109/TAC.2019.2937496 [Citations: 118]

  20. Push–Pull Gradient Methods for Distributed Optimization in Networks

    Pu, Shi | Shi, Wei | Xu, Jinming | Nedic, Angelia

    IEEE Transactions on Automatic Control, Vol. 66 (2021), Iss. 1 P.1

    https://doi.org/10.1109/TAC.2020.2972824 [Citations: 186]

  21. Computational Convergence Analysis of Distributed Optimization Algorithms for Directed Graphs

    Zhang, Shengjun | Yi, Xinlei | George, Jemin | Yang, Tao

    2019 IEEE 15th International Conference on Control and Automation (ICCA), (2019), P.1096

    https://doi.org/10.1109/ICCA.2019.8899565 [Citations: 7]

  22. DC-DistADMM: ADMM Algorithm for Constrained Optimization Over Directed Graphs

    Khatana, Vivek | Salapaka, Murti V.

    IEEE Transactions on Automatic Control, Vol. 68 (2023), Iss. 9 P.5365

    https://doi.org/10.1109/TAC.2022.3221856 [Citations: 9]

  23. AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs

    Zhang, Jiaqi | You, Keyou

    IEEE Transactions on Automatic Control, Vol. 65 (2020), Iss. 6 P.2494

    https://doi.org/10.1109/TAC.2019.2930234 [Citations: 48]

  24. Primal-dual algorithm for distributed optimization with local domains on signed networks

    Ren, Xiaoxing | Li, Dewei | Xi, Yugeng | Pan, Lulu | Shao, Haibin

    2020 39th Chinese Control Conference (CCC), (2020), P.4930

    https://doi.org/10.23919/CCC50068.2020.9189564 [Citations: 1]

  25. Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs

    Xie, Pei | You, Keyou | Tempo, Roberto | Song, Shiji | Wu, Cheng

    IEEE Transactions on Automatic Control, Vol. 63 (2018), Iss. 12 P.4331

    https://doi.org/10.1109/TAC.2018.2816104 [Citations: 94]
  26. Large-Scale and Distributed Optimization

    Decentralized Consensus Optimization and Resource Allocation

    Nedić, Angelia | Olshevsky, Alexander | Shi, Wei

    2018

    https://doi.org/10.1007/978-3-319-97478-1_10 [Citations: 7]

  27. Distributed Proximal Alternating Direction Method of Multipliers for Constrained Composite Optimization Over Directed Networks

    Yan, Jing | Shi, Xinli | Guo, Luyao | Wan, Ying | Wen, Guanghui

    IEEE Transactions on Signal and Information Processing over Networks, Vol. 10 (2024), Iss. P.539

    https://doi.org/10.1109/TSIPN.2024.3407660 [Citations: 0]

  28. Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations

    Shen, Chungen | Liu, Xiao

    Journal of Global Optimization, Vol. 81 (2021), Iss. 4 P.1019

    https://doi.org/10.1007/s10898-021-01028-9 [Citations: 1]