Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory

Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Mengxiao Zhang · 2026

Read Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory by Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Mengxiao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-06902.txt.

Description

Hao Qiu and three co-authors study online learning where the price of changing one's mind shifts from round to round. A learner pays both for wrong guesses and for moving its choice, and past work held that move price fixed. This paper lets it vary freely over time, a small change that breaks old guarantees.

The team builds a new algorithm with the first bound of its kind that adapts to the best moving target in this setting. When move prices drop to zero, the bound recovers the best known rates for both fixed and moving targets. Two uses show its reach: learning with late feedback and learning with time-varying memory both reduce to shifting move prices, with a fresh reduction for the late-feedback case. The bound's direct, first-order link to move prices is what makes the sharp guarantees work in both uses.

Catalog record

CREATOREmmanuel Esposito, Andrew Jacobsen, Hao Qiu, Mengxiao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-06902

Browse the full library · About the Tower of Babel