PaperlayerView exact revision on arXiv

Source-linked AI summary

Coin Betting and Parameter-Free Online Learning

Francesco Orabona, Dávid Pál

arXiv:1602.04128v4cs.LG

TL;DR

Parameter-free online learning avoids tuning regret-optimal learning rates to unknown competitors, but existing methods lack a unified, intuitive construction. The paper reduces OLO and LEA to adversarial coin betting and instantiates the reduction with the Krichevsky-Trofimov estimator, obtaining simple algorithms with optimal worst-case guarantees and competitive empirical behavior.

  • Problem

    Existing optimal-regret algorithms for OLO and LEA require learning rates based on unknown competitor quantities, motivating parameter-free methods without oracle tuning.

  • Method

    The paper develops a potential-based reduction from betting on adversarial coin outcomes to OLO over Hilbert spaces and LEA, using the Krichevsky-Trofimov estimator.

  • Results

    The resulting algorithms achieve optimal worst-case regret and time-complexity guarantees, while the KT-based algorithm performs close to unknown optimal learning-rate tuning in experiments.

  • Takeaways & Limitations

    Coin betting provides a common structure for prior parameter-free algorithms and enables simple new algorithms for both OLO and LEA.

  • Takeaways & Limitations

    The framework’s possible improvement is left to future work on data-dependent bounds.

Abstract

from arXiv · show

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 \emph{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.

1 Introduction

The paper targets parameter-free OLO and LEA, where optimal regret traditionally requires learning rates tuned to unknown competitor properties. It proposes a unified coin-betting framework with simple algorithms achieving optimal worst-case regret and time complexity.

  • Problem setting: OLO chooses points from a convex decision set and seeks low regret against a fixed competitor.The regret compares cumulative algorithmic reward with the cumulative reward of u ∈ K.
  • Problem setting: LEA is OLO over the N-dimensional probability simplex, while Hilbert-space OLO uses bounded reward-vector norms.For Hilbert spaces, ||g_t|| ≤ 1; for LEA, g_t ∈ [0,1]^N.
  • Problem setting: OLO supports reductions for online convex optimization and batch or stochastic convex optimization, while LEA combines classifiers and underlies boosting.
  • Motivation: Optimal regret in existing methods generally requires learning rates depending on unknown quantities such as ||u|| or D(u||π).This dependence creates an oracle-tuning requirement for methods including OGD and Hedge.
  • Contribution: Existing LEA methods trade off regret or running time, whereas the paper presents a unified constructive alternative.Reported shortcomings include an extra O(log log T) regret factor or numerical optimization during each round.
  • Contribution: The proposed framework reduces parameter-free OLO and LEA to maximizing wealth from bets on adversarial coin outcomes.Instantiating the framework with the Krichevsky-Trofimov estimator yields algorithms with optimal worst-case regret and time-complexity guarantees.

2 Preliminaries

The preliminaries define the mathematical setting and introduce coin betting against adversarial outcomes. Bets are constrained by available wealth, and outcomes may be generalized from binary values to [−1,1].

  • Coin Betting: Coin betting models a gambler with initial endowment ε who repeatedly bets on adversarial coin outcomes g_t ∈ {−1,1}.Heads correspond to +1 and tails to −1, with no assumption on how outcomes are generated.
  • Coin Betting: The bet w_t encodes both the betting direction through its sign and the amount through its absolute value.The gambler cannot borrow additional money, and losses or winnings update wealth accordingly.
  • Related algorithms: Some prior parameter-free algorithms require solving a numerical problem at each step, with precision and iteration count not calculated in those papers.
  • Coin Betting: Writing bets as fractions β_t of current wealth imposes β_t ∈ [−1,1].The absolute value of β_t is the wealth fraction wagered, while its sign selects heads or tails.
  • Coin Betting: The framework generalizes coin outcomes from {−1,1} to any real value in [−1,1] without changing wealth and reward definitions.

3 Warm-Up: From Betting to One-Dimensional Online Linear Optimization

The warm-up reduction interprets one-dimensional OLO predictions as wealth-scaled coin bets. A betting algorithm’s wealth guarantee then yields an OLO regret bound through the reward-regret relationship.

  • Reduction framework: The reduction uses betting potentials as the main design choice for constructing online learning algorithms from coin-betting procedures.The same reasoning is later extended to Hilbert-space OLO and LEA.
  • One-dimensional construction: In one-dimensional OLO, the algorithm defines wealth as ε plus cumulative reward and restricts predictions to w_t = β_t Wealth_{t−1}.Here β_t ∈ [−1,1], matching the no-borrowing constraint in coin betting.
  • One-dimensional construction: A coin-betting algorithm can therefore reuse its bets as predictions for one-dimensional OLO on rewards g_t ∈ [−1,1].
  • Reward-regret relationship: A lower bound on reward converts into an upper bound on regret through the reward-regret relationship.The lemma applies to dual vector spaces and a proper convex lower-semicontinuous function with Fenchel conjugate F* .
  • Reward-regret relationship: If wealth is at least F(Σ_t g_t), then regret is bounded by F*(u) + ε for every competitor u.Faster wealth growth produces a smaller regret bound.
  • Adaptivity: Designing an algorithm adaptive to the competitor u is equivalent to designing betting wealth adaptive to the cumulative outcome Σ_t g_t.The framework reuses betting methods that guarantee optimal wealth.

4 Designing a Betting Algorithm: Coin Betting Potentials

The paper turns adversarial coin betting into a parameter-free design framework by selecting potentials that guarantee rapid wealth growth. The Krichevsky–Trofimov estimator yields adaptive Kelly betting and excellent potentials for constructing online-learning algorithms.

  • Adaptive Kelly betting: For adversarial coins, the optimal fixed betting fraction depends on the cumulative outcomes, while perfect future knowledge would achieve wealth ϵ2T.Pinsker’s inequality supplies a bound relating the adaptive strategy to the best fixed fraction.
  • Adaptive Kelly betting: Adaptive Kelly betting replaces the unknown coin bias with the KT estimator computed from previously observed outcomes.The resulting strategy is an online, slightly biased version of the oracle fixed-fraction bet.
  • Coin betting potentials: A coin betting potential is a sequence of functions whose properties ensure that betting preserves a lower bound on wealth for every admissible outcome sequence.The definition requires initialization, symmetry and growth properties, a one-step inequality, and an additional differentiability condition for Hilbert-space reductions.
  • Coin betting potentials: The potential-based betting strategy is derived by minimizing the worst-case value of the induction inequality with respect to the next outcome.This construction makes the potential the central design choice of the betting algorithm.
  • Coin betting potentials: The differentiability condition enables reduction from Hilbert-space betting to a one-dimensional problem by characterizing the worst-case reward direction.The same potential framework is used for both OLO and learning with expert advice.
  • Coin betting potentials: Potentials that approximate the best possible wealth can recover earlier parameter-free constructions while also motivating new potential examples.The framework identifies the exponential potential used in prior OLO and LEA algorithms as an excellent coin betting potential.

5 From Coin Betting to OLO over Hilbert Space

The paper extends one-dimensional coin betting to OLO over Hilbert spaces using excellent coin betting potentials. The resulting prediction strategy reduces the general proof to the one-dimensional case and provides a regret guarantee under bounded reward vectors.

  • Construction: The Hilbert-space construction uses a sequence of excellent coin betting potentials to define an OLO algorithm and prove its regret bound.Rewards are accumulated as inner products, while wealth is initialized as ϵ plus cumulative reward.
  • Construction: The Hilbert-space prediction combines the scalar betting strategy with a direction determined by the cumulative reward vectors.When the cumulative reward vector is zero, the algorithm predicts the zero vector.
  • Guarantee: The proof reduces the general Hilbert-space case to one dimension using the differentiability condition on excellent potentials, then follows the one-dimensional analysis.This is the key bridge from coin betting to parameter-free OLO in Hilbert spaces.
  • Guarantee: Theorem 3 guarantees the stated OLO regret bound for any reward-vector sequence with ∥gt∥≤1.The theorem assumes a sequence of excellent coin betting potentials and predictions defined by the construction.

6 From Coin Betting to Learning with Expert Advice

The paper constructs learning-with-expert-advice algorithms by instantiating copies of a one-dimensional coin-betting OLO algorithm. Predictions are normalized expert-specific quantities, and the resulting construction satisfies a regret bound.

  • Construction: The LEA algorithm is built from the one-dimensional coin-betting OLO algorithm by instantiating one copy for each expert.The construction uses a prior distribution π over the N experts.
  • Construction: Each round, expert-specific predictions are transformed into nonnegative quantities and normalized to form the algorithm’s probability vector.If the transformed vector has zero ℓ1 norm, the algorithm predicts the prior π.
  • Construction: The reward fed to expert i’s copy is its reward relative to the algorithm’s reward, clipped to a nonnegative value when that copy’s prediction is nonpositive.This produces transformed rewards in [−1,1] for the one-dimensional OLO instances.
  • Guarantee: Theorem 4 provides a regret bound for the experts algorithm constructed from the one-dimensional coin-betting OLO algorithm.The theorem is stated for an algorithm A based on a sequence of coin betting potentials.
  • Guarantee: The LEA proof uses a nonpositive prior-weighted transformed reward and a change-of-measure argument related to PAC-Bayes analyses.These ingredients connect the per-expert reductions to the final regret guarantee.

7 Applications of the Krichevsky-Trofimov Estimator to OLO and LEA

The KT estimator yields coin-betting potentials that produce parameter-free algorithms for OLO in Hilbert spaces and for LEA. These algorithms are simple and achieve optimal regret guarantees, with Algorithm 2 also matching the best known per-round complexity.

  • KT-based construction: The KT estimator supplies excellent coin-betting potentials whose wealth guarantees translate into optimal parameter-free regret bounds for OLO and LEA.The paper identifies KT potentials as the basis for both applications.
  • OLO in Hilbert Space: Algorithm 1 applies the KT potential to OLO over a Hilbert space with reward vectors satisfying ∥g_t∥≤1.Its regret guarantee follows as a corollary of the general coin-betting theorem.
  • OLO in Hilbert Space: Algorithm 1 has an optimal regret bound, and its initial endowment ϵ may be set to any constant such as 1.The endowment plays a role analogous to the initial guess in doubling tricks.
  • Learning with Expert Advice: Algorithm 2 uses a δ-shifted KT potential with δ=T/2 and requires the number of rounds T in advance.The known-horizon requirement can be removed using the standard doubling trick, at the cost of a larger leading constant.
  • Learning with Expert Advice: Algorithm 2 achieves the best known worst-case regret guarantee and per-round time complexity for learning with expert advice.The paper also emphasizes its simplicity.
  • Learning with Expert Advice: Shifting the KT potential improves the LEA regret from O(√(T(log T + D(u∥π)))) to a bound of O(√(T(1 + D(u∥π)))).Changing the fraction used in the shift trades off constants in the square-root bound.

8 Discussion of the Results

The paper interprets parameter-free online learning through coin betting and reports empirical performance close to oracle-tuned methods. It also identifies data-dependent regret bounds as the main remaining improvement target.

  • Interpretation: Coin betting reveals a common hidden structure behind parameter-free algorithms for both OLO and LEA.The paper presents this interpretation as more than a mathematical reformulation because it enables new algorithm design.
  • Theoretical results: Algorithms 1 and 2 achieve optimal worst-case regret upper bounds for their respective settings.The claim is made relative to established optimal bounds in the cited literature.
  • Empirical evaluation: In three regression datasets, parameter-free algorithms performed very close to OGD with its unknown optimal learning-rate tuning.The experiments solved OCO through OLO using absolute loss and normalized input vectors to have L2 norm 1.
  • Empirical evaluation: In the LEA experiment, parameter-free algorithms performed close to or better than Hedge with oracle learning-rate tuning, with no clear winner among them.The synthetic setting used Hadamard matrices and T=32768 samples.
  • Limitations: The remaining possible improvement is a data-dependent regret bound; extending the reductions to that case is left for future work.This limitation is motivated by the near-optimality of the adaptive Kelly strategy based on the KT estimator.

C Proof of Lemma 11

This appendix proves the Hilbert-space technical lemma used to transfer coin-betting potential properties into reward and regret guarantees. The proof relies on geometric inequalities for admissible potential functions.

  • Lemma 10: Lemma 10 establishes an extreme-point inequality for even functions satisfying x·h′′(x)≥h′(x) on a Hilbert space.The inequality compares an inner-product term with endpoint evaluations involving vector norms.
  • Proof strategy: The proof reduces the Hilbert-space inequality to concavity in the cosine α of the angle between two vectors.It defines α=⟨u,v⟩/(∥u∥·∥v∥) and verifies that the relevant second derivative is non-positive.
  • Lemma 11: Lemma 11 bounds the potential after an update using the betting fraction, reward-vector norm, and preceding potential value.The argument applies the extreme-point lemma and the defining properties of excellent coin-betting potentials.
  • Theorem 3: Theorem 3 follows by induction, with Lemma 11 supplying the key inequality and the base case given by the initial endowment ϵ.The resulting inequality immediately yields a reward lower bound.
  • Regret conversion: The final regret conversion applies Lemma 1 to F(x)=F_T(∥x∥)−ϵ and uses the radial form of the Fenchel conjugate.The conjugate identity is cited for even functions.

D Proof of Theorem 4

This appendix section proves the LEA reduction by verifying the required identities for transformed expert rewards and the associated probability vector. The proof then connects these quantities to the KL divergence term.

  • Reduction identities: The proof first establishes the required sum identity for the transformed rewards g_t,i.The equality follows directly from the definition of g_t,i.
  • Reduction identities: When ∥b_t∥_1>0, the positive parts of the transformed weights define p_t through b_t,i=∥b_t∥_1p_t,i.If all relevant terms are nonpositive, both sides are zero instead.
  • KL-divergence bound: The proof substitutes the exponential weighting relation and invokes the KL-divergence inequality from equation (18).The supplied proof passage identifies this as the step producing the D(u∥π) term.

E Properties of Krichevsky-Trofimov Potential

The KT potential is constructed from gamma functions and shown to have the analytic and recurrence properties required of an excellent coin-betting potential.

  • Analytic properties: Lemma 12 establishes that the gamma-function potential is defined on (−a, a), even, logarithmically convex, and increasing on [0, a).Its logarithmic convexity follows from the corresponding property of the gamma function.
  • Analytic properties: The logarithm of the potential is expanded in a Maclaurin series whose nonconstant coefficients are non-negative.This coefficient structure implies monotonicity on the nonnegative part of the domain.
  • KT potential: For every admissible x, the potential satisfies [F_t(x+1)−F_t(x−1)]/[F_t(x+1)+F_t(x−1)] = x/(t+δ).The identity is derived algebraically using Γ(1+z)=zΓ(z).
  • KT potential: The proof verifies the coin-betting inequality by checking g=+1 and g=−1, then extending to all g∈[−1,1] through logarithmic convexity.The endpoint evaluations yield 1+x/(t+δ) and 1−x/(t+δ), respectively.
  • Lower bounds: The paper develops lower bounds for the KT potential and its shifted version using gamma-function inequalities, digamma bounds, and divergence bounds.These technical lemmas support later regret analyses.

F.1 Proof of Corollary 5

The proof of Corollary 5 bounds the Lambert function and applies those bounds to the KT potential through Fenchel duality and the earlier shifted-potential lower bound.

  • Lambert-function bounds: Lemma 17 bounds the Lambert function for x≥0 as 0.6321 log(x+1)≤W(x)≤log(x+1).The lower bound is obtained through an auxiliary inequality, while the upper bound uses a published result.
  • Fenchel duality: The proof derives a Fenchel-dual representation by optimizing xy−f(x) at a point satisfying y=f′(x∗).The resulting expression involves the Lambert function.
  • Application to the KT potential: The KT potential is rewritten in a form suitable for applying the lower bound on the shifted potential with δ=0.The proof then combines this bound with Lemma 18.
  • Application to the KT potential: The proof concludes by applying Theorem 3 to complete Corollary 5.The final step follows after the potential and Lambert-function bounds have been established.
Loading 1602.04128v4…