A split in the error rate
An arXiv preprint offers a two-part theoretical account of error in agnostic multiclass transductive learning. It asks whether the binary equivalence between agnostic transductive and PAC learning extends to multiclass classes, even when the label space is unbounded. Its central result is a pair of worst-population bounds: one term scales with the DS dimension divided by n, while another scales with the square root of the Natarajan dimension divided by n. The lower and upper bounds have this same basic shape, but they match only up to logarithmic factors.
The analysis ranges over every nonempty multiclass hypothesis class H with an arbitrary label space Y. Its input is a finite indexed labeled population, and repeated instances and repeated labeled examples are allowed. The endpoint is optimal worst-population agnostic transductive excess error: it optimizes over learners and then takes the worst labeled population. The quantity compares a learner's loss with the loss of the best fixed hypothesis in H on that same population.
The two terms do different work
For every such class and every n of at least 2, the theorem places the optimal excess error between a lower and an upper bound. The lower side contains DS dimension divided by n, plus the square root of Natarajan dimension divided by n. The upper side contains the same two pieces, but adds a log-squared factor to the DS term and a log-cubed factor inside the square-root Natarajan term. Both bounds are capped at 1.
The authors interpret this as a division of labor between the two dimensions. DS controls a faster approximation term, while Natarajan controls a slower, square-root estimation term. At the sample-complexity level, the result says transductive learning follows, up to polylogarithmic factors, the same two-parameter law as agnostic PAC learning: DS dimension divided by target error, plus Natarajan dimension divided by target error squared.
How the learner handles the hidden label
To obtain the upper bound, the learner begins with a random reservation. With q equal to the floor of n divided by 4, it selects three disjoint visible blocks, A, B and C, each of size q, and ignores the other visible labels. The construction makes the hidden index equivalent to a uniformly selected point in the unseen complement V, allowing the hidden-label loss to be studied over that unseen part.
That reservation feeds a three-stage architecture. First, realizable compression creates a finite cover of candidate rules. Next, a multiplicative-weights step reduces the pointwise label space. Finally, inside-menu agnostic compression learns on the final block. The compression ingredients are stated for arbitrary label spaces, with their sizes controlled by the DS and Natarajan dimensions and logarithmic overhead.
Two worst-case obstructions
The lower bound is built from two different obstructions. For the Natarajan term, the construction takes d equal to the smaller of the Natarajan dimension and n, repeats the resulting shattered points in blocks, and assigns independent fair witness labels. The hidden label remains unpredictable, leaving every learner with conditional error of at least one-half. This is a worst-population construction, not an empirical performance estimate.
A DS pseudo-cube supplies the second obstruction. It produces a realizable population in which some vertex incurs at least (d minus 1) divided by 2 expected errors across the n possible hidden positions. Dividing by n yields the DS lower bound for randomized learners. Taken together, the two constructions account for the two terms in the theorem's worst-case rate.
The logarithmic gap remains
The result leaves a logarithmic gap between the lower and upper bounds. The paper traces that gap to boosting, reconstructed-family enumeration and inside-menu compression. The construction is information-theoretic and need not be computationally efficient. The paper also does not provide a black-box reduction for arbitrary bounded losses.
The document is an arXiv preprint, version 1, dated 26 August 2026. It sets out the setting, learner and assumptions in Sections 2 through 4 and includes complete proofs of every stated lemma and theorem after the references.
Paper data and sources
Original title: Two Dimensions Govern Agnostic Multiclass Transductive Learning
Authors: Pahan Dewasurendra
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text