# Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

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

- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [A Unified Theoretical Analysis of Private and Robust Offline Alignment: from RLHF to DPO](https://mlsanity.com/paper/2505.15694/) (2025)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Online Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/2405.12958/) (2024)
- [Provably Extracting the Features from a General Superposition](https://mlsanity.com/paper/2512.15987/) (2025)

## Abstract (arXiv)

In this paper we revisit some classic problems on classification under misspecification. In particular, we study the problem of learning halfspaces under Massart noise with rate η. In a recent work, Diakonikolas, Goulekakis, and Tzamos resolved a long-standing problem by giving the first efficient algorithm for learning to accuracy η + ε for any ε > 0. However, their algorithm outputs a complicated hypothesis, which partitions space into poly(d,1/ε) regions. Here we give a much simpler algorithm and in the process resolve a number of outstanding open questions: (1) We give the first proper learner for Massart halfspaces that achieves η + ε. We also give improved bounds on the sample complexity achievable by polynomial time algorithms. (2) Based on (1), we develop a blackbox knowledge distillation procedure to convert an arbitrarily complex classifier to an equally good proper classifier. (3) By leveraging a simple but overlooked connection to evolvability, we show any SQ algorithm requires super-polynomially many queries to achieve mathsfOPT + ε. Moreover we study generalized linear models where mathbbE[Y|X] = σ(langle w^*, Xrangle) for any odd, monotone, and Lipschitz function σ. This family includes the previously mentioned halfspace models as a special case, but is much richer and includes other fundamental models like logistic regression. We introduce a challenging new corruption model that generalizes Massart noise, and give a general algorithm for learning in this setting. Our algorithms are based on a small set of core recipes for learning to classify in the presence of misspecification. Finally we study our algorithm for learning halfspaces under Massart noise empirically and find that it exhibits some appealing fairness properties.