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 asks how accurately and efficiently one can estimate a Gaussian mean from a small inlier fraction and learn spherical Gaussian mixtures under corruption. It uses high-degree multivariate polynomials and multifilters to remove outliers, obtaining list-decodable mean estimates with error ˜O_d(α^-1/(2d)) and an SQ lower bound suggesting near-optimal complexity.

  • Problem

    The paper studies unresolved information-theoretic and computationally efficient error guarantees for list-decodable Gaussian mean estimation, including the challenge that projections can resemble mixtures of 1/α widely separated Gaussians.

  • Method

    The paper uses degree-d multivariate polynomials, structural analysis under Gaussian distributions, and multifilters to remove outliers from high-dimensional datasets.

  • Results

    ˜O_d(α^-1/(2d)) error: an efficient algorithm outputs O(1/α) candidate means, one of which is close to the true Gaussian mean with high probability.

  • Takeaways & Limitations

    The techniques provide efficient list-decodable mean estimation guarantees while extending outlier removal to settings where most high-dimensional data points are corrupted.

  • Takeaways & Limitations

    An SQ lower bound suggests that the algorithm's complexity is qualitatively close to best possible, while the robust mixture setting assumes η ≪ min_i w_i.

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

The paper develops efficient algorithms for list-decodable Gaussian mean estimation and learning separated spherical Gaussian mixtures. Its polynomial-based techniques improve mean-estimation error and reduce the separation required for mixture learning, while lower bounds characterize limits on these gains.

  • Technical Approach: Degree-d multivariate polynomials enable outlier removal when the good data are a minority, exploiting the stronger effect of distant points on higher moments.Multifilters address the possibility that polynomial values form several clusters, making the good cluster unidentified directly.
  • List-Decodable Mean Estimation: O(1/α) candidates achieve ℓ2-error ˜O_d(α^-1/(2d)) for list-decodable Gaussian mean estimation.The algorithm runs in time O(n^d/α)^O(d) under the stated sample-size condition.
  • List-Decodable Mean Estimation: For d = O(1/ε), the mean-estimation algorithm runs in polynomial time and achieves error O(α^ε).
  • Computational Limits: An SQ lower bound suggests that the computational complexity of the Gaussian mean-estimation algorithm is qualitatively close to best possible.
  • Learning Separated Spherical GMMs: For uniform mixtures of k identity-covariance Gaussians, separation Ω(k^ε + √log(1/δ)) suffices for parameter accuracy δ with polynomial sample complexity and runtime.This improves on the prior polynomial-time separation requirement k^1/4 polylog(k/δ).
  • Minimax Bounds: The minimax list-decoding error is polylog(1/α) for subgaussian distributions and Θ_k(α^-1/k) under bounded even k-th moments, with matching optimality statements.The corresponding Gaussian algorithm approaches the information-theoretic bound in a higher-degree regime.

1.5 Related Work

The paper builds on robust high-dimensional estimation and Gaussian-mixture learning, addressing open information-theoretic and algorithmic gaps with polynomial-based filtering and stronger error and separation guarantees.

  • List-Decodable Mean Estimation: The algorithmic challenge in the large-error regime is that one-dimensional projections can simulate mixtures of 1/α Gaussians with widely separated means.The paper addresses this with multifilters that return several subsets, at least one substantially cleaner than the input.
  • Algorithmic Approach: The paper’s Gaussian mean-estimation algorithm outputs O(1/α) candidates and runs in time (nd log(1/τ)/α)^O(d).Its filtering framework uses polynomial discrepancies to remove outliers and recursively refine candidate subsets.
  • Minimax Error Bounds: Degree-d polynomial techniques enable an inefficient algorithm to achieve the information-theoretic error for subgaussian and bounded-moment distributions.For bounded first k moments, the matching error bound is O_k(α^-1/k).
  • Computational Lower Bounds: Statistical Query lower bounds indicate that achieving accuracy around α^-1/2d requires either nd time or weaker accuracy.This suggests a qualitative runtime–accuracy tradeoff close to the algorithm’s.

2 Definitions and Preliminaries

This section defines Gaussian and spherical-mixture models, formalizes list-decodable robust estimation and parameter estimation, and introduces Hermite-polynomial tools for later analysis.

  • Gaussian Models: A spherical Gaussian is an n-dimensional Gaussian whose covariance is σ^2·I.The Gaussian is parameterized by its mean and covariance through the standard density formula.
  • Gaussian Mixtures: A spherical k-GMM is a mixture of k spherical Gaussian components with component weights, means, and scales.The parameter-estimation task seeks these quantities up to accuracy δ, after matching components by a permutation.
  • List-Decodable Learning: List-decodable learning requires an efficient algorithm to output m hypotheses, at least one accurate with high probability.The robust mean problem applies this model to an α-corrupted sample set and seeks O(poly(1/α)) candidate means.
  • Problem Scope: The main algorithmic setting is unknown-mean, known-covariance Gaussian learning, while minimax bounds extend to broader distribution families.The paper also studies parameter estimation for separated spherical Gaussian mixtures.
  • Hermite Analysis: Hermite polynomials form a complete orthogonal basis for square-integrable functions under the standard Gaussian distribution.Multivariate Hermite polynomials are products of univariate Hermite polynomials, with degree given by the sum of coordinate degrees.
  • Polynomial Concentration: A degree-d polynomial concentration bound provides the technical basis for controlling polynomial behavior on Gaussian samples.The section records this as a standard degree-d Chernoff bound.

3 List-Decodable Robust Mean Estimation Algorithm

The mean-estimation algorithm recursively uses polynomial-based multifilters to remove outliers or certify that the empirical mean is close to the true mean.

  • Main Guarantee: Theorem 3.1 gives a list-decodable Gaussian algorithm that returns O(1/α) candidates with runtime (nd log(1/τ)/α)^O(d).It operates when at least a 2α-fraction of the input points are independent samples from N(µ,I).
  • Recursive Filtering: The recursive subroutine either produces cleaner subsets or certifies that the Gaussian mean is close to the empirical mean.Repeated application to returned subsets yields the final candidate vectors.
  • Multifilters: Multifilters cluster polynomial values and remove points far from sufficiently large clusters, or split the dataset into overlapping subsets.At least one resulting subset is intended to contain substantially fewer errors.
  • Polynomial Detection: The algorithm first identifies degree-d polynomials whose empirical second moments are too large relative to a Gaussian model.If no such polynomial exists, the empirical and true means are close; otherwise, the algorithm constructs a multifilter.
  • Multilinear Reduction: The method converts homogeneous polynomials into multilinear forms to verify whether evaluations at the unknown mean are large.Large multilinear evaluations imply that random tuples of samples can expose discrepancies for filtering.
  • Algebraic Tools: The polynomial machinery uses harmonic, homogeneous, and multilinear polynomials together with tensor and spectral techniques.These components are combined to obtain the full filtering procedure.

3.1 Representative Sets and Good Sets

Representative sets model clean Gaussian samples through low-degree polynomial tests, while good sets embed such representatives within bounded corrupted datasets.

  • Corruption Model: The corruption model supplies an α-fraction of independent Gaussian samples and allows an adversary to add the remaining points arbitrarily.The algorithm must produce a list containing a candidate close to the unknown mean.
  • Representative Sets: A representative set approximately matches Gaussian probabilities for threshold events defined by degree-at-most-2d polynomials.This deterministic condition is used to guarantee algorithmic success on corrupted inputs.
  • Parameter Dependence: Representativeness becomes a weaker requirement when α increases or d decreases.A set representative for parameters α and d remains representative for β≥α and d′≤d.
  • Representative Sets: For sufficiently many independent samples, representativeness holds with high probability.The required sample size is O(d!^2·n^4d·log(1/τ)/α^6).
  • Good Sets: A good set contains a representative subset of clean Gaussian samples and also requires its points to remain within a bounded-radius region.These conditions support repeated outlier removal during the algorithm.

3.2 Naive Clustering

Naive clustering partitions the corrupted set into at most 1/α candidate subsets using dense, separated balls, guaranteeing that one subset is α-good with high probability.

  • Lemma 3.5 returns at most 1/α subsets, one of which is α-good with probability at least 1−τ.The input contains at least a 2α-fraction of independent samples from N(µ, I).
  • The method handles sets that are not already contained in a single O(√n)-radius ball by finding at most 1/α such balls.At least one ball contains a (1−α/6−e^(-3n))-fraction of the clean samples.
  • It constructs a maximal collection of disjoint radius-R balls, each containing at least an α-fraction of T, then expands them to radius 3R.Here R = 2C√n, while the expanded balls have radius 6C√n.
  • The procedure is given as a direct clustering algorithm that scans T and returns the resulting list of subsets.A new center is added only when it has α|T| nearby points and is not within 3R of an existing center.
  • The resulting subsets contain all points of T inside the expanded balls and are therefore bounded within radius 3R of their centers.Maximality ensures that a ball around a clean point intersects one selected ball, placing most clean samples in the corresponding expanded subset.

3.3 Main Multifilter Algorithm and Proof of Theorem 3.1

The main multifilter algorithm recursively either estimates the Gaussian mean or splits corrupted data into cleaner subsets, while controlling list size, termination, and runtime.

  • MainSubroutine returns a vector, “NO”, or at most two weighted subsets satisfying the multifilter condition.With probability at least 1−τ, these outputs respectively provide an estimate, certify non-goodness, or preserve an α_i-good subset.
  • The algorithm runs in time O(((d + ln(1/τ))/α)^d · poly(|T|, nd)).
  • The algorithm recursively processes the subsets produced by MainSubroutine and collects every vector it returns as a candidate hypothesis.ListReduction later reduces the candidate list without more than a constant-factor loss in final error.
  • The procedure terminates after at most O(|T|/α^3) calls to MainSubroutine.There are at most O(α^-3) active terms, and each iteration either increases their number or removes at least one point from a subset.
  • With probability at least 1−τ, every stage either retains an α_i-good subset or has already produced a good approximation to µ.The proof tracks descendants of subsets in a generation tree.

3.4 Basic Multifilter Routine

The basic multifilter uses a low-variance degree-d polynomial to test whether corrupted data behaves like the Gaussian and, when it does not, split or trim the data to increase cleanliness.

  • A degree-d polynomial whose mean or variance differs substantially on T and G provides a basis for splitting T into cleaner subsets.The split is performed according to the polynomial values on the data.
  • When Var[p(G)] is small, most clean polynomial values lie in an interval of length log(1/α)^O(d).This concentration enables removal of points outside a suitable threshold.
  • If no short interval captures nearly all of T, overlapping intervals split T so that one retains most clean points while limiting retained corrupted points.The overlap protects against the unknown location of E[p(G)].
  • BasicMultifilter returns “YES” when T has controlled polynomial variance, “NO” when T cannot be α-good, or one or two reweighted subsets.Its input promise is Var[p(G)] ≤ 1 whenever T is α-good.
  • The threshold-search steps are correct: suitable thresholds exist in both the concentrated and split cases.These are established by Lemmas 3.10 and 3.12.
  • If “YES” is returned, |E[p(G)]−E[p(T)]| is at most O((d + C log(1/α))^(d/2) log(2 + log(1/α))).
  • For a good T, the routine preserves a large clean fraction, keeps α′ at least α for a single output, and preserves goodness after filtering.The supporting guarantees include concentration around E[p(G)] and correctness of the single-subset output.

3.5 Useful Results on Polynomials and Tensors

This section develops the polynomial and tensor framework used by the algorithm, including homogeneous, multilinear, harmonic, and normalized polynomials and their Gaussian moment identities.

  • Polynomial classes: Degree-d homogeneous polynomials correspond to symmetric order-d tensors through evaluation on repeated copies of x.
  • Polynomial classes: Harmonic degree-d polynomials are orthogonal under the standard Gaussian inner product to all polynomials of lower degree.They are equivalently linear combinations of degree-d multivariate Hermite polynomials.
  • Polynomial classes: Symmetric multilinear polynomials are multilinear in d vector arguments and are represented by symmetric order-d tensors.
  • Normalization: For a harmonic polynomial h_A, the Gaussian 2-norm equals the tensor norm, and positive-degree harmonic polynomials have zero standard-Gaussian mean.A polynomial is normalized when its associated tensor has norm 1.
  • Gaussian identities: Lemma 3.24 expresses the mean and variance of harmonic polynomials under N(µ, I) using tensor contractions and lower-degree harmonic components.The mean satisfies d!·E[h_A(X)] = Hom_A(µ).
  • Gaussian identities: The moment identities follow by Taylor expanding h_A(Y+µ), applying directional derivatives, and using orthogonality to eliminate cross-terms.

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

The routine extends multifiltering from normalized linear polynomials to degree-2 homogeneous polynomials with trace norm at most one. It returns a certified YES, NO, or multifilter list.

  • Degree-1 case: Degree-1 homogeneous polynomials have variance one under the Gaussian, so BasicMultifilter applies directly.For Homa(x)=a^T x with ||a||_2=1, Var[a^T G]=1 independently of the unknown mean.
  • Degree-2 case: Degree-2 inputs have the form x^T A x with symmetric A and ||A||_*≤1, a weaker condition than Frobenius normalization.The trace norm is the ℓ1-norm of the singular values and satisfies ||A||_*≥||A||_F.
  • Guarantees: A YES output certifies the required degree-2 condition when T is α-good, while NO certifies that T is not α-good.A returned list satisfies the multifilter condition for (T, α).
  • Algorithm: The algorithm eigendecomposes A and runs BasicMultifilter on each eigenvector projection v_i^T x.It returns NO or a list as soon as one projection produces that output; otherwise it returns YES.

3.7 Multifilter Routine for Symmetric Multilinear Polynomials

The symmetric multilinear multifilter recursively tests conditional variance and mean behavior, using degree-2 multifilters to detect problematic restrictions. Its outputs are correct, with runtime exponential in degree and polynomial in the input size.

  • Purpose: The routine either verifies that the polynomial behaves similarly on good and input samples or finds a filter removing bad points.This is the central multifilter objective for degree-d multilinear polynomials.
  • Guarantees: If the algorithm returns NO, T is not α-good; if it returns a list, the list satisfies the multifilter condition.These correctness guarantees hold alongside the YES-case bound on the good distribution.
  • Recursive mechanism: Fixing one coordinate turns the remaining variance into a degree-2 trace-norm-1 polynomial, enabling recursive filtering.If fixing a coordinate substantially increases variance, the degree-2 multifilter produces a filter.
  • Recursive mechanism: The algorithm recursively fixes variables, samples candidate restrictions, and returns YES only when no detectable variance or mean problem appears.At degree one it invokes BasicMultifilter; otherwise it computes q(x)=||A(x−µ_T)||_2^2 and recurses.
  • Complexity: O((ln(1/τ)+d)/α)^d calls and O((ln(1/τ)+d)/α)^d · poly(|T|, n^d) time characterize the recursive cost.The call bound follows from repeated sampling and recursive precision reduction.
  • Guarantees: For α-good T, a YES output yields |E[A(G_1−µ_T,...,G_d−µ_T)]|=O((1+log(1/α))log(2+log(1/α))^2)^{d/2}.The guarantee is stated for independent Gaussian copies G_i.

3.8 Multifilter Routine for Harmonic Polynomials

The harmonic-polynomial multifilter decomposes higher-degree tests into symmetric multilinear components, recursively filters those components, and then applies a normalized BasicMultifilter. It provides correctness and variance bounds for α-good datasets.

  • Construction: The routine decomposes harmonic-polynomial structure across degrees d′ and applies MultilinearMultifilter to the resulting symmetric tensors.The decomposition uses eigendecompositions of matrices formed from the tensor contractions.
  • Guarantees: A returned NO certifies that T is not α-good, while a returned list satisfies the multifilter condition for (T, α).These are the corresponding non-YES guarantees of the harmonic routine.
  • Complexity: The total runtime is O((ln(1/τ)+d)/α)^d · poly(|T|, n^d), with at most 1/α^2 total list mass.This combines the recursive multilinear filtering cost with the harmonic decomposition.
  • Confidence and cost: At most d n^d recursive calls plus one external call are combined by a union bound to obtain overall confidence at least 1−τ.The recursive calls use failure probability τ/(d n^d).
  • Variance control: If T is α-good and the recursive calls return YES, E[h_A(G−µ_T)^2]=O((1+log(1/α))log(2+log(1/α))^2)^d.This bound controls the Gaussian-side variance before the final BasicMultifilter step.
  • Final filtering: The final normalized BasicMultifilter yields bounds on both Var[h_A(T−µ_T)] and the expectation gap between G and T.The stated bounds depend on d and log(1/α).

3.9 Putting Everything Together: Proof of Proposition 3.6

The proof of Proposition 3.6 constructs a degree-d harmonic polynomial from the top eigenvector of an empirical moment matrix, filters it, and outputs the empirical mean when no filter is needed. The resulting procedure is correct for α-good datasets.

  • Polynomial selection: The method searches for a degree-d harmonic polynomial with large empirical second moment using the top eigenvalue and eigenvector of an O(n^d)×O(n^d) matrix.The associated polynomial is represented as h_A(x)=v_*^T P_{n,d}(x).
  • Main subroutine: It runs HarmonicMultifilter on the selected polynomial and returns its NO or list output; otherwise it outputs µ_T.This is the main algorithmic flow of MainSubroutine.
  • Spectral argument: Every degree-d harmonic polynomial has empirical second moment at most λ||B||_2^2, with equality for the selected polynomial h_A.Thus the top eigenvalue controls the largest tested harmonic-polynomial moment.
  • Mean recovery: For a unit vector v, the Hermite polynomial H_d(v^T(G−µ_T)) has mean (v^T(µ−µ_T))^d and controlled variance.This links the selected polynomial’s behavior to the displacement between the Gaussian mean and empirical mean.
  • Conclusion: When T is α-good and the routine returns µ_T, the resulting mean-estimation guarantee holds simultaneously for all unit vectors v.The proof concludes the proposition from the harmonic-polynomial bound and the Hermite analysis.

4 Learning Spherical Gaussian Mixture Models

The section develops algorithms for learning spherical Gaussian mixtures, first for identity covariance and then for general spherical covariances, using list-decoded mean hypotheses, association and filtering, and dimension reduction. The resulting procedures estimate component weights, means, and scales under separation and corruption conditions.

  • Robustness and guarantees: The overall approach remains robust to a small constant fraction of corrupted samples while learning spherical Gaussian mixture parameters under the stated separation assumptions.The identity-covariance treatment explicitly incorporates a distribution X=(1−ε)M+εY.
  • Identity covariance: O(ε) weight error and ˜O(ε/w_i) mean error are achieved for identity-covariance mixtures with component weights at least α and sufficiently separated means.The algorithm uses polynomially many samples and runs in degree-dependent sample-polynomial time.
  • Identity covariance: The identity-covariance algorithm converts list-decoded mean hypotheses into component estimates by associating each sample with its nearest hypothesis and clustering these assignments.The procedure then runs robust Gaussian mean estimation on each cluster.
  • Identity covariance: The association analysis shows that all but an exp(−Ω(S^2)) fraction of samples from each component are assigned to hypotheses within S/20 of that component mean.This concentration makes the induced clusters correspond to individual mixture components.
  • General spherical covariance: For unknown spherical covariances, the algorithm outputs weights, means, and scales with weight error O(ε), normalized mean error ˜O(ε/w_i), and normalized scale error of order ˜O(ε/w_i)/√n.The method first identifies hypotheses with comparable scales and groups them into component-associated classes.
  • Dimension reduction: Dimension reduction finds an affine subspace of dimension poly(k/ε) whose projection preserves each component mean up to O(εσ_i), enabling the general learning guarantees.After projection, the identity-covariance procedure can be applied in the reduced dimension.

5 Minimax Error Bounds and SQ Lower Bounds

This section characterizes the information-theoretic error of list-decodable mean estimation across distribution families and establishes Statistical Query barriers for achieving these rates efficiently. It also gives matching upper and lower bounds for Gaussian, sub-Gaussian, bounded-covariance, and bounded-moment settings.

  • Problem and approach: The central question is the smallest error achievable with O(1/α) or poly(1/α) candidate means when fewer than half the samples are genuine.The section seeks bounds independent of computational and sample complexity.
  • Matching bounds: The information-theoretically optimal error is Θ(1/√α) for bounded covariance and Θ_k(α^−1/k) when the first k central moments are bounded.The section states matching upper and lower bounds for these regimes.
  • Upper bounds: An exponential-time covering algorithm gives O(1/α) candidates with error at most 2u whenever every one-dimensional projection has tail probability at most α/20 beyond u.The proof covers the feasible hypothesis set by balls of radius 2u.
  • Upper bounds: The resulting upper bounds apply to sub-Gaussian, bounded-covariance, and bounded-kth-moment families through their corresponding concentration inequalities.For bounded kth central moments, the stated error is O((C/α)^(1/k)).
  • Gaussian bounds: For Gaussian means with polynomial-size lists, the lower bound is logarithmic in 1/α, and the paper strengthens prior lower-bound results to the identity-covariance Gaussian setting.The cited passages state an Ω(log(1/α)) lower bound for N(µ,I).
  • SQ lower bounds: Any Statistical Query algorithm targeting error c_kα^−1/k must either use exp(Ω(n^(c/2))) queries or return more than exp(Ω(n^c)) hypotheses.This establishes a computational barrier for efficient SQ list decoding.

A Proof of Claim 3.11

The proof section records a sequence of inequalities used to establish the claim, followed by the statement that the proof is complete.

  • Proof: The proof uses a sequence of inequalities to establish the preceding claim.The displayed integral inequality is part of that sequence.
  • Proof: The section concludes immediately after the inequalities with the statement that the proof is complete.

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

The list-reduction procedure filters candidate means using directional sample consistency and separation, producing a shorter list while preserving a candidate near the true mean. Its output has size approximately 1/α and contains a point within 3(β+t) of the target.

  • Guarantee: A candidate retained in the reduced list is within 3(β+t) of the true mean when the original list contains a candidate within β.This guarantee follows from the directional concentration assumption on the representative sample subset.
  • Guarantee: The reduced list has size at most α^−1(1+O(δ_N)) when δ_N=o(1).The bound follows because sufficiently separated candidate neighborhoods have disjoint supporting sample sets.
  • Gaussian application: For Gaussian applications, choosing δ=1/(C log(1/α)) and t=log(C log(1/α)) yields a value of t smaller than β in the intended applications.
  • List reduction: The procedure constructs candidate-specific sample sets and uses pairwise directions between hypotheses to test whether candidates are compatible with the data.The directions are normalized differences between candidate means.
Loading 1711.07211v1…