Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes
复制标题
通过压缩方案稳健学习高斯混合物的近最优样本复杂度界限
DOI：
10.1145/3417994
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Y. Plan
中科院分区：
文献类型：
--
作者：
H. Ashtiani;S. Ben;Nicholas J. A. Harvey;Christopher Liaw;Abbas Mehrabian;Y. Plan
我们引入一种基于样本压缩概念的分布学习新技术。任何允许这种压缩方案的分布类别都可以用少量样本进行学习。此外，如果一类分布具有这样的压缩方案，那么这些分布的乘积类别和混合类别也具有。作为这项技术的一个应用，我们证明了对于在$R^d$中学习$k$个高斯分布的混合，在总变差距离误差为$\varepsilon$的情况下，$\tilde{\Theta}(kd^2 / \varepsilon^2)$个样本是必要且充分的。这改进了该问题已知的上界和下界。对于轴对齐高斯分布的混合，我们表明$\tilde{O}(kd / \varepsilon^2)$个样本就足够了，与已知的下界相匹配。此外，这些结果在不可知学习（或稳健估计）设定下成立，在该设定中目标分布只是近似为高斯分布的混合。我们的主要上界是通过证明$R^d$中的高斯分布类别具有一种小的压缩方案来证明的。
We introduce a novel technique for distribution learning based on a notion of sample compression. Any class of distributions that allows such a compression scheme can be learned with few samples. Moreover, if a class of distributions has such a compression scheme, then so do the classes of products and mixtures of those distributions. As an application of this technique, we prove that ˜Θ(kd2/ε2) samples are necessary and sufficient for learning a mixture of k Gaussians in Rd, up to error ε in total variation distance. This improves both the known upper bounds and lower bounds for this problem. For mixtures of axis-aligned Gaussians, we show that Õ(kd/ε2) samples suffice, matching a known lower bound. Moreover, these results hold in an agnostic learning (or robust estimation) setting, in which the target distribution is only approximately a mixture of Gaussians. Our main upper bound is proven by showing that the class of Gaussians in Rd admits a small compression scheme.
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
通讯作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt