{"id":"a86eac5a-6fc1-4170-b0ef-c8e87c34c6bb","arxiv_id":"2501.09851","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Perspectron algorithm matches the random-noise sample complexity for PAC learning halfspaces with Massart noise, and extends to generalized linear models.","lead":"This paper gives a simple algorithm, Perspectron, that learns margin halfspaces under Massart label noise using only O~((epsilon gamma)^-2) samples, matching the rate known for the much simpler random noise model. The same approach extends to generalized linear models with known link functions, improving prior sample complexity bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main halfspace theorem appears correct; the GLM extension has a real gap: Definition 3 permits sign-incompatible sigma, and Lemma 6's B1 inequality fails, making Theorem 4 false as stated.","rationale":"The halfspace half of the paper is solid: I checked Lemma 2's algebra, the potential argument in Lemma 3, the validation step in Lemma 4, and the sample/time accounting in Theorem 3. The reweighting by (|w.x|+gamma)^{-1} is bounded by gamma^{-1}, the progress per step is 2(ell(w)-eta) >= epsilon, and the constants in Lemma 3 work as stated. The known-eta assumption is handled in Appendix A and is standard. So the central claim about Massart halfspaces -- O~(gamma^{-2} epsilon^{-2}) samples and a proper halfspace -- is credible and matches the advertised RCN rate. The GLM extension is where the paper's guarantee breaks. The reader's weakest assumption is correct and can be sharpened: it is not just that the proof of Lemma 6 silently assumes a sign condition; under the definition actually written, the theorem is false. The one-sided asymmetry condition is also used in the wrong direction in the B1 case. A concrete degenerate but admissible sigma == -1 makes Algorithm 2 provably fail on a two-point deterministic distribution, so Theorem 4 cannot be accepted without amending Definition 3 (e.g., requiring sigma(t) >= 0 for t in [0,1] and using a two-sided asymmetry bound). The Claim 1 constant issue is real but secondary; it affects the stated T1 but not the epsilon^{-4} gamma^{-2} rate. Because the main halfspace result is unaffected and the GLM gap is fixable by a definitional repair, I would keep the reader's conditional verdict rather than escalate to a reject.","tokens_in":20699,"tokens_out":21395,"duration_ms":219713,"concrete_test":"Analytic counterexample: take d = 2, gamma = 1, w* = (1,0), D_x uniform on {(1,0),(-1,0)}, labels y = sign(w*.x), and sigma == -1, tau = 0. This satisfies Definition 3. Simulate Algorithm 2: from w = 0 the update is w <- w + 2*lambda*x on the positive example and w <- w on the negative example, so the returned halfspace misclassifies (-1,0) with probability 1/2, contradicting Theorem 4 for epsilon < 1/2. If the authors instead intend sigma(t) >= 0 on [0,1], amend Definition 3 and re-verify Lemma 6's B1 step with a two-sided asymmetry bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Definition 3 only requires sigma non-decreasing with |sigma(t)| - |sigma(-t)| <= tau on [0,1]; it does not require sigma to be sign-compatible. Lemma 6's B1 case needs two things that do not follow: (i) |sigma(w.x)| >= max(0,|sigma(-w.x)|-tau) is the reverse of the stated one-sided asymmetry bound; (ii) |sigma(-w.x)| >= |sigma(w*.x)| from |w.x| >= |w*.x| uses monotonicity of |sigma| on the common sign of -w.x and w*.x, which monotonicity of sigma gives only when sigma(t) >= 0 for t >= 0 (or the analogous sign condition). The degenerate link sigma == -1 satisfies Definition 3 with tau = 0 and makes labels deterministic, but in Algorithm 2 the signal sigma(w_t.x) - y is -2 on positive-labeled examples and 0 on negative-labeled ones. On D_x uniform over {(1,0),(-1,0)} with w* = (1,0), the iterate grows along (1,0) and the negative example is always misclassified, so Theorem 4's claimed error <= opt_RCN + tau/2 + epsilon = epsilon fails. Thus the GLM result is false as stated, not merely missing a constant. Separately, Claim 1's bad threshold E[.] + tau + epsilon/2 leaves only a tau/2 + epsilon/2 gap over Lemma 6's threshold, so the progress invoked is epsilon/2 rather than epsilon; the stated T = 32/(epsilon^4 gamma^2) is off by a constant factor, though the asymptotic rate is unchanged.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies PAC learning of gamma-margin halfspaces with Massart noise. It proposes the Perspectron (Algorithm 1), a perceptron-like update with inverse-margin reweighting, and proves that it learns with error at most eta + epsilon using O~(gamma^{-2} epsilon^{-2}) samples, matching the best known rates for random classification noise. The proof combines a reweighted separating-hyperplane certificate (Lemmas 1-2), a potential-based martingale argument (Lemma 3), and a validation step (Lemma 4). The paper also claims an extension to generalized linear models with a known link function under Massart noise (Definition 3, Lemma 6, Algorithm 2, Theorem 4), with sample complexity O~(gamma^{-2} epsilon^{-4}). The halfspace part is clean, self-contained, and appears correct; the GLM part has a genuine gap in the definition of the admissible link functions and is, as stated, false.","tokens_in":21040,"tokens_out":16902,"duration_ms":172246,"significance":"If the halfspace result stands, it resolves the motivating question in the affirmative and is a substantial improvement over prior proper learners under Massart noise, with explicit constants, high-probability bounds, and a simple algorithm. The inverse-margin reweighting certificate is a nice technical contribution. The GLM extension, if repaired, would be a meaningful generalization of prior work, but in its current form it is incorrect; the significance of the manuscript therefore currently rests primarily on Theorem 3.","major_comments":[{"comment":"The proof of Lemma 6 silently requires sigma to be sign-compatible, but Definition 3 does not impose this. In the A-case, the proof replaces sigma(w* . x) by |sigma(w* . x)| sign(w* . x), which is an equality only when sigma has the same sign as its argument; in the B1-case, the inference |sigma(-w . x)| >= |sigma(w* . x)| from |w . x| >= |w* . x| and monotonicity again requires sigma(t) >= 0 for t >= 0. Definition 3 allows, for example, sigma(t) = -1, which satisfies |sigma(t)| - |sigma(-t)| = 0 with tau = 0. For this sigma, Theorem 4 is false as stated: with D_x uniform on {(1,0),(-1,0)}, w* = (1,0), and deterministic labels y = sign(w* . x), the update in Algorithm 2 is a positive multiple of (1,0) on the positive example and zero on the negative example, so the returned halfspace misclassifies the negative example with probability 1/2 while opt_RCN = tau = 0. The definition must add an explicit sign-compatibility condition, such as sigma(t) >= 0 for all t in [0,1], or the theorem must be restricted to the odd case of Definition 2.","section":"Definition 3 / Lemma 6"},{"comment":"The analysis applies sigma to w_t . x for iterates w_t that are never projected back to the unit ball, but sigma is only defined on [-1,1]. Lemma 6 states the result for arbitrary w in R^d, and Algorithm 2 does not maintain w_t in B_d, so w_t . x may leave the domain of sigma. Either the algorithm should project or otherwise constrain the iterates, or sigma should be extended to the real line; as written the GLM update and the claim \"for any w in R^d\" in Lemma 6 are not well-defined.","section":"Lemma 6 / Algorithm 2"},{"comment":"There is a threshold mismatch in the GLM potential argument. Claim 1 declares an iterate bad when its error is at least opt_RCN + tau + epsilon/2, but Lemma 6 only certifies progress epsilon when the error is at least opt_RCN + tau/2 + epsilon. At the Claim 1 threshold, Lemma 6 gives progress only about epsilon/2 (in the worst case tau = 0), while the potential calculation in Lemma 3 needs progress epsilon to make the stated T = 32/(epsilon^4 gamma^2) suffice. The displayed constants in Claim 1 therefore do not follow from the cited argument; the proof should be written out with the correct progress term and the resulting threshold and T adjusted.","section":"Claim 1 / Theorem 4"}],"minor_comments":[{"comment":"Line 2 sets beta <- 1 - 2 eta, but eta is not defined in the GLM setting of Definition 3, and beta is never used in Algorithm 2; this line should be removed or clarified.","section":"Algorithm 2"},{"comment":"The paragraph after Definition 3 says the noise rate is upper bounded by (1 - sigma(w* . x))/2, but the definition uses (1 - |sigma(w* . x)|)/2; the absolute value should appear consistently.","section":"Definition 3"},{"comment":"The quantity tau is called a \"constant shift\" but it is an asymmetry parameter, not a shift; a less misleading name would help readers.","section":"Definition 3"}],"recommendation":"major_revision","confidential_remarks":"The halfspace theorem is sound and, in my view, publishable. The GLM section as submitted is not correct, but the flaw has an evident local fix (adding a sign-compatibility condition to Definition 3 and rewriting Lemma 6 and Claim 1). I recommend major revision rather than rejection because the main result is defensible and the GLM gap appears fixable, but the authors must not leave Theorem 4 in its current false form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the halfspace result (Theorem 3) is solid: the inverse-margin reweighting (|w.x|+gamma)^{-1} and the Perspectron update are genuinely new, the potential argument in Lemma 3 is clean with explicit constants, and matching the RCN sample complexity is a real advance. The paper is also honest about the concurrent [DZ24] work, which is good practice. Second, the GLM extension has a load-bearing flaw: Definition 3 does not require sigma to be sign-compatible, and Lemma 6's B1 case silently replaces sigma(w.x) with |sigma(w.x)|. That needs sigma(t) >= 0 for t >= 0 (as the odd case of Definition 2 gives). Without it, Theorem 4 is false as stated. A simple counterexample: sigma(t) = -1 for all t, D_x a point mass at x = (-1,0), w* = (1,0), gamma = 0.1. This satisfies Definition 3 with tau = 0, labels are deterministic y = -1, and opt_RCN = 0. Algorithm 2 updates by sigma(w.x) - y, which is 0 at w = 0, so the iterate never moves, and h_0(x) = +1 misclassifies with error 1, not <= epsilon. The stress-test's uniform counterexample does not actually misclassify the negative example, but the point-mass version above kills the theorem. The fix is easy: add the sign condition to Definition 3, then Lemma 6's B1 case goes through with the asymmetry bound. There is also a minor constant slip in Claim 1's threshold (tau + epsilon/2 instead of tau/2 + epsilon), which leaves only epsilon/2 progress but does not change the asymptotic rate. My take: the halfspace half is publishable now; the GLM half needs the definition and Lemma 6 repaired before it can be trusted. The paper deserves a serious referee, not a desk reject. Send it to review with a request for a revised GLM section.","headline":"Halfspace result is real and the proof holds; the GLM extension has a definitional gap that makes Theorem 4 false as stated, though the fix is straightforward.","tokens_in":21624,"tokens_out":16366,"would_cite":true,"duration_ms":155562,"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":"Massart-noised margin halfspaces are learnable with the same $\\tilde O((\\epsilon\\gamma)^{-2})$ sample complexity as random-label noise, via a bounded inverse-margin update.","keywords":["Massart noise","halfspace learning","margin","sample complexity","perceptron","generalized linear models","semi-random noise","proper learning"],"falsifier":"Take $\\sigma(t)=t-1/2$, $w^\\star=(1,0)$, $w=(0,1)$, $x_1=(1,0)$, $x_2=(-1,0)$, $\\gamma=1/2$, and labels drawn with $\\eta(x)=(1-|\\sigma(w^\\star\\cdot x)|)/2$; this satisfies the paper's Definition 3. Numerically evaluate $\\mathbb{E}[(\\sigma(w\\cdot x)-y)x/(|w\\cdot x|+\\alpha\\gamma)]\\cdot(w-w^\\star)$ from Lemma 6: if it falls below $\\epsilon$ while the error-gap condition holds, the GLM theorem as stated is false.","tokens_in":20489,"feed_emoji":"🎯","tokens_out":12572,"duration_ms":131994,"temperature":0.7,"pith_summary":"This paper attacks a gap in the theory of learning halfspaces: noisy labels that are only mildly adversarial (Massart noise, where each point is flipped with probability at most $\\eta$) have historically required more samples than purely random label noise. The authors prove this gap is not real, at least for margin halfspaces, by giving a simple perceptron-style algorithm, the Perspectron, that reaches error $\\eta+\\epsilon$ with $\\tilde O((\\epsilon\\gamma)^{-2})$ samples, the same rate as the best algorithms for the much milder random classification noise. They also extend the method to generalized linear models with a known link function, at a modest extra $\\epsilon^{-2}$ cost. The argument turns on a bounded inverse-margin reweighting of the Leaky-ReLU gradient, which acts as a one-sample unbiased certificate of suboptimality. A reader should care because the result says the harder, more realistic Massart model is no harder sample-wise than the easier random-noise model, for these hypothesis classes.","feed_headline":"A simple update makes Massart noise no harder than random noise","feed_subtitle":"Perspectron matches the best random-noise sample rate for Massart halfspaces and extends to GLMs.","key_machinery":"The central object is the bounded inverse-margin reweighted gradient $g(w;x,y)=(\\beta\\,\\mathrm{sign}(w\\cdot x)-y)x/(|w\\cdot x|+\\gamma)$ for halfspaces, and $(\\sigma(w\\cdot x)-y)x/(|w\\cdot x|+\\alpha\\gamma)$ for GLMs. It is an unbiased estimator of a separating hyperplane: for every suboptimal $w$, its expectation has inner product at least $2\\epsilon$ with $w-w^\\star$. The denominator $|w\\cdot x|+\\gamma$ is the margin padding; it keeps the estimator's Euclidean norm bounded by $2/\\gamma$ while preserving the certificate property, and it turns the hard conditional-sampling step of prior work into one reweighted sample. The second mechanism is the perceptron-style potential argument, which uses $\\Phi_t=\\mathbb{E}[\\mathbf{1}_{\\{\\text{all iterates bad}\\}}\\|w^\\star-w_t\\|^2]$ to convert one-step drift into the sample and iteration bounds.","core_discovery":"Theorem 3 states that if examples come from an $\\eta$-Massart halfspace model with margin $\\gamma$, Algorithm 1 returns $w\\in B_d$ with $\\ell_{0-1}(w)\\le \\eta+\\epsilon$ with probability at least $1-\\delta$, using $O(\\log(1/\\delta)/(\\epsilon^2\\gamma^2)+\\log(1/(\\epsilon\\gamma\\delta))/\\epsilon^2)$ samples and $O(d\\log(1/\\delta)\\log(1/(\\epsilon\\gamma\\delta))/(\\epsilon^4\\gamma^2))$ time. The load-bearing structural lemma (Lemma 2) shows that whenever $\\ell_{0-1}(w)\\ge \\eta+\\epsilon$, the vector $g(w)=\\mathbb{E}[(\\beta\\,\\mathrm{sign}(w\\cdot x)-y)x/(|w\\cdot x|+\\gamma)]$, with $\\beta=1-2\\eta$, satisfies $g(w)\\cdot(w-w^\\star)\\ge 2\\epsilon$; because the denominator is at least $\\gamma$, this certificate is bounded and estimable from a single sample. The update $w_{t+1}\\leftarrow w_t-\\lambda(\\beta\\,\\mathrm{sign}(w_t\\cdot x_t)-y_t)x_t/(|w_t\\cdot x_t|+\\gamma)$ is then analyzed through a perceptron-style potential $\\|w^\\star-w_t\\|^2$, yielding the matching bound. For Massart GLMs, the same plan works with $\\sigma(w\\cdot x)-y$ in place of $\\beta\\,\\mathrm{sign}(w\\cdot x)-y$, and a smaller denominator $\\alpha\\gamma$ with $\\alpha=\\epsilon/(2-\\epsilon)$, which costs an extra $\\epsilon^{-2}$ factor in samples.","pith_inferences":["The inverse-margin padding is not tied to Leaky-ReLU; any convex surrogate whose reweighted excess equals the classification error could yield analogous certificates for other noise models, such as Tsybakov noise.","The extra $\\epsilon^{-2}$ in the GLM bound looks like an artifact of the $\\epsilon$-small padding $\\alpha\\gamma$; the paper's own appendix sketches two routes to remove it, so a plausible conjecture is that the true GLM rate is also $\\tilde O((\\epsilon\\gamma)^{-2})$.","A practical reading is that the update needs only one pass over samples and one inner product per step, making the Perspectron a drop-in replacement for perceptron in noisy linear classification, though the paper reports no empirical tests."],"forward_implications":["The proper learner for $\\gamma$-margin Massart halfspaces now matches the $\\tilde O((\\epsilon\\gamma)^{-2})$ sample complexity of the best random-classification-noise learners.","The error target $\\eta+\\epsilon$, the known noise ceiling, is the right benchmark; lower bounds prevent competing with the true average noise rate, so matching this target is the meaningful resolution.","The same method yields a polynomial sample complexity for Massart generalized linear models with known link function, $\\tilde O(\\gamma^{-2}\\epsilon^{-4})$, improving on the prior unspecified polynomial dependence.","The algorithm is proper and needs only $\\eta$ up to an $\\epsilon$ error; when $\\eta$ is unknown, a standard discretization over $\\beta=1-2\\eta$ preserves the guarantees."],"supporting_citations":[{"why":"Supplies the identity $\\mathbb{E}_y[\\ell_\\lambda(-y w\\cdot x)]=(\\Pr[\\mathrm{sign}(w\\cdot x)\\neq y]-\\lambda)|w\\cdot x|$ used in Lemma 1, and gives the prior improper Massart halfspace learner that this work improves.","marker":"[DGT19]"},{"why":"Introduces the Massart GLM model and the Leaky-ReLU certificate framework; its proper learner is the main baseline whose sample complexity Theorem 1 improves.","marker":"[CKMY20]"},{"why":"Gives the $\\tilde O((\\epsilon\\gamma)^{-2})$ sample bound for random classification noise that Theorem 1 matches, and provides a lower bound cited for tightness.","marker":"[DDK+23]"},{"why":"Provides the other recent random-noise learner achieving the $\\tilde O((\\epsilon\\gamma)^{-2})$ sample complexity matched here.","marker":"[KIT+23]"},{"why":"Establishes the $\\tilde\\Omega(\\gamma^{-2}\\epsilon^{-1})$ information-theoretic lower bound that the paper cites as evidence its $\\epsilon$ and $\\gamma$ dependence is tight.","marker":"[MN06]"},{"why":"Develops the certificate framework for semi-random noise that the separating-hyperplane approach builds on.","marker":"[DKTZ20b]"}],"fun_headline_variants":["Massart noise as easy as random for margin halfspaces","Perspectron matches random-noise sample rate under Massart","Simple update: Massart halfspaces match random-noise rates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the margin: every example lies at distance at least $\\gamma$ from the optimal boundary, and for the GLM extension the known link function must be nonnegative on $[0,1]$, a sign condition the paper's bounded-asymmetry definition does not explicitly state.","fun_headline_variants_meta":{"raw":{"variants":["Massart noise as easy as random for margin halfspaces","Perspectron matches random-noise sample rate under Massart","Simple update: Massart halfspaces match random-noise rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000409,"raw_usage":{"total_tokens":2178,"prompt_tokens":1059,"completion_tokens":1119,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":1064}},"tokens_in":675,"tokens_out":1119,"duration_ms":10808,"temperature":1.0,"reasoning_tokens":1064,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:39:42.392679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $\\sigma(t)=t-1/2$, $w^\\star=(1,0)$, $w=(0,1)$, $x_1=(1,0)$, $x_2=(-1,0)$, $\\gamma=1/2$, and labels drawn with $\\eta(x)=(1-|\\sigma(w^\\star\\cdot x)|)/2$; this satisfies the paper's Definition 3. Numerically evaluate $\\mathbb{E}[(\\sigma(w\\cdot x)-y)x/(|w\\cdot x|+\\alpha\\gamma)]\\cdot(w-w^\\star)$ from Lemma 6: if it falls below $\\epsilon$ while the error-gap condition holds, the GLM theorem as stated is false.","supporting_citations":[],"review_version":1}