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

Julian Asilis; Shaddin Dughmi; Vatsal Sharan; Alec Sun; Shang-Hua Teng; Chang Wang

cs.LGAug 27, 2026

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

Authors: Julian Asilis, Shaddin Dughmi, Vatsal Sharan, Alec Sun, Shang-Hua Teng, Chang Wang

Organizations: USC · University of Chicago · Northwestern University

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 $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.

Figures & tables

Panel of Figure 1 — Figure 1: The tree underlying the no-envelope construction. Each node $v$ is associated with a block $X_{v}$ , and its children are indexed by all binary labelings of that block. A target follows the highlighted finite path, selecting one public coordinate $u_{i}$ in each visited non-terminal block and using a private label elsewhere. In the lower bound, each continuation $b_{i}$ is a $d$ -bit pattern missing from the learner’s image at the current block.

Panel of Figure 2 — Figure 2: The hard distribution for the poisoned first-Cantor construction. The target $h_{A}$ predicts the private label $\lambda_{A}$ on the hidden half-set $A$ , and the common label $\star$ on $X_{n}\setminus A$ . The marker region $P_{n}\subseteq X_{n}\setminus A$ receives total mass $1/4$ , while the remaining common-label region receives mass $3/4$ . The sample therefore hits every marker in $P_{n}$ , ruling out the poisoned fallbacks, while revealing only a sparse portion of the common-label region.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 554 papers

Jul 26, 2026

Local Regularization Does Not Characterize Multiclass PAC Learnability

Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--Shalev-Shwartz dimension at most two with realizable PAC sample complexity

O\!\left(\frac{1}{\varepsilon}\log\frac{1}δ\right),

that no local regularizer learns. Hypotheses are edges of complete graphs and instances are tournaments. At a test tournament, the scores fix an edge ranking while the training sample independently removes competitors. Cyclic triangles force enough inversions that surviving competitors produce constant population error at arbitrarily large sample sizes.

Eric Hou

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Ask PDF

May 20, 2026

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples

(x, y)

from a distribution over

\mathbb{R}^d \times [k]

, with Gaussian

x

-marginal, the goal is to output a hypothesis whose error is comparable to that of the best

k

-class linear classifier. While the binary case

k=2

has a well-developed algorithmic theory, much less is known for

k \ge 3

. Even for

k=3

, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error

\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε

for general

k

. Additionally, we develop a sharper localization-based framework which leads to error

O(\mathrm{opt})+ε

for

k=3

, and error

\mathrm{poly}(k)\mathrm{opt}+ε

for geometrically regular

k

-class linear classifiers.

Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma

University of Wisconsin-Madison

Agnostic Learning Multiclass Classification Classification Statistical Learning Theory Linear Classification Robust Classification

Ask PDF

May 18, 2026

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes

k

is at least

3

, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers

\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}

using at most

O(k^2\cdot (d\log d+\log k))

samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e.

k=2

, our result is strictly stronger than all prior works.

Rita Adhikari, Shiwei Zeng

Augusta University

Multiclass Classification Classification Learning with Noisy Labels PAC Learning Linear Classification

Ask PDF

Abstract

Statistical Learning Theory

Explore similar work

Local Regularization Does Not Characterize Multiclass PAC Learnability

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers