mlsanityData to 7 Oct 2026

Improved Strongly Adaptive Online Learning using Coin Betting

arXiv 1610.04578 ↗First posted 14 Oct 2016stat.ML cs.LGcited by 48

Not on the map. Why?

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.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 13; 2023: 9; 2024: 7; 2025: 5; 2026: 8.

48 papers.

Sort:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2023Improved Online Conformal Prediction via Strongly Adaptive Online Learningcited by 76
  3. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  4. 2022Parameter-free Mirror Descentcited by 45
  5. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  6. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  7. 2023Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agentscited by 25
  8. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  9. 2022Adaptive Fairness-Aware Online Meta-Learning for Changing Environmentscited by 17
  10. 2023Adapting to Continuous Covariate Shift via Online Density Ratio Estimationcited by 15
  11. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  12. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
36 more
  1. 2022Projection-free Adaptive Regret with Membership Oraclescited by 13
  2. 2023Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guaranteescited by 13
  3. 2022Adaptive Online Learning of Quantum Statescited by 12
  4. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  5. 2021Online Caching with Optimal Switching Regretcited by 11
  6. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  7. 2023Towards Fair Disentangled Online Learning for Changing Environmentscited by 11
  8. 2025Error-quantified Conformal Inference for Time Seriescited by 11
  9. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  10. 2022Adaptive Gradient Methods with Local Guaranteescited by 8
  11. 2022Smoothed Online Convex Optimization Based on Discounted-Normal-Predictorcited by 6
  12. 2022Optimal Dynamic Regret in LQR Controlcited by 6
  13. 2022On Accelerated Perceptrons and Beyondcited by 6
  14. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  15. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  16. 2024Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneouslycited by 4
  17. 2025Exploring the Noise Robustness of Online Conformal Predictioncited by 4
  18. 2021Delay-Tolerant Constrained OCO with Application to Network Resource Allocationcited by 2
  19. 2021Improved Regret Bounds for Tracking Experts with Memorycited by 2
  20. 2022On the Computational Efficiency of Adaptive and Dynamic Regret Minimizationcited by 2
  21. 2024Dynamic Environment Responsive Online Meta-Learning with Fairness Awarenesscited by 2
  22. 2025Discounted Online Convex Optimization: Uniform Regret Across a Continuous Intervalcited by 2
  23. 2022Adversarial Bandits against Arbitrary Strategiescited by 1
  24. 2024Adaptive Regret for Bandits Made Possible: Two Queries Sufficecited by 1
  25. 2025Adaptive Estimation and Learning under Temporal Distribution Shiftcited by 1
  26. 2025Online conformal inference with retrospective adjustment for faster adaptation to distribution shiftcited by 1
  27. 2026Adaptive Bayesian Online Learning via Expert Aggregationcited by 1
  28. 2026Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constantcited by 1
  29. 2022Modifying Squint for Prediction with Expert Advice in a Changing Environmentcited by 0
  30. 2024Score-based change point detection via tracking the best of infinitely many expertscited by 0
  31. 2026Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Pointscited by 0
  32. 2026Locally Adaptive Multi-Objective Learningcited by 0
  33. 2026Parameter-Free and Group Conditional Online Conformal Predictioncited by 0
  34. 2026Blackwell Approachability and Gradient Equilibrium are Equivalentcited by 0
  35. 2026Parameter-Free Dynamic Regret under Heavy-Tailed Noisecited by 0
  36. 2026On the Relation Between Interval Regret and Dynamic Regretcited by 0