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.

本文提出了一种统计查询下限技术，用于解决高维学习问题中高斯分布的学习和鲁棒性学习问题，并得出了样本复杂度和计算复杂度之间存在的超多项式差距，同时提供了一个新的方法来解决一些相关的无监督估计和测试问题。

高维高斯分布和高斯混合模型的鲁棒估计的统计查询下限

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

We consider the problem of deciding whether a highly incomplete signal lies
within a given subspace. This problem, Matched Subspace Detection, is a
classical, well-studied problem when the signal is completely observed. High-
dimensional testing problems in which it may be prohibitive or impossible to
obtain a complete observation motivate this work. The signal is represented as
a vector in R^n, but we only observe m << n of its elements. We show that
reliable detection is possible, under mild incoherence conditions, as long as m
is slightly greater than the dimension of the subspace in question.

本研究考虑高度不完整信号是否属于给定子空间的问题，称为匹配子空间检测问题。当信号完全被观察时，这是一个经典的和深入研究的问题。我们将信号表示为向量，但仅观察其少部分元素。在温和的不一致条件下，只要观察的元素数略大于所讨论的子空间的维数，就可能实现可靠检测。