Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
arXiv:2012.11579
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.
arXiv commentAccepted by Journal of Machine Learning Research (JMLR)
References in corpus (13)
- Convergence of Edge Computing and Deep Learning: A Comprehensive Survey
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- Adaptive Bound Optimization for Online Convex Optimization
- The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
- Bandits with Delayed, Aggregated Anonymous Feedback
- Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
- Stochastic Bandit Models for Delayed Conversions
- Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression
- Nonstochastic Bandits with Composite Anonymous Feedback
- Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
- A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds
- Real-Time Optimisation for Online Learning in Auctions