AFTD Auto-Formalizing Theoretical Domains

Halving.halving_bound

theoremverifiedformalizationimported Lean

Halving mistake bound. Let $\mathtt{eval} : \mathit{Hyp} \to X \to \mathsf{Bool}$ assign a Boolean label to each input under each hypothesis, let $H$ be a finite class of hypotheses, and fix a target hypothesis $\mathtt{target} \in H$ that supplies the correct label $\mathtt{eval}(\mathtt{target}, x)$ for every input $x$. Then, on any finite sequence $xs$ of inputs, the number of mistakes made by the Halving Algorithm run from the initial version space $H$ is at most $\lfloor \log_2 \abs{H} \rfloor$: \[ \mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, H, xs) \;\le\; \lfloor \log_2 \abs{H} \rfloor. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
theorem Halving.halving_bound
    (eval : Hyp → X → Bool) (target : Hyp) (H : Finset Hyp) (xs : List X)
    (htarget : target ∈ H) :
    mistakes eval target H xs ≤ Nat.log 2 H.card
Formalizes
Halving mistake bound, as formalized in TCSlib (`Halving.halving_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.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • Halving.mistakes$\mathtt{mistakes}(\mathtt{eval}, \mathtt{target}, V, xs)$ is the total number of prediction errors made by the Halving Algorithm when it…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {Hyp X : Type*} in
/-- The Halving mistake bound from the initial finite hypothesis class `H`: in the realizable setting (`target ∈ H`), the Halving Algorithm makes at most `⌊log₂ |H|⌋` mistakes on any finite list of inputs labelled by `target`. This is `mistakes_bound` with `V := H`. [MRT18, Thm 8.1]; origin [Lit88, §3]. Deviation: `Nat.log 2 H.card` (floor of `log₂ |H|`) over an explicit finite example list with an explicit realizable target, versus the source's `opt(H) ≤ log₂ |H|` for the adversarial online model. -/
theorem Halving.halving_bound
    (eval : Hyp → X → Bool) (target : Hyp) (H : Finset Hyp) (xs : List X)
    (htarget : target ∈ H) :
    mistakes eval target H xs ≤ Nat.log 2 H.card :=
  mistakes_bound eval target H xs htarget
See it in the graphDiscuss this resultChallenge it