potential_ge_best_expert
theoremverifiedimported Lean
Potential lower bound via the best expert. Fix $N \ge 1$ experts and $T$ rounds, a loss sequence $\ell$, and a learning rate $\eta > 0$. Then the final potential is at least the unnormalized Hedge weight of the best expert in hindsight: \[ W_T \;\ge\; \exp\!\bigl(-\eta \, L^*\bigr), \] where $L^* = \min_{i} L_T(i)$ is the smallest cumulative loss over the full horizon $T$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma potential_ge_best_expert {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) : potential η ℓ T ≥ Real.exp (-η * bestExpertLoss ℓ)
- Source
- TCSlib, `potential_ge_best_expert`
- 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_ge_best_expert← potential_ge_best_expert (TCSlib/LearningTheory/Hedge/Basic.lean:365): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- cumLossThe cumulative loss of expert $i$ through the first $t$ rounds is \[ L_t(i) \;=\; \sum_{s < t} \ell_s(i), \] where the sum ranges…
- potentialThe potential (sum of unnormalized weights) at time $t$ is \[ W_t \;=\; \sum_{i=1}^{N} w_t(i). \] The potential telescopes to…
- bestExpertLossThe best expert loss in hindsight is the minimum cumulative loss achieved by any single expert:…
- 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
- 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,…
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/-- Lower bound on the final potential by the best expert: `W_T ≥ exp(-η · min_i L_T(i))`, since the sum of the final weights is at least the single largest weight [CBL06, proof of Thm 2.2]; [FS97, §2.1, proof of Thm 2]. The hypothesis `hη` is not used. -/lemma potential_ge_best_expert {N T : ℕ} [NeZero N] (η : ℝ) (hη : 0 < η) (ℓ : LossSeq N T) : potential η ℓ T ≥ Real.exp (-η * bestExpertLoss ℓ) := by -- The sum of all final weights is at least the single final weight of the -- best expert. This is the lower-bound half of the potential method. simp only [bestExpertLoss, potential, ge_iff_le, hedgeWeight] -- ⨅ is achieved at some i₀ (Fin N is finite nonempty). obtain ⟨i₀, hi₀⟩ := Finite.exists_min (cumLoss ℓ T) -- hi₀ : ∀ j, cumLoss ℓ T i₀ ≤ cumLoss ℓ T j -- So cumLoss i₀ = ⨅ cumLoss. have hinf : ⨅ i, cumLoss ℓ T i = cumLoss ℓ T i₀ := le_antisymm (ciInf_le ⟨_, by rintro _ ⟨j, rfl⟩; exact hi₀ j⟩ i₀) (le_ciInf hi₀) rw [hinf] -- Goal: exp(-η * cumLoss i₀) ≤ ∑ exp(-η * cumLoss i) exact Finset.single_le_sum (f := fun i => Real.exp (-η * cumLoss ℓ T i)) (fun i _ => (exp_pos _).le) (Finset.mem_univ i₀)