log_potential_telescope
theoremverifiedimported Lean
Telescoping of the log potential. Let $\eta \in \bbr$ and let $\ell$ be a loss sequence for $N$ experts over $T$ rounds, with potential $W_t = potential\ \eta\ \ell\ t$. Then the one-step changes of the log potential telescope: \[ \sum_{t=0}^{T-1} \bigl(\log W_{t+1} - \log W_t\bigr) \;=\; \log W_T - \log W_0 . \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma log_potential_telescope {N T : ℕ} (η : ℝ) (ℓ : LossSeq N T) : ∑ t : Fin T, (Real.log (potential η ℓ (t.val + 1)) - Real.log (potential η ℓ t.val)) = Real.log (potential η ℓ T) - Real.log (potential η ℓ 0)
- Source
- TCSlib, `log_potential_telescope`
- 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.log_potential_telescope← log_potential_telescope (TCSlib/LearningTheory/Hedge/Regret.lean:62): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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/-- Telescoping the one-step changes of the log potential: summing `log W_{t+1} - log W_t` over the `T` rounds gives `log W_T - log W_0`. Pure bookkeeping (the sum over `Fin T` is rewritten as a sum over `range T` and `Finset.sum_range_sub` applies); no textbook counterpart. -/lemma log_potential_telescope {N T : ℕ} (η : ℝ) (ℓ : LossSeq N T) : ∑ t : Fin T, (Real.log (potential η ℓ (t.val + 1)) - Real.log (potential η ℓ t.val)) = Real.log (potential η ℓ T) - Real.log (potential η ℓ 0) := by set f := fun n => Real.log (potential η ℓ n) show ∑ t : Fin T, (f (t.val + 1) - f t.val) = f T - f 0 conv_lhs => arg 2; ext t; rw [show t.val = (t : ℕ) from rfl] rw [Fin.sum_univ_eq_sum_range (fun n => f (n + 1) - f n)] exact Finset.sum_range_sub f T