AFTD Auto-Formalizing Theoretical Domains

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

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