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

# Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning
Source: [https://arxiv.org/html/2608.26516](https://arxiv.org/html/2608.26516)
###### 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, notably the VC dimension for binary classification and the DS dimension for multiclass\. The latter question 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 makingo⁡\(m\)o\(m\)errors on samples of sizemm, but every prescribed sublinear scaleam=o⁡\(m\)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\. Together, our results delineate the limits of proper learning and regularization, along with the structural conditions under which regularization succeeds\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2608.26516#S1)1. [1\.1Results](https://arxiv.org/html/2608.26516#S1.SS1) 2. [1\.2Techniques](https://arxiv.org/html/2608.26516#S1.SS2) 3. [1\.3Related work](https://arxiv.org/html/2608.26516#S1.SS3)
2. [2Preliminaries](https://arxiv.org/html/2608.26516#S2)1. [2\.1Regularization models](https://arxiv.org/html/2608.26516#S2.SS1) 2. [2\.2Topological conditions](https://arxiv.org/html/2608.26516#S2.SS2)
3. [3Proper Learning and Noninterpolation](https://arxiv.org/html/2608.26516#S3)1. [3\.1Learning does not reduce to proper learning](https://arxiv.org/html/2608.26516#S3.SS1) 2. [3\.2Proper learning requires empirical error](https://arxiv.org/html/2608.26516#S3.SS2) 3. [3\.3The exact scale of empirical noninterpolation](https://arxiv.org/html/2608.26516#S3.SS3)
4. [4Limits of Global and Local Regularization](https://arxiv.org/html/2608.26516#S4)1. [4\.1A closed incidence class beyond weighted SRM](https://arxiv.org/html/2608.26516#S4.SS1) 2. [4\.2A PAC counterexample to hard local regularization](https://arxiv.org/html/2608.26516#S4.SS2)
5. [5Structural Conditions and Integrability](https://arxiv.org/html/2608.26516#S5)1. [5\.1Fallback localization](https://arxiv.org/html/2608.26516#S5.SS1) 2. [5\.2Ordered disagreement complexity](https://arxiv.org/html/2608.26516#S5.SS2) 3. [5\.3Integrability of revealed preferences](https://arxiv.org/html/2608.26516#S5.SS3)
6. [6Conclusion](https://arxiv.org/html/2608.26516#S6)
7. [References](https://arxiv.org/html/2608.26516#bib)
8. [AAuxiliary Probabilistic and Structural Lemmas](https://arxiv.org/html/2608.26516#A1)1. [A\.1Selecting a light marker](https://arxiv.org/html/2608.26516#A1.SS1) 2. [A\.2A hidden\-halfset lemma](https://arxiv.org/html/2608.26516#A1.SS2) 3. [A\.3Projective\-plane incidence estimates](https://arxiv.org/html/2608.26516#A1.SS3) 4. [A\.4A weighted approximate\-interpolation principle](https://arxiv.org/html/2608.26516#A1.SS4)
9. [BOmitted Proofs for Empirical Noninterpolation](https://arxiv.org/html/2608.26516#A2)1. [B\.1The tunable lower bound](https://arxiv.org/html/2608.26516#A2.SS1) 2. [B\.2Pathological learners](https://arxiv.org/html/2608.26516#A2.SS2)

## 1Introduction

Designing optimal, tractable learners for learnable problems stands as one of statistical learning theory’s most central goals\. Such a learnable problem is described by a domain𝒳\\mathcal\{X\}, label set𝒴\\mathcal\{Y\}, and hypothesis class of functionsℋ⊆𝒴𝒳\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}\. A learner receives a training sampleS=\(\(xi,yi\)\)i≤nS=\\big\(\(x\_\{i\},y\_\{i\}\)\\big\)\_\{i\\leq n\}, with eachxix\_\{i\}drawn i\.i\.d\. from a marginal distribution𝒟\\mathcal\{D\}over𝒳\\mathcal\{X\}and labeled by a hypothesish∗∈ℋh^\{\*\}\\in\\mathcal\{H\}, i\.e\.,yi=h∗​\(xi\)y\_\{i\}=h^\{\*\}\(x\_\{i\}\)\. The purpose of a learnerAAis to ingest only the sampleSSand emit a predictorA⁡\(S\):𝒳→𝒴A\(S\):\\mathcal\{X\}\\to\\mathcal\{Y\}with high probability of correctly classifying a freshly drawn test pointxtest∼𝒟x\_\{\\mathrm\{test\}\}\\sim\\mathcal\{D\}\. That is, the learner seeks to minimize

L𝒟​\(A⁡\(S\)\)=ℙxtest∼𝒟\(A⁡\(S\)​\(xtest\)≠h∗​\(xtest\)\)\.L\_\{\\mathcal\{D\}\}\\big\(A\(S\)\\big\)=\\P\_\{x\_\{\\mathrm\{test\}\}\\sim\\mathcal\{D\}\}\\Big\(A\(S\)\(x\_\{\\mathrm\{test\}\}\)\\neq h^\{\*\}\(x\_\{\\mathrm\{test\}\}\)\\Big\)\.
Binary classification, where one employs the label set𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}, enjoys a simple characterization of its \(optimal\) learners\. Empirical Risk Minimization \(ERM\) learns whenever learning is possible, with nearly\-optimal sample complexity, and a simple majority of just 3 ERM learners suffices to attain the optimal rate\([Aden\-Ali et al\., 2024](https://arxiv.org/html/2608.26516#bib.bib1);[Rawal and Zhivotovskiy, 2026](https://arxiv.org/html/2608.26516#bib.bib9)\)\. Perhaps surprisingly, the landscape for multiclass classification, with𝒴\\mathcal\{Y\}arbitrary, is strikingly more complex\.

All known general\-purpose multiclass learners appeal to abstract orientations of so\-called*one\-inclusion graphs*\(OIGs\), which can be exponentially large in the size of the training setSS, or even infinite should𝒴\\mathcal\{Y\}be infinite\([Brukhim et al\., 2022](https://arxiv.org/html/2608.26516#bib.bib2);[Aden\-Ali et al\., 2023](https://arxiv.org/html/2608.26516#bib.bib8);[Pabbaraju, 2026](https://arxiv.org/html/2608.26516#bib.bib10)\)\. Such reliance on intractable OIGs can be partly explained: Some natural algorithmic templates have been ruled out for multiclass learning\. In particular,[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3)demonstrated the existence of learnable problems that cannot be learned by any*proper*learner, i\.e\., a learner that always emits a function in the underlying classℋ\\mathcal\{H\}\. Subsequently,[Asilis et al\. \(2025b\)](https://arxiv.org/html/2608.26516#bib.bib7)exhibited the same failure for any aggregation of a bounded number of proper learners, such as a majority of 3 ERMs\. How, then, can one hope to design a simple algorithmic framework for multiclass learning?

Two paths are suggested by prior work\. The first appeals to*regularization*, one of the most fundamental algorithmic templates for learning with considerable successes on both theoretical and empirical fronts\.111Empirically, regularized empirical\-risk objectives—most prominentlyℓ1\\ell\_\{1\}penalties such as the lasso andℓ2\\ell\_\{2\}penalties such as ridge regression or weight decay—are routinely used to control effective model complexity and encourage generalization\([Hoerl and Kennard, 1970](https://arxiv.org/html/2608.26516#bib.bib17);[Tibshirani, 1996](https://arxiv.org/html/2608.26516#bib.bib18);[Krogh and Hertz, 1991](https://arxiv.org/html/2608.26516#bib.bib19);[Hastie et al\., 2009](https://arxiv.org/html/2608.26516#bib.bib20)\)\. Theoretically, SRM has been shown to characterize non\-uniform learnability\([Shalev\-Shwartz and Ben\-David, 2014](https://arxiv.org/html/2608.26516#bib.bib6)\)\.Recall that a regularizerψ:ℋ→ℝ≥0\\psi\\colon\\mathcal\{H\}\\to\\mathbb\{R\}\_\{\\geq 0\}assigns a score to each hypothesish∈ℋh\\in\\mathcal\{H\}, often thought of as measuring the “complexity” ofhh, and that a*Structural Risk Minimization*\(SRM\) learner then trades off empirical risk with hypothesis complexity in an effort to avoid overfitting\. In multiclass learning,[Asilis et al\. \(2024b\)](https://arxiv.org/html/2608.26516#bib.bib4)exhibited optimal learners based upon*unsupervised local regularization*\. In this framework, a learner receives a labeled sampleS=\(\(xi,yi\)\)i≤nS=\\big\(\(x\_\{i\},y\_\{i\}\)\\big\)\_\{i\\leq n\}and uses only its unlabeled datapoints\(xi\)i≤n\(x\_\{i\}\)\_\{i\\leq n\}to learn a local regularizerψ:ℋ×𝒳→ℝ≥0\\psi:\\mathcal\{H\}\\times\\mathcal\{X\}\\to\\mathbb\{R\}\_\{\\geq 0\}\. Intuitively, the local regularizerψ⁡\(h,x\)\\psi\(h,x\)measures the “complexity” of a functionhhat the test pointxx, reflecting the fact that hypotheses may act simply in certain regions of the domain and more intricately in others\. At test time, for an unlabeled datapointxtest∈𝒳x\_\{\\mathrm\{test\}\}\\in\\mathcal\{X\}, the learner makes the prediction

A⁡\(S\)​\(xtest\)∈\{h⁡\(xtest\):h∈arg​minℋ⁡L^S​\(h\)\+ψ⁡\(h,xtest\)\}\.A\(S\)\(x\_\{\\mathrm\{test\}\}\)\\in\\Big\\\{h\(x\_\{\\mathrm\{test\}\}\):h\\in\\argmin\_\{\\mathcal\{H\}\}\\widehat\{L\}\_\{S\}\(h\)\+\\psi\(h,x\_\{\\mathrm\{test\}\}\)\\Big\\\}\.Note that the dependence of the regularizer upon the test pointxtestx\_\{\\mathrm\{test\}\}is essential in order to express improper learners\. \(Intuitively, it permits a learner to “stitch together” various hypotheses inℋ\\mathcal\{H\}when producing a predictor\.\)

It is, however, not clear whether the unsupervised pre\-training stage of the local regularizer can be omitted\. Perhaps all that is required to learn a classification problem is an appropriate choice of local regularizerψ:ℋ×𝒳→ℝ≥0\\psi:\\mathcal\{H\}\\times\\mathcal\{X\}\\to\\mathbb\{R\}\_\{\\geq 0\}encoding the “complexity” of hypotheses at particular regions in the domain\. Precisely this question was recently articulated by[Asilis et al\. \(2024a\)](https://arxiv.org/html/2608.26516#bib.bib5)\.

###### Open Problem 1\(\([Asilis et al\., 2024a](https://arxiv.org/html/2608.26516#bib.bib5)\)\)\.

Can all learnable multiclass problemsℋ\\mathcal\{H\}be learned by a local regularizer? If so, with \(nearly\) optimal sample complexity?

A second path towards simplicity in multiclass learning is to invoke an additional assumption on the underlying hypothesis classℋ\\mathcal\{H\}\. Perhaps the most natural is that of proper learnability, i\.e\., to assume thatℋ\\mathcal\{H\}can be learned while only emitting hypotheses inℋ\\mathcal\{H\}itself\. In this setting, the most ambitious goal would be to demonstrate that classic regularization is all one needs\. This question, too, was previously raised and remains open\.

###### Open Problem 2\(\([Asilis et al\., 2025a](https://arxiv.org/html/2608.26516#bib.bib11)\)\)\.

Letℋ\\mathcal\{H\}be a properly learnable multiclass problem\. Mustℋ\\mathcal\{H\}be learnable by an SRM learner?

Allow us to briefly remark upon a subtlety related to[Open Problem2](https://arxiv.org/html/2608.26516#Thmproblem2)\. In the design of improper learners for learnable multiclass problems, one makes crucial use of the fact that learnability amounts to finiteness of the DS dimension\([Brukhim et al\., 2022](https://arxiv.org/html/2608.26516#bib.bib2);[Pabbaraju, 2026](https://arxiv.org/html/2608.26516#bib.bib10)\)\. That is, finiteness ofℋ\\mathcal\{H\}’s DS dimension provides an important handhold in analyzing successful learners, by way ofℋ\\mathcal\{H\}’s one\-inclusion graphs\. Proper learnability, however, is a fundamentally stranger beast\.[Asilis et al\. \(2025a\)](https://arxiv.org/html/2608.26516#bib.bib11)demonstrated that it cannot be characterized by any combinatorial dimension, and that it can even be logically undecidable, i\.e\., independent of the ZFC axioms\. This complicates the task of resolving[Open Problem2](https://arxiv.org/html/2608.26516#Thmproblem2)in either direction, as merely establishing the proper learnability of a hypothesis class can be surprisingly involved \(or even undecidable\!\)\.

Finally, there is a curious commonality shared by existing hypothesis classes designed to be improperly learnable yet not properly learnable: they can easily be made properly learnable with the addition of a small number of functions to the class\. This includes the first Cantor class of[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3), along with the EMX learning problem of[Ben\-David et al\. \(2019\)](https://arxiv.org/html/2608.26516#bib.bib13)when viewed as a classification problem as in[Asilis et al\. \(2025a\)](https://arxiv.org/html/2608.26516#bib.bib11)\. This raises an alluring possibility: perhaps all learnable classes can be embedded within properly learnable classes\.

###### Open Problem 3\(\([Asilis et al\., 2025a](https://arxiv.org/html/2608.26516#bib.bib11)\)\)\.

Is every learnable hypothesis classℋ\\mathcal\{H\}contained within a properly learnable classℋprop⊇ℋ\\mathcal\{H\}\_\{\\mathrm\{prop\}\}\\supseteq\\mathcal\{H\}?

Note that a positive resolution to[Open Problem3](https://arxiv.org/html/2608.26516#Thmproblem3)would establish, roughly speaking, that general multiclass learning can be reduced to proper learning\. If it were accompanied by a positive resolution to[Open Problem2](https://arxiv.org/html/2608.26516#Thmproblem2), demonstrating that proper learning reduces to SRM, it would then be the case that general multiclass learning reduces to SRM\!

Unfortunately, our results demonstrate that the picture is not so rosy: multiclass learning resists simple algorithmic principles, even under the promise of proper learnability\. We elaborate upon our impossibility results, and upon our characterizations of SRM learnability, in[Section1\.1](https://arxiv.org/html/2608.26516#S1.SS1)\.

### 1\.1Results

Our primary results resolve[Open Problems1](https://arxiv.org/html/2608.26516#Thmproblem1),[2](https://arxiv.org/html/2608.26516#Thmproblem2)and[3](https://arxiv.org/html/2608.26516#Thmproblem3)in the negative\. We divide our contributions into three groups\.

- •Proper learning and noninterpolation\.We first show that general multiclass learning does not reduce to proper learning, even after enlarging the learner’s output space\. That is, there exists a learnable class that cannot be embedded into any properly learnable envelope, resolving[Open Problem3](https://arxiv.org/html/2608.26516#Thmproblem3)in the negative \([Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1)\)\. We next construct a topologically well\-behaved hypothesis class that is properly learnable but cannot be learned by any interpolating proper learner \([Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6)\)\. Finally, we give a tight quantitative account of this phenomenon: every properly learnable class admits a proper learner makingo⁡\(m\)o\(m\)errors on every realizable sample of sizemm, and every prescribed sublinear scaleam=o⁡\(m\)a\_\{m\}=o\(m\)is necessary for some properly learnable problem \([Theorems3\.8](https://arxiv.org/html/2608.26516#S3.Thmtheorem8)and[3\.9](https://arxiv.org/html/2608.26516#S3.Thmtheorem9)\)\. Thus proper learners never need to sacrifice a constant fraction of their training sample, but within the sublinear regime essentially any number of errors can be forced\.
- •Limits of global and local regularization\.We first demonstrate that regularization\-based learners can fail even on problems that are properly learnable\. Namely, we exhibit a properly learnable class for which every weighted SRM objective of the formh⟼L^S​\(h\)\+λ⁡\(S\)⋅ψ⁡\(h\)h\\longmapsto\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\(S\)\\cdot\\psi\(h\)fails to learn, resolving[Open Problem2](https://arxiv.org/html/2608.26516#Thmproblem2)in the negative \([Theorem4\.2](https://arxiv.org/html/2608.26516#S4.Thmtheorem2)\)\. We next consider whether*local regularizers*, which may combine different hypotheses at different test points and thereby express improper learners, succeed whenever improper learning is possible\. Here we again give a negative answer: we construct a learnable class that lies beyond the reach of local regularization, resolving the PAC version of[Open Problem1](https://arxiv.org/html/2608.26516#Thmproblem1)\([Theorem4\.6](https://arxiv.org/html/2608.26516#S4.Thmtheorem6)\)\. We note that the concurrent, independent work of[Hou \(2026\)](https://arxiv.org/html/2608.26516#bib.bib23)also exhibited such a counterexample; we compare and contrast our approach in[Section1\.3](https://arxiv.org/html/2608.26516#S1.SS3)\.
- •Sufficient conditions for SRM\.We complement these impossibility results with two positive routes to SRM learnability\. First, we show that hard SRM succeeds whenever non\-trivial samples admit a consistent hypothesis from a fixed finite family of hypotheses; more generally, the same principle applies when the relevant hypotheses lie inside a statistically simple sublevel of the regularizer \([Theorems5\.3](https://arxiv.org/html/2608.26516#S5.Thmtheorem3),[5\.4](https://arxiv.org/html/2608.26516#S5.Thmtheorem4)and[5\.5](https://arxiv.org/html/2608.26516#S5.Thmtheorem5)\)\. Second, we introduce an order\-sensitive disagreement dimension that similarly measures the complexity of sublevel sets of the regularizer\. We prove that finiteness of this dimension suffices for hard\-SRM learnability, though it is not necessary \([Theorems5\.7](https://arxiv.org/html/2608.26516#S5.Thmtheorem7)and[5\.8](https://arxiv.org/html/2608.26516#S5.Thmtheorem8)\)\. Finally, we characterize when the behavior of a particular learner can be witnessed by a regularizer\. Here we find that a consistent learner is representable by SRM precisely when the pairwise preferences revealed by its choices are acyclic, while weighted SRM representability over finite systems is equivalent to positivity of every revealed\-preference cycle \([Theorems5\.11](https://arxiv.org/html/2608.26516#S5.Thmtheorem11)and[5\.14](https://arxiv.org/html/2608.26516#S5.Thmtheorem14)\)\.

### 1\.2Techniques

Our proofs appeal to diverse combinatorial tools: diagonal arguments on rooted trees, projective\-plane expansion, and directed\-triangle counting\. Let us describe the key ideas\.

v0v\_\{0\}v1v\_\{1\}v2v\_\{2\}v3v\_\{3\}b1b\_\{1\}b2b\_\{2\}b3b\_\{3\}⋱\\ddotsXv0X\_\{v\_\{0\}\}Xv1X\_\{v\_\{1\}\}Xv2X\_\{v\_\{2\}\}u1u\_\{1\}u2u\_\{2\}u3u\_\{3\}TdT\_\{d\}\|Xvi\|=d\|X\_\{v\_\{i\}\}\|=d

Figure 1:The tree underlying the no\-envelope construction\. Each nodevvis associated with a blockXvX\_\{v\}, and its children are indexed by all binary labelings of that block\. A target follows the highlighted finite path, selecting one public coordinateuiu\_\{i\}in each visited non\-terminal block and using a private label elsewhere\. In the lower bound, each continuationbib\_\{i\}is add\-bit pattern missing from the learner’s image at the current block\.#### No properly learnable envelope\.

We first ask whether an arbitrary learnable multiclass problemℋ\\mathcal\{H\}can be embedded into a properly learnable envelopeℋprop⊇ℋ\\mathcal\{H\}\_\{\\mathrm\{prop\}\}\\supseteq\\mathcal\{H\}\. Were this true, then general learning would reduce to proper learning in a precise sense: one could properly learnℋprop\\mathcal\{H\}\_\{\\mathrm\{prop\}\}, thereby obtaining a learnerAAforℋ\\mathcal\{H\}whose image is contained in a properly learnable class\. We rule out this possibility by constructing a learnable classℋ\\mathcal\{H\}for which every successful learnerAAmust satisfyDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\infty\. In particular, the image ofAAcannot be contained in*any*learnable class, even improperly so\.

The construction \(illustrated in[Figure1](https://arxiv.org/html/2608.26516#S1.F1)\) employs, for eachd≥1d\\geq 1, an infinite complete2d2^\{d\}\-ary treeTdT\_\{d\}\.222TdT\_\{d\}shares some features of a Vapnik\-Chervonenkis\-Littlestone \(VCL\) tree\([Bousquet et al\., 2021](https://arxiv.org/html/2608.26516#bib.bib21)\)\. Each node carries a block whose binary labelings index its children\. However, its shape is slightly different, as withinTdT\_\{d\}it has a fixed block size and a fixed branching factor at every depth\.To every node

v=\(b1,…,bk\),bi∈\{0,1\}d,v=\(b\_\{1\},\\ldots,b\_\{k\}\),\\qquad b\_\{i\}\\in\\\{0,1\\\}^\{d\},at depthkk, we associate a fresh block of domain pointsXv=\{xv,1,…,xv,d\}X\_\{v\}=\\\{x\_\{v,1\},\\ldots,x\_\{v,d\}\\\}\. The nodevvhas one child\(v,b\)\(v,b\)for every binary labelingb∈\{0,1\}db\\in\\\{0,1\\\}^\{d\}ofXvX\_\{v\}\. A target hypothesis chooses a finite path

∅=v0≺v1≺⋯≺vℓ\\varnothing=v\_\{0\}\\prec v\_\{1\}\\prec\\cdots\\prec v\_\{\\ell\}and one coordinateui∈\[d\]u\_\{i\}\\in\[d\]from each non\-terminal block along that path\. At the selected pointxvi−1,uix\_\{v\_\{i\-1\},u\_\{i\}\}, it predicts the public bitbi​\(ui\)∈\{0,1\}b\_\{i\}\(u\_\{i\}\)\\in\\\{0,1\\\}; at every other point, it predicts a private label identifying the entire target\.

First note that the class can be improperly learned: if a private label is present in the sample, then the target function has been revealed\. Otherwise, the sample is supported on public labeled points, which reveal a branch prefix—as each nodevkv\_\{k\}records the earlier vectorsb1,…,bkb\_\{1\},\\ldots,b\_\{k\}\. An improper learner can simply stitch together the public predictions from the longest such prefix, emitting a default label elsewhere\. Informally, this emitted classifier can err only on an unobserved private region or the as\-yet\-unseen tail of the path, both of which have small mass whenever the sample has missed them\.

Now letAAbe an arbitrary successful learner forℋ\\mathcal\{H\}\. We show thatDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\infty\. To this end, it suffices to show that for eachd∈ℕd\\in\\mathbb\{N\},im\(A\)\\im\(A\)contains add\-dimensional binary hypercube of functions, e\.g\., the behaviors\{0,1\}d\\\{0,1\\\}^\{d\}on a set ofddunlabeled datapoints\.333In fact, it would suffice merely to exhibit*pseudocubes*of arbitrarily large dimension, rather than the \(binary\) hypercubes we exhibit\.Fix one suchd∈ℕd\\in\\mathbb\{N\}, and consider theddpoints in the block associated with each node ofTdT\_\{d\}\. There are two possibilities\. If at some node, every binary labeling of the block is realized by some hypothesis inim⁡\(A\)\\operatorname\{im\}\(A\), then the image ofAAcontains a fulldd\-dimensional binary cube, meaningDS\(im⁡\(A\)\)≥d\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)\\geq d\. Otherwise, every node has some binary labeling of its block that is not realized by any hypothesis inim⁡\(A\)\\operatorname\{im\}\(A\)\. Since the children of a node are indexed by all binary labelings of its block, we may follow the corresponding child\. Repeating this procedure produces an infinite pathPPalong which the image ofAAmisses a \(prescribed\) labeling at every depth\.

The second possibility is incompatible with the success ofAA\. To see why, fix a sample sizem=\|S\|m=\|S\|and take a prefix ofPPof length2​m2m, sayP2​mP\_\{2m\}\. At each depth ofP2​mP\_\{2m\}, choose one of theddpoints uniformly at random as public points\. Then construct the hard distribution by distributing mass uniformly across the chosen public points\. Clearly, a sample of sizemmleaves at least half of the depths inP2​mP\_\{2m\}unseen\. Then at any unseen depth, the learner’s output must disagree with the prescribed labeling on at least one point in the block\. Since the selected public point at that depth remains uniformly random among thoseddpoints, the learner errs with probability at least1d\\frac\{1\}\{d\}\. Asmmis arbitrary, this implies thatAAdoes not attain vanishing expected error, contradicting the PAC guarantee\.

Thus only the first possibility can occur\. That is, for everydd, some block must contain a fulldd\-dimensional binary cube in the image ofAA, meaningDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\inftyas desired\.

#### Proper learning beyond interpolation\.

To separate proper learning from interpolation, our starting point is the first Cantor class of[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3)\. Each finite block𝒳n\\mathcal\{X\}\_\{n\}supports the class

ℋn=\{hA:A⊆𝒳n,\|A\|=\|𝒳n\|2\},hA\(x\)=\{λA,x∈A,⋆,x∈𝒳n∖A,\\mathcal\{H\}\_\{n\}=\\left\\\{h\_\{A\}:A\\subseteq\\mathcal\{X\}\_\{n\},\\ \|A\|=\\frac\{\|\\mathcal\{X\}\_\{n\}\|\}\{2\}\\right\\\},\\qquad h\_\{A\}\(x\)=\\begin\{cases\}\\lambda\_\{A\},&x\\in A,\\\\ \\star,&x\\in\\mathcal\{X\}\_\{n\}\\setminus A,\\end\{cases\}whereλA\\lambda\_\{A\}is a private label unique toAA\. Taking𝒳=⨆n∈ℕ𝒳n\\mathcal\{X\}=\\bigsqcup\_\{n\\in\\mathbb\{N\}\}\\mathcal\{X\}\_\{n\}and extending every hypothesis by the fresh label$\\$outside its own block gives the full class\. Thus each hypothesis outputs a unique identifier on one half of its block and the uninformative label⋆\\staron the other\. The class is easily learned improperly: either the sample contains a private label that definitively reveals the target, or the learner may safely output the simple predictor that is constantly⋆\\staron the active block and$\\$elsewhere\. A proper learner, however, can be forced to guess an arbitrary half\-setA⊆𝒳nA\\subseteq\\mathcal\{X\}\_\{n\}using only draws from its complement\. Choosing\|𝒳n\|\|\\mathcal\{X\}\_\{n\}\|large relative to\|S\|\|S\|therefore destroys proper learnability\.

We augment this construction by adding a small number of “poisoned” hypotheses toℋn\\mathcal\{H\}\_\{n\}that each output the⋆\\starlabel on all of𝒳n\\mathcal\{X\}\_\{n\}, save for a distinguished marker point\. In particular, we first carve a small marker regionPnP\_\{n\}within𝒳n\\mathcal\{X\}\_\{n\},

Pn=\{z1,…,zrn\}⊆𝒳n,rn⟶∞,\|Pn\|≪\|𝒳n\|\.P\_\{n\}=\\\{z\_\{1\},\\ldots,z\_\{r\_\{n\}\}\\\}\\subseteq\\mathcal\{X\}\_\{n\},\\qquad r\_\{n\}\\longrightarrow\\infty,\\qquad\|P\_\{n\}\|\\ll\|\\mathcal\{X\}\_\{n\}\|\.We then require each private half\-setAAto avoidPnP\_\{n\}, so that every Cantor hypothesishAh\_\{A\}assigns the common label⋆\\starto the marker region\. For every markerzi∈Pnz\_\{i\}\\in P\_\{n\}, we then introduce an additional hypothesishzih\_\{z\_\{i\}\}satisfying

hzi\(zi\)=λzi,hzi\(x\)=⋆for everyx∈𝒳n∖\{zi\}\.h\_\{z\_\{i\}\}\(z\_\{i\}\)=\\lambda\_\{z\_\{i\}\},\\qquad h\_\{z\_\{i\}\}\(x\)=\\star\\quad\\text\{for every \}x\\in\\mathcal\{X\}\_\{n\}\\setminus\\\{z\_\{i\}\\\}\.Eachhzih\_\{z\_\{i\}\}is thus an almost\-all\-⋆\\starhypothesis, deliberately poisoned at one marker\.

XnX\_\{n\}AAPnP\_\{n\}Figure 2:The hard distribution for the poisoned first\-Cantor construction\. The targethAh\_\{A\}predicts the private labelλA\\lambda\_\{A\}on the hidden half\-setAA, and the common label⋆\\staronXn∖AX\_\{n\}\\setminus A\. The marker regionPn⊆Xn∖AP\_\{n\}\\subseteq X\_\{n\}\\setminus Areceives total mass1/41/4, while the remaining common\-label region receives mass3/43/4\. The sample therefore hits every marker inPnP\_\{n\}, ruling out the poisoned fallbacks, while revealing only a sparse portion of the common\-label region\.When the sample contains only⋆\\starlabels, a successful proper learner can output any hypothesis associated with one of the least frequently observed markers\. If a marker is absent from the sample, i\.e\.,S⊆𝒳n∖PnS\\subseteq\\mathcal\{X\}\_\{n\}\\setminus P\_\{n\}and all labels are⋆\\star, then this choice is interpolating\. However, if every markerp∈Pnp\\in P\_\{n\}appears inSSwith the label⋆\\star, then the proper learner sacrifices the least frequently observed markerpmin∈Pnp\_\{\\min\}\\in P\_\{n\}, and outputshpminh\_\{p\_\{\\min\}\}\. \(See[Figure2](https://arxiv.org/html/2608.26516#S1.F2)\.\) An elementary probabilistic argument can be used to show that, because\|Pn\|=ω⁡\(1\)\|P\_\{n\}\|=\\omega\(1\),pminp\_\{\\min\}has population masso⁡\(1\)o\(1\)with high probability\. On the other hand, when the sample contains any non\-⋆\\star, then the true labeling function has been identified by its private label, guaranteeing 0 test error\. Thus the described proper learner, which does not interpolate, is indeed a PAC learner\.

To see that such noninterpolation is necessary, consider the process which selectshAh\_\{A\}uniformly at random and assigns1/41/4mass uniformly toPnP\_\{n\}, with the remaining3/43/4mass uniform onAC∖PnA^\{C\}\\setminus P\_\{n\}\. For samples of order\|Pn\|​log⁡\(\|Pn\|\)\|P\_\{n\}\|\\log\(\|P\_\{n\}\|\), it will occur with high probability that every marker inPnP\_\{n\}is observed in the training setSS\. Thus all marker hypotheses are noninterpolating forSS\. Then succeeding with an interpolating proper learner amounts to learning the usual first Cantor class — the learner must guess the hidden half\-setAAfrom only a negligible fraction of its complement\. This is impossible\.

#### The exact empirical\-error scale\.

The same construction can be tuned to demonstrate that any numberam=o⁡\(m\)a\_\{m\}=o\(m\)of empirical errors is necessary for certain properly learnable problems\. In particular, fix one sucham=o⁡\(m\)a\_\{m\}=o\(m\)\. We calibrate the number and masses of the markers so that each marker hypothesis incursΘ⁡\(am\)\\Theta\(a\_\{m\}\)errors on anmm\-sample from a realizable distribution\. \(The right values happen to be roughly\|𝒳m\|=Θ⁡\(m3\)\|\\mathcal\{X\}\_\{m\}\|=\\Theta\(m^\{3\}\)and\|Pm\|=min⁡\{eΘ⁡\(am\),m/am\}\|P\_\{m\}\|=\\min\\\{e^\{\\Theta\(a\_\{m\}\)\},\\sqrt\{m/a\_\{m\}\}\\\}, with probabilityΘ⁡\(am/m\)\\Theta\(a\_\{m\}/m\)placed on each marker\.\) As argued previously, a proper learner can only succeed by selecting such a marker hypothesis, thus forcingΩ⁡\(am\)\\Omega\(a\_\{m\}\)training errors with constant probability\.

To demonstrate that a sublinear number of training errors can always be achieved, we first fix an arbitrary \(successful\) proper learnerAA\. We then describe a procedure by whichAAyields a proper learner witho⁡\(m\)o\(m\)empirical errors\. In particular, we trainAAon a prefix of the sample—of carefully chosen length—and then validate its output on the remaining suffix\. If the candidate passes validation, it already makes few errors on the complete sample; otherwise, we simply “forfeit” and output an arbitrary interpolating hypothesis\. Crucially, it is possible to select the prefix length and validation threshold along a sufficiently slow diagonal to achieve ano⁡\(m\)o\(m\)bound while preserving PAC learnability \([Theorems3\.8](https://arxiv.org/html/2608.26516#S3.Thmtheorem8)and[3\.9](https://arxiv.org/html/2608.26516#S3.Thmtheorem9)\)\.

#### Global regularization\.

Our previous “poisoned” Cantor construction demonstrates that a successful proper learner may need to sacrifice empirical fit in order to generalize\. Recall that weighted SRM permits precisely such a trade\-off by minimizing the objectiveh↦L^S​\(h\)\+λ⁡\(S\)​ψ​\(h\)h\\mapsto\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\(S\)\\,\\psi\(h\)\([Equation2](https://arxiv.org/html/2608.26516#S2.E2)\)\. Ruling it out therefore requires a different obstruction\. Rather than merely eliminating every consistent safe hypothesis, we must ensure that every scalar regularizer ranks some statistically bad hypothesis at least as favorably as a good one\.

Our construction begins with three disjoint vertex setsV0,V1,V2V\_\{0\},V\_\{1\},V\_\{2\}, each of sizeNN, connected cyclically by copies of the same bipartite graph, as below\.

V0V\_\{0\}V1V\_\{1\}V2V\_\{2\}

More precisely, for everyr∈ℤ/3​ℤr\\in\\mathbb\{Z\}/3\\mathbb\{Z\}, we orient add\-regular bipartite graph fromVrV\_\{r\}toVr\+1V\_\{r\+1\}\. For a vertexv∈Vrv\\in V\_\{r\}, we writeΓ\+​\(v\)⊆Vr\+1\\Gamma^\{\+\}\(v\)\\subseteq V\_\{r\+1\}to denote its set ofddoutgoing neighbors\. We letS⁡\(v\):=\{v\}∪Γ\+​\(v\)S\(v\):=\\\{v\\\}\\cup\\Gamma^\{\+\}\(v\)denote the support ofvv\. Then only three graph\-theoretic properties are needed: every vertex has large degreedd; the supports of two distinct vertices intersect in at most one point; and any two subsetsU⊆VrU\\subseteq V\_\{r\}andW⊆Vr\+1W\\subseteq V\_\{r\+1\}, each occupying a constant fraction of its respective part, haveΩ⁡\(d​N\)\\Omega\(dN\)edges between them\. Informally, the graph has very small codegree but remains sufficiently dense and well mixed across large sets\. Projective\-plane incidence graphs satisfy these requirements, withN=q2\+q\+1N=q^\{2\}\+q\+1andd=q\+1=Θ⁡\(N\)d=q\+1=\\Theta\(\\sqrt\{N\}\), and we therefore use them in the formal construction\.

For every vertexvv, we introduce a Boolean\-cube blockZv:=\{0,1\}Γ\+​\(v\)Z\_\{v\}:=\\\{0,1\\\}^\{\\Gamma^\{\+\}\(v\)\}, and the domain𝒳N\\mathcal\{X\}\_\{N\}is the disjoint union of all such blocks\. We refer tovvas the*owner*ofZvZ\_\{v\}\. Each vertexuugives rise to a hypothesisgug\_\{u\}in the following manner: on its own blockZuZ\_\{u\}, the hypothesisgug\_\{u\}predicts⋆\\stareverywhere\. On a blockZvZ\_\{v\}for whichu∈Γ\+​\(v\)u\\in\\Gamma^\{\+\}\(v\), it acts like a first Cantor classifier, i\.e\., predicting⋆\\staron half ofZvZ\_\{v\}and a private labelλu\\lambda\_\{u\}on the remaining half ofZvZ\_\{v\}\. In particular, on inputz∈Zv=\{0,1\}Γ\+​\(v\)z\\in Z\_\{v\}=\\\{0,1\\\}^\{\\Gamma^\{\+\}\(v\)\},gug\_\{u\}predicts⋆\\starwhenzu=0z\_\{u\}=0andλu\\lambda\_\{u\}whenzu=1z\_\{u\}=1\. On all remaining blocks, for whichu∉Γ\+​\(v\)u\\notin\\Gamma^\{\+\}\(v\), the hypothesisgug\_\{u\}simply acts as the constant function emittingλu\\lambda\_\{u\}\. Crucially, each blockZvZ\_\{v\}witnesses three kinds of behaviors: the all\-private\-label behavior induced by any classifiergug\_\{u\}withu∉S⁡\(v\)u\\notin S\(v\), the all\-⋆\\starbehavior induced by the ownergvg\_\{v\}, and Cantor\-like behaviors induced by the remaining hypotheses\{gu:u∈Γ\+​\(v\)\}\\\{g\_\{u\}:u\\in\\Gamma^\{\+\}\(v\)\\\}\.

We first argue that the class is properly learnable\. If a private labelλu\\lambda\_\{u\}is observed in the sample, then the true classifier has simply been revealed asgug\_\{u\}\. Otherwise, the sample must consist of only⋆\\star\-labeled points\. If such points lie in two blocksZuZ\_\{u\}andZvZ\_\{v\}, then the target function must belong toS⁡\(u\)∩S⁡\(v\)S\(u\)\\cap S\(v\)\. By the second of our 3 graph\-theoretic properties, this set has cardinality 1, thus revealing the target function\. Finally, if all the⋆\\star\-labeled datapoints lie in a single blockZvZ\_\{v\}, then we can safely predict its ownergvg\_\{v\}, which acts as the all\-⋆\\starclassifier onZvZ\_\{v\}\.

To defeat a regularizerψ\\psi, we first use the cyclic arrangement to find two adjacent partsVrV\_\{r\}andVr\+1V\_\{r\+1\}whose median regularizer values are nonincreasing\. LetUUbe the upper half of the first part andWWthe lower half of the second, as measured by the regularizer\. Since these two large sets spanΩ⁡\(d​N\)\\Omega\(dN\)edges—by our third graph\-theoretic requirement—some vertexv∈Uv\\in UhasΩ⁡\(d\)\\Omega\(d\)outgoing neighborsw∈Ww\\in W\. Each such neighbor satisfiesψ⁡\(gw\)≤ψ⁡\(gv\)\\psi\(g\_\{w\}\)\\leq\\psi\(g\_\{v\}\)\. We then takegvg\_\{v\}as the target and sample unlabeled data uniformly fromZvZ\_\{v\}\. Crucially, every hypothesis other thangvg\_\{v\}incurs population error≥12\\geq\\frac\{1\}\{2\}on this distribution\. However, each neighboringgwg\_\{w\}will happen to interpolate anmm\-sample with probability2−m2^\{\-m\}\. By takingddexponential inmm, some such neighbor will interpolate with constant probability\. On this event, eithergvg\_\{v\}is not a minimizer of the weighted objective, in which case every minimizer is bad, orgvg\_\{v\}is a minimizer and the bad neighbor ties it\. The argument therefore survives arbitrary ties and arbitrary sample\-dependent choices ofλ⁡\(S\)\\lambda\(S\), includingλ⁡\(S\)=0\\lambda\(S\)=0\([Theorem4\.2](https://arxiv.org/html/2608.26516#S4.Thmtheorem2)\)\.

#### Local regularization\.

The preceding lower bound ultimately exploits a single global ranking of the hypotheses\. Local regularization can evade this obstruction by changing its preferences with the test point: at eachxx, it may choose somehS,x∈arg​minh∈VS⁡\(S\)⁡ψ​\(h,x\)h\_\{S,x\}\\in\\argmin\_\{h\\in\\mathrm\{VS\}\(S\)\}\\psi\(h,x\)and predicthS,x​\(x\)h\_\{S,x\}\(x\)\([Equation3](https://arxiv.org/html/2608.26516#S2.E3)\)\. Indeed, on the incidence class above, a local regularizer could simply rank the ownergvg\_\{v\}first throughout its blockZvZ\_\{v\}\. To obtain a lower bound, we therefore need a collection of pointwise preferences that cannot all be satisfied simultaneously\. The cyclic structure of the preceding construction remains useful, but the projective\-plane geometry is no longer needed: it suffices to simply consider a complete tripartite graph\.

In particular, for each sample sizemm, setN=2m−1N=2^\{m\-1\}and consider the complete tripartite graphGm=KN,N,NG\_\{m\}=K\_\{N,N,N\}\. An unlabeled datapoint is an orientation of every edge ofGmG\_\{m\}, and each edgee=\{a,b\}e=\\\{a,b\\\}defines a hypothesisheh\_\{e\}that outputs the endpoint toward whicheeis directed\. Thus every hypothesis uses only two labels, and improper learning is immediate: two observed labels identify the target edge, while a sample containing only one label permits the corresponding constant predictor\. The lower bound, meanwhile, is witnessed by directed cyclic triangles\. Given a test orientation, letffbe the earliest edge of such a triangle in the local regularizer’s order, leteebe the preceding edge around the cycle, and letaabe the tail offf\. Then the targetheh\_\{e\}predictsaa, whereas the locally preferred hypothesishfh\_\{f\}does not\. The learner must therefore err wheneverffsurvives the sample and every incident edge ranked ahead of it is eliminated, an event of probability at least2−m​\(1−2−m\)2​N2^\{\-m\}\(1\-2^\{\-m\}\)^\{2N\}\. A random orientation containsN3/4N^\{3\}/4directed cyclic triangles on average, compared with only3​N23N^\{2\}possible target edges\. TakingN=2m−1N=2^\{m\-1\}and averaging over these witnesses yields a target\-distribution pair on which the learner has constant error \([Theorem4\.6](https://arxiv.org/html/2608.26516#S4.Thmtheorem6)\)\.

#### Positive results\.

Our positive results are organized around the complementary ideas of*localization*and*integrability*\. Localization asks whether the ambiguity remaining after observing the sample is substantially simpler than the full hypothesis class\. The cleanest example is a finite fallback coreℱ\\mathcal\{F\}: every realizable sample either uniquely identifies the target or leaves at least one member ofℱ\\mathcal\{F\}consistent\. An SRM rule may therefore rankℱ\\mathcal\{F\}first, after which an ordinary finite\-class generalization bound completes the argument\. More generally, it suffices that every sampleSSwith\|VS⁡\(S\)\|\>1\|\\mathrm\{VS\}\(S\)\|\>1retain a consistent hypothesis inside a regularizer sublevelℋrm:=\{h:ψ⁡\(h\)≤rm\}\\mathcal\{H\}\_\{r\_\{m\}\}:=\\\{h:\\psi\(h\)\\leq r\_\{m\}\\\}whose complexity grows sufficiently slowly withmm\. Ordered disagreement gives a target\-dependent version of the same principle\. Since the targeth⋆h^\{\\star\}is always consistent, every SRM outputggsatisfiesψ⁡\(g\)≤ψ⁡\(h⋆\)\\psi\(g\)\\leq\\psi\(h^\{\\star\}\)\. We therefore need not control the full classℋ\\mathcal\{H\}; it is enough to bound the VC dimension of the disagreement sets\{x:g⁡\(x\)≠h⋆​\(x\)\}\\\{x:g\(x\)\\neq h^\{\\star\}\(x\)\\\}generated by hypotheses lying belowh⋆h^\{\\star\}in the regularizer order\. Anε\\varepsilon\-net argument then ensures that every such disagreement set of substantial mass is hit by the sample, forcing the SRM output to have small population error \([Theorems5\.3](https://arxiv.org/html/2608.26516#S5.Thmtheorem3),[5\.4](https://arxiv.org/html/2608.26516#S5.Thmtheorem4),[5\.5](https://arxiv.org/html/2608.26516#S5.Thmtheorem5)and[5\.7](https://arxiv.org/html/2608.26516#S5.Thmtheorem7)\)\.

Integrability instead begins with a learner and asks whether its sample\-dependent choices can be represented by one regularizer\. Whenever a consistent learner chooseshhwhile another hypothesisggremains feasible, it reveals a preference forhhovergg\. In the hard\-SRM setting, such choices admit a scalar representation exactly when the resulting preference relation is acyclic\. Weighted SRM also records the empirical\-loss margin supporting each preference, producing a system of strict difference constraints on the valuesψ⁡\(h\)\\psi\(h\)\. Summing these inequalities around a cycle eliminates the unknown potential; over finite systems, positivity of every cycle is both necessary and sufficient for reconstructing a regularizer realizing all of the learner’s choices \([Theorems5\.11](https://arxiv.org/html/2608.26516#S5.Thmtheorem11)and[5\.14](https://arxiv.org/html/2608.26516#S5.Thmtheorem14)\)\.

### 1\.3Related work

#### Multiclass learnability\.

[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3)introduced the DS dimension and conjectured it to characterize improper multiclass learnability over arbitrary label sets\. This characterization was later confirmed by the breakthrough work of[Brukhim et al\. \(2022\)](https://arxiv.org/html/2608.26516#bib.bib2), using an intricate learner based upon list\-learning reductions and orientations of one\-inclusion graphs\. More recently,[Pabbaraju \(2026\)](https://arxiv.org/html/2608.26516#bib.bib10)settled the sample complexity of realizable multiclass learning by proving a quantitative version of a Daniely–Shalev\-Schwartz conjecture, building upon combinatorial work of[Hanneke et al\. \(2026\)](https://arxiv.org/html/2608.26516#bib.bib24)\. The separation between proper and improper multiclass learning originates in the first Cantor construction of[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3), which exhibits a learnable class admitting no proper learner\.[Asilis et al\. \(2025b\)](https://arxiv.org/html/2608.26516#bib.bib7)strengthened this obstruction by ruling out every aggregation of a bounded number of proper learners for general multiclass problems\. Furthermore,[Asilis et al\. \(2025a\)](https://arxiv.org/html/2608.26516#bib.bib11)demonstrated that proper learnability can be a poorly\-behaved condition, by proving that it cannot be characterized by any combinatorial dimension, and that it can even be logically undecidable\([Ben\-David et al\., 2019](https://arxiv.org/html/2608.26516#bib.bib13)\)\.

#### Regularization in multiclass learning\.

Structural risk minimization is among the classical mechanisms for trading empirical fit against hypothesis complexity\([Shalev\-Shwartz and Ben\-David, 2014](https://arxiv.org/html/2608.26516#bib.bib6)\)\. In multiclass learning,[Asilis et al\. \(2024b\)](https://arxiv.org/html/2608.26516#bib.bib4)showed that optimal learners can be expressed through substantially more flexible notions of regularization: the regularizer may be inferred from unlabeled data and may depend upon the test point, thereby combining different hypotheses across different regions of the domain\. The necessity of these relaxations motivated the question of[Asilis et al\. \(2024a\)](https://arxiv.org/html/2608.26516#bib.bib5), who asked whether a fixed local regularizer can nevertheless learn every multiclass problem\.[Jafar et al\. \(2025\)](https://arxiv.org/html/2608.26516#bib.bib12)gave a negative answer in the transductive setting while leaving the PAC model open\. We exhibit a tripartite construction that furthermore rules out local regularization in the PAC model, settling the problem completely\. We note that the concurrent and independent work of[Hou \(2026\)](https://arxiv.org/html/2608.26516#bib.bib23)obtains a closely related counterexample derived from tournaments on complete graphs\. Both proofs exploit directed cyclic triangles as certificates of incompatible local preferences, but the analyses proceed differently:[Hou \(2026\)](https://arxiv.org/html/2608.26516#bib.bib23)first expresses the learner’s risk as a weighted count of inversions in the local edge order, whereas our tripartite construction isolates from each cyclic triangle a concrete bad edge whose survival forces an error, allowing for a somewhat more direct argument\. On the proper side, prior work asked whether the promise of proper learnability is enough to recover classical SRM as a general learner\([Asilis et al\., 2025a](https://arxiv.org/html/2608.26516#bib.bib11)\)\. We again answer this question in the negative, even when the coefficient on the regularization term is permitted to depend arbitrarily upon the complete labeled sample\.

#### Revealed preferences and integrability\.

Our representation results connect SRM with the classical theory of rational choice\. A deterministic learner choosing from sets of feasible hypotheses defines a choice rule, and asking for an SRM representation amounts to asking whether these choices can be rationalized by one scalar ordering\. Acyclicity, contraction consistency, and path independence are familiar themes in this literature\([Plott, 1973](https://arxiv.org/html/2608.26516#bib.bib14)\)\. Weighted SRM introduces sample\-dependent empirical\-loss offsets, leading instead to systems of difference constraints and corresponding cycle conditions\. This perspective bears a broad resemblance to revealed\-preference and cyclic\-monotonicity arguments in economics and mechanism design\([Afriat, 1967](https://arxiv.org/html/2608.26516#bib.bib16);[Rochet, 1987](https://arxiv.org/html/2608.26516#bib.bib15)\), although the formal settings and questions are different\.

## 2Preliminaries

Our setting is realizable multiclass PAC learning\.𝒳\\mathcal\{X\}and𝒴\\mathcal\{Y\}are, respectively, an arbitrary unlabeled data domain and label set\. We permit𝒴\\mathcal\{Y\}to be infinite throughout the paper\. Ahypothesis classis a setℋ⊆𝒴𝒳\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}, and a labeledexampleis a pair\(x,y\)∈𝒳×𝒴\(x,y\)\\in\\mathcal\{X\}\\times\\mathcal\{Y\}\. Given a sampleS=\(\(x1,y1\),…,\(xm,ym\)\)S=\(\(x\_\{1\},y\_\{1\}\),\\ldots,\(x\_\{m\},y\_\{m\}\)\), itsempirical lossisL^S\(h\):=1m∑i=1m𝟏\{h\(xi\)≠yi\}\\widehat\{L\}\_\{S\}\(h\):=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}\\mathbf\{1\}\\\{h\(x\_\{i\}\)\\neq y\_\{i\}\\\}\. For a distributionDDon𝒳\\mathcal\{X\}and a targeth⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}, the population loss ofhhisLD\(h,h⋆\):=ℙx∼D\[h\(x\)≠h⋆\(x\)\]L\_\{D\}\(h,h^\{\\star\}\):=\\P\_\{x\\sim D\}\[h\(x\)\\neq h^\{\\star\}\(x\)\]\. A sample isrealizableif there exists anh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}such thatyi=h⋆​\(xi\)​∀iy\_\{i\}=h^\{\\star\}\(x\_\{i\}\)\\,\\,\\forall i\. Alearneris a function\(𝒳×𝒴\)<ω→𝒴𝒳\(\\mathcal\{X\}\\times\\mathcal\{Y\}\)^\{<\\omega\}\\to\\mathcal\{Y\}^\{\\mathcal\{X\}\}, and isproperif its output always lies inℋ\\mathcal\{H\}, otherwiseimproper\. We say thatAAPAC learnsℋ\\mathcal\{H\}if for everyε,δ∈\(0,1\)\\varepsilon,\\delta\\in\(0,1\)there existsnA​\(ε,δ\)n\_\{A\}\(\\varepsilon,\\delta\)such that for allm≥nA​\(ε,δ\)m\\geq n\_\{A\}\(\\varepsilon,\\delta\), everyh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}, and every marginalDD,

ℙS∼Dm\[LD\(A\(S\),h⋆\)\>ε\]≤δ,\\P\_\{S\\sim D^\{m\}\}\\left\[L\_\{D\}\(A\(S\),h^\{\\star\}\)\>\\varepsilon\\right\]\\leq\\delta,where the sample is labeled byh⋆h^\{\\star\}\.

Theversion spaceof a realizable sampleSSis

VS⁡\(S\):=\{h∈ℋ:L^S​\(h\)=0\}\.\\mathrm\{VS\}\(S\):=\\left\\\{h\\in\\mathcal\{H\}:\\widehat\{L\}\_\{S\}\(h\)=0\\right\\\}\.Aconsistentproper learner, or*interpolating*proper learner, is one whose output always lies inVS⁡\(S\)\\mathrm\{VS\}\(S\)\. A realizable sampleSSis said to beambiguousif\|VS⁡\(S\)\|≥2\|\\mathrm\{VS\}\(S\)\|\\geq 2\.

### 2\.1Regularization models

Aregularizerforℋ\\mathcal\{H\}is a functionψ:ℋ→ℝ≥0\\psi:\\mathcal\{H\}\\to\\mathbb\{R\}\_\{\\geq 0\}, thought of as encoding an inductive bias over hypotheses inℋ\\mathcal\{H\}\. Roughly, hypothesesh∈ℋh\\in\\mathcal\{H\}with smaller values underψ\\psiare thought of as being preferred byψ\\psi, perhaps owing to their “simplicity\.” Alocal regularizerforℋ\\mathcal\{H\}is a functionψ:ℋ×𝒳→ℝ≥0\\psi:\\mathcal\{H\}\\times\\mathcal\{X\}\\to\\mathbb\{R\}\_\{\\geq 0\}, likewise thought of as expressing preferences over hypotheses inℋ\\mathcal\{H\}, but at a more granular, location\-dependent level\.

We now describe three manners in which \(local\) regularizers give rise to Structural Risk Minimization \(SRM\) learners\. In particular, Hard SRM minimizesψ\\psiamong interpolating hypotheses forSS\(i\.e\., among the version spaceVS⁡\(S\)\\mathrm\{VS\}\(S\)\), Weighted SRM minimizes the sum of empirical risk andψ\\psiacross all ofℋ\\mathcal\{H\}, and local regularization minimizesψ⁡\(⋅,xtest\)\\psi\(\\,\\cdot\\,,x\_\{\\mathrm\{test\}\}\)locally atxtestx\_\{\\mathrm\{test\}\}among interpolating hypotheses\.

###### Definition 2\.1\(Hard SRM\)\.

Letψ\\psibe a regularizer forℋ\\mathcal\{H\}\. A learnerAAis said to beinducedbyψ\\psias a hard\-SRM learner if the following condition holds over all realizable samplesSS,

A⁡\(S\)∈arg​minh∈ℋ⁡\{ψ⁡\(h\):h∈VS⁡\(S\)\}\.A\(S\)\\in\\argmin\_\{h\\in\\mathcal\{H\}\}\\big\\\{\\psi\(h\):h\\in\\mathrm\{VS\}\(S\)\\big\\\}\.\(1\)Should all hard\-SRM learners induced byψ\\psisuccessfully learnℋ\\mathcal\{H\}, thenψ\\psiitself is said tolearnℋ\\mathcal\{H\}\.

###### Definition 2\.2\(Weighted SRM\)\.

Letψ\\psibe a regularizer forℋ\\mathcal\{H\}and letλ:\(𝒳×𝒴\)<ω→ℝ≥0\\lambda:\(\\mathcal\{X\}\\times\\mathcal\{Y\}\)^\{<\\omega\}\\to\\mathbb\{R\}\_\{\\geq 0\}\. A learnerAAisinducedby the pair\(ψ,λ\)\(\\psi,\\lambda\)as a weighted\-SRM learner if for all samplesSS,

A⁡\(S\)∈arg​minh∈ℋ⁡\{L^S​\(h\)\+λ⁡\(S\)​ψ​\(h\)\}\.A\(S\)\\in\\argmin\_\{h\\in\\mathcal\{H\}\}\\left\\\{\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\(S\)\\,\\psi\(h\)\\right\\\}\.\(2\)Should all weighted SRM learners induced by the pair\(ψ,λ\)\(\\psi,\\lambda\)be PAC learners forℋ\\mathcal\{H\}, then they are said tolearnℋ\\mathcal\{H\}\.

###### Definition 2\.3\(Local Regularization\)\.

Letψ:ℋ×𝒳→ℝ≥0\\psi:\\mathcal\{H\}\\times\\mathcal\{X\}\\to\\mathbb\{R\}\_\{\\geq 0\}be a local regularizer\. A learnerAAisinducedbyψ\\psiif for all samplesSSand pointsx∈𝒳x\\in\\mathcal\{X\},

A⁡\(S\)​\(x\)∈arg​min⁡\{ψ⁡\(h,x\):h∈VS⁡\(S\)\}\.A\(S\)\(x\)\\in\\argmin\\big\\\{\\psi\(h,x\):h\\in\\mathrm\{VS\}\(S\)\\big\\\}\.\(3\)When all learners induced byψ\\psiare PAC learners forℋ\\mathcal\{H\}, thenψ\\psiis said tolearnℋ\\mathcal\{H\}\.

A notable feature of our definitions is that we only crown a \(local\) regularizerψ\\psias having successfully learned a hypothesis classℋ\\mathcal\{H\}if*all*learners it induces are PAC learners forℋ\\mathcal\{H\}\. In short, we take a worst\-case perspective with respect to tie\-breaking of theargmin\\mathrm\{argmin\}in[Equations1](https://arxiv.org/html/2608.26516#S2.E1),[2](https://arxiv.org/html/2608.26516#S2.E2)and[3](https://arxiv.org/html/2608.26516#S2.E3): any fixed choice of tie\-breaking must produce a successful learner\. Semantically, this amounts to requiring that the success of a regularizerψ\\psiowe itself only to discernments made byψ\\psi, not a particular sequence of good tie\-breaking decisions\.

### 2\.2Topological conditions

Several of our forthcoming results take the form of impossibility theorems, prohibiting families of regularization\-based learners from succeeding on certain learnable problems\. We have found that such learnable counter\-examples can often be found — in a somewhat artificial way — by exploiting hypothesis classes that are not topologically closed, i\.e\., that do not contain all their limit points\. Briefly, the idea is that one can designℋ\\mathcal\{H\}lacking a limit pointffwhich could easily be learned by a regularizer favoringffover all other hypotheses, if onlyffwere inℋ\\mathcal\{H\}\. In order to exclude such classes, we thus require all counter\-examples presented in the paper to satisfy two regularity conditions\.

The first requirement is thatℋ\\mathcal\{H\}should be closed in the product topology on𝒴𝒳\\mathcal\{Y\}^\{\\mathcal\{X\}\}, when𝒴\\mathcal\{Y\}is endowed with the discrete topology\. \(I\.e\., the topology given by the 0\-1 loss function on𝒴\\mathcal\{Y\}\.\) In the event that𝒴\\mathcal\{Y\}is infinite, however, closedness ofℋ\\mathcal\{H\}can be “cheated” by simply appending a single point to the domain𝒳\\mathcal\{X\}and having each hypothesis emit a unique label on that point\. As our second condition, we thus require that\|ℋ⁡\(x\)\|=\|\{h⁡\(x\):h∈ℋ\}\|\|\\mathcal\{H\}\(x\)\|=\|\\\{h\(x\):h\\in\\mathcal\{H\}\\\}\|be finite at eachx∈𝒳x\\in\\mathcal\{X\}, which we refer to as having*pointwise finite range*\.444Note that this is a pointwise condition, not a uniform one —\|ℋ⁡\(x\)\|\|\\mathcal\{H\}\(x\)\|is permitted to attain arbitrarily large \(but finite\!\) values acrossx∈𝒳x\\in\\mathcal\{X\}\.

###### Definition 2\.4\.

Letℋ⊆𝒴𝒳\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}be a hypothesis class\.

1. \(i\)We say thatℋ\\mathcal\{H\}is*closed*if it is closed in the product topology on𝒴𝒳\\mathcal\{Y\}^\{\\mathcal\{X\}\}when each copy of𝒴\\mathcal\{Y\}carries the discrete topology\.
2. \(ii\)We say thatℋ\\mathcal\{H\}has*pointwise finite range*if for everyx∈𝒳x\\in\\mathcal\{X\}the following set is finite: ℋ⁡\(x\):=\{h⁡\(x\):h∈ℋ\}\.\\mathcal\{H\}\(x\):=\\big\\\{h\(x\):h\\in\\mathcal\{H\}\\big\\\}\.
3. \(iii\)A finite setI⊆𝒳I\\subseteq\\mathcal\{X\}is an*identifier*forℋ\\mathcal\{H\}if the restriction maph↦h↾Ih\\mapsto\{h\}\\\!\\upharpoonright\_\{I\}is an injection onℋ\\mathcal\{H\}\.

It is useful to observe that the product\-topological definition of closedness admits an elementary finite\-projection reformulation\. The following lemma arises directly from the definition of the product topology\.

###### Lemma 2\.5\.

A classℋ⊆𝒴𝒳\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}is closed if and only if the following holds: wheneverf:𝒳→𝒴f:\\mathcal\{X\}\\to\\mathcal\{Y\}has the property that for every finiteI⊆𝒳I\\subseteq\\mathcal\{X\}there existshI∈ℋh\_\{I\}\\in\\mathcal\{H\}withf↾I=hI↾I\{f\}\\\!\\upharpoonright\_\{I\}=\{h\_\{I\}\}\\\!\\upharpoonright\_\{I\}, thenf∈ℋf\\in\\mathcal\{H\}\.

It is not difficult to see from Lemma[2\.5](https://arxiv.org/html/2608.26516#S2.Thmtheorem5)that any classℋ\\mathcal\{H\}with a finite identifierIIis automatically rendered closed, by considering sets of the formI∪\{x\}I\\cup\\\{x\\\}for eachx∈𝒳x\\in\\mathcal\{X\}\. Conversely, ifℋ\\mathcal\{H\}is infinite and has pointwise finite range, then it cannot admit a finite identifier, as for any finiteI⊆𝒳I\\subseteq\\mathcal\{X\}one has that\|ℋ↾I\|≤∏x∈I\|ℋ\(x\)\|<∞\\left\|\{\\mathcal\{H\}\}\\\!\\upharpoonright\_\{I\}\\right\|\\leq\\prod\_\{x\\in I\}\\left\|\\mathcal\{H\}\(x\)\\right\|<\\infty\. Thus the pointwise finite range condition precludes this “identifier trick” so long asℋ\\mathcal\{H\}is infinite\.

Finally, we note that the combination of both closedness and pointwise finite range — which we employ in our negative results — is sufficiently strong so as to ensure that all projections ofℋ\\mathcal\{H\}to a subdomainA⊆𝒳A\\subseteq\\mathcal\{X\}are likewise closed \(and furthermore compact\)\.

###### Lemma 2\.6\.

Ifℋ\\mathcal\{H\}is closed and has pointwise finite range, then the restrictionℋ↾A:=\{h↾A:h∈ℋ\}\{\\mathcal\{H\}\}\\\!\\upharpoonright\_\{A\}:=\\left\\\{\{h\}\\\!\\upharpoonright\_\{A\}:h\\in\\mathcal\{H\}\\right\\\}is closed and compact in𝒴A\\mathcal\{Y\}^\{A\}for eachA⊆𝒳A\\subseteq\\mathcal\{X\}\.

LetK:=∏x∈𝒳ℋ⁡\(x\)K:=\\prod\_\{x\\in\\mathcal\{X\}\}\\mathcal\{H\}\(x\)\. Asℋ\\mathcal\{H\}has pointwise finite range, each factorℋ⁡\(x\)\\mathcal\{H\}\(x\)is finite and thus compact\. By Tychonoff’s theorem,KKis thus compact\. Thenℋ\\mathcal\{H\}is a closed subset ofKK, hence compact\. The restriction mapπA:h↦h↾A\\pi\_\{A\}:h\\mapsto\{h\}\\\!\\upharpoonright\_\{A\}is continuous, soπA\(ℋ\)=ℋ↾A\\pi\_\{A\}\(\\mathcal\{H\}\)=\{\\mathcal\{H\}\}\\\!\\upharpoonright\_\{A\}is compact in𝒴A\\mathcal\{Y\}^\{A\}\. Finally, as𝒴A\\mathcal\{Y\}^\{A\}is Hausdorff, its compact subsets are closed\. ∎

## 3Proper Learning and Noninterpolation

We begin by establishing two limitations of proper learning\. First, we demonstrate in[Section3\.1](https://arxiv.org/html/2608.26516#S3.SS1)that general multiclass learning does not reduce to proper learning in the manner posited by[Open Problem3](https://arxiv.org/html/2608.26516#Thmproblem3)\. In particular,[Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1)exhibits a learnable multiclass problemℋ\\mathcal\{H\}that cannot be enveloped by any properly learnable classℋprop\\mathcal\{H\}\_\{\\mathrm\{prop\}\}, i\.e\.,ℋ⊆ℋprop\\mathcal\{H\}\\subseteq\\mathcal\{H\}\_\{\\mathrm\{prop\}\}\. Subsequently, in[Section3\.2](https://arxiv.org/html/2608.26516#S3.SS2), we demonstrate that proper learning requires one to tolerate empirical error: That is, there exist properly learnable problems for which all successful proper learners must err on realizable training samples\. In[Section3\.3](https://arxiv.org/html/2608.26516#S3.SS3), we give a precise quantitative account of this phenomenon, by showing that there always exists a proper learner making a sublinear number of errorso⁡\(n\)o\(n\)on training sets of sizenn, and conversely that any sublinear error ratean=o⁡\(n\)a\_\{n\}=o\(n\)can be made necessary on certain properly learnable problems\.

### 3\.1Learning does not reduce to proper learning

The following theorem resolves[Open Problem3](https://arxiv.org/html/2608.26516#Thmproblem3), first articulated \(in the converse direction\) as Conjecture 18 of[Asilis et al\. \(2025a\)](https://arxiv.org/html/2608.26516#bib.bib11)\.

###### Theorem 3\.1\.

There exists a learnable multiclass hypothesis classℋ\\mathcal\{H\}that cannot be embedded into any properly learnable class\. That is, there does not exist any properly learnable classℋprop\\mathcal\{H\}\_\{\\mathrm\{prop\}\}such thatℋ⊆ℋprop\\mathcal\{H\}\\subseteq\\mathcal\{H\}\_\{\\mathrm\{prop\}\}\.

The remainder of this subsection is devoted to proving[Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1)\.

We start with the construction of the data domain𝒳\\mathcal\{X\}, the label set𝒴\\mathcal\{Y\}, and the hypothesis classℋ\\mathcal\{H\}\.

#### Construction\.

For eachd≥1d\\geq 1, letTdT\_\{d\}denote the infinite complete2d2^\{d\}\-ary tree whose children at every depth are indexed by\{0,1\}d\\\{0,1\\\}^\{d\}\. A nodevvofTdT\_\{d\}at depthkkcan be identified as a sequencev=\(b1,…,bk\)v=\(b\_\{1\},\\dotsc,b\_\{k\}\)wherebi∈\{0,1\}db\_\{i\}\\in\\\{0,1\\\}^\{d\}:

- •The root at depth 0 is∅\\varnothing\.
- •A nodev=\(b1,…,bk\)v=\(b\_\{1\},\\dotsc,b\_\{k\}\)at depthkkhas2d2^\{d\}children of the form\(v,bk\+1\)\(v,b\_\{k\+1\}\)forbk\+1∈\{0,1\}db\_\{k\+1\}\\in\\\{0,1\\\}^\{d\}\.

Using the treeTdT\_\{d\}, we now define the domain𝒳\\mathcal\{X\}\. Letting\|v\|\|v\|denote the depth ofvv, for each nodev∈Tdv\\in T\_\{d\}definedddomain pointsxd,v,jx\_\{d,v,j\}forj∈\[d\]j\\in\[d\]\. Let

𝒳=⋃d≥1⋃v∈Td\{xd,v,j:j∈\[d\]\}\.\\mathcal\{X\}=\\bigcup\_\{d\\geq 1\}\\bigcup\_\{v\\in T\_\{d\}\}\\\{x\_\{d,v,j\}:j\\in\[d\]\\\}\.We call\{xd,v,j:j∈\[d\]\}\\\{x\_\{d,v,j\}:j\\in\[d\]\\\}theblockof nodevv\.

Each hypothesis in our constructed hypothesis class will correspond to choosing a finite path inTdT\_\{d\}and choosing one domain point in every non\-terminal block along the path to label with 0 or 1\. All other domain points are assigned a fixed label \(other than 0 and 1\) that can immediately identify the hypothesis\. Formally, for anyℓ≥1\\ell\\geq 1, anyb=\(b1,…,bℓ\)∈∏i=1ℓ\{0,1\}db=\(b\_\{1\},\\dotsc,b\_\{\\ell\}\)\\in\\prod\_\{i=1\}^\{\\ell\}\\\{0,1\\\}^\{d\}, andu=\(u1,…,uℓ\)∈\[d\]ℓu=\(u\_\{1\},\\dotsc,u\_\{\\ell\}\)\\in\[d\]^\{\\ell\}, define the hypothesis

hd,b,u\(x\)=\{bi​\(ui\)ifx=xd,\(b1,…,bi−1\),uifor somei∈\[ℓ\],αd,b,uifx∉\{xd,\(b1,…,bi−1\),ui:i∈\[ℓ\]\},h\_\{d,b,u\}\(x\)=\\begin\{cases\}b\_\{i\}\(u\_\{i\}\)&\\text\{if $x=x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),u\_\{i\}\}$ for some $i\\in\[\\ell\]$\},\\\\ \\alpha\_\{d,b,u\}&\\text\{if $x\\notin\\\{x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),u\_\{i\}\}:i\\in\[\\ell\]\\\}$\},\\end\{cases\}wherebi​\(ui\)b\_\{i\}\(u\_\{i\}\)denotes theuiu\_\{i\}\-th component ofbib\_\{i\}\. Hereuuspecifies which domain points are labeled with 0 or 1 on nodes along the path\. Call the unique labelsαd,b,u\\alpha\_\{d,b,u\}that identify the hypothesisprivatelabels, and callbi​\(ui\)∈\{0,1\}b\_\{i\}\(u\_\{i\}\)\\in\\\{0,1\\\}thepubliclabels\.

We finish the construction by defining the hypothesis class

ℋ=\{hd,b,u:d≥1,ℓ≥1,b∈∏i=1ℓ\{0,1\}d,u∈\[d\]ℓ\}\.\\mathcal\{H\}=\\left\\\{h\_\{d,b,u\}:d\\geq 1,\\ell\\geq 1,b\\in\\prod\_\{i=1\}^\{\\ell\}\\\{0,1\\\}^\{d\},u\\in\[d\]^\{\\ell\}\\right\\\}\.The label set𝒴\\mathcal\{Y\}consists of the public labels\{0,1\}\\\{0,1\\\}along with all private labels defined above:

𝒴=\{0,1\}∪\{αd,b,u:d≥1,ℓ≥1,b∈∏i=1ℓ\{0,1\}d,u∈\[d\]ℓ\}\.\\mathcal\{Y\}=\\\{0,1\\\}\\cup\\left\\\{\\alpha\_\{d,b,u\}:d\\geq 1,\\ell\\geq 1,b\\in\\prod\_\{i=1\}^\{\\ell\}\\\{0,1\\\}^\{d\},u\\in\[d\]^\{\\ell\}\\right\\\}\.

#### An improper learner\.

As mentioned earlier, we construct an improper learner that either sees the private label and recovers the target exactly, or uses a deepest public example to reconstruct all preceding blocks\.

Given a sampleSS, the learnerAAproceeds as follows:

1. 1\.If a private labelαd,b,u\\alpha\_\{d,b,u\}appears, then output the uniquely identified hypothesishd,b,uh\_\{d,b,u\}\(note thatℓ\\ellis also identified with the length of the vectorsbbanduu\)\.
2. 2\.Otherwise, all the labels are in\{0,1\}\\\{0,1\\\}\. Choose any labeled example\(xd,v,j,y\)\(x\_\{d,v,j\},y\)where\|v\|\|v\|is maximal in the data\. Letv=\(b1,…,bi∗−1\)v=\(b\_\{1\},\\dotsc,b\_\{i^\{\*\}\-1\}\)wherei∗=\|v\|\+1i^\{\*\}=\|v\|\+1andui∗=ju\_\{i^\{\*\}\}=j\. Output the classifier hS​\(x\)=\{y\(ifx=xd,\(b1,…,bi∗−1\),ui∗\),bi​\(j\)\(ifx=xd,\(b1,…,bi−1\),jfor somei<i∗,j∈\[d\]\),0otherwise\.h\_\{S\}\(x\)=\\begin\{cases\}y&\\text\{\(if $x=x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i^\{\\ast\}\-1\}\),u\_\{i^\{\*\}\}\}$\)\},\\\\ b\_\{i\}\(j\)&\\text\{\(if $x=x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),j\}$ for some $i<i^\{\*\},j\\in\[d\]$\)\},\\\\ 0&\\text\{otherwise\}\.\\end\{cases\}In words, choose the domain point that has the largest depth and use that as the reference example to recover the labels in all preceding blocks\.

AAis an improper learner becausehS​\(x\)h\_\{S\}\(x\)produced by the second case assigns public labels to the whole block of the node at depthi−1i\-1wherei<i∗i<i^\{\*\}according tobi​\(⋅\)b\_\{i\}\(\\cdot\), but any hypothesis inℋ\\mathcal\{H\}assigns a public label to only one element of the block\.

We next show thatAAis a PAC learner\.

###### Lemma 3\.2\.

For every target hypothesish∈ℋh\\in\\mathcal\{H\}, distributionDDon𝒳\\mathcal\{X\}, errorε∈\(0,1\)\\varepsilon\\in\(0,1\), and sample sizem≥1m\\geq 1, we have

ℙ\[LD\(A\(S\),h\)\>ε\]≤e−m​ε\.\\P\[L\_\{D\}\(A\(S\),h\)\>\\varepsilon\]\\leq e^\{\-m\\varepsilon\}\.

The proof first handles the easy private\-label case\. For the remaining case we bound the probability that every example lies in a public prefix whose mass is less than1−ε1\-\\varepsilon\.

Leth=hd,b,uh=h\_\{d,b,u\}\. IfSSever contains a private label, then by construction the learner recovershhexactly\.

For the case where every example inSShas a public label, leti∗=\|v\|\+1i^\{\*\}=\|v\|\+1be the index of the reference example\. Forj=0,1,…,ℓj=0,1,\\dotsc,\\ellletPjP\_\{j\}be the set of domain points to whichhd,b,uh\_\{d,b,u\}has given public labels in the firstjjdepths\. Formally,

Pj:=\{xd,\(b1,…,bi−1\),ui:1≤i≤j\},P0:=∅\.P\_\{j\}:=\\\{x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),u\_\{i\}\}:1\\leq i\\leq j\\\},\\quad P\_\{0\}:=\\varnothing\.Observe that the outputhS​\(⋅\)h\_\{S\}\(\\cdot\)is correct onPi∗P\_\{i^\{\*\}\}\. Therefore, even ifhS​\(⋅\)h\_\{S\}\(\\cdot\)is wrong everywhere else, we still haveLD​\(A⁡\(S\),h\)≤1−D⁡\(Pi∗\)L\_\{D\}\(A\(S\),h\)\\leq 1\-D\(P\_\{i^\{\*\}\}\)\. HereD\(Z\):=ℙx∼D\[x∈Z\]D\(Z\):=\\P\_\{x\\sim D\}\[x\\in Z\]\.

IfD⁡\(Pi∗\)≥1−εD\(P\_\{i^\{\*\}\}\)\\geq 1\-\\varepsilonthen we are done\. If not, letiεi\_\{\\varepsilon\}be the largesti∈\{0,1,…,ℓ\}i\\in\\\{0,1,\\dotsc,\\ell\\\}such thatD⁡\(Pi\)<1−εD\(P\_\{i\}\)<1\-\\varepsilon\. By assumption,iεi\_\{\\varepsilon\}exists andi∗≤iεi^\{\*\}\\leq i\_\{\\varepsilon\}\. Since every example has a public label and has depth at mosti∗−1i^\{\*\}\-1, every example is also inPiεP\_\{i\_\{\\varepsilon\}\}\. Therefore

ℙ\[LD\(A\(S\),h\)\>ε\]≤D\(Piε\)m<\(1−ε\)m≤e−m​ε\\P\[L\_\{D\}\(A\(S\),h\)\>\\varepsilon\]\\leq D\(P\_\{i\_\{\\varepsilon\}\}\)^\{m\}<\(1\-\\varepsilon\)^\{m\}\\leq e^\{\-m\\varepsilon\}as desired\. ∎

#### No properly learnable envelope exists\.

We prove the stronger statement that every \(possibly randomized\) PAC learnerAAforℋ\\mathcal\{H\}satisfiesDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\infty, as promised in[Section1\.2](https://arxiv.org/html/2608.26516#S1.SS2)\. This immediately proves[Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1)\. Indeed, ifℋ⊆ℋprop\\mathcal\{H\}\\subseteq\\mathcal\{H\}\_\{\\mathrm\{prop\}\}andℋprop\\mathcal\{H\}\_\{\\mathrm\{prop\}\}has a proper PAC learnerAA, thenim⁡\(A\)⊆ℋprop\\operatorname\{im\}\(A\)\\subseteq\\mathcal\{H\}\_\{\\mathrm\{prop\}\}, soDS\(ℋprop\)=∞\\DS\(\\mathcal\{H\}\_\{\\mathrm\{prop\}\}\)=\\infty, which contradicts the fact thatℋprop\\mathcal\{H\}\_\{\\mathrm\{prop\}\}is learnable\.

Fix an arbitrary PAC learnerAAforℋ\\mathcal\{H\}, and letnA​\(ε,δ\)n\_\{A\}\(\\varepsilon,\\delta\)be its sample complexity bound\. Fix anyd≥1d\\geq 1and consider the corresponding treeTdT\_\{d\}\. We first prove the following dichotomy, which says that eitherim⁡\(A\)\\operatorname\{im\}\(A\)is very rich or it systematically misses certain patterns\.

###### Lemma 3\.3\.

For a nodev∈Tdv\\in T\_\{d\}, identify a vectorc∈\{0,1\}dc\\in\\\{0,1\\\}^\{d\}as a function on the block

Ed,v:=\{xd,v,j:j∈\[d\]\}E\_\{d,v\}:=\\\{x\_\{d,v,j\}:j\\in\[d\]\\\}that mapsxd,v,jx\_\{d,v,j\}toc⁡\(j\)c\(j\), wherec⁡\(j\)c\(j\)denotes thejjth component ofcc\. Then at least one of the following holds:

Condition 1There exists a nodev∈Tdv\\in T\_\{d\}such that

∀c∈\{0,1\}d∃fc∈im\(A\)fc↾Ed,v=c\.\\forall c\\in\\\{0,1\\\}^\{d\}\\ \\exists f\_\{c\}\\in\\operatorname\{im\}\(A\)\\quad\{f\_\{c\}\}\\\!\\upharpoonright\_\{E\_\{d,v\}\}=c\.
Condition 2There exists an infinite sequenceb1,b2,…b\_\{1\},b\_\{2\},\\dotscwithbi∈\{0,1\}db\_\{i\}\\in\\\{0,1\\\}^\{d\}such that for everyi≥1i\\geq 1

bi∉im\(A\)↾Ed,\(b1,…,bi−1\)\.b\_\{i\}\\notin\{\\operatorname\{im\}\(A\)\}\\\!\\upharpoonright\_\{E\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\)\}\}\.

We prove the dichotomy by assuming Condition 1 fails and recursively following a missingdd\-bit pattern down the tree\.

If the first condition does not hold, then

∀v∈Td∃c∈\{0,1\}d∀fc∈im\(A\)fc↾Ed,v≠c\.\\forall v\\in T\_\{d\}\\ \\exists c\\in\\\{0,1\\\}^\{d\}\\ \\forall f\_\{c\}\\in\\operatorname\{im\}\(A\)\\quad\{f\_\{c\}\}\\\!\\upharpoonright\_\{E\_\{d,v\}\}\\neq c\.In words, for every nodevvthere exists a functionccsuch that no hypothesis inim⁡\(A\)\\operatorname\{im\}\(A\)realizescconEd,vE\_\{d,v\}\. Therefore, we can start with the root \(labeled as∅\\varnothing\) and choose a missing vectorb1∉im\(A\)↾Ed,∅b\_\{1\}\\notin\{\\operatorname\{im\}\(A\)\}\\\!\\upharpoonright\_\{E\_\{d,\\varnothing\}\}\. After choosingb1,…,bi−1b\_\{1\},\\dotsc,b\_\{i\-1\}, we are at nodev=\(b1,…,bi−1\)v=\(b\_\{1\},\\dotsc,b\_\{i\-1\}\)and by the condition above we can choose a missing vectorbi∉im\(A\)↾Ed,vb\_\{i\}\\notin\{\\operatorname\{im\}\(A\)\}\\\!\\upharpoonright\_\{E\_\{d,v\}\}and move to the next child\(b1,…,bi\)\(b\_\{1\},\\dotsc,b\_\{i\}\)\. This finishes the proof\. ∎

In the remaining text, we show that \(1\) Condition 1 supplies the promised pseudocube in[Section1\.2](https://arxiv.org/html/2608.26516#S1.SS2)and henceDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\infty, and \(2\) Condition 2 contradicts the PAC guarantee ofAAand hence is impossible\.

#### Condition 1\.

First recall that a non\-empty finite classℋ⊆𝒴E\\mathcal\{H\}\\subseteq\\mathcal\{Y\}^\{E\}where\|E\|=d\|E\|=dis apseudocubeif, for everyf∈ℋf\\in\\mathcal\{H\}and everyx∈Ex\\in E, there existsg∈ℋg\\in\\mathcal\{H\}such thatg⁡\(x\)≠f⁡\(x\)g\(x\)\\neq f\(x\)andg⁡\(x′\)=f⁡\(x′\)g\(x^\{\\prime\}\)=f\(x^\{\\prime\}\)for everyx′∈E∖\{x\}x^\{\\prime\}\\in E\\setminus\\\{x\\\}\. In particular, a full binary cube is a pseudocube\. Also recall that a setE⊆𝒳E\\subseteq\\mathcal\{X\}isDS\-shatteredby a classℋ\\mathcal\{H\}ifℋ↾E\{\\mathcal\{H\}\}\\\!\\upharpoonright\_\{E\}contains a\|E\|\|E\|\-dimensional pseudocube, and theDS dimensionofℋ\\mathcal\{H\}is the supremum of the sizes of its finite DS\-shattered sets\.

Now, Condition 1 says that the restrictions\{fc↾Ed,v:c∈\{0,1\}d\}\\\{\{f\_\{c\}\}\\\!\\upharpoonright\_\{E\_\{d,v\}\}:c\\in\\\{0,1\\\}^\{d\}\\\}wherefc∈im⁡\(A\)f\_\{c\}\\in\\operatorname\{im\}\(A\)contain the full binary cube onEd,vE\_\{d,v\}, and hence add\-dimensional pseudocube\. Therefore,DS\(im⁡\(A\)\)≥d\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)\\geq d\. Sinceddis arbitrary, we conclude thatDS\(im⁡\(A\)\)=∞\\DS\\bigl\(\\operatorname\{im\}\(A\)\\bigr\)=\\infty\.

#### Condition 2\.

Letm=nA​\(14​d,18​d\)m=n\_\{A\}\\left\(\\frac\{1\}\{4d\},\\frac\{1\}\{8d\}\\right\)andℓ=2​m\\ell=2m\. Fix the pathb1,…,bℓb\_\{1\},\\dotsc,b\_\{\\ell\}that is shown to exist by assumption\. We will use the probabilistic method to show that, whenAAis givenmmexamples, there exists a hard instancehu∈ℋh\_\{u\}\\in\\mathcal\{H\}such thatAAcannot satisfy its PAC guarantee\. The crux is that we will drawmmpublic samples from a distribution supported uniformly on one public point at each of the2​m2mdepths in the tree, butmmexamples cannot cover all2​m2mdepths, so at every unseen depth, membership inim⁡\(A\)\\operatorname\{im\}\(A\)forces at least one error coordinate in the block, and the lower bound follows because a random example hits such a coordinate with probability at least1d\\frac\{1\}\{d\}\.

Choose independentlyu1,…,uℓ∼U⁡\(\[d\]\)u\_\{1\},\\dotsc,u\_\{\\ell\}\\sim U\(\[d\]\)and consider the random targethu:=hd,\(b1,…,bℓ\),uh\_\{u\}:=h\_\{d,\(b\_\{1\},\\dotsc,b\_\{\\ell\}\),u\}\. LetDuD\_\{u\}be the uniform distribution overhuh\_\{u\}’s public points

xi​\(u\):=xd,\(b1,…,bi−1\),uii∈\[ℓ\]\.x\_\{i\}\(u\):=x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),u\_\{i\}\}\\quad i\\in\[\\ell\]\.Recall that the label forxi​\(u\)x\_\{i\}\(u\)isbi​\(ui\)b\_\{i\}\(u\_\{i\}\), so samplingmmi\.i\.d\. examples \(which form the sampleSS\) fromDuD\_\{u\}can also be done by first samplingmmi\.i\.d\. depth indicesi1,…,im∼U⁡\(\[ℓ\]\)i\_\{1\},\\dotsc,i\_\{m\}\\sim U\(\[\\ell\]\)and then returning\(xit​\(u\),bit​\(uit\)\)\(x\_\{i\_\{t\}\}\(u\),b\_\{i\_\{t\}\}\(u\_\{i\_\{t\}\}\)\)\. We call a depthi−1i\-1unseenifi∉\{i1,…,im\}i\\notin\\\{i\_\{1\},\\dotsc,i\_\{m\}\\\}\.

Conditional on themmexamples for learning which form the setSSandAA’s internal randomness, the output functiong:=A⁡\(S\)∈im⁡\(A\)g:=A\(S\)\\in\\operatorname\{im\}\(A\)is determined\. No hypothesis inim⁡\(A\)\\operatorname\{im\}\(A\)agrees withbib\_\{i\}on blockEd,\(b1,…,bi−1\)E\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\)\}\. So onEd,\(b1,…,bi−1\)E\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\)\}we haveg≠big\\neq b\_\{i\}, and in particular there exists at least onej∈\[d\]j\\in\[d\]such that

g⁡\(xd,\(b1,…,bi−1\),j\)≠bi​\(j\)\.g\(x\_\{d,\(b\_\{1\},\\dotsc,b\_\{i\-1\}\),j\}\)\\neq b\_\{i\}\(j\)\.Observe crucially that, if depthi−1i\-1is unseen, thenuiu\_\{i\}is uniformly distributed over\[d\]\[d\]conditional on the sample andAA’s internal randomness\. Therefore, for an unseen depthi−1i\-1,ui=ju\_\{i\}=jwith probability at least1d\\frac\{1\}\{d\}, andggmakes an error\. Together with the fact that the depths are uniformly randomly selected according toDuD\_\{u\}, we conclude that an unseen depthi−1i\-1contributes to conditional expected loss at least1d​ℓ\\frac\{1\}\{d\\ell\}\.

Finally, because for each fixedi∈\[ℓ\]i\\in\[\\ell\], depthi−1i\-1is unseen with probability at least\(1−1ℓ\)m\\left\(1\-\\frac\{1\}\{\\ell\}\\right\)^\{m\}, we have

𝔼u,S,A\[LDu​\(A⁡\(S\),hu\)\]≥ℓ⋅1d​ℓ​\(1−1ℓ\)m=1d​\(1−12​m\)m≥12​d\\operatorname\*\{\\mathbb\{E\}\}\_\{u,S,A\}\[L\_\{D\_\{u\}\}\(A\(S\),h\_\{u\}\)\]\\geq\\ell\\cdot\\frac\{1\}\{d\\ell\}\\left\(1\-\\frac\{1\}\{\\ell\}\\right\)^\{m\}=\\frac\{1\}\{d\}\\left\(1\-\\frac\{1\}\{2m\}\\right\)^\{m\}\\geq\\frac\{1\}\{2d\}by summing over the contribution from allℓ\\elldepths\. Hence there exists auusuch that𝔼S,A\[LDu​\(A⁡\(S\),hu\)\]≥12​d\\operatorname\*\{\\mathbb\{E\}\}\_\{S,A\}\[L\_\{D\_\{u\}\}\(A\(S\),h\_\{u\}\)\]\\geq\\frac\{1\}\{2d\}\. However, if we look at the PAC learning guarantee ofAA, becausem=nA​\(14​d,18​d\)m=n\_\{A\}\\left\(\\frac\{1\}\{4d\},\\frac\{1\}\{8d\}\\right\)andhu∈ℋh\_\{u\}\\in\\mathcal\{H\}, the expected error is at most

18​d\+\(1−18​d\)⋅14​d≤38​d<12​d,\\frac\{1\}\{8d\}\+\\left\(1\-\\frac\{1\}\{8d\}\\right\)\\cdot\\frac\{1\}\{4d\}\\leq\\frac\{3\}\{8d\}<\\frac\{1\}\{2d\},which is a contradiction\. Thus Condition 2 is impossible\. ∎

###### Corollary 3\.4\.

Our proof of[Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1)provides a simpler construction of a partial concept class with VC dimension 1 that cannot be disambiguated to a total concept class of finite VC\-dimension: replace every private labelαd,b,u\\alpha\_\{d,b,u\}with⋆\\star\. The original result\([Alon et al\., 2022](https://arxiv.org/html/2608.26516#bib.bib22), Theorem 6\)uses graphs whose chromatic number is large compared to their biclique partition number\.

### 3\.2Proper learning requires empirical error

We now restrict our attention to properly learnable classes and ask whether interpolation is always possible\. That is, must every properly learnable class admit a successful proper learner whose output incurs no error on the training sample? Our answer is negative\.

The construction begins from the first Cantor class of[Daniely and Shalev\-Shwartz \(2014\)](https://arxiv.org/html/2608.26516#bib.bib3)\. Given a finite domainXX, this class contains one hypothesishAh\_\{A\}for each half\-setA⊆XA\\subseteq Xwith\|A\|=\|X\|/2\|A\|=\|X\|/2: the hypothesis predicts a private label identifyingAAon the points ofAA, and predicts a common label⋆\\stareverywhere else\. Thus the appearance of a private label reveals the target immediately, whereas an all\-⋆\\starsample reveals only that the sample has avoided the target’s private\-label region\. We use a version of this class that is augmented with a family of hypotheses that output the⋆\\starlabel on nearly the entire domain, but are deliberately inconsistent at rare marker points\.

###### Definition 3\.5\(Poisoned first\-Cantor class\)\.

For everyn≥1n\\geq 1, let

Xn=Cn⊔Pn,Pn=\{pn,1,…,pn,n\},\|Cn\|=2​n3\+n\.X\_\{n\}=C\_\{n\}\\sqcup P\_\{n\},\\qquad P\_\{n\}=\\\{p\_\{n,1\},\\ldots,p\_\{n,n\}\\\},\\qquad\|C\_\{n\}\|=2n^\{3\}\+n\.Thus

\|Xn\|=2​n3\+2​n,an:=n3\+n=\|Xn\|2\.\|X\_\{n\}\|=2n^\{3\}\+2n,\\qquad a\_\{n\}:=n^\{3\}\+n=\\frac\{\|X\_\{n\}\|\}\{2\}\.Set the final domain to the disjoint union of these blocks, i\.e\.,𝒳P:=⨆n≥1Xn\\mathcal\{X\}^\{\\mathrm\{P\}\}:=\\bigsqcup\_\{n\\geq 1\}X\_\{n\}\.

The label set contains two common labels⋆\\starand$\\$\. For everyA⊆XnA\\subseteq X\_\{n\}with\|A\|=an\|A\|=a\_\{n\}, introduce a private labelλn,A\\lambda\_\{n,A\}, and for everyi∈\[n\]i\\in\[n\], introduce a poison labelρn,i\\rho\_\{n,i\}\. All private and poison labels are distinct\.

For everyA⊆XnA\\subseteq X\_\{n\}with\|A\|=an\|A\|=a\_\{n\}, define the Cantor hypothesis

cn,A​\(x\)=\{⋆,x∈A,λn,A,x∈Xn∖A,$,x∉Xn\.c\_\{n,A\}\(x\)=\\begin\{cases\}\\star,&x\\in A,\\\\ \\lambda\_\{n,A\},&x\\in X\_\{n\}\\setminus A,\\\\ \\$,&x\\notin X\_\{n\}\.\\end\{cases\}For everyi∈\[n\]i\\in\[n\], define the poisoned fallback

sn,i​\(x\)=\{ρn,i,x=pn,i,⋆,x∈Xn∖\{pn,i\},$,x∉Xn\.s\_\{n,i\}\(x\)=\\begin\{cases\}\\rho\_\{n,i\},&x=p\_\{n,i\},\\\\ \\star,&x\\in X\_\{n\}\\setminus\\\{p\_\{n,i\}\\\},\\\\ \\$,&x\\notin X\_\{n\}\.\\end\{cases\}Finally, leth$h\_\{\\$\}denote the all\-$\\$hypothesis\. The*poisoned first\-Cantor class*is

ℋP:=\{h$\}∪\{cn,A:n≥1,A⊆Xn,\|A\|=an\}∪\{sn,i:n≥1,i∈\[n\]\}\.\\mathcal\{H\}\_\{\\mathrm\{P\}\}:=\\\{h\_\{\\$\}\\\}\\cup\\left\\\{c\_\{n,A\}:n\\geq 1,\\ A\\subseteq X\_\{n\},\\ \|A\|=a\_\{n\}\\right\\\}\\cup\\left\\\{s\_\{n,i\}:n\\geq 1,\\ i\\in\[n\]\\right\\\}\.

Note that the poisoned hypothesessn,is\_\{n,i\}are almost constantly⋆\\star, and are therefore natural fallbacks when an all\-⋆\\starsample leaves the target unresolved\. Their isolated errors at the marker pointspn,ip\_\{n,i\}, however, can make them unavailable to an interpolating learner\. This forms the central idea behind the following theorem\.

###### Theorem 3\.6\.

The classℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}is countable, closed, and has pointwise finite range\. It is furthermore properly PAC learnable, but cannot be learned by any interpolating proper learner\.

We establish the four claims in turn\.

#### Proper learnability\.

For a sample sizemm, put

Km:=⌊m1/5⌋,K\_\{m\}:=\\lfloor m^\{1/5\}\\rfloor,and letℋP≤Km\\mathcal\{H\}\_\{\\mathrm\{P\}\}^\{\\leq K\_\{m\}\}consist ofh$h\_\{\\$\}together with all hypotheses supported on blocksXnX\_\{n\}for whichn≤Kmn\\leq K\_\{m\}\.

The learner proceeds as follows\. If every observed label is$\\$, it outputsh$h\_\{\\$\}\. Otherwise, all non\-$\\$labels occur in a unique blockXnX\_\{n\}\. If a private Cantor labelλn,A\\lambda\_\{n,A\}appears, the learner outputscn,Ac\_\{n,A\}; if a poison labelρn,i\\rho\_\{n,i\}appears, it outputssn,is\_\{n,i\}\. The only remaining case is that the sample contains non\-$\\$points fromXnX\_\{n\}, all labeled⋆\\star\. Ifn≤Kmn\\leq K\_\{m\}, the learner outputs an arbitrary member ofℋP≤Km\\mathcal\{H\}\_\{\\mathrm\{P\}\}^\{\\leq K\_\{m\}\}consistent with the entire sample\. Ifn\>Kmn\>K\_\{m\}, it chooses a least\-observed marker

i^∈arg​mini∈\[n\]⁡\#​\{\(x,y\)∈S:x=pn,i\}\\hat\{i\}\\in\\argmin\_\{i\\in\[n\]\}\\\#\\\{\(x,y\)\\in S:x=p\_\{n,i\}\\\}and outputssn,i^s\_\{n,\\hat\{i\}\}\.

The small\-block rule is uniformly sound\. Indeed,

log⁡\|ℋP≤Km\|=O⁡\(∑n≤Km\|Xn\|\)=O⁡\(Km4\)=O⁡\(m4/5\)=o⁡\(m\)\.\\log\|\\mathcal\{H\}\_\{\\mathrm\{P\}\}^\{\\leq K\_\{m\}\}\|=O\\\!\\left\(\\sum\_\{n\\leq K\_\{m\}\}\|X\_\{n\}\|\\right\)=O\(K\_\{m\}^\{4\}\)=O\(m^\{4/5\}\)=o\(m\)\.Hence the standard finite\-class realizable bound implies that every consistent choice fromℋP≤Km\\mathcal\{H\}\_\{\\mathrm\{P\}\}^\{\\leq K\_\{m\}\}has vanishing population error, uniformly over the target and marginal distribution\.

Consider now a large\-block Cantor targetcn,Ac\_\{n,A\}, wheren\>Kmn\>K\_\{m\}, and write

Q:=Xn∖AQ:=X\_\{n\}\\setminus Afor its private\-label region\. If the sample meetsQQ, the labelλn,A\\lambda\_\{n,A\}reveals the target exactly\. If the sample missesQQ, then for everyε\>0\\varepsilon\>0,

ℙ\[D\(Q\)\>ε4andS∩Q=∅\]≤e−mε/4\.\\P\\\!\\left\[D\(Q\)\>\\frac\{\\varepsilon\}\{4\}\\ \\text\{and\}\\ S\\cap Q=\\varnothing\\right\]\\leq e^\{\-m\\varepsilon/4\}\.Likewise, if the sample misses the active blockXnX\_\{n\}entirely, the learner outputsh$h\_\{\\$\}; this can incur error greater thanε\\varepsilononly whenD⁡\(Xn\)\>εD\(X\_\{n\}\)\>\\varepsilon, in which case the probability of missingXnX\_\{n\}is at moste−m​εe^\{\-m\\varepsilon\}\.

In the remaining case the learner outputssn,i^s\_\{n,\\hat\{i\}\}, and its disagreement with the target is contained in\{x:sn,i^​\(x\)≠cn,A​\(x\)\}⊆Q∪\{pn,i^\}\\\{x:s\_\{n,\\hat\{i\}\}\(x\)\\neq c\_\{n,A\}\(x\)\\\}\\subseteq Q\\cup\\\{p\_\{n,\\hat\{i\}\}\\\}\. The least\-observed\-marker lemma, proved in[LemmaA\.1](https://arxiv.org/html/2608.26516#A1.Thmtheorem1), asserts that among a growing family of distinguished atoms, a marker of minimum empirical frequency has small true mass with high probability\. Sincen\>Km→∞n\>K\_\{m\}\\to\\infty, it follows thatD⁡\(pn,i^\)≤ε4D\(p\_\{n,\\hat\{i\}\}\)\\leq\\frac\{\\varepsilon\}\{4\}with probability tending to one, uniformly over the marker marginal\. Together with the preceding missed\-mass bounds, this proves that the output has population error at mostε\\varepsilonwith high probability\.

Fallback targets are handled similarly\. Fixsn,js\_\{n,j\}\. If the markerpn,jp\_\{n,j\}is sampled, the poison labelρn,j\\rho\_\{n,j\}reveals the target exactly\. If it is missed, then

ℙ\[D\(pn,j\)\>ε4andpn,j∉S\]≤e−mε/4\.\\P\\\!\\left\[D\(p\_\{n,j\}\)\>\\frac\{\\varepsilon\}\{4\}\\ \\text\{and\}\\ p\_\{n,j\}\\notin S\\right\]\\leq e^\{\-m\\varepsilon/4\}\.If the active block is observed but the poison label is not, the learner outputssn,i^s\_\{n,\\hat\{i\}\}, whose disagreement withsn,js\_\{n,j\}is contained in\{x:sn,i^​\(x\)≠sn,j​\(x\)\}⊆\{pn,i^,pn,j\}\\\{x:s\_\{n,\\hat\{i\}\}\(x\)\\neq s\_\{n,j\}\(x\)\\\}\\subseteq\\\{p\_\{n,\\hat\{i\}\},p\_\{n,j\}\\\}\. The first mass is controlled by the least\-observed\-marker lemma and the second by the preceding missed\-mass estimate\. The all\-$\\$target is learned exactly\. This proves distribution\-free proper learnability\.

#### Countability and pointwise finite range\.

Each blockXnX\_\{n\}is finite and supports only finitely many hypotheses, while there are countably many blocks\. HenceℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}is countable\. To see that it has pointwise finite range, fix anx∈Xnx\\in X\_\{n\}\. Each hypothesis supported on a different block takes the value$\\$atxx, and only finitely many hypotheses are supported onXnX\_\{n\}\. Thus\|ℋP​\(x\)\|<∞\|\\mathcal\{H\}\_\{\\mathrm\{P\}\}\(x\)\|<\\infty\.

#### Closedness\.

We use the finite\-projection characterization of closedness from[Lemma2\.5](https://arxiv.org/html/2608.26516#S2.Thmtheorem5)\. Letf:𝒳P→𝒴f:\\mathcal\{X\}^\{\\mathrm\{P\}\}\\to\\mathcal\{Y\}be finitely consistent withℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}\. Iff≡$f\\equiv\\$, thenf=h$f=h\_\{\\$\}\. Otherwise, choosex∈Xnx\\in X\_\{n\}withf⁡\(x\)≠$f\(x\)\\neq\\$\. We claim thatffis identically$\\$outsideXnX\_\{n\}\. Indeed, ify∈Xn′y\\in X\_\{n^\{\\prime\}\},n′≠nn^\{\\prime\}\\neq n, also satisfiedf⁡\(y\)≠$f\(y\)\\neq\\$, then no hypothesis inℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}could realize the two\-point restriction offfto\{x,y\}\\\{x,y\\\}, since every nontrivial hypothesis is supported on a single block\. This would contradict finite consistency\. The blockXnX\_\{n\}is finite, so finite consistency applied to all ofXnX\_\{n\}yields someh∈ℋPh\\in\\mathcal\{H\}\_\{\\mathrm\{P\}\}satisfyingh↾Xn=f↾Xn\{h\}\\\!\\upharpoonright\_\{X\_\{n\}\}=\{f\}\\\!\\upharpoonright\_\{X\_\{n\}\}\. Sincef⁡\(x\)≠$f\(x\)\\neq\\$, this hypothesis is supported onXnX\_\{n\}\. Bothffandhhequal$\\$outsideXnX\_\{n\}, and hencef=h∈ℋPf=h\\in\\mathcal\{H\}\_\{\\mathrm\{P\}\}\.

#### Failure of every interpolating proper learner\.

LetBmB\_\{m\}be an arbitrary deterministic interpolating proper learner\. Fix a large sample sizemm, and choose

n:=⌊m20​log⁡m⌋,k:=n3\.n:=\\left\\lfloor\\frac\{m\}\{20\\log m\}\\right\\rfloor,\\qquad k:=n^\{3\}\.ChooseT⊆CnT\\subseteq C\_\{n\}uniformly among allkk\-subsets, and putA:=Pn∪TA:=P\_\{n\}\\cup T\. Since\|A\|=n\+k=an\|A\|=n\+k=a\_\{n\}, the Cantor hypothesiscn,Ac\_\{n,A\}belongs toℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}\.

Now letDAD\_\{A\}place mass1/41/4uniformly onPnP\_\{n\}and mass3/43/4uniformly onTT\. Takecn,Ac\_\{n,A\}as the true labeling function\. Each point in the support ofDAD\_\{A\}lies inAA, and is therefore labeled⋆\\star\. Furthermore, each marker has mass1/\(4​n\)1/\(4n\), so a union bound gives

ℙ\[some marker in​Pn​is missed\]≤n​\(1−14​n\)m≤n​exp⁡\(−m4​n\)=o⁡\(1\)\.\\P\[\\text\{some marker in \}P\_\{n\}\\text\{ is missed\}\]\\leq n\\left\(1\-\\frac\{1\}\{4n\}\\right\)^\{m\}\\leq n\\exp\\\!\\left\(\-\\frac\{m\}\{4n\}\\right\)=o\(1\)\.On the complementary event, every poisoned fallbacksn,is\_\{n,i\}is inconsistent, since the sample containspn,ip\_\{n,i\}with label⋆\\star, whereassn,i​\(pn,i\)=ρn,is\_\{n,i\}\(p\_\{n,i\}\)=\\rho\_\{n,i\}\. The hypothesish$h\_\{\\$\}, all hypotheses supported on other blocks, and all private\-label hypotheses whose⋆\\star\-regions do not contain the sample are likewise inconsistent\. Thus the learner must output a Cantor hypothesiscn,Bc\_\{n,B\}\.

LetR⊆TR\\subseteq Tbe the set of distinct sampled core points\. Consistency forcesPn∪R⊆BP\_\{n\}\\cup R\\subseteq B\. Since\|B\|=n\+k\|B\|=n\+kandPn⊆BP\_\{n\}\\subseteq B, the setBC:=B∩CnB\_\{C\}:=B\\cap C\_\{n\}has sizekkand containsRR\. Now condition on the complete observed sample and on the learner’s internal choice ofBCB\_\{C\}\. Given this information, the posterior distribution ofTTis uniform over allkk\-subsets ofCnC\_\{n\}containingRR\. Moreover,

\|R\|≤m=o⁡\(k\),\|Cn\|=2​k\+n=\(2\+o⁡\(1\)\)​k\.\|R\|\\leq m=o\(k\),\\qquad\|C\_\{n\}\|=2k\+n=\(2\+o\(1\)\)k\.ThusT∖RT\\setminus Ris a uniformly random\(k−\|R\|\)\(k\-\|R\|\)\-subset ofCn∖RC\_\{n\}\\setminus R, whileBC∖RB\_\{C\}\\setminus Ris a fixed set of the same cardinality\. A standard hypergeometric concentration bound therefore yields

ℙ\[\|T∖BC\|≥k5\|S,BC\]=1−o\(1\)\.\\P\\\!\\left\[\|T\\setminus B\_\{C\}\|\\geq\\frac\{k\}\{5\}\\,\\middle\|\\,S,B\_\{C\}\\right\]=1\-o\(1\)\.On this event,

LDA​\(cn,B,cn,A\)≥34​\|T∖BC\|\|T\|≥320\.L\_\{D\_\{A\}\}\(c\_\{n,B\},c\_\{n,A\}\)\\geq\\frac\{3\}\{4\}\\frac\{\|T\\setminus B\_\{C\}\|\}\{\|T\|\}\\geq\\frac\{3\}\{20\}\.
Averaging over the random choice ofTT, we conclude that there is a fixedkk\-subsetT⊆CnT\\subseteq C\_\{n\}for whichBmB\_\{m\}has population error at least3/203/20with probability bounded away from zero\. Since the construction applies for arbitrarily largemm, the learnerBBis not PAC\.

The same argument rules out randomized interpolating proper learners: one simply includes the learner’s internal randomness in the averaging and then fixes a targetTTwitnessing the resulting constant failure probability\. ∎

We now observe an immediate consequence of[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6): hard SRM learners, which select interpolating hypotheses using an a\-priori inductive bias, are in general insufficiently expressive for properly learnable problems\.

###### Corollary 3\.7\.

There exists a properly learnable hypothesis class, namelyℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}, that cannot be learned by hard SRM\.

Every hard\-SRM learner is an interpolating proper learner, whereasℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}is properly learnable but admits no successful interpolating proper learner by[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6)\. ∎

Let us briefly make two observations concerning[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6)\. First, note that the presence of only a single poisoned fallback would not suffice\. In order to force every interpolating learner to reject the fallback with high probability, its poisoned point would need appreciable population mass\. This would immediately imply, however, that the fallback is no longer statistically safe at test time\. In contrast, a collection ofω⁡\(1\)\\omega\(1\)many poisoned fallbacks ensures that the entire collection of markers can carry constant mass, while nevertheless containing some markers that are successful at test time\. \(In particular, the ones whose poisoned points are least likely\.\)

Second, we note that[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6)separates proper learning from interpolation, but does not by itself rule out weighted SRM\. In particular, weighted SRM can express improper learners by selecting a preferred hypothesis with positive training error\. We will, however, rule out weighted SRM in[Section4](https://arxiv.org/html/2608.26516#S4)using a separate construction\.

### 3\.3The exact scale of empirical noninterpolation

We next establish a sharp characterization concerning how many training errors can be required in proper learning: a sublinear rateo⁡\(m\)o\(m\)can be attained for any properly learnable problem, and conversely every sublinear rateam=o⁡\(m\)a\_\{m\}=o\(m\)can be made necessary for some properly learnable problem\.

###### Theorem 3\.8\.

LetAAbe a proper PAC learner for a classℋ\\mathcal\{H\}with a sample complexitynA​\(ε,δ\)n\_\{A\}\(\\varepsilon,\\delta\)\. Then there exists a proper PAC learnerA~\\widetilde\{A\}forℋ\\mathcal\{H\}and a sequenceγm→0\\gamma\_\{m\}\\to 0such that for every realizable sampleSSof sizemm,

L^S​\(A~m​\(S\)\)≤γm\.\\widehat\{L\}\_\{S\}\(\\widetilde\{A\}\_\{m\}\(S\)\)\\leq\\gamma\_\{m\}\.Moreover, one may takenA~​\(ε,δ\)≤R⁡\(ε,δ\)​nA​\(R​\(ε,δ\)−2,R​\(ε,δ\)−1\)n\_\{\\widetilde\{A\}\}\(\\varepsilon,\\delta\)\\leq R\(\\varepsilon,\\delta\)\\,n\_\{A\}\\\!\\left\(R\(\\varepsilon,\\delta\)^\{\-2\},R\(\\varepsilon,\\delta\)^\{\-1\}\\right\), whereR\(ε,δ\)=⌈max\{2,ε−1/2,2/δ\}⌉R\(\\varepsilon,\\delta\)=\\left\\lceil\\max\\left\\\{2,\\varepsilon^\{\-1/2\},2/\\delta\\right\\\}\\right\\rceil\.

For eachmm, letrmr\_\{m\}be the largest integerr≥2r\\geq 2satisfying

r​nA​\(r−2,r−1\)≤m,r\\,n\_\{A\}\(r^\{\-2\},r^\{\-1\}\)\\leq m,if such an integer exists\. Putkm=nA​\(rm−2,rm−1\)k\_\{m\}=n\_\{A\}\(r\_\{m\}^\{\-2\},r\_\{m\}^\{\-1\}\)\. On anmm\-sampleSS, trainAAon the firstkmk\_\{m\}examples, obtaininghh\. If the empirical error ofhhon the remainingm−kmm\-k\_\{m\}examples is at mostrm−1r\_\{m\}^\{\-1\}, outputhh; otherwise output an arbitrary hypothesis inℋ\\mathcal\{H\}consistent with the full sample\. On the finitely manymmfor whichrmr\_\{m\}is undefined, output a full\-sample consistent hypothesis\.

The learner is proper\. On every realizable sample, the fallback has empirical error zero\. Ifhhis accepted, it makes at mostkmk\_\{m\}mistakes on the training prefix and at most\(m−km\)/rm\(m\-k\_\{m\}\)/r\_\{m\}mistakes on the validation suffix\. Sincekm/m≤1/rmk\_\{m\}/m\\leq 1/r\_\{m\},

L^S​\(A~m​\(S\)\)≤2rm\.\\widehat\{L\}\_\{S\}\(\\widetilde\{A\}\_\{m\}\(S\)\)\\leq\\frac\{2\}\{r\_\{m\}\}\.For every fixedrr, the defining inequality eventually holds, sorm→∞r\_\{m\}\\to\\inftyand we may takeγm=2/rm\\gamma\_\{m\}=2/r\_\{m\}\.

For the PAC guarantee, fix a target and marginal\. With probability at least1−rm−11\-r\_\{m\}^\{\-1\}, the prefix learner has true error at mostrm−2r\_\{m\}^\{\-2\}\. Conditional on such an output, the validation suffix is independent and its expected empirical error is at mostrm−2r\_\{m\}^\{\-2\}; Markov’s inequality therefore bounds the probability of rejection byrm−1r\_\{m\}^\{\-1\}\. Outside these two events,A~m\\widetilde\{A\}\_\{m\}accepts a hypothesis of true error at mostrm−2r\_\{m\}^\{\-2\}\. Thus

ℙ\[LD\(A~m\(S\),h⋆\)\>rm−2\]≤2rm\.\\P\\left\[L\_\{D\}\(\\widetilde\{A\}\_\{m\}\(S\),h^\{\\star\}\)\>r\_\{m\}^\{\-2\}\\right\]\\leq\\frac\{2\}\{r\_\{m\}\}\.Ifm≥R​nA​\(R−2,R−1\)m\\geq Rn\_\{A\}\(R^\{\-2\},R^\{\-1\}\), thenrm≥Rr\_\{m\}\\geq R, yielding the displayed sample\-complexity bound\. ∎

###### Theorem 3\.9\.

Let\(am\)m≥1\(a\_\{m\}\)\_\{m\\geq 1\}be any nonnegative sequence witham=o⁡\(m\)a\_\{m\}=o\(m\)\. There exists a countable, closed, pointwise finite\-range, properly learnable classℋa\\mathcal\{H\}\_\{a\}and a universal constantc\>0c\>0such that every proper PAC learnerAAforℋa\\mathcal\{H\}\_\{a\}satisfies the following: for all sufficiently largemm, there is a realizable pair\(Dm,hm⋆\)\(D\_\{m\},h\_\{m\}^\{\\star\}\)for which

ℙS∼Dmm\[mL^S\(Am\(S\)\)≥cam\]≥c\.\\P\_\{S\\sim D\_\{m\}^\{m\}\}\\left\[m\\widehat\{L\}\_\{S\}\(A\_\{m\}\(S\)\)\\geq ca\_\{m\}\\right\]\\geq c\.

We defer the proof of[Theorem3\.9](https://arxiv.org/html/2608.26516#S3.Thmtheorem9)to[SectionB\.1](https://arxiv.org/html/2608.26516#A2.SS1)\. Roughly speaking, the construction simply tunes the poisoned first Cantor classℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}\(i\.e\., either increasing or decreasing the number of marker points\) in order to ensure that every marker point receives the prescribed number of training points, while still having vanishing population mass\.

## 4Limits of Global and Local Regularization

The preceding section shows that proper multiclass learning may require a sample\-dependent departure from interpolation\. We now ask whether this flexibility can nevertheless be encoded by regularization\. We consider two templates: weighted SRM, which provides global scalar preferences over hypotheses, and local regularization, which provides pointwise preferences and can express improper learning\.

### 4\.1A closed incidence class beyond weighted SRM

Our global lower bound is built from finite projective planes\. Recall that a projective plane of orderqqhasN=q2\+q\+1N=q^\{2\}\+q\+1points and the same number of lines\. Every point lies ond=q\+1d=q\+1lines, every line containsddpoints, and every two distinct points lie on a unique common line\. IfMMdenotes itsN×NN\\times Nincidence matrix, thenM​M⊤=q​I\+JMM^\{\\top\}=qI\+J\. Consequently, the largest singular value ofMMisdd, while every nontrivial singular value isq\\sqrt\{q\}\.

###### Definition 4\.1\(Projective\-plane incidence class\)\.

For every integerm≥2m\\geq 2, let

qm:=2m\+10,Nm:=qm2\+qm\+1,dm:=qm\+1\.q\_\{m\}:=2^\{m\+10\},\\qquad N\_\{m\}:=q\_\{m\}^\{2\}\+q\_\{m\}\+1,\\qquad d\_\{m\}:=q\_\{m\}\+1\.Sinceqmq\_\{m\}is a prime power, a projective plane of orderqmq\_\{m\}exists\.

Take three disjoint vertex setsV0\(m\),V1\(m\),V2\(m\)V\_\{0\}^\{\(m\)\},V\_\{1\}^\{\(m\)\},V\_\{2\}^\{\(m\)\}, each of cardinalityNmN\_\{m\}\. For everyr∈ℤ/3​ℤr\\in\\mathbb\{Z\}/3\\mathbb\{Z\}, place an oriented copy of the point\-line incidence graph fromVr\(m\)V\_\{r\}^\{\(m\)\}toVr\+1\(m\)V\_\{r\+1\}^\{\(m\)\}\. Forv∈Vr\(m\)v\\in V\_\{r\}^\{\(m\)\}, writeΓ\+​\(v\)⊆Vr\+1\(m\)\\Gamma^\{\+\}\(v\)\\subseteq V\_\{r\+1\}^\{\(m\)\}for its outgoing neighborhood and put𝖲⁡\(v\):=\{v\}∪Γ\+​\(v\)\\mathsf\{S\}\(v\):=\\\{v\\\}\\cup\\Gamma^\{\+\}\(v\)\. The projective\-plane axioms imply

\|𝖲⁡\(v\)∩𝖲⁡\(w\)\|≤1for every pair of distinct vertices​v,w\.\|\\mathsf\{S\}\(v\)\\cap\\mathsf\{S\}\(w\)\|\\leq 1\\qquad\\text\{for every pair of distinct vertices \}v,w\.\(4\)Indeed, two vertices in the same part have exactly one common outgoing neighbor, whereas the cyclic supports of vertices in different parts permit at most one intersection\.

For every vertexvv, create the Boolean\-cube blockZv:=\{0,1\}Γ\+​\(v\)Z\_\{v\}:=\\\{0,1\\\}^\{\\Gamma^\{\+\}\(v\)\}\. Themmth incidence component and the full domain are

𝒳mI:=⨆v∈V0\(m\)⊔V1\(m\)⊔V2\(m\)Zv,𝒳I:=⨆m≥2𝒳mI\.\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}:=\\bigsqcup\_\{v\\in V\_\{0\}^\{\(m\)\}\\sqcup V\_\{1\}^\{\(m\)\}\\sqcup V\_\{2\}^\{\(m\)\}\}Z\_\{v\},\\qquad\\mathcal\{X\}^\{\\mathrm\{I\}\}:=\\bigsqcup\_\{m\\geq 2\}\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}\.Introduce a private labelτu\\tau\_\{u\}for every vertexuu, with all such labels distinct across components\. For a vertexuuin themmth component, definegug\_\{u\}on that component by

gu​\(v,z\)=\{⋆,u=v,⋆,u∈Γ\+​\(v\)​and​zu=0,τu,otherwise,\(v,z\)∈𝒳mI,g\_\{u\}\(v,z\)=\\begin\{cases\}\\star,&u=v,\\\\ \\star,&u\\in\\Gamma^\{\+\}\(v\)\\text\{ and \}z\_\{u\}=0,\\\\ \\tau\_\{u\},&\\text\{otherwise\},\\end\{cases\}\\qquad\(v,z\)\\in\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\},\(5\)and extendgug\_\{u\}by$\\$outside its component\. Leth$h\_\{\\$\}be the all\-$\\$hypothesis, and set

ℋI:=\{h$\}∪\{gu:u​is a vertex in some incidence component\}\.\\mathcal\{H\}\_\{\\mathrm\{I\}\}:=\\\{h\_\{\\$\}\\\}\\cup\\\{g\_\{u\}:u\\text\{ is a vertex in some incidence component\}\\\}\.We callℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}the*projective\-plane incidence class*\.

The intuition behind the incidence class of[Definition4\.1](https://arxiv.org/html/2608.26516#S4.Thmtheorem1)is easiest to see on a single blockZvZ\_\{v\}\. Its ownergvg\_\{v\}predicts⋆\\starthroughout the block, whereas the outgoing neighborsu∈Γ\+​\(v\)u\\in\\Gamma^\{\+\}\(v\)behave in a Cantor\-like manner, i\.e\., agreeing with the owner on the half ofZvZ\_\{v\}wherezu=0z\_\{u\}=0and revealing the private labelτu\\tau\_\{u\}on the half wherezu=1z\_\{u\}=1\. Every hypothesis whose index lies outside𝖲⁡\(v\)\\mathsf\{S\}\(v\)simply predicts its private label throughoutZvZ\_\{v\}\.

###### Theorem 4\.2\.

The incidence classℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}is countable, closed, and has pointwise finite range\. It is properly PAC learnable, but no weighted\-SRM objectiveh↦L^S​\(h\)\+λ⁡\(S\)​ψ​\(h\)h\\mapsto\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\(S\)\\,\\psi\(h\)learns it\.

We first establish proper learnability and the topological properties, and then prove the lower bound\.

#### Proper learnability within one incidence component\.

We first describe a learner when the target and marginal are supported on one finite component\. If the sample contains a private labelτu\\tau\_\{u\}, simply outputgug\_\{u\}\. Otherwise, every observed label is⋆\\star; letI⁡\(S\)I\(S\)denote the collection of blocksZvZ\_\{v\}appearing in the sample\. If\|I⁡\(S\)\|≥2\|I\(S\)\|\\geq 2, realizability implies that the target indexuubelongs to𝖲⁡\(v\)\\mathsf\{S\}\(v\)for everyv∈I⁡\(S\)v\\in I\(S\)\. By \([4](https://arxiv.org/html/2608.26516#S4.E4)\), the intersection⋂v∈I⁡\(S\)𝖲⁡\(v\)\\bigcap\_\{v\\in I\(S\)\}\\mathsf\{S\}\(v\)contains at most one vertex\. Since it contains the target, it identifiesuuexactly, and the learner outputsgug\_\{u\}\. IfI⁡\(S\)=\{v\}I\(S\)=\\\{v\\\}, the learner outputs the ownergvg\_\{v\}\.

Fix a targetgug\_\{u\}and a marginalDDsupported on the component\. For everyvvsatisfyingu∈𝖲⁡\(v\)u\\in\\mathsf\{S\}\(v\), define

Au,v:=\{x∈Zv:gu\(x\)=⋆\},eu,v:=LD\(gv,gu\)\.A\_\{u,v\}:=\\\{x\\in Z\_\{v\}:g\_\{u\}\(x\)=\\star\\\},\\qquad e\_\{u,v\}:=L\_\{D\}\(g\_\{v\},g\_\{u\}\)\.The learner can output an incorrect ownergvg\_\{v\}only if every sampled point lies inAu,vA\_\{u,v\}\. On this set the target and owner agree, soD⁡\(Au,v\)≤1−eu,vD\(A\_\{u,v\}\)\\leq 1\-e\_\{u,v\}\. Moreover, the setsAu,vA\_\{u,v\}are disjoint because they lie in distinct blocks\. Hence, for a sample of sizek≥1k\\geq 1and everyε∈\(0,1\)\\varepsilon\\in\(0,1\),

ℙ\[LD\(A\(S\),gu\)\>ε\]\\displaystyle\\P\\\!\\left\[L\_\{D\}\(A\(S\),g\_\{u\}\)\>\\varepsilon\\right\]≤∑v:eu,v\>εD\(Au,v\)k\\displaystyle\\leq\\sum\_\{v:e\_\{u,v\}\>\\varepsilon\}D\(A\_\{u,v\}\)^\{k\}≤\(1−ε\)k−1​∑vD⁡\(Au,v\)\\displaystyle\\leq\(1\-\\varepsilon\)^\{k\-1\}\\sum\_\{v\}D\(A\_\{u,v\}\)≤\(1−ε\)k−1\.\\displaystyle\\leq\(1\-\\varepsilon\)^\{k\-1\}\.\(6\)Crucially, this estimate is independent of the size of the component\.

#### Proper learnability of the countable union\.

We now define the learner on the full class\. If every observed label is$\\$, outputh$h\_\{\\$\}\. Otherwise the non\-$\\$examples lie in one incidence component; discard the$\\$examples and run the component learner above on the active subsample\.

Fix a targetgug\_\{u\}, letDDbe an arbitrary marginal on𝒳I\\mathcal\{X\}^\{\\mathrm\{I\}\}, and writeppfor the mass of the target’s active component\. Outside that component, both the target and every hypothesis from the component predict$\\$\. Ifp≤εp\\leq\\varepsilon, every output of the preceding learner has population error at mostε\\varepsilon\.

Suppose therefore thatp\>εp\>\\varepsilon, and letK∼Bin⁡\(r,p\)K\\sim\\operatorname\{Bin\}\(r,p\)be the number of active observations in a sample of sizerr\. IfK=0K=0, the learner outputsh$h\_\{\\$\}, andℙ\[K=0\]=\(1−p\)r≤e−r​ε\\P\[K=0\]=\(1\-p\)^\{r\}\\leq e^\{\-r\\varepsilon\}\. Conditional onK=k≥1K=k\\geq 1, the active examples are iid from the conditional marginal on the component\. Apply \([6](https://arxiv.org/html/2608.26516#S4.Ex53)\) with thresholdα:=ε/\(2​p\)≤1/2\\alpha:=\\varepsilon/\(2p\)\\leq 1/2\. If the global population error exceedsε\\varepsilon, then the conditional component error exceedsε/p\\varepsilon/p, and hence also exceedsα\\alpha\. Consequently,

ℙ\[LD\(A\(S\),gu\)\>ε\]\\displaystyle\\P\\\!\\left\[L\_\{D\}\(A\(S\),g\_\{u\}\)\>\\varepsilon\\right\]≤\(1−p\)r\+∑k=1r\(rk\)​pk​\(1−p\)r−k​\(1−α\)k−1\\displaystyle\\leq\(1\-p\)^\{r\}\+\\sum\_\{k=1\}^\{r\}\\binom\{r\}\{k\}p^\{k\}\(1\-p\)^\{r\-k\}\(1\-\\alpha\)^\{k\-1\}≤e−r​ε\+\(1−p\+p⁡\(1−α\)\)r1−α\\displaystyle\\leq e^\{\-r\\varepsilon\}\+\\frac\{\(1\-p\+p\(1\-\\alpha\)\)^\{r\}\}\{1\-\\alpha\}≤e−r​ε\+2​\(1−ε/2\)r\\displaystyle\\leq e^\{\-r\\varepsilon\}\+2\(1\-\\varepsilon/2\)^\{r\}≤3e−rε/2\.\\displaystyle\\leq 3e^\{\-r\\varepsilon/2\}\.The all\-$\\$target is learned exactly\. ThusℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}is properly PAC learnable, with a component\-size\-independent sample complexity\.

#### Countability, pointwise finite range, and closedness\.

Every incidence component is finite, and there are countably many components; henceℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}is countable\. At a fixed coordinatexx, only the finitely many hypotheses from its own component can output a value other than$\\$, soℋI​\(x\)\\mathcal\{H\}\_\{\\mathrm\{I\}\}\(x\)is finite\. For closedness, invoke the finite\-projection characterization from[Lemma2\.5](https://arxiv.org/html/2608.26516#S2.Thmtheorem5)\. Letf:𝒳I→𝒴f:\\mathcal\{X\}^\{\\mathrm\{I\}\}\\to\\mathcal\{Y\}be finitely consistent withℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}\. Iff≡$f\\equiv\\$, thenf=h$f=h\_\{\\$\}\. Otherwise choose a pointxxin some component𝒳mI\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}for whichf⁡\(x\)≠$f\(x\)\\neq\\$\. Two\-point restrictions forceffto equal$\\$outside𝒳mI\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}, since no nontrivial hypothesis is active on two components\. The component is finite, so finite consistency applied to the entire component produces a hypothesisgug\_\{u\}agreeing withffthere\. Both functions equal$\\$elsewhere, and hencef=guf=g\_\{u\}\. ThereforeℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}is closed\.

#### An incidence inversion for every scalar regularizer\.

Fix a sample scalemmand an arbitrary regularizerψ\\psi\. For eachr∈ℤ/3​ℤr\\in\\mathbb\{Z\}/3\\mathbb\{Z\}, letara\_\{r\}be a median of the values\{ψ⁡\(gv\):v∈Vr\(m\)\}\\\{\\psi\(g\_\{v\}\):v\\in V\_\{r\}^\{\(m\)\}\\\}\. For some cyclic indexrr, one hasar\+1≤ara\_\{r\+1\}\\leq a\_\{r\}\. LetUUbe the vertices inVr\(m\)V\_\{r\}^\{\(m\)\}whose regularizer values are at leastara\_\{r\}, and letW0W\_\{0\}be the vertices inVr\+1\(m\)V\_\{r\+1\}^\{\(m\)\}whose regularizer values are at mostar\+1a\_\{r\+1\}\. Both sets have cardinality at leastNm/2N\_\{m\}/2\. The projective\-plane mixing estimate givese⁡\(U,W0\)≥\(dm/Nm\)​\|U\|​\|W0\|−qm​\|U\|​\|W0\|≥dm​Nm/8e\(U,W\_\{0\}\)\\geq\(d\_\{m\}/N\_\{m\}\)\|U\|\|W\_\{0\}\|\-\\sqrt\{q\_\{m\}\|U\|\|W\_\{0\}\|\}\\geq d\_\{m\}N\_\{m\}/8, where the final inequality usesqm≥16q\_\{m\}\\geq 16\. Averaging overUUyields a vertexv∈Uv\\in Uwith at leastdm/8d\_\{m\}/8outgoing neighbors inW0W\_\{0\}\. ForW:=Γ\+​\(v\)∩W0W:=\\Gamma^\{\+\}\(v\)\\cap W\_\{0\}, we therefore have

\|W\|≥dm8andψ⁡\(gw\)≤ar\+1≤ar≤ψ⁡\(gv\)∀w∈W\.\|W\|\\geq\\frac\{d\_\{m\}\}\{8\}\\qquad\\text\{and\}\\qquad\\psi\(g\_\{w\}\)\\leq a\_\{r\+1\}\\leq a\_\{r\}\\leq\\psi\(g\_\{v\}\)\\quad\\forall w\\in W\.\(7\)

#### Failure of weighted SRM\.

Fix an arbitrary regularizerψ\\psiand coefficientλ\\lambda\. By definition, a weighted\-SRM objective must attain its minimum on every sample in order to induce a learner; an objective with an empty argmin is therefore already disqualified\. The lower bound below does not exploit this technicality\. On each hard sample, the version space is finite and contains the ownergvg\_\{v\}together with its surviving coordinate neighbors\. If an attained global minimizer lies outside the version space, it is already population\-bad; if a minimizer lies among the interpolators, we force a bad interpolator into the argmin set\.

For everym≥2m\\geq 2, apply \([7](https://arxiv.org/html/2608.26516#S4.E7)\) inside themmth component to obtainvvandW⊆Γ\+​\(v\)W\\subseteq\\Gamma^\{\+\}\(v\)such that\|W\|≥dm/8\>2m\+7\|W\|\\geq d\_\{m\}/8\>2^\{m\+7\}andψ⁡\(gw\)≤ψ⁡\(gv\)\\psi\(g\_\{w\}\)\\leq\\psi\(g\_\{v\}\)for everyw∈Ww\\in W\. Take targetgvg\_\{v\}, and letDDbe uniform on the full cubeZvZ\_\{v\}\. The ownergvg\_\{v\}is the unique population\-perfect hypothesis\. Every neighborgwg\_\{w\},w∈Γ\+​\(v\)w\\in\\Gamma^\{\+\}\(v\), has population error1/21/2, while every remaining hypothesis has population error one\.

For a fixedw∈Ww\\in W, the hypothesisgwg\_\{w\}interpolates anmm\-sample exactly when thewwth coordinate is zero on every sampled vector, an event of probability2−m2^\{\-m\}\. These events are independent over distinctww, and therefore

ℙ\[∃w∈W:L^S\(gw\)=0\]\\displaystyle\\P\\\!\\left\[\\exists w\\in W:\\widehat\{L\}\_\{S\}\(g\_\{w\}\)=0\\right\]=1−\(1−2−m\)\|W\|\\displaystyle=1\-\(1\-2^\{\-m\}\)^\{\|W\|\}≥1−exp⁡\(−\|W\|​2−m\)\\displaystyle\\geq 1\-\\exp\(\-\|W\|2^\{\-m\}\)≥1−e−128\.\\displaystyle\\geq 1\-e^\{\-128\}\.\(8\)
On the event in \([8](https://arxiv.org/html/2608.26516#S4.Ex59)\), choose an interpolatinggwg\_\{w\}withw∈Ww\\in W\. ThenL^S​\(gw\)=L^S​\(gv\)=0\\widehat\{L\}\_\{S\}\(g\_\{w\}\)=\\widehat\{L\}\_\{S\}\(g\_\{v\}\)=0andψ⁡\(gw\)≤ψ⁡\(gv\)\\psi\(g\_\{w\}\)\\leq\\psi\(g\_\{v\}\), soL^S​\(gw\)\+λ⁡\(S\)​ψ​\(gw\)≤L^S​\(gv\)\+λ⁡\(S\)​ψ​\(gv\)\\widehat\{L\}\_\{S\}\(g\_\{w\}\)\+\\lambda\(S\)\\psi\(g\_\{w\}\)\\leq\\widehat\{L\}\_\{S\}\(g\_\{v\}\)\+\\lambda\(S\)\\psi\(g\_\{v\}\)\. Ifgvg\_\{v\}is not an objective minimizer, every minimizer is population\-bad becausegvg\_\{v\}is the unique population\-perfect hypothesis\. Ifgvg\_\{v\}is a minimizer, the preceding inequality forcesgwg\_\{w\}to be a minimizer as well\. Hence the argmin set contains a nonowner of population error at least1/21/2on the event \([8](https://arxiv.org/html/2608.26516#S4.Ex59)\)\. Fixing an enumeration ofℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}, choose the first nonowner minimizer on such samples whenever one exists, and the first minimizer otherwise; this defines an induced learner whose population error is at least1/21/2with probability at least1−e−1281\-e^\{\-128\}for arbitrarily largemm, so the weighted\-SRM objective does not learnℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}\. ∎

Combining the incidence class with the poisoned first\-Cantor construction yields one class exhibiting both global obstructions\.

###### Theorem 4\.4\.

There exists a countable hypothesis classℋ\\mathcal\{H\}satisfying all of the following:

1. \(i\)ℋ\\mathcal\{H\}is properly PAC learnable;
2. \(ii\)ℋ\\mathcal\{H\}is closed and has pointwise finite range;
3. \(iii\)no interpolating proper learner PAC learnsℋ\\mathcal\{H\};
4. \(iv\)no weighted\-SRM objective learnsℋ\\mathcal\{H\}\.

Take the disjoint union ofℋP\\mathcal\{H\}\_\{\\mathrm\{P\}\}andℋI\\mathcal\{H\}\_\{\\mathrm\{I\}\}, identify their all\-$\\$hypotheses, and extend every remaining hypothesis by$\\$on the opposite domain\. Proper learnability follows by running the two component learners and validating between their outputs on a fresh subsample, while closedness and pointwise finite range are preserved by the finite disjoint union\. Restricting the marginal to the poisoned component recovers[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6), whereas restricting it to the incidence component recovers[Theorem4\.2](https://arxiv.org/html/2608.26516#S4.Thmtheorem2); in either case, hypotheses from the opposite component predict$\\$throughout the hard distribution and therefore cannot rescue the constrained learner\. ∎

### 4\.2A PAC counterexample to hard local regularization

We now resolve[Open Problem1](https://arxiv.org/html/2608.26516#Thmproblem1)in the negative\. Recall that the local regularizers of[Asilis et al\. \(2024b\)](https://arxiv.org/html/2608.26516#bib.bib4)are first learned from the unlabeled sample, after which they may depend upon the test point\. The open problem asks whether this unsupervised pre\-training stage is truly necessary: perhaps every learnable multiclass problem admits a single local preference function, fixed in advance, whose favorite interpolating hypothesis makes the correct prediction at each test point\. We demonstrate that this is not the case\. Indeed, the obstruction already occurs in a class where every hypothesis uses only two labels; see also the related transductive separation of[Jafar et al\. \(2025\)](https://arxiv.org/html/2608.26516#bib.bib12)\.

###### Definition 4\.5\(Tripartite orientation class\)\.

For every integerm≥2m\\geq 2, setNm:=2m−1N\_\{m\}:=2^\{m\-1\}and letGm=KNm,Nm,NmG\_\{m\}=K\_\{N\_\{m\},N\_\{m\},N\_\{m\}\}be the complete tripartite graph whose three vertex parts each have cardinalityNmN\_\{m\}\. WriteEmE\_\{m\}for its edge set, so\|Em\|=3​Nm2\|E\_\{m\}\|=3N\_\{m\}^\{2\}and every vertex has degree2​Nm2N\_\{m\}\.

LetXm:=\{0,1\}EmX\_\{m\}:=\\\{0,1\\\}^\{E\_\{m\}\}denote the set of all orientations ofGmG\_\{m\}, where the bit indexed by an edge determines which endpoint is its head\. Forz∈Xmz\\in X\_\{m\}ande=\{u,v\}∈Eme=\\\{u,v\\\}\\in E\_\{m\}, writeheadz⁡\(e\)∈\{u,v\}\\operatorname\{head\}\_\{z\}\(e\)\\in\\\{u,v\\\}for the head ofeein the orientationzz\. The vertex sets of the graphsGmG\_\{m\}are pairwise disjoint and serve as labels, and the full domain is𝒳or:=⨆m≥2Xm\\mathcal\{X\}^\{\\mathrm\{or\}\}:=\\bigsqcup\_\{m\\geq 2\}X\_\{m\}\.

For every edgee=\{u,v\}∈Eme=\\\{u,v\\\}\\in E\_\{m\}, fix one distinguished endpointℓ⁡\(e\)∈\{u,v\}\\ell\(e\)\\in\\\{u,v\\\}and define

he​\(x\):=\{headx⁡\(e\),x∈Xm,ℓ⁡\(e\),x∉Xm\.h\_\{e\}\(x\):=\\begin\{cases\}\\operatorname\{head\}\_\{x\}\(e\),&x\\in X\_\{m\},\\\\ \\ell\(e\),&x\\notin X\_\{m\}\.\\end\{cases\}The*tripartite orientation class*isℋor:=\{he:e∈Em,m≥2\}\\mathcal\{H\}\_\{\\mathrm\{or\}\}:=\\\{h\_\{e\}:e\\in E\_\{m\},\\ m\\geq 2\\\}\.

Every hypothesisheh\_\{e\}uses exactly the two endpoint labels ofee, and distinct edges have distinct unordered endpoint pairs\. Thus observing both labels used by the target identifies it exactly\. Nevertheless, the class cannot be learned by a fixed local preference rule\.

###### Theorem 4\.6\.

The tripartite orientation classℋor\\mathcal\{H\}\_\{\\mathrm\{or\}\}is PAC learnable, but it cannot be learned by any hard local regularizer\.

We first prove that the class is learnable, and then establish the lower bound against an arbitrary local regularizer\.

#### PAC learnability\.

Consider the following improper learner\. If two distinct labelsaaandbbappear in the sample, then the unordered pair\{a,b\}\\\{a,b\\\}identifies the unique target edgee=\{a,b\}e=\\\{a,b\\\}, and the learner outputsheh\_\{e\}\. If exactly one labelaaappears in the sample, then a fresh test point is unlikely to be accompanied by a different label, and a learner can simply emit the constant\-aaclassifier\.

#### Reduction to a strict pointwise order\.

Fix an arbitrary local regularizerψ:ℋor×𝒳or→ℝ≥0\\psi:\\mathcal\{H\}\_\{\\mathrm\{or\}\}\\times\\mathcal\{X\}^\{\\mathrm\{or\}\}\\to\\mathbb\{R\}\_\{\\geq 0\}\. Since a local regularizer learns only if every induced learner succeeds, we may refine each pointwise tie according to a fixed enumeration of the countable class\. This produces a strict total order≺z\\prec\_\{z\}on the hypotheses at every test pointzz\. The associated local learner selects the≺z\\prec\_\{z\}\-least member of the version space and predicts with it atzz\. We prove the lower bound for an arbitrary collection of strict orders\(≺z\)z\(\\prec\_\{z\}\)\_\{z\}\.

#### A hard family of target\-distribution pairs\.

Fix a sample sizemmand work in the componentGmG\_\{m\}\. For brevity, writeN:=Nm=2m−1N:=N\_\{m\}=2^\{m\-1\}andp:=2−mp:=2^\{\-m\}\. Lete∈Eme\\in E\_\{m\}be incident to a vertexaa\. DefineDa,eD\_\{a,e\}to be the uniform distribution on orientationsz∈Xmz\\in X\_\{m\}satisfyingheadz⁡\(e\)=a\\operatorname\{head\}\_\{z\}\(e\)=a, and takeheh\_\{e\}as the target\. Under this target\-distribution pair, every example has labelaa\. Furthermore, for a realized sampleS=\(\(z1,a\),…,\(zm,a\)\)S=\(\(z\_\{1\},a\),\\ldots,\(z\_\{m\},a\)\), the version space is exactly

VS\(S\)=\{hf:f∈Em,a∈f,headzi\(f\)=afor everyi∈\[m\]\}\.\\mathrm\{VS\}\(S\)=\\Big\\\{h\_\{f\}:f\\in E\_\{m\},\\ a\\in f,\\ \\operatorname\{head\}\_\{z\_\{i\}\}\(f\)=a\\text\{ for every \}i\\in\[m\]\\Big\\\}\.Indeed, an edge not incident toaacan never output the labelaa, while hypotheses from other components use disjoint labels\. The target edgeeealways survives\. Every other edgeffincident toaasurvives independently with probabilityp=2−mp=2^\{\-m\}, since its orientation is an independent fair bit in each sampled graph orientation\.

#### Every directed triangle creates an error witness\.

Fix a test orientationz∈Xmz\\in X\_\{m\}, and consider a directed cyclic triangle inzz\. Letffbe the earliest of its three edges under the strict local order≺z\\prec\_\{z\}\. Letaabe the tail offfin the directed cycle, and leteebe the edge immediately precedingff, which points intoaa\. Thenheadz⁡\(e\)=a\\operatorname\{head\}\_\{z\}\(e\)=a, whileheadz⁡\(f\)≠a\\operatorname\{head\}\_\{z\}\(f\)\\neq aandf≺zef\\prec\_\{z\}e\. Thus\(a,e\)\(a,e\)defines one of the hard target\-distribution pairs above, while the earlier edgeffpredicts incorrectly at the test pointzz\.

Consider the event thatffsurvives the training sample and every edge incident toaathat precedesffunder≺z\\prec\_\{z\}fails to survive\. The target edgeeeneed not be eliminated, sincef≺zef\\prec\_\{z\}e\. A vertex has degree2​N2N, and the non\-target survival events are independent\. Consequently, this event has probability at least

p​\(1−p\)2​N\.p\(1\-p\)^\{2N\}\.\(9\)Whenever it occurs,ffis the first surviving edge incident toaa, so the local learner predictshf​\(z\)=headz⁡\(f\)≠a=he​\(z\)h\_\{f\}\(z\)=\\operatorname\{head\}\_\{z\}\(f\)\\neq a=h\_\{e\}\(z\)\. For a fixed target incidence\(a,e\)\(a,e\), the events corresponding to distinct witness edgesffare disjoint: at most one edge can be the first survivor under≺z\\prec\_\{z\}\. Hence the probabilities in \([9](https://arxiv.org/html/2608.26516#S4.E9)\) may be summed over all directed triangles producing that target incidence\.

#### Averaging over the tripartite geometry\.

Draw a test orientationzzuniformly fromXmX\_\{m\}, choose an edgeeeuniformly fromEmE\_\{m\}, seta:=headz⁡\(e\)a:=\\operatorname\{head\}\_\{z\}\(e\), and then draw the training sample independently fromDa,emD\_\{a,e\}^\{m\}\. Conditional on\(a,e\)\(a,e\), the test pointzzis itself distributed according toDa,eD\_\{a,e\}\. LetC⁡\(z\)C\(z\)denote the number of directed cyclic triangles inzz\. Conditional onzz, the expected test error averaged over the uniformly random target edge is at leastC⁡\(z\)​p​\(1−p\)2​N/\|Em\|C\(z\)p\(1\-p\)^\{2N\}/\|E\_\{m\}\|\. The graphGmG\_\{m\}containsN3N^\{3\}triangles, and a uniformly random orientation makes any fixed triangle cyclic with probability1/41/4\. Therefore𝔼z\[C⁡\(z\)\]=N3/4\\E\_\{z\}\[C\(z\)\]=N^\{3\}/4\. Since\|Em\|=3​N2\|E\_\{m\}\|=3N^\{2\}, averaging overzzgives

𝔼z,e,S\{A\(S\)\(z\)≠he\(z\)\}\\displaystyle\\E\_\{z,e,S\}\\mathbf\{1\}\\\!\\left\\\{A\(S\)\(z\)\\neq h\_\{e\}\(z\)\\right\\\}≥N3/43​N2​p​\(1−p\)2​N\\displaystyle\\geq\\frac\{N^\{3\}/4\}\{3N^\{2\}\}\\,p\(1\-p\)^\{2N\}=N​p12​\(1−p\)2​N\.\\displaystyle=\\frac\{Np\}\{12\}\(1\-p\)^\{2N\}\.\(10\)WithN=2m−1N=2^\{m\-1\}andp=2−mp=2^\{\-m\}, the right\-hand side equals124​\(1−2−m\)2m\\frac\{1\}\{24\}\(1\-2^\{\-m\}\)^\{2^\{m\}\}, which is at least1/1001/100for everym≥2m\\geq 2\. The expectation in \([10](https://arxiv.org/html/2608.26516#S4.Ex63)\) is an average over the finitely many target incidences\(a,e\)\(a,e\)\. Thus, for everymm, some fixed pair\(he,Da,e\)\(h\_\{e\},D\_\{a,e\}\)satisfies𝔼SLDa,e​\(A⁡\(S\),he\)≥1/100\\E\_\{S\}L\_\{D\_\{a,e\}\}\(A\(S\),h\_\{e\}\)\\geq 1/100\. This completes the argument\. ∎

## 5Structural Conditions and Integrability

The preceding sections rule out several universal algorithmic templates\. We now ask a more constructive question: when does regularization succeed? Two answers emerge\. The first is statistical: though the full hypothesis class may be enormous, the hypotheses still relevant after observing the sample may occupy a simple region of the class\. The second is algebraic: even when a successful learner makes genuinely sample\-dependent choices, those choices may happen to fit together under one global potential\.

### 5\.1Fallback localization

Many pathological multiclass classes share a reveal\-or\-fallback structure\. In particular, the appearance of a private label—one associated with a unique hypothesis—instantly identifies the true labeling function, whereas samples containing only the common, public labels reveal less but suggest a simple default explanation\. Roughly speaking, for such hypothesis classes, learning is possible because every sampleSSeither reveals the target function \(i\.e\.,\|VS⁡\(S\)\|=1\|\\mathrm\{VS\}\(S\)\|=1\) or the version spaceVS⁡\(S\)\\mathrm\{VS\}\(S\)contains one of a few statistically safe “fallback” hypotheses\. We begin by isolating this principle\.

###### Definition 5\.1\.

A finite nonempty setℱ⊆ℋ\\mathcal\{F\}\\subseteq\\mathcal\{H\}is a*fallback core*forℋ\\mathcal\{H\}if

ℱ∩VS⁡\(S\)≠∅\\mathcal\{F\}\\cap\\mathrm\{VS\}\(S\)\\neq\\varnothingfor every ambiguous realizable sampleSS\(i\.e\., with\|V⁡\(S\)\|\>1\|V\(S\)\|\>1\)\.

Thus, whenever the sample has failed to identify the target, at least one member of the same fixed finite family remains consistent\. In this case, learning can be achieved by a simple regularizer that prioritizes the fallback core\.

###### Example 5\.2\(Fallback completions\)\.

The first Cantor class acquires a singleton fallback core after adjoining the all\-⋆\\starhypothesis\. Indeed, a private label uniquely identifies the target, while every remaining ambiguous sample contains only⋆\\starlabels and is therefore consistent with the added hypothesis\. The same observation applies to the EMX\-derived class of[Asilis et al\. \(2025a\)](https://arxiv.org/html/2608.26516#bib.bib11)after taking its all\-⋆\\starcompletion\.

Our incidence and tripartite constructions exhibit the same reveal\-or\-fallback behavior after similarly natural completions, although their fallback families are now infinite\. For the incidence class, adjoin for each component𝒳mI\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}a hypothesisfm⋆f\_\{m\}^\{\\star\}that predicts⋆\\starthroughout𝒳mI\\mathcal\{X\}\_\{m\}^\{\\mathrm\{I\}\}and$\\$elsewhere\. A private label reveals the target; until one appears, eitherh$h\_\{\\$\}or the componentwise fallbackfm⋆f\_\{m\}^\{\\star\}remains consistent\. For the tripartite orientation class, adjoin the constant hypothesisca≡ac\_\{a\}\\equiv afor every vertex labelaa\. A sample containing two distinct labels identifies the target edge, while a sample containing only the labelaaremains consistent withcac\_\{a\}\.

These latter families are infinite, thus not fallback cores in the sense above, yet they are statistically very simple in another manner: each has graph dimension 1\. We will soon develop techniques for handling such infinite yet low\-dimensional fallback structures \([Theorem5\.5](https://arxiv.org/html/2608.26516#S5.Thmtheorem5)\)\.

###### Theorem 5\.3\.

Ifℋ\\mathcal\{H\}has a fallback coreℱ\\mathcal\{F\}of sizeKK, thenℋ\\mathcal\{H\}is learnable by hard SRM\. More precisely, there is a hard\-SRM learner with sample complexity

O⁡\(log⁡K\+log⁡\(1/δ\)ε\)\.O\\\!\\left\(\\frac\{\\log K\+\\log\(1/\\delta\)\}\{\\varepsilon\}\\right\)\.

Setψ⁡\(h\)=0\\psi\(h\)=0forh∈ℱh\\in\\mathcal\{F\}andψ⁡\(h\)=1\\psi\(h\)=1otherwise\. On a nonambiguous sample, the version space is the singleton\{h⋆\}\\\{h^\{\\star\}\\\}; on an ambiguous sample, every minimum\-ψ\\psiconsistent hypothesis belongs toℱ\\mathcal\{F\}\. For eachf∈ℱf\\in\\mathcal\{F\}withLD​\(f,h⋆\)\>εL\_\{D\}\(f,h^\{\\star\}\)\>\\varepsilon, the probability thatffremains consistent with anmm\-sample is at most\(1−ε\)m\(1\-\\varepsilon\)^\{m\}\. A union bound therefore gives

ℙ\[LD\(A\(S\),h⋆\)\>ε\]≤K\(1−ε\)m≤Ke−m​ε,\\P\\\!\\left\[L\_\{D\}\(A\(S\),h^\{\\star\}\)\>\\varepsilon\\right\]\\leq K\(1\-\\varepsilon\)^\{m\}\\leq Ke^\{\-m\\varepsilon\},simultaneously for every fixed choice of tie\-breaking\. ∎

It is not difficult to see that the existence of fallback cores admits an exact behavioral converse, by considering consistent proper learners with restricted range\.

###### Theorem 5\.4\.

A classℋ\\mathcal\{H\}has a finite fallback core if and only if it admits a consistent proper PAC learner whose range on ambiguous realizable samples is finite\.

Ifℱ\\mathcal\{F\}is a fallback core, the hard\-SRM learner constructed in[Theorem5\.3](https://arxiv.org/html/2608.26516#S5.Thmtheorem3)is consistent, properly PAC learnsℋ\\mathcal\{H\}, and emits only members ofℱ\\mathcal\{F\}on ambiguous samples\. Conversely, letAAbe a consistent proper PAC learner whose range on ambiguous samples is a finite familyℱ\\mathcal\{F\}\. For every ambiguous realizable sampleSS, consistency givesA⁡\(S\)∈ℱ∩VS⁡\(S\)A\(S\)\\in\\mathcal\{F\}\\cap\\mathrm\{VS\}\(S\), soℱ\\mathcal\{F\}is a fallback core\. ∎

The fallback core definition is quite restrictive: we now consider a broader localization principle, by which a regularizer forces its output into a statistically manageable region whenever the sample has not already identified the target\. Notably, this fallback region may now grow with the sample size, provided its complexity grows sufficiently slowly\. We useGraph\(ℋ\)\\Gdim\(\\mathcal\{H\}\)to denote the Graph dimension ofℋ\\mathcal\{H\}\.

###### Theorem 5\.5\.

Letψ:ℋ→ℝ≥0\\psi:\\mathcal\{H\}\\to\\mathbb\{R\}\_\{\\geq 0\}be a regularizer whose minimum is attained on every realized version space, and define

ℋr:=\{h∈ℋ:ψ⁡\(h\)≤r\}\.\\mathcal\{H\}\_\{r\}:=\\\{h\\in\\mathcal\{H\}:\\psi\(h\)\\leq r\\\}\.Suppose that for every sample sizemmthere existsrmr\_\{m\}such that every ambiguous \(realizable\)mm\-sample satisfiesVS⁡\(S\)∩ℋrm≠∅\\mathrm\{VS\}\(S\)\\cap\\mathcal\{H\}\_\{r\_\{m\}\}\\neq\\varnothing\. Ifdm:=Graph\(ℋrm\)d\_\{m\}:=\\Gdim\(\\mathcal\{H\}\_\{r\_\{m\}\}\)satisfiesdm​log⁡\(m\+1\)=o⁡\(m\)d\_\{m\}\\log\(m\+1\)=o\(m\), then every hard\-SRM selector induced byψ\\psiPAC learnsℋ\\mathcal\{H\}\.

Leth^\\widehat\{h\}be an arbitrary minimum\-ψ\\psimember ofVS⁡\(S\)\\mathrm\{VS\}\(S\)\. IfSSis nonambiguous, thenh^=h⋆\\widehat\{h\}=h^\{\\star\}\. IfSSis ambiguous, some consistent hypothesis belongs toℋrm\\mathcal\{H\}\_\{r\_\{m\}\}, so minimality givesψ⁡\(h^\)≤rm\\psi\(\\widehat\{h\}\)\\leq r\_\{m\}and henceh^∈ℋrm\\widehat\{h\}\\in\\mathcal\{H\}\_\{r\_\{m\}\}\. The standard graph\-dimension bound for consistent hypotheses gives

ℙ\[∃h∈ℋrm:L^S\(h\)=0,LD\(h,h⋆\)\>ε\]≤exp\(O\(dmlog\(m\+1\)\)−ε​m2\)\.\\P\\\!\\left\[\\exists h\\in\\mathcal\{H\}\_\{r\_\{m\}\}:\\widehat\{L\}\_\{S\}\(h\)=0,\\ L\_\{D\}\(h,h^\{\\star\}\)\>\\varepsilon\\right\]\\leq\\exp\\\!\\left\(O\(d\_\{m\}\\log\(m\+1\)\)\-\\frac\{\\varepsilon m\}\{2\}\\right\)\.The right\-hand side tends to zero for every fixedε\>0\\varepsilon\>0, uniformly over all realizable target\-distribution pairs\. Since every possible minimizer is confined to the same sublevel class, the conclusion holds for every fixed tie\-breaking rule\. ∎

Note that in[Theorem5\.5](https://arxiv.org/html/2608.26516#S5.Thmtheorem5), the full classℋ\\mathcal\{H\}may have infinite graph dimension and exhibit no useful uniform convergence whatsoever\. The theorem invokes uniform convergence only after the sample has failed to identify the target, and only within the low\-complexity sublevel to which regularization confines its output\. A weighted analogue, in which the comparator may incur a controlled amount of empirical error, is given in[TheoremA\.4](https://arxiv.org/html/2608.26516#A1.Thmtheorem4)\.

### 5\.2Ordered disagreement complexity

Fallback localization is phrased in terms of the version space left by a sample\. We now consider a complementary viewpoint, which fixes the targeth∗h^\{\*\}and asks which disagreement sets can be generated by examining hypotheses that are preferred toh∗h^\{\*\}\(by an ambient regularizer under consideration\)\.

A brief bit of notation: forg,h∈ℋg,h\\in\\mathcal\{H\}, writeΔ⁡\(g,h\):=\{x∈𝒳:g⁡\(x\)≠h⁡\(x\)\}\\Delta\(g,h\):=\\\{x\\in\\mathcal\{X\}:g\(x\)\\neq h\(x\)\\\}for their disagreement set\. Given a regularizerψ\\psi, define the lower contour and its disagreement family by

ℒψ​\(h\):=\{g∈ℋ:ψ⁡\(g\)≤ψ⁡\(h\)\},𝒟ψ​\(h\):=\{Δ⁡\(g,h\):g∈ℒψ​\(h\)\}\.\\mathcal\{L\}\_\{\\psi\}\(h\):=\\\{g\\in\\mathcal\{H\}:\\psi\(g\)\\leq\\psi\(h\)\\\},\\qquad\\mathcal\{D\}\_\{\\psi\}\(h\):=\\\{\\Delta\(g,h\):g\\in\\mathcal\{L\}\_\{\\psi\}\(h\)\\\}\.In words,ℒψ​\(h\)\\mathcal\{L\}\_\{\\psi\}\(h\)records the hypotheses that are preferred tohh, while𝒟ψ​\(h\)\\mathcal\{D\}\_\{\\psi\}\(h\)records the differences of all such hypotheses withhh\.

###### Definition 5\.6\.

For a regularizerψ\\psi, define the*ordered disagreement dimension*dOD​\(ψ\)d\_\{\\mathrm\{OD\}\}\(\\psi\)asdOD​\(ψ\):=suph∈ℋVC\(𝒟ψ​\(h\)\)d\_\{\\mathrm\{OD\}\}\(\\psi\):=\\sup\_\{h\\in\\mathcal\{H\}\}\\VC\\bigl\(\\mathcal\{D\}\_\{\\psi\}\(h\)\\bigr\)\. The corresponding class parameter is

dOD⋆​\(ℋ\):=infψdOD​\(ψ\),d\_\{\\mathrm\{OD\}\}^\{\\star\}\(\\mathcal\{H\}\):=\\inf\_\{\\psi\}d\_\{\\mathrm\{OD\}\}\(\\psi\),where the infimum ranges over all regularizers attaining their minima on realized version spaces\.

###### Theorem 5\.7\.

Supposeψ\\psiattains its minimum on every realized version space anddOD​\(ψ\)=d<∞d\_\{\\mathrm\{OD\}\}\(\\psi\)=d<\\infty\. Then every hard\-SRM selector induced byψ\\psiPAC learnsℋ\\mathcal\{H\}with sample complexity

O⁡\(d​log⁡\(1/ε\)\+log⁡\(1/δ\)ε\)\.O\\\!\\left\(\\frac\{d\\log\(1/\\varepsilon\)\+\\log\(1/\\delta\)\}\{\\varepsilon\}\\right\)\.

Fix a targeth⋆h^\{\\star\}\. Sinceh⋆h^\{\\star\}is consistent, every hard\-SRM outputh^\\widehat\{h\}satisfiesψ⁡\(h^\)≤ψ⁡\(h⋆\)\\psi\(\\widehat\{h\}\)\\leq\\psi\(h^\{\\star\}\)\. Hence

Δ⁡\(h^,h⋆\)∈𝒟ψ​\(h⋆\)\.\\Delta\(\\widehat\{h\},h^\{\\star\}\)\\in\\mathcal\{D\}\_\{\\psi\}\(h^\{\\star\}\)\.Consistency means that the unlabeled sample misses this disagreement set\. By the VCε\\varepsilon\-net theorem, a sample of the stated size intersects every member of𝒟ψ​\(h⋆\)\\mathcal\{D\}\_\{\\psi\}\(h^\{\\star\}\)havingDD\-mass greater thanε\\varepsilon, with probability at least1−δ1\-\\delta\. ThereforeLD​\(h^,h⋆\)≤εL\_\{D\}\(\\widehat\{h\},h^\{\\star\}\)\\leq\\varepsilon\. ∎

The advantage of ordered disagreement is that it is target\-relative\. For a fixed targeth⋆h^\{\\star\}, hard SRM can emit only hypothesesggsatisfyingψ⁡\(g\)≤ψ⁡\(h⋆\)\\psi\(g\)\\leq\\psi\(h^\{\\star\}\); hypotheses ranked above the target are therefore irrelevant, regardless of how complicated their disagreement patterns may be\. Consequently,dOD​\(ψ\)d\_\{\\mathrm\{OD\}\}\(\\psi\)can remain finite even when the full class has infinite Graph dimension\. This sufficient condition is not necessary, however: a regularizer may rank many statistically complicated hypotheses below the target even though none of them can ever be selected from a realized version space\. The following example isolates precisely this gap\.

###### Example 5\.8\.

Let𝒳=⨆n≥1Xn\\mathcal\{X\}=\\bigsqcup\_\{n\\geq 1\}X\_\{n\}, where\|Xn\|=2​n\|X\_\{n\}\|=2n\. Include the all\-$\\$hypothesis and, for everynn, the fallback

fn​\(x\)=\{⋆,x∈Xn,$,x∉Xn\.f\_\{n\}\(x\)=\\begin\{cases\}\\star,&x\\in X\_\{n\},\\\\ \\$,&x\\notin X\_\{n\}\.\\end\{cases\}For every nonemptyA⊆XnA\\subseteq X\_\{n\}with\|A\|≤n\|A\|\\leq n, introduce a private labelλn,A\\lambda\_\{n,A\}and the revealing hypothesis

cn,A​\(x\)=\{λn,A,x∈A,⋆,x∈Xn∖A,$,x∉Xn\.c\_\{n,A\}\(x\)=\\begin\{cases\}\\lambda\_\{n,A\},&x\\in A,\\\\ \\star,&x\\in X\_\{n\}\\setminus A,\\\\ \\$,&x\\notin X\_\{n\}\.\\end\{cases\}LetℋRF\\mathcal\{H\}\_\{\\mathrm\{RF\}\}be the resulting class, and consider the hard SRM rule that ranksh$h\_\{\\$\}first, then all fallbacks, and then all revealing hypotheses\. It is not difficult to see that this rule learnsℋRF\\mathcal\{H\}\_\{\\mathrm\{RF\}\}\.

Consider, however, an arbitrary regularizerψ\\psi\. For eachnn, choose a maximum\-ψ\\psirevealing hypothesiscn,A⋆c\_\{n,A^\{\\star\}\}in thennth block\. Since\|A⋆\|≤n\|A^\{\\star\}\|\\leq n, there existsT⊆Xn∖A⋆T\\subseteq X\_\{n\}\\setminus A^\{\\star\}with\|T\|=n\|T\|=n\. For every nonemptyU⊆TU\\subseteq T, maximality givesψ⁡\(cn,U\)≤ψ⁡\(cn,A⋆\)\\psi\(c\_\{n,U\}\)\\leq\\psi\(c\_\{n,A^\{\\star\}\}\), whileΔ⁡\(cn,U,cn,A⋆\)∩T=U\\Delta\(c\_\{n,U\},c\_\{n,A^\{\\star\}\}\)\\cap T=U\. The empty subset is realized by the center itself\. Thus the lower contour ofcn,A⋆c\_\{n,A^\{\\star\}\}shattersTT, anddOD​\(ψ\)≥nd\_\{\\mathrm\{OD\}\}\(\\psi\)\\geq n\. Sincennis arbitrary,dOD⋆​\(ℋRF\)=∞d\_\{\\mathrm\{OD\}\}^\{\\star\}\(\\mathcal\{H\}\_\{\\mathrm\{RF\}\}\)=\\infty, despite the existence of a successful hard\-SRM rule\.

The failure of[Example5\.8](https://arxiv.org/html/2608.26516#S5.Thmtheorem8)arises from hypotheses that lie below the target in the regularizer order but can never actually be selected from a version space\. This suggests restricting attention to genuine minimizers\.

###### Definition 5\.9\.

For a regularizerψ\\psiand targethh, letSelψ⁡\(h\)\\operatorname\{Sel\}\_\{\\psi\}\(h\)denote the collection of all hypotheses inℋ\\mathcal\{H\}that are most\-preferred byψ\\psion anhh\-realizable sample\. That is,

Selψ⁡\(h\):=\{g∈ℋ:there exists a realizable sampleSlabeled byhsuch that​g∈arg​minu∈VS⁡\(S\)⁡ψ​\(u\)\}\.\\operatorname\{Sel\}\_\{\\psi\}\(h\):=\\left\\\{g\\in\\mathcal\{H\}:\\begin\{array\}\[\]\{l\}\\text\{there exists a realizable sample $S$ labeled by $h$\}\\\\\[\-1\.00006pt\] \\text\{such that \}g\\in\\argmin\_\{u\\in\\mathrm\{VS\}\(S\)\}\\psi\(u\)\\end\{array\}\\right\\\}\.Then the*selected ordered disagreement dimension*ofψ\\psiis

dSOD​\(ψ\):=suph∈ℋVC\{Δ⁡\(g,h\):g∈Selψ⁡\(h\)\}\.d\_\{\\mathrm\{SOD\}\}\(\\psi\):=\\sup\_\{h\\in\\mathcal\{H\}\}\\VC\\\{\\Delta\(g,h\):g\\in\\operatorname\{Sel\}\_\{\\psi\}\(h\)\\\}\.

We now demonstrate that finiteness of the SOD dimension suffices to ensure thatψ\\psilearnsℋ\\mathcal\{H\}, using standardε\\varepsilon\-net properties enjoyed by VC classes\. Whether finiteness of the SOD dimension is necessary forψ\\psi’s success, however, remains open\.

###### Proposition 5\.10\.

IfdSOD​\(ψ\)<∞d\_\{\\mathrm\{SOD\}\}\(\\psi\)<\\infty, then every hard\-SRM selector induced byψ\\psiPAC learnsℋ\\mathcal\{H\}\.

Under targeth⋆h^\{\\star\}, every possible hard\-SRM output belongs toSelψ⁡\(h⋆\)\\operatorname\{Sel\}\_\{\\psi\}\(h^\{\\star\}\)and is consistent\. Apply the sameε\\varepsilon\-net argument as in[Theorem5\.7](https://arxiv.org/html/2608.26516#S5.Thmtheorem7)to the selected disagreement family\. ∎

### 5\.3Integrability of revealed preferences

The preceding results ask when a particular regularizer learns\. We now reverse the question\. Suppose a successful learnerAAis already given: when can its sample\-dependent choices be represented by one regularizer? The answer turns out to be intimately related to the revealed preferences ofAA\.

In particular, letAAbe a deterministic consistent proper learner\. Define its revealed\-preference relation≺A\\prec\_\{A\}by

A\(S\)≺Agwheneverg∈VS\(S\)∖\{A\(S\)\}\.A\(S\)\\prec\_\{A\}g\\qquad\\text\{whenever \}g\\in\\mathrm\{VS\}\(S\)\\setminus\\\{A\(S\)\\\}\.Thush≺Agh\\prec\_\{A\}gmeans that the learner has selectedhhwhileggremained feasible\.

###### Theorem 5\.11\.

Letℋ\\mathcal\{H\}be countable\. An arbitrary consistent learnerAAis representable by an injective hard\-SRM regularizer if and only if≺A\\prec\_\{A\}is acyclic\.

IfAAis induced by an injective regularizerψ\\psi, every revealed edgeh≺Agh\\prec\_\{A\}gsatisfiesψ⁡\(h\)<ψ⁡\(g\)\\psi\(h\)<\\psi\(g\), so a directed cycle is impossible\. Conversely, suppose≺A\\prec\_\{A\}is acyclic\. Its transitive closure is a strict partial order, which may be extended to a strict total order on the countable setℋ\\mathcal\{H\}\. Every countable total order embeds intoℚ\\mathbb\{Q\}; letq:ℋ→ℚq:\\mathcal\{H\}\\to\\mathbb\{Q\}be an injective order\-preserving embedding\. Composing with the strictly increasing map

t⟼12\+1π​arctan⁡\(t\)t\\longmapsto\\frac\{1\}\{2\}\+\\frac\{1\}\{\\pi\}\\arctan\(t\)gives an injective regularizerψ:ℋ→\(0,1\)\\psi:\\mathcal\{H\}\\to\(0,1\)\. For every sampleSS, the relation placesA⁡\(S\)A\(S\)strictly below every other member ofVS⁡\(S\)\\mathrm\{VS\}\(S\)\. HenceA⁡\(S\)A\(S\)is the uniqueψ\\psi\-minimum of the version space\. ∎

The same result has a choice\-theoretic formulation\. Recall that a choice functionCCon nonempty finite menus is*contraction consistent*ifC⁡\(B\)∈M⊆B⟹C⁡\(M\)=C⁡\(B\)C\(B\)\\in M\\subseteq B\\Longrightarrow C\(M\)=C\(B\)\. We say thatCCextends the learnerAAif, for every realized sampleSSand every finite menuMMsatisfyingA⁡\(S\)∈M⊆VS⁡\(S\)A\(S\)\\in M\\subseteq\\mathrm\{VS\}\(S\), one hasC⁡\(M\)=A⁡\(S\)C\(M\)=A\(S\)\.

###### Proposition 5\.12\(Finite\-menu extension\)\.

A consistent learner on a countable class is representable by hard SRM if and only if its choices admit a contraction\-consistent extension to all nonempty finite menus\.

IfAAis induced by an injective regularizer, choose from each finite menu its unique minimum\. This choice function is contraction consistent and extendsAA\. Conversely, supposeCCis such an extension\. Defineh≺gh\\prec gwhenC⁡\(\{h,g\}\)=hC\(\\\{h,g\\\}\)=h\. This relation is a tournament\. It has no directed three\-cycle: ifh≺g≺k≺hh\\prec g\\prec k\\prec h, then the choice from\{h,g,k\}\\\{h,g,k\\\}would contradict contraction consistency after restriction to one of the three pairs\. A tournament without directed three\-cycles is transitive, and hence defines a strict total order\. For every realized sampleSSand competitorg∈VS⁡\(S\)∖\{A⁡\(S\)\}g\\in\\mathrm\{VS\}\(S\)\\setminus\\\{A\(S\)\\\}, compatibility on the finite menu\{A⁡\(S\),g\}\\\{A\(S\),g\\\}givesA⁡\(S\)≺gA\(S\)\\prec g\. ThusA⁡\(S\)A\(S\)is the unique order\-minimum of its version space\. Apply[Theorem5\.11](https://arxiv.org/html/2608.26516#S5.Thmtheorem11)\. ∎

The previous results concern hard SRM learners, which select a most\-favored hypotheses from the version spaceVS⁡\(S\)\\mathrm\{VS\}\(S\)of interpolating hypotheses forSS\. We now consider the more general weighted SRM learners, that minimized the sum of empirical risk and \(weighted\) regularization value\. For finite hypothesis sets and finite collections of samples, we obtain an exact characterization: the learner’s prescribed choices admit a weighted\-SRM representation precisely when every directed cycle in a naturally associated weighted preference graph has positive total weight\. We suspect that it should be possible to extend this cycle criterion to infinite systems, by invoking certain compactness assumptions, but that remains an interesting direction for future work\.

###### Definition 5\.13\.

LetHHbe a finite hypothesis class, letAAbe a deterministicHH\-valued learner, and letλ⁡\(S\)\>0\\lambda\(S\)\>0be fixed for every sampleSS\. For a finite family of samples𝒮\\mathcal\{S\}, the*weighted revealed\-preference multigraph*GA,λ​\(𝒮\)G\_\{A,\\lambda\}\(\\mathcal\{S\}\)has vertex setHH, and for everyS∈𝒮S\\in\\mathcal\{S\}and every competitorg∈H∖\{A⁡\(S\)\}g\\in H\\setminus\\\{A\(S\)\\\}, it contains an edgeg⟶A⁡\(S\)g\\longrightarrow A\(S\)of weight

wA,λ​\(S,g\):=L^S​\(g\)−L^S​\(A⁡\(S\)\)λ⁡\(S\)\.w\_\{A,\\lambda\}\(S,g\):=\\frac\{\\widehat\{L\}\_\{S\}\(g\)\-\\widehat\{L\}\_\{S\}\(A\(S\)\)\}\{\\lambda\(S\)\}\.Different samples may generate parallel edges between the same pair of hypotheses\.

###### Theorem 5\.14\(Strict cycle characterization\)\.

Fix a finite hypothesis setHH, a deterministicHH\-valued learnerAA, positive coefficientsλ⁡\(S\)\\lambda\(S\), and a finite family of samples𝒮\\mathcal\{S\}\. There exists a regularizerψ:H→ℝ≥0\\psi:H\\to\\mathbb\{R\}\_\{\\geq 0\}for whichA⁡\(S\)A\(S\)is the unique minimizer of

h⟼L^S​\(h\)\+λ⁡\(S\)​ψ​\(h\)h\\longmapsto\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\(S\)\\psi\(h\)for everyS∈𝒮S\\in\\mathcal\{S\}if and only if every directed cycle inGA,λ​\(𝒮\)G\_\{A,\\lambda\}\(\\mathcal\{S\}\)has strictly positive total weight\.

For a sampleSSand competitorg≠A⁡\(S\)g\\neq A\(S\), strict preference forA⁡\(S\)A\(S\)is equivalent to

ψ⁡\(A⁡\(S\)\)−ψ⁡\(g\)<wA,λ​\(S,g\)\.\\psi\(A\(S\)\)\-\\psi\(g\)<w\_\{A,\\lambda\}\(S,g\)\.Summing these inequalities around a directed cycle makes the potential terms telescope, so every cycle must have positive total weight\. Conversely, suppose every directed cycle has positive total weight\. Since the multigraph is finite, the minimum mean weight of a directed cycle is someμ\>0\\mu\>0; if the graph is acyclic, choose anyμ\>0\\mu\>0\. Fix0<η<μ0<\\eta<\\muand subtractη\\etafrom every edge weight\. The adjusted graph has no negative directed cycle, so the classical feasibility theorem for difference constraints supplies a potential satisfying

ψ⁡\(v\)−ψ⁡\(u\)≤w⁡\(u,v\)−η\\psi\(v\)\-\\psi\(u\)\\leq w\(u,v\)\-\\etaon every edgeu→vu\\to v\. These inequalities are strict for the original weights, and hence makeA⁡\(S\)A\(S\)the unique weighted\-SRM minimizer for everyS∈𝒮S\\in\\mathcal\{S\}\. Adding a common constant makesψ\\psinonnegative\. ∎

## 6Conclusion

Our results rule out several of the most natural algorithmic principles for multiclass learning\. At the broadest level, learning does not reduce to proper learning: some learnable classes cannot be embedded into any properly learnable envelope\. Even when proper learning is possible, interpolation may fail, and the number of training errors required by a successful proper learner can occupy any prescribed sublinear scale\. Furthermore, allowing a fixed notion of hypothesis complexity fails to repair the situation in general — weighted SRM can fail on properly learnable classes, and local regularization can fail for improperly learnable classes\. On the positive side, we demonstrate that regularization succeeds whenever non\-trivial version spaces are sufficiently simple, and at the learner level we provide exact characterizations of SRM using revealed preferences\. Of course, our results leave open the possibility of some other algorithmic principle for multiclass learning that we have yet to consider\. Identifying such principles—tractable learning rules beyond properness and regularization—is perhaps the most compelling direction left open by this work\.

### Acknowledgments

Julian Asilis was supported by the National Science Foundation Graduate Research Fellowship under Grant No\. DGE\-1842487, and by a National Science Foundation award CCF\-2239265\. Shaddin Dughmi was supported by NSF Grant CCF\-2432219, and completed part of this work while on sabbatical as the Carter and Tania Neild visiting professor at Northwestern University, as well as a visiting professor in the Data Science Institute at the University of Chicago\. Vatsal Sharan was supported by National Science Foundation award CCF\-2239265, an Amazon Research Award, a Google Research Scholar Award, and an Okawa Foundation Research Grant\. Shang\-Hua Teng was supported in part by NSF Grant CCF\-2308744\. Alec Sun was supported by the National Science Foundation Graduate Research Fellowship\.

### AI Disclosure

ChatGPT 5\.6 Pro played a significant role in the development of all constructions in the paper\. In particular, it first designed the poisoned first Cantor class of[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6)after the fundamental ideas of the construction were described by the \(human\) authors, i\.e\., augmenting the classic first Cantor class with a small collection of nearly constant⋆\\starhypotheses\. Subsequent interactions used this construction to uncover the tight empirical\-error scale of[Theorems3\.8](https://arxiv.org/html/2608.26516#S3.Thmtheorem8)and[3\.9](https://arxiv.org/html/2608.26516#S3.Thmtheorem9), and then sought a different obstruction capable of defeating weighted SRM\. After several rounds of investigating possible constructions, with little substantive feedback, GPT 5\.6 Pro discovered the projective\-plane incidence class of[Theorem4\.2](https://arxiv.org/html/2608.26516#S4.Thmtheorem2)\. In the same session, it was then instructed to attempt to solve the local regularization open problem of[Asilis et al\. \(2024a\)](https://arxiv.org/html/2608.26516#bib.bib5), and derived the tripartite construction\. The authors then discovered that even in a fresh conversation, GPT Pro was able to resolve the open problem\. It also assisted in finding and formalizing the2d2^\{d\}\-ary tree construction used in the proof of[Theorem3\.1](https://arxiv.org/html/2608.26516#S3.Thmtheorem1), and in the positive results of[Section5](https://arxiv.org/html/2608.26516#S5)\. Finally, the model was used to draft and edit portions of the manuscript\. The authors take full responsibility for all content in the paper\.

## References

- Aden\-Aliet al\.\(2023\)I\. Aden\-Ali, Y\. Cherapanamjeri, A\. Shetty, and N\. ZhivotovskiyOptimal pac bounds without uniform convergence\.In2023 IEEE 64th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 1203–1223\.Cited by:[§1](https://arxiv.org/html/2608.26516#S1.p3.1)\.
- Aden\-Aliet al\.\(2024\)I\. Aden\-Ali, M\. M\. Høandgsgaard, K\. G\. Larsen, and N\. ZhivotovskiyMajority\-of\-three: the simplest optimal learner?\.InThe Thirty Seventh Annual Conference on Learning Theory,pp\. 22–45\.Cited by:[§1](https://arxiv.org/html/2608.26516#S1.p2.1)\.
- Afriat \(1967\)S\. N\. AfriatThe construction of utility functions from expenditure data\.International Economic Review8\(1\),pp\. 67–77\.External Links:[Document](https://dx.doi.org/10.2307/2525382)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px3.p1.1)\.
- Alonet al\.\(2022\)N\. Alon, S\. Hanneke, R\. Holzman, and S\. MoranA theory of pac learnability of partial concept classes\.In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science \(FOCS\),Vol\.,pp\. 658–671\.External Links:[Document](https://dx.doi.org/10.1109/FOCS52979.2021.00070)Cited by:[Corollary 3\.4](https://arxiv.org/html/2608.26516#S3.Thmtheorem4.p1.1.1)\.
- Asiliset al\.\(2024a\)J\. Asilis, S\. Devic, S\. Dughmi, V\. Sharan, and S\. TengOpen problem: can local regularization learn all multiclass problems?\.InProceedings of Thirty Seventh Conference on Learning Theory,S\. Agrawal and A\. Roth \(Eds\.\),Proceedings of Machine Learning Research, Vol\.247,pp\. 5301–5305\.External Links:[Link](https://proceedings.mlr.press/v247/asilis24b.html)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p5.1),[§6](https://arxiv.org/html/2608.26516#S6.SSx2.p1.1),[Open Problem 1](https://arxiv.org/html/2608.26516#Thmproblem1)\.
- Asiliset al\.\(2024b\)J\. Asilis, S\. Devic, S\. Dughmi, V\. Sharan, and S\. TengRegularization and optimal multiclass learning\.InThe Thirty Seventh Annual Conference on Learning Theory,pp\. 260–310\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p4.1),[§4\.2](https://arxiv.org/html/2608.26516#S4.SS2.p1.1)\.
- Asiliset al\.\(2025a\)J\. Asilis, S\. Devic, S\. Dughmi, V\. Sharan, and S\. TengProper learnability and the role of unlabeled data\.InProceedings of The 36th International Conference on Algorithmic Learning Theory,G\. Kamath and P\. Loh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.272,pp\. 112–133\.External Links:[Link](https://proceedings.mlr.press/v272/asilis25b.html)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p7.1),[§1](https://arxiv.org/html/2608.26516#S1.p8.1),[§3\.1](https://arxiv.org/html/2608.26516#S3.SS1.p1.1),[Example 5\.2](https://arxiv.org/html/2608.26516#S5.Thmtheorem2.p1.1.1),[Open Problem 2](https://arxiv.org/html/2608.26516#Thmproblem2),[Open Problem 3](https://arxiv.org/html/2608.26516#Thmproblem3)\.
- Asiliset al\.\(2025b\)J\. Asilis, M\. M\. Høgsgaard, and G\. VelegkasUnderstanding aggregations of proper learners in multiclass classification\.In36th International Conference on Algorithmic Learning Theory,Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p3.1)\.
- Ben\-Davidet al\.\(2019\)S\. Ben\-David, P\. Hrubeš, S\. Moran, A\. Shpilka, and A\. YehudayoffLearnability can be undecidable\.Nature Machine Intelligence1\(1\),pp\. 44–48\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p8.1)\.
- Bousquetet al\.\(2021\)O\. Bousquet, S\. Hanneke, S\. Moran, R\. van Handel, and A\. YehudayoffA theory of universal learning\.InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing,New York, NY, USA\.Cited by:[footnote 2](https://arxiv.org/html/2608.26516#footnote2)\.
- Brukhimet al\.\(2022\)N\. Brukhim, D\. Carmon, I\. Dinur, S\. Moran, and A\. YehudayoffA characterization of multiclass learnability\.In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 943–955\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p3.1),[§1](https://arxiv.org/html/2608.26516#S1.p7.1)\.
- Daniely and Shalev\-Shwartz \(2014\)A\. Daniely and S\. Shalev\-ShwartzOptimal learners for multiclass problems\.InConference on Learning Theory,pp\. 287–316\.Cited by:[§1\.2](https://arxiv.org/html/2608.26516#S1.SS2.SSS0.Px2.p1.1),[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p3.1),[§1](https://arxiv.org/html/2608.26516#S1.p8.1),[§3\.2](https://arxiv.org/html/2608.26516#S3.SS2.p2.1)\.
- Hannekeet al\.\(2026\)S\. Hanneke, Q\. Meng, S\. Moran, and A\. ShaeiriAn optimal sauer lemma overkk\-ary alphabets\.arXiv preprint arXiv:2604\.12952\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1)\.
- Hastieet al\.\(2009\)T\. Hastie, R\. Tibshirani, and J\. FriedmanThe elements of statistical learning: data mining, inference, and prediction\.2 edition,Springer Series in Statistics,Springer,New York\.External Links:[Document](https://dx.doi.org/10.1007/978-0-387-84858-7)Cited by:[footnote 1](https://arxiv.org/html/2608.26516#footnote1)\.
- Hoerl and Kennard \(1970\)A\. E\. Hoerl and R\. W\. KennardRidge regression: biased estimation for nonorthogonal problems\.Technometrics12\(1\),pp\. 55–67\.External Links:[Document](https://dx.doi.org/10.1080/00401706.1970.10488634)Cited by:[footnote 1](https://arxiv.org/html/2608.26516#footnote1)\.
- Hou \(2026\)E\. HouLocal regularization does not characterize multiclass pac learnability\.arXiv preprint arXiv:2607\.23449\.Cited by:[2nd item](https://arxiv.org/html/2608.26516#S1.I1.i2.p1.1),[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1)\.
- Jafaret al\.\(2025\)S\. Jafar, J\. Asilis, and S\. DughmiLocal regularizers are not transductive learners\.InProceedings of Thirty Eighth Conference on Learning Theory,N\. Haghtalab and A\. Moitra \(Eds\.\),Proceedings of Machine Learning Research, Vol\.291,pp\. 2942–2957\.External Links:[Link](https://proceedings.mlr.press/v291/jafar25a.html)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1),[§4\.2](https://arxiv.org/html/2608.26516#S4.SS2.p1.1)\.
- Krogh and Hertz \(1991\)A\. Krogh and J\. A\. HertzA simple weight decay can improve generalization\.InAdvances in Neural Information Processing Systems,J\. E\. Moody, S\. J\. Hanson, and R\. P\. Lippmann \(Eds\.\),Vol\.4,pp\. 950–957\.Cited by:[footnote 1](https://arxiv.org/html/2608.26516#footnote1)\.
- Pabbaraju \(2026\)C\. PabbarajuThe optimal sample complexity of multiclass and list learning\.arXiv preprint arXiv:2604\.24749\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2608.26516#S1.p3.1),[§1](https://arxiv.org/html/2608.26516#S1.p7.1)\.
- Plott \(1973\)C\. R\. PlottPath independence, rationality, and social choice\.Econometrica41\(6\),pp\. 1075–1091\.External Links:[Link](https://authors.library.caltech.edu/records/besvk-pqy14)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px3.p1.1)\.
- Rawal and Zhivotovskiy \(2026\)D\. Rawal and N\. ZhivotovskiyMajority\-of\-three is optimal\.arXiv preprint arXiv:2606\.13614\.Cited by:[§1](https://arxiv.org/html/2608.26516#S1.p2.1)\.
- Rochet \(1987\)J\. RochetA necessary and sufficient condition for rationalizability in a quasi\-linear context\.Journal of Mathematical Economics16\(2\),pp\. 191–200\.External Links:[Document](https://dx.doi.org/10.1016/0304-4068%2887%2990007-3)Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px3.p1.1)\.
- Shalev\-Shwartz and Ben\-David \(2014\)S\. Shalev\-Shwartz and S\. Ben\-DavidUnderstanding machine learning: from theory to algorithms\.Cambridge university press\.Cited by:[§1\.3](https://arxiv.org/html/2608.26516#S1.SS3.SSS0.Px2.p1.1),[footnote 1](https://arxiv.org/html/2608.26516#footnote1)\.
- Tibshirani \(1996\)R\. TibshiraniRegression shrinkage and selection via the lasso\.Journal of the Royal Statistical Society: Series B \(Methodological\)58\(1\),pp\. 267–288\.External Links:[Document](https://dx.doi.org/10.1111/j.2517-6161.1996.tb02080.x)Cited by:[footnote 1](https://arxiv.org/html/2608.26516#footnote1)\.

## Appendix AAuxiliary Probabilistic and Structural Lemmas

We collect several probabilistic and structural tools used by the constructions in the main text\. We conclude with a weighted extension of the localization principle developed in[Section5\.1](https://arxiv.org/html/2608.26516#S5.SS1)\.

### A\.1Selecting a light marker

The proper learner for the poisoned first\-Cantor class chooses a marker of minimum empirical frequency\. The following lemma shows that this simple rule is distribution\-free: among sufficiently many distinguished atoms, an empirically least frequent one cannot carry substantial population mass\.

###### Lemma A\.1\(Least\-observed marker\)\.

Letp1,…,pNp\_\{1\},\\ldots,p\_\{N\}be the masses ofNNdistinguished atoms under a probability distribution, and letp^i\\widehat\{p\}\_\{i\}denote their empirical frequencies in an iid sample of sizemm\. Choosei^∈arg​mini∈\[N\]⁡p^i\\widehat\{i\}\\in\\argmin\_\{i\\in\[N\]\}\\widehat\{p\}\_\{i\}\. There is a universal constantC\>0C\>0such that, for everyη,δ∈\(0,1\)\\eta,\\delta\\in\(0,1\), if

N≥8ηandm​η≥C​log⁡1η​δ,N\\geq\\frac\{8\}\{\\eta\}\\qquad\\text\{and\}\\qquad m\\eta\\geq C\\log\\frac\{1\}\{\\eta\\delta\},thenℙ\[pi^\>η\]≤δ\\P\[p\_\{\\widehat\{i\}\}\>\\eta\]\\leq\\delta\.

Choosei0i\_\{0\}withpi0≤1/N≤η/8p\_\{i\_\{0\}\}\\leq 1/N\\leq\\eta/8\. A Chernoff bound givesℙ\[p^i0\>η/2\]≤e−cm​η\.\\P\[\\widehat\{p\}\_\{i\_\{0\}\}\>\\eta/2\]\\leq e^\{\-cm\\eta\}\.On the other hand, for everyiiwithpi\>ηp\_\{i\}\>\\eta,ℙ\[p^i≤η/2\]≤e−cm​η\.\\P\[\\widehat\{p\}\_\{i\}\\leq\\eta/2\]\\leq e^\{\-cm\\eta\}\.There are at most1/η1/\\etasuch heavy atoms\. Except on an event of probability at most\(1\+1/η\)​e−c​m​η\(1\+1/\\eta\)e^\{\-cm\\eta\}, the empirical minimum is therefore attained only by atoms of mass at mostη\\eta\. Increasing the universal constantCCproves the claim\. ∎

### A\.2A hidden\-halfset lemma

The lower bounds for the poisoned constructions use the same posterior\-symmetry principle: after observing onlyo⁡\(K\)o\(K\)samples from a uniformly randomKK\-subset of a set of size roughly2​K2K, no procedure can cover much more than half of the hidden set\.

###### Lemma A\.2\(Hidden halfset\)\.

LetK→∞K\\to\\infty, letN=o⁡\(K\)N=o\(K\), and letCCbe a set of size2​K\+N2K\+N\. ChooseT⊆CT\\subseteq Cuniformly among theKK\-subsets\. A possibly randomized procedure observes at mostm=o⁡\(K\)m=o\(K\)iid draws from the uniform distribution onTTand outputs a setB⊆CB\\subseteq Cwith\|B\|≤K\+N\|B\|\\leq K\+N\. Then

ℙ\[\|T∖B\|≥K/5\]=1−o\(1\),\\P\\left\[\|T\\setminus B\|\\geq K/5\\right\]=1\-o\(1\),uniformly over the procedure\.

Condition on the complete observed sequence, its set of distinct valuesR⊆TR\\subseteq T, and the procedure’s internal randomness\. EveryKK\-subset ofCCcontainingRRassigns the same likelihood to the observed sequence\. Hence the posterior law ofTTis uniform over these sets\. WriteT=R∪UT=R\\cup U, whereUUis a uniformly random\(K−\|R\|\)\(K\-\|R\|\)\-subset ofC∖RC\\setminus R\.

Conditional onRRandBB, the random variable\|U∩\(B∖R\)\|\|U\\cap\(B\\setminus R\)\|is hypergeometric\. Since\|R\|≤m=o⁡\(K\)\|R\|\\leq m=o\(K\)and\|B\|≤K\+N=\(1\+o⁡\(1\)\)​K\|B\|\\leq K\+N=\(1\+o\(1\)\)K, its mean is at most

\(K−\|R\|\)​K\+N2​K\+N−\|R\|=\(12\+o⁡\(1\)\)​K\.\(K\-\|R\|\)\\frac\{K\+N\}\{2K\+N\-\|R\|\}=\\left\(\\frac\{1\}\{2\}\+o\(1\)\\right\)K\.A hypergeometric Chernoff bound therefore gives

ℙ\[\|T∩B\|\>4K/5∣R,B\]≤e−cK\\P\[\|T\\cap B\|\>4K/5\\mid R,B\]\\leq e^\{\-cK\}for all sufficiently largeKK, uniformly inRRandBB\. Since\|T∖B\|=K−\|T∩B\|\|T\\setminus B\|=K\-\|T\\cap B\|, the conclusion follows\. ∎

### A\.3Projective\-plane incidence estimates

###### Lemma A\.3\(Projective\-plane mixing\)\.

LetMMbe the point\-line incidence matrix of a projective plane of orderqq, and writeN=q2\+q\+1N=q^\{2\}\+q\+1andd=q\+1d=q\+1\. Then

M​M⊤=q​I\+J\.MM^\{\\top\}=qI\+J\.Consequently, the singular values ofMMareddandq\\sqrt\{q\}, and for every setAAof points and setBBof lines,

\|e⁡\(A,B\)−dN​\|A\|​\|B\|\|≤q​\|A\|​\|B\|\.\\left\|e\(A,B\)\-\\frac\{d\}\{N\}\|A\|\|B\|\\right\|\\leq\\sqrt\{q\|A\|\|B\|\}\.

Every row ofMMcontainsq\+1q\+1ones, while two distinct rows have inner product one\. This givesM​M⊤=q​I\+JMM^\{\\top\}=qI\+J\. The all\-ones vector has eigenvalue\(q\+1\)2\(q\+1\)^\{2\}, and every vector orthogonal to it has eigenvalueqq\. The asserted singular values follow\. Decomposing the indicator vectors ofAAandBBinto their all\-ones and orthogonal components then yields the displayed mixing estimate\. ∎

This is the estimate used in the incidence\-inversion step \([7](https://arxiv.org/html/2608.26516#S4.E7)\) of the proof of[Theorem4\.2](https://arxiv.org/html/2608.26516#S4.Thmtheorem2)\.

### A\.4A weighted approximate\-interpolation principle

Fallback localization extends naturally to weighted learners that make a controlled number of training errors\. The following theorem records the corresponding comparator argument\.

###### Theorem A\.4\(Approximate\-interpolation weighted SRM\)\.

Letψ:ℋ→ℝ≥0\\psi:\\mathcal\{H\}\\to\\mathbb\{R\}\_\{\\geq 0\}, letλm\>0\\lambda\_\{m\}\>0, and suppose that the weighted objective attains its minimum on every realizablemm\-sample\. Assume that for every such sampleSSthere existsgS∈ℋg\_\{S\}\\in\\mathcal\{H\}satisfying

L^S​\(gS\)≤ηm,ψ⁡\(gS\)≤rm\.\\widehat\{L\}\_\{S\}\(g\_\{S\}\)\\leq\\eta\_\{m\},\\qquad\\psi\(g\_\{S\}\)\\leq r\_\{m\}\.SetRm:=rm\+ηmλm\.R\_\{m\}:=r\_\{m\}\+\\frac\{\\eta\_\{m\}\}\{\\lambda\_\{m\}\}\.If

ηm\+λm​rm→0andGraph\(ℋRm\)​log⁡\(m\+1\)=o⁡\(m\),\\eta\_\{m\}\+\\lambda\_\{m\}r\_\{m\}\\to 0\\qquad\\text\{and\}\\qquad\\Gdim\(\\mathcal\{H\}\_\{R\_\{m\}\}\)\\log\(m\+1\)=o\(m\),whereℋR:=\{h∈ℋ:ψ⁡\(h\)≤R\}\\mathcal\{H\}\_\{R\}:=\\\{h\\in\\mathcal\{H\}:\\psi\(h\)\\leq R\\\}, then every minimizer ofh↦L^S​\(h\)\+λm​ψ​\(h\)h\\mapsto\\widehat\{L\}\_\{S\}\(h\)\+\\lambda\_\{m\}\\psi\(h\)PAC learnsℋ\\mathcal\{H\}\.

Leth^\\widehat\{h\}be any minimizer\. Comparison withgSg\_\{S\}gives

L^S​\(h^\)\+λm​ψ​\(h^\)≤ηm\+λm​rm\.\\widehat\{L\}\_\{S\}\(\\widehat\{h\}\)\+\\lambda\_\{m\}\\psi\(\\widehat\{h\}\)\\leq\\eta\_\{m\}\+\\lambda\_\{m\}r\_\{m\}\.Since both terms on the left are nonnegative,

L^S​\(h^\)≤ηm\+λm​rmandψ⁡\(h^\)≤rm\+ηm/λm=Rm\.\\widehat\{L\}\_\{S\}\(\\widehat\{h\}\)\\leq\\eta\_\{m\}\+\\lambda\_\{m\}r\_\{m\}\\qquad\\text\{and\}\\qquad\\psi\(\\widehat\{h\}\)\\leq r\_\{m\}\+\\eta\_\{m\}/\\lambda\_\{m\}=R\_\{m\}\.Thus every minimizer lies in the fixed sublevel classℋRm\\mathcal\{H\}\_\{R\_\{m\}\}and has vanishing empirical error\. Uniform convergence on that sublevel yields

suph∈ℋRm\|LD​\(h,h⋆\)−L^S​\(h\)\|=oℙ​\(1\)\\sup\_\{h\\in\\mathcal\{H\}\_\{R\_\{m\}\}\}\|L\_\{D\}\(h,h^\{\\star\}\)\-\\widehat\{L\}\_\{S\}\(h\)\|=o\_\{\\P\}\(1\)uniformly over realizable pairs\. HenceLD​\(h^,h⋆\)≤L^S​\(h^\)\+oℙ​\(1\)→0L\_\{D\}\(\\widehat\{h\},h^\{\\star\}\)\\leq\\widehat\{L\}\_\{S\}\(\\widehat\{h\}\)\+o\_\{\\P\}\(1\)\\to 0\. The argument controls all minimizers simultaneously and is therefore robust to ties\. ∎

## Appendix BOmitted Proofs for Empirical Noninterpolation

### B\.1The tunable lower bound

We now prove[Theorem3\.9](https://arxiv.org/html/2608.26516#S3.Thmtheorem9)\. Fix a nonnegative sequenceam=o⁡\(m\)a\_\{m\}=o\(m\)and define

rm:=max⁡\{⌈am⌉,⌈log⁡log⁡\(m\+ee\)⌉\}\.r\_\{m\}:=\\max\\left\\\{\\lceil a\_\{m\}\\rceil,\\left\\lceil\\log\\log\(m\+e^\{e\}\)\\right\\rceil\\right\\\}\.Thenrm→∞r\_\{m\}\\to\\infty,rm=o⁡\(m\)r\_\{m\}=o\(m\), andrm≥amr\_\{m\}\\geq a\_\{m\}\. Put

Nm:=max⁡\{1,⌊min⁡\{erm/32,m/rm\}⌋\},Km:=m3\.N\_\{m\}:=\\max\\left\\\{1,\\left\\lfloor\\min\\left\\\{e^\{r\_\{m\}/32\},\\sqrt\{m/r\_\{m\}\}\\right\\\}\\right\\rfloor\\right\\\},\\qquad K\_\{m\}:=m^\{3\}\.These parameters satisfy

Nm→∞,Nm​rmm→0,Nme−rm/8→0\.N\_\{m\}\\to\\infty,\\qquad\\frac\{N\_\{m\}r\_\{m\}\}\{m\}\\to 0,\\qquad N\_\{m\}e^\{\-r\_\{m\}/8\}\\to 0\.\(11\)Indeed, botherm/32e^\{r\_\{m\}/32\}andm/rm\\sqrt\{m/r\_\{m\}\}diverge; moreover,Nm​rm/m≤rm/mN\_\{m\}r\_\{m\}/m\\leq\\sqrt\{r\_\{m\}/m\}andNme−rm/8≤e−3rm/32N\_\{m\}e^\{\-r\_\{m\}/8\}\\leq e^\{\-3r\_\{m\}/32\}for all sufficiently largemm\.

For each block indexj≥1j\\geq 1, letPj=\{pj,1,…,pj,Nj\}P\_\{j\}=\\\{p\_\{j,1\},\\ldots,p\_\{j,N\_\{j\}\}\\\}be a marker set, letCjC\_\{j\}be a core of size2​Kj\+Nj2K\_\{j\}\+N\_\{j\}, and putXj=Pj⊔CjX\_\{j\}=P\_\{j\}\\sqcup C\_\{j\}\. Thus\|Xj\|=2​Kj\+2​Nj\|X\_\{j\}\|=2K\_\{j\}\+2N\_\{j\}, and every half\-set has sizeKj\+NjK\_\{j\}\+N\_\{j\}\. Introduce global labels⋆\\starand$\\$, a private labelλj,A\\lambda\_\{j,A\}for every half\-setA⊆XjA\\subseteq X\_\{j\}, and a poison labelρj,i\\rho\_\{j,i\}for every marker\. Include the all\-$\\$hypothesis, every Cantor hypothesis

cj,A​\(x\)=\{⋆,x∈A,λj,A,x∈Xj∖A,$,x∉Xj,c\_\{j,A\}\(x\)=\\begin\{cases\}\\star,&x\\in A,\\\\ \\lambda\_\{j,A\},&x\\in X\_\{j\}\\setminus A,\\\\ \\$,&x\\notin X\_\{j\},\\end\{cases\}and every fallback

sj,i​\(x\)=\{ρj,i,x=pj,i,⋆,x∈Xj∖\{pj,i\},$,x∉Xj\.s\_\{j,i\}\(x\)=\\begin\{cases\}\\rho\_\{j,i\},&x=p\_\{j,i\},\\\\ \\star,&x\\in X\_\{j\}\\setminus\\\{p\_\{j,i\}\\\},\\\\ \\$,&x\\notin X\_\{j\}\.\\end\{cases\}Letℋa\\mathcal\{H\}\_\{a\}be the resulting class\.

###### Lemma B\.1\.

The classℋa\\mathcal\{H\}\_\{a\}is countable, closed, pointwise finite\-range, and properly PAC learnable\.

Countability and pointwise finite range follow because every block is finite and supports only finitely many hypotheses\. For closedness, letffbe finitely consistent withℋa\\mathcal\{H\}\_\{a\}\. Iff≡$f\\equiv\\$, thenf=h$f=h\_\{\\$\}\. Otherwise choosex∈Xjx\\in X\_\{j\}withf⁡\(x\)≠$f\(x\)\\neq\\$\. Two\-point restrictions forceffto equal$\\$outsideXjX\_\{j\}, since no nonbackground hypothesis is active on two blocks\. Finite consistency on the finite blockXjX\_\{j\}then supplies one hypothesis agreeing withffthere, and hence everywhere\.

For learnability, choose cutoffsJs→∞J\_\{s\}\\to\\inftysufficiently slowly that

log⁡\|ℋa,≤Js\|=o⁡\(s\)andinfj\>JsNj→∞,\\log\|\\mathcal\{H\}\_\{a,\\leq J\_\{s\}\}\|=o\(s\)\\qquad\\text\{and\}\\qquad\\inf\_\{j\>J\_\{s\}\}N\_\{j\}\\to\\infty,whereℋa,≤Js\\mathcal\{H\}\_\{a,\\leq J\_\{s\}\}contains the background hypothesis and all hypotheses supported on the firstJsJ\_\{s\}blocks\. Such a sequence exists because every initial class is finite andNj→∞N\_\{j\}\\to\\infty\.

On a sample of sizess, use finite\-class consistent learning on blocksj≤Jsj\\leq J\_\{s\}\. On a larger block, use the same reveal\-or\-least\-observed\-marker learner as in the proof of[Theorem3\.6](https://arxiv.org/html/2608.26516#S3.Thmtheorem6): a private or poison label identifies the target, while an all\-⋆\\starsample triggers the fallback associated with a least\-observed marker\. The initial class is controlled by the realizable finite\-class bound because its logarithmic size iso⁡\(s\)o\(s\)\. Uniformly over the tail blocks, the number of markers tends to infinity, so[LemmaA\.1](https://arxiv.org/html/2608.26516#A1.Thmtheorem1)controls the selected marker mass\. The remaining failure events are precisely that the sample misses a private\-label region or a target poison point of substantial mass, each of which has exponentially small probability\. This proves distribution\-free proper learnability\. ∎

Fix an arbitrary proper PAC learnerAAforℋa\\mathcal\{H\}\_\{a\}and a sufficiently large sample sizemm\. Work in blockXmX\_\{m\}\. ChooseT⊆CmT\\subseteq C\_\{m\}uniformly among theKmK\_\{m\}\-subsets, putAT:=Pm∪TA\_\{T\}:=P\_\{m\}\\cup T, and take targetcm,ATc\_\{m,A\_\{T\}\}\. DefineDTD\_\{T\}by

DT​\(pm,i\)=rmm\(i∈\[Nm\]\),D\_\{T\}\(p\_\{m,i\}\)=\\frac\{r\_\{m\}\}\{m\}\\qquad\(i\\in\[N\_\{m\}\]\),and distribute the remaining mass1−qm1\-q\_\{m\}uniformly onTT, where

qm:=Nm​rmm=o⁡\(1\)\.q\_\{m\}:=\\frac\{N\_\{m\}r\_\{m\}\}\{m\}=o\(1\)\.Every point in the support is labeled⋆\\star\.

LetEmE\_\{m\}be the event that every marker appears at leastrm/2r\_\{m\}/2times\. Each marker count has meanrmr\_\{m\}, so a Chernoff bound and \([11](https://arxiv.org/html/2608.26516#A2.E11)\) give

ℙ\(Emc\)≤Nme−rm/8=o\(1\)\.\\P\(E\_\{m\}^\{c\}\)\\leq N\_\{m\}e^\{\-r\_\{m\}/8\}=o\(1\)\.OnEmE\_\{m\}, every fallbacksm,is\_\{m,i\}supported on the active block makes at leastrm/2r\_\{m\}/2training mistakes\.

We next show that every nonfallback output has constant population error with probability1−o⁡\(1\)1\-o\(1\)over the random choice ofTT, the sample, and the learner’s internal randomness\. The background hypothesis and all hypotheses supported on another block have error one\. Suppose the output is a Cantor hypothesiscm,Bc\_\{m,B\}, and putBC:=B∩CmB\_\{C\}:=B\\cap C\_\{m\}\. Since\|B\|=Km\+Nm\|B\|=K\_\{m\}\+N\_\{m\}, one has\|BC\|≤Km\+Nm\|B\_\{C\}\|\\leq K\_\{m\}\+N\_\{m\}\. Conditional on the marker observations, the learner sees at mostm=o⁡\(Km\)m=o\(K\_\{m\}\)iid uniform draws from the hidden setTT; the marker observations themselves carry no information aboutTT\. Applying[LemmaA\.2](https://arxiv.org/html/2608.26516#A1.Thmtheorem2)withK=KmK=K\_\{m\},N=NmN=N\_\{m\}, andC=CmC=C\_\{m\}gives

\|T∖BC\|≥Km/5\|T\\setminus B\_\{C\}\|\\geq K\_\{m\}/5with probability1−o⁡\(1\)1\-o\(1\)\. Therefore

LDT​\(cm,B,cm,AT\)≥\(1−qm\)​\|T∖BC\|Km≥17L\_\{D\_\{T\}\}\(c\_\{m,B\},c\_\{m,A\_\{T\}\}\)\\geq\(1\-q\_\{m\}\)\\frac\{\|T\\setminus B\_\{C\}\|\}\{K\_\{m\}\}\\geq\\frac\{1\}\{7\}for all sufficiently largemm\.

Fixε0=δ0=1/20\\varepsilon\_\{0\}=\\delta\_\{0\}=1/20\. SinceAAPAC learns, for every fixedTTand all sufficiently largemm,

ℙS,A\[LDT\(Am\(S\),cm,AT\)\>ε0\]≤δ0\.\\P\_\{S,A\}\\left\[L\_\{D\_\{T\}\}\(A\_\{m\}\(S\),c\_\{m,A\_\{T\}\}\)\>\\varepsilon\_\{0\}\\right\]\\leq\\delta\_\{0\}\.Averaging over the random choice ofTTand comparing with the preceding lower bound shows that the learner outputs an active\-block fallback with probability at least1−δ0−o⁡\(1\)1\-\\delta\_\{0\}\-o\(1\)on average overTT\. Hence there is a fixedTTfor which this fallback probability is at least3/43/4\. For this fixed target\-distribution pair,ℙ\(Em\)=1−o⁡\(1\)\\P\(E\_\{m\}\)=1\-o\(1\)because the marker marginal is independent ofTT\. Thus, for all sufficiently largemm,

ℙ\[mL^S\(Am\(S\)\)≥rm/2\]≥12\.\\P\\left\[m\\widehat\{L\}\_\{S\}\(A\_\{m\}\(S\)\)\\geq r\_\{m\}/2\\right\]\\geq\\frac\{1\}\{2\}\.Sincerm≥amr\_\{m\}\\geq a\_\{m\}, the theorem follows with a universal constant\. ∎

### B\.2Pathological learners

The following examples explain why the upper bound in[Theorem3\.8](https://arxiv.org/html/2608.26516#S3.Thmtheorem8)is existential: an otherwise successful learner may behave arbitrarily on a sufficiently rare sequence of samples\.

###### Proposition B\.2\.

There is a proper PAC learner for the two constant binary hypotheses onℕ\\mathbb\{N\}that misclassifies every training point on some realizable sample of every size\.

Leth0≡0h\_\{0\}\\equiv 0andh1≡1h\_\{1\}\\equiv 1\. On anmm\-sample, if the ordered unlabeled sequence is exactly\(1,2,…,m\)\(1,2,\\ldots,m\), output the constant hypothesis opposite to the observed label; otherwise output the correct constant hypothesis\. The exceptional sample is misclassified completely\. For every marginalDD,

ℙ\[\(X1,…,Xm\)=\(1,…,m\)\]=∏i=1mD\(i\)≤m−m\\P\[\(X\_\{1\},\\ldots,X\_\{m\}\)=\(1,\\ldots,m\)\]=\\prod\_\{i=1\}^\{m\}D\(i\)\\leq m^\{\-m\}by AM–GM\. The additional failure probability therefore vanishes superexponentially\. ∎

###### Proposition B\.3\.

The preceding pathology can coexist with optimal realizable sample complexityΘ⁡\(ε−1​log⁡\(1/δ\)\)\\Theta\(\\varepsilon^\{\-1\}\\log\(1/\\delta\)\)\.

Let𝒳=\{0\}∪ℕ\\mathcal\{X\}=\\\{0\\\}\\cup\\mathbb\{N\}and

h0≡0,h1\(x\)=𝟏\{x=0\},h2≡1\.h\_\{0\}\\equiv 0,\\qquad h\_\{1\}\(x\)=\\mathbf\{1\}\\\{x=0\\\},\\qquad h\_\{2\}\\equiv 1\.A finite\-class learner gives the upper boundO⁡\(ε−1​log⁡\(1/δ\)\)O\(\\varepsilon^\{\-1\}\\log\(1/\\delta\)\)\. For the matching lower bound, place mass2​ε2\\varepsilonon00and the remaining mass on11\. Under targetsh0h\_\{0\}andh1h\_\{1\}, the labeled samples are identical unless00is observed\. Conditional on missing00, no learner can identify both targets; for at least one of them it incurs error2​ε2\\varepsilonwith conditional probability at least1/21/2\. Since00is missed with probability\(1−2​ε\)m\(1\-2\\varepsilon\)^\{m\}, the usualΩ⁡\(ε−1​log⁡\(1/δ\)\)\\Omega\(\\varepsilon^\{\-1\}\\log\(1/\\delta\)\)lower bound follows\.

Now modify an optimal finite\-class learner only on the ordered sample\(1,2,…,m\)\(1,2,\\ldots,m\): if all labels are zero, outputh2h\_\{2\}, and if all labels are one, outputh0h\_\{0\}\. The exceptional probability is at mostm−mm^\{\-m\}under every marginal, so the asymptotic sample complexity is unchanged, while the emitted hypothesis misclassifies every training point on the exceptional realizable samples\. ∎