# Faster Algorithms for Agnostically Learning Disjunctions and their Implications

arXiv: https://arxiv.org/abs/2504.15244 · HTML: https://mlsanity.com/paper/2504.15244/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 21 Apr 2025.

## Builds on (most cited first, 6 of 6)

- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems](https://mlsanity.com/paper/2207.14030/) (2022)
- [The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning](https://mlsanity.com/paper/2010.11925/) (2020)

## Abstract (arXiv)

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, 1n is the L1-polynomial regression algorithm, achieving complexity 2^tildeO(n1/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^tildeO(n1/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.