# Regularization and Optimal Multiclass Learning arXiv: https://arxiv.org/abs/2309.13692 ยท HTML: https://mlsanity.com/paper/2309.13692/ ## Key facts - Cited by 15 papers in the map (data through 14 Oct 2026). - Builds on 18 of its 45 references that are in the map. - First posted on arXiv 24 Sep 2023. ## Builds on (most cited first, 18 of 18) - [DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs](https://mlsanity.com/paper/1606.00915/) (2016) - [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021) - [On the Origin of Implicit Regularization in Stochastic Gradient Descent](https://mlsanity.com/paper/2101.12176/) (2021) - [Predicting What You Already Know Helps: Provable Self-Supervised Learning](https://mlsanity.com/paper/2008.01064/) (2020) - [Human Pose Estimation with Iterative Error Feedback](https://mlsanity.com/paper/1507.06550/) (2015) - [A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks](https://mlsanity.com/paper/2010.03648/) (2020) - [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 PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021) - [Geometry of Optimization and Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1705.03071/) (2017) - [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023) - [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021) - [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023) - [On the Provable Advantage of Unsupervised Pretraining](https://mlsanity.com/paper/2303.01566/) (2023) - [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021) - [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022) - [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022) - [Entropy, Optimization and Counting](https://mlsanity.com/paper/1304.8108/) (2013) ## Built on by (most cited first, 15 of 15) - [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024) - [Understanding Aggregations of Proper Learners in Multiclass Classification](https://mlsanity.com/paper/2410.22749/) (2024) - [Transductive Learning Is Compact](https://mlsanity.com/paper/2402.10360/) (2024) - [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) - [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026) - [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025) - [On the Computability of Multiclass PAC Learning](https://mlsanity.com/paper/2502.06089/) (2025) - [The price of multi-group transductive learning](https://mlsanity.com/paper/2606.04423/) (2026) - [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026) - [Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation](https://mlsanity.com/paper/2603.02043/) (2026) - [A One-Inclusion Graph Approach to Multi-Group Learning](https://mlsanity.com/paper/2603.23208/) (2026) - [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026) - [Two Dimensions Govern Agnostic Multiclass Transductive Learning](https://mlsanity.com/paper/2608.25326/) (2026) - [Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning](https://mlsanity.com/paper/2608.26516/) (2026) ## Abstract (arXiv) The quintessential learning algorithm of empirical risk minimization (ERM) is known to fail in various settings for which uniform convergence does not characterize learning. It is therefore unsurprising that the practice of machine learning is rife with considerably richer algorithmic techniques for successfully controlling model capacity. Nevertheless, no such technique or principle has broken away from the pack to characterize optimal learning in these more general settings. The purpose of this work is to characterize the role of regularization in perhaps the simplest setting for which ERM fails: multiclass learning with arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal learning algorithms that dovetail with tried-and-true algorithmic principles: Occam's Razor as embodied by structural risk minimization (SRM), the principle of maximum entropy, and Bayesian reasoning. Most notably, we introduce an optimal learner which relaxes structural risk minimization on two dimensions: it allows the regularization function to be "local" to datapoints, and uses an unsupervised learning stage to learn this regularizer at the outset. We justify these relaxations by showing that they are necessary: removing either dimension fails to yield a near-optimal learner. We also extract from OIGs a combinatorial sequence we term the Hall complexity, which is the first to characterize a problem's transductive error rate exactly. Lastly, we introduce a generalization of OIGs and the transductive learning setting to the agnostic case, where we show that optimal orientations of Hamming graphs -- judged using nodes' outdegrees minus a system of node-dependent credits -- characterize optimal learners exactly. We demonstrate that an agnostic version of the Hall complexity again characterizes error rates exactly, and exhibit an optimal learner using maximum entropy programs.