Research map / Learning theory and algorithms / Sample complexity
Reliable Learning of Halfspaces under Gaussian 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 the first reliable agnostic learner for Gaussian halfspaces faster than agnostic learning (d^{O(log(1/alpha))}-type dependence via random walk with polynomial-structure subspace) and an SQ lower bound showing the d^{Omega(log(1/alpha))} dependence is near-optimal.
Problem
Reliable (one-sided-error) agnostic PAC learning of halfspaces under Gaussian marginals, where false positives must be nearly zero while false negatives are compared against the best zero-false-positive halfspace.
Approach
Instead of L1 polynomial regression, condition on negative-labeled points (which are uncorrupted under reliability), show low-degree moments of that conditional distribution correlate with the optimal normal vector, find a low-dimensional subspace from moment tensors via SVD, and run a random walk that updates the hypothesis direction, yielding complexity quasi-polynomial in 1/epsilon for constant
Key results
- Algorithm with sample and runtime d^{O(log(min{1/alpha,1/epsilon}))} * min(2^{log(1/eps)^{O(log(1/alpha))}}, 2^{poly(1/eps)}), beating agnostic d^{O(1/eps^2)} complexity.
- SQ lower bound of d^{Omega(log(1/alpha))} for epsilon < alpha/3, showing the d-exponent is essentially optimal.
- Establishes a computational separation between reliable and standard agnostic learning of Gaussian halfspaces.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed reliable-learning algorithm instead of the prior L1-regression approach | Reliable learning of Gaussian halfspaces · Gaussian halfspaces (reliable agnostic) | computational complexity: d^{O(1/\epsilon^2)} -> polynomial in d and quasi-polynomial in 1/\epsilon (for universal-constant \alpha) | Helped |
Surprising findings
- Reliable learning of Gaussian halfspaces is qualitatively easier than agnostic learning, with complexity closer to the semi-random (Massart) regime than to agnostic learning.
Limitations
- Epsilon-dependence is quasi-polynomial in 1/epsilon rather than polynomial, left open.
- Results are for Gaussian marginals; extension to other distributions is open.
- Algorithm assumes bias alpha is known (handled by guessing).
Experimental setup
Metrics: sample complexity computational complexity SQ dimension / query lower bound
Baselines: L1 polynomial regression (agnostic learner via reduction)
Builds on: Kalai et al. 2012 reliable agnostic learning Diakonikolas et al. Massart halfspace random walk L1 polynomial regression
Closest papers by meaning
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.91)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.90)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.90)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.89)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.89)
- Replicable Learning of Large-Margin Halfspaces (ICML 2024 · 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.