Research map / Learning theory and algorithms / Sample complexity
Robust learning of halfspaces under log-concave marginals
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a d^{Õ(1/ε²)}-time agnostic learner for halfspaces under subgaussian isotropic log-concave distributions that outputs an improper Boolean hypothesis with error OPT+O(ε) and boundary volume O(r+ε), via convex PTF regression under noise-sensitivity constraints, randomized partitioning, and a local corrector.
Problem
Agnostically learning halfspaces with adversarial robustness (small boundary volume at perturbation radius r) under subgaussian isotropic log-concave distributions, efficiently and without outputting a halfspace.
Approach
Augments polynomial regression with l1 regression under noise-sensitivity convex constraints, a randomized partition of the domain into constant-many intervals each rounded at a different threshold (found via Caratheodory and LP), and a local corrector that smooths the function into an adversarially robust hypothesis.
Key results
- Algorithm agnostically learns halfspaces with error OPT+O(eps) and boundary volume O(r+eps) in time and samples d^{Õ(1/eps^2)}, matching polynomial regression's complexity.
- Proper-type guarantee not obtained: output is an improper Boolean hypothesis built from PTFs, partitioned into four rounded pieces.
- Under P=BPP-type assumptions, robustness of output can be verified deterministically in the corollary on verifiable robustness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add noise-sensitivity-constrained regression, structured partitioning and rounding, and local correction to polynomial regression | RobustLearn for halfspaces · Subgaussian isotropic log-concave marginals | boundary volume: O(r + \eps) | Helped |
Surprising findings
- Generic polynomial threshold functions of degree 1/eps^2 can have boundary volume Omega(1) even at tiny radius, so standard polynomial regression gives no robustness guarantee.
Limitations
- Output is improper (a Boolean combination of PTFs), not a halfspace; proper robust learning remains open.
- Requires eps >= d^{-1/7} and a subgaussian isotropic log-concave marginal.
- Deterministic robustness corollary relies on complexity assumption P=BPP.
Experimental setup
Metrics: agnostic error (OPT + O(eps)) boundary volume at radius r
Baselines: polynomial regression
Builds on: polynomial regression local computation algorithms Gaussian proper agnostic learning of halfspaces
Closest papers by meaning
- Provable Robustness of Adversarial Training for Learning Halfspaces with Noise (ICML 2021 · similarity 0.90)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.87)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.87)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.86)
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.86)
- Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.