Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
Authors: Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos
JMLR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | Yu-Guan Hsieh EMAIL Franck Iutzeler EMAIL Univ. Grenoble Alpes, LJK, Grenoble, 38000, France Jérôme Malick EMAIL Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, 38000 Grenoble, France Panayotis Mertikopoulos EMAIL Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000, Grenoble, France & Criteo AI Lab |
| Pseudocode | Yes | Algorithm 1: (DDA) from the point of view of agent i ... Algorithm 2: Ada Delay Dist from the point of view of agent i ... Algorithm 3: Ada Delay+ |
| Open Source Code | No | No explicit statement about releasing source code or a link to a code repository for the described methodology is provided in the paper. The license information refers to the paper itself, not its code. |
| Open Datasets | No | The paper focuses on theoretical analysis, framework development, and algorithm design. It does not use or reference any specific datasets for empirical evaluation, hence no information regarding public availability or access is provided. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets. Therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes a theoretical framework and algorithms. It does not present experimental results that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper focuses on theoretical aspects of online optimization. It does not mention any specific software dependencies or their versions that would be required to reproduce experimental results. |
| Experiment Setup | No | The paper is theoretical and analyzes algorithms with mathematical proofs and regret bounds. It does not detail an experimental setup with specific hyperparameter values or training configurations for empirical evaluation. |