Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

1.1 Background and Overview

• SQ algorithms access distributions only through approximate expectations, a broad model encompassing spectral, moment, tensor, and local-search methods; SQ-dimension bounds yield unconditional runtime lower bounds.For the problems studied, known algorithms with non-trivial guarantees are SQ or easily implementable as SQ algorithms.Source: §1.1 · pp. 2–3

1.2 Our Results

• The unified moment-matching technique proves SQ lower bounds for robust spectral covariance and sparse mean estimation that match known quadratic statistical–computational tradeoffs.These lower bounds are computational rather than sample-complexity lower bounds: near-optimal-sample SQ algorithms exist but may require exponential running time.Source: §1.1 · pp. 2–3, §1.2 · p. 7
• For robustly testing an unknown Gaussian mean, the technique gives an information-theoretic sample lower bound linear in dimension, separating robust from non-robust testing.The testing lower bounds apply to all algorithms and match the sample complexity of the corresponding robust learning problem.Source: §1.1 · p. 2, §1.2 · p. 7

1.1 Background and Overview

• The introduction frames open questions about whether efficient algorithms can achieve information-theoretically optimal learning for GMMs and robust Gaussian estimation, and whether robustness creates statistical–computational gaps.Without robustness, optimal sample bounds can be efficiently achievable, whereas robust sparse mean and covariance estimation exhibit quadratic gaps for known algorithms.Source: §1.1 · pp. 3–5

1.2 Our Results

• Any SQ algorithm learning an arbitrary n-dimensional k-GMM to constant accuracy requires n^Ω(k) queries, despite Θ(k · log n) samples sufficing for nearly non-overlapping hard instances.The hard GMM components can have pairwise total variation distance 1 − 1/poly(n, k), so the lower bound persists even when components are almost non-overlapping.Source: §1.2 · p. 7
• Robustly learning N(µ, I) within total variation O(ǫ log(1/ǫ)^(1/2−c)) requires n^Ω(log(1/ǫ)^(c/2)) SQ queries at the stated precision.This lower bound applies for ǫ > 0, 0 < c ≤ 1/2, and n ≥ poly(log(1/ǫ)).Source: §1.2 · p. 7
• Robustly learning an unknown-mean Gaussian has a super-polynomial SQ complexity gap: O(n/ǫ2) samples suffice information-theoretically, but accuracy O(ǫ) requires quasi-polynomial SQ time.Theorem 1.2 gives a lower bound of nΩ(log1/4(1/ǫ)) running time, while [DKK+16] achieves O(ǫ log(1/ǫ)) error and is best possible among polynomial-time SQ algorithms.Source: §1.2 · pp. 7–8
• Theorem 1.3 qualitatively matches this lower bound: an SQ and sampling algorithm achieves O(ǫ) error with Oǫ(nO(√log(1/ǫ))) complexity.The SQ algorithm uses inverse quasi-polynomial precision, and the sampling implementation has the same error guarantee and comparable sample complexity and running time.Source: §1.2 · p. 8
• These robust-learning bounds apply to the agnostic model but not Huber contamination, where [DKK+17b] gives poly(n/ǫ) time and O(ǫ) error for unknown mean, separating the corruption models.The agnostic model permits both removing good samples and adding corrupted ones, whereas Huber contamination only adds corrupted samples.Source: §1.2 · p. 8
• For robust zero-mean covariance learning, Theorem 1.4 requires 2nΩ(1) queries, establishing a super-polynomial SQ gap and making [DKK+16]’s O(ǫ log(1/ǫ)) guarantee best possible for polynomial-time SQ algorithms.The lower bound concerns spectral error O(ǫ log(1/ǫ)1−c) under I/2 ⪯Σ⪯2I, while O(n/ǫ2) samples suffice information-theoretically.Source: §1.2 · p. 8
• Robust covariance estimation and robust sparse-mean estimation exhibit nearly quadratic SQ statistical–computational tradeoffs, including 2Ω(nc/3) queries for covariance and nΩ(ckc) for k-sparse means.The corresponding query precisions imply sample costs Ω(n2−5c) and Ω(k2−3c), respectively.Source: §1.2 · p. 9
• Robust Gaussian mean testing requires Ω(n) samples when δ=ǫ/100 and Ω(n1−c) samples when δ=ǫ/nc/4, versus Oǫ(√n) without robustness.Thus robust testing is information-theoretically harder and has essentially the same sample complexity as robust learning, O(n/ǫ2).Source: §1.2 · p. 9
• Testing whether a spherical GMM is ǫ-far from N(0,I) requires Ω(n/ǫ2) samples, matching the optimal sample complexity for learning the underlying distribution.The test distinguishes N(0,I) from an equal-weight mixture of two unit-covariance Gaussians with total variation distance at least ǫ.Source: §1.2 · p. 9

1.3 Our Approach and Techniques

• The generic lower-bound construction embeds a moment-matched one-dimensional distribution along an unknown direction and uses exponentially many nearly orthogonal directions to force many imprecise SQ queries.Moment matching suppresses low-degree tensor information; Ornstein–Uhlenbeck smoothing and Hermite analysis show nearly orthogonal instances are nearly uncorrelated, while the same instances yield testing lower bounds.Source: §1.3 · pp. 10, 11, 13
• The approach combines robust filtering with moment matching: filtering aligns higher moments, after which a one-dimensional lemma uses k = Θ(log^1/2(1/ǫ)) moments to imply O(ǫ) variation-distance closeness.The remaining mean estimation is restricted to a low-dimensional exceptional subspace, where brute-force computation is feasible.Source: §1.3 · pp. 13–14

1.4 Related Work

• Unlike prior SQ lower bounds for planted-like problems [FGR+13, FPV15, KV16] and discrete mixture learning [FOS08], this construction targets continuous Gaussian problems through different techniques.The paper also contrasts its super-polynomial SQ gaps with sparse-problem tradeoffs that become tractable after a quadratic sample increase [BR13a, BR13b, MW15, WBS16a].Source: §1.4 · p. 14

1.5 Discussion and Future Directions

• The paper’s main contribution is the first essentially tight SQ lower bounds for continuous high-dimensional distribution learning, explaining observed super-polynomial gaps between sample complexity and algorithmic runtime.The results include learning Gaussian mixtures and robustly learning a single Gaussian.Source: §1.5 · p. 14
• The lower-bound technique does not directly extend to spherical Gaussian mixtures because its n^Ω(k) bound exploits covariance structure, motivating broader-distribution extensions as open problems.Faster spherical-mixture algorithms are known [SOAJ14], though they have exponential dependence on the number of components.Source: §1.5 · pp. 14–15

1.6 Organization

• Sections 3–6 establish SQ lower bounds, Section 7 proves testing sample lower bounds, and Section 8 presents an optimal-accuracy robust Gaussian-learning algorithm matching the Section 5 SQ lower bound qualitatively.Sections 4 and 5 address Gaussian mixtures and robust Gaussian learning, while Section 6 gives quadratic tradeoffs for robust covariance and sparse mean estimation.Source: §1.6 · p. 15

2.1 Notation and Basic Definitions

• The paper studies n-dimensional Gaussians, finite k-Gaussian mixtures, total variation distance, and standard Euclidean, spectral, and Frobenius norms.A k-GMM is a weighted mixture of k Gaussian components; the standard one-dimensional Gaussian is denoted G(x).Source: §2.1 · p. 15

2.2 Formal Problem Definitions

• The formal problems include GMM density estimation and proper learning, componentwise parameter estimation, robust Gaussian learning, robust unknown-mean testing, and spherical-GMM testing.Robust Gaussian learning is specialized to unknown mean with identity covariance or unknown covariance with zero mean; the latter lower bound also applies under spectral-norm approximation.Source: §2.2 · p. 16

2.3 Basics on Statistical Query Algorithms over Distributions

• SQ algorithms access distributions through STAT(τ) or VSTAT(t) rather than samples, and these polynomially equivalent oracles may return adversarial values within tolerance.The framework treats general distributional search problems and defines valid solutions for each unknown distribution.Source: §2.3 · pp. 16–17
• Statistical Query dimension measures how many candidate distributions remain pairwise low-correlated relative to a reference distribution after excluding those compatible with any fixed solution.The paper lower-bounds this dimension and applies the resulting lemma from [FGR+13], which yields SQ query lower bounds as a function of the dimension and correlation parameters.Source: §2.3 · p. 17

3 Statistical Query Lower Bounds: From One–Dimension to High–Dimensions

• The high-dimensional family P_v places A along an unknown unit direction v and a standard Gaussian on its orthogonal complement, while sphere packings supply 2^Ω(n^c) separated directions.This common construction applies the same one-dimensional distribution A to all considered lower bounds and uses a packing with pairwise inner products at most O(n^(c−1/2)).Source: §3 · pp. 17–18, §3.2 · p. 21

3.2 Proof of Proposition 3.3

• Any SQ learner for hidden-direction distributions requires at least 2^Ω(n^(c/2)) ≥ n^(m+1) queries under the stated separation and dimension conditions.The construction uses a one-dimensional A matching the first m Gaussian moments with finite χ2 divergence, and assumes dTV(P_v,P_v′) > 2ε for nearly orthogonal directions.Source: §3 · p. 18, §3.2 · p. 21

3.1 Main Correlation Lemma

• The correlation lemma reduces high-dimensional correlations to one-dimensional projections and exploits Hermite eigenfunctions, whose degree-i components are scaled by cos^i(θ).Matching the first m moments makes the Hermite coefficients through degree m vanish, enabling correlation bounds for hidden directions.Source: §3.1 · pp. 18–20

• Any SQ learner for a k-mixture of n-dimensional Gaussians under the stated separation and dimensional conditions needs at least 2^Ω(n^1/8) ≥ n^2k STAT calls to achieve dTV(P,Q) ≤ 1/2.The theorem assumes n ≥ Ω(k^8 log(1/ε)^3) and pairwise component distance dTV(P_i,P_j) ≥ 1−ε.Source: §4 · pp. 21–22
• The lower bound is obtained by applying the Section 3 framework to a k-Gaussian mixture A that matches N(0,1) on the first 2k−1 moments and has χ2(A,N(0,1)) ≤ exp(O(k)) log(1/ε).The same construction yields high-dimensional distributions P_v that remain separated for vectors with |v·v′| ≤ 1/2.Source: §4 · p. 22
• Under n = Ω(k^8 log(1/ε)^3), the lower bound requires STAT precision O(n)^−k/6 or VSTAT tolerance O(n)^k/3.This follows from the resulting query lower bound and the relation nk/2 ≥ (exp(O(k)) log(1/ε))^3.Source: §4 · p. 22
• The construction uses Gaussian quadrature to create a k-point distribution matching the first 2k−1 moments, then adds positive Gaussian variance δ so the result is a k-Gaussian mixture with finite χ2 divergence.For any 0 < δ < 1, the component means have magnitude O(√k), while each component has variance δ.Source: §4 · p. 23
• Choosing δ = C/(k^2 log^2(k + 1/ε)) simultaneously ensures moment matching, pairwise component separation, bounded χ2 divergence, and high-dimensional separation.The resulting high-dimensional components satisfy dTV(P_v,P_v′) ≥ 1−O(...) for |v·v′| ≤ 1/2, as required by the theorem’s construction.Source: §4 · pp. 24–26

5.1 Robust Learning Lower Bound for Unknown Mean Gaussian

• For unknown mean spherical Gaussians, achieving total variation error O(ǫ log(1/ǫ)1/2/M2) requires at least 2Ω(n1/12) ≥ nM STAT calls.The result assumes n ≥ log(1/ǫ)Ω(1), M = O(log1/2(1/ǫ)), and an input distribution within ǫ total variation of N(µ, I).Source: §5.1 · pp. 26–27
• The unknown-mean lower bound is obtained from a one-dimensional distribution matching the first m Gaussian moments, remaining close in total variation to a shifted Gaussian, and having χ2-divergence O(δ).The construction uses a polynomial correction represented with scaled Legendre polynomials, whose coefficient bounds control the correction’s L1 and L∞ norms.Source: §5.1 · pp. 26–27

5.2 Robust Learning Lower Bound for Unknown Covariance Gaussian

• For unknown covariance Gaussians, spectral-norm error O(ǫ log(1/ǫ)/M4) requires at least 2n2/15 ≥ nM STAT calls.This holds for inputs within ǫ total variation of N(0, Σ), where I/2 ⪯ Σ ⪯ 2I, assuming n ≥ Ω(log2(1/ǫ)) and M = O(log1/4(1/ǫ)).Source: §5.2 · pp. 31–32
• The covariance lower bound uses a moment-matching univariate perturbation and a packing whose associated covariance-search problem has at most one valid solution.The perturbation matches the first m moments, is O(δm4/ log(1/δ)) in total variation from N(0, (1 −δ)2), and has χ2-divergence O(1 + m8δ3/2/log(1/δ)5/2).Source: §5.2 · pp. 31–32
• A is shown to be nonnegative everywhere, so it defines a distribution while matching the first m moments of N(0,1).For |x| > C positivity is immediate; for |x| ≤ C, the perturbation is bounded by a quantity smaller than δ^1/2 < G(x/(1−δ))/(1−δ).Source: §5.2 · p. 33
• The proof next bounds dTV(A, N(0,1−δ)) by controlling the L1 distance between A and G(x/(1−δ))/(1−δ).This identifies the variance-shifted Gaussian N(0,1−δ) as the comparison distribution for the total-variation calculation.Source: §5.2 · p. 33
• The χ2 bound decomposes into the divergence between N(0,1−δ) and N(0,1), plus the χ2 contribution of A−N(0,1−δ), with the Gaussian term equal to O(1+δ).The argument uses χ2(A,N(0,1)) ≤ O(χ2(N(0,1−δ),N(0,1)) + χ2(A−N(0,1−δ),N(0,1))).Source: §5.2 · p. 33

6.1 Robust Estimation of Covariance Matrix in Spectral Norm

• Ω(n2−c) samples are required by computationally efficient SQ algorithms to estimate a corrupted n-dimensional Gaussian covariance within a factor of 2, even under Huber contamination.The information-theoretic optimum is Θ(n) samples, yielding a nearly-quadratic efficient–inefficient SQ gap.Source: §6.1 · p. 34
• 2Ω(nc/3) STAT calls are required for factor-2 covariance approximation under contamination level ǫ ≤ c/ln(n), even when the noise is a mixture of 2 Gaussians.The formal theorem assumes 0 < c < 1/6, n > 125, and covariance operator norm at most poly(n/ǫ).Source: §6.1 · p. 34

6.2 Robust Sparse Mean Estimation

• Ω(k2−c) samples are required by computationally efficient SQ algorithms to robustly estimate a k-sparse mean of a corrupted N(µ, I), versus an information-theoretic optimum of Θ(k log n).The lower bound applies under the weaker Huber contamination model and establishes a nearly-quadratic gap between efficient and inefficient SQ algorithms.Source: §6.2 · p. 35
• Ω(nckc/8) queries to STAT or VSTAT are required to estimate a k-sparse mean within ǫ/2 when δ = ǫ/kc/4 and n ≥ 8k2.The theorem assumes sufficiently large k and n, a k-sparse µ with ∥µ∥2 = ǫ, and gives the query tolerances STAT(O(k)3c/2−1) or VSTAT(O(k)2−3c).Source: §6.2 · pp. 35, 38

General testing lower bound

• Proposition 7.1 rules out distinguishing N(0, I) from random-direction alternatives P_v with fewer than n/(8χ2(A, N(0, 1))) samples and success probability at least 2/3.The result assumes A has mean 0 and finite χ2(A, N(0, 1)).Source: §7 · p. 38

Limitations and extensions

• Matching more than one moment does not improve the previous lower bound when χ2(A, N(0, 1)) ≤1, while the technique suggests stronger bounds when χ2(A, N(0, 1)) > 1.For general m, the suggested requirement is N = Ω(n/(χ2(A, N(0, 1)))2/m) samples, but details are omitted for the paper’s main regime.Source: §7 · p. 40

Robust Gaussian mean testing

• Robustly testing an unknown mean Gaussian requires Ω(n) samples for δ = ǫ/100 and Ω(n1−c) samples for δ = ǫ/nc/4.These bounds apply when distinguishing N(0, I) from contaminated shifted Gaussians with ∥µ∥2 ≥ǫ, with success probability at least 2/3.Source: §7 · p. 41

Testing GMMs

• Testing whether a distribution is N(0, I) or a separated equal-weight mixture of two identity-covariance Gaussians requires fewer than Ω(n/ǫ2) samples to be impossible.The alternative must satisfy dTV(P, N(0, I)) ≥ǫ, and the claimed success probability is at least 2/3.Source: §7 · pp. 41–42

8.1 One-Dimensional Moment Matching Lemma

• Moment matching uses k = 2⌈ǫ ln(1/ǫ)/δ⌉ and shows that matching moments through degree k forces total variation distance dTV(G,G′) = O(δ).For every t ≤ k, the tth moments agree within (t − 1)!(δ/ǫ)^t ǫ/t.Source: §8.1 · p. 42

8.2 Robust Testing Algorithm

• The SQ testing algorithm distinguishes N(0, I) from distributions δ-far in total variation, using O(nk) queries with k = 2⌈O(ǫ ln(1/ǫ)/δ)⌉.It applies when δ is at least a sufficiently large constant multiple of ǫ and runs in time nO(k).Source: §8.2 · p. 45
• The testing result yields a sample-access algorithm that succeeds with probability 9/10 using at most (n log(1/ǫ))O(k)/ǫ2 samples.The same corollary applies when δ is at least a sufficiently large constant multiple of ǫ.Source: §8.2 · p. 45

Robust Testing Algorithm:

• Testing truncates samples to a bounded-radius ball and checks all mixed moments through degree k, preserving the standard Gaussian moments closely enough for soundness and completeness.The truncation changes degree-at-most-k moments only slightly, while a mean shift of norm at least δ creates a detectable projected moment discrepancy.Source: Robust Testing Algorithm · pp. 46–48

8.3 Robust Learning Algorithm

• The robust learning algorithm estimates the mean of an ǫ-noisy N(µ, I), achieving ||µ − µ̃||2 ≤ O(ǫ) when ||µ||2 ≤ poly(n, ǫ).Its sample-access version succeeds with probability 9/10 and preserves the O(ǫ) mean error guarantee.Source: §8.3 · p. 48
• The robust learning algorithm from [DKK+16] can be implemented with Statistical Queries by replacing expectations over surviving samples with conditional expectations after previous filters.It uses Filter-Gaussian-Unknown-Mean from [DKK+16] as preprocessing and then estimates Hermite-polynomial moments through SQ queries.Source: §8.3 · pp. 48, 50

8.3.1 Proof of Proposition 8.12

• The filtering loop takes O(n^2k) iterations, and all filters together accept with probability at least 1 − O(ǫ).Conditional expectations can be approximated as ratios of SQ-estimated expectations because the filters discard only an O(ǫ) fraction of points.Source: §8.3 · p. 50
• The proof shows that a sufficiently large Hermite-moment discrepancy yields a detectable polynomial expectation, enabling a filter to remove corrupt mass while controlling the Gaussian contribution.The argument uses Hermite-polynomial identities, moment lower bounds, and concentration inequalities to establish this filtering progress.Source: §8.3.1 · pp. 53, 55
• The filtering proof establishes a threshold T with the required tail behavior and uses it to improve the good, error, and leftover weights across iterations.The threshold is found by enumerating O(n log(1/ǫ))^t possibilities, and Proposition 8.12 follows by induction on the iterations.Source: §8.3.1 · pp. 58–59

8.3.2 Completing the Proof of Correctness

• The filtered moment matrices span a subspace V of dimension at most O(log(1/ǫ))^k, while the mean’s projection onto V has error at most O(ǫ).The algorithm uses moment matching to show that approximating µV suffices.Source: §8.3.2 · p. 60
• Each direction in V can be estimated to O(ǫ) using O(log log 1/ǫ) statistical queries of precision ǫ/2, after which an LP recovers µV to O(ǫ).A finite 1/2-net of V supports the LP constraints used for reconstruction.Source: §8.3.2 · pp. 60–61
• Theorem 8.7 is correct: the algorithm outputs an estimate with ∥µ−eµV∥2 ≤ O(ǫ), using statistical queries of the claimed precision.The proof combines ∥µV−µ∥2 ≤ O(ǫ) with ∥µV−eµV∥2 ≤ O(ǫ).Source: §8.3.2 · pp. 60–62

A Sample Complexity Upper Bound for Learning GMMs

• O(n^2k^3 log^2(k)/ε^5) samples suffice to learn a k-mixture of n-dimensional Gaussians to dTV error ε with probability at least 2/3.The resulting algorithm is information-theoretically efficient but not computationally efficient.Source: A Sample Complexity Upper Bound for… · p. 68
• The construction guesses mixture weights and component distributions, then uses a standard tournament to select a candidate close to the true mixture.The tournament argument is cited as standard in [DL01, DDS12b, DDS15].Source: A Sample Complexity Upper Bound for… · pp. 68–69
• O(n^2/δ^2) samples suffice for a polynomial-time algorithm to learn an n-dimensional Gaussian to total variation error δ with probability at least 2/3.This individual-Gaussian learner is the component used inside the mixture candidate construction.Source: A Sample Complexity Upper Bound for… · p. 68
• With M samples, an n-dimensional Gaussian can be learned to error ε with probability at least 1 − exp(−Ω(Mε^2/d^2)).The success probability improvement costs a logarithmic factor in the sample complexity for target failure probability δ.Source: A Sample Complexity Upper Bound for… · p. 68
• The mixture learner handles unknown component labels by enumerating all sample-to-component assignments, of which there are exp(N log(k)) for N samples.For the correct assignment, samples grouped by component are independent samples from the corresponding Gaussian components.Source: A Sample Complexity Upper Bound for… · p. 68
• Θ(n^2k^3 log(k)/ε^3) samples produce exp(O(n^2k^3 log^2(k)/ε^3)) candidate distributions, one of which is within ε in total variation with probability at least 2/3.Candidates correspond to guesses assigning every sample to one of the k mixture components.Source: A Sample Complexity Upper Bound for… · p. 68
• Ignoring components with weight below ε/(5k), concentration ensures sufficiently many samples for every remaining component, while each learned component has error at most ε/(10k).Together these conditions imply the correctly assigned candidate mixture has total variation error below ε with probability at least 2/3.Source: A Sample Complexity Upper Bound for… · p. 69

• Separation removes the general exponential-in-k obstruction because mixtures that are close in variation distance cannot remain far in their individual components.Without separation, pairs of mixtures can be ε^Ω(k)-close in variation distance while being ε-far in component parameters.Source: B Sample Complexity Upper Bound for… · p. 69
• Under pairwise overlap below (δ/k)^C, mixtures within total variation (δ/k)^C can be matched component-wise within L1 distance δ.The matching holds for normalized mixtures whose Gaussian components satisfy the stated separation condition, via a permutation of the k components.Source: B Sample Complexity Upper Bound for… · p. 69
• Because the basic Hellinger-like quantity lacks a triangle inequality for Gaussians, the analysis introduces an intermediate Gaussian notation that satisfies an approximate triangle inequality.A wide Gaussian can substantially overlap two widely separated narrow Gaussians, motivating the additional covariance and mean controls used in the proof.Source: B Sample Complexity Upper Bound for… · p. 70
• The proof establishes that each component Gi has large overlap with at most one component Hj, enabling the required permutation matching.Proposition B.7 supplies the uniqueness property under the assumptions of Theorem B.1; the final overlap-to-L1 argument yields the δ bound.Source: B Sample Complexity Upper Bound for… · pp. 72, 74

Testing the Mean

• O(√n/ε^2) samples suffice to distinguish N(μ, I) with zero mean from a Gaussian whose mean satisfies ||μ||_2 > ε, with probability at least 2/3.The test compares a statistic based on the aggregated samples against a threshold involving n and ε^2k/2.Source: C Testing the Mean of a… · p. 74
• The tester can be implemented in the SQ model by checking whether every coordinate-wise median has absolute value below ε/√n.This condition can be verified through coordinate-wise probabilities of the form Pr(x_i > 0) = 1/2 + O(ε/√n).Source: C Testing the Mean of a… · p. 74
• The O(√n/ε^2) sample complexity is optimal up to a constant factor, because mixtures over random nonzero means remain close in total variation to the zero-mean sample distribution.The lower bound uses μ drawn from N(0, (2ε/√n)I), for which ||μ||_2 > ε with probability at least 9/10, and compares the resulting covariance to the identity.Source: C Testing the Mean of a… · pp. 74–75

D.1 Proof of Fact 3.6

• D.1 proves the Hermite rotation identity by matching leading terms and using Gaussian orthogonality to show the residual polynomial vanishes identically.Rotation invariance gives the same second moment, while orthogonality forces E[p(X,Y)^2] = 0.Source: D Omitted Proofs · pp. 75–76

D.2 Proof of Lemma 3.7

• D.2 derives the random-unit-vector angle bound from Lemma D.2 [CFJ13], then applies a union bound to obtain the required set with positive probability.The argument uses α = 1/2 − c and controls pairwise inner products by Ω(n^(c−1/2)).Source: D Omitted Proofs · pp. 76–77

D.3 Proof of Fact 6.2

• D.3 proves Fact 6.2 by expanding the chi-squared expression for a mixture into weighted component divergences and a cross term.The resulting identity is 1 + w^2χ^2(B,D) + (1−w)^2χ^2(C,D) + 2w(1−w)χ_D(B,C).Source: D Omitted Proofs · p. 77

D.4 Proof of Fact 6.3

• D.4 proves Fact 6.3 directly from its definition.The passage provides no further intermediate argument.Source: D Omitted Proofs · p. 77

D.5 Proof of Fact 6.4

• D.5 likewise proves Fact 6.4 directly from its definition.The proof concludes immediately after the definitional step.Source: D Omitted Proofs · p. 77