Halving.mistakes_bound
Mistake bound for the Halving Algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V$ be a finite version space of hypotheses, and fix a target hypothesis $\mathtt{target} \in V$ whose predictions supply the true label at each step. Then for every input sequence $xs$, the total number of mistakes made by the Halving Algorithm — which predicts by majority vote over the current version space and, after each input, retains only those hypotheses that agreed with the observed label — satisfies \[ \mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs) \;\le\; \lfloor \log_2 \abs{V} \rfloor. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in theorem Halving.mistakes_bound (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) (xs : List X) (htarget : target ∈ V) : mistakes eval target V xs ≤ Nat.log 2 V.card
- Source
- TCSlib, `Halving.mistakes_bound`
- Lean proof
- By Arhaan Aggarwal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Arhaan Aggarwal. 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.Halving.mistakes_bound← Halving.mistakes_bound (TCSlib/LearningTheory/MistakeBounds/Halving.lean:204): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- Halving.mistake_halvesMistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
- Halving.mistakes$\mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs)$ is the total number of prediction errors made by the Halving Algorithm when it…
- Halving.target_mem_updateTarget survives its own update. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let…
- Halving.log_succ_le_log_of_double_leLogarithm increment under doubling. For natural numbers $a$ and $b$ with $b > 0$ and $2b \le a$,…
- Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
- Halving.update_subsetThe updated version space is a subset. Fix an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a finite version…
- Halving.predictThe Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$…
- Used by 1
- Halving.halving_boundHalving mistake bound. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ assign a Boolean label to each input under each…
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 invariable {Hyp X : Type*} in/-- In the realizable setting, the Halving Algorithm makes at most `⌊log₂ |V|⌋` mistakes: if the target hypothesis lies in the finite version space `V`, then on any finite list of inputs `xs`, labelled by `target`, the number of mistakes is at most `Nat.log 2 V.card`. [MRT18, Thm 8.1]; origin [Lit88, §3]. Deviation: the bound is stated as `Nat.log 2 V.card` (the floor of `log₂ |V|`) over an explicit finite list of examples with an explicit realizable target `target ∈ V`; the source's `opt(H) ≤ log₂ |H|` is the same bound for the adversarial online model. **Proof sketch.** Induction on the list of inputs, generalizing the version space `V`. The empty list makes no mistakes. For an input `x` followed by `xs`, let `y` be the target's label on `x` and `V'` the version space updated on `(x, y)`. Step 1: the target survives the update (`target ∈ V'`), so the induction hypothesis applies to `V'` and bounds the mistakes on `xs` by `⌊log₂ |V'|⌋`. Step 2 (no mistake on `x`): `V' ⊆ V`, so `|V'| ≤ |V|` and, by monotonicity of `Nat.log`, `⌊log₂ |V'|⌋ ≤ ⌊log₂ |V|⌋`; the mistake count on `x :: xs` equals that on `xs`. Step 3 (mistake on `x`): by the halving lemma `2 · |V'| ≤ |V|`, and `V'` is nonempty because it contains the target, so `⌊log₂ |V'|⌋ + 1 ≤ ⌊log₂ |V|⌋`; the one mistake on `x` is paid by this unit of logarithmic budget. -/theorem Halving.mistakes_bound (eval : Hyp → X → Bool) (target : Hyp) (V : Finset Hyp) (xs : List X) (htarget : target ∈ V) : mistakes eval target V xs ≤ Nat.log 2 V.card := by induction xs generalizing V with | nil => simp [mistakes] | cons x xs ih => let y := eval target x let V' := update eval V x y -- Step 1: the target survives the update, so the induction hypothesis applies to `V'`. have htarget' : target ∈ V' := by simpa [V', y] using target_mem_update eval target V x htarget have ih' : mistakes eval target V' xs ≤ Nat.log 2 V'.card := ih V' htarget' by_cases hcorr : predict eval V x = y · -- No mistake: the version space can only shrink. -- Step 2: `V' ⊆ V`, hence `|V'| ≤ |V|` and the log bound is monotone. have hsubset : V' ⊆ V := by simpa [V', y] using update_subset eval V x y have hcard : V'.card ≤ V.card := Finset.card_le_card hsubset have hlog : Nat.log 2 V'.card ≤ Nat.log 2 V.card := Nat.log_mono_right hcard calc mistakes eval target V (x :: xs) = mistakes eval target V' xs := by simp [mistakes, y, V', hcorr] _ ≤ Nat.log 2 V'.card := ih' _ ≤ Nat.log 2 V.card := hlog · -- Mistake: apply the halving lemma and spend one unit of logarithmic budget. -- Step 3: `2·|V'| ≤ |V|` and `V'` is nonempty, so `⌊log₂ |V'|⌋ + 1 ≤ ⌊log₂ |V|⌋`. have hhalve : 2 * V'.card ≤ V.card := by simpa [V', y] using mistake_halves eval V x y hcorr have hpos : 0 < V'.card := by exact Finset.card_pos.mpr ⟨target, htarget'⟩ have hlogstep : Nat.log 2 V'.card + 1 ≤ Nat.log 2 V.card := log_succ_le_log_of_double_le hpos hhalve calc mistakes eval target V (x :: xs) = 1 + mistakes eval target V' xs := by simp [mistakes, y, V', hcorr] _ ≤ 1 + Nat.log 2 V'.card := Nat.add_le_add_left ih' 1 _ = Nat.log 2 V'.card + 1 := by omega _ ≤ Nat.log 2 V.card := hlogstep