2022-06-28-diakonikolas22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
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 $\eps$-corrupted binary product distribution can learn its mean within $\ell_2$-error $o(\eps \sqrt{\log(1/\eps)})$. Similarly, we show that no efficient SQ algorithm with access to an $\eps$-corrupted ferromagnetic high-temperature Ising model can learn the model to total variation distance $o(\eps \log(1/\eps))$. 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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	diakonikolas22a	0	Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models	3936	3978	3936-3978	3936	false	Diakonikolas, Ilias and Kane, Daniel M. and Sun, Yuxin	given family Ilias Diakonikolas given family Daniel M. Kane given family Yuxin Sun	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/diakonikolas22a/diakonikolas22a.pdf