The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning

Aravind Gollakota, Sushrut Karmalkar, Adam Klivans

We consider the problem of distribution-free learning for Boolean function classes in the PAC and agnostic models. Generalizing a beautiful work of Malach and Shalev-Shwartz (2022)…