AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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
  • 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/-- 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
See it in the graphDiscuss this resultChallenge it