Publication Radar · Source metadata
Strongly Adaptive Online Learning with Time-Varying Movement Costs
Publication record
Bibliographic evidence describes where and when a record appeared. It does not validate scientific claims.
First public release: 2026-10-23 · Indexed by Pub-AI: 2026-10-27 UTC
Strongly Adaptive Online Learning with Time-Varying Movement Costs
Preprint posted: 2026-10-23 · Original record ↗
- arxiv
- 2610.32740
Explicit source versions (2)
- v1 · 2026-10-23
- v2 · 2026-11-07
- Preprint available
Source date: 2026-10-23 · First detected: 2026-10-27 UTC · Historical baseline
Source evidence (4)
- Official evidence ↗ · atom:published (official metadata)
- Official evidence ↗ · atom:published (official metadata)
- Official evidence ↗ · atom:published (official metadata)
- Official evidence ↗ · atom:published (official metadata)
- Explicit source version detected · v2
Source date: 2026-11-07 · First detected: 2026-11-10 UTC
Source evidence (2)
- Official evidence ↗ · atom:id explicit version (official metadata)
- Official evidence ↗ · atom:id explicit version (official metadata)
Abstract · arxiv
We study online convex optimization (OCO) with time-varying movement costs, where the learner incurs both a loss and a time-dependent penalty for changing its decisions. While previous work has established dynamic regret guarantees for this setting, obtaining strongly adaptive guarantees that hold simultaneously over arbitrary intervals remains an open challenge. We address this by developing a new algorithm which, for every interval $[a,b]\subseteq[T]$ and arbitrary comparator sequence, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $λ_t$ is the movement-cost coefficient at round~$t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of our development, we further obtain strongly-adaptive dynamic regret guarantees under arbitrary delayed feedback with a refined dependence on interval-restricted cumulative delays. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.
