§2.2, display (12) — the omitted-mass recursion
ProvedGaussMixGated.ExactReal.eq_12distribution-learninggaussian-mixturesmachine-learningp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilitystatistics
Let , , , and let , and be as in (7)–(8). Let be nonnegative reals with such that, for every with ,
Then for every ,
and in particular . In the paper is the latent mass outside the stage- cover, and the recursion is (6) with from (4) with . This display keeps the omitted mass small across all stages.
Differences from the source:
- generalization: b_j the omitted masses of the algorithm on the success events, C_cov the constant of Theorem 2.3 → any nonnegative sequence with b₀ ≤ β obeying the recursion at stages with b_j ≤ 1/2, any C_cov ≥ 1; reason: the display is an arithmetic consequence of these facts; it specializes to the source's b_j
- reading: 'This verifies the hypothesis b_j ≤ 1/2 at every stage' → b_j ≤ 1/2 stated as a third conclusion; reason: it is the purpose of the display
Preamble
import Mathlib import Definitions.Def_GaussMixGated_ExactReal_Schedule
Formal statement
namespace GaussMixGated.ExactReal
/-- §2.2, display (12) (Zheng–Xie–He, STOC 2027 #36, PDF pp. 7–8): the omitted-mass recursion
`b_{j+1} ≤ b_j + (1 − b_j){3β + C_cov(2b_j + β)}` (valid at stages with `b_j ≤ 1/2`), started from
`b₀ ≤ β`, gives `b_j ≤ 3 A*^j β ≤ ε²/1000` for `0 ≤ j ≤ J`; in particular `b_j ≤ 1/2`. -/
theorem eq_12 (d : ℕ) (hd : 1 ≤ d) (ε δ Ccov : ℝ) (hε : 0 < ε) (hε' : ε < 1 / 4)
(hδ : 0 < δ) (hδ' : δ < 1 / 4) (hC : 1 ≤ Ccov) (b : ℕ → ℝ) (hb : ∀ j, 0 ≤ b j)
(hb0 : b 0 ≤ betaSched d ε δ Ccov)
(hrec : ∀ j < Jsched d δ, b j ≤ 1 / 2 →
b (j + 1) ≤ b j + (1 - b j) *
(3 * betaSched d ε δ Ccov + Ccov * (2 * b j + betaSched d ε δ Ccov))) :
∀ j ≤ Jsched d δ,
b j ≤ 3 * Astar Ccov ^ j * betaSched d ε δ Ccov ∧
3 * Astar Ccov ^ j * betaSched d ε δ Ccov ≤ ε ^ 2 / 1000 ∧
b j ≤ 1 / 2 := by sorry
end GaussMixGated.ExactReal
Source
Zheng, Xie, He, Learning Finite Gaussian Location Mixtures via Gated Moments and Posterior Covers, STOC 2027 submission #36 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/36.pdf, PDF p. 8 (printed p. 6), §2.2, display (12); recursion on PDF p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.