Decentralized Online Convex Optimization with Unknown Feedback Delays

Hao Qiu; Mengxiao Zhang; Juliette Achddou

doi:10.48550/arxiv.2601.07901

Back

Preprint

Open access

Decentralized Online Convex Optimization with Unknown Feedback Delays

Hao Qiu, Mengxiao Zhang and Juliette Achddou

ArXiv.org

Cornell University

01/12/2026

DOI: 10.48550/arxiv.2601.07901

Files and links (1)

url

https://doi.org/10.48550/arxiv.2601.07901View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. 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 (Nguyen et al., 2024), 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 O N$\sqrt$d tot + N$\sqrt$T (1- $σ$ 2) 1/4 , where T is the total horizon, d tot denotes the average total delay across agents, N is the number of agents, and 1 - $σ$2 is the spectral gap of the network. Our approach builds upon recent advances in D-OCO (Wan et al., 2024a), 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 of O N$δ$ max ln T$α$, where$α$is the strong convexity parameter and$δ$max is the maximum number of missing observations averaged over agents. We also show that our upper bounds for both settings are tight up to logarithmic factors. Experimental results validate the effectiveness of our approach, showing improvements over existing benchmark algorithms.

Computer Science - Artificial Intelligence

Computer Science - Learning

Statistics - Machine Learning

Details

Title: Subtitle: Decentralized Online Convex Optimization with Unknown Feedback Delays
Creators: Hao Qiu
Mengxiao Zhang
Juliette Achddou
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.2601.07901
ISSN: 2331-8422
Publisher: Cornell University; Ithaca, New York
Number of pages: 43 pages
Language: English
Date posted: 01/12/2026
Academic Unit: Business Analytics
Record Identifier: 9985121596302771

Metrics

1 Record Views