2021-07-21-diakonikolas21c.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
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model	We study the problem of agnostic learning under the Gaussian distribution in the Statistical Query (SQ) model. We develop a method for finding hard families of examples for a wide range of concept classes by using LP duality. For Boolean-valued concept classes, we show that the $L^1$-polynomial regression algorithm is essentially best possible among SQ algorithms, and therefore that the SQ complexity of agnostic learning is closely related to the polynomial degree required to approximate any function from the concept class in $L^1$-norm. Using this characterization along with additional analytic tools, we obtain explicit optimal SQ lower bounds for agnostically learning linear threshold functions and the first non-trivial explicit SQ lower bounds for polynomial threshold functions and intersections of halfspaces. We also develop an analogous theory for agnostically learning real-valued functions, and as an application prove near-optimal SQ lower bounds for agnostically learning ReLUs and sigmoids.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	diakonikolas21c	0	The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model	1552	1584	1552-1584	1552	false	Diakonikolas, Ilias and Kane, Daniel M. and Pittas, Thanasis and Zarifis, Nikos	given family Ilias Diakonikolas given family Daniel M. Kane given family Thanasis Pittas given family Nikos Zarifis	2021-07-21		Proceedings of Thirty Fourth Conference on Learning Theory	134	inproceedings	date-parts 2021 7 21	http://proceedings.mlr.press/v134/diakonikolas21c/diakonikolas21c.pdf