Lemma 7.3 — A small family of sign tests detects ℓ_1 error
OpenCalibratedMA.Randomized.Supplement.lemma_7_3calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
There are positive universal constants . For each integer and every real in the entire interval , there is a finite set of actual sign functions satisfying
and, simultaneously for every ,
No multiplicity is counted in . This finite testing result supports the prescribed group budget in Theorem 7.1.
Differences from the source:
- encoding: a finite discrete domain [R] → Fin R, with source coordinate i represented by i.val+1; reason: finite relabeling preserves every statistical experiment, test and error
- encoding: a maximum over the finite sign-test family → for every vector there exists a test attaining at least the bound; reason: equivalent to the maximum inequality on the finite nonempty family; cardinality counts distinct functions
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Lemma 7.3, p.38: one set of actual functions works for every real vector. -/
theorem lemma_7_3 :
∃ a A c C : ℝ, 0 < a ∧ 0 < A ∧ 0 < c ∧ 0 < C ∧
∀ N : ℕ, 2 ≤ N → ∀ Ktest : ℝ,
A * Real.log N ≤ Ktest → Ktest ≤ a * N →
∃ G : Finset (Fin N → ℝ),
(∀ g ∈ G, ∀ i, IsSign (g i)) ∧
Real.exp (c * Ktest) ≤ (G.card : ℝ) ∧
(G.card : ℝ) ≤ Real.exp (C * Ktest) ∧
∀ d : Fin N → ℝ, ∃ g ∈ G,
|∑ i : Fin N, g i * d i| ≥
c * Real.sqrt (Ktest / N) * ∑ i : Fin N, |d i| := by sorry
end CalibratedMA.Randomized.Supplement
Source
Jiuyao Lu, Georgy Noarov, Aaron Roth, Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity, STOC 2027 submission #900 (October 2026; title page November 2, 2026), p. 38, Lemma 7.3 (PDF pp. 40)