Pith. sign in

REVIEW 4 major objections 4 minor 1 cited by

Faster Algorithms for Agnostically Learning Disjunctions and their Implications

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Agnostic learning of Boolean disjunctions runs in $2^{\tilde{O}(n^{1/3})}$ time, beating the old $2^{\tilde{O}(\sqrt{n})}$ barrier.

desk verdict A real algorithmic advance and a real answer to GKK20's open question, but Theorem 3.1's final VC-dimension step needs repair before the proof is complete. read the letter →

arxiv 2504.15244 v1 pith:ASNNMWAF submitted 2025-04-21 cs.LG cs.DSstat.ML

Ilias Diakonikolas , Daniel M. Kane , Lisheng Ren This is my paper · ORCID
classification cs.LGcs.DSstat.ML MSC 68Q3268T05
keywords agnosticPAClearningBooleandisjunctionstatisticalqueriescorrelationalpolynomialregressionapproximatedegreesamplecomplexitycomputational
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that agnostically learning Boolean disjunctions—finding an OR of literals that predicts labels as well as the best such OR, even when labels are arbitrarily noisy—can be done with sample and computational complexity $2^{\tilde{O}(n^{1/3}\log(1/\epsilon))}$, improving the previous $2^{\tilde{O}(n^{1/2})}$ bound. The improvement comes from splitting the input distribution by Hamming weight: low-weight strings are handled by low-degree polynomial regression, while high-weight strings are either classified by a constant or used to identify and remove coordinates that cannot be in the target OR. The same scheme can be implemented with statistical queries, giving the first super-polynomial separation between the statistical query (SQ) and correlational statistical query (CSQ) models in distribution-free agnostic learning. If the claims hold, they close a gap left open by existing CSQ lower bounds and show that the exponent $1/2$ is not inherent to distribution-free agnostic learning of disjunctions.

What carries the argument

The load-bearing mechanism is a Hamming-weight threshold partition with radius $r=n^{2/3}$, paired with Chebyshev polynomial approximants for monotone disjunctions on low-weight strings. The algorithm alternates two operations: $L_1$-polynomial regression on the low-weight part, whose cost is $n^{O(r^{1/2}\log(1/\epsilon))}$, and coordinate elimination on the high-weight part, where each successful guess removes at least $r$ coordinates. The SQ variant uses heavy coordinates—coordinates appearing in at least $r/n$ of the inputs—as the eliminable objects. Choosing $r=n^{2/3}$ equalizes the recursion-factor and regression-factor contributions to the exponent, producing $2^{\tilde{O}(n^{1/3}\log(1/\epsilon))}$.

What would settle it

Compute or bound the VC dimension of the class of hypotheses obtained by taking a degree-$d$ polynomial threshold function on the low-weight part ($d=O(n^{1/3})$) and a constant on the high-weight part of a Hamming-weight partition. If that VC dimension is $n^{\Omega(d)}$ rather than $O(n)$, the final uniform-convergence step of the sample-based proof needs a new argument; if it is $O(n)$, the proof stands.

Watch

Extended reading notes

Core claim

The central discovery is that the $2^{\tilde{O}(\sqrt{n})}$ complexity of the standard $L_1$-polynomial regression learner is not an information-theoretic barrier, and a recursive coordinate-elimination strategy reaches exponent $1/3$. For a parameter $r=n^{2/3}$, the domain is split into strings of Hamming weight at most $r$ and strings of larger weight. On the low-weight part, Chebyshev polynomials approximate every monotone disjunction to error $\epsilon$ in degree $O(r^{1/2}\log(1/\epsilon))$, so $L_1$ regression learns a good classifier there. On the high-weight part, either a constant classifier is already weakly correct, or a random high-weight point with label 0 can be guessed; all coordinates set to 1 in that point are provably outside the target OR, so the algorithm removes at least $r$ coordinates and recurses. Balancing recursion depth $n/r$ against success probability $(1/\epsilon)^{n/r}$ and regression cost $n^{O(\sqrt{r})}$ at $r=n^{2/3}$ yields the claimed complexity. The SQ analogue replaces point-guessing with heavy-coordinate guessing, where a coordinate appearing with frequency at least $r/n$ either lies in the target, so the label 1 is known there, or can be deleted; this gives the same exponent and, combined with the known CSQ lower bound, separates SQ from CSQ.

Load-bearing premise

The proof transfers errors observed on samples to the true distribution by assuming the class of all hypotheses the algorithm may output has VC dimension only $O(n)$ (a polynomial amount of flexibility in $n$), but the hypotheses are degree-$O(n^{1/3})$ polynomial thresholds composed with Hamming-weight thresholds, so that VC-dimension bound is not established in the paper.

Editorial extensions

If this is right

  • General disjunctions, conjunctions, and mixed literals are all learned with the same $2^{\tilde{O}(n^{1/3}\log(1/\epsilon))}$ complexity, because negated variables can be added as new coordinates.
  • A distribution-free agnostic learner in the SQ model achieves this complexity, while any CSQ learner for disjunctions requires either $2^{\Omega(\sqrt{n})}$ queries or query tolerance $2^{-\Omega(\sqrt{n})}$; hence SQ is super-polynomially stronger than CSQ for this natural class.
  • There is an $(\alpha,\epsilon)$-approximate agnostic learner with complexity $2^{\tilde{O}(n^{1/3}\alpha^{-2/3})}\mathrm{poly}(1/\epsilon)$, interpolating between the new exact-error learner and the earlier polynomial-time $O(\sqrt{n})$-approximation result.
  • Any further improvement in the exponent of the disjunction learner would translate into a faster realizable PAC learner for DNFs, improving the previous $2^{\tilde{O}(n^{1/3})}$ bound for that problem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Not in the paper: the same low-weight/high-weight partition with coordinate elimination may extend to other structured classes such as $k$-juntas or width-$k$ DNFs, with the exponent depending on $k$; this would give a test of the template beyond disjunctions.
  • Not in the paper: the SQ/CSQ separation is achieved by replacing point-guessing with aggregate heavy-coordinate guesses, which isolates label-independent queries about the marginal distribution as the source of SQ's extra power; applying that lens to another concept class would show whether the separation mechanism is general.
  • Not in the paper: the algorithm's success probability per attempt is only $2^{-\tilde{O}(n^{1/3}\log(1/\epsilon))}$, so the practical guarantee rests on repetition and empirical-error testing; a derandomized version preserving the same exponent is an open direction the paper does not discuss.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies distribution-free agnostic PAC learning of disjunctions over {0,1}^n. The main result is an agnostic learner with sample and computational complexity 2^{O~(n^{1/3} log(1/epsilon))}, improving the previous 2^{O~(n^{1/2})} bound from L1 polynomial regression. The authors give two algorithms: a sample-based learner (Algorithm 1) and an SQ learner (Algorithm 2). The SQ learner is claimed to give the first super-polynomial separation between the SQ and CSQ models in distribution-free agnostic learning, answering an open question from GKK20. A third contribution is an alpha-approximate agnostic learner with complexity 2^{O~(n^{1/3} alpha^{-2/3})} poly(1/epsilon). The main technical ingredients are a new approximate-degree bound for monotone disjunctions on low-Hamming-weight inputs (Lemma 3.2), a recursion that removes coordinates of high-weight negative examples, and black-box use of L1 regression and agnostic boosting.

Significance. If the main theorem is correct, it is a significant advance: it replaces the long-standing 2^{O~(n^{1/2})} upper bound for agnostically learning disjunctions and resolves the SQ/CSQ separation question posed in GKK20. The paper is careful to use known approximation-theoretic facts (Chebyshev polynomials, Nisan-Szegedy) and black-box subroutines, and there are no fitted constants or circular reductions in the upper bounds. The approximate-degree lemma is proved in detail. However, the proof as written contains a load-bearing gap in the generalization step of Theorem 3.1 and several smaller unaddressed details about the reuse of the sample set; these need to be repaired before the claims are fully established.

major comments (4)
  1. [Section 3, proof of Theorem 3.1, final paragraph] The claim that every possible output h1 or h2 is an intersection of two halfspaces and therefore has VC dimension O(n) is incorrect. The hypothesis h1 is a degree-d polynomial threshold function on Xlight, with d = O(n^{1/3} log(1/epsilon)); in the monomial feature space it is a halfspace of dimension N = sum_{i=0}^d binom(n,i) = 2^{O~(n^{1/3} log(1/epsilon))}, combined with a Hamming-weight threshold. The correct bound is log VC = O(d log n) = O~(n^{1/3} log(1/epsilon)), not O(n). The stated sample size 2^{O~(n^{1/3} log(1/epsilon))} can absorb this larger VC dimension by choosing the implied constant sufficiently large, but the proof as written does not provide that argument, so the transfer from empirical error on P to true error on D is not justified as stated.
  2. [Section 3, Algorithm 1 and proof of Theorem 3.1] The proof does not account for the fact that the same sample set P is reused across iterations for L1 regression on Plight, for choosing the constants c', for evaluating empirical error, and for sampling xguess. A uniform-convergence argument requires a fixed hypothesis class F that contains all hypotheses reachable by any execution of the algorithm, and then applies Fact 2.2 to the empirical process sup_{h in F} |err_P(h) - err_D(h)|. The proof only applies uniform convergence to the returned hypothesis and states a VC bound for an informally described class. This needs to be made explicit with a global class that includes all possible subsets I_t, constants c', and degree-d polynomial threshold functions, together with the correct VC dimension bound from the previous comment.
  3. [Section 4, Lemma 4.3] The proof of Property 2 uses Fact 4.4 to claim |hat{P_i}/hat{P_U} - Pr[x_i=1 | x in U_t]| <= (1/100)r/n. This requires a lower bound on P_U = Pr[x in U_t] that is not stated; the argument should use the termination condition in Algorithm 2, Line 7, to note that before each iteration P_U > epsilon/3, and check that the tolerance tau = epsilon r/(800n) is small enough for Fact 4.4 to apply. In addition, the Markov calculation contains a factor error: the displayed bound should be E[W_I(x) | x in U_t] <= (4/3)r, not (4/3)r/n, for the conclusion Pr[x in B_t | x in U_t] >= 1/3 to follow.
  4. [Section 5, Lemma B.1] The proof of Lemma B.1 contains a summation over i in [t] in which the hypothesis is written as h'_t instead of h'_i in several terms. This is a typographical error, but it obscures the argument that the partial classifiers on the removed sets accumulate error; it should be corrected for the proof to be readable.
minor comments (4)
  1. [Algorithm 1, Line 4] The definition of Pheavy is written as {(x,y) in P | x in Xlight}; it should be x in Xheavy.
  2. [Algorithm 2, Line 6] The query function for estimating P_{U_{t+1}} is written as 1(x in U_t); it should be 1(x in U_{t+1}).
  3. [Proof of Theorem 3.1] In the paragraph on termination, the proof says Line 13 removes at least r coordinates from S; it should say from I_t, since the removed coordinates are those not in S when the sampled xguess satisfies f_S(xguess)=0.
  4. [Section 4, proof of Theorem 4.2] The repeated use of 'mortality' in the description of the SQ algorithm is a typo; the intended phrase is 'morally corresponds'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new upper bounds are derived from external approximation theory, L1 regression, and boosting, while the lower bound comes from independent prior work.

full rationale

The paper's central derivation is self-contained against external benchmarks and does not reduce to its own inputs by construction. Theorem 1.2 is obtained from Theorem 3.1 via standard agnostic boosting (Fact A.2), and Theorem 3.1 is proved using the Chebyshev approximation bound of Lemma 3.2, the black-box L1-regression subroutine of Fact 2.4, and uniform convergence. The radius r = n^{2/3} is set analytically, not fitted to data; no parameter is calibrated on a subset and then renamed as a prediction. The SQ learner in Section 4 uses the same external subroutine and standard statistical-query estimation, and its correctness proof does not presuppose the theorem it establishes. The CSQ lower bound is imported from GKK20 together with the standard Nisan-Szegedy approximate-degree lower bound, not from the present authors' prior work, and it is not used to prove the upper bound. Self-citations in the references are background or non-load-bearing. One technical concern is separate from circularity: the proof of Theorem 3.1 asserts that every possible output hypothesis h1 or h2 is an intersection of two halfspaces and thus has VC dimension O(n), but h1 is a polynomial threshold function in a lifted monomial feature space of dimension roughly n^{O(n^{1/3})}. This appears to be a correctness gap in the written uniform-convergence argument, not a circularity: the stated sample size 2^{O~(n^{1/3} log(1/epsilon))} is large enough to absorb the larger VC dimension, and no claimed result is equivalent to an input by definition. For these reasons, the circularity score is 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard approximation theory and black-box subroutines from prior literature. There are no fitted parameters: the n^{2/3} threshold is an optimization choice. The SQ/CSQ separation uses GKK20's independent lower bound, so nothing circular is present.

free parameters (1)
  • Hamming weight threshold r = n^{2/3}
    Chosen to balance recursion depth O(n/r) against L1 regression degree O(sqrt(r)); not fitted to data. The number of iterations T = ceil(n/r)+1 follows from r.
assumptions (5)
  • standard math VC inequality (Fact 2.2) bounds uniform deviations of empirical means over finite-VC classes.
    Used in the proof of Theorem 3.1 to transfer guarantees from the sample set P to the underlying distribution D.
  • domain assumption L1 polynomial regression learns distribution-free agnostically with complexity n^{O(d)} when the class has approximate degree d, and has an SQ implementation (Fact 2.4).
    Core subroutine from KKMS08; taken as a black box in Sections 3 and 4.
  • standard math Chebyshev polynomials give O(sqrt(r) log(1/epsilon)) approximate degree for disjunctions restricted to strings of Hamming weight at most r (Lemma 3.2).
    Proved in the paper from Fact 3.3; this underlies both algorithms.
  • domain assumption Agnostic boosting theorems (Fact A.2 and Fact B.2) convert weak agnostic learners to strong learners.
    Used to go from weak learner guarantees to OPT + epsilon and alpha-OPT + epsilon learners.
  • domain assumption The GKK20 CSQ lower bound (Fact C.5) with the Omega(sqrt n) approximate degree of disjunctions (Fact C.6).
    Needed for the claimed SQ versus CSQ separation; quoted and reproved in Appendix C.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Algorithms for Agnostically Learning Disjunctions and their Implications." pith.science (2026). https://pith.science/paper/ASNNMWAF

@misc{pith2026250415244,
  author       = {Pith},
  title        = {Pith review of: Faster Algorithms for Agnostically Learning Disjunctions and their Implications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ASNNMWAF}},
  note         = {Machine review of arXiv:2504.15244}
}
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions

    cs.DS 2025-04 accept novelty 7.0 of 10

    The authors identify a link between agnostic conjunction learning and tolerant junta testing, and use it to improve both algorithms, roughly to 2^{O~(n^{1/3})} time and 2^{O~(k^{1/3})} queries.

Reference graph

Works this paper leans on

28 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [1]

    Awasthi, A

    P. Awasthi, A. Blum, and O. Sheffet. Improved guarantees for agnostic learning of disjunctions. In COLT 2010 - The 23rd Conference on Learning Theory , pages 359--367, 2010

    work page 2010

  2. [2]

    Bshouty and V

    N. Bshouty and V. Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research , 2:359--395, 2002

    work page 2002

  3. [3]

    A. Blum. Machine learning: My favorite results, directions, and open problems. In 44th Symposium on Foundations of Computer Science (FOCS 2003) , pages 11--14, 2003

    2003

  4. [4]

    Bun and J

    M. Bun and J. Thaler. Approximate degree in classical and quantum computing. Found. Trends Theor. Comput. Sci. , 15(3-4):229--423, 2022

    work page 2022

  5. [5]

    E. Cheney. Introduction to Approximation Theory . McGraw-Hill, New York, New York, 1966

    work page 1966

  6. [6]

    A. Daniely. Complexity theoretic limitations on learning halfspaces. In Proceedings of the 48th Annual Symposium on Theory of Computing, STOC 2016 , pages 105--117, 2016

    work page 2016

  7. [7]

    Dachman - Soled, V

    D. Dachman - Soled, V. Feldman, L. - Y. Tan, A. Wan, and K. Wimmer. Approximate resilience, monotonicity, and the complexity of agnostic learning. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , pages 498--511. SIAM , 2015

    work page 2015

  8. [8]

    Cryptographic Hardness of Learning Halfspaces with Massart Noise

    I. Diakonikolas, D. M. Kane, P. Manurangsi, and L. Ren. Cryptographic hardness of learning halfspaces with massart noise. In Advances in Neural Information Processing Systems (NeurIPS) , volume 35, pages 3624--3636, 2022. Available at https://doi.org/10.48550/arXiv.2207.14266

    work page Pith review arXiv doi:10.48550/arxiv.2207.14266 2022

Show all 28 references
  1. [9]

    Diakonikolas, D

    I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial regression for agnostic learning under gaussian marginals. In Proceedings of The 34th Conference on Learning Theory, COLT , 2021

    2021

  2. [10]

    V. Feldman. A complete characterization of statistical query learning with applications to evolvability. In Proc. 50th Symposium on Foundations of Computer Science (FOCS) , pages 375--384, 2009

    2009

  3. [11]

    V. Feldman. Distribution-specific agnostic boosting. In Proceedings of Innovations in Computer Science , pages 241--250, 2010

    2010

  4. [12]

    V. Feldman. Distribution-independent evolvability of linear threshold functions. In COLT 2011 - The 24th Annual Conference on Learning Theory , volume 19 of JMLR Proceedings , pages 253--272. JMLR.org, 2011

    2011

  5. [13]

    Feldman, V

    V. Feldman, V. Guruswami, P. Raghavendra, and Y. Wu. Agnostic learning of monomials by halfspaces is hard. In FOCS , pages 385--394, 2009

    2009

  6. [14]

    Gollakota, S

    A. Gollakota, S. Karmalkar, and A. R. Klivans. The polynomial method is universal for distribution-free correlational SQ learning. CoRR , abs/2010.11925, 2020

    2010 arXiv

  7. [15]

    Haussler

    D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications . Information and Computation , 100:78--150, 1992

    1992

  8. [16]

    M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM , 45(6):983--1006, 1998

    1998

  9. [17]

    Kalai and V

    A. Kalai and V. Kanade. Potential-based agnostic boosting. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009 , pages 880--888, 2009

    2009

  10. [18]

    Kalai, A

    A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. SIAM Journal on Computing , 37(6):1777--1805, 2008. Special issue for FOCS 2005

    2008

  11. [19]

    Kalai, Y

    A. Kalai, Y. Mansour, and E. Verbin. On agnostic boosting and parity learning. In Proc.\ 40th Annual ACM Symposium on Theory of Computing (STOC) , pages 629--638, 2008

    2008

  12. [20]

    Klivans and R

    A. Klivans and R. Servedio. Learning DNF in time 2^ O (n^ 1/3 ) . In Proc.\ 33rd Annual ACM Symposium on Theory of Computing (STOC) , pages 258--265. ACM Press, 2001

    2001

  13. [21]

    A. R. Klivans and A. A. Sherstov. Lower bounds for agnostic learning via approximate rank. Comput. Complex. , 19(4):581--604, 2010

    2010

  14. [22]

    Kearns, R

    M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning . Machine Learning , 17(2/3):115--141, 1994

    1994

  15. [23]

    Nisan and M

    N. Nisan and M. Szegedy. On the degree of B oolean functions as real polynomials . Comput. Complexity , 4:301--313, 1994

    1994

  16. [24]

    R. Paturi. On the degree of polynomials that approximate symmetric B oolean functions . In Proceedings of the 24th Symposium on Theory of Computing , pages 468--474, 1992

    1992

  17. [25]

    D. Peleg. Approximation algorithms for the label-cover\( _ max \) and red-blue set cover problems. J. Discrete Algorithms , 5(1):55--64, 2007

    2007

  18. [26]

    Sherstov

    A. Sherstov. The pattern matrix method for lower bounds on quantum communication. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing , pages 85--94, 2008

    2008

  19. [27]

    S. Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems. In The Thirty Sixth Annual Conference on Learning Theory, COLT , volume 195 of Proceedings of Machine Learning Research , pages 3029--3064, 2023

    2023

  20. [28]

    L. G. Valiant. A theory of the learnable. In Proc.\ 16th Annual ACM Symposium on Theory of Computing (STOC) , pages 436--445. ACM Press, 1984

    1984

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.