Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates
This work addresses the robustness-agility trade-off in tuning-free online model selection, offering a practical solution for adaptive learning under unknown distribution shifts.
The paper proposes an optimistic online mirror descent algorithm with safeguarded large learning rates (up to Θ(T)) to resolve adaptation lag in online model selection under non-stationary environments. The algorithm achieves near-optimal worst-case guarantees while reducing adaptation lag from hundreds of rounds to a few rounds, as demonstrated on synthetic and eleven real-world datasets.
Maintaining predictive accuracy in non-stationary environments requires online model selection to adapt autonomously to unknown distribution shifts. However, existing tuning-free algorithms face a fundamental trade-off between robustness and agility. Specifically, to ensure dynamic regret bounds, they must restrict learning rates to small constants (e.g., $O(1)$). This restriction inevitably causes significant adaptation lag during abrupt changes. To resolve this, we propose a novel optimistic online mirror descent that utilizes safeguarded large learning rates up to $Θ(T)$, where $T$ is the number of rounds. Our key technical contribution is a post-hoc penalty mechanism that dynamically monitors unstable updates and excludes learning rates incurring excessive regret, eliminating the need for restrictive a priori constraints. We show that the cumulative penalty remains $O(\log T)$, allowing our algorithm to match near-optimal worst-case guarantees while achieving superior rates in benign cases. Empirical evaluations on synthetic and eleven diverse real-world datasets demonstrate that our approach reduces the adaptation lag from hundreds of rounds to a few rounds, consistently outperforming tuning-free baselines.