AFTD Auto-Formalizing Theoretical Domains

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

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