AFTD Auto-Formalizing Theoretical Domains

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.
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

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
See it in the graphDiscuss this resultChallenge it