Halving.mistake_halves
theoremverifiedimported Lean
Mistake bound for the Halving algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V \subseteq \mathit{Hyp}$ be a finite version space, let $x \in X$ be an input, and let $y \in \mathsf{Bool}$ be its true label. If the Halving prediction on $x$ is wrong, that is $\mathtt{predict}(\mathtt{eval}, V, x) \ne y$, then the updated version space contains at most half of the hypotheses: \[ 2 \cdot \abs{\mathtt{update}(\mathtt{eval}, V, x, y)} \le \abs{V}. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {Hyp X : Type*} in lemma Halving.mistake_halves (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) (hmistake : predict eval V x ≠ y) : 2 * (update eval V x y).card ≤ V.card
- Source
- TCSlib, `Halving.mistake_halves`
- 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.mistake_halves← Halving.mistake_halves (TCSlib/LearningTheory/MistakeBounds/Halving.lean:127): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- Halving.voteFor_false_add_trueVote counts partition the version space. Let $\mathrm{eval}$ be a Boolean evaluation map assigning to each hypothesis and each input a…
- Halving.updateAfter observing that the correct label for input $x$ is $y$, the version space is updated to…
- Halving.predictThe Halving Algorithm predicts on input $x$ by taking a majority vote of the current version space $V$: it returns $\mathsf{true}$…
- Halving.voteForGiven an evaluation map $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$, a version space $V \subseteq \mathit{Hyp}$, an input…
- Used by 1
- Halving.mistakes_boundMistake bound for the Halving Algorithm. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ be an evaluation map, let $V$ be a…
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/-- Every mistake at least halves the version space: if the Halving prediction on `x` differs from the observed label `y`, then the version space updated on `(x, y)` has at most half as many hypotheses as `V`, i.e. `2 · |update eval V x y| ≤ |V|`. [MRT18, proof of Thm 8.1]. **Proof sketch.** Case on the label `y`. If the prediction was wrong, the majority (ties included) voted for the other label, so the voters for `y` are at most the voters against `y`. Since the two vote sets partition `V` (`voteFor_false_add_true`), the survivors number at most half of `V`. -/lemma Halving.mistake_halves (eval : Hyp → X → Bool) (V : Finset Hyp) (x : X) (y : Bool) (hmistake : predict eval V x ≠ y) : 2 * (update eval V x y).card ≤ V.card := by cases y · -- true label is false/0, so a mistake means the algorithm predicted true/1. unfold predict at hmistake by_cases hmaj : (voteFor eval V x true).card ≥ (voteFor eval V x false).card · have hsum := voteFor_false_add_true (eval := eval) (V := V) (x := x) simp [update, hmaj] at hmistake ⊢ omega · simp [hmaj] at hmistake · -- true label is true/1, so a mistake means the algorithm predicted false/0. unfold predict at hmistake by_cases hmaj : (voteFor eval V x true).card ≥ (voteFor eval V x false).card · simp [hmaj] at hmistake · have hsum := voteFor_false_add_true (eval := eval) (V := V) (x := x) have hle : (voteFor eval V x true).card ≤ (voteFor eval V x false).card := by omega simp [update, hmaj] at hmistake ⊢ omega