Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

A sample-only proper constant-factor agnostic learner for arbitrary affine halfspaces under every isotropic log-concave marginal. For arbitrary binary labels, the algorithm returns an affine halfspace or a constant with classification error C OPT + epsilon, using samples and real-arithmetic operations polynomial jointly in dimension, inverse accuracy, and log inverse failure probability. The proof combines robust minority-cap normalization, a classical zonoid-depth dual objective, a balanced log-concave quantile restriction, and a minority-mass local-to-global disagreement inequality. It uses the quadratic-form variance theorem of Letwin, fixed-degree robust moment estimation of Kothari and Steurer, and a translated homogeneous learning primitive. No finite-bit, general monotone-single-index, or practical-runtime guarantee is asserted.