Online learning adapts strongly with changing costs and feedback delays
Strongly Adaptive Online Learning with Time-Varying Movement Costs
Machine Learning
Summary
This paper deals with teaching computers how to make good decisions when both the problems they face and the costs of changing their choices vary over time. The authors developed a new way for the computer to learn that performs well even if the environment changes unexpectedly or the feedback is delayed. Their method breaks down the problem into parts and uses a clever approach involving 'sleeping experts,' which were not studied before with movement costs. This helps the computer keep up with complex environments more accurately than before.
What this means in practice
- •For adaptive control engineers: Improve control strategies where switching costs and environmental conditions vary unpredictably over time.
- •For online advertising teams: Adjust ad strategies dynamically accounting for varying costs of changing ad placements and delayed performance feedback.
Authors
Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang
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] \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+λ_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.