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

arXiv: https://arxiv.org/abs/2602.06902 · HTML: https://mlsanity.com/paper/2602.06902/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 60 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 30 of 43)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)

## Built on by (most cited first, 2 of 2)

- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Dynamic Regret in Online Convex Optimization with Indicator Switching Costs](https://mlsanity.com/paper/2609.30556/) (2026)

## Abstract (arXiv)

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 widetildeO(√(M2+MPT)(T+sumt λt)) regret, where PT is the path length of the comparator sequence over T rounds and M is the maximal comparator norm. Our result recovers the optimal adaptive rates for both static and dynamic regret in OCO as the special case where λt=0 for 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.