PaperlayerView exact revision on arXiv

Source-linked AI summary

Two Dimensions Govern Agnostic Multiclass Transductive Learning

Pahan Dewasurendra

arXiv:2608.25326v1cs.LG

TL;DR

Whether agnostic transductive and PAC learning share the same rate in multiclass classification was open. This paper uses random reservation and structured compression to show that both models obey the same two-dimension law up to logarithmic factors.

  • Problem

    Whether agnostic transductive and PAC learning have the same rate for multiclass classification remained open.

  • Method

    A random-reservation reduction combines realizable compression, label-space reduction, and inside-menu agnostic compression for finite populations.

  • Results

    Agnostic multiclass transductive learning matches PAC learning up to logarithmic factors, including for unbounded label spaces.

  • Takeaways & Limitations

    DS dimension governs the fast approximation term, while Natarajan dimension governs the square-root estimation term.

  • Takeaways & Limitations

    The result has a logarithmic gap, is information-theoretic rather than necessarily computationally efficient, and does not cover arbitrary bounded losses via a black-box reduction.

Abstract

from arXiv · show

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 dimension $d_{DS}$ and Natarajan dimension $d_{\mathrm N}$, the optimal agnostic transductive excess error satisfies $\widetildeΘ\left(\frac{d_{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 realizable $d_{DS}/n$ obstruction, while a Natarajan cube with repeated points and fair labels gives the agnostic $\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 fast $d_{DS}/n$ term. Consequently, agnostic multiclass PAC and transductive learning obey the same two-dimension law up to logarithmic factors.

1 INTRODUCTION

The paper resolves the multiclass agnostic transductive-learning question up to logarithmic factors: the optimal excess error has separate DS and Natarajan terms for arbitrary label spaces. It achieves this through random reservation and establishes matching lower bounds from DS pseudo-cubes and Natarajan cubes.

  • Main result: The optimal agnostic transductive excess error is ~Theta(d_DS/n + sqrt(d_N/n)), matching the multiclass PAC rate up to logarithmic factors.Here d_DS is the DS dimension and d_N is the Natarajan dimension.
  • Main result: The characterization holds for arbitrary, including infinite or uncountable, label spaces.Separate DS and Natarajan dimensions are required because no single dimension controls multiclass agnostic complexity.
  • Upper bound: The learner reserves random blocks and ignores other visible labels, making the hidden label uniform within a large unseen block.A three-stage construction then combines realizable compression, pointwise label-space reduction by multiplicative weights, and inside-menu agnostic compression.
  • Upper bound: The new without-replacement multiplicative-weights menu lemma achieves miss probability O(log |F|/n).It preserves the fast DS-dependent term despite examples arriving without replacement.
  • Lower bounds: Both dimensions are necessary: Natarajan cubes yield the sqrt(d_N/n) obstruction, while DS pseudo-cubes yield the d_DS/n obstruction.The Natarajan construction repeats shattered points with fair witness labels; the DS construction orients pseudo-cube coordinate fibers.

2 SETTING AND MAIN RESULT

The paper defines agnostic multiclass transductive learning over arbitrary label spaces and proves that its optimal excess-error rate is governed by DS and Natarajan dimensions. It also explains why generic empirical-risk-minimization transfer fails without random reservation.

  • Setting: A transductive learner sees all instances, a held-out index, and the remaining labeled examples, then predicts the hidden label.Repeated instances and labeled examples are allowed, and the label space may be arbitrary.
  • Dimensions: The Natarajan dimension counts shattered sequences, while the DS dimension is the largest dimension of a pseudo-cube appearing in a class trace.These dimensions capture distinct multiclass combinatorial structures.
  • Main result: d_DS/n + sqrt(d_N/n) governs optimal agnostic transductive excess error up to logarithmic factors for every multiclass class.The theorem provides universal-constant upper and lower bounds, with the upper bound vacuous when d_DS = ∞.
  • Main result: A class with Natarajan dimension zero has zero transductive excess error.This is an explicit convention used in the theorem statement.
  • Why a generic ERM transfer fails: Generic ERM transfer fails because leave-one-out tie-breaking can select a hypothesis wrong only at the held-out index, producing error one.Finite cardinality bounds help only when the test point lies in a large block not used to choose the output; random reservation creates that block.

3 THREE FINITE-POPULATION LEMMAS

The upper bound rests on three finite-population tools: compression ingredients, a realizable compression cover, and a without-replacement multiplicative-weights menu. A random split then transfers empirical optimality from one block to excess control on another.

  • Compression ingredients: Realizable and sample compression schemes provide the core ingredients, including empirical optimality for arbitrary loss functions and arbitrary label spaces.The menu-restricted compression size satisfies k2(m) ≤ C dN log(ep) log(em).
  • Finite-population compression cover: A finite-population compression cover bounds a fixed comparator’s unseen disagreements after compressing its correctly labeled examples.The proof uses a compression union bound over unseen points, with at most (k + 1)N^k possible reconstructed outputs.
  • Finite-population MW menu: The finite-population multiplicative-weights lemma constructs a prediction menu from sampled experts and controls every comparator’s unseen misses.The sampled experts’ expected cumulative reward is at most two because their newly covered point sets are disjoint.
  • Random-split agnostic compression: A uniformly random split into sufficiently large compression and validation blocks transfers empirical optimality on the compression block into excess control on the validation block.The argument applies sampling-without-replacement concentration and a union bound over at most (k + 1)N^k possible outputs.

4 THE TRANSDUCTIVE LEARNER

The transductive learner reserves three random blocks from the visible examples, ignores all other visible labels, and applies realizable compression, label-space reduction, and inside-menu learning in sequence. Deferred decisions make the test point uniform in the remaining population, enabling the upper-bound argument.

  • Random reservation: The learner selects disjoint blocks A, B, and C of size q = ⌊n/4⌋ with independent uniform orders, using no labels outside these blocks.The hidden index is uniformly selected, and all visible labels outside A, B, and C are deliberately ignored.
  • Upper-bound argument: Deferred decisions show that conditioning on A, B, and C yields the same joint law as first choosing the blocks and then selecting I uniformly from V.Consequently, expected test loss is LV(bh), while V is a uniform subset of S and ELV(h⋆) = LS(h⋆).
  • Three-stage learner: The three stages construct a finite expert cover from A, reduce the label space to a menu of size at most q using B, and learn inside that menu from C.The final classifier is reconstructed from the inside-menu compression scheme and used to predict the hidden point.
  • Information validity: The algorithm is information valid because it selects A, B, and C from visible examples and never uses labels in V, even when those labels are available.This preserves the intended transductive information restriction.
  • Upper-bound argument: The final miss event is contained in the union of the intermediate events, and combining the resulting bounds yields the theorem’s right-hand side before applying the cap at one.The trivial upper bound one supplies the final cap.

5 MATCHING LOWER BOUNDS

The section proves the two lower-bound terms separately: Natarajan dimension yields the agnostic d_N/n obstruction, while DS dimension yields the realizable d_DS/n obstruction. Since their maximum is at least half their sum, the combined lower bound follows.

  • Combining bounds: Proving the two terms separately suffices because their maximum is at least half their sum.This establishes the combined lower bound up to the stated constant factor.
  • Natarajan lower bound: A Natarajan-shattered construction repeats d=min{d_N,n} points in nearly equal blocks and assigns each copy an independent fair witness label.The hidden label remains a fair independent bit after conditioning on visible labels.
  • Natarajan lower bound: Every learner has expected error at least 1/2, while blockwise majority choices are realizable and produce the agnostic obstruction.Hypotheses using third labels are dominated by the two witness-label choices on each point.
  • Natarajan lower bound: The probabilistic method fixes a deterministic labeling with excess error at least d/n.Here d=min{d_N,n}.
  • DS lower bound: A DS pseudo-cube construction uses one copy of each coordinate except one heavily repeated point and labels the population by a realizable pseudo-cube vertex.For d≥2, fibers of vertices agreeing outside a coordinate force aggregate errors when that coordinate is hidden.
  • DS lower bound: Some realizable vertex causes at least (d−1)/2 errors across the n possible hidden positions.For d=1, the Natarajan obstruction already dominates the desired 1/n term.

6 RELATED WORK AND DISCUSSION

Prior work characterizes agnostic transductive error through hypergraph orientation and develops the PAC compression architecture that this paper transfers to fixed populations. The result remains logarithmically loose, information-theoretic rather than necessarily computationally efficient, and limited for arbitrary bounded losses.

  • Agnostic one-inclusion graphs: Agnostic Hall complexity exactly characterizes optimal multiclass transductive error, while prior work does not bound it by statistical dimensions.Asilis et al. formulate the problem as orienting a Hamming hypergraph with vertex credits given by distance from H.
  • Agnostic multiclass PAC learning: The paper transfers the three-stage cover, multiplicative-weights, and inside-menu PAC architecture to a fixed population using random reservation.The finite-population menu lemma is identified as essential for this transfer.
  • Other transductive models: Batch leave-one-out transduction differs from online multiclass transduction, which reveals the full instance sequence and predicts many labels sequentially.Online rates are governed by level-constrained Littlestone-type dimensions.
  • Limitations and open questions: The logarithmic gap arises from boosting weak learners into compression, enumerating reconstructed families, and inside-menu compression.Removing the gap may require directly weighting orientations of the multiclass agnostic Hamming hypergraph.
  • Limitations and open questions: The result is information-theoretic, need not be computationally efficient, and does not give a black-box reduction for arbitrary bounded losses.These limitations parallel the underlying one-inclusion and compression constructions.

7 CONCLUSION … A.2 INSIDE-MENU COMPRESSION

Agnostic multiclass transduction and PAC learning share two statistical scales up to logarithmic factors: DS dimension governs approximation, while Natarajan dimension governs estimation. The appendix derives the compression ingredients supporting this result, including realizable and inside-menu schemes for arbitrary label spaces.

  • 7 CONCLUSION: DS dimension controls the fast approximation term, while Natarajan dimension controls the square-root estimation term in agnostic multiclass transduction.This resolves the multiclass PAC-versus-transductive question up to logarithmic factors.
  • 7 CONCLUSION: Randomly reserving a large unseen block converts structured compression arguments into finite-population guarantees and avoids unstable direct leave-one-out transfer.The resulting principle underlies the transductive upper bound.
  • REPRODUCIBILITY STATEMENT: The setting, learner, and assumptions are specified in Sections 2–4, with complete proofs included after the references.The proofs include exact partition bookkeeping and randomized lower-bound quantifiers.
  • A COMPRESSION INGREDIENTS: The appendix provides a self-contained derivation of the consequences collected in Proposition 3.This establishes the stated compression ingredients used by the main results.
  • A.1 REALIZABLE COMPRESSION FROM DS DIMENSION: O(dDS) examples suffice for a deterministic constant-error weak learner for every label space.The construction extends to infinite label spaces through the cited density and compactness arguments.
  • A.1 REALIZABLE COMPRESSION FROM DS DIMENSION: O(dDS log(en)) compression size follows by converting the deterministic weak learner into a realizable compression scheme on sequences of length at most n.Compression tuples may repeat input examples, motivating counting with N^k rather than binomial coefficients.
  • A.2 INSIDE-MENU COMPRESSION: O(dN log(ep)/m) leave-one-out error holds for partial hypotheses restricted to menus of size p, whose active labels per point are at most p.The partial class has Natarajan dimension at most dN, and the one-inclusion learner yields the inside-menu compression scheme.

B PROOF OF THE FINITE-POPULATION COMPRESSION COVER

The proof analyzes reconstructions generated by short ordered tuples, then controls each reconstruction through its indexed bad set. Realizability ensures the bad set avoids the tuple’s associated sample subset, enabling sampling-without-replacement control.

  • Reconstruction enumeration: Every possible reconstruction is represented as ρ(t), where t is an ordered tuple from R of length at most k and repetitions are allowed.The proof reduces the reconstruction family to tuple-indexed candidates.
  • Bad-set analysis: For a fixed tuple t and reconstruction f = ρ(t), the proof defines an indexed bad set to analyze its errors.This establishes the object used in the subsequent finite-population argument.
  • Sampling control: When f = f_h,A, realizability implies A∩D_t = ∅, allowing sampling without replacement to bound cases where |D_t|/(N − m) exceeds u.The disjointness condition is the key structural fact used in the sampling argument.

C PROOF OF THE FINITE-POPULATION MW LEMMA

The proof establishes the finite-population multiplicative-weights bound by comparing a benchmark’s final unseen-set misses with sequential conditional expectations. It controls the learner’s cumulative mistakes using disjoint first-correct sets and the resulting bound on the remaining population.

  • Benchmark-miss tracking: The proof fixes a benchmark f⋆ and tracks points it labels correctly but the learner has missed in every prior round.This is represented by the indicators Q_t(x, y).
  • Finite-population comparison: At each round, the next revealed point is uniform in the remaining population, while the final unseen set is a uniform subset of that remainder.Because Q_T+1(z) ≤ Q_t(z) on the final unseen set, sequential miss rates lower-bound the final unseen-set miss rate.
  • Multiplicative-weights step: The learner’s cumulative loss is analyzed through multiplicative-weights regret at learning rate 1/2.The proof then reduces the remaining task to bounding the left side of the regret inequality.
  • Disjointness argument: The sets D_1, ..., D_T of first-round correct predictions are pairwise disjoint along every path.This disjointness enables the remaining-population bound used to control the regret expression.
  • Final normalization: The proof bounds the remaining population by |R_t| ≤ |D_t| (N − T + 1), then sums over rounds and divides by T.The summed ratio is at most 2, after which the first part of the proof gives the desired result.

E PROOF OF RANDOM-SPLIT AGNOSTIC COMPRESSION … F.4 SMALL POPULATIONS

The upper-bound proof combines random-split compression with deferred-decision identities, exchangeability, and an inside-menu error decomposition. Boundary cases are handled separately for small populations and classes with no Natarajan disagreements.

  • E PROOF OF RANDOM-SPLIT AGNOSTIC COMPRESSION: Conditional on R, the compression scheme’s outputs lie in a restricted family whose size is bounded by (k + 1)N k.The proof invokes this finite output-family restriction before taking expectations.
  • E PROOF OF RANDOM-SPLIT AGNOSTIC COMPRESSION: Hoeffding’s comparison theorem for sampling without replacement, followed by a union bound and tail integration, controls the compression scheme’s deviations.The same argument yields a smaller bound for the single fixed comparator, while empirical optimality supplies the final comparison.
  • F.1 PARTITION IDENTITY: The deferred-decision analysis verifies that the implemented partition and the deferred procedure assign matching probabilities to fixed disjoint tuples.Internal block orders are ignored because they are uniform under both procedures.
  • F.2 SUBDIVISION IDENTITIES: Conditional on a fixed initial block A, every later block and remainder is exchangeable within S \ A, yielding E[LV (1D) | A] = LS\A(1D).After fixing A and B, the same identity holds within S \ (A ∪B), allowing bounds from Lemmas 4 and 5 to pass to V.
  • F.3 INSIDE-MENU DECOMPOSITION: The inside-menu decomposition bounds excess error by menu-restricted errors plus the event that the comparator’s correct label lies outside the menu.For h⋆, the missed-correct-label event splits into prediction failure or failure to include the correct label in the menu.
  • F.4 SMALL POPULATIONS: For n below a universal constant, enlarging C suffices because transductive excess error is at most one.For larger n, q = ⌊n/4⌋ satisfies the constant-fraction conditions used earlier.
  • F.4 SMALL POPULATIONS: When dN = 0, no two hypotheses disagree at any point, so the learner can output the single pointwise behavior with zero excess.This handles the degenerate class case separately from the population-size argument.

G COMPLETE LOWER-BOUND PROOFS … G.3 RANDOMIZED FIBER COUNTING

The lower-bound proofs establish Natarajan and DS obstructions through conditional label uncertainty, pseudo-cube projection, and randomized fiber counting. A realizable padded population forces at least (d −1)/2 expected errors for randomized learners, yielding the DS lower bound after normalization by n.

  • G.1 NATARAJAN LOWER BOUND: For d = min{d_N, n}, the hidden label is conditionally uniform over two witness labels, so predicting any third label incurs error one and every randomized learner has conditional error at least 1/2.The conditioning is on the random labels outside the hidden index.
  • G.1 NATARAJAN LOWER BOUND: Block labels are encoded as independent Rademacher variables σ_j,1, . . . , σ_j,k_j.
  • G.1 NATARAJAN LOWER BOUND: Because the expectation ranges over finitely many labelings, at least one labeling attains the expected lower bound.
  • G.2 PROJECTION OF A PSEUDO-CUBE: Restricting a pseudo-cube F to coordinates J preserves a |J|-dimensional pseudo-cube in the distinct projection set F|J.For each projected vertex, a preimage and a witness differing only at the selected coordinate produce distinct projections differing only there.
  • G.3 RANDOMIZED FIBER COUNTING: In each retained direction i ≥ 2, vertices within a coordinate fiber induce the same observed labeled population, so the learner uses one common prediction distribution P_e.Distinct fiber vertices have distinct labels at coordinate i.
  • G.3 RANDOMIZED FIBER COUNTING: Every vertex belongs to one nontrivial fiber in each of the d −1 retained directions.
  • G.3 RANDOMIZED FIBER COUNTING: At least (d −1)/2 expected errors occur for some vertex, while its realizable population has zero comparator loss; dividing by n proves the randomized DS lower bound.
Loading 2608.25326v1…