Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.4 — Recovering hidden bits from a randomized predictor

Open
CalibratedMA.Randomized.Supplement.lemma_6_4

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

calibrationmultiaccuracyp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1sample-complexity

There are positive universal constants a,ca,ca,c, with a≤1/4a\le1/4a≤1/4. For every integer k≥2k\ge2k≥2, put xi=i/kx_i=i/kxi​=i/k, bi=1/4+xi/2b_i=1/4+x_i/2bi​=1/4+xi​/2 and Δ=a/k2\Delta=a/k^2Δ=a/k2. For θ∈{0,1}k\theta\in\{0,1\}^kθ∈{0,1}k, let DθD_\thetaDθ​ have uniform contexts xix_ixi​ and Bernoulli means bi+Δθib_i+\Delta\theta_ibi​+Δθi​. Let QQQ be any admissible randomized predictor. The public decoder defined by nearest-baseline bins and the integrals of (P−bi)(P-b_i)(P−bi​), with no labels or hidden bits as inputs, satisfies

CMADθ(Q;{x↦x})≤c/k2⟹dH(θ^,θ)≤k/5.\mathrm{CMA}_{D_\theta}(Q;\{x\mapsto x\})\le c/k^2 \quad\Longrightarrow\quad d_H(\widehat\theta,\theta)\le k/5.CMADθ​​(Q;{x↦x})≤c/k2⟹dH​(θ,θ)≤k/5.

The same decoder works for every hidden vector. This is the recovery statement used for the calibration component of Theorem 6.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: public points x_i=i/k and singleton identity test → a relabeled Fin k law and the actual test contextPoint i=(i.val+1)/k; reason: the labeled laws and published CMA are preserved by this bijection
  • encoding: there is a label-free decoder and positive universal a,c → the displayed public decoder bitDecoder and witnesses with a≤1/4; reason: the proof explicitly constructs this decoder and chooses a≤1/4; there is no hidden-vector input
Preamble
import Mathlib
import Definitions.Def_CalibratedMA_Randomized_Supplement_Hidden

open MeasureTheory
Formal statement
namespace CalibratedMA.Randomized.Supplement

/-- Lemma 6.4, p.34, using the public decoder displayed immediately below the statement. -/
theorem lemma_6_4 :
    ∃ a c : ℝ, 0 < a ∧ a ≤ 1 / 4 ∧ 0 < c ∧
      ∀ k : ℕ, ∀ hk : 2 ≤ k, ∀ (Q : Fin k → Measure ℝ),
        IsRandomizedPredictor Q → ∀ θ : Fin k → ℝ, (∀ i, IsBit (θ i)) →
        CMA (offsetData baseline (a / (k : ℝ) ^ 2) θ) Q {contextPoint} ≤ c / (k : ℝ) ^ 2 →
        (hamming (bitDecoder k (by omega) (a / (k : ℝ) ^ 2) Q) θ : ℝ) ≤ (k : ℝ) / 5 := 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. 34, Lemma 6.4 (PDF pp. 36)

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