Two Dimensions Govern Agnostic Multiclass Transductive Learning

# Two Dimensions Govern Agnostic Multiclass Transduction
Source: [https://arxiv.org/html/2608.25326](https://arxiv.org/html/2608.25326)
###### Abstract

In transductive classification, an adversary fixes a labeled population, one label is hidden uniformly, and the learner sees all remaining labels\. For binary classes, agnostic transductive and PAC learning have the same minimax rate\. Whether this extends to multiclass learning was open, especially for unbounded label spaces where uniform convergence can fail\.

We resolve the question up to logarithmic factors\. For every multiclass classℋ\\mathcal\{H\}with DS dimensiondDSd\_\{\\mathrm\{DS\}\}and Natarajan dimensiondNd\_\{\\mathrm\{N\}\}, the optimal agnostic transductive excess error satisfies

Θ~​\(dDSn\+dNn\)\.\\widetilde\{\\Theta\}\\left\(\\frac\{d\_\{\\mathrm\{DS\}\}\}\{n\}\+\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\}\{n\}\}\\right\)\.The result holds for arbitrary label spaces\. The two terms are both necessary\. A DS pseudo\-cube gives the realizabledDS/nd\_\{\\mathrm\{DS\}\}/nobstruction, while a Natarajan cube with repeated points and fair labels gives the agnosticdN/n\\sqrt\{d\_\{\\mathrm\{N\}\}/n\}obstruction\.

The upper bound uses a random\-reservation principle\. The learner deliberately ignores a constant fraction of the visible labels, which makes the true test point uniform in a large unseen block\. We combine realizable compression, a label\-space reduction, and inside\-menu agnostic compression across this finite\-population split\. A new without\-replacement multiplicative\-weights lemma preserves the fastdDS/nd\_\{\\mathrm\{DS\}\}/nterm\. Consequently, agnostic multiclass PAC and transductive learning obey the same two\-dimension law up to logarithmic factors\.

## 1Introduction

The transductive model isolates one of the simplest prediction problems with dependent data\. An adversary choosesnnlabeled examples\. One index is hidden uniformly at random\. The learner sees the full unlabeled population and every label except the hidden one, then predicts that label\. Its loss is compared with the empirical loss of the best fixed hypothesis in a benchmark class\.

For realizable classification, transductive learning is tightly connected to one\-inclusion graphs and to PAC learning\([Haussler et al\., 1994](https://arxiv.org/html/2608.25326#bib.bib4);[Daniely and Shalev\-Shwartz, 2014](https://arxiv.org/html/2608.25326#bib.bib5);[Asilis et al\., 2024](https://arxiv.org/html/2608.25326#bib.bib8)\)\. The agnostic setting is subtler\. A learner must compete additively with the best hypothesis on each adversarial population\. Generic transformations from PAC learners to transductive learners lose a factor of1/ε1/\\varepsilonin sample complexity\([Asilis et al\., 2024](https://arxiv.org/html/2608.25326#bib.bib8)\)\. In the other direction, a recent transformation from transductive to PAC learning has only a class\-independent validation cost\([Dughmi et al\., 2025](https://arxiv.org/html/2608.25326#bib.bib9)\)\. For binary classification, a symmetrization of the agnostic one\-inclusion graph completes the converse and gives the optimal rateΘ⁡\(d/n\)\\Theta\(\\sqrt\{d/n\}\), whereddis VC dimension\. The corresponding multiclass question was left open\.

Multiclass learning over an arbitrary label space has an additional difficulty: no single dimension controls its agnostic sample complexity\. The DS dimension characterizes realizable learnability\([Daniely and Shalev\-Shwartz, 2014](https://arxiv.org/html/2608.25326#bib.bib5);[Brukhim et al\., 2022](https://arxiv.org/html/2608.25326#bib.bib7)\)\. Recent work showed that the Natarajan dimension reappears in the small\-excess agnostic regime\([Cohen et al\., 2026](https://arxiv.org/html/2608.25326#bib.bib10)\)\. A subsequent sharp density theorem removed the remaining polynomial gap in the DS term\([Pabbaraju, 2026](https://arxiv.org/html/2608.25326#bib.bib11)\)\. Combining these results, the agnostic PAC sample complexity is, up to logarithms,

dDSε\+dNε2\.\\frac\{d\_\{\\mathrm\{DS\}\}\}\{\\varepsilon\}\+\\frac\{d\_\{\\mathrm\{N\}\}\}\{\\varepsilon^\{2\}\}\.This progress does not itself yield a transductive learner\. PAC proofs average over independent samples, while transductive guarantees must hold for every fixed population\. In particular, empirical minimization over a finite reconstructed family can have constant leave\-one\-out error even when the family has onlynnmembers\. This is the instability behind the open problem\.

We show that the two models nevertheless have the same multiclass rate, up to logarithmic factors\. Letϵℋtr​\(n\)\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)denote the optimal agnostic transductive excess error\. Our main theorem gives

c​min⁡\{1,dDSn\+dNn\}≤ϵℋtr​\(n\)≤C​min⁡\{1,dDS​log2⁡\(e​n\)n\+dN​log3⁡\(e​n\)n\}\.c\\min\\left\\\{1,\\frac\{d\_\{\\mathrm\{DS\}\}\}\{n\}\+\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\}\{n\}\}\\right\\\}\\leq\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)\\leq C\\min\\left\\\{1,\\frac\{d\_\{\\mathrm\{DS\}\}\\log^\{2\}\(en\)\}\{n\}\+\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\\log^\{3\}\(en\)\}\{n\}\}\\right\\\}\.The result permits an infinite or uncountable label space\.

The upper bound rests on a simple change in how the visible sample is used\. Given the hidden index, the learner chooses three disjoint random blocks from then−1n\-1visible examples and ignores all other visible labels\. Equivalently, the three blocks can be chosen first from the full population, after which the hidden index is uniform in their complement\. The ignored points turn the single hidden label into a uniformly random point of a large unseen block\. This permits finite\-population generalization without requiring leave\-one\-out stability\.

We then adapt the three\-stage label\-space reduction of[Cohen et al\. \(2026\)](https://arxiv.org/html/2608.25326#bib.bib10)\. The first block creates a finite cover using realizable compression\. The second runs multiplicative weights to reduce the pointwise label space\. The third performs inside\-menu agnostic compression\. Two standard compression arguments transfer to random splits\. The key new ingredient is a finite\-population multiplicative\-weights lemma\. Although the examples arrive without replacement, the expected number of rewards earned by sampled experts is constant because each expert can newly cover only a disjoint part of the population\. This preserves the1/n1/napproximation term\.

The lower bounds reveal why both dimensions remain necessary in the transductive model\. For the Natarajan term, repeat each shattered point and independently assign one of its two witness labels\. The hidden label is an independent fair bit, while the best hypothesis chooses each block majority after seeing the entire population\. For the DS term, orient the coordinate fibers of a pseudo\-cube\. Every orientation has average outdegree proportional to the pseudo\-cube dimension, even after the population is padded by repetitions\.

Our result answers the multiclass instance of the open question of[Dughmi et al\. \(2025\)](https://arxiv.org/html/2608.25326#bib.bib9)\. It is specific enough to exploit the structure of multiclass learning\. We do not give a black\-box PAC\-to\-transductive reduction for every bounded loss\. The random\-reservation argument may, however, be useful whenever a PAC construction factors through small reconstructed families\.

#### Contributions\.

1. 1\.We characterize agnostic multiclass transductive error up to logarithmic factors by separate DS and Natarajan terms, for arbitrary label spaces\.
2. 2\.We introduce a random\-reservation reduction that transfers a structured three\-stage PAC learner to every fixed finite population\.
3. 3\.We prove a without\-replacement multiplicative\-weights menu lemma with miss probabilityO⁡\(log⁡\|F\|/n\)O\(\\log\|F\|/n\)\.
4. 4\.We give direct transductive lower bounds from Natarajan cubes and DS pseudo\-cubes\.

## 2Setting and main result

LetXXbe an instance space, letYYbe an arbitrary label space, and letℋ⊆YX\\mathcal\{H\}\\subseteq Y^\{X\}be nonempty\. A labeled population isS=\(z1,…,zn\)∈\(X×Y\)nS=\(z\_\{1\},\\ldots,z\_\{n\}\)\\in\(X\\times Y\)^\{n\}, wherezi=\(xi,yi\)z\_\{i\}=\(x\_\{i\},y\_\{i\}\)\. Repeated instances and repeated labeled examples are allowed\. Write

LS\(h\)=1n∑i=1n𝟏\{h\(xi\)≠yi\}\.L\_\{S\}\(h\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{h\(x\_\{i\}\)\\neq y\_\{i\}\\\}\.
A randomized transductive learner receives the full instance sequencex1:nx\_\{1:n\}, an indexii, and the labeled sequenceS−iS\_\{\-i\}\. It outputs a label forxix\_\{i\}\. Its agnostic excess error onSSis

ℰS\(A\)=1n∑i=1nℙA\{A\(x1:n,S−i,i\)≠yi\}−minh∈ℋLS\(h\)\.\\mathcal\{E\}\_\{S\}\(A\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbb\{P\}\_\{A\}\\\{A\(x\_\{1:n\},S\_\{\-i\},i\)\\neq y\_\{i\}\\\}\-\\min\_\{h\\in\\mathcal\{H\}\}L\_\{S\}\(h\)\.\(1\)The optimal worst\-population error is

ϵℋtr​\(n\)=infAsupS∈\(X×Y\)nℰS​\(A\)\.\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)=\\inf\_\{A\}\\sup\_\{S\\in\(X\\times Y\)^\{n\}\}\\mathcal\{E\}\_\{S\}\(A\)\.This agrees with the agnostic transductive criterion of[Asilis et al\. \(2024\)](https://arxiv.org/html/2608.25326#bib.bib8)and[Dughmi et al\. \(2025\)](https://arxiv.org/html/2608.25326#bib.bib9)\.

We recall the two dimensions\. A sequencex1:dx\_\{1:d\}is Natarajan shattered if there are pairsaj≠bja\_\{j\}\\neq b\_\{j\}such thatℋ\|x1:d\\mathcal\{H\}\|\_\{x\_\{1:d\}\}contains every vector in∏j\{aj,bj\}\\prod\_\{j\}\\\{a\_\{j\},b\_\{j\}\\\}\. The largestddis the Natarajan dimensiondNd\_\{\\mathrm\{N\}\}\([Natarajan, 1989](https://arxiv.org/html/2608.25326#bib.bib3)\)\. A finite nonempty setF⊆YdF\\subseteq Y^\{d\}is add\-dimensional pseudo\-cube if everyf∈Ff\\in Fhas a neighbor differing only in coordinatejj, for everyj∈\[d\]j\\in\[d\]\. The largestddfor which a trace ofℋ\\mathcal\{H\}contains such a pseudo\-cube is the DS dimensiondDSd\_\{\\mathrm\{DS\}\}\([Daniely and Shalev\-Shwartz, 2014](https://arxiv.org/html/2608.25326#bib.bib5);[Brukhim et al\., 2022](https://arxiv.org/html/2608.25326#bib.bib7)\)\.

###### Theorem 1\(Two\-dimension transductive law\)\.

There are universal constantsc,C\>0c,C\>0such that every nonemptyℋ⊆YX\\mathcal\{H\}\\subseteq Y^\{X\}and everyn≥2n\\geq 2satisfy

ϵℋtr​\(n\)\\displaystyle\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)≥c​min⁡\{1,dDSn\+dNn\},\\displaystyle\\geq c\\min\\left\\\{1,\\frac\{d\_\{\\mathrm\{DS\}\}\}\{n\}\+\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\}\{n\}\}\\right\\\},\(2\)ϵℋtr​\(n\)\\displaystyle\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)≤C​min⁡\{1,dDS​log2⁡\(e​n\)n\+dN​log3⁡\(e​n\)n\}\.\\displaystyle\\leq C\\min\\left\\\{1,\\frac\{d\_\{\\mathrm\{DS\}\}\\log^\{2\}\(en\)\}\{n\}\+\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\\log^\{3\}\(en\)\}\{n\}\}\\right\\\}\.\(3\)The conventions are that the upper bound is vacuous whendDS=∞d\_\{\\mathrm\{DS\}\}=\\infty, and that a class of Natarajan dimension zero has zero transductive excess error\.

Definemℋtr​\(ε\)=min⁡\{n:supN≥nϵℋtr​\(N\)≤ε\}m^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(\\varepsilon\)=\\min\\\{n:\\sup\_\{N\\geq n\}\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(N\)\\leq\\varepsilon\\\}\. Inverting the rates gives the sample\-complexity form\.

###### Corollary 2\(PAC and transductive rates\)\.

Up to polylogarithmic factors,

mℋtr​\(ε\)=Θ~​\(dDSε\+dNε2\)\.m^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(\\varepsilon\)=\\widetilde\{\\Theta\}\\left\(\\frac\{d\_\{\\mathrm\{DS\}\}\}\{\\varepsilon\}\+\\frac\{d\_\{\\mathrm\{N\}\}\}\{\\varepsilon^\{2\}\}\\right\)\.This is the same two\-parameter law as agnostic PAC learning, obtained by combining[Cohen et al\. \(2026\)](https://arxiv.org/html/2608.25326#bib.bib10)and[Pabbaraju \(2026\)](https://arxiv.org/html/2608.25326#bib.bib11)\.

#### Why a generic ERM transfer fails\.

Suppose a learner trains an empirical minimizer over a finite family on then−1n\-1visible labels\. Even with one perfect comparator and onlynnadditional hypotheses, tie\-breaking can choose, for each held\-out indexii, a hypothesis that is correct everywhere except atii\. Its leave\-one\-out error is one\. A finite cardinality bound is useful only when the test point lies in a large block that was not used to choose the output\. Random reservation creates precisely this block\.

## 3Three finite\-population lemmas

We state the tools used by the upper bound\. All populations below are finite multisets of indexed examples\. Uniform samples are over indices, so duplicate values cause no ambiguity\.

### 3\.1Realizable compression cover

A deterministic selection scheme𝒜=\(κ,ρ\)\\mathcal\{A\}=\(\\kappa,\\rho\)of sizek⁡\(m\)k\(m\)selects an ordered tuple of at mostk⁡\(m\)k\(m\)input examples, with repetition allowed, and reconstructs a predictor from that tuple\. It is a realizable compression scheme if its reconstruction realizes every realizable input sequence\. Recent one\-inclusion and boosting results imply the following fact\.

For a lossℓ\\ell, anℓ\\ell\-sample compression scheme additionally requires its reconstruction on every input sequence to have empiricalℓ\\ell\-loss no larger than the empiricalℓ\\ell\-loss of any comparator inℋ\\mathcal\{H\}\. Thus empirical optimality is part of the guarantee, not an extra property of the reconstruction\.

###### Proposition 3\(Compression ingredients\)\.

Ifℋ\\mathcal\{H\}has finite DS dimensiondDSd\_\{\\mathrm\{DS\}\}, it admits a deterministic realizable compression scheme of size

k1​\(m\)≤C​dDS​log⁡\(e​m\)\.k\_\{1\}\(m\)\\leq Cd\_\{\\mathrm\{DS\}\}\\log\(em\)\.For every menuμ:X→2Y\\mu:X\\to 2^\{Y\}of size at mostpp,ℋ\\mathcal\{H\}admits a deterministic sample compression scheme for

ℓμ​\(g,\(x,y\)\)=𝟏​\{y∈μ⁡\(x\),g⁡\(x\)≠y\}\\ell\_\{\\mu\}\(g,\(x,y\)\)=\\mathbf\{1\}\\\{y\\in\\mu\(x\),\\ g\(x\)\\neq y\\\}of size

k2​\(m\)≤C​dN​log⁡\(e​p\)​log⁡\(e​m\)\.k\_\{2\}\(m\)\\leq Cd\_\{\\mathrm\{N\}\}\\log\(ep\)\\log\(em\)\.Both statements hold for arbitrary label spaces\.

The first statement combines the density theorem of[Pabbaraju \(2026\)](https://arxiv.org/html/2608.25326#bib.bib11)with the weak\-learning\-to\-compression construction of[David et al\. \(2016\)](https://arxiv.org/html/2608.25326#bib.bib6)\. The exact construction is also given by[Cohen et al\. \(2026, Corollary C\.2\)](https://arxiv.org/html/2608.25326#bib.bib10)\. The second statement is[Cohen et al\. \(2026, Proposition 3\.6\)](https://arxiv.org/html/2608.25326#bib.bib10)\. Appendix[A](https://arxiv.org/html/2608.25326#A1)records the reduction and the infinite\-label point\.

For a fixed comparatorhh, letA⁡\(h\)A\(h\)denote the examples inAAcorrectly labeled byhh\. Applying the first scheme toA⁡\(h\)A\(h\)produces a predictor that may disagree withhh, but not on any point ofAAwherehhis correct\.

###### Lemma 4\(Finite\-population compression cover\)\.

LetRRbe a fixed population of sizeNN, letAAbe a uniform size\-mmsubset withm≤N/2m\\leq N/2, and let𝒜=\(κ,ρ\)\\mathcal\{A\}=\(\\kappa,\\rho\)be a deterministic realizable compression scheme of size at mostkk\. For fixedhh, putfh,A=𝒜⁡\(A⁡\(h\)\)f\_\{h,A\}=\\mathcal\{A\}\(A\(h\)\)\. Then

𝔼A1N−m∑\(x,y\)∈R∖A𝟏\{h\(x\)=y≠fh,A\(x\)\}≤C\(k\+1\)​log⁡\(e​N\)m\.\\mathbb\{E\}\_\{A\}\\frac\{1\}\{N\-m\}\\sum\_\{\(x,y\)\\in R\\setminus A\}\\mathbf\{1\}\\\{h\(x\)=y\\neq f\_\{h,A\}\(x\)\\\}\\leq C\\frac\{\(k\+1\)\\log\(eN\)\}\{m\}\.

The proof is a compression union bound, but over the unseen finite population rather than a distribution\. Every possible output is reconstructed from one of at most\(k\+1\)​Nk\(k\+1\)N^\{k\}tuples\. If its bad fraction onR∖AR\\setminus Aisuu, the probability thatAAavoids all bad points is at moste−um/2e^\{\-um/2\}\. We give details in Appendix[B](https://arxiv.org/html/2608.25326#A2)\.

### 3\.2A without\-replacement menu lemma

LetF⊆YXF\\subseteq Y^\{X\}be finite and letZ1,…,ZTZ\_\{1\},\\ldots,Z\_\{T\}be a random ordered sample without replacement from a fixed populationRRof sizeNN\. Multiplicative weights starts with uniform weights\. Before seeingZt=\(Xt,Yt\)Z\_\{t\}=\(X\_\{t\},Y\_\{t\}\), it drawsftf\_\{t\}from the current distributionptp\_\{t\}\. It assigns everyf∈Ff\\in Freward

rt\(f\)=𝟏\{f\(Xt\)=Yt,fs\(Xt\)≠Ytfor alls<t\}r\_\{t\}\(f\)=\\mathbf\{1\}\\\{f\(X\_\{t\}\)=Y\_\{t\},\\ f\_\{s\}\(X\_\{t\}\)\\neq Y\_\{t\}\\text\{ for all \}s<t\\\}\(4\)and updates bywt\+1​\(f\)=wt​\(f\)​ert​\(f\)/2w\_\{t\+1\}\(f\)=w\_\{t\}\(f\)e^\{r\_\{t\}\(f\)/2\}\. Its final menu isμ⁡\(x\)=\{f1​\(x\),…,fT​\(x\)\}\\mu\(x\)=\\\{f\_\{1\}\(x\),\\ldots,f\_\{T\}\(x\)\\\}\.

###### Lemma 5\(Finite\-population MW menu\)\.

IfT≤N/2T\\leq N/2andU=R∖\{Z1,…,ZT\}U=R\\setminus\\\{Z\_\{1\},\\ldots,Z\_\{T\}\\\}, then everyf⋆∈Ff^\{\\star\}\\in Fsatisfies

𝔼​1\|U\|​∑\(x,y\)∈U𝟏​\{f⋆​\(x\)=y,y∉μ⁡\(x\)\}≤2​log⁡\|F\|\+3T\.\\mathbb\{E\}\\frac\{1\}\{\|U\|\}\\sum\_\{\(x,y\)\\in U\}\\mathbf\{1\}\\\{f^\{\\star\}\(x\)=y,\\ y\\notin\\mu\(x\)\\\}\\leq\\frac\{2\\log\|F\|\+3\}\{T\}\.

This is the main new technical lemma\. Its proof has two parts\. First, the expected reward off⋆f^\{\\star\}at every round upper bounds its final unseen miss rate\. This follows from exchangeability of the remaining permutation and monotonicity as the menu grows\. Second, the expected cumulative reward of the sampled experts is at most two\. To see this, defineDt⊆RD\_\{t\}\\subseteq Ras the points newly covered byftf\_\{t\}\. The setsDtD\_\{t\}are disjoint\. Conditional on the past andftf\_\{t\}, the reward probability is at most\|Dt\|/\(N−T\+1\)\|D\_\{t\}\|/\(N\-T\+1\)\. Summing gives at mostN/\(N−T\+1\)≤2N/\(N\-T\+1\)\\leq 2\. The multiplicative\-weights regret inequality completes the proof\. Appendix[C](https://arxiv.org/html/2608.25326#A3)is formal\.

### 3\.3Agnostic compression across a split

The final tool converts empirical optimality on one random block into excess control on another\.

###### Lemma 6\(Random\-split agnostic compression\)\.

Let a fixed populationRRof sizeNNbe split uniformly intoCCandVV, where\|C\|,\|V\|≥N/3\|C\|,\|V\|\\geq N/3\. Letℓ∈\[0,1\]\\ell\\in\[0,1\], and let a deterministicℓ\\ell\-sample compression scheme of size at mostkkoutputh^\\widehat\{h\}onCC\. Then every fixed comparatorhhin the benchmark class satisfies

𝔼⁡\[LVℓ​\(h^\)−LVℓ​\(h\)\]≤C​\(k\+1\)​log⁡\(e​N\)N\.\\mathbb\{E\}\\big\[L\_\{V\}^\{\\ell\}\(\\widehat\{h\}\)\-L\_\{V\}^\{\\ell\}\(h\)\\big\]\\leq C\\sqrt\{\\frac\{\(k\+1\)\\log\(eN\)\}\{N\}\}\.

Conditional onRR, every possible output lies in a family of size at most\(k\+1\)​Nk\(k\+1\)N^\{k\}\. Hoeffding’s comparison theorem for sampling without replacement\([Hoeffding, 1963](https://arxiv.org/html/2608.25326#bib.bib1);[Serfling, 1974](https://arxiv.org/html/2608.25326#bib.bib2)\)and a union bound control the difference between its losses onCCandVV\. Empirical optimality onCCthen gives the result\. Appendix[E](https://arxiv.org/html/2608.25326#A5)includes the calculation\.

## 4The transductive learner

Fornnbelow a universal constant, use an arbitrary predictor and enlarge the universal constant in Theorem[1](https://arxiv.org/html/2608.25326#Thmtheorem1)\. Henceforth fix a populationSSof sufficiently large sizenn, and letIIbe the uniform hidden index\. Putq=⌊n/4⌋q=\\lfloor n/4\\rfloor\. From the visible indices\[n\]∖\{I\}\[n\]\\setminus\\\{I\\\}, choose disjoint blocksA,B,CA,B,C, each of sizeqq, uniformly in sequence\. Give every block an independent uniform order\. The learner ignores every visible label outside these blocks\.

The joint distribution has an equivalent deferred\-decision form:

A,B,C​are chosen first from​S,V=S∖\(A∪B∪C\),I∼Unif⁡\(V\)\.A,B,C\\text\{ are chosen first from \}S,\\qquad V=S\\setminus\(A\\cup B\\cup C\),\\qquad I\\sim\\operatorname\{Unif\}\(V\)\.\(5\)Both orders assign the same probability to every disjoint tuple\(A,B,C,I\)\(A,B,C,I\)\. Thus the expected test loss conditional on\(A,B,C\)\(A,B,C\)is exactlyLV​\(h^\)L\_\{V\}\(\\widehat\{h\}\)\.

The learner uses Proposition[3](https://arxiv.org/html/2608.25326#Thmtheorem3)in three stages\.

#### Stage 1: finite cover\.

Let\(κ1,ρ1\)\(\\kappa\_\{1\},\\rho\_\{1\}\)be the realizable compression scheme\. Construct

FA=\{ρ1​\(t\):t∈⋃j=0k1​\(q\)Aj\}\.F\_\{A\}=\\left\\\{\\rho\_\{1\}\(t\):t\\in\\bigcup\_\{j=0\}^\{k\_\{1\}\(q\)\}A^\{j\}\\right\\\}\.Then\|FA\|≤\(q\+1\)k1​\(q\)\+1\|F\_\{A\}\|\\leq\(q\+1\)^\{k\_\{1\}\(q\)\+1\}\. For everyh∈ℋh\\in\\mathcal\{H\}, the reconstructionfh,A=𝒜1​\(A⁡\(h\)\)f\_\{h,A\}=\\mathcal\{A\}\_\{1\}\(A\(h\)\)belongs toFAF\_\{A\}\.

#### Stage 2: label\-space reduction\.

Run the procedure of Lemma[5](https://arxiv.org/html/2608.25326#Thmtheorem5)on the ordered blockBB, with expert setFAF\_\{A\}andT=qT=q\. This produces a menuμ\\muof size at mostqq\.

#### Stage 3: inside\-menu learning\.

Run the inside\-menu compression scheme onCCand output its reconstructed classifierh^\\widehat\{h\}\. Predicth^​\(xI\)\\widehat\{h\}\(x\_\{I\}\)\.

The algorithm is information valid\. It selectsA,B,CA,B,Cfrom visible examples and never uses labels inVV, even when they are available\.

###### Proof of the upper bound in Theorem[1](https://arxiv.org/html/2608.25326#Thmtheorem1)\.

The result is trivial whendN=0d\_\{\\mathrm\{N\}\}=0, so assumedN≥1d\_\{\\mathrm\{N\}\}\\geq 1\. Fix

h⋆∈arg⁡minh∈ℋ​LS​\(h\)\.h^\{\\star\}\\in\\arg\\min\_\{h\\in\\mathcal\{H\}\}L\_\{S\}\(h\)\.An empirical minimizer exists because the possible empirical errors lie in\{0,1/n,…,1\}\\\{0,1/n,\\ldots,1\\\}\.

Lemma[4](https://arxiv.org/html/2608.25326#Thmtheorem4), followed by random subdivision ofS∖AS\\setminus A, gives

𝔼LV\(𝟏\{h⋆\(x\)=y≠fh⋆,A\(x\)\}\)≤CdDS​log2⁡\(e​n\)n\.\\mathbb\{E\}L\_\{V\}\\big\(\\mathbf\{1\}\\\{h^\{\\star\}\(x\)=y\\neq f\_\{h^\{\\star\},A\}\(x\)\\\}\\big\)\\leq C\\frac\{d\_\{\\mathrm\{DS\}\}\\log^\{2\}\(en\)\}\{n\}\.\(6\)Conditional onAA, Lemma[5](https://arxiv.org/html/2608.25326#Thmtheorem5)applies to the remaining population becauseq≤\(n−q\)/2q\\leq\(n\-q\)/2\. Since

log⁡\|FA\|≤C​dDS​log2⁡\(e​n\),\\log\|F\_\{A\}\|\\leq Cd\_\{\\mathrm\{DS\}\}\\log^\{2\}\(en\),another subdivision step gives

𝔼​LV​\(𝟏​\{fh⋆,A​\(x\)=y,y∉μ⁡\(x\)\}\)≤C​dDS​log2⁡\(e​n\)n\.\\mathbb\{E\}L\_\{V\}\\big\(\\mathbf\{1\}\\\{f\_\{h^\{\\star\},A\}\(x\)=y,\\ y\\notin\\mu\(x\)\\\}\\big\)\\leq C\\frac\{d\_\{\\mathrm\{DS\}\}\\log^\{2\}\(en\)\}\{n\}\.\(7\)
Conditional on\(A,B,μ\)\(A,B,\\mu\), the blocksC,VC,Vform a uniform split of the remaining population, with both sizes at least one third of it\. The inside\-menu scheme has size

k2​\(q\)≤C​dN​log2⁡\(e​n\)\.k\_\{2\}\(q\)\\leq Cd\_\{\\mathrm\{N\}\}\\log^\{2\}\(en\)\.Lemma[6](https://arxiv.org/html/2608.25326#Thmtheorem6)yields

𝔼⁡\[LVμ​\(h^\)−LVμ​\(h⋆\)\]≤C​dN​log3⁡\(e​n\)n\.\\mathbb\{E\}\\left\[L\_\{V\}^\{\\mu\}\(\\widehat\{h\}\)\-L\_\{V\}^\{\\mu\}\(h^\{\\star\}\)\\right\]\\leq C\\sqrt\{\\frac\{d\_\{\\mathrm\{N\}\}\\log^\{3\}\(en\)\}\{n\}\}\.\(8\)
For every fixed menu and population,

LV​\(h^\)−LV​\(h⋆\)≤\\displaystyle L\_\{V\}\(\\widehat\{h\}\)\-L\_\{V\}\(h^\{\\star\}\)\\leq\{\}LVμ​\(h^\)−LVμ​\(h⋆\)\\displaystyle L\_\{V\}^\{\\mu\}\(\\widehat\{h\}\)\-L\_\{V\}^\{\\mu\}\(h^\{\\star\}\)\+LV​\(𝟏​\{h⋆​\(x\)=y,y∉μ⁡\(x\)\}\)\.\\displaystyle\+L\_\{V\}\\big\(\\mathbf\{1\}\\\{h^\{\\star\}\(x\)=y,\\ y\\notin\\mu\(x\)\\\}\\big\)\.\(9\)The final miss event is contained in the union of the events in \([6](https://arxiv.org/html/2608.25326#S4.E6)\) and \([7](https://arxiv.org/html/2608.25326#S4.E7)\)\. Combining the displays gives the right side of \([3](https://arxiv.org/html/2608.25326#S2.E3)\) without the cap at one\.

Finally, \([5](https://arxiv.org/html/2608.25326#S4.E5)\) makes the expected test loss equal to𝔼​LV​\(h^\)\\mathbb\{E\}L\_\{V\}\(\\widehat\{h\}\)\. The setVVis a uniform subset ofSS, so𝔼​LV​\(h⋆\)=LS​\(h⋆\)\\mathbb\{E\}L\_\{V\}\(h^\{\\star\}\)=L\_\{S\}\(h^\{\\star\}\)\. The trivial upper bound one supplies the cap\. ∎

## 5Matching lower bounds

We prove the two terms separately\. Since their maximum is at least half their sum, this proves \([2](https://arxiv.org/html/2608.25326#S2.E2)\)\.

### 5\.1The Natarajan obstruction

Letd=min⁡\{dN,n\}d=\\min\\\{d\_\{\\mathrm\{N\}\},n\\\}, and take Natarajan\-shattered pointsx1,…,xdx\_\{1\},\\ldots,x\_\{d\}with witness labelsaj≠bja\_\{j\}\\neq b\_\{j\}\. Partition thennpositions into nonempty blocks of sizeskj∈\{⌊n/d⌋,⌈n/d⌉\}k\_\{j\}\\in\\\{\\lfloor n/d\\rfloor,\\lceil n/d\\rceil\\\}\. Every position in blockjjhas featurexjx\_\{j\}\. Label its copies independently and uniformly from\{aj,bj\}\\\{a\_\{j\},b\_\{j\}\\\}\.

Conditional on every visible label, the hidden label remains a fair independent bit\. Every learner therefore has expected error at least1/21/2\. IfBj∼Bin⁡\(kj,1/2\)B\_\{j\}\\sim\\operatorname\{Bin\}\(k\_\{j\},1/2\), the best hypothesis makesmin⁡\{Bj,kj−Bj\}\\min\\\{B\_\{j\},k\_\{j\}\-B\_\{j\}\\\}errors in blockjj\. Natarajan shattering realizes all blockwise majority choices\. A hypothesis using a third label onxjx\_\{j\}is dominated by one of these choices\. Hence the expected excess is at least

12​n​∑j=1d𝔼​\|2​Bj−kj\|\.\\frac\{1\}\{2n\}\\sum\_\{j=1\}^\{d\}\\mathbb\{E\}\|2B\_\{j\}\-k\_\{j\}\|\.Khinchine’s inequality gives𝔼​\|2​Bj−kj\|≥kj/2\\mathbb\{E\}\|2B\_\{j\}\-k\_\{j\}\|\\geq\\sqrt\{k\_\{j\}/2\}\. Sincekj≥n/\(2​d\)k\_\{j\}\\geq n/\(2d\), the excess is at leastc​d/nc\\sqrt\{d/n\}\. The probabilistic method fixes one deterministic labeling with at least this error\.

### 5\.2The pseudo\-cube obstruction

Letd=min⁡\{dDS,n\}d=\\min\\\{d\_\{\\mathrm\{DS\}\},n\\\}\. Project a DS witness onto anyddwitness coordinates\. After duplicate vertices are removed, the projection is still a pseudo\-cube\. Ford≥2d\\geq 2, put one sample copy at eachx2,…,xdx\_\{2\},\\ldots,x\_\{d\}, and use every remaining position as a copy ofx1x\_\{1\}\. Label the population by a vertex of the pseudo\-cube, making it realizable\.

Fix a possibly randomized learner\. For every directioni≥2i\\geq 2, vertices that agree outside coordinateiiform a nontrivial fiberee\. Whenxix\_\{i\}is hidden, all vertices ineegive the learner exactly the same observation\. Their labels atxix\_\{i\}are distinct\. Consequently, the sum of their error probabilities is at least\|e\|−1\|e\|\-1\. Summing over all fibers,

∑e\(\|e\|−1\)≥12​∑e\|e\|=\|F\|​\(d−1\)2,\\sum\_\{e\}\(\|e\|\-1\)\\geq\\frac\{1\}\{2\}\\sum\_\{e\}\|e\|=\\frac\{\|F\|\(d\-1\)\}\{2\},whereFFis the pseudo\-cube\. Some realizable vertex causes at least\(d−1\)/2\(d\-1\)/2errors across thennpossible hidden positions\. Thus

ϵℋtr​\(n\)≥d−12​n\.\\epsilon^\{\\mathrm\{tr\}\}\_\{\\mathcal\{H\}\}\(n\)\\geq\\frac\{d\-1\}\{2n\}\.Ford=1d=1, the Natarajan obstruction already dominates the desired1/n1/nterm\. Appendix[G](https://arxiv.org/html/2608.25326#A7)gives the projection and randomized\-orientation details\.

## 6Related work and discussion

#### Agnostic one\-inclusion graphs\.

[Asilis et al\. \(2024\)](https://arxiv.org/html/2608.25326#bib.bib8)formulate multiclass agnostic transduction as orienting a Hamming hypergraph with vertex credits equal to distance fromℋ\\mathcal\{H\}\. Their agnostic Hall complexity exactly characterizes optimal transductive error, but it is not bounded there by statistical dimensions\.[Dughmi et al\. \(2025\)](https://arxiv.org/html/2608.25326#bib.bib9)solve the binary case by showing that symmetrization enlarges discounted density until the full Boolean cube is reached, then invoke Rademacher complexity\. That symmetrization is specific to two labels\. Our proof instead constructs a transductive learner and exposes the separate DS and Natarajan roles\.

#### Agnostic multiclass PAC learning\.

[Cohen et al\. \(2026\)](https://arxiv.org/html/2608.25326#bib.bib10)introduce the three\-stage cover, multiplicative\-weights, and inside\-menu architecture\. Their bound is expressed through the optimal constant\-error realizable complexity\.[Pabbaraju \(2026\)](https://arxiv.org/html/2608.25326#bib.bib11)prove that one\-inclusion density is at most DS dimension, closing the realizable gap and yielding the two\-dimension PAC rate\. Our random\-reservation analysis transfers this architecture to a fixed population\. The finite\-population menu lemma is essential for retaining the fast DS term\.

#### Other transductive models\.

Multiclass transductive online learning reveals the full instance sequence and then predicts many labels sequentially\. Its rates are governed by level\-constrained Littlestone\-type dimensions\([Hanneke et al\., 2024](https://arxiv.org/html/2608.25326#bib.bib14);[Hanneke and Wang, 2026](https://arxiv.org/html/2608.25326#bib.bib15)\)\. This differs from the batch leave\-one\-out model studied here\. Recent work separates local regularizers from general multiclass transductive learners\([Jafar et al\., 2025](https://arxiv.org/html/2608.25326#bib.bib12)\), and a subsequent construction gives the corresponding separation for fixed local scores in PAC learning\([Hou, 2026](https://arxiv.org/html/2608.25326#bib.bib13)\)\. Our learner is highly improper and does not contradict either separation\.

#### Limitations and open questions\.

The logarithmic gap comes from boosting weak learners into compression, enumerating reconstructed families, and inside\-menu compression\. Removing it may require a direct weighted orientation of the multiclass agnostic Hamming hypergraph\. Our result is information\-theoretic\. Like the underlying one\-inclusion and compression constructions, it need not be computationally efficient\. It also does not provide a black\-box reduction for arbitrary bounded losses\.

## 7Conclusion

Agnostic multiclass transduction has the same two statistical scales as agnostic PAC learning\. DS dimension controls the fast approximation term, while Natarajan dimension controls the square\-root estimation term\. Randomly reserving a large unseen block turns structured compression arguments into finite\-population guarantees and bypasses the instability of direct leave\-one\-out transfer\. This closes the PAC versus transductive question for multiclass classification up to logarithmic factors, including for unbounded label spaces\.

### Reproducibility statement

The setting, learner, and assumptions are specified in Sections[2](https://arxiv.org/html/2608.25326#S2)–[4](https://arxiv.org/html/2608.25326#S4)\. Complete proofs of every stated lemma and theorem are included after the references, including exact partition bookkeeping and randomized lower\-bound quantifiers\.

## References

- Asiliset al\.\(2024\)J\. Asilis, S\. Devic, S\. Dughmi, V\. Sharan, and S\. TengRegularization and optimal multiclass learning\.InProceedings of the 37th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.247,pp\. 260–310\.Cited by:[§1](https://arxiv.org/html/2608.25326#S1.p2.1),[§2](https://arxiv.org/html/2608.25326#S2.p2.3),[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px1.p1.1)\.
- 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,pp\. 943–955\.Cited by:[§1](https://arxiv.org/html/2608.25326#S1.p3.1),[§2](https://arxiv.org/html/2608.25326#S2.p3.1)\.
- Cohenet al\.\(2026\)A\. Cohen, L\. Erez, S\. Hanneke, T\. Koren, Y\. Mansour, S\. Moran, and Q\. ZhangSample complexity of agnostic multiclass classification: Natarajan dimension strikes back\.InProceedings of the 58th Annual ACM Symposium on Theory of Computing,pp\. 722–733\.External Links:[Document](https://dx.doi.org/10.1145/3798129.3800787),2511\.12659Cited by:[§A\.1](https://arxiv.org/html/2608.25326#A1.SS1.p2.1),[§A\.2](https://arxiv.org/html/2608.25326#A1.SS2.p1.2),[§1](https://arxiv.org/html/2608.25326#S1.p3.1),[§1](https://arxiv.org/html/2608.25326#S1.p6.1),[§3\.1](https://arxiv.org/html/2608.25326#S3.SS1.p3.1),[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px2.p1.1),[Corollary 2](https://arxiv.org/html/2608.25326#Thmtheorem2.p1.2.1)\.
- Daniely and Shalev\-Shwartz \(2014\)A\. Daniely and S\. Shalev\-ShwartzOptimal learners for multiclass problems\.InProceedings of the 27th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.35,pp\. 287–316\.Cited by:[§1](https://arxiv.org/html/2608.25326#S1.p2.1),[§1](https://arxiv.org/html/2608.25326#S1.p3.1),[§2](https://arxiv.org/html/2608.25326#S2.p3.1)\.
- Davidet al\.\(2016\)O\. David, S\. Moran, and A\. YehudayoffSupervised learning through the lens of compression\.InAdvances in Neural Information Processing Systems,Vol\.29\.Cited by:[§A\.1](https://arxiv.org/html/2608.25326#A1.SS1.p2.1),[§3\.1](https://arxiv.org/html/2608.25326#S3.SS1.p3.1)\.
- Dughmiet al\.\(2025\)S\. Dughmi, Y\. H\. Kalayci, and G\. YorkIs transductive learning equivalent to PAC learning?\.InProceedings of the 36th International Conference on Algorithmic Learning Theory,Proceedings of Machine Learning Research, Vol\.272,pp\. 418–443\.External Links:2405\.05190Cited by:[§1](https://arxiv.org/html/2608.25326#S1.p2.1),[§1](https://arxiv.org/html/2608.25326#S1.p8.1),[§2](https://arxiv.org/html/2608.25326#S2.p2.3),[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px1.p1.1)\.
- Hannekeet al\.\(2024\)S\. Hanneke, V\. Raman, A\. Shaeiri, and U\. SubediMulticlass transductive online learning\.InAdvances in Neural Information Processing Systems,Vol\.37\.External Links:2411\.01634Cited by:[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px3.p1.1)\.
- Hanneke and Wang \(2026\)S\. Hanneke and H\. WangUniversal multiclass transductive online learning\.arXiv preprint arXiv:2605\.30479\.Cited by:[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px3.p1.1)\.
- Haussleret al\.\(1994\)D\. Haussler, N\. Littlestone, and M\. K\. WarmuthPredicting \{0,1\}\-functions on randomly drawn points\.Information and Computation115\(2\),pp\. 248–292\.Cited by:[§1](https://arxiv.org/html/2608.25326#S1.p2.1)\.
- Hoeffding \(1963\)W\. HoeffdingProbability inequalities for sums of bounded random variables\.Journal of the American Statistical Association58\(301\),pp\. 13–30\.Cited by:[§3\.3](https://arxiv.org/html/2608.25326#S3.SS3.p2.1)\.
- Hou \(2026\)E\. HouLocal regularization does not characterize multiclass PAC learnability\.arXiv preprint arXiv:2607\.23449\.Cited by:[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px3.p1.1)\.
- Jafaret al\.\(2025\)S\. Jafar, J\. Asilis, and S\. DughmiLocal regularizers are not transductive learners\.InProceedings of the 38th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.291,pp\. 2942–2957\.Cited by:[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px3.p1.1)\.
- Natarajan \(1989\)B\. K\. NatarajanOn learning sets and functions\.Machine Learning4\(1\),pp\. 67–97\.Cited by:[§2](https://arxiv.org/html/2608.25326#S2.p3.1)\.
- Pabbaraju \(2026\)C\. PabbarajuThe optimal sample complexity of multiclass and list learning\.arXiv preprint arXiv:2604\.24749\.Cited by:[§A\.1](https://arxiv.org/html/2608.25326#A1.SS1.p1.1),[§1](https://arxiv.org/html/2608.25326#S1.p3.1),[§3\.1](https://arxiv.org/html/2608.25326#S3.SS1.p3.1),[§6](https://arxiv.org/html/2608.25326#S6.SS0.SSS0.Px2.p1.1),[Corollary 2](https://arxiv.org/html/2608.25326#Thmtheorem2.p1.2.1)\.
- Serfling \(1974\)R\. J\. SerflingProbability inequalities for the sum in sampling without replacement\.The Annals of Statistics2\(1\),pp\. 39–48\.Cited by:[§3\.3](https://arxiv.org/html/2608.25326#S3.SS3.p2.1)\.

## Appendix ACompression ingredients

We give a self\-contained derivation of the consequences collected in Proposition[3](https://arxiv.org/html/2608.25326#Thmtheorem3)\.

### A\.1Realizable compression from DS dimension

IfdDS=0d\_\{\\mathrm\{DS\}\}=0, every hypothesis has the same pointwise behavior and compression size zero suffices\. AssumedDS≥1d\_\{\\mathrm\{DS\}\}\\geq 1\. The density theorem of[Pabbaraju \(2026, Theorem 1\)](https://arxiv.org/html/2608.25326#bib.bib11)and the standard one\-inclusion orientation construction give the deterministic realizable learner in their Corollary 1\.1\. Form0≤C​dDSm\_\{0\}\\leq Cd\_\{\\mathrm\{DS\}\}training examples, run that learner with target error and failure probability both1/61/6\. For every realizable distributionPP, its bounded loss then satisfies

𝔼T∼Pm0​errP⁡\(A0​\(T\)\)≤16\+16=13\.\\mathbb\{E\}\_\{T\\sim P^\{m\_\{0\}\}\}\\operatorname\{err\}\_\{P\}\(A\_\{0\}\(T\)\)\\leq\\frac\{1\}\{6\}\+\\frac\{1\}\{6\}=\\frac\{1\}\{3\}\.The density statement extends to infinite label spaces by their Remark 2, and the learner extends by the compactness argument in their Remark 4\. ThusA0A\_\{0\}is a deterministic constant\-error weak learner usingO⁡\(dDS\)O\(d\_\{\\mathrm\{DS\}\}\)examples for every label space\.

The minimax and boosting construction of[David et al\. \(2016\)](https://arxiv.org/html/2608.25326#bib.bib6), stated explicitly as[Cohen et al\. \(2026, Corollary C\.2\)](https://arxiv.org/html/2608.25326#bib.bib10), converts a deterministic weak learner usingO⁡\(dDS\)O\(d\_\{\\mathrm\{DS\}\}\)examples into a realizable compression scheme of sizeO⁡\(dDS​log⁡\(e​n\)\)O\(d\_\{\\mathrm\{DS\}\}\\log\(en\)\)on sequences of length at mostnn\. Its compression tuple may repeat input examples, which is why our counting arguments useNkN^\{k\}rather than binomial coefficients\.

### A\.2Inside\-menu compression

Fix a menuμ:X→2Y\\mu:X\\to 2^\{Y\}of sizepp\. Forh∈ℋh\\in\\mathcal\{H\}, define a partial hypothesis that equalsh⁡\(x\)h\(x\)whenh⁡\(x\)∈μ⁡\(x\)h\(x\)\\in\\mu\(x\)and is undefined otherwise\. On every finite support, this partial class has Natarajan dimension at mostdNd\_\{\\mathrm\{N\}\}and at mostppactive labels per point\. Its one\-inclusion learner has leave\-one\-out errorO⁡\(dN​log⁡\(e​p\)/m\)O\(d\_\{\\mathrm\{N\}\}\\log\(ep\)/m\)\. Applying the same weak\-learning\-to\-compression construction gives anℓμ\\ell\_\{\\mu\}\-sample compression scheme of size

O⁡\(dN​log⁡\(e​p\)​log⁡\(e​m\)\)\.O\(d\_\{\\mathrm\{N\}\}\\log\(ep\)\\log\(em\)\)\.This is the construction and proof of[Cohen et al\. \(2026, Proposition 3\.6\)](https://arxiv.org/html/2608.25326#bib.bib10)\. The reconstruction depends only on the selected tuple,ℋ\\mathcal\{H\}, andμ\\mu\. It uses no additional side information\. Whenp=1p=1, the unique menu label has zero inside\-menu loss and no examples are needed\.

## Appendix BProof of the finite\-population compression cover

###### Proof of Lemma[4](https://arxiv.org/html/2608.25326#Thmtheorem4)\.

Every possible reconstruction has the formρ⁡\(t\)\\rho\(t\), wherettis an ordered tuple of elements ofRRof length at mostkk\. Repetition is allowed\. There are at most

M=∑j=0kNj≤\(k\+1\)​NkM=\\sum\_\{j=0\}^\{k\}N^\{j\}\\leq\(k\+1\)N^\{k\}such tuples\.

Fix one tuplett, putf=ρ⁡\(t\)f=\\rho\(t\), and define the indexed bad set

Dt=\{\(x,y\)∈R:h⁡\(x\)=y≠f⁡\(x\)\}\.D\_\{t\}=\\\{\(x,y\)\\in R:h\(x\)=y\\neq f\(x\)\\\}\.Iff=fh,Af=f\_\{h,A\}, thenA∩Dt=∅A\\cap D\_\{t\}=\\varnothing, becausefh,Af\_\{h,A\}realizesA⁡\(h\)A\(h\)\. If\|Dt\|/\(N−m\)\>u\|D\_\{t\}\|/\(N\-m\)\>u, sampling without replacement gives

ℙ⁡\(A∩Dt=∅\)\\displaystyle\\mathbb\{P\}\(A\\cap D\_\{t\}=\\varnothing\)=\(N−\|Dt\|m\)\(Nm\)\\displaystyle=\\frac\{\\binom\{N\-\|D\_\{t\}\|\}\{m\}\}\{\\binom\{N\}\{m\}\}≤\(1−\|Dt\|N\)m\\displaystyle\\leq\\left\(1\-\\frac\{\|D\_\{t\}\|\}\{N\}\\right\)^\{m\}≤exp\(−u\(N−m\)​mN\)≤e−um/2\.\\displaystyle\\leq\\exp\\left\(\-u\\frac\{\(N\-m\)m\}\{N\}\\right\)\\leq e^\{\-um/2\}\.A union bound yields

ℙ\(\|Dκ⁡\(A⁡\(h\)\)\|N−m\>u\)≤min\{1,Me−um/2\}\.\\mathbb\{P\}\\left\(\\frac\{\|D\_\{\\kappa\(A\(h\)\)\}\|\}\{N\-m\}\>u\\right\)\\leq\\min\\\{1,Me^\{\-um/2\}\\\}\.Integrating overu∈\[0,1\]u\\in\[0,1\],

𝔼​\|Dκ⁡\(A⁡\(h\)\)\|N−m≤2​\(log⁡M\+1\)m≤C​\(k\+1\)​log⁡\(e​N\)m\.\\mathbb\{E\}\\frac\{\|D\_\{\\kappa\(A\(h\)\)\}\|\}\{N\-m\}\\leq\\frac\{2\(\\log M\+1\)\}\{m\}\\leq C\\frac\{\(k\+1\)\\log\(eN\)\}\{m\}\.∎

## Appendix CProof of the finite\-population MW lemma

###### Proof of Lemma[5](https://arxiv.org/html/2608.25326#Thmtheorem5)\.

LetRt=R∖\{Z1,…,Zt−1\}R\_\{t\}=R\\setminus\\\{Z\_\{1\},\\ldots,Z\_\{t\-1\}\\\}\. For a fixed benchmarkf⋆f^\{\\star\}, define

Qt\(x,y\)=𝟏\{f⋆\(x\)=y,fs\(x\)≠yfor alls<t\}\.Q\_\{t\}\(x,y\)=\\mathbf\{1\}\\\{f^\{\\star\}\(x\)=y,\\ f\_\{s\}\(x\)\\neq y\\text\{ for all \}s<t\\\}\.Conditional on the history before roundtt,ZtZ\_\{t\}is uniform inRtR\_\{t\}, so

𝔼⁡\[rt​\(f⋆\)∣ℱt−1\]=1\|Rt\|​∑z∈RtQt​\(z\)\.\\mathbb\{E\}\[r\_\{t\}\(f^\{\\star\}\)\\mid\\mathcal\{F\}\_\{t\-1\}\]=\\frac\{1\}\{\|R\_\{t\}\|\}\\sum\_\{z\\in R\_\{t\}\}Q\_\{t\}\(z\)\.The final unseen setUUis a uniform size\-\(N−T\)\(N\-T\)subset ofRtR\_\{t\}, conditional on the same history\. AlsoQT\+1​\(z\)≤Qt​\(z\)Q\_\{T\+1\}\(z\)\\leq Q\_\{t\}\(z\)for everyz∈Uz\\in U\. Therefore

𝔼​rt​\(f⋆\)≥𝔼​1\|U\|​∑z∈UQT\+1​\(z\)\.\\mathbb\{E\}r\_\{t\}\(f^\{\\star\}\)\\geq\\mathbb\{E\}\\frac\{1\}\{\|U\|\}\\sum\_\{z\\in U\}Q\_\{T\+1\}\(z\)\.Summing overttlower bounds𝔼​∑trt​\(f⋆\)\\mathbb\{E\}\\sum\_\{t\}r\_\{t\}\(f^\{\\star\}\)byTTtimes the desired final miss rate\.

The multiplicative\-weights regret inequality at learning rate1/21/2is

∑t=1T⟨pt,rt⟩≥23​∑t=1Trt​\(f⋆\)−43​log⁡\|F\|\.\\sum\_\{t=1\}^\{T\}\\langle p\_\{t\},r\_\{t\}\\rangle\\geq\\frac\{2\}\{3\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(f^\{\\star\}\)\-\\frac\{4\}\{3\}\\log\|F\|\.\(10\)For completeness, letWt=∑f∈Fwt​\(f\)W\_\{t\}=\\sum\_\{f\\in F\}w\_\{t\}\(f\)\. For0≤u≤10\\leq u\\leq 1and0<η≤10<\\eta\\leq 1,

eη​u≤1\+η​u\+η2​u2≤1\+η⁡\(1\+η\)​u\.e^\{\\eta u\}\\leq 1\+\\eta u\+\\eta^\{2\}u^\{2\}\\leq 1\+\\eta\(1\+\\eta\)u\.Consequently,

log⁡WT\+1W1≤η⁡\(1\+η\)​∑t=1T⟨pt,rt⟩,log⁡WT\+1W1≥η​∑t=1Trt​\(f⋆\)−log⁡\|F\|\.\\log\\frac\{W\_\{T\+1\}\}\{W\_\{1\}\}\\leq\\eta\(1\+\\eta\)\\sum\_\{t=1\}^\{T\}\\langle p\_\{t\},r\_\{t\}\\rangle,\\qquad\\log\\frac\{W\_\{T\+1\}\}\{W\_\{1\}\}\\geq\\eta\\sum\_\{t=1\}^\{T\}r\_\{t\}\(f^\{\\star\}\)\-\\log\|F\|\.Takingη=1/2\\eta=1/2gives \([10](https://arxiv.org/html/2608.25326#A3.E10)\)\.

It remains to bound the left side\. BeforeZtZ\_\{t\}is exposed, define

Dt=\{\(x,y\)∈R:ft\(x\)=y,fs\(x\)≠yfor alls<t\}\.D\_\{t\}=\\\{\(x,y\)\\in R:f\_\{t\}\(x\)=y,\\ f\_\{s\}\(x\)\\neq y\\text\{ for all \}s<t\\\}\.The setsD1,…,DTD\_\{1\},\\ldots,D\_\{T\}are pairwise disjoint on every path\. Conditional on the past and onftf\_\{t\},

𝔼\[rt\(ft\)∣ℱt−1,ft\]=\|Dt∩Rt\|\|Rt\|≤\|Dt\|N−T\+1\.\\mathbb\{E\}\[r\_\{t\}\(f\_\{t\}\)\\mid\\mathcal\{F\}\_\{t\-1\},f\_\{t\}\]=\\frac\{\|D\_\{t\}\\cap R\_\{t\}\|\}\{\|R\_\{t\}\|\}\\leq\\frac\{\|D\_\{t\}\|\}\{N\-T\+1\}\.Sinceft∼ptf\_\{t\}\\sim p\_\{t\}beforeZtZ\_\{t\}is revealed,

𝔼​∑t=1T⟨pt,rt⟩=𝔼​∑t=1Trt​\(ft\)≤𝔼​∑t\|Dt\|N−T\+1≤NN−T\+1≤2\.\\mathbb\{E\}\\sum\_\{t=1\}^\{T\}\\langle p\_\{t\},r\_\{t\}\\rangle=\\mathbb\{E\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(f\_\{t\}\)\\leq\\frac\{\\mathbb\{E\}\\sum\_\{t\}\|D\_\{t\}\|\}\{N\-T\+1\}\\leq\\frac\{N\}\{N\-T\+1\}\\leq 2\.Rearranging \([10](https://arxiv.org/html/2608.25326#A3.E10)\) gives

𝔼​∑t=1Trt​\(f⋆\)≤3\+2​log⁡\|F\|\.\\mathbb\{E\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(f^\{\\star\}\)\\leq 3\+2\\log\|F\|\.Divide byTTand use the first part of the proof\. ∎

## Appendix DAI Use

LLM\-based tools were used to assist with proofs and language editing\.

## Appendix EProof of random\-split agnostic compression

###### Proof of Lemma[6](https://arxiv.org/html/2608.25326#Thmtheorem6)\.

Conditional onRR, every output of the scheme belongs to

𝒢R=\{ρ⁡\(t\):t∈⋃j=0kRj\},\|𝒢R\|≤\(k\+1\)​Nk\.\\mathcal\{G\}\_\{R\}=\\left\\\{\\rho\(t\):t\\in\\bigcup\_\{j=0\}^\{k\}R^\{j\}\\right\\\},\\qquad\|\\mathcal\{G\}\_\{R\}\|\\leq\(k\+1\)N^\{k\}\.For fixedgg, Hoeffding’s comparison theorem for sampling without replacement gives

ℙ\{\|LCℓ\(g\)−LRℓ\(g\)\|\>s\}≤2e−2​\|C\|​s2\.\\mathbb\{P\}\\\{\|L\_\{C\}^\{\\ell\}\(g\)\-L\_\{R\}^\{\\ell\}\(g\)\|\>s\\\}\\leq 2e^\{\-2\|C\|s^\{2\}\}\.Because

LCℓ​\(g\)−LVℓ​\(g\)=N\|V\|​\(LCℓ​\(g\)−LRℓ​\(g\)\),L\_\{C\}^\{\\ell\}\(g\)\-L\_\{V\}^\{\\ell\}\(g\)=\\frac\{N\}\{\|V\|\}\\left\(L\_\{C\}^\{\\ell\}\(g\)\-L\_\{R\}^\{\\ell\}\(g\)\\right\),a union bound and tail integration imply

𝔼​supg∈𝒢R\|LCℓ​\(g\)−LVℓ​\(g\)\|≤C​log⁡\(2​\|𝒢R\|\)N≤C​\(k\+1\)​log⁡\(e​N\)N\.\\mathbb\{E\}\\sup\_\{g\\in\\mathcal\{G\}\_\{R\}\}\|L\_\{C\}^\{\\ell\}\(g\)\-L\_\{V\}^\{\\ell\}\(g\)\|\\leq C\\sqrt\{\\frac\{\\log\(2\|\\mathcal\{G\}\_\{R\}\|\)\}\{N\}\}\\leq C\\sqrt\{\\frac\{\(k\+1\)\\log\(eN\)\}\{N\}\}\.The same argument for the single fixed comparatorhhgives a smaller bound\. Empirical optimality of the compression scheme yieldsLCℓ​\(h^\)≤LCℓ​\(h\)L\_\{C\}^\{\\ell\}\(\\widehat\{h\}\)\\leq L\_\{C\}^\{\\ell\}\(h\)\. Hence

LVℓ​\(h^\)−LVℓ​\(h\)\\displaystyle L\_\{V\}^\{\\ell\}\(\\widehat\{h\}\)\-L\_\{V\}^\{\\ell\}\(h\)≤\[LVℓ−LCℓ\]​\(h^\)\+\[LCℓ−LVℓ\]​\(h\)\.\\displaystyle\\leq\[L\_\{V\}^\{\\ell\}\-L\_\{C\}^\{\\ell\}\]\(\\widehat\{h\}\)\+\[L\_\{C\}^\{\\ell\}\-L\_\{V\}^\{\\ell\}\]\(h\)\.Taking expectations proves the lemma\. ∎

## Appendix FDeferred decisions and the complete upper\-bound bookkeeping

We verify the exact partition identity and the passage between remaining populations\.

### F\.1Partition identity

Ignore internal block orders, which are uniform under both procedures\. Under the implemented procedure, a fixed disjoint tuple\(A,B,C,I\)\(A,B,C,I\)has probability

1n​\(n−1q\)−1​\(n−1−qq\)−1​\(n−1−2​qq\)−1\.\\frac\{1\}\{n\}\\binom\{n\-1\}\{q\}^\{\-1\}\\binom\{n\-1\-q\}\{q\}^\{\-1\}\\binom\{n\-1\-2q\}\{q\}^\{\-1\}\.Under deferred decisions, its probability is

\(nq\)−1​\(n−qq\)−1​\(n−2​qq\)−1​1n−3​q\.\\binom\{n\}\{q\}^\{\-1\}\\binom\{n\-q\}\{q\}^\{\-1\}\\binom\{n\-2q\}\{q\}^\{\-1\}\\frac\{1\}\{n\-3q\}\.Both expressions equal

\(q\!\)3​\(n−3​q−1\)\!n\!\.\\frac\{\(q\!\)^\{3\}\(n\-3q\-1\)\!\}\{n\!\}\.

### F\.2Subdivision identities

IfD⊆S∖AD\\subseteq S\\setminus Ais fixed conditional onAA, every later block and remainder is exchangeable withinS∖AS\\setminus A\. In particular,

𝔼⁡\[LV​\(𝟏D\)∣A\]=LS∖A​\(𝟏D\)\.\\mathbb\{E\}\[L\_\{V\}\(\\mathbf\{1\}\_\{D\}\)\\mid A\]=L\_\{S\\setminus A\}\(\\mathbf\{1\}\_\{D\}\)\.After\(A,B\)\(A,B\)are fixed, the same statement holds withS∖\(A∪B\)S\\setminus\(A\\cup B\)\. This justifies passing the bounds from Lemmas[4](https://arxiv.org/html/2608.25326#Thmtheorem4)and[5](https://arxiv.org/html/2608.25326#Thmtheorem5)toVV\.

### F\.3Inside\-menu decomposition

For anyg,hg,hand any example\(x,y\)\(x,y\),

𝟏\{g\(x\)≠y\}−𝟏\{h\(x\)≠y\}≤\\displaystyle\\mathbf\{1\}\\\{g\(x\)\\neq y\\\}\-\\mathbf\{1\}\\\{h\(x\)\\neq y\\\}\\leq\{\}𝟏​\{y∈μ⁡\(x\),g⁡\(x\)≠y\}−𝟏​\{y∈μ⁡\(x\),h⁡\(x\)≠y\}\\displaystyle\\mathbf\{1\}\\\{y\\in\\mu\(x\),g\(x\)\\neq y\\\}\-\\mathbf\{1\}\\\{y\\in\\mu\(x\),h\(x\)\\neq y\\\}\+𝟏​\{h⁡\(x\)=y,y∉μ⁡\(x\)\}\.\\displaystyle\+\\mathbf\{1\}\\\{h\(x\)=y,y\\notin\\mu\(x\)\\\}\.Averaging gives \([9](https://arxiv.org/html/2608.25326#S4.E9)\)\. Ifh⋆​\(x\)=yh^\{\\star\}\(x\)=ybuty∉μ⁡\(x\)y\\notin\\mu\(x\), eitherfh⋆,A​\(x\)≠yf\_\{h^\{\\star\},A\}\(x\)\\neq y, orfh⋆,A​\(x\)=yf\_\{h^\{\\star\},A\}\(x\)=yand this correct label is missed by the menu\. These are exactly the events in \([6](https://arxiv.org/html/2608.25326#S4.E6)\) and \([7](https://arxiv.org/html/2608.25326#S4.E7)\)\.

### F\.4Small populations

Fornnbelow a universal constant, the upper bound follows after enlargingCCbecause transductive excess error is at most one\. For largernn,q=⌊n/4⌋q=\\lfloor n/4\\rfloorsatisfies all constant\-fraction conditions used above\. IfdN=0d\_\{\\mathrm\{N\}\}=0, no two hypotheses disagree at any point\. The class has one pointwise behavior, which the learner can output with zero excess\.

## Appendix GComplete lower\-bound proofs

### G\.1Natarajan lower bound

Letd=min⁡\{dN,n\}d=\\min\\\{d\_\{\\mathrm\{N\}\},n\\\}\. Conditional on the random labels outside the hidden index, its label is uniform over the two witness labels\. Predicting any third label has error one, so every randomized learner has conditional error at least1/21/2\.

For blockjj, encode its labels as independent Rademacher variablesσj,1,…,σj,kj\\sigma\_\{j,1\},\\ldots,\\sigma\_\{j,k\_\{j\}\}\. Then

kj2−min⁡\{Bj,kj−Bj\}=12​\|∑r=1kjσj,r\|\.\\frac\{k\_\{j\}\}\{2\}\-\\min\\\{B\_\{j\},k\_\{j\}\-B\_\{j\}\\\}=\\frac\{1\}\{2\}\\left\|\\sum\_\{r=1\}^\{k\_\{j\}\}\\sigma\_\{j,r\}\\right\|\.Thep=1p=1Khinchine inequality gives

𝔼​\|∑r=1kjσj,r\|≥kj2\.\\mathbb\{E\}\\left\|\\sum\_\{r=1\}^\{k\_\{j\}\}\\sigma\_\{j,r\}\\right\|\\geq\\sqrt\{\\frac\{k\_\{j\}\}\{2\}\}\.Sincekj≥⌊n/d⌋≥n/\(2​d\)k\_\{j\}\\geq\\lfloor n/d\\rfloor\\geq n/\(2d\),

𝔼​ℰS​\(A\)≥12​n​∑j=1dkj2≥14​dn\.\\mathbb\{E\}\\mathcal\{E\}\_\{S\}\(A\)\\geq\\frac\{1\}\{2n\}\\sum\_\{j=1\}^\{d\}\\sqrt\{\\frac\{k\_\{j\}\}\{2\}\}\\geq\\frac\{1\}\{4\}\\sqrt\{\\frac\{d\}\{n\}\}\.This expectation is over a finite random choice of labelings\. At least one labeling attains the expected lower bound\.

### G\.2Projection of a pseudo\-cube

LetF⊆YDF\\subseteq Y^\{D\}be a pseudo\-cube and retain a coordinate setJ⊆\[D\]J\\subseteq\[D\]\. LetF\|JF\|\_\{J\}be the set of distinct projections\. Fixv∈F\|Jv\\in F\|\_\{J\}, choose a preimagev~∈F\\widetilde\{v\}\\in F, and fixj∈Jj\\in J\. The pseudo\-cube property suppliesu~∈F\\widetilde\{u\}\\in Fdiffering fromv~\\widetilde\{v\}only atjj\. Their projections remain distinct and differ only atjj\. ThusF\|JF\|\_\{J\}is a\|J\|\|J\|\-dimensional pseudo\-cube\.

### G\.3Randomized fiber counting

Fix the padded population described in Section[5](https://arxiv.org/html/2608.25326#S5)\. For a directioni≥2i\\geq 2, leteebe a coordinate fiber ofFF\. Allv∈ev\\in einduce exactly the same observed labeled population when the unique copy ofxix\_\{i\}is hidden\. The learner therefore uses one common distributionPeP\_\{e\}over predicted labels\. Distinct vertices ineehave distinct labels at coordinateii, so

∑v∈eℙPe\{y^≠vi\}=\|e\|−∑v∈ePe\(vi\)≥\|e\|−1\.\\sum\_\{v\\in e\}\\mathbb\{P\}\_\{P\_\{e\}\}\\\{\\widehat\{y\}\\neq v\_\{i\}\\\}=\|e\|\-\\sum\_\{v\\in e\}P\_\{e\}\(v\_\{i\}\)\\geq\|e\|\-1\.Each vertex belongs to one fiber in each of thed−1d\-1retained directions\. Every fiber is nontrivial, so

∑v∈F∑i=2dℙ⁡\{A​errs at​xi∣v\}\\displaystyle\\sum\_\{v\\in F\}\\sum\_\{i=2\}^\{d\}\\mathbb\{P\}\\\{A\\text\{ errs at \}x\_\{i\}\\mid v\\\}≥∑e\(\|e\|−1\)\\displaystyle\\geq\\sum\_\{e\}\(\|e\|\-1\)≥12​∑e\|e\|\\displaystyle\\geq\\frac\{1\}\{2\}\\sum\_\{e\}\|e\|=\|F\|​\(d−1\)2\.\\displaystyle=\\frac\{\|F\|\(d\-1\)\}\{2\}\.Somevvhas at least\(d−1\)/2\(d\-1\)/2expected errors\. Its population is realizable, so the comparator loss is zero\. Dividing bynnproves the DS lower bound for randomized learners\.