CB-RML: Dynamic Regret Minimization via Coin-Betting Regularization and Meta-Learning

We address the challenge of dynamic regret minimization in non-stationary environments, where traditional online learning algorithms struggle to adapt to shifting data distributions. Existing approaches typically require prior knowledge of environmental dynamics or careful parameter tuning, limiting their practical utility. This paper introduces the Coin-Betting Regularized Meta-Learner (CB-RML), a novel framework that achieves parameter-free adaptation while maintaining provable regret guarantees. Our key contributions are threefold: (1) a three-timescale adaptation mechanism combining per-iteration learning rate updates <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\eta_{t+1}^{(k)}=\eta_{0} / \sqrt{1+\sum\Vert\theta_{s}^{(k)}-\theta_{s-1}^{(k)}\Vert^{2}})$</tex>, partition-based restarts, and meta-regularization through <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S_{t}=$</tex> <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sum\left\Vert g_{t}\right\Vert^{2}$</tex>; (2) a parameter-free design requiring only <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\eta_{0}&gt;0$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\beta&gt;0$</tex>, eliminating the need for knowledge of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$V_{T}, G$</tex>, or shift counts; and (3) an automatic drift detection mechanism via <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\left\Vert g_{t}-g_{t-1}\right\Vert &gt;\gamma \sqrt{\log t /\left|I_{k}\right|}$</tex>, enabling adaptation to both gradual and abrupt concept shifts. Theoretical analysis demonstrates that CB-RML achieves dynamic regret bounded by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}\left(\sqrt{T\left(1+V_{T}\right)}\right)$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$V_{T}$</tex> quantifies environmental variation, while maintaining computational efficiency. Experimental results across synthetic and real-world benchmarks validate our theoretical claims, showing superior performance compared to state-of-the-art baselines in scenarios with unanticipated distribution shifts. The framework's combination of theoretical rigor and practical applicability advances the frontier of robust online learning in dynamic environments.