PaperlayerView exact revision on arXiv

Source-linked AI summary

Follow the Leader If You Can, Hedge If You Must

Steven de Rooij, Tim van Erven, Peter D. Grünwald, Wouter M. Koolen

arXiv:1301.0534v2cs.LGstat.ML

TL;DR

The paper addresses the gap between FTL’s strong performance on easy or stochastic data and hedging methods’ robust worst-case guarantees. It develops AdaHedge and combines it with FTL in FlipFlop. FlipFlop provably retains AdaHedge-like worst-case guarantees while achieving regret within a constant factor of FTL’s regret.

  • Problem

    FTL can perform poorly on worst-case data, while robust hedging strategies may perform much worse than FTL on easy data.

  • Method

    The paper develops AdaHedge, dynamically tunes its learning rate without the doubling trick, and alternates AdaHedge with FTL in FlipFlop.

  • Results

    FlipFlop retains AdaHedge’s worst-case guarantees up to a constant factor while its regret is bounded by a constant times FTL’s regret.

  • Takeaways & Limitations

    AdaHedge and FlipFlop provide loss-scale- and translation-invariant weights without requiring advance knowledge of the loss range.

  • Takeaways & Limitations

    The paper leaves extension to a full range of learning rates and arbitrary expert sets or prior distributions for future work.

Abstract

from arXiv · show

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.

1. Introduction

The paper seeks sequential prediction that performs well on both adversarial and easy data. It introduces AdaHedge and FlipFlop to retain robust worst-case guarantees while matching FTL more closely.

  • Motivation: Hedge achieves adversarial lower-bound regret but can retain high regret on easy data, unlike FTL.FTL can have bounded regret when the data are easy, while Hedge may continue to suffer regret of order sqrt(T).
  • Motivation: FTL puts weight on the currently best expert and performs well when leader changes are few, including suitable i.i.d. stochastic settings.In such i.i.d. cases, the leader is almost surely overtaken only finitely often when the best expert has the smallest mean loss.
  • Motivation: FTL can incur regret about T/2 on antagonistic alternating losses, motivating algorithms with stronger worst-case guarantees.The example uses two experts whose losses alternate in opposite patterns.
  • Contributions: AdaHedge refines CBMS by tuning its learning rate from past performance, improving the dominant bound by a factor of 2 and making weights invariant to loss translation and rescaling.Its analysis avoids the earlier doubling-trick presentation and yields fundamental regret bounds.
  • Contributions: FlipFlop alternates FTL and AdaHedge to guarantee regret within a constant factor of FTL while retaining AdaHedge-like worst-case behavior.The paper presents FlipFlop as the first algorithm to provably combine FTL’s performance on easy data with robust behavior on antagonistic data.
  • Analysis: The mixability gap is central to designing and analyzing the proposed algorithms and decomposing Hedge regret.FlipFlop’s analysis uses the smallest cumulative mixability gap encountered in either regime, with slightly increased constant factors.

2. AdaHedge

AdaHedge refines Hedge by tuning its learning rate online from the cumulative mixability gap rather than using a fixed rate or the doubling trick. It retains strong worst-case guarantees while adapting to easy data, including stochastic settings where its regret is bounded.

  • Properties: AdaHedge’s weights are invariant to scaling and translation of losses, although the analysis initially assumes losses lie in [0, 1].Unnormalised losses are handled by reduction to the normalised case.
  • Adaptive learning rate: AdaHedge uses Hedge with a learning rate tuned directly from the observable cumulative mixability gap.The tuning balances the cumulative mixability gap against ln(K)/η.
  • Adaptive learning rate: The learning rate decreases smoothly over time, achieving the balancing goal without restarting blocks through the doubling trick.This replaces an earlier block-based AdaHedge approach.
  • Easy data: When data are easy and one expert is clearly best, AdaHedge weights concentrate on that expert; under the stated stochastic separation condition, its regret is bounded.The condition is independent loss vectors with expected cumulative-loss gaps growing as Ω(t^β) for every β > 1/2.
  • Worst-case guarantees: AdaHedge improves the dominant term of the Cesa-Bianchi et al. (2007) regret bound by a factor of 2.The improvement follows from a refined mixability-gap bound that also simplifies tuning.
  • Guarantees: The resulting bound is described as the best known for a Hedge algorithm expressed in terms of the best expert’s loss rate.The bound is also small when the best expert has a very low or very high loss rate, supporting translation from bounded gains.

3. FlipFlop

FlipFlop alternates between optimistic FTL and AdaHedge to handle both easy and adversarial data. Its analysis yields simultaneous regret guarantees tied to FTL performance and AdaHedge’s worst-case bound.

  • Motivation: AdaHedge can exploit concentration on a single best expert, but early difficult trials may trigger a feedback loop that causes substantial regret.Reducing the learning rate makes weights more uniform, potentially increasing later mixability gaps and causing further reductions.
  • Construction: FlipFlop combines FTL’s high-learning-rate behavior with AdaHedge’s adaptive learning rate by alternating between dedicated flip and flop regimes.The flip regime follows the leader, while the flop regime uses the AdaHedge-determined learning rate; the process switches between epochs according to regime-specific conditions.
  • Guarantees: FTL regret is bounded by the number of leader changes, while FlipFlop competes with FTL’s actual regret rather than merely its bound.This makes FTL especially effective when one expert remains best and leader changes are rare.
  • Assumptions: The analysis assumes losses in [0, 1], while the paper discusses the general loss case separately.The displayed FlipFlop guarantees are stated under this bounded-loss assumption.
  • Analysis: FlipFlop separately accumulates mixability gaps, mix losses, and variances for its FTL-like and AdaHedge-like regimes.Its analysis bounds regret using the smallest cumulative mixability gap encountered in either regime, with increased constant factors.
  • Guarantees: FlipFlop’s main theorem gives simultaneous regret bounds, and the result is within a multiplicative factor of the better of FTL and AdaHedge’s bound.The authors note that FlipFlop may be better or worse than AdaHedge’s realized regret, while preserving its bound up to a constant factor.

4. Invariance to Rescaling and Translation

AdaHedge and FlipFlop retain fundamental regret behavior under arbitrary loss translations and positive rescaling, while their output weights remain unchanged.

  • Their regret bounds remain fundamental: translation leaves regret unchanged, while scaling losses by σ scales regret by σ.The bounds apply without requiring prior normalization or knowledge of the loss range.
  • AdaHedge and FlipFlop are invariant to translating and rescaling losses.For ℓ′_t,k = σℓ_t,k + τ_t with σ > 0, both algorithms issue the same sequence of weights as on the original losses.
  • The invariance proof establishes matching transformations for mixability gaps, learning rates, weights, and regret under loss rescaling.The induction uses η′_t = η_t/σ and preserves the relevant relations across rounds and FlipFlop regime changes.
  • AdaHedge refines the CBMS strategy while improving the dominant worst-case-bound term by a factor of 2.Its learning rate is tuned using a direct measure of past performance rather than the doubling trick.

5. Experiments

Four deterministic two-expert experiments show that the useful learning rate depends strongly on the data: small rates protect against FTL’s worst case, while large rates can excel on easy data.

  • Experimental setup: The experiments use deterministic artificial data with two experts and 1,000 rounds to isolate learning-rate effects.Each dataset begins with a hand-crafted loss vector followed by 999 loss vectors generated from slowly changing performance functions.
  • Experiment 1. Worst case for FTL: In the FTL worst case, FTL regret reaches about 500, whereas Hedge regret becomes negligible for η below about 0.01.The alternating losses make FTL incur loss one each round while each expert loses once every two rounds.
  • Experiment 1. Worst case for FTL: FlipFlop alternates between AdaHedge-like and FTL-like regret, keeping its costly FTL intervals short enough to remain within a constant-factor overhead.Hedge with η = 1 also performs poorly, while safe Hedge becomes competitive after reducing its learning rate.
  • Experiment 2. Best case for FTL: When FTL is favorable, its regret is only 1/2, and FlipFlop eventually remains in the FTL regime with bounded regret.The second dataset has no leader changes after the first round, so a large learning rate is advantageous.
  • Experiment 3. Weights do not concentrate in AdaHedge: In the third experiment, weights fail to concentrate quickly enough for intermediate or small learning rates, producing substantial overhead by t = 1000.FTL, Hedge with η = 1, FlipFlop, and NormalHedge perform excellently, while safe Hedge, AdaHedge, and Hazan and Kale’s algorithm perform poorly.
  • Experiment 4. Weights concentrate in AdaHedge: In the fourth experiment, AdaHedge achieves bounded regret because its weights concentrate quickly enough on the better expert.The larger performance gap makes identifying the better expert easier than in the third experiment.

6. Discussion and Conclusion

The paper develops AdaHedge and FlipFlop to combine strong worst-case regret with performance close to FTL on easy data. It also identifies broader open questions about competing with arbitrary learning rates and extending guarantees to richer expert classes.

  • Contributions: AdaHedge simplifies prior analyses, improves their bounds, and is fundamental because its weights are invariant to translating and scaling losses.It tunes the learning rate without the doubling trick.
  • Contributions: FlipFlop stays within a multiplicative constant of FTL while retaining a worst-case bound similar to AdaHedge.It interleaves FTL and AdaHedge to address the difficulty of tuning one learning rate for both easy and hard data.
  • Open question: Higher learning rates often outperform the rates selected by sophisticated Hedge variants in practical applications, motivating adaptation toward the best rate with hindsight.FlipFlop is presented as a first step toward this broader Universal Hedge goal.
  • Open question: For K = 2 experts with losses in {0, 1}, Theorem 18 establishes a fixed-learning-rate result whose first implication is not known to extend to more experts and other losses.The second implication does remain valid in those broader settings.
  • Future work: Future work aims to extend the worst-case approach to competing with ranges of learning rates, countably infinite experts, and arbitrary expert sets with priors.The proposed extensions would replace the finite-expert quantities L∗_T and ln K with comparator losses and prior-weight terms.

Appendix A. Proof of Lemma 1

The appendix derives basic Hedge identities and bounds using Jensen’s inequality, loss-range bounds, and the best expert’s prior weight. It also compares two learning rates through another Jensen inequality.

  • Proof of Lemma 1: Jensen’s inequality moves the logarithm inside the expectation to establish m_t ≤ h_t.The limiting case η = ∞ follows from finite η.
  • Proof of Lemma 1: Bounding losses by their minimum and maximum gives m_t ≥ 0 and h_t ≤ 1.
  • Proof of Lemma 1: The cumulative-loss bound follows by lower-bounding every expert’s loss by L∗_T and retaining the best expert’s term with w_1,k = 1/K.
  • Proof of Lemma 1: For learning rates 0 < η < γ, Jensen’s inequality supplies the comparison between the two rates.

Appendix B. Proof of Theorem 18

The proof shows that if FTL has unbounded regret for two experts, fixed-rate Hedge must also have unbounded regret. It removes neutral and local-extremum trials while preserving the relevant implication, then identifies linear regret on the reduced sequence.

  • Proof of Theorem 18: Unbounded FTL regret implies infinitely many leader changes after trials with equal expert losses are removed.A leader change occurs when the cumulative-loss difference crosses zero.
  • Proof of Theorem 18: Removing a local extremum decreases Hedge’s regret because Hedge loses more than 1 while the best expert loses 1 over the opposite-loss pair.Leader changes cannot themselves be local extrema.
  • Proof of Theorem 18: On the reduced sequence, Hedge regret is linear in t because the best expert’s loss rises by 2 per period while Hedge’s loss rises by a larger amount.
  • Proof of Theorem 18: Therefore, Hedge regret is unbounded on the original loss sequence whenever FTL regret is unbounded.
Loading 1301.0534v2…