potential_ratio_le
theoremverifiedimported Lean
Potential ratio bound for Hedge. Fix $N \ge 1$ experts, a horizon of $T$ rounds, a learning rate $\eta > 0$, and a valid loss sequence $\ell$. Then for every round $t$ with $t < T$, the consecutive potentials satisfy \[ \frac{W_{t+1}}{W_t} \;\le\; 1 - \bigl(1 - e^{-\eta}\bigr)\,\widehat{\ell}_t, \] where $\widehat{\ell}_t = \sum_{i=1}^{N} p_t(i)\,\ell_t(i)$ is the expected loss of the learner under the Hedge distribution at round $t$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma potential_ratio_le {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) (t : Fin T) (ht : t.val + 1 ≤ T) : potential η ℓ (t.val + 1) / potential η ℓ t.val ≤ 1 - (1 - Real.exp (-η)) * hedgeLoss η ℓ t
- Source
- TCSlib, `potential_ratio_le`
- 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.potential_ratio_le← potential_ratio_le (TCSlib/LearningTheory/Hedge/Basic.lean:251): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- hedgeWeightThe unnormalized Hedge weight of expert $i$ at time $t$ with learning rate $\eta$ is…
- hedgeDistThe Hedge distribution at round $t$ is the normalization of the weight vector: \[ p_t(i) \;=\; \frac{w_t(i)}{W_t}. \]
- hedgeWeight_succRecursion for the Hedge weight. Fix a learning rate $\eta \in \bbr$ and a loss sequence $\ell$ for $N$ experts over $T$ rounds. For every…
- 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…
- exp_neg_le_linearChord bound for the exponential on the unit interval. For every $\eta > 0$ and every $x \in [0,1]$, the value $e^{-\eta x}$ lies below the…
- hedgeWeight_posPositivity of Hedge weights. Fix a learning rate $\eta \in \bbr$, a loss sequence $\ell$ for $N$ experts over $T$ rounds, a time $t$, 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$.
- 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…
- 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 2
- 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…
- log_potential_stepOne-step logarithmic potential bound for Hedge. Fix $N \ge 1$ experts and $T$ rounds, a learning rate $\eta > 0$, and a valid loss…
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/-- One-step potential ratio bound: for a valid loss sequence and `η > 0`, `W_{t+1} / W_t ≤ 1 - (1 - exp(-η)) · (p_t · ℓ_t)`, where `p_t · ℓ_t` is Hedge's expected loss at round `t` [CBL06, proof of Thm 2.2]; [FS97, §2.1, Eq. (4) (proof of Lemma 1)]. Deviation: each term is bounded with the elementary chord inequality `exp_neg_le_linear` instead of Hoeffding's lemma, which is why the downstream weak bound has `ηT/2` rather than `ηT/8`. (An earlier docstring called this "CBL Lemma 2.2"; that lemma is Hoeffding's lemma, used only in the tight bound.) The hypothesis `ht` is not used. **Proof sketch.** Multiply through by `W_t > 0`. Step 1: by the multiplicative weight update, `W_{t+1} = ∑_i w_t(i) exp(-η ℓ_t(i))`. Step 2: bound each summand by `w_t(i) (1 - (1 - e^{-η}) ℓ_t(i))` using `exp_neg_le_linear` on `ℓ_t(i) ∈ [0,1]`. Step 3: sum the bounds and identify `∑_i w_t(i) (1 - c ℓ_t(i)) = (1 - c · hedgeLoss) · W_t` with `c = 1 - e^{-η}`, using `hedgeLoss = (∑_i w_t(i) ℓ_t(i)) / W_t`. -/lemma potential_ratio_le {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) (hℓ : ℓ.Valid) (t : Fin T) (ht : t.val + 1 ≤ T) : potential η ℓ (t.val + 1) / potential η ℓ t.val ≤ 1 - (1 - Real.exp (-η)) * hedgeLoss η ℓ t := by -- This is the core one-step Hedge estimate. The only use of validity is -- that every coordinate of the current loss vector lies in `[0, 1]`. -- W_{t+1} = ∑_i w_t(i) · exp(-η · ℓ_t(i)) -- W_{t+1}/W_t = ∑_i p_t(i) · exp(-η · ℓ_t(i)) -- ≤ ∑_i p_t(i) · (1 - (1-e^{-η}) · ℓ_t(i)) [by exp_neg_le_linear] -- = 1 - (1-e^{-η}) · ∑_i p_t(i) · ℓ_t(i) -- = 1 - (1-e^{-η}) · hedgeLoss have hWt := potential_pos η ℓ t.val -- Step 1: clear the denominator and rewrite `W_{t+1}` by the multiplicative weight update rw [div_le_iff₀ hWt] -- Goal: potential η ℓ (t+1) ≤ (1 - (1 - exp(-η)) * hedgeLoss η ℓ t) * potential η ℓ t -- W_{t+1} = ∑ w_t(i) * exp(-η * ℓ_t(i)) have hW_succ : potential η ℓ (t.val + 1) = ∑ i : Fin N, hedgeWeight η ℓ t.val i * Real.exp (-η * ℓ t i) := by simp only [potential]; congr 1; ext i; exact hedgeWeight_succ η ℓ t i rw [hW_succ] -- Step 2: bound each summand with `exp_neg_le_linear` have hbound : ∀ i : Fin N, hedgeWeight η ℓ t.val i * Real.exp (-η * ℓ t i) ≤ hedgeWeight η ℓ t.val i * (1 - (1 - Real.exp (-η)) * ℓ t i) := by intro i exact mul_le_mul_of_nonneg_left (exp_neg_le_linear hη (hℓ t i).1 (hℓ t i).2) (hedgeWeight_pos η ℓ t.val i).le -- Step 3: sum the bounds and show RHS = (1 - c * hedgeLoss) * W -- where c = 1 - exp(-η) and W = potential. -- RHS expanded: W - c * W * hedgeLoss = W - c * ∑(w_i * ℓ_i / W) * W = W - c * ∑ w_i * ℓ_i -- LHS ≤ ∑ w_i * (1 - c * ℓ_i) = ∑ w_i - c * ∑ w_i * ℓ_i = W - c * ∑ w_i * ℓ_i = RHS ✓ set c := (1 : ℝ) - Real.exp (-η) with hc_def set W := potential η ℓ t.val with hW_def -- Expand the RHS have hW_ne : W ≠ 0 := ne_of_gt hWt -- hedgeLoss = (∑ w_i * ℓ_i) / W have hHL : hedgeLoss η ℓ t = (∑ i : Fin N, hedgeWeight η ℓ t.val i * ℓ t i) / W := by simp only [hedgeLoss, hedgeDist, hW_def, Finset.sum_div] congr 1; ext i; ring -- Goal: ∑ w_i * exp(-η * ℓ_i) ≤ (1 - c * hedgeLoss) * W -- ≤ ∑ w_i * (1 - c * ℓ_i) (from hbound) -- = ∑ w_i - c * ∑ w_i * ℓ_i -- = W - c * hedgeLoss * W = (1 - c * hedgeLoss) * W ✓ have step1 := Finset.sum_le_sum fun i (_ : i ∈ Finset.univ) => hbound i suffices ∑ i, hedgeWeight η ℓ t.val i * (1 - c * ℓ t i) = (1 - c * hedgeLoss η ℓ t) * W by linarith rw [hHL, hW_def, potential] have hW_ne : (∑ i : Fin N, hedgeWeight η ℓ t.val i) ≠ 0 := ne_of_gt hWt have : ∀ i : Fin N, hedgeWeight η ℓ t.val i * (1 - c * ℓ t i) = hedgeWeight η ℓ t.val i - c * (hedgeWeight η ℓ t.val i * ℓ t i) := by intro i; ring simp_rw [this, Finset.sum_sub_distrib, ← Finset.mul_sum] field_simp