Logo image
Universal Online Convex Optimization With Delayed Feedback
Preprint   Open access

Universal Online Convex Optimization With Delayed Feedback

Hao Qiu, Andrew Jacobsen, Emmanuel Esposito and Mengxiao Zhang
arXiv
arXiv
10/20/2026
DOI: 10.48550/arxiv.2610.28058
url
https://doi.org/10.48550/arxiv.2610.28058View
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

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.
Computer Science - Learning

Details

Metrics

1 Record Views
Logo image