{"id":"c7bfcf10-907d-4752-a080-67c4b3df92c2","arxiv_id":"2504.15244","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A new 2^{O~(n^{1/3})} agnostic learner for disjunctions, together with an SQ implementation that yields the first SQ versus CSQ separation in distribution-free agnostic learning.","lead":"This paper gives a faster algorithm for learning Boolean OR-functions from noisy labels, improving the previous 2^{O~(sqrt n)} bound to 2^{O~(n^{1/3})}. Its statistical-query variant separates two standard oracle models in distribution-free agnostic learning, resolving an open question in the field.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's final uniform-convergence step misstates the VC dimension of its output hypotheses as O(n); the correct bound n^{O(n^{1/3} log(1/eps))} still fits the sample size, but the proof needs repair.","rationale":"The reader's weakest assumption pinpoints exactly the most load-bearing gap: the proof of Theorem 3.1 transfers empirical error to true error using a VC-dimension claim that is false as written. I agree that this is the critical step for the sample-based learner and hence for Theorem 1.2. The correct VC dimension of degree-d polynomial threshold functions is about n^{O(d)} = 2^{O~(n^{1/3} log(1/eps))}; the stated sample size can absorb this because log VC is O~(n^{1/3} log(1/eps)), so the concern is a proof repair rather than a refutation of the main result. I also checked Lemma 3.2 and found a separate proof defect: the construction with p2(t) = p1(t) * c log(1/eps) does not satisfy |p2(t)| <= eps (e.g., eps=0.01, r=64, d=16, c=10 gives |p2(1)| much larger than eps). The lemma is nonetheless true via the standard approximate-degree bound for OR, O(sqrt(r log(1/eps))), so this is also repairable and does not change the verdict. The reader's CONDITIONAL verdict remains appropriate: the algorithmic ideas are credible and likely correct, but the written proofs contain nontrivial gaps that should be fixed before the claims are treated as fully established.","tokens_in":25959,"tokens_out":29168,"duration_ms":263162,"concrete_test":"Re-derive Fact 2.2 for the class H of all hypotheses Algorithm 1 can return, using the correct VC bound VCdim(H) = O(n^{d+1}) with d = O(n^{1/3} log(1/eps)), and verify that the sample size in Theorem 3.1 (with its implied constant) satisfies n_sample >= C * VCdim(H) / eps^2. If the implied constant must be increased, increase it; if VCdim(H) instead turns out to be exponential in n^{1/3} log(1/eps) times a factor not absorbed by the tilde, the proof would fail.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is the final generalization step in the proof of Theorem 3.1. The proof asserts that every hypothesis h1 or h2 that Algorithm 1 can return is an intersection of two halfspaces and therefore has VC dimension O(n). This is not correct as stated: h1 is defined as h'_1 on X_light, where h'_1 is the degree-d polynomial threshold function produced by L1 regression with d = O(n^{1/3} log(1/eps)), and 'X_light' is a Hamming-weight threshold W_{I_t}(x) <= r. In the feature space of all monomials of degree at most d, h'_1 is a halfspace of dimension N = sum_{i=0}^d binom(n,i) = 2^{O~(n^{1/3} log(1/eps))}; intersecting with W <= r gives VC dimension at most O(n * N) (or O(N) up to polylog factors), not O(n). The argument as written therefore does not justify the transfer from empirical error on P to true error on D. The gap is repairable: the sample size 2^{O~(n^{1/3} log(1/eps))} is large enough for the correct VC bound, since log VC = O(d log n) = O~(n^{1/3} log(1/eps)), but the proof must be reworked to state and use this bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":26255,"tokens_out":19305,"duration_ms":178434,"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":[{"comment":"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.","section":"Section 3, proof of Theorem 3.1, final paragraph"},{"comment":"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.","section":"Section 3, Algorithm 1 and proof of Theorem 3.1"},{"comment":"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.","section":"Section 4, Lemma 4.3"},{"comment":"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.","section":"Section 5, Lemma B.1"}],"minor_comments":[{"comment":"The definition of Pheavy is written as {(x,y) in P | x in Xlight}; it should be x in Xheavy.","section":"Algorithm 1, Line 4"},{"comment":"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}).","section":"Algorithm 2, Line 6"},{"comment":"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.","section":"Proof of Theorem 3.1"},{"comment":"The repeated use of 'mortality' in the description of the SQ algorithm is a typo; the intended phrase is 'morally corresponds'.","section":"Section 4, proof of Theorem 4.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Top line: this is genuine progress. The new learner gets 2^{O~(n^{1/3})} for agnostically learning disjunctions, improving the old 2^{O~(n^{1/2})} barrier, and the SQ variant gives the first super-polynomial SQ/CSQ separation in distribution-free agnostic learning. Those are the two things that matter, and they are new.\n\nThe core ideas are good. Partition by Hamming weight, use Chebyshev-based low-degree approximations on the light part, and on the heavy part either learn a trivial classifier or delete a block of coordinates by guessing a negative example. The recursion depth n/r with r = n^{2/3} is what buys the exponent n^{1/3}. Lemma 3.2 is carefully done. The SQ version replaces random high-weight samples with guesses of heavy coordinates, which is a clever and legitimate way to stay inside SQ. The CSQ lower bound is a clean application of GKK20 plus approximate degree. No fitted parameters, no circularity, no prediction tuned to the answer. The citation pattern looks appropriate.\n\nSoft spots, in proportion:\n\n1. The last paragraph of Theorem 3.1's proof asserts that h1 and h2 are intersections of two halfspaces and hence have VC dimension O(n). That is wrong as stated. h1 is a degree-d polynomial threshold function on the monomial feature space composed with a Hamming-weight threshold, so the relevant VC dimension is n^{O(d)}, with d = O(n^{1/3} log(1/eps)). The advertised sample size can absorb this because log of that VC bound is the same exponent, but the proof does not say so. This is a load-bearing step: it transfers empirical error on P to true error on D. It is repairable, but it must be rewritten.\n\n2. Sample reuse. The L1 subroutine is run on Plight, a subset of P, and then the same P is used to choose c' and evaluate h1 and h2, and later iterations reuse the same samples. Adaptive reuse like that is not covered by a single VC bound and needs an explicit argument — fresh samples per iteration, or a union bound over the algorithm's choices.\n\n3. Minor pseudocode issues. Line 4 of Algorithm 1 defines Pheavy with x in Xlight, which is clearly a typo for Xheavy; Algorithm 2 has similar small slips. These are cosmetic, but they need cleanup before publication.\n\nI agree with the stress-test note: the VC gap is real and the fix is absorbable. I also agree with the reader's overall conditional verdict. The main theorems are likely correct, but the proof is not fully established as written.\n\nWho this is for: anyone working on agnostic learning, SQ/CSQ separations, or polynomial regression. It deserves a serious referee. I would send it to review with an explicit request to check the repaired VC argument, the sample-reuse accounting, and the SQ conditioning details.","headline":"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.","tokens_in":26786,"tokens_out":3048,"would_cite":true,"duration_ms":31414,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Agnostic learning of Boolean disjunctions runs in $2^{\\tilde{O}(n^{1/3})}$ time, beating the old $2^{\\tilde{O}(\\sqrt{n})}$ barrier.","keywords":["agnostic PAC learning","Boolean disjunction","statistical queries","correlational statistical queries","polynomial regression","approximate degree","sample complexity","computational complexity"],"falsifier":"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.","tokens_in":25766,"feed_emoji":"🧠","tokens_out":12205,"duration_ms":97283,"temperature":0.7,"pith_summary":"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.","feed_headline":"Agnostic OR-learning drops to exponent n^(1/3)","feed_subtitle":"The old sqrt(n) upper bound falls, and statistical queries beat correlation queries for this class.","key_machinery":"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))}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the $L_1$-polynomial regression subroutine whose complexity is $n^{O(d)}$ and which is used on the low-weight part.","marker":"[KKMS08]"},{"why":"Provides the $\\Omega(\\sqrt{n})$ approximate-degree lower bound for disjunctions used in the CSQ lower bound.","marker":"[NS94]"},{"why":"Together with [NS94], establishes the $O(\\sqrt{n})$-degree polynomial approximation of disjunctions that motivated the previous $L_1$-regression bound.","marker":"[Pat92]"},{"why":"Supplies the Chebyshev polynomial estimates used to approximate monotone disjunctions on low-weight strings in degree $O(\\sqrt{r})$.","marker":"[Che66]"},{"why":"Provides the CSQ lower bound and poses the open question whether it extends to SQ, which the paper answers negatively.","marker":"[GKK20]"},{"why":"States the $1/2$-approximate degree lower bound for disjunctions used in the appendix's CSQ lower bound proof.","marker":"[BT22]"},{"why":"Provides the distribution-free agnostic boosting algorithm that converts the weak learner into the full agnostic learner.","marker":"[Fel10]"},{"why":"Defines the relation between CSQ and SQ that the paper contrasts with the new distribution-free separation.","marker":"[BF02]"}],"fun_headline_variants":["Agnostic disjunction learning: exponent 1/3 beats sqrt(n)","SQ separates from CSQ: disjunctions in n^(1/3) time","Disjunctions learned agnostically in 2^{n^{1/3}} complexity","From sqrt(n) to n^(1/3): faster agnostic OR learning","Recursive elimination yields n^(1/3) for agnostic disjunctions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Agnostic disjunction learning: exponent 1/3 beats sqrt(n)","SQ separates from CSQ: disjunctions in n^(1/3) time","Disjunctions learned agnostically in 2^{n^{1/3}} complexity","From sqrt(n) to n^(1/3): faster agnostic OR learning","Recursive elimination yields n^(1/3) for agnostic disjunctions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000937,"raw_usage":{"total_tokens":4023,"prompt_tokens":977,"completion_tokens":3046,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":593,"completion_tokens_details":{"reasoning_tokens":2936}},"tokens_in":593,"tokens_out":3046,"duration_ms":18859,"temperature":1.0,"reasoning_tokens":2936,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:40:30.420367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}