Logo image
Back
Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
Preprint   Open access

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

Emmanuel Esposito, Andrew Jacobsen, Hao Qiu and Mengxiao Zhang
ArXiv.org
Cornell University
02/06/2026
DOI: 10.48550/arxiv.2602.06902
url
https://doi.org/10.48550/arxiv.2602.06902View
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

In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficientsλ_(t)to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing\widetilde{𝓞}{(}{√(̅1̅+̅P̅_̅(̅T̅)̅)̅(̅T̅+̅∑̅_̅(̅t̅)̅ ̅λ̅_̅(̅t̅)̅)̅})regret, whereP_(T)is the path length of the comparator sequence overTrounds. This recovers the optimal guarantees for both static and dynamic regret in standard OCO as a special case whereλ_(t)=0for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.
 Computer Science - Learning Statistics - Machine Learning

Details

Metrics

3 Record Views
Logo image