Revisiting multi-agent asynchronous online optimization with delays: the strongly convex case

Abstract

We revisit multi-agent asynchronous online optimization with delays, where only one of the agents becomes active for making the decision at each round, and the corresponding feedback is received by all the agents after unknown delays. Although previous studies have established an O(\sqrt{dT}) regret bound for this problem, they assume that the maximum delay d is knowable or the arrival order of feedback satisfies a special property, which may not hold in practice. In this paper, we surprisingly find that when the loss functions are strongly convex, these assumptions can be eliminated, and the existing regret bound can be significantly improved to O(d\log T) meanwhile. Specifically, to exploit the strong convexity of functions, we first propose a delayed variant of the classical follow-the-leader algorithm, namely FTDL, which is very simple but requires the full information of functions as feedback. Moreover, to handle the more general case with only the gradient feedback, we develop an approximate variant of FTDL by combining it with surrogate loss functions. Experimental results show that the approximate FTDL outperforms the existing algorithm in the strongly convex case.

Graphical abstract

Keywords

strongly convex optimization / multi-agent system / online learning / delayed feedback

References

[1] Shalev-Shwartz S . Online learning and online convex optimization. Foundations and Trends in Machine Learning, 2011, 4( 2): 107–194

[2] Hazan E. Introduction to online convex optimization. Foundations and Trends in Optimization, 2016, 2(3−4): 157−325

[3] Tan B, Srikant R . Online advertisement, optimization and stochastic networks. IEEE Transactions on Automatic Control, 2012, 57( 11): 2854–2868

[4] Lin J, Li Y, Lian J . A novel recommendation system via L0-regularized convex optimization. Neural Computing and Applications, 2020, 32( 6): 1649–1663

[5] Agarwal A, Hazan E, Kale S, Schapire R E. Algorithms for portfolio management based on the newton method. In: Proceedings of the 23rd International Conference on Machine Learning. 2006, 9−16

[6] Zinkevich M. Online convex programming and generalized infinitesimal gradient ascent. In: Proceedings of the 20th International Conference on Machine Learning. 2003, 928−935

[7] Hazan E, Agarwal A, Kale S. Logarithmic regret algorithms for online convex optimization. Machine Learning, 2007, 69(2−3): 169−192

[8] Abernethy J D, Bartlett P L, Rakhlin A, Tewari A. Optimal strategies and minimax lower bounds for online convex games. In: Proceedings of the 21st Annual Conference on Learning Theory. 2008, 415−424

[9] Duchi J, Hazan E, Singer Y . Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 2011, 12: 2121–2159

[10] Kingma D P, Ba J. Adam: a method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations. 2015, 1−15

[11] Wang G, Lu S, Cheng Q, Tu W W, Zhang L. SAdam: a variant of Adam for strongly convex functions. In: Proceedings of the 8th International Conference on Learning Representations. 2020, 1−21

[12] Wan Y, Zhang L. Projection-free online learning over strongly convex sets. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 10076−10084

[13] Wan Y, Zhang L . Efficient adaptive online learning via frequent directions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44( 10): 6910–6923

[14] Olfati-Saber R. Distributed Kalman filtering for sensor networks. In: Proceedings of the 46th IEEE Conference on Decision and Control. 2007, 5492−5498

[15] Tsagkatakis G, Savakis A . Online distance metric learning for object tracking. IEEE Transactions on Circuits and Systems for Video Technology, 2011, 21( 12): 1810–1821

[16] Kia S S, Cortés J, Martínez S . Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Automatica, 2015, 55: 254–264

[17] Souza É L, Nakamura E F, Pazzi R W . Target tracking for sensor networks: a survey. ACM Computing Surveys (CSUR), 2017, 49( 2): 30

[18] Hsieh Y G, Iutzeler F, Malick J, Mertikopoulos P . Multi-agent online optimization with delays: asynchronicity, adaptivity, and optimism. The Journal of Machine Learning Research, 2022, 23( 1): 78

[19] Weinberger M J, Ordentlich E . On delayed prediction of individual sequences. IEEE Transactions on Information Theory, 2002, 48( 7): 1959–1976

[20] Joulani P, György A, Szepesvári C. Online learning under delayed feedback. In: Proceedings of the 30th International Conference on Machine Learning. 2013, 1453−1461

[21] Quanrud K, Khashabi D. Online learning with adversarial delays. In: Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1. 2015, 1270−1278

[22] Joulani P, György A, Szepesvári C. Delay-tolerant online convex optimization: unified analysis and adaptive-gradient algorithms. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 1744−1750

[23] Wan Y, Tu W W, Zhang L . Online strongly convex optimization with unknown delays. Machine Learning, 2022, 111( 3): 871–893

[24] Hannan J. Approximation to Bayes risk in repeated play. In: Contributions to the Theory of Games, Volume III, Annals of Mathematics Studies. Princeton: Princeton University Press, 1957, 97−139

[25] Kalai A, Vempala S . Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 2005, 71( 3): 291–307

[26] Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004

[27] Shalev-Shwartz S, Singer Y. Convex repeated games and fenchel duality. In: Proceedings of the 20th International Conference on Neural Information Processing Systems. 2006, 1265−1272

[28] Langford J, Smola A J, Zinkevich M. Slow learners are fast. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems. 2009, 2331−2339

[29] McMahan H B, Streeter M. Delay-tolerant algorithms for asynchronous distributed online learning. In: Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2. 2014, 2915−2923

[30] Li B, Chen T, Giannakis G B. Bandit online learning with unknown delays. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. 2019, 993−1002

[31] Héliou A, Mertikopoulos P, Zhou Z. Gradient-free online learning in games with delayed rewards. In: Proceedings of the 37th International Conference on Machine Learning. 2020, 390

[32] Flaspohler G E, Orabona F, Cohen J, Mouatadid S, Oprescu M, Orenstein P, Mackey L. Online learning with optimism and delay. In: Proceedings of the 38th International Conference on Machine Learning. 2021, 3363−3373

[33] Wan Y, Tu W W, Zhang L. Online Frank-Wolfe with arbitrary delays. In: Proceedings of the 36th International Conference on Neural Information Processing Systems. 2022, 1432

[34] Wan Y, Yao C, Song M, Zhang L. Improved regret for bandit convex optimization with delayed feedback. In: Proceedings of the 38th International Conference on Neural Information Processing Systems. 2024, 5

[35] Wan Y, Yao C, Song M, Zhang L. Non-stationary online convex optimization with arbitrary delays. In: Proceedings of the 41st International Conference on Machine Learning. 2024, 2045

[36] Wu P, Huang H, Liu Z. Online sequential decision-making with unknown delays. In: Proceedings of the ACM Web Conference 2024. 2024, 4028−4036

[37] Cesa-Bianchi N, Freund Y, Haussler D, Helmbold D P, Schapire R E, Warmuth M K . How to use expert advice. Journal of the ACM (JACM), 1997, 44( 3): 427–485

[38] Garber D, Hazan E . A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 2016, 26( 3): 1493–1528

[39] Hazan E, Kale S. Projection-free online learning. In: Proceedings of the 29th International Conference on Machine Learning. 2012, 1843−1850

[40] Chang C C, Lin C J . LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2( 3): 27

[41] Qiu H, Esposito E, Zhang M. Exploiting curvature in online convex optimization with delayed feedback. In: Proceedings of the 42nd International Conference on Machine Learning. 2025, 50448−50479

RIGHTS & PERMISSIONS

Higher Education Press