Faster Algorithms for Agnostically Learning Disjunctions and their Implications
Not on the map. Why?
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.
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
6 of 31 references.
References · 6
- 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
- 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
- 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
- 2014Approximate resilience, monotonicity, and the complexity of agnostic learningcited by 16
- 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
- 2020The Polynomial Method is Universal for Distribution-Free Correlational SQ Learningcited by 3
Built on by
Not cited yet.