{"id":"91ffff67-37d8-42ec-9e00-ecce4dad6927","arxiv_id":"2501.09691","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An online stochastic gradient descent algorithm learns gamma-margin halfspaces under Massart noise with O~(1/(gamma^2 epsilon^2)) samples, nearly matching the information-computation tradeoff lower bound.","lead":"A new algorithm learns noisy labeled halfspaces with near-optimal sample efficiency: it uses about 1/(margin squared times error squared) samples, matching the theoretical lower bound for efficient algorithms. This settles, up to log factors, how many samples are needed to learn margin halfspaces when labels are corrupted by Massart noise.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The final selection step in Theorem 2.1 uses N = Θ(1/(ε(1-2η))) samples, but candidates can be far from the Bayes optimal, so empirical-error selection requires Ω(log(T/δ)/ε²) samples; the stated N is insufficient.","rationale":"The reader's conditional verdict is justified: the final hypothesis-selection step is the load-bearing weakness. I agree with the reader that the stated N is wrong, but the reason is more subtle than a naive Hoeffding bound over T+1 hypotheses. Massart noise does not automatically give a 1/(ε(1-2η)) fast rate for empirical-error selection; that rate only holds when the candidate hypotheses are near the Bayes optimal. The algorithm's candidates are only guaranteed to reach error η+ε, and since η is an upper bound on the noise rather than the actual optimum, opt can be drastically smaller. In that regime the loss difference between two candidates with errors around η has variance ~1/4, and Ω(1/ε²) samples are necessary. This is precisely the reader's flagged technical error, and it is correct. The margin assumption, which the reader lists as the weakest assumption, is not the primary issue: it is explicitly assumed and used correctly in Claims 2.3 and 2.4. The main result's sample complexity survives if N is corrected, because T = Θ(log(1/δ)/(ε²γ²)) dominates N for small ε and γ≤1. The runtime bound, however, must be adjusted. The verdict remains CONDITIONAL, hence no change from the reader's verdict.","tokens_in":18058,"tokens_out":45439,"duration_ms":495502,"concrete_test":"Fix η=0.49, opt=0, ε=10^{-4}, δ=0.01, and take two candidate hypotheses with true errors 0.49+ε/2 and 0.49+ε, whose loss difference has variance ≈0.98 (realizable by two margin halfspaces on a suitable distribution with γ=1). For N1 = C/(ε(1-2η)) = 50C/ε and N2 = log(2/δ)/ε², repeatedly draw N samples, compute empirical errors, and record how often the worse hypothesis has lower empirical error. If the failure probability at N1 is bounded away from 0 as ε→0 while at N2 it is below δ, the paper's claimed N is refuted and the corrected bound is validated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2.1 states N = Θ(log(1/(γδ))/(ε(1-2η))) and the proof's last paragraph claims this suffices for Step (5), 'due to [MN06].' That fast-rate bound requires the compared hypotheses to have small excess risk over the Bayes optimal, so the Bernstein variance condition E[Z²] ≤ B·E[Z] holds. Here the candidates wt only need error ≤ η+ε, while the true optimal error opt may be much smaller than η. Thus a 'good' candidate can have error η+ε/2 with opt=0, and another candidate can have error η+ε while disagreeing with the first on a set of probability near 2η. The 0-1 loss difference then has variance ~1/4, not O(ε/(1-2η)). Distinguishing these two Bernoulli(≈0.5) means requires N = Ω(1/ε²), exactly the Hoeffding union bound over T+1 hypotheses; the paper's N is too small by a factor of 1/ε. Correcting N to Θ(log(T/δ)/ε²) preserves the total sample complexity n=N+T = O~(1/(ε²γ²)), since T dominates, but it changes the runtime bound O(dNT) by an extra 1/ε factor. As written, the final selection can select a hypothesis with true error > η+ε, so the proof of Theorem 2.1 does not go through without this correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies PAC learning of gamma-margin halfspaces under Massart noise and proposes an online projected SGD algorithm with a final empirical-error selection step. The main claimed result, Theorem 2.1, is a sample complexity of O~(1/(gamma^2 epsilon^2)) and error eta+epsilon, nearly matching SQ/low-degree lower bounds. The proof decomposes the stochastic gradient into a direction that correlates with w-w* and a zero-mean estimation error, uses a potential argument on ||w_t-w*||^2 with subgaussian concentration, and then selects the best empirical candidate among T+1 iterates.","tokens_in":18240,"tokens_out":26778,"duration_ms":269711,"significance":"If the main theorem holds, this is a substantial improvement over the previous efficient algorithm with O~(1/(gamma^4 epsilon^3)) samples, and it matches the best known algorithmic guarantees for Random Classification Noise. The structural lemma (Lemma 2.2) and the potential-decrease argument are clean and self-contained, and the algorithm is simple and practical. The lower-bound evidence is from SQ/low-degree hardness, so 'near-optimal' is appropriately qualified. The main proof up to the identification of one good candidate is sound; the final selection step, however, contains a load-bearing error that must be corrected before the stated theorem is valid.","major_comments":[{"comment":"The stated bound N = Theta(log(1/(gamma delta))/(epsilon(1-2 eta))) is not sufficient for the final selection step. The candidates w_t are only known to include a hypothesis with error at most eta+epsilon; they need not be close to the Bayes classifier, and the excess over the Bayes error can be as large as eta even when the optimal error is 0. The [MN06] fast-rate/Bernstein condition therefore does not apply when comparing an arbitrary candidate with the best candidate in the finite set. Uniformly controlling the empirical 0-1 errors of T+1 hypotheses requires N = Omega(log(T/delta)/epsilon^2) by a Hoeffding union bound. With this corrected N, the total sample count n = N+T remains O~(1/(epsilon^2 gamma^2)) because T dominates, but the stated runtime O(dNT) gains an extra factor of 1/epsilon. As written, the proof of Theorem 2.1 does not rule out selecting a hypothesis with true error above eta+epsilon.","section":"Section 2, Step (5) and final paragraph of Theorem 2.1"},{"comment":"Even after correcting the selection sample size, the proof concludes err_D(w_hat) <= min_t err_D(w_t) + epsilon <= eta + 2 epsilon, while Theorem 2.1 promises eta + epsilon. The internal accuracy parameter must be rescaled, for example by replacing epsilon with epsilon/2 throughout the SGD target and the selection tolerance, or the theorem statement must be adjusted accordingly. This is a statement-level but local fix.","section":"Section 2, proof of Theorem 2.1, last paragraph"}],"minor_comments":[{"comment":"Condition (i) as written says y = sign(w* . x) for (x,y)~D, which is inconsistent with Massart noise; it should say that the Massart-corrupted label is generated from the clean label sign(w* . x), or that sign(w* . x) is the target concept in Definition 1.1.","section":"Definition 1.2"},{"comment":"The theorem statement gives N = Theta(log(1/(gamma delta))/(epsilon(1-2 eta))), while the proof's last paragraph uses N = O(log(T/delta)/(epsilon(1-2 eta))). These two expressions should be reconciled after the correction in the major comments.","section":"Theorem 2.1 vs. proof of Theorem 2.1"},{"comment":"There are several formatting artifacts and typos in this passage, including a stray 'a' after 'Inequality (4)' and '/bracehtipupleft' fragments, which should be cleaned up.","section":"Equation (4) and surrounding text"},{"comment":"In the proofs of these claims, the notation W(w . x) is sometimes written without the second argument gamma/2; the definition in Equation (3) uses W(v . x, gamma/2), so the proofs should consistently write W(w . x, gamma/2).","section":"Claims 2.3 and 2.4"},{"comment":"The argument that the final distance satisfies ||w_{T+1}-w*||^2 <= 0 should explicitly account for the initial distance ||w_0-w*||^2, which can be as large as 4; this is absorbed by choosing constants in T appropriately, but as written the equality to 0 is only up to universal constants.","section":"Proof of Theorem 2.1, constant in T"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about the final selection step is real and I agree with it: the paper's N is too small by a factor related to 1/epsilon, and the proof as written does not establish the theorem's guarantee. The correction is straightforward and preserves the main sample-complexity claim, so this should be a major revision rather than a rejection. The authors should also fix the eta+epsilon versus eta+2epsilon inconsistency in the final paragraph."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the main result is real and the proof is mostly sound, but Theorem 2.1 as stated has a genuine bug in the final selection step. The fix is known and doesn't change the sample complexity, but it does add a 1/epsilon factor to the runtime, and the current appeal to [MN06] fast rates is not justified for the candidate set.\n\nWhat's new: the paper gives an efficient online SGD learner for gamma-margin halfspaces under Massart noise using O~(1/(gamma^2 epsilon^2)) samples, improving on the previous O~(1/(gamma^4 epsilon^3)) from CKMY20 and nearly matching the SQ/low-degree lower bounds. The structural lemma (gradient strongly correlates with w-w* when error exceeds eta+epsilon) is clean, and the potential argument is self-contained. Step size and iteration count are chosen analytically, with no fitted constants. I checked the pointwise claims in Appendix C; they hold. Independent concurrent work CKST24 obtained the same bounds, which corroborates that the target is right.\n\nSoft spots: (1) The selection step. The paper states N = Theta(log(1/(gamma delta))/(epsilon(1-2eta))) via [MN06]. That fast-rate bound needs a Bernstein condition that fails here: candidates can have error eta+epsilon while opt is near 0, so the loss difference between two candidates can have variance on the order of 1. Distinguishing T+1 hypotheses requires N = Omega(log(T/delta)/epsilon^2) by Hoeffding. With N corrected, n = N+T is still O~(1/(epsilon^2 gamma^2)) since T dominates, but the runtime O(dNT) picks up an extra 1/epsilon factor. This should be fixed in a revision; the main theorem's sample complexity survives, but the proof as written does not. (2) The abstract says the sample complexity 'nearly matches' the lower bound, but the upper bound has an extra 1/gamma relative to the Omega(1/(gamma epsilon^2)) bound adapted from DDK+23b. That gap should be stated precisely rather than glossed over. (3) Minor: the algorithm needs eta and gamma as inputs; that is standard in this line and not a real flaw.\n\nVerdict: this is a serious paper with a correct core and one fixable technical error. It deserves a careful referee and likely acceptance after the selection-step correction. I would cite it for the SGD analysis and would bring it to a reading group to discuss the fast-rate pitfall.","headline":"Solid near-optimal SGD learner for Massart margin halfspaces, with a real but fixable bug in the final hypothesis-selection step.","tokens_in":18919,"tokens_out":3162,"would_cite":true,"duration_ms":32034,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives a computationally efficient algorithm that learns $\\gamma$-margin halfspaces with Massart noise using $\\tilde{O}(1/(\\gamma^2\\epsilon^2))$ samples, nearly matching the known lower bound for efficient learners.","keywords":["Massart noise","margin halfspaces","sample complexity","online SGD","information-computation tradeoff","PAC learning","convex surrogate losses","bounded label noise"],"falsifier":"Concrete check: compute $g_1(w,x)\\cdot(w-w^*)$ and compare with $2(\\mathrm{err}(w,x)-\\eta)$ on a fine grid of unit vectors $x$ with $|w^*\\cdot x| \\ge \\gamma$ and weight vectors $w$ with $\\|w\\| \\le 1$ in $d=2$ or $d=3$; a single pair $(w,x)$ where the inequality fails—especially on the region $|w\\cdot x| < \\gamma/2$, where the clipping and margin condition do the work—would invalidate the structural lemma (Claims 2.3 and 2.4) on which the sample bound rests.","tokens_in":17726,"feed_emoji":"🎯","tokens_out":19562,"duration_ms":162848,"temperature":0.7,"pith_summary":"This paper establishes that $\\gamma$-margin halfspaces can be learned in polynomial time under Massart label noise using only $\\tilde{O}(1/(\\gamma^2\\epsilon^2))$ samples, nearly matching the information-computation tradeoff lower bound for efficient learners. Since the information-theoretically optimal sample complexity is $\\tilde{\\Theta}(1/(\\gamma^2\\epsilon))$, the result pins down the extra factor $1/\\epsilon$ as the price of computational efficiency for this problem. The algorithm is projected online SGD on a sequence of convex surrogate losses, followed by choosing the iterate with smallest empirical error; prior efficient algorithms required roughly $1/(\\gamma^4\\epsilon^3)$ samples, so the improvement is substantial in both $\\epsilon$ and $\\gamma$. The margin assumption is load-bearing: extending to general halfspaces is explicitly left open, with the authors noting that their approach would yield dimension-suboptimal sample complexity. The proof shows that, whenever the current classifier's error exceeds $\\eta+\\epsilon$, each stochastic gradient step reduces the distance to the optimal halfspace, which is why the near-optimal sample bound holds.","feed_headline":"Near-optimal sample complexity for learning noisy halfspaces","feed_subtitle":"An SGD algorithm closes most of the gap between the information-theoretic limit and efficient learners.","key_machinery":"The load-bearing construction is the clipped reweighted convex loss $L_{\\lambda,v}(w) = \\mathbb{E}_{x,y}[\\ell_\\lambda(w,x,y)/\\max(|v\\cdot x|,\\gamma/2)]$, where $\\ell_\\lambda(w,x,y)=(1\\{\\mathrm{sign}(w\\cdot x)\\ne y\\}-\\lambda)|w\\cdot x|$ is the LeakyReLU surrogate for the 0-1 loss. Each round fixes $v=w_t$, so the loss stays convex in $w$ while the $|w\\cdot x|$ factor reweights errors toward confident points. The clipping by $\\gamma/2$ is where the margin assumption enters: for inputs whose current margin is small, the target halfspace's margin $\\gamma$ makes $|w^*\\cdot x|/\\max(|w_t\\cdot x|,\\gamma/2) \\ge 1$, forcing the gradient's sign to point toward $w^*$. The proof splits the stochastic gradient into a signal part $G_1$ satisfying $G_1\\cdot(w-w^*) \\ge 2(\\mathrm{err}(w)-\\eta)$ and a zero-mean estimation part, then bounds the cumulative estimation error with subgaussian concentration via Hoeffding's lemma.","core_discovery":"Theorem 2.1 is the paper's central claim: for any distribution on the unit sphere satisfying $\\eta$-Massart noise with respect to an unknown halfspace $\\mathrm{sign}(w^*\\cdot x)$ with margin $\\gamma$, Algorithm 1 returns a hypothesis $\\hat{w}$ with $\\mathrm{err}_D(\\hat{w}) \\le \\eta+\\epsilon$ with probability at least $1-\\delta$ using $n = O(N+T) = \\tilde{O}(1/(\\epsilon^2\\gamma^2))$ samples and $O(dNT)$ time. The algorithm is projected stochastic gradient descent with step size proportional to $\\gamma^2\\epsilon$, applied to the loss $\\ell_\\lambda(w,x,y)W(w_t\\cdot x,\\gamma/2)$, where $\\ell_\\lambda$ is the LeakyReLU proxy $(1\\{\\mathrm{sign}(w\\cdot x)\\ne y\\}-\\lambda)|w\\cdot x|$ and $W(a,b)=1/\\max(a,b)$; a final step selects, among the iterates, the one with smallest empirical 0-1 error. The proof constructs a potential $\\Phi(w)=\\|w-w^*\\|^2$ and shows the gradient has a component that decreases this potential by an amount proportional to $(\\mathrm{err}(w_t)-\\eta)$ whenever $\\mathrm{err}(w_t) \\ge \\eta+\\epsilon$, while the estimation noise is subgaussian and bounded in total. The sample complexity nearly matches the known SQ and low-degree lower bounds for the problem and matches the best known bound for the special case of random classification noise.","pith_inferences":["Our testable prediction: on synthetic $\\gamma$-margin distributions with constant Massart noise, the empirical sample complexity of Algorithm 1 with step size $c\\gamma^2\\epsilon$ should scale as $1/(\\gamma^2\\epsilon^2)$; a sweep over $\\gamma$ and $\\epsilon$ would confirm the theorem's stated dependence or expose hidden constants.","Our transfer suggestion: the clipping reweighting $1/\\max(|v\\cdot x|,\\gamma/2)$ is a general template for convexifying objectives that are nonconvex only through a denominator, and may be useful in margin-based active learning or regression with bounded noise.","Our open-problem reading: replacing the known margin with a dimension-dependent slack in the clipping is the natural route to remove the margin assumption; the paper says this needs new ideas, but the proof structure shows where such slack could enter."],"forward_implications":["If Theorem 2.1 is correct, the computational sample complexity of learning margin halfspaces with Massart noise is $\\tilde{\\Theta}(1/(\\gamma^2\\epsilon^2))$ up to logarithmic factors, leaving only the gap to the information-theoretic bound $\\tilde{\\Theta}(1/(\\gamma^2\\epsilon))$ as the measurable price of computational efficiency.","The algorithm is simple enough to implement—projected SGD with fixed step size $c\\gamma^2\\epsilon$ plus a final empirical-error selection—so the near-optimal sample bound is a practical guarantee rather than an existence statement.","The result matches the sample complexity previously known only for the easier Random Classification Noise special case, indicating that the harder Massart model does not incur additional sample cost in the margin regime.","Because every step of the proof uses the margin assumption, the method does not directly yield a dimension-optimal learner for general halfspaces; the paper states this extension is open and would require new ideas."],"supporting_citations":[{"why":"Supplies the information-theoretic sample complexity benchmark for Massart noise and the estimator used in the final hypothesis-selection step.","marker":"[MN06]"},{"why":"Introduced the LeakyReLU convex surrogate for the 0-1 loss on which the paper's loss sequence is built.","marker":"[DGT19]"},{"why":"Gave the previous best efficient algorithm with sample complexity O~(1/(γ⁴ε³)), the bound this work improves.","marker":"[CKMY20]"},{"why":"Provided SQ and low-degree evidence that efficient learners need quadratic 1/ε sample dependence, the lower bound nearly matched here.","marker":"[DDK+23a]"},{"why":"Strengthened the near-optimal lower-bound evidence for Gaussian halfspaces with random classification noise.","marker":"[DDK+23b]"},{"why":"Supplies Hoeffding's lemma used to show the cumulative estimation error of the stochastic gradients is subgaussian.","marker":"[Ver18]"}],"fun_headline_variants":["Simple SGD learns noisy halfspaces with near-optimal samples","Near-optimal sample complexity for Massart noise via SGD","SGD achieves near-optimal sample complexity for noisy halfspaces","Nearly optimal sample complexity for Massart halfspaces","A simple SGD learner nearly matches the efficient lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the $\\gamma$-margin condition—every clean example satisfies $|w^*\\cdot x| \\ge \\gamma$, with the algorithm given $\\gamma$ and the noise ceiling $\\eta$ in advance; if examples can approach the separating hyperplane arbitrarily closely, the sign-reversal argument that makes each gradient point toward $w^*$ stops working and the $\\tilde{O}(1/(\\gamma^2\\epsilon^2))$ sample bound no longer follows from the proof.","fun_headline_variants_meta":{"raw":{"variants":["Simple SGD learns noisy halfspaces with near-optimal samples","Near-optimal sample complexity for Massart noise via SGD","SGD achieves near-optimal sample complexity for noisy halfspaces","Nearly optimal sample complexity for Massart halfspaces","A simple SGD learner nearly matches the efficient lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000904,"raw_usage":{"total_tokens":3935,"prompt_tokens":1035,"completion_tokens":2900,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":2818}},"tokens_in":651,"tokens_out":2900,"duration_ms":17905,"temperature":1.0,"reasoning_tokens":2818,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:46:48.911628+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Concrete check: compute $g_1(w,x)\\cdot(w-w^*)$ and compare with $2(\\mathrm{err}(w,x)-\\eta)$ on a fine grid of unit vectors $x$ with $|w^*\\cdot x| \\ge \\gamma$ and weight vectors $w$ with $\\|w\\| \\le 1$ in $d=2$ or $d=3$; a single pair $(w,x)$ where the inequality fails—especially on the region $|w\\cdot x| < \\gamma/2$, where the clipping and margin condition do the work—would invalidate the structural lemma (Claims 2.3 and 2.4) on which the sample bound rests.","supporting_citations":[],"review_version":1}