mlsanityData to 7 Oct 2026

Coin Betting and Parameter-Free Online Learning

arXiv 1602.04128 ↗First posted 12 Feb 2016cs.LGcited by 131

Not on the map. Why?

Abstract (arXiv)

In the recent years, a number of parameter-free algorithms have been developed for online linear optimization over Hilbert spaces and for learning with expert advice. These algorithms achieve optimal regret bounds that depend on the unknown competitors, without having to tune the learning rates with oracle choices. We present a new intuitive framework to design parameter-free algorithms for both online linear optimization over Hilbert spaces and for learning with expert advice, based on reductions to betting on outcomes of adversarial coins. We instantiate it using a betting algorithm based on the Krichevsky-Trofimov estimator. The resulting algorithms are simple, with no parameters to be tuned, and they improve or match previous results in terms of regret guarantee and per-round complexity.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 18; 2023: 28; 2024: 22; 2025: 23; 2026: 24.

131 papers.

Sort:

By area:

  1. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  2. 2023Improved Online Conformal Prediction via Strongly Adaptive Online Learningcited by 76
  3. 2022Making SGD Parameter-Freecited by 50
  4. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 42
  5. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 41
  6. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  7. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  8. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  9. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  10. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  11. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  12. 2022Learning Predictions for Algorithms with Predictionscited by 25
38 more
  1. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  2. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  3. 2023Auditing Fairness by Bettingcited by 24
  4. 2024Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approachcited by 22
  5. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  6. 2023Mechanic: A Learning Rate Tunercited by 20
  7. 2023Normalized Gradients for Allcited by 18
  8. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  9. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  10. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  11. 2021Off-policy Confidence Sequencescited by 15
  12. 2021Learning-to-learn non-convex piecewise-Lipschitz functionscited by 15
  13. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  14. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  15. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  16. 2023Tighter PAC-Bayes Bounds Through Coin-Bettingcited by 13
  17. 2024Tuning-Free Stochastic Optimizationcited by 13
  18. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 13
  19. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  20. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  21. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  22. 2023Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Bettingcited by 11
  23. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  24. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  25. 2024Online Detection of LLM-Generated Texts via Sequential Hypothesis Testing by Bettingcited by 11
  26. 2025Error-quantified Conformal Inference for Time Seriescited by 11
  27. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  28. 2024Fully Unconstrained Online Learningcited by 10
  29. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
  30. 2022Optimal Comparator Adaptive Online Learning with Switching Costcited by 9
  31. 2023Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtrackingcited by 9
  32. 2024An Equivalence Between Static and Dynamic Regret Minimizationcited by 9
  33. 2021A unified framework for bandit multiple testingcited by 8
  34. 2021Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizerscited by 8
  35. 2022Implicit Parameter-free Online Learning with Truncated Linear Modelscited by 8
  36. 2022Towards Painless Policy Optimization for Constrained MDPscited by 8
  37. 2023Coin Sampling: Gradient-Based Bayesian Inference without Learning Ratescited by 8
  38. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8

50 most cited of 131 All 131 (JSON)