First stage of the adversary in Theorem 8.1: k − 1 forced mistakes and two consistent functions that disagree
ProvedWeightedMajority.Anomalies.first_stageLet be a class of -valued functions on a domain , and let . Suppose has a complete -mistake tree, i.e. a complete binary tree of depth whose internal nodes are labelled by instances of such that every root-to-leaf labelling is realized by some along the path it determines ( shatters the tree).
Then for every deterministic on-line prediction algorithm there exist a sequence of trials , an instance and two functions such that
- is wrong at every one of the trials: its prediction at trial , made from and , differs from ;
- and are both consistent with all trials: for every and ;
This is the first stage of the adversary in the lower bound : after it, the adversary can repeat the instance with labels that disagree with the algorithm, keeping one of within the anomaly budget.
Formalization Note A complete -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 the truncated subtraction is exact.
import Mathlib import Definitions.Def_UnderstandingML_Online import Definitions.Def_WeightedMajority_Anomalies_Opt
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.