有向网络中基于动量方法的加速行随机优化
Accelerated Row-Stochastic Optimization over Directed Networks Based on Momentum Methods
摘要: 本文研究了有向网络下的分布式凸优化问题，并在现有分布式算法的基础上提出了一种新颖的分布式动量加速算法，叫做ARNH。该算法采用行随机矩阵和异构步长，有效克服网络不平衡性的同时提高了网络灵活性。此外，为了实现更快的收敛速率，ARNH采用Nesterov梯度法和Heavy-Ball法相结合的双加速机制。在局部目标函数可微且强凸的假设下，本文证明通过选取合适的步长和动量参数，算法可使节点状态渐近收敛到全局最优解。最后，在仿真实验中将ARNH与相关算法进行性能比较，验证了新算法的优越性。
Abstract: In this paper, we study the distributed convex optimization problems over directed networks, and propose a novel distributed momentum acceleration algorithm called ARNH based on the existing distributed algorithms. ARNH uses row-stochastic matrix and heterogeneous step size, which effec-tively overcomes the network imbalance and improves the network flexibility. Furthermore, in or-der to achieve faster convergence, ARNH employs a double acceleration mechanism combining Nesterov gradient method and heavy-ball method. Under the assumption that the local objective function is differentiable and strongly convex, it is proved that the node state can be asymptotically converged to the global optimal solution by choosing appropriate step-sizes and momentum pa-rameters. Finally, the superiority of the new algorithm is verified by comparing the performance of ARNH with related algorithms in simulation experiments.
文章引用：任冬梅. 有向网络中基于动量方法的加速行随机优化[J]. 应用数学进展, 2023, 12(3): 919-931. https://doi.org/10.12677/AAM.2023.123094

参考文献

[1] Meng, M. and Li, X. (2020) Distributed Nonlinear Estimation Over Unbalanced Directed Networks. IEEE Transactions on Signal Processing, 68, 6212-6223. [Google Scholar] [CrossRef] 
[2] Forero, P.A., Cano, A. and Giannakis, G.B. (2010) Consensus-Based Distributed Support Vector Machines. Journal of Machine Learning Research, 11, 1663-1707. [Google Scholar] [CrossRef] 
[3] Raja, H. and Bajwa, W.U. (2016) Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data. IEEE Transactions on Signal Processing, 64, 173-188. [Google Scholar] [CrossRef] 
[4] Lorenzo, P.D. and Sayed, A.H. (2016) Sparse Distrib-uted Learning Based on Diffusion Adaptation. IEEE Transactions on Signal Processing, 61, 1419-1433. [Google Scholar] [CrossRef] 
[5] Wu, D., Yang, T., Stoorvogel, A.A. and Stoustrup, J. (2017) Dis-tributed Optimal Coordination for Distributed Energy Resources in Power Systems. IEEE Transactions on Automation Science and Engineering, 14, 414-424. [Google Scholar] [CrossRef] 
[6] Safavi, S., Khan, U.A., Kar, S. and Moura, J.M.F. (2018) Dis-tributed Localization: A Linear Theory. Proceedings of the IEEE, 106, 1204-1223. [Google Scholar] [CrossRef] 
[7] Mateos, G., Bazerque, J.A. and Giannakis, G.B. (2010) Dis-tributed Sparse Linear Regression. IEEE Transactions on Signal Processing, 58, 5262-5276. [Google Scholar] [CrossRef] 
[8] Nedić, A. and Ozdaglar, A. (2009) Distributed Subgradient Methods for Multi-Agent Optimization. IEEE Transactions on Automatic Control, 54, 48-61. [Google Scholar] [CrossRef] 
[9] Shi, W., Ling, Q., Wu, G. and Yin, W. (2015) EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization. SIAM Journal on Optimization, 25, 944-966. [Google Scholar] [CrossRef] 
[10] Qu, G. and Li, N. (2017) Harnessing Smoothness to Accelerate Distrib-uted Optimization. IEEE Transactions on Control of Network Systems, 5, 1245-1260. [Google Scholar] [CrossRef] 
[11] Jakovetić, D. (2019) A Unification and Generalization of Exact Distributed First-Order Methods. IEEE Transactions on Signal and Information Processing over Networks, 5, 31-46. [Google Scholar] [CrossRef] 
[12] Xi, C., Wu, Q. and Khan, U.A. (2017) On the Distributed Op-timization over Directed Networks. Neurocomputing, 267, 508-515. [Google Scholar] [CrossRef] 
[13] Kempe, D., Dobra, A. and Gehrke, J. (2003) Gossip-Based Computation of Aggregate Information. 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, 11-14 October 2003, 482-491. [Google Scholar] [CrossRef] 
[14] Xi, C. and Khan, U.A. (2017) DEXTRA: A Fast Algorithm for Optimization over Directed Graphs. IEEE Transactions on Signal Processing, 62, 4980-4993. [Google Scholar] [CrossRef] 
[15] Nedić, A., Olshevsky, A. and Shi, A. (2017) Achieving Geomet-ric Convergence for Distributed Optimization over Time-Varying Graphs. SIAM Journal on Optimization, 27, 2597-2633. [Google Scholar] [CrossRef] 
[16] Pu, S., Shi, W., Xu, J. and Nedić, A. (2018) Push-Pull Gradient Meth-ods for Distributed Optimization in Networks. IEEE Transactions on Automatic Control, 66, 1-16. [Google Scholar] [CrossRef] 
[17] Xin, R. and Khan, U.A. (2018) A Linear Algorithm for Optimiza-tion over Directed Graphs with Geometric Convergence. IEEE Control Systems Letters, 2, 315-320. [Google Scholar] [CrossRef] 
[18] Xi, C., Mai, V.S. and Abed, E.H. (2018) Linear Convergence in Optimization over Directed Graphs with Row-Stochastic Matrices. IEEE Transactions on Automatic Control, 63, 3558-3565. [Google Scholar] [CrossRef] 
[19] Mai, V.S. and Abed, E.H. (2016) Distributed Opti-mization over Weighted Directed Graphs Using Row Stochastic Matrix. 2016 American Control Conference (ACC), Boston, 6-8 July 2016, 7165-7170.
[20] Xin, R., Xi, C. and Khan, U.A. (2019) FROST—Fast Row-Stochastic Opti-mization with Uncoordinated Step-Sizes. EURASIP Journal on Advances in Signal Processing, 2019, Article No. 1. [Google Scholar] [CrossRef] 
[21] Xin, R., Jakovetić, D. and Khan, U.A. (2019) Distributed Nesterov Gradient Methods over Arbitrary Graphs. IEEE Signal Processing Letters, 26, 1247-1251. [Google Scholar] [CrossRef] 
[22] Lu, Q., Liao, X., Li, H. and Huang, T. (2021) A Nesterov-Like Gradient Tracking Algorithm for Distributed Optimization over Directed Networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51, 6258-6270. [Google Scholar] [CrossRef] 
[23] Li, H., Wang, J. and Wang, Z. (2019) Row-Stochastic Matrices Based Distributed Optimization Algorithm with Uncoordinated Step-Sizes. 2019 6th International Conference on Infor-mation, Cybernetics, and Computational Social Systems (ICCSS), Chongqing, 27-30 September 2019, 124-131. [Google Scholar] [CrossRef] 
[24] Ghaderyan, D., Aybat, N.S., Aguiar, A.P. and Pereira, F.M.L. (2021) A Fast Row-Stochastic Decentralized Optimization Method over Directed Graphs.
[25] Polyak, B. (1964) Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathe-matical Physics, 4, 1-17. [Google Scholar] [CrossRef] 
[26] Nesterov, Y. (2013) Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, Berlin, 87.

为你推荐