论文标题
多项式方法是通用的，用于无分布相关SQ学习
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
论文作者
论文摘要
我们考虑PAC和不可知模型中布尔功能类别的无分布学习问题。概括了Malach和Shalev-Shwartz（2022）的精美作品，这些作品给出了与学习DNF公式的紧密相关SQ（CSQ）下限，我们提供了新的证据，这些证明是在任何功能类别的阈值或近似程度上直接暗示PAC或无与伦比诺斯特学习的csq下限的下限。尽管这种界限隐含地结合了Feldman（2008，2012）和Sherstov（2008，2011）的先前结果，据我们所知，我们以前没有以这种形式出现过的确切陈述。此外，我们的证明很简单，并且在很大程度上是独立的。 这些下限与SQ模型中PAC或不可知性学习的阈值或近似程度上的上限相匹配的相应阳性结果，从这个意义上讲，这些结果表明多项式方法是一种通用，最有可能的无分配CSQ学习方法。
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) that gave tight correlational SQ (CSQ) lower bounds for learning DNF formulas, we give new proofs that lower bounds on the threshold or approximate degree of any function class directly imply CSQ lower bounds for PAC or agnostic learning respectively. While such bounds implicitly follow by combining prior results by Feldman (2008, 2012) and Sherstov (2008, 2011), to our knowledge the precise statements we give had not appeared in this form before. Moreover, our proofs are simple and largely self-contained. These lower bounds match corresponding positive results using upper bounds on the threshold or approximate degree in the SQ model for PAC or agnostic learning, and in this sense these results show that the polynomial method is a universal, best-possible approach for distribution-free CSQ learning.
