Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
Abstract
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.
Related
- Multiclass Classification with Rare Useful Features: Fundamental Limits and the Optimality of Diversity Pursuit Higher Criticism Thresholding
- Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
- Quantitative vanishing-regularization limits for degenerate cross-diffusion with changing boundary strata
- Aperiodic random walks: uniform estimates, local limits and invariance principles
- Nonvanishing derived limits from clubsuit-type principles
BibTeX
@misc{asilis2026algorithmic,
title = {{Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning}},
author = {Julian Asilis and Shaddin Dughmi and Vatsal Sharan and Alec Sun and Shang-Hua Teng and Chang Wang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2608.26516},
eprint = {2608.26516},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26516},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
AU - Julian Asilis
AU - Shaddin Dughmi
AU - Vatsal Sharan
AU - Alec Sun
AU - Shang-Hua Teng
AU - Chang Wang
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2608.26516
UR - https://arxiv.org/abs/2608.26516
AB - 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 a_m=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.
ER -