Lemma 6.2 — Sample cost of recovering hidden coordinates
OpenCalibratedMA.Randomized.Supplement.lemma_6_2calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity
There is a universal . Choose either alphabet or , an integer , an offset , and baselines . Assume every gives means . Let have uniform context marginal on and Bernoulli labels with these means. A single measurable estimator based on iid examples and an independent seed, with values in , satisfies
Here counts unequal coordinates; the estimator has no access to . This information bound supports both Theorems 6.1 and 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: either hidden alphabet and an independent seed estimator → a Boolean choice of alphabet and a single measurable data-and-seed estimator; reason: keeps both alphabets and makes the stated success probabilities ordinary probabilities
- encoding: uniform contexts and Bernoulli labels → the explicit finite mixture offsetData; reason: its means are constrained for every hidden vector exactly as in the source
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden open MeasureTheory open scoped ENNReal
Formal statement
namespace CalibratedMA.Randomized.Supplement
/-- Lemma 6.2, pp.32–33: the same estimator for every hidden vector, either alphabet. -/
theorem lemma_6_2 :
∃ c_info : ℝ, 0 < c_info ∧ ∀ (signed : Bool) (R : ℕ), 1 ≤ R →
∀ (η : ℝ), 0 < η → ∀ t : Fin R → ℝ,
(∀ i, t i ∈ Set.Icc (0 : ℝ) 1) →
(∀ θ : Fin R → ℝ, (∀ i, θ i ∈ Alphabet signed) →
∀ i, t i + η * θ i ∈ Set.Icc (1 / 8 : ℝ) (7 / 8)) →
∀ (n : ℕ) (seed : TrainingSeed)
(estimate : ((Fin n → Fin R × ℝ) × seed.Ω) → Fin R → ℝ),
Measurable estimate → (∀ z i, estimate z i ∈ Alphabet signed) →
(∀ θ : Fin R → ℝ, (∀ i, θ i ∈ Alphabet signed) →
ENNReal.ofReal (2 / 3 : ℝ) ≤ trainingLaw n (offsetData t η θ) seed
{z | (hamming (estimate z) θ : ℝ) ≤ (R : ℝ) / 5}) →
(n : ℝ) ≥ c_info * R / η ^ 2 := 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. 32-33, Lemma 6.2 (PDF pp. 34-35)