# Follow the Leader If You Can, Hedge If You Must

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2013.

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

- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Off-policy Confidence Sequences](https://mlsanity.com/paper/2102.09540/) (2021)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Conformal online model aggregation](https://mlsanity.com/paper/2403.15527/) (2024)
- [Adaptive Prediction-Powered AutoEval with Reliability and Efficiency Guarantees](https://mlsanity.com/paper/2505.18659/) (2025)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Adaptive Oracle-Efficient Online Learning](https://mlsanity.com/paper/2210.09385/) (2022)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Online Learning to Transport via the Minimal Selection Principle](https://mlsanity.com/paper/2202.04732/) (2022)
- [Conformal Distributed Remote Inference in Sensor Networks Under Reliability and Communication Constraints](https://mlsanity.com/paper/2409.07902/) (2024)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Valid Selection among Conformal Sets](https://mlsanity.com/paper/2506.20173/) (2025)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Isotuning With Applications To Scale-Free Online Learning](https://mlsanity.com/paper/2112.14586/) (2021)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)

## Abstract (arXiv)

Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has terrible performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We introduce the FlipFlop algorithm, which is the first method that provably combines the best of both worlds. As part of our construction, we develop AdaHedge, which is a new way of dynamically tuning the learning rate in Hedge without using the doubling trick. AdaHedge refines a method by Cesa-Bianchi, Mansour and Stoltz (2007), yielding slightly improved worst-case guarantees. By interleaving AdaHedge and FTL, the FlipFlop algorithm achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge's worst-case guarantees. AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains.