hedge_regret_bound_tight
theoremverifiedimported Lean
Tight Hedge regret bound. Fix $N \ge 1$ experts and a horizon of $T$ rounds, and run the Hedge algorithm with a learning rate $\eta > 0$. For every valid loss sequence $\ell$ — one whose losses satisfy $0 \le \ell_t(i) \le 1$ for all rounds $t$ and experts $i$ — the regret of Hedge is bounded by \[ R_T(\eta) \;\le\; \frac{\log N}{\eta} + \frac{\eta\,T}{8}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in theorem hedge_regret_bound_tight {N T : ℕ} [NeZero N] (η : ℝ) (hη_pos : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) : regret η ℓ ≤ Real.log N / η + η * T / 8
- Source
- TCSlib, `hedge_regret_bound_tight`
- Lean proof
- By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.hedge_regret_bound_tight← hedge_regret_bound_tight (TCSlib/LearningTheory/Hedge/Regret.lean:344): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- log_potential_step_tightTight per-step logarithmic potential bound for Hedge. Fix $N \ge 1$ experts and a learning rate $\eta > 0$, and let $\ell$ be a valid loss…
- LossSeq.ValidA loss sequence $\ell$ is valid if all individual losses are in $[0,1]$: $\forall t\,i,\; 0 \le \ell_t(i) \le 1$.
- hedgeLossThe expected loss of the learner at round $t$ under the Hedge distribution is…
- regretThe regret of the Hedge algorithm is the excess cumulative loss over the best expert in hindsight:…
- potentialThe potential (sum of unnormalized weights) at time $t$ is \[ W_t \;=\; \sum_{i=1}^{N} w_t(i). \] The potential telescopes to…
- regret_le_of_log_potential_stepRegret from a per-step log-potential bound. Let $N \ge 1$, let $\eta > 0$, let $\ell$ be a loss sequence for $N$ experts over $T$ rounds,…
- LossSeqA loss sequence $\ell$ for $N$ experts over $T$ rounds is a function $\ell : \mathrm{Fin}\,T \to \mathrm{Fin}\,N \to \mathbb{R}$,…
- Used by 1
- hedge_constructionHedge yields an approximate minimax pair. Let $G$ be a finite two-player zero-sum game with $M \ge 2$ row actions and $N \ge 1$ column…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- **Hedge regret bound** (tight constant): for any valid loss sequence with `N` experts, `T` rounds, and any learning rate `η > 0`, the regret of Hedge is at most `(ln N)/η + ηT/8` [CBL06, Thm 2.2]; [MRT18, §8.2.4]. Deviation: stated in the expert-loss (linear) setting rather than for a convex loss of a weighted-average prediction; the constant and the hypotheses otherwise match CBL exactly (the prediction-space form is `hedgePrediction_regret_bound_tight` in `Hedge.ConvexPrediction`). This is the theorem reused by the adaptive-episode layer: once an online interaction has generated a valid `LossSeq`, the bound applies directly. **Proof sketch.** The theorem instantiates the shared potential argument `regret_le_of_log_potential_step` with `c = η²/8`. Step 1: for each round, `log_potential_step_tight` (Hoeffding's lemma) gives `log W_{t+1} - log W_t ≤ -η · hedgeLoss_t + η²/8`; no `η ≤ 1` is needed. Step 2: apply `regret_le_of_log_potential_step`. Step 3: simplify the constant `(η²/8) · T / η = ηT/8`. -/theorem hedge_regret_bound_tight {N T : ℕ} [NeZero N] (η : ℝ) (hη_pos : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) : regret η ℓ ≤ Real.log N / η + η * T / 8 := by -- Step 1: tight per-step bound from Hoeffding's lemma (no `η ≤ 1` needed) have hstep : ∀ t : Fin T, Real.log (potential η ℓ (t.val + 1)) - Real.log (potential η ℓ t.val) ≤ -η * hedgeLoss η ℓ t + η ^ 2 / 8 := fun t => log_potential_step_tight η hη_pos ℓ hℓ t (by omega) -- Step 2: shared potential argument with c = η²/8 -- Step 3: constant algebra (η²/8)·T/η = ηT/8 calc regret η ℓ ≤ Real.log N / η + η ^ 2 / 8 * T / η := regret_le_of_log_potential_step η hη_pos ℓ (η ^ 2 / 8) hstep _ = Real.log N / η + η * T / 8 := by congr 1 rw [div_eq_iff (ne_of_gt hη_pos)] ring