Decentralized Online Convex Optimization with Unknown Feedback Delays
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (30) · 25000-25008
DOI: 10.1609/aaai.v40i30.39688 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Hao Qiu und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Decentralized online convex optimization (D-OCO), where multiple agents within a network collaboratively learn optimal decisions in real-time, arises naturally in applications such as federated learning, sensor networks, and multi-agent control. In this paper, we study D-OCO under unknown, time- and agent-varying feedback delays. While recent work has addressed this problem~\citep{nguyen2024handling}, existing algorithms assume prior knowledge of the total delay over agents and still suffer from suboptimal dependence on both the delay and network parameters. To overcome these limitations, we propose a novel algorithm that achieves an improved regret bound of Õ(N √d_tot + N √( T / √(1 − σ₂) )), where d_tot denotes the average total delay across agents, N is the number of agents, and 1 − σ₂ is the spectral gap of the network. We also prove a lower bound showing that our upper bound is tight up to logarithmic factors. Our approach builds upon recent advances in D-OCO~\citep{wan2024nearly}, but crucially incorporates an adaptive learning rate mechanism via a decentralized communication protocol. This enables each agent to estimate delays locally using a gossip-based strategy without the prior knowledge of the total delay. We further extend our framework to the strongly convex setting and derive a sharper regret bound. Experimental results validate the effectiveness of our approach, showing improvements over existing benchmark algorithms.
Zitieren
APA
Qiu, H., Zhang, M., & Achddou, J. (2026). Decentralized Online Convex Optimization with Unknown Feedback Delays. Proceedings of the AAAI Conference on Artificial Intelligence, 40(30), 25000-25008. https://doi.org/10.1609/aaai.v40i30.39688
Vancouver
Qiu H, Zhang M, Achddou J. Decentralized Online Convex Optimization with Unknown Feedback Delays. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(30):25000-25008. doi:10.1609/aaai.v40i30.39688
BibTeX
@article{Qiu2026,
author = {Qiu, Hao and Zhang, Mengxiao and Achddou, Juliette},
title = {Decentralized Online Convex Optimization with Unknown Feedback Delays},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {30},
pages = {25000--25008},
doi = {10.1609/aaai.v40i30.39688}
}
EUVIMED