Faster Algorithms for Agnostically Learning Disjunctions and Their Implications
Abstract
We study the algorithmic task of learning Boolean disjunctions in the distribution-free agnostic PAC model. The best known agnostic learner for the class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound is known to be nearly best possible within the class of Correlational Statistical Query (CSQ) algorithms. In this work, we develop an agnostic learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our algorithm can be implemented in the Statistical Query (SQ) model, providing the first separation between the SQ and CSQ models in distribution-free agnostic learning.
Cite
Text
Diakonikolas et al. "Faster Algorithms for Agnostically Learning Disjunctions and Their Implications." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.Markdown
[Diakonikolas et al. "Faster Algorithms for Agnostically Learning Disjunctions and Their Implications." Proceedings of Thirty Eighth Conference on Learning Theory, 2025.](https://mlanthology.org/colt/2025/diakonikolas2025colt-faster/)BibTeX
@inproceedings{diakonikolas2025colt-faster,
title = {{Faster Algorithms for Agnostically Learning Disjunctions and Their Implications}},
author = {Diakonikolas, Ilias and Kane, Daniel M. and Ren, Lisheng},
booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory},
year = {2025},
pages = {1531-1558},
volume = {291},
url = {https://mlanthology.org/colt/2025/diakonikolas2025colt-faster/}
}