Distributed finite-time-consensus-based heavy-ball algorithm

doi:10.7523/j.ucas.2020.0009

Abstract

Abstract: Based on the finite-time-consensus algorithm and the heavy-ball algorithm which is a first order accelerate algorithm, a distributed optimization algorithm is proposed. The algorithm can achieve consensus after every periodic updates. The non-ergodic convergence rate is at the same order of the centralized heavy-ball algorithm. In addition, the numerical examples compare our algorithm with other state-of-art distributed optimization algorithms on machine learning problems and show the competitive performance.

Key words: distributed optimization, algorithm design, finite-time-consensus algorithm, heavy-ball algorithm

CLC Number:

TN99

QU Zhihai, LU Jie. Distributed finite-time-consensus-based heavy-ball algorithm[J]. Journal of University of Chinese Academy of Sciences, 2022, 39(1): 127-133.

References

[1] Beck A, Nedić A, Ozdaglar A, et al. An O(1/k) gradient method for network resource allocation problems[J]. IEEE Transactions on Control of Network Systems, 2014, 1(1):64-73.
[2] Rabbat M, Nowak R. Distributed optimization in sensor networks[C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks 2004. April 26-27, 2004. Berkeley, California, USA. New York:Association for Computing Machinery, 2004:20-27.
[3] Shamma J S. Cooperative control of distributed multi-agent systems[M]. New York:John Wiley & Sons, Ltd, 2007.
[4] Wai H T, Yang Z, Wang Z, et al. Multi-agent reinforcement learning via double averaging primal-dual optimization[C]//Bengio S, Wallach H, Larochelle, et al. Advances in Neural Information Processing Systems 31:New York:Curran Associates, 2018:9649-9660.
[5] Nedic A, Ozdaglar A. Distributed subgradient methods for multi-agent optimization[J]. IEEE Transactions on Automatic Control, 2009, 54(1):48-61.
[6] Shi W, Ling Q, Wu G, et al. EXTRA:an exact first-order algorithm for decentralized consensus optimization[J]. SIAM Journal on Optimization, 2015, 25(2):944-966.
[7] Nedić A, Olshevsky A, Shi W. Achieving geometric convergence for distributed optimization over time-varying graphs[J]. SIAM Journal on Optimization, 2017, 27(4):2597-2633.
[8] Sundaram S, Hadjicostis C N. Finite-time distributed consensus in graphs with time-invariant topologies[C]//2007 American Control Conference, July 9-13, 2007, New York NY, USA. IEEE, 2007:711-716.
[9] Mai V S, Abed E H. Local prediction for enhanced convergence of distributed optimization algorithms[J]. IEEE Transactions on Control of Network Systems, 2018, 5(4):1962-1975.
[10] Qu Z H, Wu X Y, Lu J. Finite-time-consensus-based methods for distributed optimization[C]//2019 Chinese Control Conference (CCC). July 27-30, 2019, Guangzhou, China. IEEE, 2019:5764-5769.
[11] Xiao L, Boyd S. Fast linear iterations for distributed averaging[J]. Systems & Control Letters, 2004, 53(1):65-78.
[12] Horn R A, Johnson C R. Matrix analysis[M]. 2nd ed. Cambridge:Cambridge University Press, 1985, 191-200.
[13] Sundaram S, Hadjicostis C N. Distributed function calculation and consensus using linear iterative strategies[J]. IEEE Journal on Selected Areas in Communications, 2008, 26(4):650-660.
[14] Ghadimi E, Feyzmahdavian H R, Johansson M. Global convergence of the heavy-ball method for convex optimization[C]//2015 European Control Conference (ECC). July 15-17, 2015, Linz, Austria. IEEE, 2015:310-315.
[15] Sun T, Yin P H, Li D S, et al. Non-ergodic convergence analysis of heavy-ball algorithms[C]//Proceedings of the AAAI Conference on Artificial Intelligence. AAAI, 2019, 33(1):5033-5040.
[16] Murphy K P. Machine learning:a probabilistic perspective[M]. Cambridge, Massachusetts:MIT press, 2012:290-295.
[17] Löfberg J. YALMIP:a toolbox for modeling and optimization in MATLAB[C]//2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508). September 2-42004, Taipei, Taiwan, China. IEEE, 2004:284-289.
[18] Bajović D, Jakovetić D, Krejić N, et al. Newton-like method with diagonal correction for distributed optimization[J]. SIAM Journal on Optimization, 2017, 27(2):1171-1203.
[19] Mokhtari A, Ling Q, Ribeiro A. Network Newton distributed optimization methods[J]. IEEE Transactions on Signal Processing, 2017, 65(1):146-161.