Efficient Proper Agnostic Learning of Halfspaces
Abstract
We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on {±1}n. Given query access to an arbitrary function f:{±1}n → {±1}, our algorithm runs in time poly(n)+2poly(1/ε) and outputs a halfspace with error at most OPT+ε, where OPT is the error of the best-fitting halfspace for f. Previously, even with membership queries, the best known running time was npoly(1/ε), achieved by the sample-based algorithm of Kalai, Klivans, Mansour, and Servedio (FOCS 2005). Our algorithm is the first agnostic halfspace learner under the uniform distribution on {±1}n whose running time is polynomial in n with an exponent independent of ε. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same OPT+ε guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on ε. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time 2o(n) for every fixed ε>0.
Related
- Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
- Privacy for Free in Efficient Agnostic Halfspace Learning
- Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
- Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
- Agnostic Model-Assisted Estimation with Machine Learning for Survey Data
BibTeX
@misc{de2026efficient,
title = {{Efficient Proper Agnostic Learning of Halfspaces}},
author = {Anindya De and Elchanan Mossel and Shivam Nadimpalli and Joe Neeman},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02344},
eprint = {2611.02344},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02344},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Efficient Proper Agnostic Learning of Halfspaces
AU - Anindya De
AU - Elchanan Mossel
AU - Shivam Nadimpalli
AU - Joe Neeman
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02344
UR - https://arxiv.org/abs/2611.02344
AB - We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on {±1}^n. Given query access to an arbitrary function f:{±1}^n → {±1}, our algorithm runs in time poly(n)+2^poly(1/ε) and outputs a halfspace with error at most OPT+ε, where OPT is the error of the best-fitting halfspace for f. Previously, even with membership queries, the best known running time was n^poly(1/ε), achieved by the sample-based algorithm of Kalai, Klivans, Mansour, and Servedio (FOCS 2005). Our algorithm is the first agnostic halfspace learner under the uniform distribution on {±1}^n whose running time is polynomial in n with an exponent independent of ε. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same OPT+ε guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on ε. To our knowledge, this is the first sample-based proper agnostic learner in the Boolean setting with running time 2^o(n) for every fixed ε>0.
ER -