TY - JOUR
T1 - Distributed Online Convex Optimization With Unknown Delays
AU - Wu, Ping
AU - Huang, Heyan
AU - Lu, Haolin
AU - Liu, Zhengyang
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2026
Y1 - 2026
N2 - In the field of distributed online convex optimization with delayed feedback, previous works have primarily focused on scenarios with fixed and predetermined delays. In this paper, we consider a more complex and realistic scenario with unknown delays. Here the delayed periods vary among agents and iterations, and even the time stamps could be unknown. To address the challenges arising from asynchronous delayed optimization and communication within the network, we propose a delayed distributed online gradient descent algorithm that incorporates an agent-specific and delay-tracking learning rate dependent on the amount of feedback received from each local agent. Specifically, we achieve regret bounds of O(√d̄T) and O(d̄log T) for general convex and strongly convex loss functions, respectively, where d̄ denotes the average maximum delay among agents and T denotes the total horizon. Furthermore, we extend the algorithm and theoretical guarantees to bandit setting by leveraging multi-point gradient estimators. We offer empirical experiments to substantiate the effectiveness of the proposed algorithms. To the best of our knowledge, this work is the first step to address distributed online convex optimization under the universal delayed setting.
AB - In the field of distributed online convex optimization with delayed feedback, previous works have primarily focused on scenarios with fixed and predetermined delays. In this paper, we consider a more complex and realistic scenario with unknown delays. Here the delayed periods vary among agents and iterations, and even the time stamps could be unknown. To address the challenges arising from asynchronous delayed optimization and communication within the network, we propose a delayed distributed online gradient descent algorithm that incorporates an agent-specific and delay-tracking learning rate dependent on the amount of feedback received from each local agent. Specifically, we achieve regret bounds of O(√d̄T) and O(d̄log T) for general convex and strongly convex loss functions, respectively, where d̄ denotes the average maximum delay among agents and T denotes the total horizon. Furthermore, we extend the algorithm and theoretical guarantees to bandit setting by leveraging multi-point gradient estimators. We offer empirical experiments to substantiate the effectiveness of the proposed algorithms. To the best of our knowledge, this work is the first step to address distributed online convex optimization under the universal delayed setting.
KW - Bandit setting
KW - distributed convex optimization
KW - multi-agent network
KW - unknown delays
UR - https://www.scopus.com/pages/publications/105033483697
U2 - 10.1109/TAC.2026.3676242
DO - 10.1109/TAC.2026.3676242
M3 - Article
AN - SCOPUS:105033483697
SN - 0018-9286
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
ER -