Logo image
Back
Decentralized Online Convex Optimization with Unknown Feedback Delays
Journal article   Open access

Decentralized Online Convex Optimization with Unknown Feedback Delays

Hao Qiu, Mengxiao Zhang and Juliette Achddou
Proceedings of the ... AAAI Conference on Artificial Intelligence, Vol.40(30), pp.25000-25008
03/14/2026
DOI: 10.1609/aaai.v40i30.39688
url
https://doi.org/10.1609/aaai.v40i30.39688View
Published (Version of record) Open Access

Abstract

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~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~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.

Details

Metrics

1 Record Views
Logo image