# Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates

arXiv: https://arxiv.org/abs/2605.26919 · HTML: https://mlsanity.com/paper/2605.26919/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 51 references that are in the map.
- First posted on arXiv 26 May 2026.

## Builds on (most cited first, 10 of 10)

- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Wild-Time: A Benchmark of in-the-Wild Distribution Shift over Time](https://mlsanity.com/paper/2211.14238/) (2022)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Handling Concept Drift via Model Reuse](https://mlsanity.com/paper/1809.02804/) (2018)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)

## Abstract (arXiv)

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 Theta(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 three 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.