# Distribution-Specific Agnostic Conditional Classification With Halfspaces

arXiv: https://arxiv.org/abs/2502.00172 · HTML: https://mlsanity.com/paper/2502.00172/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2025.

## Built on by (most cited first, 2 of 2)

- [Personalized Prediction By Learning Halfspace Reference Classes Under Well-Behaved Distribution](https://mlsanity.com/paper/2509.15592/) (2025)
- [Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals](https://mlsanity.com/paper/2604.26446/) (2026)

## Abstract (arXiv)

We study ``selective'' or ``conditional'' classification problems under an agnostic setting. Classification tasks commonly focus on modeling the relationship between features and categories that captures the vast majority of data. In contrast to common machine learning frameworks, conditional classification intends to model such relationships only on a subset of the data defined by some selection rule. Most work on conditional classification either solves the problem in a realizable setting or does not guarantee the error is bounded compared to an optimal solution. In this work, we consider selective/conditional classification by sparse linear classifiers for subsets defined by halfspaces, and give both positive as well as negative results for Gaussian feature distributions. On the positive side, we present the first PAC-learning algorithm for homogeneous halfspace selectors with error guarantee bigO*√opt, where opt is the smallest conditional classification error over the given class of classifiers and homogeneous halfspaces. On the negative side, we find that, under cryptographic assumptions, approximating the conditional classification loss within a small additive error is computationally hard even under Gaussian distribution. We prove that approximating conditional classification is at least as hard as approximating agnostic classification in both additive and multiplicative form.