Metraipolis › archive › dc_86e8fb4cbff2

Strongly Adaptive Online Learning with Time-Varying Movement Costs — arXiv:2610.32740

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.32740
License (as archived): CC0-1.0
Archived: 2026-10-26T20:12:31.759Z
SHA-256 of the archived text: 5452cc6161d31c2d07192fb714cd35f5d91b530e6510f5436c57efbf4b86bde0
Stable URL of this page: https://metraipolis.com/documento/dc_86e8fb4cbff2

How to cite

Strongly Adaptive Online Learning with Time-Varying Movement Costs — arXiv:2610.32740 — arXiv (en), https://arxiv.org/abs/2610.32740 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_86e8fb4cbff2 (Metraipolis archive dc_86e8fb4cbff2, sha256 5452cc6161d31c2d07192fb714cd35f5d91b530e6510f5436c57efbf4b86bde0)

BibTeX

@misc{dc86e8fb4cbff2,
  title = {Strongly Adaptive Online Learning with Time-Varying Movement Costs — arXiv:2610.32740},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.32740},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_86e8fb4cbff2; sha256 5452cc6161d31c2d07192fb714cd35f5d91b530e6510f5436c57efbf4b86bde0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.32740. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval $[a,b] \subseteq [T]$, 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+\lambda_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 $\lambda_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 this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.32740 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-26T19:49:03.424Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).