Section 3.4, Eq. (5) — size of the lifted class: log |A_{M,ρ}| ≤ C M log(e/ρ)
ProvedCalibratedMA.Randomized.eq_5calibrationcountingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with an integer, , and let be an integer. The lifted test class of Section 3.4 satisfies the counting bound
and, for a universal constant ,
This bound makes the online learner's guarantee (Lemma 3.1) over cost only in the logarithm, which yields the term of Theorem 4.1.
Formalization Note. with a natural number, so and is written exp 1 / (1/K). is the cardinality of the Finset of distinct lifted functions. is quantified before and .
Differences from the source:
- encoding: with an integer → , , ; reason: same instances.
- encoding: as a class of functions on → a
Finset (ℝ → ℝ)of lifts extended to by clamping the score to ; reason: functions that agree on have the same extension, so the cardinality is unchanged.
Preamble
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Rounding
Formal statement
namespace CalibratedMA.Randomized
/-- Section 3.4, the counting bound and Eq. (5) (p. 17): with `ρ = 1/K`, `K_ρ = |Λ_ρ| = K + 1`,
`|A_{M,ρ}| ≤ Σ_{L=1}^M (K_ρ choose L+1) 2^{L+1} ≤ (M + 1)(2K_ρ)^{M+1}` and `log |A_{M,ρ}| ≤ C M log(e/ρ)` for a universal `C`. -/
theorem eq_5 :
∃ C : ℝ, 0 < C ∧ ∀ K M : ℕ, 1 ≤ K → 1 ≤ M →
(liftedClass K M).card ≤
∑ L ∈ Finset.Icc 1 M, Nat.choose (K + 1) (L + 1) * 2 ^ (L + 1) ∧
(∑ L ∈ Finset.Icc 1 M, Nat.choose (K + 1) (L + 1) * 2 ^ (L + 1)) ≤
(M + 1) * (2 * (K + 1)) ^ (M + 1) ∧
Real.log (liftedClass K M).card ≤ C * M * Real.log (Real.exp 1 / (1 / (K : ℝ))) := by sorry
end CalibratedMA.Randomized
Source
Jiuyao Lu, Georgy Noarov, Aaron Roth, Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity, STOC 2027 submission #900 (October 2026), p. 17, Section 3.4, counting display and Eq. (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.