# Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin

arXiv: https://arxiv.org/abs/1908.11335 · HTML: https://mlsanity.com/paper/1908.11335/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2019.

## Built on by (most cited first, 8 of 8)

- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Formulating Robustness Against Unforeseen Attacks](https://mlsanity.com/paper/2204.13779/) (2022)
- [Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random](https://mlsanity.com/paper/2501.09851/) (2025)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)

## Abstract (arXiv)

We study the problem of em properly learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning d-dimensional halfspaces on the unit ball within misclassification error α · OPTγ + ε, where OPTγ is the optimal γ-margin error rate and α ≥ 1 is the approximation ratio. We give learning algorithms and computational hardness results for this problem, for all values of the approximation ratio α ≥ 1, that are nearly-matching for a range of parameters. Specifically, for the natural setting that α is any constant bigger than one, we provide an essentially tight complexity characterization. On the positive side, we give an α = 1.01-approximate proper learner that uses O(1/(ε2γ2)) samples (which is optimal) and runs in time poly(d/ε) · 2^tildeO(1/γ2). On the negative side, we show that em any constant factor approximate proper learner has runtime poly(d/ε) · 2^(1/γ)2-o(1), assuming the Exponential Time Hypothesis.