Metraipolis › archive › dc_496bbfe6e078
Efficient Proper Agnostic Learning of Halfspaces — arXiv:2611.02344
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02344
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:29:02.598Z
- SHA-256 of the archived text
fec4b9e3f2e41228201c9060d6401ac9e7f28cf7b1a6c20f21fe4cade228c029- Stable URL of this page
https://metraipolis.com/documento/dc_496bbfe6e078
How to cite
Efficient Proper Agnostic Learning of Halfspaces — arXiv:2611.02344 — arXiv (en), https://arxiv.org/abs/2611.02344 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_496bbfe6e078 (Metraipolis archive dc_496bbfe6e078, sha256 fec4b9e3f2e41228201c9060d6401ac9e7f28cf7b1a6c20f21fe4cade228c029)
BibTeX
@misc{dc496bbfe6e078,
title = {Efficient Proper Agnostic Learning of Halfspaces — arXiv:2611.02344},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02344},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_496bbfe6e078; sha256 fec4b9e3f2e41228201c9060d6401ac9e7f28cf7b1a6c20f21fe4cade228c029},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02344. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm1\}^n$. Given query access to an arbitrary function $f:\{\pm1\}^n \to \{\pm1\}$, our algorithm runs in time $\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}$ and outputs a halfspace with error at most $\mathrm{OPT}+\varepsilon$, where $\mathrm{OPT}$ is the error of the best-fitting halfspace for $f$. Previously, even with membership queries, the best known running time was $n^{\mathrm{poly}(1/\varepsilon)}$, 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 $\{\pm1\}^n$ whose running time is polynomial in $n$ with an exponent independent of $\varepsilon$. Combining our algorithm with a boosting argument yields a proper agnostic learner using only random examples. It achieves the same $\mathrm{OPT}+\varepsilon$ guarantee, with running time matching that of Kalai et al.\ up to an additive term depending only on $\varepsilon$. 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 $\varepsilon>0$.
Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.02344 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:03:22.256Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).