# Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 27 Aug 2026.

## Builds on (most cited first, 14 of 14)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [The Optimal Sample Complexity of Multiclass and List Learning](https://mlsanity.com/paper/2604.24749/) (2026)
- [An Optimal Sauer Lemma Over k-ary Alphabets](https://mlsanity.com/paper/2604.12952/) (2026)
- [Majority-of-Three is Optimal](https://mlsanity.com/paper/2606.13614/) (2026)
- [Understanding Aggregations of Proper Learners in Multiclass Classification](https://mlsanity.com/paper/2410.22749/) (2024)
- [Local Regularizers Are Not Transductive Learners](https://mlsanity.com/paper/2502.07187/) (2025)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [Local Regularization Does Not Characterize Multiclass PAC Learnability](https://mlsanity.com/paper/2607.23449/) (2026)

## Abstract (arXiv)

Two of the most fundamental questions in statistical learning theory are the following: which prediction problems are learnable, and how should they be learned? For the former, elegant answers often take the form of combinatorial dimensions. The latter question, however, has proved considerably more elusive: all known general-purpose multiclass learners rely on intricate orientations of exponentially large one-inclusion structures, and familiar algorithmic principles such as proper learning and regularization remain poorly understood. Motivated by prior work, we ask whether learning reduces to proper learning---possibly over a larger hypothesis class---and whether proper or improper multiclass learning can ultimately be captured by suitable regularizers. Our primary results answer both questions negatively, resolving three open problems from prior work. First, we exhibit a learnable multiclass problem that cannot be embedded in any properly learnable class, meaning learning cannot be reduced to proper learning by enlarging the hypothesis class. Second, we demonstrate that proper learning can require training error and characterize this phenomenon precisely: every properly learnable class admits a proper learner making o(m) errors on samples of size m, but every prescribed sublinear scale am=o(m) is necessary for some properly learnable problem. Third, regularization is not a general learner: we exhibit a properly learnable class that cannot be learned by any Structural Risk Minimization (SRM) learner, and a learnable class that cannot be learned by any local regularizer. We complement these impossibility results with a positive theory that gives two sufficient conditions for SRM learnability and characterizes SRM representability through integrability of revealed preferences.