Abstract

We study the algorithmic task of learning Boolean disjunctions in thedistribution-free agnostic PAC model. The best known agnostic learner for theclass of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regressionalgorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity boundis known to be nearly best possible within the class of CorrelationalStatistical Query (CSQ) algorithms. In this work, we develop an agnosticlearner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Ouralgorithm can be implemented in the Statistical Query (SQ) model, providing thefirst separation between the SQ and CSQ models in distribution-free agnosticlearning.

 

Quick Read (beta)