Publication Radar · Source metadata

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

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

preprint

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

Preprint posted: 2026-10-23 · Original record ↗

arxiv
2610.32740
Explicit source versions (2)
  • v1 · 2026-10-23
  • v2 · 2026-11-07
  1. Preprint available

    Source date: 2026-10-23 · First detected: 2026-10-27 UTC · Historical baseline

    Source evidence (4)
  2. Explicit source version detected · v2

    Source date: 2026-11-07 · First detected: 2026-11-10 UTC

    Source evidence (2)
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.