Preprint
Universal Online Convex Optimization With Delayed Feedback
arXiv
arXiv
10/20/2026
DOI: 10.48550/arxiv.2610.28058
Abstract
We study universal online convex optimization with delayed feedback. We develop a single algorithm that simultaneously adapts to general convex, strongly convex, and exp-concave losses without prior knowledge of the curvature class or parameters. Our regret bounds match the best known dependence on the time horizon$T$and delays up to doubly logarithmic factors: roughly$\sqrt{T + d_{\mathrm{tot}}}$for convex losses and$σ_{\max}\log T$rates with curved losses, where$d_{\mathrm{tot}}$is the total cumulative delay and$σ_{\max}$is the maximum number of simultaneously missing observations. Our main technical contribution is a delayed meta-learner with a second-order excess-loss guarantee, which enables curvature-adaptive aggregation of delayed base learners. In addition, our new exp-concave base learner yields a sharper regret bound which improves the state-of-the-art delay dependence by replacing the maximum delay with the potentially much smaller$σ_{\max}$ , while retaining the complementary$\sqrt{d_{\mathrm{tot}}}$dependence.
Details
- Title: Subtitle
- Universal Online Convex Optimization With Delayed Feedback
- Creators
- Hao Qiu - Duke-NUS Medical SchoolAndrew Jacobsen - Universitat Pompeu FabraEmmanuel Esposito - ENSAE ParisMengxiao Zhang - University of Iowa
- Resource Type
- Preprint
- Publication Details
- arXiv
- DOI
- 10.48550/arxiv.2610.28058
- ISSN
- 2331-8422
- Publisher
- arXiv
- Language
- English
- Date posted
- 10/20/2026
- Academic Unit
- Business Analytics
- Record Identifier
- 9985247499502771
Metrics
1 Record Views