Strongly Adaptive Online Learning with Time-Varying Movement Cost

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 $$\begin{gathered} \tilde{\mathcal{O}}\left(\sqrt{(D^2+D{P}_{[a,b]}){\sum }_{t\in [a,b]}( \\ |g_t \\ {|}^2+{\lambda }_t \\ |g_t \\ |)}\right) \end{gathered}$$, 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.