Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the agility-robustness trade-off in online model selection for non-stationary environments by introducing an optimistic online mirror descent algorithm. The algorithm employs safeguarded large learning rates, up to $Θ(T)$, and a novel post-hoc penalty mechanism to dynamically monitor and exclude unstable updates, avoiding restrictive a priori constraints. The method achieves near-optimal worst-case dynamic regret guarantees while significantly reducing adaptation lag compared to existing tuning-free algorithms, as demonstrated across synthetic and real-world datasets.
Adaptation lag in online learning can be slashed from hundreds of rounds to just a few by dynamically penalizing unstable updates, unlocking the potential for truly agile model selection.
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.