Lemma 3.1 — online residual control for finite tests
ProvedCalibratedMA.Randomized.lemma_3_1Let and let be a finite nonempty class of tests , each continuous in its second argument. Run the online rule of Appendix D, which before round determines a rule from the preceding examples, observes , predicts and then observes . There is a universal constant such that for every sequence of examples in ,
The statement also records that takes values in and depends only on the examples of rounds before .
The bound is deterministic and holds against an adversarial sequence. In Theorem 4.1 it controls the empirical residuals of the sequential scores against the tests in and against the lifted class .
Formalization Note. The constant is quantified first, ∃ C > 0, before the input type, , and the sequence. Rounds are , and the tests are only constrained on .
Differences from the source:
- generalization: "There is an online algorithm" → the bound is stated for the specific rule of Appendix D (
onlineRule), with its online property and range as conclusions; reason: Appendix D proves the lemma for this rule and Algorithm 1 runs this rule; the existence statement follows by taking this rule. - encoding: → ; reason: equivalent for a finite set.
- encoding: rounds and tests on → rounds
Fin Nand testsX → ℝ → ℝwith hypotheses only on ; reason: Lean convention, same instances. - generalization: tests on X × [0,1] → tests extended to X × ℝ, with distinct extensions counted separately even if their restrictions agree; reason: the signed-potential bound applies to this larger family; choosing the clamped extension of each source test recovers its exact cardinality and full bound.
import Mathlib import Definitions.Def_CalibratedMA_Randomized_OnlineRule universe u
namespace CalibratedMA.Randomized
/-- Lemma 3.1 (p. 13), online residual control for finite tests, for the online rule of
Appendix D: the rule `s_t` depends only on the examples of rounds `< t`, takes values in
`[0,1]`, and for every sequence of examples in `X × [0,1]` every test `ϕ ∈ Φ` has
`|N⁻¹ Σ_t ϕ(X_t, S_t)(Y_t − S_t)| ≤ C √(log(2|Φ|)/N)`, `C` universal. -/
theorem lemma_3_1 :
∃ C : ℝ, 0 < C ∧
∀ (X : Type u) (N : ℕ) (Φ : Finset (X → ℝ → ℝ)), 1 ≤ N → Φ.Nonempty →
(∀ ϕ ∈ Φ, ∀ x, ContinuousOn (ϕ x) (Set.Icc (0 : ℝ) 1)) →
(∀ ϕ ∈ Φ, ∀ x, ∀ p ∈ Set.Icc (0 : ℝ) 1, ϕ x p ∈ Set.Icc (-1 : ℝ) 1) →
(∀ (z z' : Fin N → X × ℝ) (t : ℕ), (∀ s : Fin N, (s : ℕ) < t → z s = z' s) →
onlineRule N Φ z t = onlineRule N Φ z' t) ∧
(∀ (z : Fin N → X × ℝ) (t : ℕ) (x : X), onlineRule N Φ z t x ∈ Set.Icc (0 : ℝ) 1) ∧
∀ z : Fin N → X × ℝ, (∀ t, (z t).2 ∈ Set.Icc (0 : ℝ) 1) →
∀ ϕ ∈ Φ,
|(1 / (N : ℝ)) * ∑ t : Fin N,
ϕ (z t).1 (onlineScore N Φ z t) * ((z t).2 - onlineScore N Φ z t)| ≤
C * Real.sqrt (Real.log (2 * (Φ.card : ℝ)) / N) := by sorry
end CalibratedMA.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.