PaperlayerView exact revision on arXiv

Source-linked AI summary

List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

arXiv:1711.07211v1cs.DScs.CCcs.ITcs.LGmath.ST

TL;DR

The paper addresses open questions in list-decodable Gaussian mean estimation and learning separated spherical-Gaussian mixtures. It uses high-degree multivariate polynomials for outlier removal and achieves improved efficient guarantees, including error O(α^-1/(2d)) for mean estimation.

  • Problem

    The best information-theoretic and computational error guarantees for list-decodable Gaussian mean estimation remain open.

    Source: §1.2 · pp. 3–4

  • Method

    The paper analyzes high-degree multivariate polynomials to design outlier-removal algorithms for heavily corrupted high-dimensional datasets.

    Source: §1.4 · p. 5, §1.6.1 · p. 10

  • Results

    O(α^-1/(2d)) error: the algorithm outputs O(1/α) candidate means and runs in time O(n^d/α)^O(d).

    Source: §1.4 · p. 5

  • Takeaways & Limitations

    The results provide improved efficient guarantees for list-decodable Gaussian mean estimation and related robust mixture-learning problems.

    Source: §1.4 · p. 5

    The robust mixture-learning setting assumes the corruption fraction η is much smaller than the minimum mixture weight.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

We study the problem of list-decodable Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. {\bf List-Decodable Mean Estimation.} Fix any $d \in \mathbb{Z}_+$ and $0< α<1/2$. We design an algorithm with runtime $O (\mathrm{poly}(n/α)^{d})$ that outputs a list of $O(1/α)$ many candidate vectors such that with high probability one of the candidates is within $\ell_2$-distance $O(α^{-1/(2d)})$ from the true mean. The only previous algorithm for this problem achieved error $\tilde O(α^{-1/2})$ under second moment conditions. For $d = O(1/ε)$, our algorithm runs in polynomial time and achieves error $O(α^ε)$. We also give a Statistical Query lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. {\bf Learning Mixtures of Spherical Gaussians.} We give a learning algorithm for mixtures of spherical Gaussians that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform mixture of $k$ identity covariance Gaussians we obtain: For any $ε>0$, if the pairwise separation between the means is at least $Ω(k^ε+\sqrt{\log(1/δ)})$, our algorithm learns the unknown parameters within accuracy $δ$ with sample complexity and running time $\mathrm{poly} (n, 1/δ, (k/ε)^{1/ε})$. The previously best known polynomial time algorithm required separation at least $k^{1/4} \mathrm{polylog}(k/δ)$. Our main technical contribution is a new technique, using degree-$d$ multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.

1 Introduction … 1.4 Our Contributions

This section studies list-decodable Gaussian mean estimation and spherical Gaussian-mixture learning under substantial corruption or weak separation. It presents polynomial-based algorithms with improved error and separation guarantees, establishes minimax errors and SQ lower bounds for mean estimation, and outlines clustering methods for equal and arbitrary component covariances.

1.1 Background

  • List-decodable estimation seeks an O(1/α)-sized candidate list containing a Gaussian mean despite arbitrary corruption of the remaining points.A single accurate hypothesis is information-theoretically impossible when α<1/2.Source: §1.1 · p. 2

1.2 List-Decodable Robust Learning

  • The large-error regime asks whether efficient algorithms can estimate a Gaussian component when the good fraction α is strictly below 1/2.This setting is motivated both by applications and by its connection to learning mixture components.Source: §1.2 · pp. 3–4

1.4 Our Contributions

  • The spherical-GMM result extends to arbitrary spherical mixtures and tolerates a small dimension-independent fraction of adversarial noise.Theorem 1.4 estimates weights, means, and scales under component-weight and separation conditions, with polynomial sample and time complexity.Source: §1.3 · p. 4, §1.4 · pp. 6–7

1.3 Learning Mixtures of Separated Spherical Gaussians

  • Prior efficient learning of spherical k-GMMs required pairwise mean separation at least k^1/4 polylog(nk/δ), motivating weaker-separation algorithms.The information-theoretic threshold for equal-weight, identity-covariance mixtures was characterized as Θ(√log k), but the corresponding approach was exponential in dimension.Source: §1.3 · p. 4

1.4 Our Contributions

  • The method iteratively uses degree-d polynomial moments and spectral decompositions to split the data into O(1/α) subsets, one substantially cleaner than the input.Clustering polynomial values handles the difficulty that good samples form a minority and may occupy an unknown cluster.Source: §1.4 · pp. 5–6
  • Theorem 1.3 outputs O(1/α) candidates, one within ℓ2-distance ˜O_d(α^-1/(2d)) of the mean, in time O(n^d/α)^O(d).It assumes an α-fraction of identity-covariance Gaussian samples and uses a sample size of O(d^2d)·n^O(d)/poly(α).Source: §1.4 · p. 5
  • For d=O(1/ε), the mean-estimation algorithm runs in polynomial time and achieves error O(α^ε), while d=Θ(log(1/α)) gives error ˜O(log^3/2(1/α)).An SQ lower bound suggests that the algorithm’s complexity is qualitatively best possible.Source: §1.4 · p. 5
  • For uniform identity-covariance mixtures, the algorithm learns parameters at accuracy δ when mean separation is at least Ω(k^ε+√log(1/δ)), with polynomial sample complexity and runtime.With d=Θ(log k), it achieves separation ˜O(log^3/2(k)+√log(1/δ)), close to the information-theoretic Ω(√log k) threshold.Source: §1.4 · p. 7
  • For equal-covariance mixtures, list-decoding produces candidate means, after which nearest-mean assignment and clustering recover the components accurately.The method first generates a small hypothesis list, then associates samples with their closest candidate mean before clustering.Source: §1.4 · p. 7
  • For arbitrary covariances, the algorithm guesses component radii, constructs a polynomial-size hypothesis list, and uses distance testing to validate clusters.The secondary test checks whether a discovered cluster contains many points at approximately the correct pairwise distance.Source: §1.4 · p. 7
  • Theorem 1.5 gives optimal error O(log(1/α)) for subgaussian distributions and O_k(α^-1/k) for bounded even-k moments, using lists of O(1/α) vectors.These bounds are information-theoretically optimal up to constants, including for N(µ, I) with polynomial-size lists and moment-bounded distributions with α-dependent list size.Source: §1.4 · pp. 7–8
  • Theorem 1.6 shows that SQ algorithms achieving Gaussian mean error O(α^-1/d) require either accuracy 2^O((1/α)^(2/d)) · n^-Ω(d) or 2^n^Ω(1) queries.Thus, achieving the minimax Gaussian bound may be computationally difficult within the SQ model.Source: §1.4 · p. 8

1.5 Related Work · 1.6 Detailed Overview of Techniques · 1.7 Organization

The paper develops efficient list-decodable mean estimation and spherical-GMM learning via higher-degree polynomial multifilters, while establishing minimax guarantees and SQ lower bounds. It builds on prior robust-estimation and GMM-learning work and organizes these results across Sections 2–5.

1.5 Related Work

  • Prior work established efficient robust learning under constant corruption rates and advanced list-decodable, sparse, optimal-error, lower-bound, supervised-learning, and practical robust methods [DKK+16, LRV16, DKS16a, CSV17, SCV17, BDLS17, DKK+17b, DKS16b, DKS17, DKK+17a].For spherical GMMs, achieved the weakest known efficient separation, while [RV17] characterized polynomial-sample separation and left efficient attainability open.Source: §1.5 · pp. 8–9

1.6.1 List-Decodable Mean Estimation

  • Multifilters address large-error list decoding by returning overlapping subsets, one substantially cleaner, when one-dimensional projections cannot identify the true component among roughly 1/α separated Gaussians.Degree-d polynomials detect displaced good points missed by variance tests on linear projections.Source: §1.6.1 · pp. 9–10
  • The algorithm searches degree-d polynomials with excessive empirical expectation or variance, using eigenvalue computations; absent such a polynomial, the sample mean is within ˜O_d(α^-1/(2d)) of the true mean.To construct multifilters, it analyzes polynomial variances through normalized homogeneous polynomials and multilinear replacements, iteratively plugging in variables to expose non-concentration.Source: §1.6.1 · p. 10

1.6.2 Learning Spherical GMMs

  • For identity-covariance mixtures, list decoding supplies hypotheses near every component mean, and nearest-hypothesis assignments cluster samples when mixture separation exceeds hypothesis error.For general spherical mixtures, nearest-neighbor distances estimate component standard deviations, enabling viable mean lists and scale-aware clustering without merging smaller components.Source: §1.6.2 · p. 11
  • Dimension reduction groups samples with approximately equal covariance and projects each group, reducing the problem to poly(k) dimensions while removing the extra n^d runtime dependence.This avoids a separation requirement proportional to log(n) caused by polynomially many candidate hypotheses.Source: §1.6.2 · p. 11

1.6.3 Minimax Error Bounds

  • An inefficient covering/packing algorithm achieves O(log(1/α)) list-decoding error for identity-covariance Gaussians and extends to O(t) under known directional tail bounds.The framework yields O(log(1/α)) for bounded-variance subgaussian distributions and O_k(α^-1/k) when the first k central moments are bounded, with matching lower bounds.Source: §1.6.3 · pp. 11–12

1.6.4 SQ Lower Bounds

  • SQ algorithms must either spend n^d time or have accuracy worse than α^-1/(2d), indicating a qualitatively tight runtime–accuracy tradeoff.The lower bound uses a one-dimensional mixture matching Gaussian moments through degree d; degree-d moments detect errors of size α^-1/d.Source: §1.6.4 · p. 12

1.7 Organization

  • The paper presents definitions and technical facts in Section 2, list decoding in Section 3, GMM learning in Section 4, and minimax and SQ bounds in Section 5.This sequence mirrors the paper’s progression from foundations and algorithms to guarantees and lower bounds.Source: §1.7 · p. 12

2 Definitions and Preliminaries

This section defines spherical Gaussians and their mixtures, formalizes list-decodable robust mean estimation and spherical-GMM parameter estimation, and introduces Hermite analysis with polynomial concentration tools.

2.1 Notation and Basic Definitions

  • Spherical Gaussians have covariance σ^2I, and spherical k-GMMs are finite mixtures of such component distributions.The section also defines Gaussian distributions and total variation distance.Source: §2.1 · p. 13

2.2 Formal Problem Definitions

  • List-decodable robust mean estimation uses α-corrupted samples to output poly(1/α) candidate means, one of which is within error g(α) of the unknown mean; the main algorithmic case is unknown-mean, known-covariance Gaussians.An α-corrupted set contains αm genuine samples and (1−α)m arbitrary adversarial points, while list-decodable learning requires one accurate hypothesis with high probability.Source: §2.2 · p. 13
  • Spherical-GMM parameter estimation returns component weights, means, and variances matched up to permutation within accuracy δ, with approximation implying total variation distance O(kδ).The required sample and computational complexity depends on the smallest component weight and minimum separation.Source: §2.2 · p. 14

2.3 Basics of Hermite Analysis and Concentration

  • Hermite polynomials form a complete orthogonal basis for L2 under the standard Gaussian, and a degree-d Chernoff bound provides concentration for degree-d polynomials evaluated on independent Gaussians.The multivariate Hermite polynomial indexed by a has degree ||a||1.Source: §2.3 · p. 14

3 List-Decodable Robust Mean Estimation Algorithm

This section presents List-Decode-Gaussian, an algorithm for list-decodable Gaussian mean estimation with polynomial-in-n and α^-1 runtime for fixed degree d. Its recursive multifiltering framework combines clustering, spectral detection, and degree-d polynomial techniques to reduce corruption or certify accurate empirical means.

Main algorithmic result

  • List-Decode-Gaussian runs in time (n^d log(1/τ)/α)^O(d) and returns O(1/α) candidates, one containing a successful estimate with probability at least 1−τ.The algorithm uses O(d!^2 · n^4d · log(1/τ)/α^7) points, including at least a 2α-fraction of independent samples from N(µ, I).Source: §3 · p. 14

Recursive framework

  • The main recursive subroutine either produces subsets with substantially fewer errors or certifies that the Gaussian mean is close to the empirical mean.Repeatedly applying this subroutine to returned sets yields the final candidate vectors.Source: §3 · p. 14

Good-set extraction

  • The algorithm first extracts O(1/α) candidate subsets from corrupted data so that, with high probability, at least one is good and suitable for further processing.Basic clustering enforces the requirement that points in a good set are not too far apart.Source: §3 · p. 15

Multifiltering

  • A multifilter detects degree-d polynomials whose empirical second moments are too large, then separates errors using polynomial values or recursively refined subsets.If no such polynomial exists, spectral arguments imply that the empirical mean is close to the true mean.Source: §3 · p. 15

Polynomial filtering machinery

  • Multilinearization and tensor-based analysis reduce difficult variance checks to linear filters, whose Gaussian variance is bounded and whose distributional discrepancies expose corrupted points.The construction uses harmonic, homogeneous, and multilinear degree-d polynomials, expressing bounded-trace quadratic polynomials as averages of squared linear polynomials.Source: §3 · pp. 15–16

3.1 Representative Sets and Good Sets

This section defines representative clean samples and good corrupted subsets for list-decodable Gaussian mean estimation. Representative sets approximate Gaussian probabilities for low-degree polynomial threshold functions, while good sets retain enough representative points and satisfy boundedness conditions.

Corruption model

  • The corruption model contains an α-fraction of independent samples from N(µ, I) and allows an adversary to add |S|(1/α −1) arbitrary points.The algorithm receives the resulting corrupted set and must output a list containing a candidate for the unknown mean µ.Source: §3.1 · p. 16

Representative Sets

  • A representative set deterministically approximates Pr[p(G) ≥0] for every real polynomial threshold function p of degree at most 2d.This condition is designed to guarantee algorithmic success on any corrupted set formed from the representative clean set.Source: §3.1 · p. 16
  • Representativeness becomes weaker as α increases or d decreases, so parameters α and d imply representativeness for any β ≥α and d′ ≤d.The parameters remain fixed throughout the algorithm, although their dependence is implicit in the definition.Source: §3.1 · pp. 16–17
  • A sufficiently large independent sample from N(µ, I) is representative with probability at least 1 −τ using O(d!2 · n4d · log(1/τ)/α6) samples.The guarantee follows from the VC-dimension of degree-at-most-2d polynomial threshold sets and the VC inequality.Source: §3.1 · p. 17

Good Sets

  • An α-good corrupted subset contains a β-fraction of points from a representative set, with β ≥α, while allowing some clean points to be removed and requiring all points to lie in a ball of radius O(√n).This notion supports the algorithm’s iterative removal of outliers from subsets of the original corrupted set.Source: §3.1 · p. 17

3.2 Naive Clustering

Naive clustering converts a contaminated sample containing at least a 2α-fraction of Gaussian samples into a short list of candidate subsets. With probability at least 1−τ, one candidate is α-good by covering concentrated samples with maximal disjoint balls.

3.2 Naive Clustering

  • Lemma 3.5 returns at most 1/α subsets, one of which is α-good with probability at least 1−τ, given at least a 2α-fraction of N(µ,I) samples.The input size is O(d!2 · n4d · log(1/τ)/α7).Source: §3.2 · p. 18
  • At least one enlarged ball contains a (1−α/6−e^-3n)-fraction of the good samples, ensuring its candidate subset is α-good.Gaussian concentration places most good samples within O(√n) of µ, while representativeness transfers this concentration to the sample set.Source: §3.2 · p. 18
  • The algorithm selects a maximal collection of disjoint radius-R balls, each containing at least an α-fraction of T, yielding at most 1/α candidates.Here R = 2C√n, and enlarged radius-3R balls define the returned subsets.Source: §3.2 · p. 18
  • The returned candidates are bounded because each candidate lies within a radius-3R ball, while maximality guarantees one candidate contains all good samples sufficiently close to µ.This establishes both the bounded-support condition and the required coverage for α-goodness.Source: §3.2 · p. 18

3.3 Main Multifilter Algorithm and Proof of Theorem 3.1

The main multifilter subroutine either returns a candidate mean, certifies that the input is not α-good, or produces a small list preserving an α-good subset. Recursively applying it yields a good mean estimate with high probability while controlling the candidate-list size and runtime.

Main Multifilter Algorithm

  • The Main Multifilter Algorithm returns a vector, “NO,” or at most two weighted subsets, preserving an α_i-good subset whenever the input is α-good.It runs in time O((d + ln(1/τ))/α)^d · poly(|T|, nd).Source: §3.3 · p. 19

Proof of Theorem 3.1

  • The full algorithm recursively applies the subroutine to clustered subsets and outputs all returned vectors, guaranteeing that one candidate is a good approximation to the true mean with probability at least 1−τ.The recursion maintains an α_i-good branch or reaches a good mean estimate across the generations of the subset tree.Source: §3.3 · pp. 19–20
  • The recursion produces O(α^-3) candidates and terminates after at most O(|T|/α^3) calls to MainSubroutine.A subsequent ListReduction step reduces the final list to O(1/α) candidates without losing more than a constant factor in the final error guarantee.Source: §3.3 · pp. 19–20
  • The algorithm’s runtime is controlled by at most |T| generations, each processing O(α^-3) subsets with the MainSubroutine.This dominates the initial clustering, final list reduction, and bookkeeping costs.Source: §3.3 · p. 20

Multifilter Condition

  • The multifilter condition requires that, when T is α-good, at least one produced subset T_i is α_i-good with respect to the Gaussian mean.This condition formalizes the invariant needed for recursive filtering.Source: §3.3 · p. 20

3.4 Basic Multifilter Routine

This section develops and analyzes a basic multifilter routine that uses degree-d polynomial tests to distinguish corrupted from good data and produce cleaner subsets. It establishes the routine's correctness, including parameter control, tail bounds, preservation of goodness, and the guarantees associated with its possible outputs.

3.4 Basic Multifilter Routine

  • A degree-d polynomial with discrepant mean or variance identifies value-based splits or trims of T, producing overlapping subsets in which at least one is cleaner.Unknown Gaussian means are handled by overlapping intervals, ensuring most good points remain together while corrupted points are preferentially removed or separated.Source: §3.4 · pp. 20–21

3.4.1 Basic Multifilter Pseudocode

  • The pseudocode returns “YES” when p(T) is sufficiently concentrated, trims points outside a suitable interval when variance is large, or creates two overlapping threshold subsets otherwise.The two cases use intervals of length L or threshold-separated sets, with updated α parameters for the returned subsets.Source: §3.4.1 · p. 22

3.4.2 First Stage of Correctness Proof

  • If T is α-good and Var[p(G)] ≤ 1, then max x,y∈T |p(x) − p(y)| ≤ O(1 + n/d)d/2; the two branching steps admit thresholds, and a single output pair satisfies α′ ≥ α.Source: §3.4.2 · pp. 23–25

3.4.3 Second Stage of Correctness Proof

  • If T is α-good, “YES” implies |E[p(G)] − E[p(T)]| ≤ O((d + C log(1/α))^(d/2) log(2 + log(1/α))), because most good points lie near E[p(G)].The proof first shows that an appropriate interval containing most p(T) values must contain the Gaussian mean after expansion by R.Source: §3.4.3 · p. 26
  • A returned single pair (T′, α′) remains α′-good whenever T is α-good.This preserves both the required good-sample fraction in T′ and the retained fraction of S.Source: §3.4.3 · p. 27
  • The proof bounds projection tails on S ∩ T by 4 exp(−(t −2R)^2/d) + 2 · α^3/(d!n^d), enabling controlled filtering.The corresponding bound on S is 2 exp(−(t −2R)^2/d) + α^3/(d!n^d).Source: §3.4.3 · p. 27
  • If the algorithm outputs “NO” because α′ > 1, then the original set T cannot have been α-good.An α′-good set would otherwise require more good points than its total size permits.Source: §3.4.3 · p. 27
  • When the algorithm returns two sets, at least one candidate (T_i, α_i) is α_i-good.The candidate containing the concentrated inlier samples is shown to satisfy the goodness conditions, with α_i ≥ α(1 + 3α/50).Source: §3.4.3 · pp. 27–28

3.5 Useful Results on Polynomials and Tensors

This section establishes the polynomial–tensor framework and a key Gaussian moment identity used by the list-decoding algorithm. It distinguishes homogeneous, harmonic, and symmetric multilinear polynomials and connects their moments through symmetric tensors.

3.5 Useful Results on Polynomials and Tensors

  • Degree-d pure multivariate polynomials correspond to symmetric order-d tensors, with homogeneous, harmonic, and symmetric multilinear notions serving different analytical roles.The framework supports tensor representations and Gaussian-weighted harmonic analysis.Source: §3.5 · p. 28

3.5.1 Definitions and Basic Facts

  • Homogeneous, harmonic, and symmetric multilinear polynomials are represented through symmetric tensors, while normalized polynomials have associated tensor norm 1.Harmonic polynomials are Gaussian-orthogonal to lower degrees, and hA preserves the tensor ℓ2-norm.Source: §3.5.1 · pp. 28–29

3.5.2 Useful Lemma on Polynomials

  • Lemma 3.24 expresses harmonic-polynomial expectations and variances under N(µ, I) using homogeneous and symmetric multilinear polynomials.This lets the list-decoding algorithm control a harmonic polynomial’s variance by applying multifilters to symmetric multilinear polynomials, whose Gaussian linear variances are mean-independent.Source: §3.5.2 · pp. 29–31

3.6 Multifilter Routine for Degree-1 and Degree-2 Homogeneous Polynomials

The multifilter routine handles normalized degree-1 polynomials directly and extends to degree-2 homogeneous polynomials with trace norm at most 1 by reducing them to degree-1 tests along eigenvectors. It returns a certified “YES”, a certified “NO”, or a list satisfying the multifilter condition.

Degree-1 homogeneous polynomials

  • For normalized degree-1 polynomials Homa(x) = aT x with ∥a∥2 = 1, BasicMultifilter applies directly because Var[aT G] = 1 independently of the unknown mean.This establishes the degree-1 base case for the routine.Source: §3.6 · p. 32

Degree-2 homogeneous polynomials

  • For degree-2 polynomials HomA(x) = xT Ax, the routine works under the weaker assumption ∥A∥∗≤1, with ∥A∥F = 1 defining the normalized case.The matrix A is symmetric, and the trace norm is the ℓ1-norm of its singular values, while the Frobenius norm is their ℓ2-norm.Source: §3.6 · p. 32

Guarantees

  • The resulting lemma guarantees that “NO” certifies T is not α-good, while a returned list {(Ti, αi)} satisfies the multifilter condition for (T, α).The routine is polynomial-time and accepts a degree-2 polynomial with ∥A∥∗≤1 together with (T, α).Source: §3.6 · p. 32

Algorithm

  • The degree-2 algorithm computes approximate eigenvalues and unit eigenvectors of A, then runs BasicMultifilter on each degree-1 polynomial viT x, stopping at the first non-YES output.If every eigenvector test returns “YES”, the algorithm returns “YES”.Source: §3.6 · p. 32

3.7 Multifilter Routine for Symmetric Multilinear Polynomials

This section develops a recursive multifilter for degree-d multilinear polynomials that either certifies bounded expectation on α-good data or produces valid filters removing bad points. Its analysis establishes the expectation bound and runtime through recursive variance control and degree-2 filtering.

3.7 Multifilter Routine for Symmetric Multilinear Polynomials

  • The multifilter returns YES, NO, or a list satisfying the multifilter condition; YES certifies expectation at most O((1 + log(1/α))log(2 + log(1/α))^2)^(d/2) on α-good data.NO certifies that T is not α-good, while list outputs satisfy the multifilter condition.Source: §3.7 · pp. 33, 36
  • The algorithm runs in time O((ln(1/τ) + d)/α)^d · poly(|T|, nd), matching the recursive number of lower-degree multifilter calls.At each degree it samples Cα^-1 ln(2d/τ) points and recursively processes normalized contractions of the polynomial.Source: §3.7 · pp. 33–34
  • The recursion fixes variables one at a time, using degree-2 multifiltering when conditioning raises variance and otherwise continuing toward the YES case.The conditioned variance is represented by a degree-2 trace-norm-1 polynomial, enabling a filter whenever variance becomes detectably large.Source: §3.7 · pp. 33–34
  • With probability at least 1 −τ/2d^2, a sampled x simultaneously witnesses the relevant linear discrepancy and satisfies q(x −µT) ≤200E[q(G −µT)].This witness supports the inductive YES-case bound while preserving the recursive normalization conditions.Source: §3.7 · p. 35

3.8 Multifilter Routine for Harmonic Polynomials

The HarmonicMultifilter algorithm extends multifiltering to all degree-d harmonic polynomials, returning a valid acceptance, rejection, or recursive filtering outcome with high probability. Its analysis combines multilinear filters with a BasicMultifilter step to control polynomial variance and establish correctness.

Multifilter Routine for Harmonic Polynomials

  • The algorithm returns “YES” only when T is α-good, “NO” only when T is not α-good, or a list satisfying the multifilter condition.These guarantees hold with probability at least 1 −τ.Source: §3.8 · p. 36
  • The routine outputs at most 1/α^2 list components and runs in time O((ln(1/τ) + d)/α)^d · poly(|T|, nd).Source: §3.8 · p. 36
  • It decomposes tensor contractions across degrees, applies MultilinearMultifilter to normalized symmetric eigen-tensors, and then invokes BasicMultifilter on a normalized harmonic polynomial.The eigenvectors used in the decomposition correspond to symmetric tensors, ensuring the multilinear subroutine’s preconditions.Source: §3.8 · p. 37
  • For α-good T, the recursive tests imply E[hA(G −µT)^2] = O((1 + log(1/α))log(2 + log(1/α))^2)^d, enabling the final variance guarantee.With β chosen sufficiently large, BasicMultifilter yields Var[hA(T −µT)] ≤ O((d + log(1/α))log(2 + log(1/α))^2)^(2d).Source: §3.8 · pp. 37–38

3.9 Putting Everything Together: Proof of Proposition 3.6

The proof combines a top-eigenvalue test over degree-d harmonic polynomials with HarmonicMultifilter: a large eigenvalue yields a filter, while its absence certifies that the empirical mean is close to the true mean. The argument uses Hermite-polynomial moments under the Gaussian component to establish the certification guarantee.

Proof of Proposition 3.6

  • The algorithm computes the largest eigenvalue of a harmonic-polynomial moment matrix and runs HarmonicMultifilter when that eigenvalue is large; otherwise it outputs the empirical mean.The matrix is O(n^d) × O(n^d), and the top eigenvector defines the harmonic polynomial supplied to the multifilter.Source: §3.9 · p. 39
  • The top eigenvector represents a normalized degree-d harmonic polynomial, and every degree-d harmonic polynomial has second moment at most λ times its coefficient norm squared.Equality holds for the polynomial defined by the top eigenvector, establishing its extremal role.Source: §3.9 · pp. 39–40
  • If HarmonicMultifilterreturns “YES” correctly, then λ = O((d + log(1/α))log(2 + log(1/α))22d).Source: §3.9 · p. 40
  • For a unit direction v, H_d(v^T(G − μ_T)) has mean (v^T(μ − μ_T))^d and variance at most 2 max{d, v^T(μ − μ_T)}^{2(d−1)}.The calculation follows from the Hermite Taylor expansion and orthogonality of its terms.Source: §3.9 · p. 40
  • Combining the eigenvalue bound with concentration inequalities shows that, when T is α-good and the algorithm outputs μ_T, the empirical mean is close to the true mean.The final implication is obtained by applying Cantelli’s and Markov’s inequalities to the Hermite polynomial in every unit direction.Source: §3.9 · pp. 40–41

4 Learning Spherical Gaussian Mixture Models

This section develops algorithms for learning spherical Gaussian mixtures, covering identity and unknown component covariances. It combines list decoding, dimension reduction, clustering, and filtering to recover mixture parameters accurately and reduce dimension dependence.

4 Learning Spherical Gaussian Mixture Models

  • The section combines identity-covariance and general spherical-mixture algorithms, with dimension reduction and final guarantees deferred to later subsections.Section 4.1 handles shared covariance, Section 4.2 handles differing spherical covariances, and Section 4.3–4.4 assemble the final guarantees.Source: §4 · p. 41

4.1 Learning Spherical GMMs: The Identity Covariance Case

  • For identity covariance, the algorithm returns component weights with error O(ε) and means with error ˜O(ε/w_i), using list-decoding, nearest-hypothesis assignment, clustering, and filtering.It tolerates an ε-corrupted distribution and succeeds with probability at least 1−τ under the proposition’s separation and parameter conditions.Source: §4.1 · pp. 41–43
  • The identity-covariance analysis shows that each true component forms exactly one hypothesis equivalence class, while incorrect hypotheses receive only exponentially few assignments.This yields correctly clustered component samples, whose weights and means can then be estimated robustly.Source: §4.1 · pp. 42–43

4.2 Learning Spherical GMMs: The General Case

  • For differing spherical covariances, the algorithm guesses radii, generates candidate means, tests radius-consistent clusters, and filters each cluster to recover weights, means, and scales.The radius list has size O(nα^-2), the candidate-mean list has size O(nα^-5), and the method separates hypotheses by scale-aware distances.Source: §4.2 · pp. 43–46
  • The general-case construction ensures every component contributes a nearby candidate and that candidate clusters correspond to distinct true means despite unknown radii.Pairwise sample distances identify radius guesses, while nearest-hypothesis assignment and radius tests retain candidates near each component.Source: §4.2 · pp. 45–46
  • Filtering isolates mostly component-i samples, allowing recovery of its mean within σ_i˜O(ε/w_i) and its covariance matrix within the corresponding Frobenius-norm error.The retained set contains a 1−O(ε/w_i) fraction of samples from the target Gaussian and only O(ε/w_i) contamination.Source: §4.2 · p. 46

4.3 Dimension Reduction

  • Dimension reduction finds an affine subspace of dimension poly(k/ε) such that every component mean lies within O(εσ_i) of its projection.The procedure uses poly(nk/ε) samples and runs in sample-polynomial time, enabling the learning algorithm to avoid the log(n) separation dependence.Source: §4.3 · pp. 46, 48

4.4 Putting Everything Together

  • The combined algorithm returns mixture weights within O(ε) and means within ˜O(ε/w_i) for components of weight at least α, with high probability.The guarantee applies when 1/2 > α > 4ε ≥ 0 and the component means satisfy the separation condition of Corollary 4.12.Source: §4.4 · p. 49

5 Minimax Error Bounds and SQ Lower Bounds

This section develops minimax error bounds and SQ lower bounds for list-decodable mean estimation across several distribution families. It combines concentration and covering arguments with matching constructions and a search-problem reduction based on separated finite distributions and bounded list size.

5.1 Minimax Error Bounds for List-Decodable Mean Estimation

  • Θ(log(1/α)) is the optimal error for N(µ, I) with lists of size poly(1/α), while bounded covariance requires Θ(α^-1/2) and matching k moments requires Θ_k(α^-1/k).The lower bounds match the corresponding upper bounds, establishing tight minimax rates across these families.Source: §5.1 · pp. 50, 52
  • The lower bounds persist for N(µ, I), even though the covariance is known, and for distributions whose first k mixed central moments match the standard Gaussian.The constructions encode many possible means while preserving the relevant distributional information; matching k moments uses a one-dimensional mixture with µ = Ω((kα)^-1/k).Source: §5.1 · pp. 50, 52, 53, 55
  • O(log(1/α)) · σ, O(α^-1/2) · σ, and O((C/α)1/k) are achievable with O(1/α) candidates for sub-Gaussian, covariance-bounded, and kth-moment-bounded distributions, respectively.These guarantees follow from a generic exponential-time algorithm: a directional concentration threshold u yields O(1/α) covering balls of radius 2u.Source: §5.1 · pp. 50–52

5.2 SQ Lower Bounds for List-Decodable Mean Estimation

  • SQ algorithms attaining error ckα^-1/k must either make at least exp(Ω(nc/2)) queries or return more than exp(Ω(n)c) hypotheses.Thus, achieving the information-theoretic rate is incompatible with simultaneously having polynomially many queries and a small list in the SQ model.Source: §5.2 · pp. 55–56
  • The SQ lower-bound construction uses a distribution matching the first k Gaussian moments with χ2(A, N(0, 1)) = exp(O(µ2)), embedded along one direction against standard Gaussian noise.The resulting n-dimensional distribution is an α-mixture of a shifted Gaussian and another distribution, enabling many candidate mean directions.Source: §5.2 · p. 56
  • The SQ reduction treats list-decoding as finding a list of at most ℓ vectors containing a hypothesis within |µ|/10 of the target.The construction uses distributions P_v indexed by pairwise correlations at most 1/2.Source: §5.2 · p. 56
  • Because distinct target means are more than |µ|/5 apart, each list element can serve at most one distribution, leaving at least |DD| − ℓ distributions unsolved.When ℓ = exp(o(n^c)), this is at least half of DD.Source: §5.2 · p. 56
  • Fewer than exp(Ω(n^{c/2})) SQ queries cannot solve the search problem with accuracy larger than exp(O(α^{-2/k}))O(n)^{k(1/4−c/2)}.This establishes the claimed SQ lower bound for list-decodable mean estimation.Source: §5.2 · p. 56

APPENDIX · A Proof of Claim 3.11

The appendix proves Claim 3.11 through a sequence of inequalities, using 1 + y ≤ e^y, and concludes the argument.

A Proof of Claim 3.11

B Reducing the List Size to O(1/α)

This section gives a polynomial-time procedure that reduces a candidate list to at most α^-1(1+O(δN)) candidates while retaining one within distance 3(β+t) of the true mean. The method retains candidates supported by sufficiently large inlier neighborhoods and removes candidates that are too close to one already retained.

List reduction guarantee

  • α^-1(1+O(δN)) candidates suffice, while one retained candidate lies within distance 3(β+t) of µ∗.Under the proposition’s assumptions, an initial list containing a β-accurate candidate can be reduced with polynomial-time computation.Source: B Reducing the List Size to O(1/α) · pp. 60–61

ListReduction algorithm

  • The algorithm examines pairwise candidate directions and retains µ_i only when its associated set T_i has size at least α(1−δN)|T| and no retained candidate is within 2(β+t).The input is a candidate list M, samples T, and parameters α, β, δ, and t; all operations run in polynomial time.Source: B Reducing the List Size to O(1/α) · pp. 60–61

Correctness argument

  • Candidates retained at pairwise distance at least 2(β+t) have disjoint associated sample sets, so their total number is bounded by the available samples.A union bound ensures the β-accurate candidate has a sufficiently large associated set, while disjointness yields the list-size bound.Source: B Reducing the List Size to O(1/α) · p. 61

Related papers

Loading 1711.07211v1…