cumLoss_succ
theoremverifiedimported Lean
Cumulative loss recurrence. Let $\ell$ be a loss sequence for $N$ experts over $T$ rounds, and write $L_t(i) = \sum_{s < t} \ell_s(i)$ for the cumulative loss of expert $i$ through the first $t$ rounds. Then for every round $t < T$ and every expert $i$, \[ L_{t+1}(i) \;=\; L_t(i) + \ell_t(i). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma cumLoss_succ {N T : ℕ} (ℓ : LossSeq N T) (t : Fin T) (i : Fin N) : cumLoss ℓ (t.val + 1) i = cumLoss ℓ t.val i + ℓ t i
- Source
- TCSlib, `cumLoss_succ`
- 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.cumLoss_succ← cumLoss_succ (TCSlib/LearningTheory/Hedge/Basic.lean:188): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Used by 1
- hedgeWeight_succRecursion for the Hedge weight. Fix a learning rate $\eta \in \bbr$ and a loss sequence $\ell$ for $N$ experts over $T$ rounds. For every…
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/-- The cumulative loss through `t + 1` rounds is the cumulative loss through `t` rounds plus the loss at round `t`: `L_{t+1}(i) = L_t(i) + ℓ_t(i)`. -/lemma cumLoss_succ {N T : ℕ} (ℓ : LossSeq N T) (t : Fin T) (i : Fin N) : cumLoss ℓ (t.val + 1) i = cumLoss ℓ t.val i + ℓ t i := by simp only [cumLoss] -- The prefix `{s | s < t+1}` is the old prefix `{s | s < t}` plus the -- current round `t`. have : (Finset.univ (α := Fin T)).filter (fun s => s.val < t.val + 1) = ((Finset.univ).filter (fun s => s.val < t.val)) ∪ {t} := by ext s simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_singleton] constructor · intro h; by_cases hs : s = t · exact Or.inr hs · left; omega · rintro (h | rfl) · omega · omega rw [this, Finset.sum_union] · simp · simp [Finset.disjoint_left] intro s hs omega