Dynamic Regret for Distributed Online Composite Convex Optimization with Delayed Feedbacks
-
摘要: 研究了分布式在线复合优化场景中的几种反馈延迟, 包括梯度反馈、单点Bandit反馈和两点Bandit反馈, 其中, 每个智能体的局部目标函数由一个强凸光滑函数与一个凸的非光滑正则项组成. 在分布式场景下, 研究了每个智能体具有不同的时变延迟. 基于近端梯度下降算法, 分别设计了这三种延迟反馈的分布式在线复合优化算法, 并且对动态遗憾上界进行了分析. 分析结果表示, 延迟梯度反馈和延迟两点Bandit反馈的动态遗憾上界阶数在期望意义下相同, 均为$ {\rm O}(\bar{\tau} (D_T+ $$ 1)+C_T+1) $, 而延迟单点Bandit反馈的动态遗憾上界中$ T $的次数稍差于前两者, 为$ {\rm O}(\sqrt{T\log T}+\bar{\tau} (D_T+1)+C_T+1) $, 其中, $ \bar{\tau} $为所有智能体的平均延迟, $ T $为总迭代次数, $ C_T $和$ D_T $是问题的复杂度度量, 分别称为路径长度和梯度变化度. 这意味着, 存在延迟时, 两点Bandit反馈可以在期望意义下达到与梯度反馈相同阶数的动态遗憾上界, 且在步长选择合适的情况下, 三种反馈类型的平均延迟在动态遗憾上具有相同的阶数. 最后通过仿真实验验证了算法的性能和理论分析结果.Abstract: This paper investigates several types of feedback delays in distributed online composite optimization, including gradient feedback, one-point Bandit feedback, and two-point Bandit feedback, where each agent's local loss consists of a strongly convex and smooth function combined with a convex non-smooth regularizer. In the distributed scenarios, this paper investigates the scenario where each agent has a different time-varying delay. Based on the proximal gradient descent algorithm, distributed online composite optimization algorithms are designed for these three cases respectively and the upper bounds of dynamic regret are analyzed. The analysis showed that the order of dynamic regret bound under delayed gradient feedback and delayed two-point Bandit feedback is identical in the mathematical expectation sense, which is $ {\rm O}(\bar{\tau} (D_T+1)+C_T+1) $, while that under delayed single-point Bandit feedback is slightly worse than the former two, which is $ {\rm O}(\sqrt{T\log T}+\bar{\tau} (D_T+1)+C_T+1) $, where $ \bar{\tau} $ represents the average of delay for all agents, $ T $ is the total number of iterations and $ C_T $ and $ D_T $ are complexity measures of the problem, called path variation and gradient variation. Therefore, under delays, two-point Bandit feedback can achieve the same order of dynamic regret bound as gradient feedback in the mathematical expectation sense, and the average delay for the three feedbacks has the same orders on dynamic regret when choosing suitable step sizes. Finally, the performance of the algorithms and the results of the theoretical analysis are verified through simulations.
-
图 1 四种不同规模的网络 (智能体的数量$ N $从左到右从上到下依次为10, 20, 30, 40)
Fig. 1 Four networks with different sizes (the number of agents $ N $ is 10, 20, 30, 40 from left to right and from top to bottom, respectively)
图 2 不同网络规模下本文所提出算法的性能表现
Fig. 2 Performance of the proposed algorithms under different network sizes
图 3 两种不同的网络拓扑 (网络的连通度从左到右依次为0.2和0.4)
Fig. 3 Two different network topologies (the connectivity of netwrok is 0.2 and 0.4 from left to right, respectively)
图 4 不同网络拓扑下本文所提出算法的性能表现
Fig. 4 Performance of the proposed algorithms under different network topologies
图 5 不同数据集下本文所提出算法的性能表现
Fig. 5 Performance of the proposed algorithms under different datasets
图 7 不同延迟分布下本文所提出算法的性能表现
Fig. 7 Performance of the proposed algorithms under different delay distributions
图 8 在小网络的不同延迟大小下本文所提出算法的性能表现 (小网络: N=20)
Fig. 8 Performance of the proposed algorithms under different delays (small network: N=20)
-
[1] Bedi A S, Sarma P, Rajawat K. Adversarial multi-agent target tracking with inexact online gradient descent. In: 2018 IEEE International Conference on Acoustics, Speech and Signal Processing. 2018. 2881−2885 [2] Karuga G G, Khraban A M, Nair S K, Rice D O. AdPalette: An algorithm for customizing online advertisements on the fly. Decision Support Systems, 2001, 32(2): 85−106 doi: 10.1016/S0167-9236(01)00104-X [3] Li X X, Xie L H, Li N. A survey on distributed online optimization and online games. Annual Reviews in Control, 2023, 56: 100904 doi: 10.1016/j.arcontrol.2023.100904 [4] Eshraghi N, Liang B. Dynamic regret of online mirror descent for relatively smooth convex cost functions. IEEE Control Systems Letters, 2022, 6: 2395−2400 doi: 10.1109/LCSYS.2022.3155067 [5] Yuan D M, Hong Y G, Ho D W C, Xu S Y. Distributed mirror descent for online composite optimization. IEEE Transactions on Automatic Control, 2020, 66(2): 714−729 [6] Dixit R, Bedi A S, Rajawat K. Online learning over dynamic graphs via distributed proximal gradient algorithm. IEEE Transactions on Automatic Control, 2020, 66(11): 5065−5079 [7] Yuan D M, Zhang B Y, Xu S Y, Zhao H Y. Distributed regularized online optimization using forward–backward splitting. Control Theory and Technology, 2023, 21(2): 212−221 doi: 10.1007/s11768-023-00134-1 [8] Yi X L, Li X X, Yang T, Xie L H, Chai T Y, Karl H J. Regret and cumulative constraint violation analysis for distributed online constrained convex optimization. IEEE Transactions on Automatic Control, 2022, 68(5): 2875−2890 [9] Molzahn D K, Dörfler F, Sandberg H, Low S H, Chakrabarti S, Baldick R, et al. A survey of distributed optimization and control algorithms for electric power systems. IEEE Transactions on Smart Grid, 2017, 8(6): 2941−2962 doi: 10.1109/TSG.2017.2720471 [10] Li Z W, Zhang J L. Study on the distributed model predictive control for multi-zone buildings in personalized heating. Energy and Buildings, 2021, 231: 110627 doi: 10.1016/j.enbuild.2020.110627 [11] 吴庆涛, 朱军龙, 葛泉波, 张明川. 一种基于条件梯度的加速分布式在线学习算法. 自动化学报, 2024, 50(2): 386−402Wu Qing-Tao, Zhu Jun-Long, Ge Quan-Bo, Zhang Ming-Chuan. An accelerated distributed online learning algorithm based on conditional gradient. Acta Automatica Sinica, 2024, 50(2): 386−402 [12] 刘奕葶, 马铭莙, 付俊. 基于有向图的分布式连续时间非光滑耦合约束凸优化分析. 自动化学报, 2024, 50(1): 66−75Liu Yi-Ting, Ma Ming-Jun, Fu Jun. Distributed continuous-time non-smooth convex optimization analysis with coupled constraints over directed graphs. Acta Automatica Sinica, 2024, 50(1): 66−75 [13] Yuan D M, Proutiere A, Shi G D. Distributed online optimization with long-term constraints. IEEE Transactions on Automatic Control, 2021, 67(3): 1089−1104 [14] Li X X, Yi X L, Xie L H. Distributed online convex optimization with an aggregative variable. IEEE Transactions on Control of Network Systems, 2021, 9(1): 438−449 [15] Zhang Y J, Dall’Anese E, Hong M Y. Online proximal-ADMM for time-varying constrained convex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2021, 7: 144−155 doi: 10.1109/TSIPN.2021.3051292 [16] Jin D Q, Chen J, Richard C, Chen J D. Online proximal learning over jointly sparse multitask networks with $\ell_{\infty,\; 1}$ regularization. IEEE Transactions on Signal Processing, 2020, 68: 6319−6335 doi: 10.1109/TSP.2020.3021247 [17] Wang C, Tang J H, Cheng X H, Liu Y C, Wang C C. Distributed cooperative task planning algorithm for multiple satellites in delayed communication environment. Journal of Systems Engineering and Electronics, 2016, 27(3): 619−633 doi: 10.1109/JSEE.2016.00066 [18] Quanrud K, Khashabi D. Online learning with adversarial delays. Advances in Neural Information Processing Systems, 2015, 28 [19] Wang J C, Dong M, Liang B, Boudreau G, Abou-Zeid H. Delay-tolerant OCO with long-term constraints: Algorithm and its application to network resource allocation. IEEE/ACM Transactions on Networking, 2022, 31(1): 147−163 [20] Wan Y Y, Tu W W, Zhang L J. Online strongly convex optimization with unknown delays. Machine Learning, 2022, 111(3): 871−893 doi: 10.1007/s10994-021-06072-w [21] Wang D, Liu J X, Lian J, Liu Y, Wang Z, Wang W. Distributed delayed dual averaging for distributed optimization over time-varying digraphs. Automatica, 2023, 150: 110869 doi: 10.1016/j.automatica.2023.110869 [22] Bedi A S, Koppel A, Rajawat K. Asynchronous online learning in multi-agent systems with proximity constraints. IEEE Transactions on Signal and Information Processing over Networks, 2019, 5(3): 479−94 doi: 10.1109/TSIPN.2019.2902493 [23] Inoue K, Hayashi N, Takai S. Distributed online optimization with dynamic coupling constraints under time-varying communication delays. IEEE Access, 2023, 11: 87256−87269 doi: 10.1109/ACCESS.2023.3305529 [24] Liu B, Wen G, Fang X, Huang T, Chen G. Distributed online generalized Nash Equilibrium learning in multi-cluster games: A delay-tolerant algorithm. arXiv preprint arXiv: 2407.03578. 2024. [25] Cao X Y, Başar T. Decentralized online convex optimization based on signs of relative states. Automatica, 2021, 129: 109676 doi: 10.1016/j.automatica.2021.109676 [26] Flaxman A D, Kalai A T, McMahan H B. Online convex optimization in the bandit setting: Gradient descent without a gradient. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 2005. 385−394 [27] Cao X Y, Başar T. Decentralized online convex optimization with feedback delays. IEEE Transactions on Automatic Control, 2021, 67(6): 2889−904 [28] Wang C, Xu S Y. Distributed online constrained optimization with feedback delays. IEEE Transactions on Neural Networks and Learning Systems, 2022, 35(2): 1708−1720 [29] Xiong M H, Zhang B Y, Yuan D M, Zhang Y J, Chen J. Event-triggered distributed online convex optimization with delayed bandit feedback. Applied Mathematics and Computation, 2023, 445: 127865 doi: 10.1016/j.amc.2023.127865 [30] Kocic M, Brady D, Stojanovic M. Sparse equalization for real-time digital underwater acoustic communications. In : 'Challenges of Our Changing Global Environment'. Conference Proceedings. 1995. 3 : 1417−1422 [31] Yi X L, Li X X, Xie L H, Johansson K H. Distributed online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Signal Processing, 2020, 68: 731−746 doi: 10.1109/TSP.2020.2964200 [32] Xiong M H, Ho D W C, Zhang B Y, Yuan D M, Xu S Y. Distributed online mirror descent with delayed subgradient and event-triggered communications. IEEE Transactions on Network Science and Engineering, 2024, 11(2): 1702−1715 doi: 10.1109/TNSE.2023.3329523 [33] Meng M, Li X X, Chen J. Decentralized Nash equilibria learning for online game with Bandit feedback. IEEE Transactions on Automatic Control, 2024, 69(6): 4050−4057 doi: 10.1109/TAC.2023.3342850 [34] Nguyen T A, Kim Thang N, Trystram D. Handling Delayed Feedback in Distributed online optimization: A projection-free approach. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. 2024. 197−211 [35] Matamoros J. Asynchronous online ADMM for consensus problems. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2017. 5875−5879 [36] Li X X, Yi X L, Xie L H. Distributed online optimization for multi-agent networks with coupled inequality constraints. IEEE Transactions on Automatic Control, 2020, 66(8): 3575−91 [37] Ajalloeian A, Simonetto A, Dall’Anese E. Inexact online proximal-gradient method for time-varying convex optimization. In: 2020 American Control Conference (ACC). 2020. 2850−2857 [38] 杨涛, 徐磊, 易新蕾, 张圣军, 陈蕊娟, 李渝哲. 基于事件触发的分布式优化算法. 自动化学报, 2022, 48(1): 133−143Yang Tao, Xu Lei, Yi Xin-Lei, Zhang Sheng-Jun, Chen Rui-Juan, Li Yu-Zhe. Event-triggered distributed optimization algorithms. Acta Automatica Sinica, 2022, 48(1): 133−143 [39] Zhang J Q, You K Y, Başar T. Distributed discrete-time optimization in multiagent networks using only sign of relative state. IEEE Transactions on Automatic Control, 2018, 64(6): 2352−2367 [40] Iutzeler F, Ciblat P, Jakubowicz J. Analysis of max-consensus algorithms in wireless channels. IEEE Transactions on Signal Processing, 2012, 60(11): 6103−6107 doi: 10.1109/TSP.2012.2211593 [41] Cao X Y, Liu K J R. Online convex optimization with time-varying constraints and bandit feedback. IEEE Transactions on automatic control, 2018, 64(7): 2665−2680 [42] Yi X L, Li X X, Ya ng, T, Xie L H, Chai T Y, Johansson K H. Distributed bandit online convex optimization with time-varying coupled inequality constraints. IEEE Transactions on Automatic Control, 2020, 66(10): 4620−4635 [43] Ito S. An optimal algorithm for bandit convex optimization with strongly-convex and smooth loss. In: International Conference on Artificial Intelligence and Statistics. 2020. 2229−2239 [44] Hazan E, Levy K. Bandit convex optimization: Towards tight bounds. Advances in Neural Information Processing Systems. 2014, 27 [45] Cassel A, Koren T. Bandit linear control. Advances in Neural Information Processing Systems, 2020, 33: 8872−82 [46] Parikh N, Boyd S. Proximal algorithms. Foundations and trendsⓇ in Optimization, 2014, 1(3): 127−239 doi: 10.1561/2400000003 -
下载:
计量
- 文章访问数: 13
- HTML全文浏览量: 8
- 被引次数: 0
