Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

First stage of the adversary in Theorem 8.1: k − 1 forced mistakes and two consistent functions that disagree

Proved
WeightedMajority.Anomalies.first_stage

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

adversarymistake-boundmistake-treeonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let FFF be a class of {0,1}\{0,1\}{0,1}-valued functions on a domain XXX, and let k≥1k \ge 1k≥1. Suppose FFF has a complete kkk-mistake tree, i.e. a complete binary tree of depth kkk whose internal nodes are labelled by instances of XXX such that every root-to-leaf labelling (y1,…,yk)∈{0,1}k(y_1,\dots,y_k) \in \{0,1\}^k(y1​,…,yk​)∈{0,1}k is realized by some f∈Ff \in Ff∈F along the path it determines (FFF shatters the tree).

Then for every deterministic on-line prediction algorithm AAA there exist a sequence of k−1k-1k−1 trials (x1,y1),…,(xk−1,yk−1)(x_1,y_1),\dots,(x_{k-1},y_{k-1})(x1​,y1​),…,(xk−1​,yk−1​), an instance x∈Xx \in Xx∈X and two functions f1,f2∈Ff_1, f_2 \in Ff1​,f2​∈F such that

  1. AAA is wrong at every one of the k−1k-1k−1 trials: its prediction at trial ttt, made from (x1,y1),…,(xt−1,yt−1)(x_1,y_1),\dots,(x_{t-1},y_{t-1})(x1​,y1​),…,(xt−1​,yt−1​) and xtx_txt​, differs from yty_tyt​;
  2. f1f_1f1​ and f2f_2f2​ are both consistent with all k−1k-1k−1 trials: fi(xt)=ytf_i(x_t) = y_tfi​(xt​)=yt​ for every t≤k−1t \le k-1t≤k−1 and i=1,2i = 1, 2i=1,2;
f1(x)≠f2(x).f_1(x) \ne f_2(x).f1​(x)=f2​(x).

This is the first stage of the adversary in the lower bound opt(F,η)≥opt(F,0)+2η\mathrm{opt}(F,\eta) \ge \mathrm{opt}(F,0) + 2\etaopt(F,η)≥opt(F,0)+2η: after it, the adversary can repeat the instance xxx with labels that disagree with the algorithm, keeping one of f1,f2f_1, f_2f1​,f2​ within the anomaly budget.

Formalization Note A complete kkk-mistake tree is encoded by the published predicate ShattersTree F k v of UnderstandingML_Online, in which a node is the list of labels on the path leading to it. Trials are indexed by Fin (k - 1); since k≥1k \ge 1k≥1 the truncated subtraction is exact.

Preamble
import Mathlib
import Definitions.Def_UnderstandingML_Online
import Definitions.Def_WeightedMajority_Anomalies_Opt
Formal statement
namespace WeightedMajority.Anomalies

open UnderstandingML

/-- The first stage of the adversary in the proof of Theorem 8.1 (§8, p. 251). If `F` has a
complete `k`-mistake tree (an `F`-shattered tree of depth `k`), `k ≥ 1`, then against any
deterministic algorithm `A` there is a sequence of `k − 1` trials on which `A` is wrong at every
trial, together with an instance `x` and two functions `f₁, f₂ ∈ F`, both consistent with all
`k − 1` trials, such that `f₁ x ≠ f₂ x`. -/
theorem first_stage {X : Type*} (F : Set (X → Bool)) (A : OnlineAlg X Bool) (k : ℕ)
    (hk : 1 ≤ k) (htree : ∃ v : List Bool → X, ShattersTree F k v) :
    ∃ S : Fin (k - 1) → X × Bool,
      (∀ t : Fin (k - 1), A (history S t) (S t).1 ≠ (S t).2) ∧
      ∃ f₁ ∈ F, ∃ f₂ ∈ F, ∃ x : X,
        (∀ t : Fin (k - 1), f₁ (S t).1 = (S t).2) ∧
        (∀ t : Fin (k - 1), f₂ (S t).1 = (S t).2) ∧
        f₁ x ≠ f₂ x := by sorry

end WeightedMajority.Anomalies
Source
Littlestone, Warmuth, The Weighted Majority Algorithm, Inform. and Comput. 108 (1994), p. 251, Section 8, proof of Theorem 8.1 (end of the first stage)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me