# Improved Strongly Adaptive Online Learning using Coin Betting

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2016.

## Built on by (most cited first, 30 of 50)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Adaptive Fairness-Aware Online Meta-Learning for Changing Environments](https://mlsanity.com/paper/2205.11264/) (2022)
- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Adaptive Online Learning of Quantum States](https://mlsanity.com/paper/2206.00220/) (2022)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [Error-quantified Conformal Inference for Time Series](https://mlsanity.com/paper/2502.00818/) (2025)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Towards Fair Disentangled Online Learning for Changing Environments](https://mlsanity.com/paper/2306.01007/) (2023)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Adaptive Gradient Methods with Local Guarantees](https://mlsanity.com/paper/2203.01400/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Optimal Dynamic Regret in LQR Control](https://mlsanity.com/paper/2206.09257/) (2022)
- [On Accelerated Perceptrons and Beyond](https://mlsanity.com/paper/2210.09371/) (2022)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously](https://mlsanity.com/paper/2405.20824/) (2024)
- [Exploring the Noise Robustness of Online Conformal Prediction](https://mlsanity.com/paper/2501.18363/) (2025)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Improved Regret Bounds for Tracking Experts with Memory](https://mlsanity.com/paper/2106.13021/) (2021)

## Abstract (arXiv)

This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least √log(T) better, where T is the time horizon. Empirical results show that our algorithm outperforms state-of-the-art methods in learning with expert advice and metric learning scenarios.