Research map / Learning theory and algorithms / Sample complexity
Smoothed Agnostic Learning of Halfspaces over the Hypercube
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.
Extends smoothed agnostic learning of halfspaces to the Boolean hypercube using random bit-flip perturbations, giving an efficient (quasi-polynomial-in-1/(σε) exponent) learner under strictly sub-exponential marginals.
Problem
Agnostic learning of Boolean halfspaces is computationally hard even for weak learning; existing smoothed agnostic frameworks use additive Gaussian perturbations that do not apply to discrete {±1}^n domains.
Approach
Define a smoothed agnostic benchmark where inputs are perturbed by independent random bit flips, and reduce learning to L1 polynomial regression by approximating the noise-smoothed halfspace via a rerandomization trick, Berry–Esseen Gaussian approximation for regular weight tails, and critical-index decomposition for irregular heads.
Key results
- Under strictly sub-exponential marginals on {±1}^n, halfspaces are agnostically learnable in the bit-flip smoothed model with N = n^{poly((λ/σε)^{(1+1/α)^3})} log(1/δ) samples and poly(n,N) runtime.
- Noise sensitivity bound NS_δ(f) ≤ (5/4)√δ for halfspaces over product spaces is used to show L1 approximation error of T_{1-ρ}f to f is O(√ρ).
Limitations
- Only single halfspaces; does not extend directly to intersections of halfspaces
- Requires strictly sub-exponential tail assumptions on the input marginal
- Degree and runtime degrade as smoothing parameter σ becomes small
Experimental setup
Baselines: Kalai et al. L1 regression (uniform hypercube) Chandrasekaran et al. 2024 smoothed agnostic learner Diakonikolas et al. log-concave halfspace learner
Builds on: L1 polynomial regression smoothed agnostic learning (Chandrasekaran et al. 2024) Bonami-Beckner noise operator critical index analysis
Closest papers by meaning
- 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.87)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.87)
- Testably Learning Polynomial Threshold Functions (NeurIPS 2024 · similarity 0.87)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.87)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.86)
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.