pipette
ESEspañol

Universal Online Convex Optimization With Delayed Feedback

Hao Qiu, Andrew Jacobsen, Emmanuel Esposito, Mengxiao Zhang

Preprint

In the authors' words

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 and delays up to doubly logarithmic factors: roughly for convex losses and rates with curved losses, where is the total cumulative delay and 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 , while retaining the complementary dependence.

Main resultLimitation the authors admit

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.