Research map / Learning theory and algorithms / Sample complexity
An Efficient Tester-Learner for Halfspaces
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 fully polynomial-time tester-learners for halfspaces under Gaussian/strongly log-concave marginals, with Massart noise (opt+eps) and agnostic noise (O(opt)+eps for Gaussian, quasipolynomial for general strongly log-concave).
Problem
Efficient testable learning of halfspaces under Massart or adversarial label noise with respect to Gaussian or strongly log-concave target marginals, achieving near-optimal error in polynomial time.
Approach
Combines nonconvex SGD on a smooth ramp-loss surrogate (finding approximate stationary points) with label-aware tests on the distribution conditioned on bands around candidate vectors, using moment matching to certify that stationary points are near-optimal halfspaces.
Key results
- For Massart noise, a poly(d, 1/eps, 1/(1-2eta))-time tester-learner achieves opt+eps for any isotropic strongly log-concave target marginal.
- For agnostic noise under the standard Gaussian, the tester-learner achieves O(opt)+eps in poly(d, 1/eps) time.
- For general strongly log-concave targets under agnostic noise, error O~(opt)+eps is achieved in quasipolynomial time.
Limitations
- For general strongly log-concave targets in the agnostic setting, the guarantee requires quasipolynomial time rather than polynomial time.
- Agnostic guarantee is O(opt)+eps only for the Gaussian; for general strongly log-concave it is weaker (O~(opt)).
Experimental setup
Metrics: excess error over opt sample and time complexity
Builds on: testable learning (Rubinfeld and Vasilyan 2022) moment matching for fooling functions of halfspaces (Diakonikolas et al.) nonconvex SGD for Massart noise halfspaces (Diakonikolas et al.)
Closest papers by meaning
- Efficient Testable Learning of Halfspaces with Adversarial Label Noise (NeurIPS 2023 · similarity 0.94)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.90)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.90)
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.89)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.88)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 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.