{"id":"7fe860e6-397d-4136-abc1-bd6376e9f2b6","arxiv_id":"2505.13708","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An efficient agnostic learner for halfspaces over subgaussian isotropic log-concave distributions returns a classifier with error opt+O(ε) and boundary volume O(r+ε) in time d^{~O(1/ε^2)}.","lead":"This paper gives a fast algorithm for learning halfspaces (linear classifiers) that remain correct under small adversarial perturbations, under broad random input distributions. It is the first to match the speed of standard non-robust learning while guaranteeing near-optimal robustness, a central question in adversarial machine learning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim C.11's mean-estimation concentration does not follow from the cited Chebyshev bound; the partition step's 1−O(δ) guarantee may fail unless corrected.","rationale":"I read the paper in good faith and the overall architecture is coherent: the convex-programming stage, the Carathéodory rounding, the local corrector, and the random-partition step each have substantial supporting analysis, and the claimed complexity match with non-robust polynomial regression is plausible. The reader's weakest_assumption correctly identifies Appendix C.3, the random-projection partition, as the least secure part of the proof. My concern is more specific than the reader's: within that step, Claim C.11 is the load-bearing lemma that turns 10d^3 samples into coordinate-accurate mean estimates for the eight indicator functions. The proof as written cites Chebyshev and claims a probability of 0.01 d^{−4}, but the variance bound available gives only 0.1/d per coordinate; the union bound over 8d coordinates then yields a constant failure probability per attempt, which breaks the boosting argument in Claim C.12. This is a concrete, checkable gap rather than a vague worry about external theorems. I am not asserting fraud or even that the theorem is false; the claim is likely correct via subexponential concentration, and the rest of the proof seems consistent. Because the manuscript's written proof does not establish the required high-probability mean accuracy, the verdict should be conditional on a corrected proof of Claim C.11 (or an explicit alternative concentration argument). If the corrected argument confirms d^{−3}-type failure, the reader's ACCEPT stands; if it only gives constant per-attempt failure, the theorem's high-probability guarantee is not established as stated.","tokens_in":36353,"tokens_out":49195,"duration_ms":436793,"concrete_test":"Re-derive Claim C.11 for an isotropic log-concave D using a correct tail bound for x_i f(x), e.g., Bernstein's inequality on the subexponential norm of log-concave coordinates. Determine whether the 8d-dimensional union bound yields failure ≤ O(d^{−3}) or only a constant 0.8. If only constant, simulate the partition step with mean errors of magnitude ~1 instead of 1/d and check whether the final 1−O(δ) guarantee fails; if a Bernstein-type bound restores d^{−3}, the argument goes through unchanged.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The partition argument in Appendix C.3 hinges on Claim C.11, which asserts that with 10d^3 samples, for all 8 indicators f and all d coordinates, |avg x_i f(x) − E x_i f(x)| ≤ 1/d with probability 1−O(d^{−3}). The proof applies Chebyshev using Var(x_i)=1. But the quantity averaged is x_i f(x), not x_i; its variance is only bounded by E[x_i^2]=1. Chebyshev therefore gives Pr(|avg−E| > 1/d) ≤ 1/(|T|·(1/d)^2) = 1/(10d^3 · d^{−2}) = 0.1/d, not 0.01 d^{−4}. Union over 8d coordinates gives a constant per-attempt failure probability ≈ 0.8, not O(d^{−3}). This matters because Claim C.12 uses the d^{−3} bound to justify that each random-projection attempt succeeds with high probability; with only constant success probability, log(1/δ) repetitions cannot reach total failure δ (0.8^{log(1/δ)} = δ^{0.32} >> δ). If the means are not coordinate-accurate, the subspace P is not orthogonal to the true means, so β1 in Claim C.6 becomes O(1) and the partition estimates inherit an O(1/ε) error rather than O(ε). The central guarantees err ≤ opt + O(ε) and Boundary ≤ O(r+ε) therefore rest on an unproved concentration statement. The claim is probably salvageable with Bernstein/subexponential tail bounds for isotropic log-concave vectors, but as written the proof is invalid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies agnostic learning of halfspaces with adversarial robustness guarantees when the input marginal is isotropic, subgaussian, and log-concave. The main theorem claims an improper learner that, with sample and time complexity d^{O(log^2(1/epsilon)/epsilon^2)}, outputs a Boolean hypothesis h with classification error opt + O(epsilon) and boundary volume O(r + epsilon) for perturbation radius r. The algorithm proceeds in three stages: (1) a convex program learns a real-valued degree-O(log^2(1/epsilon)/epsilon^2) polynomial with small ell_1 error and small noise-sensitivity constraints; (2) a rounding step uses Carathéodory's theorem to find a four-function mixture of thresholds, then partitions the domain by a random projection; (3) a local corrector flips labels at points with high estimated local noise sensitivity to obtain the final robust hypothesis. The proof combines the halfspace polynomial approximator of [DGJ+09], the random projection concentration theorem of [DHV06], log-concave thin-shell estimates, and self-contained analyses of the three new components.","tokens_in":36660,"tokens_out":15683,"duration_ms":145616,"significance":"If the main theorem is correct, it is a strong result: it gives the first improper agnostic halfspace learner whose output has boundary volume O(r) at perturbation radius r, matching the complexity of standard polynomial regression and, up to polylogarithmic factors in the exponent, the statistical query lower bound. The separation of the argument into a constrained real-valued regression, a constant-size randomized partitioning step, and a local corrector is conceptually clean and likely to be of independent interest. The paper also contains substantial self-contained proofs for the feasibility of the convex program and for the correctness of the local corrector, and it discusses verifiable robustness in a way that is naturally supported by the structured output. The main result, once the technical issues below are repaired, would be a meaningful contribution to computational learning theory.","major_comments":[{"comment":"The stated mean-estimation guarantee does not follow from the cited Chebyshev argument, and this is load-bearing for the partition step. The quantity being averaged is x_i f(x), not x_i; its variance is only bounded by E[x_i^2] = 1. For T of size 10d^3 and threshold 1/d, Chebyshev gives Pr(|avg - E| > 1/d) <= Var(x_i f) / (|T| * d^{-2}) <= 1/(10d) per pair (f,i), not 0.01 d^{-4}. A union bound over the 8d pairs gives a constant failure probability, not O(d^{-3}). Since Claim C.12 relies on coordinate-wise mean accuracy 1/d to make the subspace P nearly orthogonal to the true means, losing this accuracy gives beta_1 = O(1) instead of O(sqrt(1/d)); then Claim C.6 only provides an interval-mass error O(beta_1/beta_3) = O(1/epsilon), which destroys the O(epsilon) partitioning accuracy and hence the final err <= opt + O(epsilon) and Boundary <= O(r + epsilon) guarantees. The claim is probably repairable using subgaussian/Bernstein concentration for products x_i f(x) under the subgaussian log-concave marginal, but as written the proof is invalid.","section":"Theorem 3.4, proof of the robustness bound"},{"comment":"The displayed chain 'E_x[RobustIndicator_i(x)] = Pr[hat_phi <= 0.1] = 1 - Pr[hat_phi > 0.9] = ... >= 1 - (10/9) cNS' is mathematically invalid, because Pr[hat_phi <= 0.1] equals 1 - Pr[hat_phi > 0.1], not 1 - Pr[hat_phi > 0.9]. The intended lower bound can still be recovered: Markov's inequality applied to hat_phi gives Pr[hat_phi > 0.1] <= 10 E[hat_phi], and the epsilon-accuracy of hat_phi transfers this to the underlying noise sensitivity, so the final boundary-volume bound is salvageable. However, the proof as written contains a genuine error at a central point and must be corrected.","section":"Theorem 3.4, proof of the robustness bound"}],"minor_comments":[{"comment":"The algebraic transition to the failure probability '1/epsilon^5 * exp(-Omega(epsilon^6 d))' does not follow from the preceding line, which has 'ln(1/epsilon)/epsilon^4 * exp(-Omega(epsilon^5 d / ln(1/epsilon)))'. The conclusion is not affected under the assumption epsilon >= d^{-1/7}, since either form gives an exponentially small failure probability, but the displayed derivation should be corrected.","section":"Appendix C.3, Claim C.12"},{"comment":"The statement of Fact A.2 mixes the sample S and the set T: the high-probability event is over a sample S, but the empirical expectation on the right-hand side is written as 1/|T| sum_{x in T}. The two symbols should be reconciled.","section":"Appendix A.1, Fact A.2"},{"comment":"The proof contains a malformed probability expression 'Pr_{x~D} Pr_Theta Pr_{t~Theta}[...]' and the constant 0.025 should be (0.05)^2. These are presentation issues; the final bound is still obtained by Hoeffding's inequality and a Markov argument.","section":"Appendix C.2, Claim C.3(c)"},{"comment":"The truncation event is written informally as an equality '||P x||_2 / sqrt(d/2) = 1 +/- ...'; it should be written as an interval membership. This is a notation issue and does not affect the argument.","section":"Appendix C.3, Claim C.10"},{"comment":"The quantities errt, NSt, and isot are defined with respect to pt(x) = sign(p(x) - t), but pt itself is only defined later on the same line. Reordering would improve readability.","section":"Algorithm 4, line 9"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the three high-level components are well motivated, but the current manuscript should not be accepted as is: the partition step relies on a concentration claim that is false as proved, and the proof of Theorem 3.4 contains an invalid equality chain. Both issues appear localized and fixable within the scope of the paper. I would support acceptance after the authors supply a correct concentration argument for Claim C.11 (e.g., subgaussian/Bernstein tails with an adequate sample size) and clean up the robustness proof in Theorem 3.4. The reported complexity parameters, the use of Carathéodory for the four-threshold mixture, and the local-correction argument are otherwise coherent, so I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is straightforward: this is the first algorithm to agnostically learn halfspaces with opt+O(ε) error and boundary volume O(r+ε) under subgaussian isotropic log-concave marginals in d^{Õ(1/ε^2)} time, matching the non-robust learner and, up to polylogs, the SQ lower bound. That is a significant result. The architecture is clean: noise-sensitivity-constrained L1 regression, Carathéodory rounding to four thresholds, and a local corrector. The new components are analyzed in detail, and the paper correctly uses known tools (DGJ+09, DHV06, thin-shell). I believe the central claims are correct in spirit.\n\nThe soft spot is Claim C.11 in Appendix C.3. The proof applies Chebyshev to x_i f(x) using Var(x_i)=1, which does not control Var(x_i f(x)). With the actual bound Var(x_i f(x)) ≤ 1, Chebyshev gives a per-coordinate failure probability of 0.1/d; union over 8d functions gives a constant per-attempt failure probability, not O(d^{-3}). That breaks the boosting argument in Claim C.12, which needs per-attempt failure ≤ 1/2 to get δ after log(1/δ) attempts. The mistake is not cosmetic—the mean estimates feed directly into the choice of the random projection subspace, and the partition guarantees rest on them.\n\nThat said, the claim is likely true and repairable. Since x_i is subgaussian for isotropic log-concave distributions, x_i f(x) inherits subgaussian tails with a universal constant, and a Bernstein bound gives exp(-Ω(d)) per-coordinate failure, which unions cleanly over 8d coordinates. So the paper needs a corrected concentration argument, not a new idea. I'd flag this to the authors rather than reject.\n\nMinor issues: the ε ≥ d^{-1/7} condition appears in Theorem 3.1 but not in the abstract; there are some notation slips; and there is no code, which is fine for a theory paper. No circularity problems; the self-citation [LRV22] is for inspiration only.\n\nThis paper deserves a serious referee. My recommendation: send it to peer review, with a request to fix the concentration proof. Once fixed, it is a strong paper.","headline":"Real result with a real proof gap: the main theorem likely stands, but the partition step's concentration claim as written is wrong.","tokens_in":37269,"tokens_out":5228,"would_cite":true,"duration_ms":48095,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W20","52A20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Halfspaces can be learned adversarially robustly under log-concave marginals at the same complexity as ordinary agnostic learning.","keywords":["adversarial robustness","agnostic learning","halfspaces","log-concave distributions","boundary volume","noise sensitivity","polynomial threshold functions","local correction"],"falsifier":"Simulate the partition step on an explicit isotropic log-concave distribution, such as the uniform distribution on the Euclidean ball or on the cube, with the four error-indicator sets computed from the algorithm, and measure the difference between the true projected mass of each set in the Gaussian intervals and the claimed $w_i \\pm O(\\varepsilon)$. If for some set of mass $\\Omega(\\varepsilon)$ at $\\varepsilon = d^{-1/7}$ the deviation exceeds a large constant multiple of $\\varepsilon$, the partition guarantee and hence the theorem's error and robustness conclusions would fail.","tokens_in":36112,"feed_emoji":"🛡️","tokens_out":8756,"duration_ms":93934,"temperature":0.7,"pith_summary":"This paper shows that halfspaces, the simple classifiers of the form sign(u·x−τ), can be learned under subgaussian isotropic log-concave input distributions while also being adversarially robust. Standard polynomial regression learns halfspaces agnostically in time $d^{O(\\log^2(1/\\varepsilon)/\\varepsilon^2)}$ but outputs a polynomial threshold function that can have boundary volume $\\Omega(1)$ even for tiny perturbation radii. The paper gives an algorithm that achieves error at most $\\mathrm{opt}+O(\\varepsilon)$ and boundary volume $O(r+\\varepsilon)$ at perturbation radius $r$, for $\\varepsilon \\ge d^{-1/7}$, with probability at least $1-O(\\delta)$, in time $\\mathrm{poly}(d^{O(\\log^2(1/\\varepsilon)/\\varepsilon^2)}\\log(1/\\delta))$. If correct, adversarial robustness for halfspaces under these marginals costs no additional time or sample complexity, matching the best non-robust agnostic learner and, up to polylog factors, the statistical query lower bound.","feed_headline":"Robust halfspace learning now matches plain learning speed","feed_subtitle":"New algorithm returns error opt+O(ε) with boundary volume O(r+ε) under log-concave marginals.","key_machinery":"The argument runs on three linked devices. LEARN REALVALUED solves a convex program over degree-$O(\\log^2(1/\\varepsilon)/\\varepsilon^2)$ polynomials, minimizing $\\ell^1$ error subject to constraints on empirical noise sensitivity and a convex surrogate for isolation probability; a polynomial approximating the optimal halfspace is the feasibility witness. COMPUTE CLASSIFIER uses Carathéodory's theorem to replace the averaging over uniformly random rounding thresholds by a weighted mixture of four deterministic thresholds, then partitions the domain into four intervals of Gaussian mass along a random unit vector, with concentration of random projections ensuring each error and robustness set is partitioned with the correct weights. Finally, ROBUSTNESS LCA flips a point's label when an $\\varepsilon$-accurate estimate of the probability that a Gaussian perturbation of radius $10r$ changes the label exceeds $0.8$; the low-noise-sensitivity guarantees ensure few points are flipped, while the flipped points are constant on radius-$r$ balls.","core_discovery":"The central claim is Theorem 3.1: ROBUST LEARN, given sample access to a distribution on $\\mathbb{R}^d \\times \\{\\pm 1\\}$ whose $\\mathbb{R}^d$-marginal is subgaussian, isotropic, and log-concave, returns a Boolean hypothesis $h$ with $\\mathrm{err}_D(h) \\le \\mathrm{opt}+O(\\varepsilon)$ and $\\mathrm{Boundary}_{D,r}(h) \\le O(r+\\varepsilon)$, with probability $1-O(\\delta)$, in time $\\mathrm{poly}(d^{O(\\log^2(1/\\varepsilon)/\\varepsilon^2)}\\log(1/\\delta))$. The strategy is deliberately improper: rather than forcing the output to be a halfspace, it builds a piecewise polynomial-threshold classifier from four rounded versions of one low-degree polynomial, each restricted to a Gaussian-weighted interval along a random direction and each passed through a local corrector that flips labels only at points with high local noise sensitivity.","pith_inferences":["The same pipeline—convex regression under noise-sensitivity constraints, a Carathéodory mixture of thresholds, and local label correction—could plausibly yield robust learners for other concept classes with small boundary volume under log-concave marginals, though the paper does not claim this.","The local corrector alone could serve as a black-box post-processing robustness filter for arbitrary classifiers: flipping points whose estimated label-change probability is high reduces boundary volume at an error cost controlled by the isolation probability.","The four-region construction is a general way to convert a randomized rounding scheme into a fixed constant-size partition without paying more than $O(r)$ in boundary volume; testing it at the boundary condition $\\varepsilon = d^{-1/7}$ would clarify whether that technical restriction is inherent or an artifact of the proof."],"forward_implications":["Agnostically learning halfspaces with adversarial robustness under isotropic subgaussian log-concave marginals has complexity $d^{O(\\log^2(1/\\varepsilon)/\\varepsilon^2)}$, matching the non-robust baseline and the statistical query lower bound up to polylog factors.","The robust risk of the returned hypothesis is at most $\\mathrm{opt}+O(r+\\varepsilon)$, because robust risk is bounded by classification error plus boundary volume.","If $\\mathrm{P}=\\mathrm{BPP}$, the algorithm can be turned into a learner with verifiable robustness: a deterministic verifier rejects every point with an adversarial perturbation inside radius $r$ and accepts almost all points of the learned hypothesis.","The guarantee holds for any subgaussian isotropic log-concave marginal, not just the Gaussian, whereas prior proper robust learners for halfspaces were specific to the Gaussian setting."],"supporting_citations":[{"why":"Supplies the low-degree polynomial approximating a halfspace whose average $\\ell^1$ error under subgaussian isotropic log-concave marginals makes the convex program feasible.","marker":"[DGJ+09]"},{"why":"The polynomial-regression baseline whose running time is matched; its randomized rounding at a uniform threshold gives the initial error guarantee without robustness.","marker":"[KKMS08]"},{"why":"The concentration theorem for random projections that lets the four-region Gaussian partition preserve the mass of error and robustness sets.","marker":"[DHV06]"},{"why":"Carathéodory's theorem, used to show that any convex combination of the rounded-function performance vectors is realizable by four thresholds.","marker":"[Car07]"},{"why":"Thin-shell estimates for isotropic log-concave measures, used to verify that conditioned error and robustness sets lie in a thin shell after projection.","marker":"[GM11]"},{"why":"The VC-dimension bound for polynomial threshold functions underpinning the uniform-convergence estimates for the noise sensitivity approximator.","marker":"[Ant95]"}],"fun_headline_variants":["Robust halfspaces matched to plain learning speed","Halfspace robustness now costs no extra time","Agnostic halfspace learning with O(r+ε) boundary volume","Subgaussian log-concave halfspaces, robust and fast","New algorithm: robust halfspaces with minimal boundary"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the claim that the error and robustness sets of the rounded functions, when viewed through a random projection, look practically Gaussian at scale $\\varepsilon$, so that four carefully chosen intervals capture exactly the right fraction of each set—a property that is established only after truncation and mean estimation, and only under the technical condition $\\varepsilon \\ge d^{-1/7}$.","fun_headline_variants_meta":{"raw":{"variants":["Robust halfspaces matched to plain learning speed","Halfspace robustness now costs no extra time","Agnostic halfspace learning with O(r+ε) boundary volume","Subgaussian log-concave halfspaces, robust and fast","New algorithm: robust halfspaces with minimal boundary"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000833,"raw_usage":{"total_tokens":3699,"prompt_tokens":1073,"completion_tokens":2626,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":2544}},"tokens_in":689,"tokens_out":2626,"duration_ms":20155,"temperature":1.0,"reasoning_tokens":2544,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:11:32.324419+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the partition step on an explicit isotropic log-concave distribution, such as the uniform distribution on the Euclidean ball or on the cube, with the four error-indicator sets computed from the algorithm, and measure the difference between the true projected mass of each set in the Gaussian intervals and the claimed $w_i \\pm O(\\varepsilon)$. If for some set of mass $\\Omega(\\varepsilon)$ at $\\varepsilon = d^{-1/7}$ the deviation exceeds a large constant multiple of $\\varepsilon$, the partition guarantee and hence the theorem's error and robustness conclusions would fail.","supporting_citations":[],"review_version":1}