Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
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.