AFTD Auto-Formalizing Theoretical Domains

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.
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

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
See it in the graphDiscuss this resultChallenge it