Faster Algorithms for Agnostically Learning Disjunctions and their Implications

Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:1531-1558, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v291-diakonikolas25b, 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}, pages = {1531--1558}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/diakonikolas25b/diakonikolas25b.pdf}, url = {https://proceedings.mlr.press/v291/diakonikolas25b.html}, 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.} }
Endnote
%0 Conference Paper %T Faster Algorithms for Agnostically Learning Disjunctions and their Implications %A Ilias Diakonikolas %A Daniel M. Kane %A Lisheng Ren %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-diakonikolas25b %I PMLR %P 1531--1558 %U https://proceedings.mlr.press/v291/diakonikolas25b.html %V 291 %X 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.
APA
Diakonikolas, I., Kane, D.M. & Ren, L.. (2025). Faster Algorithms for Agnostically Learning Disjunctions and their Implications. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:1531-1558 Available from https://proceedings.mlr.press/v291/diakonikolas25b.html.

Related Material