PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

arXiv:1611.03473v2cs.LGcs.CCcs.DScs.ITmath.ST

TL;DR

The paper asks whether Gaussian learning and testing problems remain computationally difficult for Statistical Query algorithms even when their sample complexity is manageable. It develops a unified moment-matching technique to construct hard instances and proves super-polynomial SQ gaps, nearly quadratic estimation tradeoffs, and a linear-dimensional robust-testing sample lower bound.

  • Problem

    Existing results establish sample-complexity behavior for Gaussian learning, but computational lower bounds in the unsupervised setting are comparatively scarce.

  • Method

    The paper uses a unified moment-matching technique to construct explicit hard instances and derive SQ lower bounds for Gaussian estimation and testing problems.

  • Results

    The paper proves super-polynomial SQ gaps for GMM and robust Gaussian learning, nearly quadratic SQ tradeoffs for robust covariance and sparse mean estimation, and a linear-dimensional sample lower bound for robust Gaussian testing.

  • Takeaways & Limitations

    The results explain observed statistical–computational gaps and show that robustness makes Gaussian testing information-theoretically harder.

  • Takeaways & Limitations

    The SQ lower bounds concern running time rather than sample complexity, and the robust-learning characterization distinguishes the standard agnostic model from Huber contamination.

Abstract

from arXiv · show

We describe a general technique that yields the first {\em Statistical Query lower bounds} for a range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the problems of (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown Gaussian distribution. For each of these problems, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the computational complexity of {\em any} Statistical Query algorithm for the problem. Our SQ lower bound for Problem (1) is qualitatively matched by known learning algorithms for GMMs. Our lower bound for Problem (2) implies that the accuracy of the robust learning algorithm in~\cite{DiakonikolasKKLMS16} is essentially best possible among all polynomial-time SQ algorithms. Our SQ lower bounds are attained via a unified moment-matching technique that is useful in other contexts and may be of broader interest. Our technique yields nearly-tight lower bounds for a number of related unsupervised estimation problems. Specifically, for the problems of (3) robust covariance estimation in spectral norm, and (4) robust sparse mean estimation, we establish a quadratic {\em statistical--computational tradeoff} for SQ algorithms, matching known upper bounds. Finally, our technique can be used to obtain tight sample complexity lower bounds for high-dimensional {\em testing} problems. Specifically, for the classical problem of robustly {\em testing} an unknown mean (known covariance) Gaussian, our technique implies an information-theoretic sample lower bound that scales {\em linearly} in the dimension. Our sample lower bound matches the sample complexity of the corresponding robust {\em learning} problem and separates the sample complexity of robust testing from standard (non-robust) testing.

1 Introduction

The paper develops a unified moment-matching technique for Statistical Query lower bounds across Gaussian learning, estimation, and testing problems. It establishes super-polynomial SQ computational gaps for GMM and robust Gaussian learning, nearly quadratic tradeoffs for robust estimation, and linear-dimensional sample lower bounds for robust testing.

  • Contributions: The paper introduces a general moment-matching technique yielding the first SQ lower bounds for several high-dimensional Gaussian learning problems.The technique constructs hard instances and applies across learning, estimation, and testing settings.
  • Related estimation problems: Robust spectral covariance and sparse mean estimation exhibit nearly quadratic statistical–computational tradeoffs for SQ algorithms, matching known upper bounds.The sparse-mean theorem gives a representative lower bound of nΩ(ckc) queries under its stated contamination and sparsity conditions.
  • Robust testing: Robust testing of an unknown Gaussian mean requires an information-theoretic sample lower bound linear in dimension, unlike corresponding non-robust testing.This lower bound matches robust learning’s sample complexity, while the paper emphasizes that the SQ running-time bounds do not lower-bound sample complexity.
  • GMM learning: GMM learning has sample complexity Θ(k · log n) on nearly non-overlapping instances, but every SQ algorithm requires runtime at least nΩ(k).The corresponding formal lower bound is 2nΩ(1) ≥ nΩ(k) queries at precision n−O(k).
  • Robust Gaussian learning: Robustly learning an unknown-mean Gaussian to accuracy O(ǫ) requires SQ complexity nΩ(log1/4(1/ǫ)), despite information-theoretically sufficient sample complexity O(n/ǫ2).The stated theorem gives a more detailed accuracy and precision tradeoff for total variation error O(ǫ log(1/ǫ)1/2−c).
  • Robust Gaussian learning: The robust-learning lower bound implies that the O(ǫ log(1/ǫ)) error guarantee of the cited algorithm is best possible among polynomial-time SQ algorithms.The paper also gives an SQ algorithm with qualitatively matching quasi-polynomial complexity.

2 Definitions and Preliminaries

The paper formalizes Gaussian and Gaussian-mixture distributions, the learning and robust-testing problems studied, and the Statistical Query framework used for lower bounds.

  • Gaussian models: A k-GMM is a distribution on R^n formed from k Gaussian components, while proper learning additionally requires the hypothesis to be a k-GMM.
  • Learning problems: Robust learning receives a distribution within ϵ total variation distance of an unknown Gaussian and must output a hypothesis close to that Gaussian.
  • Learning problems: The lower bounds cover unknown-mean and unknown-covariance cases, with the latter applying even to spectral-norm learning.
  • Testing problems: Robust testing distinguishes a standard Gaussian from a contaminated shifted Gaussian, while spherical-GMM testing distinguishes the standard Gaussian from a separated two-component mixture.
  • Statistical Query framework: SQ algorithms query approximate expectations of bounded functions through STAT or VSTAT oracles instead of directly accessing samples.
  • Statistical Query framework: The Statistical Query dimension measures the size of a suitably correlated family of distributions and yields lower bounds on SQ query complexity.

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

The lower-bound framework hides a one-dimensional moment-matched perturbation in an unknown high-dimensional direction, making many candidate distributions difficult for SQ algorithms to distinguish.

  • High-dimensional construction: The construction replaces one direction of a standard Gaussian with a one-dimensional density A while retaining standard Gaussian structure orthogonally.
  • One-dimensional ingredient: A matches the first m moments of N(0,1) and has finite χ2-divergence from it, supplying the moment-matching condition required by the framework.
  • Lower-bound consequence: 2^Ω(n^(c/2)) SQ queries are required for accurate recovery of the hidden-direction distribution, and this is at least n^(m+1) under the stated dimension condition.
  • Correlation analysis: The proof controls pairwise correlations using projections, Hermite expansions, and the eigenvalue relation U_θ(He_iG)(x) = cos^i(θ)He_i(x)G(x).
  • Statistical Query dimension: A packing of 2^Ω(n^c) nearly orthogonal unit vectors creates a large correlated family to which the SQ-dimension lower-bound lemma applies.

4 SQ Lower Bound for Learning Gaussian Mixtures

The paper constructs Gaussian-mixture instances whose components are well separated yet moment-matched with a standard Gaussian, yielding super-polynomial SQ lower bounds for learning.

  • Main lower bound: Any SQ algorithm learning a k-GMM to constant accuracy requires 2^(Ω(n^(1/8))) ≥ n^(2k) STAT queries under the theorem’s dimension and conditioning assumptions.
  • Component separation: The components satisfy dTV(A_i,A_j) ≥ 1−ϵ for every distinct pair, so the hardness does not rely on substantial component overlap.
  • Divergence control: The construction controls χ2(A,N(0,1)) by exp(O(k)) log(1/ϵ), preserving the finite-divergence condition needed for the SQ analysis.
  • Moment matching: The hard mixture is built from k Gaussian components with positive variance, matching the first 2k−1 moments of N(0,1).
  • Parameter choice: Choosing δ = C/(k^2 log^2(k + 1/ϵ)) simultaneously supports moment matching, component separation, and high-dimensional total-variation separation.

5 SQ Lower Bounds for Robust Learning of a Gaussian

The paper proves super-polynomial SQ lower bounds for robustly learning high-dimensional Gaussians, covering unknown means and unknown covariances. The construction uses moment-matching distributions, yielding explicit query lower bounds for robust Gaussian learning.

  • Unknown mean: 2^{Ω(n^{1/12})} ≥ n^M STAT queries are required to robustly learn an unknown-mean spherical Gaussian to total variation error O(ε log(1/ε)^{1/2}/M^2).The result assumes n ≥ log(1/ε)^{Ω(1)} and M = O(log^{1/2}(1/ε)).
  • Moment matching: A one-dimensional distribution A is constructed to match the first m moments of N(0,1), remain close in total variation to a shifted Gaussian, and satisfy χ2(A,N(0,1)) = O(δ).The perturbation is represented using scaled Legendre polynomials, whose coefficient bounds control its L1 and L∞ norms.
  • Lower-bound framework: The SQ lower bounds follow by combining the moment-matching construction with the Section 3 framework and a family of high-dimensional distributions indexed by directions.For separated unit vectors, total variation distance is lower-bounded using the triangle inequality and Gaussian mean separation.
  • Unknown covariance: 2^{n^{2/15}} ≥ n^M STAT queries are required to robustly estimate an unknown covariance Gaussian in spectral norm.The input is ε-close in total variation to N(0,Σ), with I/2 ⪯ Σ ⪯ 2I, and the target error is O(ε log(1/ε)/M^4).

6 Statistical and Computational Tradeoffs

The paper establishes statistical–computational tradeoffs for robust covariance and sparse mean estimation. Its SQ lower bounds are nearly quadratic relative to information-theoretic sample complexity and apply in robust contamination settings.

  • Robust covariance estimation: Ω(n^{2−c}) samples are required by efficient SQ algorithms to approximate a corrupted Gaussian covariance within a factor of 2.The lower bound applies even under the weaker Huber contamination model, while the information-theoretic optimum is Θ(n) samples.
  • Tradeoff: The covariance and sparse-mean lower bounds establish nearly quadratic gaps between efficient and inefficient SQ algorithms, matching known information-theoretic scales.The covariance optimum is Θ(n) samples, while the sparse-mean optimum is Θ(k log n) samples.
  • Robust sparse mean estimation: Ω(n^{ck^c/8}) SQ queries are required to estimate a k-sparse Gaussian mean to ℓ2 error ε/2 under contamination rate δ = ε/k^{c/4}.The bound holds for arbitrary noise distributions and applies to STAT and VSTAT query models.
  • Robust sparse mean estimation: A set of ⌊n^c k^c/8⌋ k-sparse unit vectors can be chosen so every distinct pair has inner product at most 2k^{c−1}.This packing supplies the separated directions needed by the SQ lower-bound framework.

7 Sample Complexity Lower Bounds for High–Dimensional Testing

The paper derives information-theoretic sample lower bounds for robust and non-robust high-dimensional testing. Robustly testing an unknown Gaussian mean requires samples linear in dimension, separating it from standard testing complexity.

  • Robust unknown-mean testing: Ω(n) samples are necessary to robustly test whether an unknown-mean identity-covariance Gaussian has zero mean or mean norm at least ε.The result applies when the contamination rate is δ = ε/100 and the noise distribution is spherical Gaussian.
  • Consequences: The robust mean-testing lower bound scales linearly with dimension and matches the sample complexity of the corresponding robust learning problem.The paper states that this separates robust testing from standard non-robust testing.
  • Robust unknown-mean testing: Ω(n^{1−c}) samples are necessary when the contamination rate is δ = ε/n^{c/4}.This is the corresponding lower bound for the alternative robust-testing regime.
  • Testing GMMs: Ω(n/ε^2) samples are necessary to distinguish N(0,I) from a two-component identity-covariance Gaussian mixture at total variation distance at least ε.The testing guarantee is required with probability at least 2/3.

8 SQ Algorithms for Robustly Learning and Testing a Gaussian

This section develops a unified moment-matching framework for robust SQ testing and learning of high-dimensional Gaussians. It gives SQ and sample-access algorithms with explicit query, precision, sample, and runtime guarantees.

  • 8.1 One-Dimensional Moment Matching Lemma: Moment matching underlies the section’s structural result and the subsequent robust testing and learning algorithms.The section is organized around a structural result, followed by robust testing and robust learning.
  • 8.1 One-Dimensional Moment Matching Lemma: k = 2⌈O(ε log(1/ε)/δ)⌉ moments suffice to force dTV(G, G′) = O(δ) for an ε-noisy one-dimensional Gaussian G′.Lemma 8.1 establishes the relationship between approximate moment matching and total variation distance.
  • 8.1 One-Dimensional Moment Matching Lemma: The proof separates large and small Gaussian means, using mean and variance for μ ≥ 1 and a sinusoidal Taylor-polynomial test for μ ≤ 1.For small means, the expectation gap is lower-bounded while approximate moment matching upper-bounds the same quantity, yielding a contradiction.
  • 8.2 Robust Testing Algorithm: The robust testing algorithm makes O(nk) SQ queries at precision ε·O(n log(n/ε)^2)^−k, runs in time n^O(k), and distinguishes N(0,I) from distributions δ-far from it.Here k = 2⌈O(ε log(1/ε)/δ)⌉ and δ is at least a sufficiently large constant multiple of ε.
  • 8.2 Robust Testing Algorithm: The corresponding sample algorithm uses at most (n log(1/ε))^O(k)/ε^2 samples and succeeds with probability 9/10.It is obtained by simulating the statistical queries with samples.
  • 8.3 Robust Learning Algorithm: The robust learning algorithm estimates the mean of an ε-noisy N(μ,I) to error O(ε), using SQ complexity n^O(√(ε log(1/ε))) and a sample-access corollary.The SQ guarantee applies when ||μ||₂ ≤ poly(n, ε); the sample version succeeds with probability 9/10.
  • 8.3 Robust Learning Algorithm: The filtering algorithms can be implemented as SQ algorithms by replacing expectations over retained samples with conditional expectations given previous filters accepting.This establishes an SQ implementation of the robust learning procedure’s filtering operations.

A Sample Complexity Upper Bound for Learning GMMs

This section proves that learning an n-dimensional k-component Gaussian mixture is information-theoretically achievable in total variation distance. The construction is exhaustive and therefore not computationally efficient.

  • Sample Complexity Upper Bound: O(n^2k^3 log^2(k)/ε^5) samples suffice to return a distribution Q with dTV(P,Q) < ε with probability at least 2/3.The guarantee applies to any k-mixture P of n-dimensional Gaussians.
  • Algorithm: The algorithm guesses component assignments for samples, approximates each component and the mixture weights, and uses a tournament to select among candidates.A correct assignment guess yields independent samples from the appropriate Gaussian components.
  • Single-Gaussian Estimation: O(n^2/δ^2) samples from a single Gaussian suffice for a polynomial-time approximation within total variation δ with probability at least 2/3.The success probability can be amplified at an additional logarithmic sample cost.
  • Single-Gaussian Estimation: With M samples, the single-Gaussian estimator achieves dTV(G,P) < ε with probability at least 1 − exp(−Ω(Mε^2/d^2)).This amplified guarantee is used when approximating individual mixture components.
  • Candidate Generation: An exhaustive candidate generator uses Θ(n^2k^3 log(k)/ε^3) samples and returns exp(O(n^2k^3 log^2(k)/ε^3)) candidates, one ε-close with probability at least 2/3.Candidates correspond to functions assigning each sample to one of the k components.

B Sample Complexity Upper Bound for Parameter Estimation of Separated GMMs

This section shows that separated Gaussian mixtures can be parameter-estimated from a distribution-level approximation. A weighted-Gaussian distance with an approximate triangle inequality enables component matching under strong separation.

  • Parameter Estimation Problem: Parameter estimation seeks a mixture Q whose individual weighted-Gaussian components are close to those of P, rather than only matching P in total variation.Without separation, mixtures can be close in variation distance while their individual components remain far apart.
  • Component Matching: Under separation, each component Gi has at most one component Hj with h(Gi,Hj) > (δ/k)^C.This uniqueness result is the key combinatorial step for matching components.
  • Component Matching: If dTV(p,q) < (δ/k)^C and within-mixture component overlaps are below (δ/k)^C, a permutation π matches every Gi to Hπ(i) with ||Gi − Hπ(i)||1 < δ.The mixtures are normalized, and C is a constant under the theorem’s separation assumptions.
  • Distance Between Weighted Gaussians: The weighted-Gaussian distance hΣ is introduced because it satisfies an approximate triangle inequality, unlike the basic Gaussian distance h.This property supports reasoning about component overlaps through an intermediate representation.
  • Proof of the Matching Guarantee: The proof controls covariance mismatch through eigenvalue bounds and combines this with mean and overlap comparisons to establish the approximate triangle inequality.The covariance analyses include eigenvalue comparisons for products of symmetric matrices.

C Testing the Mean of a High-Dimensional Gaussian

This section studies testing whether a high-dimensional Gaussian has zero mean or mean norm exceeding ε. It gives a tester using O(√n/ε^2) samples and proves a matching lower bound up to constants.

  • Upper Bound: k = O(√n/ε^2) samples suffice for a tester distinguishing μ = 0 from ||μ||₂ > ε with probability at least 2/3.The tester is based on the squared norm of an aggregate of independent samples.
  • Upper Bound: The tester compares a squared-norm statistic against a threshold near n + ε^2k/2, accepting the zero-mean case and rejecting otherwise.Under zero mean the statistic has mean n and variance O(n); under ||μ||₂ > ε its mean increases by k||μ||₂^2.
  • SQ Implementation: The tester can be implemented in the SQ model by checking whether each coordinate-wise median has absolute value below ε/√n.The coordinate-wise condition can be expressed through probabilities such as Pr(x_i > 0) = 1/2 + O(ε/√n).
  • Lower Bound: Ω(√n/ε^2) samples are necessary to distinguish the two mean cases with probability at least 2/3.The lower bound uses a random mean prior whose induced sample distribution remains close to the zero-mean sample distribution.
  • Lower Bound: The lower-bound construction makes the distributions of samples under random nonzero means and zero mean close in total variation, contradicting any more sample-efficient tester.The contradiction follows because successful distinguishing would require constant total variation distance.

D Omitted Proofs

The omitted proofs establish polynomial identities using Hermite-polynomial structure, Gaussian rotational invariance, orthogonality, and angle concentration for random unit vectors. They also derive mixture χ² identities and conclude the required probabilistic existence result.

  • Hermite-polynomial identity: Hermite polynomials are monic, so the degree-i terms on both sides of the relevant identity agree up to a polynomial of degree at most i −1.The proof isolates a lower-degree remainder p(x, y).
  • Hermite-polynomial identity: Gaussian rotational invariance and Hermite orthogonality show that the squared expectation equals E[p(X, Y )2] + i! on both sides.The argument uses (X, Y ) ∼N(0, I), orthogonality of distinct products, and the identity cos2 θ + sin2 θ = 1.
  • Hermite-polynomial identity: E[p(X, Y )2] = 0, and the Gaussian’s everywhere-positive density therefore implies p(x, y) is identically zero.This completes the polynomial identity argument.
  • Random-vector angle bounds: For random unit vectors, Lemma D.2 and Corollary D.3 bound the probability that their angle lies within n−α of π/2.The corollary applies for any 0 ≤α ≤1/2, using ε = n−α and elementary bounds on cos ε.
  • Random-vector angle bounds: Applying the angle bound with α = 1/2 −c and a union bound controls all pairwise inner products in S by Ω(nc−1/2) with positive probability.The proof concludes that S satisfies Lemma 3.7’s statement with positive probability.
  • χ² identities: The mixture χ² calculation expands into weighted component divergences and a cross term, then simplifies to 1 + w2χ2(B, D) + (1 −w)2χ2(C, D) + 2w(1 −w)χD(B, C).This is presented as the proof of Fact 6.2; the subsequent facts are completed directly from their definitions.
  • χ² identities: The proofs of Facts 6.3 and 6.4 invoke their definitions and conclude immediately.Each proof ends with “This completes the proof.”
Loading 1611.03473v2…