Adaptive online convex optimization with unknown feedback delay

Online Convex Optimization (OCO) with unknown feedback delay presents a considerable challenge, particularly when the delay period is not available a priori. In this paper, we propose an adaptive delayed mirror descent (ADMD) algorithm to address this issue, which incorporates a virtual iterate sequence and a learning rate based on the cumulative missed feedback instances. This method improves regret bounds and eliminates the need for prior knowledge of the delay period. Furthermore, we transform the ADMD algorithm into adaptive delayed dual averaging (ADDA) using lazy gradient descent, establishing a connection between these two frameworks. To further enhance the algorithm's adaptability, we introduce a novel delayed doubling trick. Through extensive experiments, we demonstrate the efficacy of our approach, showing superior performance compared to existing algorithms.