Research map / Learning theory and algorithms / Sample complexity
A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
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 polynomial-time learner for gamma-margin halfspaces under Massart noise with sample complexity near-optimal in epsilon (1/(gamma^2 eps^2)) by running online SGD on a carefully chosen sequence of convex clipped-reweighted LeakyReLU-type losses.
Problem
Computationally efficient PAC learning of gamma-margin halfspaces under Massart (bounded) label noise to error eta+epsilon, where prior efficient methods needed about 1/(gamma^4 eps^3) samples.
Approach
Convexify the 0-1 loss by reweighting a LeakyReLU surrogate with a clipped inverse-margin weight 1/max(|v·x|, gamma/2) where v is the previous iterate, giving convex losses whose gradients are subgradients of ||w - w*||^2; then run projected online SGD with a global (not per-region) analysis, so each step needs only O(1) samples and the sample complexity drops to near 1/(gamma^2 eps^2).
Key results
- Main result: learner draws n = O~(1/(eps^2 gamma^2)) samples, runs in O~(dn/eps) time, and returns a halfspace with 0-1 error at most eta+eps with probability 9/10 (informal theorem).
- Prior efficient algorithms required O~(1/(gamma^4 eps^3)) samples; the cutting-plane variant in the appendix achieves O~(1/(gamma^4 eps^2)).
- Sample complexity nearly matches the SQ/low-degree computational lower bound Omega(1/(eps^2 gamma) + 1/(eps gamma^2)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed online-SGD learner instead of the prior efficient algorithm | Learning Massart margin halfspaces · Massart margin halfspaces | sample complexity: \tilde{O}(1/(\gamma^4 \epsilon^3)) -> \widetilde{\Theta}(1/(\gamma^2 \epsilon^2)) | Helped |
| Use the proposed learner instead of the cutting-planes variant | Learning Massart margin halfspaces · Massart margin halfspaces | sample complexity: \widetilde O(1/(\gamma^4\epsilon^2)) -> \widetilde{\Theta}(1/(\gamma^2 \epsilon^2)) | Helped |
Limitations
- Assumes unit-ball support and gamma-margin; general (margin-free) halfspaces left open with suboptimal dimension dependence.
- Final step requires an extra empirical testing stage (N samples per hypothesis, O(dNT) runtime) to select the best iterate.
- Theoretical paper with no experiments.
Experimental setup
Metrics: 0-1 error sample complexity
Baselines: Diakonikolas et al. efficient Massart margin learner (1/(gamma^4 eps^3)) cutting-plane LeakyReLU approach information-theoretic sample complexity
Builds on: LeakyReLU surrogate loss Perceptron algorithm cutting-plane method online convex optimization
Closest papers by meaning
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.95)
- Replicable Learning of Large-Margin Halfspaces (ICML 2024 · similarity 0.91)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.91)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.89)
- Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate (NeurIPS 2026 · similarity 0.89)
- Tight Generalization Bounds for Large-Margin Halfspaces (NeurIPS 2025 · similarity 0.88)
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.