论文标题
最佳的SQ下限，以鲁棒学习离散的产品分布和ISING模型
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
论文作者
论文摘要
我们建立了最佳的统计查询（SQ）下限，以鲁棒地学习某些离散高维分布的家庭。特别是，我们表明，没有访问$ε$ - 腐败的二进制产品分布的有效SQ算法可以在$ \ ell_2 $ -Error $ o（ε\ sqrt {\ log（1/ε）}）中学习其平均值。同样，我们表明没有有效的SQ算法可以访问$ε$ - 腐败的铁磁高磁性ISING模型可以学习到总变化距离$ O（ε\ log（1/ε））$的模型。我们的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 $ε$-corrupted binary product distribution can learn its mean within $\ell_2$-error $o(ε\sqrt{\log(1/ε)})$. Similarly, we show that no efficient SQ algorithm with access to an $ε$-corrupted ferromagnetic high-temperature Ising model can learn the model to total variation distance $o(ε\log(1/ε))$. 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.
