Metraipolis › archive › dc_aad7caea625f

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals — arXiv:2611.04344

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04344
License (as archived): CC0-1.0
Archived: 2026-11-04T21:51:36.801Z
SHA-256 of the archived text: 0a9ecf9039cc0e0160b374d08eee65887d16719815e1c7cb7c460ed4b408f9ae
Stable URL of this page: https://metraipolis.com/documento/dc_aad7caea625f

How to cite

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals — arXiv:2611.04344 — arXiv (en), https://arxiv.org/abs/2611.04344 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aad7caea625f (Metraipolis archive dc_aad7caea625f, sha256 0a9ecf9039cc0e0160b374d08eee65887d16719815e1c7cb7c460ed4b408f9ae)

BibTeX

@misc{dcaad7caea625f,
  title = {Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals — arXiv:2611.04344},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04344},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aad7caea625f; sha256 0a9ecf9039cc0e0160b374d08eee65887d16719815e1c7cb7c460ed4b408f9ae},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04344. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most $C\mathrm{OPT}+\varepsilon$. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass $p$, global disagreement is within universal constant factors of $p$ times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.04344 — 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-04T21:38:49.712Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).