Lemma A.2 — fixed-frame perturbation (corrected: nonnegative tolerance)
ProvedGaussMixGated.ExactReal.Supplement.lemma_A_2distribution-learningfinite-bit-computationgaussian-mixturesp2o-batch-stoc27sp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an integer, real and . Let range over any finite set of terms, and let term have factors, real coefficient and factor values . Assume , and . For , both bounds hold:
The term set may be empty and zero-factor products equal one. Factors may repeat and satisfy no independence condition. This estimate supplies the fixed-frame perturbation control in the precision budget for Theorem A.1.
Differences from the source:
- correction: the printed condition |xhat-x| ≤ h ≤ 1 permits negative h when every product is empty → the tolerance also satisfies 0 ≤ h; reason: with one empty product, coefficient 1, N=t=2 and h=-1 every printed assumption holds but the error conclusion is 0 ≤ -256; the added condition corrects exactly this empty-factor defect
- encoding: a finite sum of products with at most t factors per term → a finite index type and dependent factor types Fin (r l), allowing empty products and repeated values; reason: this represents all finite expressions with the same coefficient and factor bounds
Preamble
import Mathlib
Formal statement
namespace GaussMixGated.ExactReal.Supplement
/-- Lemma A.2, PDF p. 34 (printed p. 32). The tolerance is nonnegative.
Correction at empty products: with N=t=2, h=-1 and one constant term c=1, all printed
factor conditions are vacuous but the printed error bound reads 0 ≤ -256. -/
theorem lemma_A_2 {ι : Type*} [Fintype ι] (N : ℝ) (t : ℕ) (h : ℝ)
(r : ι → ℕ) (c : ι → ℝ) (x xhat : (l : ι) → Fin (r l) → ℝ)
(hN2 : 2 ≤ N) (hNt : (t : ℝ) ≤ N) (ht : 2 ≤ t)
(hr : ∀ l, r l ≤ t) (hc : ∑ l, |c l| ≤ N ^ (2 * t))
(hh0 : 0 ≤ h) (hh1 : h ≤ 1)
(hx : ∀ l j, |x l j| ≤ N) (hxh : ∀ l j, |xhat l j - x l j| ≤ h) :
|∑ l, c l * ∏ j, x l j| ≤ N ^ (3 * t) ∧
|(∑ l, c l * ∏ j, xhat l j) - (∑ l, c l * ∏ j, x l j)| ≤
N ^ (4 * t) * h := by sorry
end GaussMixGated.ExactReal.Supplement
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, Lemma A.2, PDF p. 34 (printed p. 32)