Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
复制标题
DOI：
10.48550/arxiv.2206.04589
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Yuxin Sun
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Yuxin Sun
我们建立了最佳的统计查询（SQ）下限，以鲁棒地学习某些离散高维分布的家庭。特别是，我们表明，没有访问$ \ epsilon $ -Cruntupted二进制产品分布的有效SQ算法可以在$ \ ell_2 $ -error $ o（\ epsilon \ sqrt {\ log（\ log（1/\ epsilon））内学习其平均值。 }）$。同样，我们表明，没有访问$ \ epsilon $ - 腐败的铁磁高温伊辛模型的有效SQ算法可以学习到总变量距离$ o（\ epsilon \ log（1/\ epsilon））$。我们的SQ下限符合这些问题已知算法的错误保证，提供证据表明这些任务的当前上限是最好的。在技术层面上，我们为离散的高维分布开发了一个通用的SQ下限，从低维矩匹配构建体开始，我们认为这将找到其他应用程序。此外，我们介绍了新的想法，以分析这些矩匹配的结构，以进行离散的单变量分布。
We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. In particular, we show that no efficient SQ algorithm with access to an $\epsilon$-corrupted binary product distribution can learn its mean within $\ell_2$-error $o(\epsilon \sqrt{\log(1/\epsilon)})$. Similarly, we show that no efficient SQ algorithm with access to an $\epsilon$-corrupted ferromagnetic high-temperature Ising model can learn the model to total variation distance $o(\epsilon \log(1/\epsilon))$. Our SQ lower bounds match the error guarantees of known algorithms for these problems, providing evidence that current upper bounds for these tasks are best possible. At the technical level, we develop a generic SQ lower bound for discrete high-dimensional distributions starting from low dimensional moment matching constructions that we believe will find other applications. Additionally, we introduce new ideas to analyze these moment-matching constructions for discrete univariate distributions.