Constant-factor agnostic learning of affine halfspaces under log-concave data

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

Machine Learning

Summary

This paper addresses the challenge of learning halfspaces — simple dividing lines or planes that separate data — when the data is noisy and follows a specific spread known as a log-concave distribution. The authors provide an algorithm that learns a single halfspace with error close to the best possible, without needing prior knowledge of the data’s mean or spread. They achieve this by carefully analyzing regions where classifiers disagree and robustly estimating the data distribution even under noisy labels. Their approach provides guaranteed accuracy with resources growing reasonably with problem size and desired confidence.

What this means in practice

  • For machine learning engineers: Develop classification models that robustly learn linear decision boundaries under noisy and high-dimensional data without knowing data parameters upfront.
  • For data scientists in finance: Build interpretable risk classification systems that handle realistic noise and log-concave features like asset returns under limited labeled data.

Authors

Zhijie Zheng

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 $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.