log_potential_step_tight
theoremverifiedimported Lean
Tight 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 sequence over $T$ rounds, so that every individual loss satisfies $0 \le \ell_t(i) \le 1$. Write $W_t = \sum_{i=1}^{N} \exp(-\eta L_t(i))$ for the Hedge potential after $t$ rounds, and $\widehat{\ell}_t$ for the expected loss of the learner at round $t$ under the Hedge distribution. Then for every round $t$ (with $0 \le t < T$), \[ \log W_{t+1} - \log W_t \;\le\; -\eta\,\widehat{\ell}_t + \frac{\eta^2}{8}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma log_potential_step_tight {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) (t : Fin T) (ht : t.val + 1 ≤ T) : Real.log (potential η ℓ (t.val + 1)) - Real.log (potential η ℓ t.val) ≤ -η * hedgeLoss η ℓ t + η ^ 2 / 8
- Source
- TCSlib, `log_potential_step_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.log_potential_step_tight← log_potential_step_tight (TCSlib/LearningTheory/Hedge/Regret.lean:300): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- potential_ratio_lePotential ratio bound for Hedge. Fix $N \ge 1$ experts, a horizon of $T$ rounds, a learning rate $\eta > 0$, and a valid loss sequence…
- potential_posPositivity of the Hedge potential. Fix a learning rate $\eta \in \bbr$, a loss sequence $\ell$ for $N \ge 1$ experts over $T$ rounds, and…
- 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$.
- hedgeLoss_le_oneHedge's expected loss is at most one. Fix a learning rate $\eta \in \bbr$, and let $\ell$ be a valid loss sequence for $N \ge 1$ experts…
- hedgeLoss_nonnegNonnegativity of Hedge's expected loss. Let $\ell$ be a valid loss sequence for $N \ge 1$ experts over $T$ rounds, fix any learning rate…
- hedgeLossThe expected loss of the learner at round $t$ under the Hedge distribution is…
- potentialThe potential (sum of unnormalized weights) at time $t$ is \[ W_t \;=\; \sum_{i=1}^{N} w_t(i). \] The potential telescopes to…
- hoeffding_lemmaHoeffding's lemma. Let $p \in [0,1]$ and let $h \in \bbr$ be arbitrary. Then…
- 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_regret_bound_tightTight 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$.…
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/-- Tight one-step log-potential bound: for a valid loss sequence and `η > 0`, `ln W_{t+1} - ln W_t ≤ -η · hedgeLoss_t + η²/8` [CBL06, proof of Thm 2.2]. The hypothesis `ht` is only forwarded to `potential_ratio_le`, which does not use it. **Proof sketch.** Write `μ = hedgeLoss_t ∈ [0,1]`. Step 1: by `potential_ratio_le`, `W_{t+1}/W_t ≤ 1 - (1 - e^{-η}) μ = (1 - μ) + μ e^{-η}`. Step 2: take logarithms (the ratio is positive). Step 3: Hoeffding's lemma `hoeffding_lemma` with `p = μ`, `h = -η` bounds `ln((1 - μ) + μ e^{-η}) ≤ -ημ + η²/8`. -/lemma log_potential_step_tight {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) (t : Fin T) (ht : t.val + 1 ≤ T) : Real.log (potential η ℓ (t.val + 1)) - Real.log (potential η ℓ t.val) ≤ -η * hedgeLoss η ℓ t + η ^ 2 / 8 := by -- Here `μ = hedgeLoss` lies in `[0,1]`. The one-step potential ratio is -- bounded by `(1-μ) + μ exp(-η)`, and Hoeffding converts the logarithm of -- that expression into `-η μ + η^2/8`. have hWt := potential_pos η ℓ t.val have hWt1 := potential_pos η ℓ (t.val + 1) rw [← Real.log_div (ne_of_gt hWt1) (ne_of_gt hWt)] -- Step 1: W_{t+1}/W_t ≤ (1-μ) + μ·e^{-η} where μ = hedgeLoss have hratio := potential_ratio_le η hη ℓ hℓ t ht set μ := hedgeLoss η ℓ t have hμ0 := hedgeLoss_nonneg η ℓ hℓ t have hμ1 := hedgeLoss_le_one η ℓ hℓ t have hratio_pos : 0 < potential η ℓ (t.val + 1) / potential η ℓ t.val := div_pos hWt1 hWt -- The ratio is ≤ (1-μ) + μ·e^{-η} have hcomp : 1 - (1 - Real.exp (-η)) * μ = (1 - μ) + μ * Real.exp (-η) := by ring -- Step 2: log monotonicity; Step 3: Hoeffding with p = μ, h = -η calc Real.log (potential η ℓ (t.val + 1) / potential η ℓ t.val) ≤ Real.log ((1 - μ) + μ * Real.exp (-η)) := by apply Real.log_le_log hratio_pos linarith [hcomp] _ ≤ μ * (-η) + (-η) ^ 2 / 8 := hoeffding_lemma hμ0 hμ1 _ = -η * μ + η ^ 2 / 8 := by ring