Research map / Learning theory and algorithms / Sample complexity
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
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.
Proposes the Perspectron, a simple proper perceptron-like learner with inverse-margin reweighting that learns gamma-margin Massart halfspaces with O~((eps*gamma)^-2) samples, and extends it to Massart GLMs with O~(gamma^-2 eps^-4) samples.
Problem
PAC learning gamma-margin halfspaces under Massart (semi-random) noise with fine-grained sample complexity, matching RCN-level bounds, and extending to Massart generalized linear models.
Approach
Uses a bounded separating hyperplane certificate built from the Leaky-ReLU gradient reweighted by (|w·x|+gamma)^{-1}, estimable from a single sample, and runs a perceptron-like stochastic update with per-sample perspective scaling, then selects among iterates on held-out data.
Key results
- Perspectron learns gamma-margin Massart halfspaces to error eta+eps with O~((eps*gamma)^-2) samples and O~(d gamma^-2 eps^-4) time, matching RCN sample complexity.
- Massart GLM extension achieves O~(gamma^-2 eps^-4) samples, improving on the prior state-of-the-art runtime bound of order L^4 gamma^-4 eps^-6 for halfspaces.
- Prior best proper Massart halfspace learners required O~(gamma^-4 eps^-3) samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use bounded inverse-margin reweighting (|w·x| + γ)^{-1} in place of the prior band-conditioned certificate | Massart halfspace learning · Massart halfspaces with margin γ | sample complexity: \widetilde{O}(\gamma^{-4}\epsilon^{-3}) -> \widetilde{O}(\gamma^{-2}\epsilon^{-2}) | Helped |
| Use Perspectron for Massart halfspaces rather than the prior proper learner | Massart halfspace learning · Massart halfspaces with margin γ | sample complexity: \gamma^{-4}\epsilon^{-3} -> \gamma^{-2}\epsilon^{-2} | Helped |
| Extend the Perspectron approach to known-link Massart GLMs | GLM Perspectron · Massart GLMs with margin γ | sample complexity: \widetilde{\Omega}(L^4 \gamma^{-4}\epsilon^{-6}) -> \widetilde{O}(L^2\gamma^{-2}\epsilon^{-4}) | Helped |
| Use the GLM-specific denominator |w·x| + εγ/(2−ε) instead of |w·x| + γ | GLM Perspectron · Massart GLMs with margin γ | sample complexity: \widetilde{O}(\gamma^{-2}\epsilon^{-2}) -> \widetilde{O}(\gamma^{-2}\epsilon^{-4}) | Hurt |
Surprising findings
- The Massart noise model with an oblivious adversary can be learned as fast as random classification noise, with no sample complexity penalty for the more general noise.
Limitations
- GLM sample complexity has an extra eps^-2 overhead compared to the halfspace case, left as an open question.
- Requires knowledge of the link function sigma; unknown-link setting not handled.
- Error guarantee is eta+eps rather than the information-theoretic optimum opt+eps.
Experimental setup
Metrics: zero-one loss sample complexity runtime
Baselines: DGT19 CKMY20 random classification noise learners
Builds on: Leaky-ReLU surrogate loss for Massart noise certificate framework for semi-random noise Perceptron
Closest papers by meaning
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.95)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.90)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.89)
- Replicable Learning of Large-Margin Halfspaces (ICML 2024 · similarity 0.88)
- Robust learning of halfspaces under log-concave marginals (NeurIPS 2025 · similarity 0.87)
- Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate (NeurIPS 2026 · similarity 0.87)
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.