AFTD Auto-Formalizing Theoretical Domains

log_potential_step

theoremverifiedimported Lean

One-step logarithmic potential bound for Hedge. Fix $N \ge 1$ experts and $T$ rounds, a learning rate $\eta > 0$, and a valid loss sequence $\ell$, so that $0 \le \ell_t(i) \le 1$ for every round $t$ and expert $i$. Writing $W_t = \sum_{i=1}^N \exp\!\bigl(-\eta L_t(i)\bigr)$ for the Hedge potential and $\widehat{\ell}_t = \sum_{i=1}^N p_t(i)\,\ell_t(i)$ for the expected loss under the Hedge distribution, the one-round change in log-potential is controlled by the expected loss: for each round $t$, \[ \ln W_{t+1} - \ln W_t \;\le\; -\bigl(1 - e^{-\eta}\bigr)\,\widehat{\ell}_t. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma log_potential_step {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)
      ≤ -(1 - Real.exp (-η)) * hedgeLoss η ℓ t
Source
TCSlib, `log_potential_step`
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 6
  • 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$.
  • 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 1
  • hedge_regret_boundRegret bound for the Hedge algorithm. Fix $N \ge 1$ experts and $T$ rounds, and let $\ell$ be a valid loss sequence, so that…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- One-step log-potential bound: for a valid loss sequence and `η > 0`, `ln W_{t+1} - ln W_t ≤ -(1 - exp(-η)) · (p_t · ℓ_t)` [CBL06, proof of Thm 2.2]. This is the additive form of `potential_ratio_le`, obtained from `ln x ≤ x - 1`; it is what telescopes over the rounds in `Hedge.Regret`. The hypothesis `ht` is only forwarded to `potential_ratio_le`, which does not use it. -/lemma log_potential_step {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)      ≤ -(1 - Real.exp (-η)) * hedgeLoss η ℓ t := by  -- Convert the multiplicative potential-ratio bound into an additive  -- log-potential bound.  This is what will telescope across time.  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)]  have hratio := potential_ratio_le η hη ℓ hℓ t ht  set c := (1 : ℝ) - Real.exp (-η)  -- The ratio is positive (from hratio and the fact W_{t+1}/W_t > 0)  have hratio_pos : 0 < potential η ℓ (t.val + 1) / potential η ℓ t.val :=    div_pos hWt1 hWt  have h1mc_pos : 0 < 1 - c * hedgeLoss η ℓ t := by linarith  -- log(ratio) ≤ log(1 - c * hedgeLoss) ≤ (1 - c * hedgeLoss) - 1 = -c * hedgeLoss  -- using log x ≤ x - 1 for x > 0.  calc Real.log (potential η ℓ (t.val + 1) / potential η ℓ t.val)      ≤ Real.log (1 - c * hedgeLoss η ℓ t) := by        exact Real.log_le_log hratio_pos hratio    _ ≤ (1 - c * hedgeLoss η ℓ t) - 1 := Real.log_le_sub_one_of_pos h1mc_pos    _ = -(1 - Real.exp (-η)) * hedgeLoss η ℓ t := by ring
See it in the graphDiscuss this resultChallenge it