Lemma 3.4 — population grid rounding rule (for the greedy partition of its proof)
ProvedCalibratedMA.Randomized.lemma_3_4Let be any distribution on , let with , and let with an integer and . Let be the greedy partition of with threshold on the grid , the construction in the proof of Lemma 3.4 that Algorithm 1 uses in step 4. Then the partition points of belong to , has at most intervals, and, for a universal constant ,
The point of the rate is that rounding to about values costs only in calibration, rather than the obtained by summing interval contributions separately. Theorem 4.1 applies this lemma to the empirical score distribution .
Formalization Note. with a natural number, so reads . The conclusion includes that the greedy output is a grid partition (IsGridPartition). is quantified before , and .
Differences from the source:
- generalization: "There is a partition " → the conclusion holds for the explicit greedy partition of the proof; reason: this is the partition Algorithm 1 uses, and the existence statement follows by taking it.
- encoding: with an integer → , , ; reason: same instances.
- encoding: a distribution on [0,1] → a probability measure on ℝ assigning zero mass to the complement of [0,1]; reason: extension by zero and restriction identify the same distributions.
import Mathlib import Definitions.Def_CalibratedMA_Randomized_Rounding import Definitions.Def_CalibratedMA_Randomized_Algorithm1 open MeasureTheory
namespace CalibratedMA.Randomized
/-- Lemma 3.4 (p. 16), population grid rounding rule, for the greedy partition constructed in
its proof: for every distribution `ν` on `[0,1]`, every `m ≥ 2` and every grid `Λ_ρ` with
`1/ρ = K` an integer and `ρ ≤ m^{-2}`, the greedy partition is a grid partition of `Λ_ρ` with at
most `4m + 2` intervals and `RoundErr(ν, Γ) ≤ C/m²`, for a universal constant `C`. -/
theorem lemma_3_4 :
∃ C : ℝ, 0 < C ∧
∀ (ν : Measure ℝ), IsProbabilityMeasure ν → ν (Set.Icc (0 : ℝ) 1)ᶜ = 0 →
∀ (m : ℝ) (K : ℕ), 2 ≤ m → 1 ≤ K → (1 : ℝ) / K ≤ (m ^ 2)⁻¹ →
IsGridPartition K (greedyPartition ν m K).1 (greedyPartition ν m K).2 ∧
((greedyPartition ν m K).1 : ℝ) ≤ 4 * m + 2 ∧
RoundErr ν (greedyPartition ν m K).1 (greedyPartition ν m K).2 ≤ C / m ^ 2 := by sorry
end CalibratedMA.Randomized
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.