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

• URL: http://arxiv.org/abs/2605.26919v2
• Date: Mon, 01 Jun 2026 03:05:51 GMT
• Title: Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Rates
• Abstract summary: We propose a novel optimistic online mirror descent that utilizes safeguarded large learning rates up to $(T)$.<n>Our key technical contribution is a post-hoc penalty mechanism that dynamically monitors unstable updates and excludes learning rates incurring excessive regret.<n> 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.
• Score: 9.463718838347955
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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 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.

Related papers

• Learning Not to Optimize: Physics-Informed Action-Space Reshaping for Intent-Based Network Control [50.46501177871741]
  We show that LNOQRD reduces small-instance candidates by $75.9%$ while retaining $90.8%$ near-oracle coverage.<n>Experiments show that LNOQRD achieves the highest utility and intent satisfaction, the lowest hard-law violation and post-generation latency.
  arXiv  Detail & Related papers  (2026-08-02T00:27:01Z)
• Near-Optimal Sample Complexity for Online Constrained MDPs [10.479589616736193]
  Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance.<n>Existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies.<n>We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations.
  arXiv  Detail & Related papers  (2026-02-16T05:16:13Z)
• Beyond Greedy Exits: Improved Early Exit Decisions for Risk Control and Reliability [14.00844847268286]
  Early-Exit Deep Neural Networks enable adaptive inference by allowing prediction at intermediary layers.<n>Our framework demonstrates consistent improvements in speedup (1.70-2.10x) with a minimal performance drop (2%) as compared to full model performance.
  arXiv  Detail & Related papers  (2025-09-28T06:05:24Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels [24.314013749328677]
  We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics.<n>We propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels.<n>Our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.
  arXiv  Detail & Related papers  (2025-06-22T22:04:52Z)
• Constrained Linear Thompson Sampling [39.724313550777715]
  Constrained Linear Thompson Sampling (COLTS) is a sampling-based framework that selects actions by solving perturbed linear programs.<n>We develop two main variants: S-COLTS, which ensures zero risk and $widetildeO(sqrtd3 T)$ regret given a safe action, and R-COLTS, which achieves $widetildeO(sqrtd3 T)$ regret and risk with no instance information.
  arXiv  Detail & Related papers  (2025-03-03T20:44:58Z)
• Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling [46.01254613933967]
  Online learning methods are still highly effective for high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications. Many such algorithms rely on fast adaptation to individual errors as a key to their convergence. While such algorithms enjoy low theoretical regret, in real-world deployment they can be sensitive to individual outliers that cause the algorithm to over-correct.
  arXiv  Detail & Related papers  (2024-10-31T03:35:48Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  We present efficient methods for optimizing dynamic regret and adaptive regret.<n>The proposed algorithms require only one gradient query and one function evaluation at each round.<n>We also study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from $O(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits [20.128001589147512]
  We study the problem of non-stationary dueling bandits and provide the first adaptive dynamic regret algorithm for this problem. We show a near-optimal $tildeO(sqrtStexttCW T)$ dynamic regret bound, where $StexttCW$ is the number of times the Condorcet winner changes in $T$ rounds.
  arXiv  Detail & Related papers  (2022-10-25T20:26:02Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  We focus on a class of nonsubmodular functions with special structure, and prove regret guarantees for several variants of the online and approximate online bandit gradient descent algorithms. We derive bounds for the agent's regret in the full information and bandit feedback setting, even if the delay between choosing a decision and receiving the incurred cost is unbounded.
  arXiv  Detail & Related papers  (2022-05-15T08:27:12Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.