Pith. sign in

REVIEW 2 major objections 5 minor 13 references

Robust learning of halfspaces under log-concave marginals

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Halfspaces can be learned adversarially robustly under log-concave marginals at the same complexity as ordinary agnostic learning.

desk verdict Real result with a real proof gap: the main theorem likely stands, but the partition step's concentration claim as written is wrong. read the letter →

arxiv 2505.13708 v1 pith:V3AL27RI submitted 2025-05-19 cs.DS cs.LG

Jane Lange , Arsen Vasilyan This is my paper · ORCID
classification cs.DScs.LG MSC 68Q3268W2052A20
keywords adversarialrobustnessagnosticlearninghalfspaceslog-concavedistributionsboundaryvolumenoisesensitivitypolynomialthresholdfunctionslocalcorrection
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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}$.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

2 major / 5 minor

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.

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 (2)
  1. [Theorem 3.4, proof of the robustness bound] 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.
  2. [Theorem 3.4, proof of the robustness bound] 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.
minor comments (5)
  1. [Appendix C.3, Claim C.12] 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.
  2. [Appendix A.1, Fact A.2] 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.
  3. [Appendix C.2, Claim C.3(c)] 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.
  4. [Appendix C.3, Claim C.10] 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.
  5. [Algorithm 4, line 9] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain rests on external theorems and self-contained analyses.

full rationale

The paper's central claim—agnostically learning halfspaces with boundary volume O(r+epsilon)—is derived from three components, each of which is either proved in the paper or imported from independent external work. The polynomial approximation input comes from [DGJ+09] (Fact B.10) and is applied to subgaussian isotropic log-concave marginals with a self-contained proof of the required L1 accuracy (Claim B.8). The randomized partitioning step invokes the external projection concentration theorem of [DHV06] (Theorem C.5), the thin-shell estimate of [GM11] (Fact C.7), and Carathéodory's theorem [Car07], none of which is authored by the present authors. The local corrector, ROBUSTNESS LCA, is analyzed directly in Theorem C.1, including the key implication that low estimated local noise sensitivity at a point implies label constancy within radius r. The only self-citation, [LRV22], is described as 'in the fashion of' and is not load-bearing: the corrector used here is a different, explicitly analyzed algorithm. The noise-sensitivity relaxation is not assumed to equal boundary volume; instead, Theorem C.1 and the proof of Theorem 3.4 establish the boundary-volume bound from noise-sensitivity and isolation-probability bounds through proved inequalities. One reviewer concern, that Claim C.11 bounds Var(x_i f(x)) by Var(x_i)=1 when applying Chebyshev, is a potential proof gap in mean estimation, not a circular reduction: it does not make any claimed quantity equal to its input by construction, nor does it introduce a fitted parameter renamed as a prediction. Similarly, the partition check in COMPUTE CLASSIFIER is a validation of a concentration guarantee, not a fit of the conclusion. Accordingly, no step exhibits self-definition, fitted-input-as-prediction, load-bearing self-citation, imported uniqueness, or ansatz-smuggling by citation, and the result is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper relies on standard external theorems and explicitly stated distributional assumptions. No ad hoc constants are fitted to data or chosen to make the target theorem true by construction; the absolute constants are chosen large but are not fitted parameters.

assumptions (8)
  • domain assumption The R^d-marginal of D is isotropic, subgaussian, and log-concave (Theorem 3.1).
    This is the main distributional hypothesis. It is used for the halfspace noise-sensitivity bound (B.4.1), the thin-shell concentration (Fact C.7), and the projection concentration theorem.
  • domain assumption The accuracy parameter satisfies ε ≥ d^{-1/7} (Theorem 3.1).
    This technical condition makes the failure probability in Claim C.12 exponentially small in d^{1/7}; without it, the partition guarantee might fail.
  • standard math VC dimension and uniform convergence bounds for degree-k polynomial threshold functions (Fact A.1, A.2, E.5, E.6).
    Used to justify the ε-accurate local noise sensitivity approximator and generalization of empirical error.
  • standard math [DHV06] Theorem 11, concentration of random projections (Theorem C.5).
    The core tool for the randomized partitioning step; it guarantees that projected conditional distributions are close to Gaussian.
  • standard math Thin-shell concentration for isotropic log-concave variables (Fact C.7, C.9).
    Used to verify the thin-shell assumption of the projection concentration theorem after truncation.
  • standard math Carathéodory's theorem (Theorem C.4).
    Guarantees that the desired mixture of rounded functions can be represented by at most four thresholds.
  • standard math [DGJ+09] univariate polynomial approximation of the sign function (Fact B.10).
    Used to construct a halfspace-approximating polynomial that satisfies the constraints of the convex program.
  • standard math Log-concavity is preserved under convolution and projection (Fact B.1, B.3).
    Used to show that the distribution of x+10r z remains subgaussian log-concave, enabling the polynomial approximation claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust learning of halfspaces under log-concave marginals." pith.science (2026). https://pith.science/paper/V3AL27RI

@misc{pith2026250513708,
  author       = {Pith},
  title        = {Pith review of: Robust learning of halfspaces under log-concave marginals},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V3AL27RI}},
  note         = {Machine review of arXiv:2505.13708}
}
abstract

We say that a classifier is \emph{adversarially robust} to perturbations of norm $r$ if, with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. The \emph{boundary volume} is the probability that a point falls within distance $r$ of a point with a different label. This work studies the task of computationally efficient learning of hypotheses with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$. Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$. Such concept classes are efficiently learnable by polynomial regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $\Omega(1)$, even for $r \ll 1$. We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume $O(r+\varepsilon)$ at radius of perturbation $r$. The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: a) performing the $\ell_1$-error regression under noise sensitivity constraints, b) a structured partitioning and rounding step that returns a Boolean classifier with error $\textsf{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and c) a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 9 canonical work pages

  1. [7]

    Planting undetectable backdoors in machine learning models

    [GKVZ22] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE,

    work page 2022

  2. [9]

    Certified robustness to adversarial examples with differential privacy

    [LAG+19] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672,

    work page 2019

  3. [11]

    Fast local computation algo- rithms

    [RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algo- rithms. arXiv preprint arXiv:1104.1377,

    arXiv

  4. [12]

    Are adversarial examples inevitable? arXiv preprint arXiv:1809.02104,

    [SHS+18] Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint arXiv:1809.02104,

    arXiv

  5. [2008]

    On robustness to adversarial examples and polynomial optimization

    [ADV19] Pranjal Awasthi, Abhratanu Dutta, and Aravindan Vijayaraghavan. On robustness to adversarial examples and polynomial optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro...

    work page 2019

  6. [2009]

    Bounded Independence Fools Halfspaces

    Number: arXiv:0902.3757 arXiv:0902.3757 [cs]. [DHV06] Sanjoy Dasgupta, Daniel Hsu, and Nakul Verma. A concentration theorem for projec- tions. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, pages 114–121,

    work page Pith review arXiv

  7. [2011]

    Goodfellow, Jonathon Shlens, and Christian Szegedy

    [GSS14] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. CoRR, abs/1412.6572,

    arXiv

  8. [2012]

    Evasion attacks against machine learning at test time

    [BCM+13] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML ...

    work page 2013

Show all 13 references
  1. [2014]

    Goodfellow, and Rob Fergus

    [SZS+14] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors,2nd International Conference on Learning Representations, ICLR 2014, B...

    2014

  2. [2018]

    The total variation dis- tance between high-dimensional gaussians with the same mean

    [DMR18] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation dis- tance between high-dimensional gaussians with the same mean. arXiv preprint arXiv:1810.08693,

    arXiv

  3. [2019]

    Second-order adversarial attack and certifiable robustness

    [LCWC] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. 11 [LRV22] Jane Lange, Ronitt Rubinfeld, and Arsen Vasilyan. Properly learning monotone func- tions via local correction. In 2022 IEEE 63rd Annual Symposi...

    2022

  4. [2021]

    Nearly tight bounds for robust proper learning of halfspaces with a margin

    10 [DKM19] Ilias Diakonikolas, Daniel Kane, and Pasin Manurangsi. Nearly tight bounds for robust proper learning of halfspaces with a margin. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Ne...

    2019

  5. [2023]

    [GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari

    Accessed: 2025-05-11 https://web.stanford.edu/class/stats300b/Notes/vc-dimension.pdf. [GKK23] Aravind Gollakota, Adam R Klivans, and Pravesh K Kothari. A moment-matching approach to testable learning and a new characterization of rademacher complexity. In Proceedings of the 55...

    2025

Pith tools

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