Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
Abstract
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 COPT+ε. 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.
Related
- Efficient Proper Agnostic Learning of Halfspaces
- Gaussian Flow Dynamics: Simulation-Free Neural SDE Learning Beyond One-Time Marginals
- Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness
- Privacy for Free in Efficient Agnostic Halfspace Learning
- Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
BibTeX
@misc{zheng2026proper,
title = {{Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals}},
author = {Zhijie Zheng},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04344},
eprint = {2611.04344},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04344},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
AU - Zhijie Zheng
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04344
UR - https://arxiv.org/abs/2611.04344
AB - 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 COPT+ε. 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.
ER -