Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Secure Dynamic Event-triggered Consensus Under Asynchronous Denial of Service
This article proposes a secure implementation for consensus using a dynamic event-triggered (DET) communication scheme in high-order nonlinear multi-agent systems (MAS) under asynchronous (distributed) denial of service …
Optimization in Open Networks via Dual Averaging
In networks of autonomous agents (e.g., fleets of vehicles, scattered sensors), the problem of minimizing the sum of the agents' local functions has received a lot of interest. We tackle here this distributed optimizatio…
Distributed OptimizationSingle-Rollout Asynchronous Optimization for Agentic Reinforcement Learning
Reinforcement learning (RL) is becoming increasingly important for post-training large language models (LLMs). Previous RL pipelines for LLMs were mostly synchronous and batch-interleaved, which is inefficient for long-h…
Reinforcement LearningRevisiting Distributed Synchronous SGD
Distributed training of deep learning models on large-scale training data is typically conducted with asynchronous stochastic optimization to maximize the rate of updates, at the cost of additional noise introduced from …
Stochastic OptimizationRevisiting Distributed Synchronous SGD
Distributed training of deep learning models on large-scale training data is typically conducted with asynchronous stochastic optimization to maximize the rate of updates, at the cost of additional noise introduced from …
Stochastic Optimization