Robust Estimators in High Dimensions without the Computational Intractability

1.1 Background

• The authors formulate agnostic distribution learning as efficiently recovering a distribution after an adversary arbitrarily corrupts an ε-fraction of samples, with total-variation error independent of dimension.They target single Gaussians, hypercube product distributions, balanced mixtures of two product distributions, and mixtures of spherical Gaussians; prior efficient algorithms had dimension-dependent guarantees.Source: §1.1 · pp. 4–5

1.2 Our Techniques

• Their common recipe replaces total variation with a dimension-independent parameter distance, then robustly estimates parameters using either spectral filtering or convex programming.Filtering removes points identified through spectral tests, while convex programming assigns weights using an approximate separation oracle; both approaches share nearly identical application guarantees, and the framework also requires strengthened concentration bounds.Source: §1.2 · pp. 5–6

1.3 Our Results

• For an arbitrary Gaussian with unknown mean and covariance, a polynomial-time algorithm achieves dTV(N(µ, Σ), N (bµ, bΣ)) ≤ O(ε log3/2(1/ε)) with probability 1 −τ.The unknown-covariance method analyzes the fourth-moment tensor, and the improved sample complexity is information-theoretically optimal up to logarithmic factors.Source: §1.3 · pp. 6–7
• The paper extends agnostic learning to binary product distributions and mixtures, proving that two c-balanced binary product distributions achieve dTV error at most O_c(ε1/6) with probability 1−τ.For balanced binary product distributions, the algorithm achieves error O(ε log(1/ε)); the mixture result assumes c-balanced components.Source: §1.3 · p. 7

1.4 Discussion and Related Work

• The work presents new robust, computationally efficient estimators for several well-studied distribution-learning problems, tolerating a constant fraction of errors independent of dimension and motivating algorithmic robust statistics.Subsequent work [DKK+17] improved the algorithms’ sample-complexity bounds to optimal up to polylogarithmic factors and extended the approach to dimension-independent robustness under weaker distributional assumptions.Source: §1.3 · p. 8, §1.5 · p. 9

1.6 Organization

• Sections 4–8 form the main body, illustrating convex programming and filtering frameworks for high-dimensional agnostic learning.Sections 2 and 3 introduce notation, the adversary model, and natural approaches that lose dimension-dependent factors.Source: §1.6 · p. 10
• The applications cover single Gaussians, mixtures of spherical Gaussians, binary product distributions, and balanced mixtures of two binary product distributions.Sections 4 and 5 study single Gaussians, Section 6 studies mixtures of spherical Gaussians, Section 7 studies binary product distributions, and Section 8 studies balanced binary-product mixtures.Source: §1.6 · p. 10
• Readers seeking the core technical ideas are directed to the Gaussian-with-unknown-mean and balanced-product-distribution examples for the convex-programming and filter frameworks, respectively.The recommended examples are Section 4.3 for convex programming and either Section 5.1 or Section 7.1 for filtering.Source: §1.6 · p. 10

2.1 Basic Notation

• The paper fixes notation for Euclidean, spectral, and Frobenius norms, PSD ordering, empirical sampling, probability densities or masses, and Kronecker products.Source: §2.1 · p. 10
• Total variation is the main distributional distance; Gaussian KL formulas and Pinsker’s inequality yield parameter-to-TV bounds, including O(δ^2) KL control for nearby covariances.The section also develops TV bounds for equal-covariance Gaussian means and binary product distributions, supporting later parameter-learning guarantees.Source: §2.1 · p. 10, §2.4 · pp. 12–14

2.2 Types of Adversaries

• The full adversary may inspect clean samples, remove a random-count subset whose marginal count is Bin(m, ε), and replace those samples arbitrarily.The paper explicitly allows the corruption count to depend on the original samples, making this model at least as strong as the oblivious model.Source: §2.2 · p. 11
• The full adversary can simulate any oblivious adversary, while analyses commonly condition on at most 2εm corruptions using a Chernoff bound.This simulation relies on the total-variation coupling described in Fact 2.4 and permits dependence between the number of edits and the original samples.Source: §2.2 · pp. 11–12

2.3 Distributions of Interest

• The distribution classes studied include Gaussians, binary product distributions determined by their mean vectors, and mixtures of distributions with specified mixing weights.Source: §2.3 · p. 12

2.5 Additional Concentration Lemmata

• Standard Chernoff, sub-Gaussian, Hanson–Wright, empirical-mean, and empirical-covariance concentration results provide the probabilistic controls used throughout the algorithms.Source: §2.5 · pp. 14–15

2.6 Agnostic Hypothesis Selection

• Finite candidate hypothesis sets enable an agnostic tournament that converts a list containing a δ-close hypothesis into one with TV error O(δ + ε) under arbitrary ε-corruption.The tournament uses computable densities to compare candidates, remains valid despite dependence between training and test samples, and also supports unknown ε through a geometric grid.Source: §2.6 · pp. 15–16

Learn Each Coordinate Separately

• Coordinatewise mean estimation can incur ε√d error because an ε-fraction of corruptions may shift every coordinate by ε.For Gaussian mean estimation with known covariance I, achieving O(ε) total variation requires O(ε) Euclidean mean error, so coordinatewise estimates lose a √d factor.Source: Learn Each Coordinate Separately · p. 17, §3 · p. 17

Maximum Likelihood

• The maximum likelihood estimator for a Gaussian with unknown mean and identity covariance is the sample mean, which an adversary can make arbitrarily bad by placing corruptions increasingly far away.Although MLE converges to the distribution closest in KL divergence to the corrupted sampling distribution, that distribution need not be close to the uncorrupted one.Source: Maximum Likelihood · p. 17

Geometric Median

• The geometric median is efficiently computable and often more robust than the mean, but it still incurs dimension-dependent error.The Tukey median is hard to compute, with best known algorithms exponential in d [JP78], whereas the geometric median can be computed quickly [CLM+16].Source: Geometric Median · p. 18
• The section formalizes the geometric-median limitation through Proposition 3.1, which gives a high-probability adversarial corruption construction under a sample-size condition.The proposition is attributed to Proposition 2.1 of [LRV16].Source: Geometric Median · p. 18

4 Agnostically Learning a Gaussian, via Convex Programming

• The framework achieves polynomial-time agnostic learning of a single Gaussian with error eO(ε) by combining convex-programming subroutines for unknown means and covariances.The section’s overall algorithm combines the intermediate results developed for identity covariance and zero mean with unknown covariance.Source: §4 · p. 18

4.1 The Set S_N,ε

• The set S_N,ε encodes selecting approximately (1−2ε)N samples, while ensuring that at most a 2ε fraction of total weight lies on corrupted points.Renormalizing weights on good points yields a valid distribution over those points, supporting robust estimation.Source: §4.1 · p. 18

4.2.1 Empirical Estimates of First and Second Moments of Large Subsets

• Gaussian concentration bounds control first and second moments uniformly over the worst-case large-subset weights in S_N,ε, despite the growth of that weight class with sample size.The section also records high-probability bounds preventing individual Gaussian samples from deviating too far in ℓ2-distance.Source: §4.2.1 · p. 19

4.2.2 Estimation Error in the Frobenius Norm

• For fixed ε, τ > 0, Corollaries 4.8 and 4.9 assert parameters δ1 and δ2, respectively, with δ1 = O(ε log 1/ε) and δ2 = O(ε log 1/ε), for independent samples from N(0, I).Source: §4.2.2 · p. 20

4.2.3 Understanding the Fourth Moment Tensor

• For X ∼ N(0,Σ), the fourth-moment tensor restricted to symmetric matrices decomposes into a high-rank term and a rank-one term.The analysis uses matrix flattening and projections onto the relevant symmetric subspaces; the two terms are explicitly distinct in rank.Source: §4.2.3 · p. 21

4.2.4 Concentration of the Fourth Moment Tensor

• The fourth-moment tensor concentrates with error δ_3 = O(ε log^2 1/ε), requiring degree-four polynomial tail bounds because ordinary union bounds are insufficient.The proof exploits concentration strong enough that removing points cannot substantially change the mean.Source: §4.2.4 · pp. 21–22

4.3 Finding the Mean, Using a Separation Oracle

• For N samples from N(µ,I), convex optimization over a weight set estimates µ, but the unknown mean necessitates naive pruning followed by an approximate separation oracle.Any feasible weight vector in C_δ yields a good empirical mean estimate, while the oracle separates inaccurate weights and supports ellipsoid optimization.Source: §4.3 · p. 22, §4.3.2 · p. 24

4.3.1 Naive Pruning

• Naive pruning removes no uncorrupted points and ensures every retained point lies within O(√d) of µ under the stated deterministic conditions.It computes all pairwise distances and removes points distant from more than a 2ε-fraction of the remaining samples.Source: §4.3.1 · p. 22

4.3.2 The Separation Oracle

• The separation oracle certifies feasible weights and separates weights outside C_cδ, completing the soundness analysis.The analysis concludes with a lower bound of Ω(ε^2 log 1/ε) in the relevant case.Source: §4.3.2 · p. 26

4.3.3 The Full Algorithm

• The full convex-programming algorithm runs in polynomial time and estimates the Gaussian mean with error at most δ, where δ = O(ε log 1/ε), with probability 1−τ.It first prunes the samples, approximately optimizes over C_cδ, and outputs the weighted sample mean.Source: §4.3.3 · p. 26

4.4 Finding the Covariance, Using a Separation Oracle

• For covariance estimation, the separation oracle accepts the uncorrupted weights and outputs a separating hyperplane for weights outside C_cδ, enabling polynomial-time convex optimization.The oracle’s correctness follows by handling deviations through its two hyperplane tests, while any output hyperplane satisfies ℓ(w∗) < 0.Source: §4.4 · pp. 27, 28, 32, 33

4.4.1 The Full Algorithm

• The full covariance algorithm runs in polynomial time and outputs weights whose infinity-norm distance from a feasible vector is at most ε/(Nd log(N/τ)).It prunes samples with excessively large normalized norms, reruns the covariance procedure, and never removes uncorrupted points; corrupted points above the stated threshold are removed.Source: §4.4.1 · pp. 33–34
• The resulting covariance estimator satisfies ∥Σ^-1/2 bΣΣ^-1/2 − I∥_F ≤ O(δ) with probability 1−τ, where δ = O(ε log 1/ε).This guarantee applies to ε-corrupted samples from N(0,Σ) for ε ≤ 1/2.Source: §4.4.1 · p. 34

4.5 Learning an Arbitrary Gaussian Agnostically

• Arbitrary Gaussian learning combines the known-covariance mean learner with the mean-zero covariance learner when both µ and Σ are unknown.The construction uses the covariance procedure from Section 4.4 and the mean procedure from Section 4.3.Source: §4.5 · p. 35

4.5.1 From Unknown Mean, Unknown Covariance, to Zero Mean, Unknown Covariance

• Pairwise differences convert N ε-corrupted samples from N(µ,Σ) into N/2 samples from N(0,Σ) with corruption rate at most 2ε.A paired difference is corrupted only when at least one member of the pair is corrupted, while uncorrupted pairs have the desired zero-mean Gaussian distribution.Source: §4.5.1 · p. 35

4.5.2 From Unknown Mean, Approximate Covariance, to Approximate Recovery

• After whitening by the recovered covariance, the transformed samples form an O(ε log 1/ε)-corrupted set from N(bΣ^-1/2µ,I), enabling mean recovery.The mean estimate satisfies ∥bµ−bΣ^-1/2µ∥_2 ≤ O(ε log^3/2(1/ε)) with probability 1−τ, assuming the covariance approximation condition holds.Source: §4.5.2 · p. 35
• Theorem 4.36 establishes a polynomial-time procedure that, with probability 1−τ, outputs estimates bΣ and bµ for an arbitrary Gaussian under ε-corruption.The theorem applies when both the mean and covariance are unknown; the supplied passage does not display the estimator’s explicit error inequalities.Source: §4.5.2 · p. 36

5.1 Learning a Gaussian With Unknown Mean

• For an ε-corrupted sample set from an identity-covariance Gaussian, an efficient algorithm returns a mean estimate within O(ε) of the true mean with probability at least 1 − τ.The algorithm uses Ω((d/ε^2) poly log(d/ετ)) samples.Source: §5.1 · p. 36
• Independent Gaussian samples satisfy the required goodness conditions with high probability, including mean and modified covariance deviations at most ε, enabling the iterative filter guarantee.The filtering proposition decreases the corruption discrepancy by ε/α when it removes a subset, and the overall procedure terminates after O(α) iterations.Source: §5.1 · pp. 36–37

5.1.1 Algorithm FILTER-GAUSSIAN-UNKNOWN-MEAN: Proof of Proposition 5.5

• The filter repeatedly removes points along a direction of unusually large covariance eigenvalue, or returns the empirical mean when no such eigenvalue exists.The procedure computes the empirical mean and covariance, then filters using the maximum-eigenvalue eigenvector when ||Σ − I||_2 exceeds O(ε log(1/ε)).Source: §5.1.1 · pp. 37–38

5.1.2 Proof of Correctness of FILTER-GAUSSIAN-UNKNOWN-MEAN

• The correctness proof shows that the empirical covariance deviation is approximately proportional to the error points’ covariance, so a large eigenvalue identifies a direction containing many corruptions.Specifically, MS′ − I = (|E|/|S′|)ME + O(ε log(1/ε)) in spectral norm.Source: §5.1.2 · pp. 38–39

5.2 Learning a Gaussian With Unknown Covariance

• The same filter technique is combined with the preceding covariance-learning algorithm to learn an arbitrary unknown Gaussian.This subsection specifically starts from zero-mean Gaussians with unknown covariance before combining the two procedures.Source: §5.2 · p. 42
• The algorithm learns N(0, Σ) from Ω((d^2/ε^2) poly log(d/ετ)) corrupted samples, returning covariance bΣ with relative Frobenius error O(ε log(1/ε)) with probability at least 1−τ.Equivalently, the associated Gaussian estimate G′ satisfies dTV(G, G′) ≤ O(ε log(1/ε)).Source: §5.2 · pp. 42–43
• The filter runs in polynomial time and either returns G′ with dTV(G, G′) ≤ O(ε log(1/ε)) or produces S′′ with strictly smaller corruption distance.Iterating this progress measure must eventually yield a valid Gaussian estimate.Source: §5.2 · p. 43, §5.2.1 · p. 45

5.2.1 Analysis of Filter-based Algorithm: Proof of Proposition 5.18

• The filter estimates Σ′ from empirical second moments and detects covariance distortion through a large fourth-moment eigenvalue, yielding a quadratic polynomial whose unusually large values identify removable corruptions.It removes points exceeding a polynomial-tail threshold, while the FIND-MAX-POLY procedure computes the relevant polynomial by approximate eigen-decomposition.Source: §5.2.1 · pp. 44–45
• The analysis shows that removing an ε-fraction of good samples changes quadratic-polynomial moments by O(ε log(1/ε)) in the mean and O(ε log^2(1/ε)) in the second moment.These bounds control the contribution of discarded good points and support the filter’s progress and correctness guarantees.Source: §5.2.1 · pp. 46–47
• If the filter stops without removing points, the empirical covariance is sufficiently close to the true covariance, implying dTV(G, G′) = O(ε log(1/ε)).Otherwise, the corruption contribution creates a detectable quadratic direction with excessive variance, so filtering can continue.Source: §5.2.1 · pp. 47–48
• The analysis bounds the quadratic statistic’s variance under the Gaussian using the estimated covariance and Frobenius/operator norm relations.It represents p(x) through a matrix M and uses Σ′ ≥ (1 − O(ε log(1/ε)))Σ to control the relevant norms.Source: §5.2.1 · p. 49
• A variance excess of at least 1 + Cε ln^2(1/ε) implies that a threshold T exists where tail points contribute disproportionately to the discrepancy.The argument uses percentile control, ε-goodness, and Cantelli’s inequality to show that valid points cannot explain the observed variance alone.Source: §5.2.1 · p. 49
• If the algorithm returns in Step 12, the filtering update reduces the distance to the uncorrupted set by ε/(d log(N/τ))^2.The proof establishes this by showing that sufficiently many extreme points belong to E rather than to valid points in S \ L.Source: §5.2.1 · p. 50

6.1 Notation and Norms

• The section introduces mixture-mean and component-separation parameters, concentration inequalities, and the Schatten top-k norm used to control robust covariance estimates.The norm is defined as the sum of the top-k singular values of a symmetric matrix.Source: §6.1 · pp. 51–52, §6.2 · p. 52

6.3 Algorithm

• The algorithm constructs a polynomial-size candidate list containing a mixture hypothesis close to the unknown distribution, then selects a suitable candidate by tournament-style hypothesis selection.The list has size poly(d, 1/ε, log(1/τ))^k2, and the approach assumes mixing weights and variance are known during its main analysis.Source: §6.3 · p. 53
• A separation-oracle framework finds sample weights whose weighted empirical covariance is spectrally close to the true covariance, replacing unreliable empirical moments under adversarial corruption.The oracle uses convex programming, while the resulting covariance estimate enables subsequent mixture-learning arguments modeled on prior spherical-Gaussian methods.Source: §6.3 · p. 53, §6.5 · p. 55

6.6 Spectral Clustering

• When component means are sufficiently separated, spectral clustering projects onto the top covariance eigenvector and tolerates a small fraction of misclassified points, avoiding dimension-dependent agnostic error.The relevant separation threshold is Ω(k log(1/ε)).Source: §6.3 · p. 54, §6.6 · p. 57

6.3 Algorithm

• For sufficiently small separation, the algorithm exhaustively searches a mesh in the estimated top-(k−1) covariance subspace to obtain candidate component means close to the true means.It then applies finite-hypothesis selection after restricting the hypothesis set to satisfy the selection lemma’s requirements.Source: §6.3 · p. 54

6.4 Naive Clustering

• Naive clustering recursively separates extremely distant components while discarding and misclassifying only O(ε)-fractions of good points under the stated concentration condition.Within each resulting cluster, associated component means differ by at most O(dk log(k/ε)), and each cluster contains fewer components for recursive learning.Source: §6.4 · pp. 54–55

6.5.1 Properties of Our Convex Set

• The convex-set analysis shows that admissible weights approximate the mixture mean, while weights outside the set expose excessive weighted covariance in the Schatten top-k norm.This establishes the geometric basis for the separation oracle and accurate covariance estimation.Source: §6.5.1 · pp. 55–56

6.5.2 Separation Oracle

• The separation oracle is complete on uniform uncorrupted-point weights and soundly returns a separating hyperplane for weights outside the convex set.The ellipsoid method therefore finds a nearby feasible weighting in polynomially many iterations.Source: §6.5.2 · p. 56

6.6 Spectral Clustering

• Spectral clustering separates components by the sign of v^T X, misclassifying at most O(poly(ε/k)) of samples when γ = O(poly(k) · log(1/ε)).The resulting partition has v^T µ_j > 0 for one subset and v^T µ_j < 0 for the other, enabling recursive clustering.Source: §6.6 · p. 57
• Unlike prior clustering requiring no misclassifications, the agnostic algorithm tolerates a poly(ε/k)-fraction and avoids a logarithmic dependence on dimension.The comparison is to [SOAJ14], whose approach requires γ = Ω(poly(k) · log(d/ε)) to ensure no sample is misclustered.Source: §6.6 · p. 57

6.7 Exhaustive Search

• Exhaustive search discretizes a (k −1)-dimensional cube around the empirical mean and uses a k-wise Cartesian product to obtain simultaneous approximations for all component means.The construction follows the exhaustive search of and uses an η-mesh with η = poly(ε/dk) sufficiently small.Source: §6.7 · p. 58

6.8.1 Guessing the Mixing Weights and Variance

• The tournament stage guesses mixing weights and variance, treating sufficiently accurate misspecification as additional agnostic error; weights below ε may be specified arbitrarily at O(kε) total variation cost.The candidate mixing-weight set has at most poly(k/ε)^k possibilities, while variance is estimated from pairwise distances among repeatedly sampled groups.Source: §6.8.1 · pp. 58–59

6.8.2 Pruning Our Hypotheses

• Hypothesis pruning removes clear outliers, meshes the remaining union of balls around samples, and rounds candidates to a fixed finite set before tournament selection.Each retained hypothesis is replaced within ε/k per mean, incurring O(ε) total variation distance by Corollary 2.13.Source: §6.8.2 · pp. 59–60

6.9 Handling Unequal Variances

• For unequal variances, the algorithm estimates the minimum variance, partitions samples into bounded variance ranges, and changes the convex program accordingly, affecting guarantees by only a constant factor.The partition contains components with variance at most a threshold t satisfying t ≤ eσ^2_min, while each cluster’s variances differ by at most a factor of e.Source: §6.9 · pp. 60–61

7 Agnostically Learning Binary Product Distributions, via Filters

• For imbalanced coordinates, the method rescales discrepancies using χ2-distance and a corrected eigenvalue problem, ultimately achieving eO(√ε) total-variation error.The initial ℓ2 estimate is used to construct the corrected covariance-based procedure.Source: §7 · pp. 61–62

7.1 The Balanced Case

• The algorithm estimates binary product means within O(ε log(1/ε)) in ℓ2-distance under ε-fraction adversarial corruption using polynomially many samples.The guarantee holds with probability at least 1 −τ from Θ(d4 log(1/τ)/ε2) samples.Source: §7.1 · p. 62
• For balanced product distributions, the mean-vector guarantee yields a corresponding total-variation guarantee because ℓ2-distance is a proxy for total variation.A distribution is c-balanced when every coordinate mean lies in [c, 1 −c], and the proxy relation applies to two c-balanced distributions.Source: §7.1 · p. 62

7.1.1 Algorithm FILTER-BALANCED-PRODUCT: Proof of Proposition 7.7

• The filter repeatedly removes points along a large-eigenvalue direction of the zero-diagonal empirical covariance, or returns the empirical mean when no large eigenvalue remains.Zeroing the diagonal prevents intrinsic diagonal contributions from producing Ω(1) spectral norm and blocking the desired error.Source: §7.1.1 · pp. 63–64
• The filter analysis is tight: O(ε log(1/ε)) is a bottleneck for filter-based approaches.Adversarially changed points may be removed but not restored, allowing them to shift the sample mean by as much as Ω(ε log(1/ε)).Source: §7.1.1 · pp. 63–64

7.1.2 Setup and Basic Structural Lemmas

• The structural proof shows that the uncorrupted zero-diagonal empirical covariance approximates its population counterpart within O(ε) spectral norm.The analysis decomposes the corrupted covariance into contributions from genuine, added, and removed samples, while controlling linear projections by concentration.Source: §7.1.2 · p. 65
• Corollary 7.13 bounds the centered second-moment discrepancy by O(ε log(1/ε) + ∥µS′ − p∥2), providing the structural estimate used by both algorithmic cases.Source: §7.1.2 · p. 66

7.1.3 The Case of Small Spectral Norm

• When ∥M∥2 ≤ O(ε log(1/ε)), Lemma 7.15 implies ∥µS′ − p∥2 = O(ε), establishing correctness when the algorithm returns the mean vector.Source: §7.1.3 · p. 67

7.1.4 The Case of Large Spectral Norm

• When ∥M∥2 ≥ Cε log(1/ε), FILTER-BALANCED-PRODUCT finds a threshold whose filter reduces ∆(S, S′) by 2ε/d while rejecting more corrupted than uncorrupted samples.Source: §7.1.4 · pp. 68–69

7.2 Agnostically Learning Arbitrary Binary Product Distributions

• The arbitrary-product learner runs in polynomial time on Θ(d6 log(1/τ)/ε3) corrupted samples and outputs a product distribution whose total variation error is O(…), with probability at least 1 − τ.Source: §7.2 · p. 69

7.2.2 Chi-Squared Distance and Basic Reductions

• Because ℓ2 distance is insufficient for unbalanced products, the analysis rescales coordinates and uses an asymmetric χ2-distance as a proxy for total variation distance.Source: §7.2 · p. 69, §7.2.2 · p. 72

7.2.1 Algorithm FILTER-PRODUCT: Proof of Proposition 7.23

• FILTER-PRODUCT computes a sample covariance, rescales it by marginal standard deviations, returns the mean when the top eigenvalue is small, and otherwise filters along a top eigenvector using a randomized threshold.Source: §7.2.1 · p. 71

7.2.2 Chi-Squared Distance and Basic Reductions

• FILTER-PRODUCT preprocesses coordinates to ensure ε/d ≤ µS′_i ≤ 1 − ε/d and modifies the target so extreme coordinates can be fixed to 0 or 1 while preserving goodness.The modification incurs an η loss of ||p − ep||1 and reduces the discrepancy by at least pi/5 or (1 − pi)/5 for each fixed coordinate.Source: §7.2.2 · pp. 72–73

7.2.3 Setup and Basic Structural Lemmas

• The structural analysis bounds the normalized clean matrix by 9 + χ2(µS′, p), the removed-sample matrix by O(|S′|/|L| + χ2(µS′, p)), and the combined error matrix by O(1 + χ2(µS′, p)).These bounds relate spectral properties of the matrices to the χ2-distance between the empirical and target means.Source: §7.2.3 · pp. 76–77

7.2.4 The Case of Small Spectral Norm

• O(ε log(1/ε)) total variation: if FILTER-PRODUCT terminates at Step 8, its product distribution with mean µS′ satisfies dTV(P, P′) ≤ O(ε log(1/ε)).The proof bounds χ2-distances to the error and removed multisets using their normalized spectral matrices, then applies the product-distribution total-variation reduction.Source: §7.2.4 · pp. 77–78

7.2.5 The Case of Large Spectral Norm

• When the spectral norm is Ω(1), a direction with |v′D_M_Dv′^T| = Ω(1) enables the algorithm to return a filter.This follows by applying Corollary 7.37 to the identified large quadratic form.Source: §7.2.5 · p. 79
• The filtering update satisfies E_Z[Δ(S, S′′)] ≤ Δ(S, S′).Thus, in expectation, the update does not worsen the sample set’s distance from the target set.Source: §7.2.5 · p. 79
• For sufficiently large λ′, the expected number of false-positive rejections and retained errors is bounded by the original error and loss counts.Specifically, E_Z[|E′| + |L′|] ≤ |E| + |L|.Source: §7.2.5 · p. 79

8.1 The Full Algorithm

• The full algorithm learns a corrupted mixture of two c-balanced binary products in polynomial time, using poly(d, 1/ε) log(1/τ) samples and succeeding with probability at least 1 −τ.It runs complementary procedures in parallel, rounds candidate parameters, and uses a tournament to select a sufficiently close hypothesis.Source: §8.1 · pp. 80–81
• The two complementary strategies handle either a coordinate with substantially different component means or means that are close in every coordinate.The first conditions on that coordinate and analyzes conditional means; the second zeroes covariance diagonals while controlling the resulting error.Source: §8.1 · p. 80

8.2 Mixtures of Products Whose Means Differ Significantly in One Coordinate

• When a separating coordinate is known, filtering conditional empirical means and covariance directions produces a candidate set containing a mixture close to the target under balancedness and nontrivial mixing weights.Theorem 8.2 assumes p_i* ≥ q_i* + ε1/6 and ε1/6 ≤ α ≤ 1 −ε1/6; its iterative proposition either reduces corruption or returns suitable candidate mixtures.Source: §8.2 · pp. 81–82
• Random samples form the required conditioned-good set with probability at least 1 −τ using Ω(d^4 log(1/τ)/ε13/6) samples, enabling the filtering analysis.The good-set condition applies simultaneously to every coordinate and supports iterative correction after an ε-fraction of entries is corrupted.Source: §8.2 · p. 82
• If Step 8 terminates, the candidate set contains a mixture Π′ with dTV(Π′, Π) = O(ε1/6/√The construction places both component means near the candidate line, with distance δ + O(ε1/6), and uses balancedness to transfer mean proximity to total variation.Source: §8.2 · p. 86
• When λ is large, the filter identifies a threshold T > 0 whose tail condition enables removal of corrupted points.The analysis shows that large variance in the v-direction is attributable to the exceptional set E, while the threshold existence follows by contradiction.Source: §8.2 · pp. 86–87
• Each filtering update strictly improves sample proximity: if the algorithm returns S′′, then Δ(S, S′′) ≤ Δ(S, S′) −2ε/d.Hoeffding’s inequality bounds the removed mass from the uncorrupted component, establishing the progress guarantee.Source: §8.2 · pp. 88–89

8.3 Mixtures of Products Whose Means Are Close in Every Coordinate

• For coordinatewise-close means, Theorem 8.17 guarantees a polynomial-time algorithm that, from Ω(d4 log(1/τ)/(ε2δ)) samples, returns Π′ with dTV(Π, Π′) ≤O(δ/√The guarantee applies to c-balanced products with ∥p −q∥∞≤δ and adversarially changed ε-fraction of samples, with success probability at least 1 −τ.Source: §8.3 · p. 89
• The algorithm first uses a large-eigenvalue test on Cov0(S′), then either enumerates candidate means along a leading eigenvector or filters along a rotated two-eigenvector direction.Its correctness relies on covariance being close to positive semidefinite and on good samples admitting a componentwise partition.Source: §8.3 · pp. 89–90
• If only one large eigenvalue exists, both component means lie near a discretized line, and Step 6 outputs a distribution with dTV(Π′, Π) ≤O(δ/√Lemma 8.24 establishes the line approximation, while Corollary 8.25 converts it into a valid mixture candidate.Source: §8.3 · p. 91
• The filter finds a direction r in span(u*, v*) and a threshold t large enough to expose many corrupted points, with t ≥ 1 + 2√log(3/ε).The construction discretizes directions in the span of u* and v*, and establishes sufficient variance along r to make the filter succeed.Source: §8.3 · pp. 92, 95
• For an arbitrary filter direction r, the analysis shows that the filter does not remove too many points from S.The argument bounds the points outside a central interval using Hoeffding’s inequality and compares the sizes of S and S′.Source: §8.3 · pp. 95–96
• If Step 9 returns S′′, then the discrepancy satisfies ∆(S, S′′) ≤ ∆(S, S′) − 2ε/d.Source: §8.3 · p. 96
• Step 9 removes at least a 12 exp(−t^2/4) + 3ε/d fraction of points.This removal bound is used together with the concentration conditions to establish the discrepancy improvement.Source: §8.3 · p. 96

Proof of Lemma 4.3

• The proof of Lemma 4.3 combines fixed-w_J bounds with events E1 and E2(J), then applies a union bound over subsets J of size (1−ε)N.The argument controls the terms uniformly over admissible J using Lemma 2.22 and entropy bounds.Source: A Deferred Proofs from Section 4 · pp. 103–104
• The Lemma 4.3 proof concludes by combining entropy estimates, the asymptotic bound H(ε)=O(ε log 1/ε), the choice of δ1, and the choice of n.These steps establish the required probability bound for sufficiently small ε.Source: A Deferred Proofs from Section 4 · pp. 103–104

Proof of Theorem 4.12

• The proof of Theorem 4.12 invokes Isserlis’ theorem to evaluate Gaussian moments and uses symmetry and eigenvalue expansions to identify the relevant quadratic form.Isserlis’ theorem expresses Gaussian moment calculations through matchings, while symmetry ensures the quadratic form uniquely identifies the operator.Source: A Deferred Proofs from Section 4 · pp. 104–105

Proof of Corollary 4.9

• The proof of Corollary 4.9 applies the same Bernstein-style analysis as Lemma 4.3 and then union bounds over all m from 1 through εN.The argument introduces the family of m-element subsets S_m and derives the result through the same subsequent manipulations.Source: A Deferred Proofs from Section 4 · p. 105

A.1 Proof of Theorem 4.13

• The proof of Theorem 4.13 follows immediately from Lemmas 5.17 and 5.20.Source: §A.1 · p. 105

B.1 Proof of Lemma 5.3

• N = Ω((d/ε^2) poly log(d/ετ)) samples are drawn from G to establish the lemma’s probabilistic properties.Source: §B.1 · p. 106
• Coordinate tails and a union bound show that all sample coordinates remain below the stated threshold with probability at least 1 − τ/3.Source: §B.1 · p. 106
• After translating by μ_G, parts (iii) and (iv) follow from Lemma 2.21 and Theorem 5.50 of under an additional sample-size requirement.The cited theorem requires N = Ω(ν^4 d log(1/τ)/ε^2), with probability at least 1 − τ/3.Source: §B.1 · p. 106
• The VC inequality controls the small-threshold regime, using the VC-dimension d + 1 of halfspaces and the chosen δ-dependent sample size.Source: §B.1 · p. 106
• A 1/2-cover of the unit sphere, dyadic thresholds, and a union bound extend the fixed-direction estimate to all unit vectors and thresholds up to R.The cover has size 2^O(d), and the resulting failure probability is bounded by τ/6 before the final union bound.Source: §B.1 · pp. 106–107
• The argument uses sub-Gaussianity and Markov’s inequality to obtain the desired bound when δ is sufficiently small and C is sufficiently large.Source: §B.1 · p. 107
• Combining the bounds by union bound proves the target inequality simultaneously for every unit vector and every 0 ≤ T ≤ R with probability at least 1 − τ/3.Source: §B.1 · p. 107

B.2 Proof of Lemma 5.16

• An even polynomial is expressed as a centered quadratic form (Σ^-1/2x)^T P_2(Σ^-1/2x) plus a constant p_0, with P_2 symmetric.The representation follows because even polynomials have no degree-1 terms.Source: §B.2 · p. 107
• An eigen-decomposition of P_2 transforms X ∼ G into Y ∼ N(0,I), reducing p(X) to a sum of terms involving independent Gaussian variables.This identifies p(X) as following a generalized χ2-distribution.Source: §B.2 · p. 107
• The eigenvalue and Frobenius-norm relationships for P_2 provide the variance parameters used in the resulting two-sided concentration bound.The proof applies the bound to both p(x) and -p(x).Source: §B.2 · p. 108
• The remaining property follows from an anti-concentration inequality for polynomials under a standard Gaussian, completing the proof.The inequality is attributed to Theorem B.3 ().Source: §B.2 · p. 108

• The argument reduces the proof from covariance Σ to Σ = I by whitening, preserving the relevant conditions under the transformation.Source: §B.3 · p. 108
• Condition 3 is established by representing degree-2 polynomials in an orthonormal basis and bounding the resulting matrix operator norm through a finite cover and union bound.The cover has size 2^O(d^2), and the proof seeks Var(p_v(S)) = 1 + O(ε) for every covered direction.Source: §B.3 · p. 108
• Hanson–Wright yields sharper tails for polynomials whose associated matrices lack a single dominant eigenvalue, motivating decomposition by eigenvalue scales.For p(x) = x^T A x − tr(A), the tail exponent depends on both ||A||_F and ||A||_2.Source: §B.3 · pp. 108–109
• Every normalized even degree-2 polynomial decomposes into O(log(d)) components from the classes P_k, each controlled by rank and eigenvalue constraints.Lemma B.5 writes p = 2(p_1 + p_2 + ... + p_2^t + p_d), with p_k ∈ P_k.Source: §B.3 · p. 109
• For each P_k, a cover C_k of size 2^O(dk log R) approximates every polynomial in variance, allowing any normalized polynomial to be represented by O(log(d)) cover elements plus residual variance O(1/R^2).The construction uses discretized eigenvalues and eigenvectors under the bounded-norm condition ||x||_2 ≤ R.Source: §B.3 · p. 109

Proof of Theorem 6.8

• Theorem 6.8 derives ||µ_j − µ_j′||_2^2 ≤ O(kd log k/ε) by connecting clusters whose component means are pairwise O(d log k/ε)-close.An auxiliary graph on k components contains a path between j and j′, whose length is at most k; the fourth property follows by the same argument.Source: C Deferred Proofs from Section 6 · p. 110

Deferred covariance proof

• The covariance argument restricts attention to a rank-at-most-k subspace spanning the component-mean offsets and v, then lower-bounds the Schatten top-k norm using its dual characterization.For an orthonormal basis matrix U of this subspace, ||C||_Tk ≥ Tr(U^T C U).Source: C Deferred Proofs from Section 6 · p. 111

Proof of Lemma 6.10

• Lemma 6.10 combines projection control, the triangle inequality, nonnegative variance, and earlier facts to obtain the stated final bound.The proof first establishes ||P_wg(X_i − µ)||_2 ≤ k^1/2δ_2 before applying the variance argument.Source: C Deferred Proofs from Section 6 · p. 112

C.1 Proof of Theorem 6.12

• The uniform weights on uncorrupted points are feasible, and Corollary 6.11 bounds the mean error ∥∆∥2.Feasibility follows from E ≤ 2εN and equation (33), which place w∗ in the constraint set.Source: §C.1 · p. 113
• The proof bounds the Schatten top-k norm of M by expanding it into positive semidefinite components and applying the stated inequalities and Lemma 6.10.The argument invokes the triangle inequality, equation (33), Fact 4.2, positive semidefiniteness, and sufficiently large c.Source: §C.1 · pp. 113–114
• Since ℓ(w) ≥ 0 by construction, the proof completes soundness by showing ℓ(w∗) < 0, including the remaining case for sufficiently large c.The final case analysis concludes that ℓ(w∗) < 0 as desired.Source: §C.1 · pp. 114–115

Proof of Lemma 7.21

• With Ω(d^4 log(1/τ)/ε′^2) samples and ε′ = ε^3/2/(10d), Lemma 7.6 yields simultaneous affine-function deviation at most ε′/d with probability at least 1 − τ.The proof conditions on this high-probability event.Source: D Deferred Proofs from Section 7 · p. 115
• The event C_T that all coordinates in T take their most common values has P-probability at least 3/5 and S-probability at least 1/2.This follows by a union bound and applying the affine-function deviation bound to 1 − #T(x), where #T counts non-common coordinates.Source: D Deferred Proofs from Section 7 · p. 115
• Defining L_T(x) = L(x) − #T(x) · max_y∈{0,1}^d L(y) makes L_T(x) > 0 equivalent to L(x) > 0 together with C_T.The proof then compares the corresponding probabilities under the uniform sample set and P to complete Lemma 7.21.Source: D Deferred Proofs from Section 7 · p. 116

Proof of Lemma 8.6

• Lemma 8.6 shows that component sample sets are simultaneously (ε, i)-good for P and Q, yielding (ε, i)-goodness for the mixture with probability at least 1 −τ.Chernoff bounds control the component proportions, while Lemma 7.6 supplies ε′-goodness using Ω(d^4 log(1/τ)/ε^2) samples.Source: E Deferred Proofs from Section 8 · pp. 116–117

Proof of Lemma 8.19

• Lemma 8.19 similarly proves that SP and SQ are ε-good for P and Q, respectively, with component sizes Ω(d^4 log(1/τ)/ε^2).The proof applies Lemma 7.6 with ε′ := ε/6 after controlling component proportions by a Chernoff bound.Source: E Deferred Proofs from Section 8 · p. 117

Proof of Lemma 8.22

• The covariance proof decomposes zero-diagonal covariance error by the triangle inequality, separately bounding diagonal and off-diagonal contributions.Product structure makes Cov(S′) have potentially large diagonal but small off-diagonal entries, while Cov(T) can retain large spectral norm through off-diagonal terms.Source: E Deferred Proofs from Section 8 · p. 117
• The Lemma 8.22 bounds combine mixture mean estimates with ∥p −q∥∞≤δ to obtain a δ + O(ε) error, and the proof closes when δ^2 = Ω(ε log(1/ε)).The mixture mean deviations satisfy ∥µ_SP−p∥∞≤ε/d and ∥µ_SQ−q∥∞≤ε/d before applying the triangle inequality.Source: E Deferred Proofs from Section 8 · pp. 118–119