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

By Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. 2016

254 citations recorded by the source corpus.

We describe a general technique that yields the first Statistical Query lower bounds} fora 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 super-polynomial gap} between the (information-theoretic)sample complexity and the computational complexity of any} Statistical Query algorithm for the problem. Statistical Query (SQ) algorithms are a class of algorithms that are only allowed to query expectations of functions of the distribution rather than directly access samples. This class of algorithms is quite broad: a wide range of known algorithmic techniques in machine learning are known to be implementable using SQs.Moreover, for the unsupervised learning problems studied in this paper, all known algorithms with non-trivial performance guarantees are SQ or are easily implementable using SQs. Our SQ lower bound for Problem (1)is qualitatively matched by known learning algorithms for GMMs. At a conceptual level, this result implies that – as far as SQ algorithms are concerned – the computational complexity of learning GMMs is inherently exponential in the dimension of the latent space} – even though there is no such information-theoretic barrier. 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. On the positive side, we also give a new (SQ) learning algorithm for Problem (2) achievingthe information-theoretically optimal accuracy, up to a constant factor, whose running time essentially matches our lower bound. Our algorithm relies on a filtering technique generalizing \cite{DiakonikolasKKLMS16} that removes outliers based on higher-order tensors.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 statistical–computational tradeoff} for SQ algorithms, matching known upper bounds. Finally, our technique can be used to obtain tight sample complexitylower bounds for high-dimensional testing} problems. Specifically, for the classical problem of robustly testing} an unknown mean (known covariance) Gaussian, our technique implies an information-theoretic sample lower bound that scales linearly} in the dimension. Our sample lower bound matches the sample complexity of the corresponding robust learning} problem and separates the sample complexity of robust testing from standard (non-robust) testing. This separation is surprising because such a gap does not exist for the corresponding learning problem.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “…estimation in a variety of high-dimensional settings, including learning graphical models [DKS16], understanding computation-robustness tradeoﬀs [DKS17c, DKK + 18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of hypotheses [CSV17, MV17, DKS17b],…”
Adversarial examples from computational constraints (2018, methodology): “This family can be seen to be a high-dimensional generalization and modification of a family considered in (Diakonikolas et al., 2017).”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “These works led to an active line of work (e.g., see (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2017; 2018; Diakonikolas et al. 2018; Prasad et al. 2018; Diakonikolas, Kong, and Stewart 2018) and references therein) exploring the possibility of robust statistics over…”
Learning geometric concepts with nasty noise (2017, unknown): “btain Tmax = √ ℓ · O(ln( p ℓ/ǫ))d = O(nd2 ln2(n/ǫ))d/2. Next, we obtain the bound on δ for (i). To get a bound on δ, we will need the following technical claim: Claim 2.23 (see, e.g., Claim 7.18 from [DKS16]). For any R > 0, d ∈Z+,ǫ > 0, and exp(−(a/R)2/d) = ǫ, we have Z ∞ a exp(−(T/R)2/d)TdT ”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, background): “However, as shown in [DKS17], any Statistical Query algorithm that runs in time poly( N ) needs to have error Ω( ǫ log(1 /ǫ )).”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “…recently that provable algorithms for learning in the presence of a large fraction of arbitrary (and potentially adversarial) data have been formulated in high-dimensional settings (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Steinhardt et al., 2016; Bhatia et al., 2015).”
Computationally Efficient Robust Sparse Estimation in High Dimensions (2017, methodology): “By Theorem 4.15 of (Diakonikolas et al., 2016a) we have the following formula for the cov (Ω)”
Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions (2022, background): “As a simple consequence, existing computational hardness results for learning natural high-dimensional distributions like mixtures of Gaussians [DKS17; Bru+21; GVV22] and pushforwards of Gaussians by shallow ReLU networks [DV21; Che+22a; CLL22] immediately imply hardness of score estimation for…”
Dealing with Range Anxiety in Mean Estimation via Statistical Queries (2016, background): “As a result lower bounds for VSTAT usually correspond more tightly to the known computational and sample complexity bounds on the problem ( e.g. [FGRVX12; FPV13; FGV15; DKS16]).”
Learning under p-Tampering Attacks (2018, background): “These works led to an active line of work (e.g., see [CSV17, DKS17, DKS18a, DKK + 18, PSBR18, DKS18b] and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees.”
A General Characterization of the Statistical Query Complexity (2016, background): “In fact, for a number of central problems in learning theory and complexity unconditional lower bounds for SQ algorithms are known that closely match the known computational complexity upper bounds for those problems (e.g. Blum et al., 1994; Feldman et al., 2012, 2013; Bresler et al., 2014; Dachman-”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, methodology): “bini-Tonelli, since X∞ ℓ=1 |µ|ℓ/(ℓ! p j!) Z∞ −∞ |Hej(x)||Heℓ(x)|G(x)dx ≤ X∞ ℓ=1 |µ|ℓ/(ℓ! p j!) sZ ∞ −∞ Hej(x)2G(x)dx Z∞ −∞ Heℓ(x)2G(x)dx = X∞ ℓ=1 |µ|ℓ/ √ ℓ! < ∞ . 53 Noting, as in Corollary 5.4 of [DKS16b], that |Pj(x)| ≤ (4|x|)j for |x| ≥ 1, we have that Xi j=0 b2 ij = Z∞ −∞ Pj(x)2G(x)dx ≤ Z1 −1”