The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1552-1584, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-diakonikolas21c, title = {The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model}, author = {Diakonikolas, Ilias and Kane, Daniel M. and Pittas, Thanasis and Zarifis, Nikos}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {1552--1584}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/diakonikolas21c/diakonikolas21c.pdf}, url = {https://proceedings.mlr.press/v134/diakonikolas21c.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model %A Ilias Diakonikolas %A Daniel M. Kane %A Thanasis Pittas %A Nikos Zarifis %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-diakonikolas21c %I PMLR %P 1552--1584 %U https://proceedings.mlr.press/v134/diakonikolas21c.html %V 134 %X 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.
APA
Diakonikolas, I., Kane, D.M., Pittas, T. & Zarifis, N.. (2021). The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:1552-1584 Available from https://proceedings.mlr.press/v134/diakonikolas21c.html.

Related Material