Logo image
Back
Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Preprint   Open access

Exploiting Curvature in Online Convex Optimization with Delayed Feedback

Hao Qiu, Emmanuel Esposito and Mengxiao Zhang
ArXiV.org
Cornell University
06/09/2025
DOI: 10.48550/arxiv.2506.07595
url
https://doi.org/10.48550/arxiv.2506.07595View
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

In this work, we study the online convex optimization problem with curved losses and delayed feedback. When losses are strongly convex, existing approaches obtain regret bounds of order dmax ln T , where dmax is the maximum delay and T is the time horizon. However, in many cases, this guarantee can be much worse than √dtot as obtained by a delayed version of online gradient descent, where dtot is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order min{σmax ln T, √dtot}, where σmax is the maximum number of missing observations. We then consider expconcave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret min{dmaxn ln T, √dtot} where n is the dimension. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.
 Computer Science - Learning Statistics - Machine Learning

Details

Metrics

46 Record Views
Logo image