Distributed Online Convex Optimization With Unknown Delays

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 -