Source-linked AI summary
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
TL;DR
The paper asks whether multiclass learning can be reduced to proper learning or captured by regularization, given the complexity of existing general-purpose learners. It constructs counterexamples resolving three open problems negatively, then gives sufficient conditions for SRM learnability and a preference-based representability characterization. The results show that proper learning and regularization are not universal, while residual simplicity and integrable preferences support SRM.
Problem
Multiclass learning lacks well-understood general-purpose principles: existing learners use intricate one-inclusion structures, while the scope of proper learning and regularization remains unresolved.
Method
The paper constructs multiclass counterexamples for proper learning, interpolation, global SRM, and local regularization, then develops localization and revealed-preference conditions for SRM.
Results
The paper resolves Open Problems 1–3 negatively: some learnable classes lack properly learnable envelopes, proper learners may require any prescribed o(m) training-error scale, and SRM or local regularization can fail.
Takeaways & Limitations
Proper learning and regularization are not universal multiclass learning principles, but SRM can succeed when unresolved ambiguity is statistically simple or revealed preferences satisfy the stated integrability conditions.
Takeaways & Limitations
The paper leaves open whether the unsupervised pre-training stage of local regularization can be omitted.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper shows that multiclass learning resists reduction to proper learning and general regularization, while identifying conditions under which SRM does succeed. It resolves three open problems negatively and quantifies the unavoidable training error of proper learners.
- Motivation: All known general-purpose multiclass learners rely on potentially exponential one-inclusion structures, motivating the search for simpler algorithmic principles.The paper contrasts this complexity with proper learning and regularization as familiar alternatives.
- Background and limitations: Proper learnability itself lacks a combinatorial characterization and can be logically undecidable, complicating proofs of proper learnability.This scope boundary explains why resolving the proper-learning question is technically difficult even before designing a learner.
- Proper learning and noninterpolation: Every properly learnable class admits a proper learner making o(m) errors on realizable samples, but every prescribed sublinear scale a_m=o(m) is necessary for some properly learnable problem.Thus proper learners need not interpolate, although they never require a constant fraction of training examples to be errors.
- Limits of global and local regularization: Weighted SRM can fail on properly learnable classes, and local regularization can fail on learnable classes, so fixed complexity scores are not universal multiclass learners.The SRM obstruction survives arbitrary ties and sample-dependent λ(S), while the local-regularizer counterexample yields constant error.
- Sufficient conditions for SRM: SRM succeeds when residual version spaces are statistically simple, and SRM representability is characterized by acyclic revealed preferences or positive weighted preference cycles.The positive theory includes finite fallback cores, simple regularizer sublevels, and an order-sensitive disagreement dimension.
- Proper learning and noninterpolation: Learning does not reduce to proper learning: some learnable classes cannot be embedded into any properly learnable envelope.This resolves Open Problem 3 in the negative, and in fact the constructed learner’s image cannot lie in any learnable class.
2 Preliminaries
The preliminaries define realizable multiclass PAC learning, proper and consistent learners, version spaces, and global or local regularizers. They formalize SRM variants and impose a worst-case tie-breaking requirement, then introduce closedness, pointwise finite range, and identifiers with compactness consequences.
- Learning model: Realizable multiclass PAC learning uses hypotheses H ⊆ Y^X, samples labeled by a target h⋆, and population loss measured on fresh points.A learner is proper when its output always lies in H; otherwise it is improper.
- Learning model: A version space contains hypotheses consistent with a realizable sample, and a consistent proper learner always outputs from that version space.A sample is ambiguous when its version space has at least two hypotheses.
- Regularization models: A global regularizer assigns complexity scores to hypotheses, whereas a local regularizer assigns location-dependent scores over H × X.Both encode preferences among hypotheses, with local regularization evaluating those preferences at particular domain points.
- Regularization models: Hard SRM minimizes regularizer values among interpolating hypotheses, weighted SRM trades empirical risk against regularization, and local regularization minimizes pointwise scores among interpolators.These are the three regularization-based learner families formalized in the preliminaries.
- Regularization models: Regularizers are required to succeed under every induced tie-breaking rule, so learning must follow from the regularizer’s preferences rather than a particular argmin choice.This is a worst-case requirement over all learners induced by the same regularizer or regularizer pair.
- Topological conditions: Closedness and pointwise finite range prevent identifier-based pathologies and ensure that every restriction H↾A is closed and compact.A finite identifier uniquely determines hypotheses on a finite domain subset; closedness also has an equivalent finite-projection characterization.
3 Proper Learning and Noninterpolation
The paper shows that multiclass learning does not generally reduce to proper learning, and that proper learners may need empirical error at any prescribed sublinear scale. It constructs learnable classes separating proper learning from interpolation and rules out hard SRM for a properly learnable class.
- Learning does not reduce to proper learning: Theorem 3.1 gives a learnable multiclass class that cannot be embedded in any properly learnable class.The construction uses an improper learner while proving that every PAC learner for the class has infinite disambiguation complexity.
- Learning does not reduce to proper learning: The constructed class uses finite paths in an infinite tree, with public labels on selected block points and private labels identifying hypotheses.The improper learner either recovers the target from a private label or reconstructs preceding blocks from the deepest public example.
- Proper learning requires empirical error: A properly learnable class can require nonzero training error: HP is properly PAC learnable but cannot be learned by any interpolating proper learner.Theorem 3.6 establishes this separation, while its proof controls population error through least-observed markers and missed-mass bounds.
- Proper learning requires empirical error: There exists a properly learnable class, HP, that cannot be learned by hard SRM.The result follows because hard SRM selects interpolating hypotheses using an a-priori inductive bias, whereas HP defeats every interpolating proper learner.
- The exact scale of empirical noninterpolation: Every properly learnable class admits a proper learner making o(m) training errors, while every prescribed sublinear sequence a_m=o(m) is necessary for some properly learnable class.Theorem 3.8 supplies the universal sublinear upper bound, and Theorem 3.9 gives matching necessity at any prescribed sublinear scale.
4 Limits of Global and Local Regularization
The paper shows that both global SRM and fixed hard local regularization can fail even for PAC-learnable multiclass classes. It proves these limitations using a properly learnable projective-plane incidence class and a learnable tripartite orientation class, while identifying flexibility that remains open for weighted local rules.
- Global regularization: The projective-plane incidence class is countable, closed, pointwise finite-range, and properly PAC learnable, yet no weighted-SRM objective learns it.The objective has the form h ↦ b_LS(h) + λ(S)ψ(h).
- Global regularization: Proper learning succeeds with a component-size-independent sample complexity by identifying the target from private labels or intersecting observed blocks.If all observed labels are uninformative, multiple blocks can identify the target; a single block uses its owner hypothesis, with an error estimate independent of component size.
- Global regularization: Projective-plane geometry creates many equally or more preferred interpolating neighbors, allowing SRM minimizers with population error at least 1/2.For arbitrarily large m, the induced learner has population error at least 1/2 with probability at least 1 − e^-128.
- Local regularization: The tripartite orientation class is PAC learnable but cannot be learned by any hard local regularizer fixed in advance.The obstruction already occurs for a class in which every hypothesis uses only two labels.
- Local regularization: The hard-local-regularization lower bound does not resolve whether weighted local rules can learn every multiclass problem.A weighted rule may choose a noninterpolating hypothesis that incurs training error but predicts the test point correctly, so the survival argument no longer applies.
5 Structural Conditions and Integrability
The section develops structural conditions under which regularization succeeds and characterizes when learners can be represented by SRM through revealed preferences. It uses fallback localization, disagreement complexity, and cycle consistency to provide sufficient conditions and exact representability results.
- Fallback localization: A finite fallback core guarantees hard-SRM learnability, while its existence is equivalent to a finite-range consistent proper PAC learner on ambiguous samples.The fallback core ensures every ambiguous realizable sample retains a consistent hypothesis from one fixed finite family.
- Fallback localization: Regularization can succeed when every ambiguous m-sample intersects a sublevel class H_rm whose Graph dimension d_m satisfies d_m log(m + 1) = o(m).This condition allows the full class H to have infinite Graph dimension because uniform convergence is needed only inside the localized sublevel class.
- Ordered disagreement complexity: Finite ordered-disagreement dimension dOD(ψ) yields PAC learning for every hard-SRM selector induced by ψ.Ordered disagreement is target-relative, so it can remain finite even when the full class has infinite Graph dimension.
- Ordered disagreement complexity: Some classes are learnable by a particular hard-SRM ordering but defeat every regularizer because lower contours can shatter sets of arbitrarily large size.The construction makes dOD(ψ) ≥ n for arbitrary n, while a designated ordering still learns the class.
- Ordered disagreement complexity: Finite symmetric ordered-disagreement dimension dSOD(ψ) is sufficient for every hard-SRM selector to PAC learn H, although its necessity remains open.The proof uses standard ε-net properties of VC classes.
- Integrability of revealed preferences: For finite menus, weighted-SRM representability is equivalent to strict positivity of every directed cycle’s total revealed-preference weight.For countable classes, injective hard-SRM representation instead requires acyclicity of the revealed preference relation, with finite-menu extension requiring contraction consistency.
- Integrability of revealed preferences: Weak weighted-SRM representation permits nonnegative cycle weights but may leave tied hypotheses with different predictions, so the objective alone need not define a successful universal selector.A separate fixed tie-breaking rule would be required, and injective regularizers do not prevent objective ties caused by cancellation with empirical loss.
6 Conclusion
The conclusion reports that proper learning and regularization are not universal principles for multiclass learning, while structural conditions and revealed-preference characterizations identify important positive cases. It leaves tractable learning rules beyond these principles as an open direction.
- Impossibility results: Learning does not reduce to proper learning, and proper learning may require sublinear but nonzero training error.The conclusion also states that the required error scale can be any prescribed sublinear scale.
- Impossibility results: Weighted SRM can fail on properly learnable classes, while local regularization can fail on improperly learnable classes.Thus a fixed notion of hypothesis complexity does not generally restore learnability.
- Positive theory: Regularization succeeds when non-trivial version spaces are sufficiently simple, and SRM representability admits exact revealed-preference characterizations.These positive results complement the paper’s impossibility constructions.
- Open direction: Identifying tractable multiclass learning rules beyond properness and regularization remains an open direction.The conclusion presents this as the most compelling direction left open by the work.
AI Disclosure
The paper discloses substantial use of ChatGPT 5.6 Pro during the development of its constructions and quantitative results.
- AI Disclosure: ChatGPT 5.6 Pro helped design the poisoned first Cantor class and uncover the empirical-error scale of Theorems 3.8 and 3.9.The human authors had first described the fundamental construction ideas.
A Auxiliary Probabilistic and Structural Lemmas
The appendix collects probabilistic and structural tools used by the main-text constructions and adds a weighted extension of the localization principle.
- A Auxiliary Probabilistic and Structural Lemmas: The appendix gathers auxiliary probabilistic and structural tools supporting the constructions developed in the main text.It concludes with a weighted extension of the localization principle from Section 5.1.
A.1 Selecting a light marker
A proper learner selects the empirically least frequent distinguished atom, and a distribution-free lemma guarantees that this marker is unlikely to have substantial population mass.
- The learner chooses a distinguished atom with minimum empirical frequency.This rule is applied to the poisoned first-Cantor class.
- For sufficiently many distinguished atoms, the selected marker has population mass at most η with probability at least 1−δ.The guarantee holds uniformly over distributions once the sample-size condition in the lemma is met.
- Chernoff bounds show that a light atom is unlikely to look heavy, while heavy atoms are unlikely to attain the empirical minimum.A union bound over the at most 1/η heavy atoms yields the result.
A.2 A hidden-halfset lemma
The hidden-halfset lemma formalizes a posterior-symmetry barrier: after observing o(K) samples from a random K-subset of a set of size 2K+N, procedures cannot cover much more than half of the hidden set.
- With N=o(K), a uniformly random K-subset is drawn from a universe of size 2K+N.A procedure observes at most m=o(K) iid uniform draws from the hidden subset and outputs at most K+N elements.
- After conditioning on the observed distinct values, the hidden subset remains uniformly distributed among K-subsets containing those values.This posterior symmetry holds even after conditioning on the procedure’s internal randomness.
- The unseen portion captured by the output is hypergeometric, with its mean constrained because both the observed sample and excess output size are sublinear in K.Here |R|≤m=o(K) and |B|≤K+N=(1+o(1))K.
- A hypergeometric Chernoff bound implies that the procedure misses a substantial portion of the hidden subset uniformly over procedures.The conclusion follows from |T\B|=K−|T∩B|.
A.3 Projective-plane incidence estimates
The projective-plane incidence matrix has two singular-value scales, yielding a mixing estimate used in the incidence-inversion step of Theorem 4.2.
- For a projective plane of order q, the incidence matrix has N=q^2+q+1 points and lines and degree d=q+1.
- The singular values of the incidence matrix are d and √q.This follows from MM⊤=qI+J and the corresponding eigenvalues on the all-ones and orthogonal subspaces.
- Decomposing point- and line-set indicators into constant and orthogonal components gives the displayed mixing estimate.That estimate is the one used in incidence inversion, step (7) of Theorem 4.2.
A.4 A weighted approximate-interpolation principle
A weighted empirical-loss-plus-regularization objective can PAC learn when its minimizers have controlled complexity and approximate interpolation, extending fallback localization to learners that make some training errors.
- The theorem considers weighted objectives bLS(h)+λmψ(h) whose minima exist on every realizable sample.It defines sublevel classes HR={h∈H:ψ(h)≤R}.
- All minimizers lie in the fixed sublevel class HRm and have vanishing empirical error.Uniform convergence on that sublevel class then supplies the generalization control.
- Consequently, every minimizer PAC learns H, and the argument handles all minimizers simultaneously, including ties.The loss to the target satisfies LD(bh,h⋆)→0 in probability.
- Every minimizer has empirical loss at most ηm+λmrm and complexity at most Rm=rm+ηm/λm.These bounds follow by comparing the minimizer with an approximate interpolating comparator.
B.1 The tunable lower bound
The construction gives a countable, pointwise finite-range, properly PAC-learnable class whose proper learners can be forced to make errors at any prescribed sublinear scale. Its block and marker structure makes fallback hypotheses incur many training mistakes while nonfallback outputs have constant population error.
- Lower bound: Choosing r_m = max {⌈a_m⌉, ⌈log log(m + e^e)⌉} forces the proper learner to make at least a universal-constant multiple of a_m errors.Since r_m ≥ a_m, the claimed tunable lower bound follows.
- Class construction: Each block contains markers, a core, global labels, private labels, and poison labels supporting background, Cantor, and fallback hypotheses.The block X_j has size 2K_j + 2N_j, while every half-set has size K_j + N_j.
- Class construction: The class H_a is countable, closed, pointwise finite-range, and properly PAC learnable.Each finite block supports only finitely many hypotheses, and finite consistency forces any consistent function to coincide with a class member.
- Lower bound: On the event that every marker appears at least r_m/2 times, every active-block fallback makes at least r_m/2 training mistakes.Each marker count has mean r_m, and the event holds with probability 1 − o(1) for the fixed target-distribution pair.
- Lower bound: Every nonfallback output has constant population error with probability 1 − o(1) because the learner observes only m = o(K_m) draws from the hidden marker set.The argument covers the background hypothesis, hypotheses on other blocks, and Cantor hypotheses whose active portions are too large to identify from the sample.
B.2 Pathological learners
These examples show that proper learners may behave pathologically on extremely rare realizable samples without losing PAC guarantees or asymptotic sample complexity. In particular, complete training-set misclassification can coexist with optimal realizable sample complexity.
- Rare-sample pathology: An otherwise successful learner can be modified arbitrarily on a sufficiently rare sequence of samples without changing asymptotic sample complexity.The ordered sample (1, 2, …, m) has probability at most m^-m under every marginal.
- Rare-sample pathology: A proper learner for the two constant binary hypotheses can misclassify every training point on some realizable sample of every size.On the exceptional ordered sample, it outputs the constant hypothesis opposite to the observed label.
- Rare-sample pathology: The exceptional sample probability vanishes superexponentially, so the pathology does not affect PAC learnability.The bound follows from AM–GM applied to the probability of the ordered unlabeled sequence.