Strongly Adaptive Online Learning with Time-Varying Movement Costs
Abstract
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] ⊆ [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+λ_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], gt 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 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.
Related
- Online Learning-to-Defer with Varying Experts
- FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
- Adaptive Beam Hopping and Power Control for Dual-Layer Over-the-Air Online Federated Learning in LEO Satellite Networks
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
- Online Optimization with Unknown Time-Varying Parameters Using Noisy Gradient Measurements
BibTeX
@misc{jacobsen2026strongly,
title = {{Strongly Adaptive Online Learning with Time-Varying Movement Costs}},
author = {Andrew Jacobsen and Emmanuel Esposito and Hao Qiu and Mengxiao Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32740},
eprint = {2610.32740},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32740},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Strongly Adaptive Online Learning with Time-Varying Movement Costs
AU - Andrew Jacobsen
AU - Emmanuel Esposito
AU - Hao Qiu
AU - Mengxiao Zhang
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32740
UR - https://arxiv.org/abs/2610.32740
AB - 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] ⊆ [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+λ_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 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.
ER -