Conference proceeding
Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Proceedings of the 42nd International Conference on Machine Learning, PMLR, Vol.267, pp.50448-50479
2025
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 dmaxlnT, 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{σmaxlnT,dtot−−−√}, where σmax is the maximum number of missing observations. We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret min{dmaxnlnT,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.
Details
- Title: Subtitle
- Exploiting Curvature in Online Convex Optimization with Delayed Feedback
- Creators
- Hao Qiu - University of MilanEmmanuel Esposito - University of MilanMengxiao Zhang - University of Iowa, United States
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 42nd International Conference on Machine Learning, PMLR, Vol.267, pp.50448-50479
- ISSN
- 2640-3498
- eISSN
- 2640-3498
- Grant note
- Università degli Studi di Milano (http://data.elsevier.com/vocabulary/SciValFunders/100012352) PSR 2021-GSA-Linea 6 / Università degli Studi di Milano (http://data.elsevier.com/vocabulary/SciValFunders/100012352) Future Artificial Intelligence Research 101120237 / EU Horizon CL4-2022-HUMAN-02 research and innovation action
- Language
- English
- Date published
- 2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9985091808502771
Metrics
4 Record Views