Skip to Main content Skip to Navigation
New interface
Journal articles

Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism

Yu-Guan Hsieh 1, 2 Franck Iutzeler 1 Jérôme Malick 1 Panayotis Mertikopoulos 2, 3 
1 DAO - Données, Apprentissage et Optimisation
LJK - Laboratoire Jean Kuntzmann
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we provide a general framework for studying multi-agent online learning problems in the presence of delays and asynchronicities. Specifically, we propose and analyze a class of adaptive dual averaging schemes in which agents only need to accumulate gradient feedback received from the whole system, without requiring any between-agent coordination. In the single-agent case, the adaptivity of the proposed method allows us to extend a range of existing results to problems with potentially unbounded delays between playing an action and receiving the corresponding feedback. In the multi-agent case, the situation is significantly more complicated because agents may not have access to a global clock to use as a reference point; to overcome this, we focus on the information that is available for producing each prediction rather than the actual delay associated with each feedback. This allows us to derive adaptive learning strategies with optimal regret bounds, even in a fully decentralized, asynchronous environment. Finally, we also analyze an "optimistic" variant of the proposed algorithm which is capable of exploiting the predictability of problems with a slower variation and leads to improved regret bounds.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-03410422
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Sunday, October 31, 2021 - 7:09:45 PM
Last modification on : Tuesday, October 25, 2022 - 4:20:38 PM
Long-term archiving on: : Tuesday, February 1, 2022 - 6:26:15 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03410422, version 1

Citation

Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Machine Learning Research, 2022, 23 (78), pp.1--49. ⟨hal-03410422⟩

Share

Metrics

Record views

80

Files downloads

81