🤖 machine learning

Two Dimensions Govern Agnostic Multiclass Transductive Learning

This paper resolves the open question of whether agnostic transductive and PAC learning share the same minimax rates in multiclass settings by proving that for arbitrary label spaces, the optimal excess error is governed by a two-dimension law combining the DS dimension and Natarajan dimension, specifically $\widetilde\Theta\left(\frac{d_{DS}}{n}+\sqrt{\frac{d_{\mathrm N}}{n}}\right)$ .

Original authors: Pahan Dewasurendra

Published 2026-08-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Pahan Dewasurendra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of machine learning, computers learn to make predictions by studying examples. Imagine a student trying to guess the answer to a test question. In the standard way of learning, called "PAC learning," the student practices on a set of flashcards, then takes a test on new, unseen cards. The goal is to perform well on average over many possible tests. But there is another, more specific way of learning called "transductive learning." Here, the student is given the entire test paper in advance, including every question, but the answer to just one specific question is hidden. The student sees all the other answers and must predict the single missing one. This setup is stricter because the student cannot rely on average performance; they must be right for that specific, fixed set of questions.

For simple problems with only two possible answers, like "yes" or "no," researchers have long known that these two ways of learning are essentially the same in terms of how much data is needed to succeed. However, when the answers can be one of many possibilities—like identifying thousands of different species of birds or diagnosing hundreds of diseases—the rules change. In these complex, "multiclass" situations, the difficulty of learning depends on two different mathematical measures of complexity. One measure, often called the DS dimension, relates to how well the learner can handle situations where a perfect answer exists. The other, the Natarajan dimension, relates to how much uncertainty remains when no perfect answer is available. For years, it was an open question whether the strict "transductive" rules would force the learner to need more data than the standard "PAC" rules, especially when the number of possible answers is huge or even infinite.

A researcher at Johns Hopkins University has now resolved this question, showing that for multiclass problems, the strict transductive rules do not actually require more data than the standard rules, up to very small adjustments. They proved that the amount of information needed to learn in this strict setting is governed by the same two complexity measures that control the standard setting. Their work demonstrates that even when the learner must predict a single hidden label from a fixed group of examples, they can achieve the same level of accuracy as if they were learning from a random stream of data. This finding is significant because it unifies two different models of learning, confirming that the fundamental limits of learning are determined by the nature of the problem itself, not by the specific way the data is presented.

To reach this conclusion, the researcher had to overcome a major hurdle. In the strict transductive setting, a learner cannot simply look at all the visible answers and pick the best rule, because doing so can lead to a kind of instability. If a learner tries to fit the visible data perfectly, they might accidentally create a rule that works for every visible example but fails completely on the hidden one. This is similar to a student who memorizes the answers to every practice question but fails the test because they didn't understand the underlying pattern. The researcher found that to avoid this trap, the learner must deliberately ignore a portion of the visible data.

The solution they devised involves a strategy of "random reservation." Instead of using all the visible examples to build a prediction, the learner randomly sets aside a large chunk of the visible data, treating it as if it were the hidden test point. By ignoring these reserved labels, the learner creates a large, unseen block of data that is statistically independent of the rule they construct. This allows them to use powerful mathematical tools that rely on the idea of generalization—predicting well on data that was not used to build the model. The learner then uses a three-step process to refine their prediction. First, they use a small sample of the visible data to create a finite list of possible prediction rules. Second, they use a weighted voting system to narrow down the list of possible answers for each question, effectively reducing the complexity of the problem. Finally, they use the remaining visible data to select the best rule from this narrowed list.

This approach relies on a new mathematical insight about how to handle data that is sampled without replacement. In many learning scenarios, data points are assumed to be independent, like drawing a card from a deck and putting it back. But in the transductive setting, once a data point is seen, it cannot be seen again. The researcher proved that even with this restriction, a specific type of weighted voting system still works effectively. They showed that the "experts" or rules in their system earn a predictable amount of "rewards" based on how well they cover the unseen parts of the data. This ensures that the learner does not lose accuracy when moving from the visible data to the hidden prediction.

The researcher also proved that their result is the best possible by constructing specific examples where learning becomes difficult. They showed that if the problem has a high level of complexity in the "perfect answer" sense, the error rate will be proportional to that complexity divided by the number of examples. If the problem has a high level of uncertainty in the "no perfect answer" sense, the error rate will be proportional to the square root of that complexity divided by the number of examples. Both of these factors are necessary; removing either one would make the learning task impossible in certain cases. This confirms that the two dimensions of complexity identified in standard learning theory are indeed the correct measures for the strict transductive setting as well.

The implications of this work are that the gap between the two learning models has been closed. For anyone designing learning algorithms for complex, multiclass problems, it means that the same theoretical limits apply whether the data is presented as a random stream or as a fixed set with one hidden answer. The researcher did not provide a specific algorithm that is guaranteed to be fast on a computer, as their proof is based on information theory rather than computational efficiency. However, they established that the fundamental barrier to learning is the same in both worlds. By showing that a structured approach using random reservation and compression can transfer the success of standard learning to the strict transductive setting, they have provided a clear roadmap for understanding the limits of prediction in complex environments.

This work also clarifies the role of different types of complexity in learning. It shows that the ability to learn a perfect rule and the ability to learn a good rule in the presence of noise are distinct challenges, each requiring a different amount of data. The researcher demonstrated that these challenges do not compound in a way that makes the transductive setting harder than the standard one. Instead, the learner can navigate the fixed population of data by strategically ignoring parts of it, thereby turning a difficult, unstable problem into a manageable one. The result holds even when the number of possible answers is infinite, a scenario where previous methods often failed.

In the end, the study confirms that the laws governing how machines learn are robust. Whether the learner is practicing on a random set of examples or solving a specific puzzle with one missing piece, the amount of information required to succeed is determined by the same underlying structure of the problem. The researcher has shown that by carefully managing how data is used and by understanding the specific dimensions of complexity involved, it is possible to achieve optimal performance in the strictest learning environments. This provides a solid theoretical foundation for future developments in machine learning, ensuring that as algorithms become more sophisticated, they remain grounded in a clear understanding of what is possible.

Technical Summary: Two Dimensions Govern Agnostic Multiclass Transduction

Problem Statement
The paper addresses the fundamental question of whether the minimax rates for agnostic multiclass transductive learning match those of agnostic multiclass PAC (Probably Approximately Correct) learning. In the transductive setting, an adversary fixes a labeled population of size $n$ , one label is hidden uniformly at random, and the learner observes all other labels and the full set of instances to predict the hidden label. While it is established that for binary classification, agnostic transductive and PAC learning share the same optimal rate of $\Theta(\sqrt{d/n})$ (where $d$ is the VC dimension), the multiclass case remained open.

Multiclass learning over arbitrary (potentially unbounded) label spaces presents a unique challenge: no single dimension controls the sample complexity. Instead, two dimensions are required:

DS Dimension ( $d_{DS}$ ): Characterizes realizable learnability.
Natarajan Dimension ( $d_N$ ): Characterizes agnostic learnability in the small-excess regime.

Recent work established that the agnostic PAC sample complexity is governed by the sum of these dimensions: $\tilde{\Theta}(d_{DS}/\epsilon + d_N/\epsilon^2)$ . The open problem was whether this "two-dimension law" extends to the transductive setting, where empirical risk minimization over finite populations can suffer from instability (high leave-one-out error) even with small hypothesis classes.

Methodology
The paper resolves this question by constructing a specific transductive learner and proving matching lower bounds. The core methodological innovation is a random-reservation principle.

Random Reservation: Instead of using all visible labels, the learner deliberately ignores a constant fraction of the visible examples. Specifically, from the $n-1$ visible examples, the learner selects three disjoint random blocks ( $A, B, C$ ) of size $q \approx n/4$ and ignores the rest. The hidden index is then uniformly distributed within the complement of these blocks (the "unseen block"). This transforms the single hidden label into a uniformly random point within a large unseen population, allowing for finite-population generalization without relying on leave-one-out stability.
Three-Stage Learning Architecture: The learner adapts a structured PAC architecture to this finite-population split:
- Stage 1 (Realizable Compression): Using block $A$ , the learner constructs a finite cover of the hypothesis space using a realizable compression scheme. This reduces the infinite hypothesis class to a finite set of candidates ( $F_A$ ) that are consistent with the realizable part of the data.
- Stage 2 (Label-Space Reduction): Using block $B$ , the learner runs a without-replacement multiplicative weights algorithm over the finite set $F_A$ . This produces a "menu" (a small set of candidate labels) for each instance, effectively reducing the label space.
- Stage 3 (Inside-Menu Agnostic Compression): Using block $C$ , the learner performs agnostic compression restricted to the labels in the generated menu to produce the final predictor.
Key Technical Lemmas:
- Finite-Population Compression Cover: Extends compression bounds to fixed populations, showing that a predictor reconstructed from a subset performs well on the unseen remainder.
- Without-Replacement Multiplicative Weights Lemma: A novel lemma proving that for experts sampled without replacement, the expected cumulative reward is bounded, preserving the fast $1/n$ approximation term (crucial for the $d_{DS}$ term) despite the lack of independence between samples.
- Random-Split Agnostic Compression: Transfers empirical optimality from one random block to another using Hoeffding's inequality for sampling without replacement.

Key Results
The paper establishes that the optimal agnostic transductive excess error $\epsilon_{tr}^H(n)$ is governed by the same two dimensions as PAC learning, up to logarithmic factors.

Upper Bound:
$\epsilon_{tr}^H(n) \leq C \min \left\{ 1, \frac{d_{DS} \log^2(en)}{n} + \sqrt{\frac{d_N \log^3(en)}{n}} \right\}$
Lower Bound:
$\epsilon_{tr}^H(n) \geq c \min \left\{ 1, \frac{d_{DS}}{n} + \sqrt{\frac{d_N}{n}} \right\}$

These bounds hold for arbitrary label spaces (including infinite and uncountable ones). Consequently, the sample complexity for transductive learning is:
$m_{tr}^H(\epsilon) = \tilde{\Theta} \left( \frac{d_{DS}}{\epsilon} + \frac{d_N}{\epsilon^2} \right)$

Lower Bound Constructions
The author proves the necessity of both terms using specific obstructions:

Natarajan Obstruction: By repeating shattered points and assigning fair labels, the hidden label remains a fair bit independent of the visible data, forcing an error rate proportional to $\sqrt{d_N/n}$ .
DS Obstruction: By orienting the coordinate fibers of a pseudo-cube, the author shows that even with repetitions, the average outdegree (error) remains proportional to the DS dimension, necessitating the $d_{DS}/n$ term.

Contributions and Significance
The paper claims the following contributions:

Characterization: It fully characterizes agnostic multiclass transductive error via separate DS and Natarajan terms for arbitrary label spaces.
Random-Reservation Reduction: It introduces a reduction technique that transfers structured PAC learners to fixed finite populations, bypassing the instability of direct leave-one-out transfers.
New Lemma: It proves a without-replacement multiplicative-weights menu lemma with a miss probability of $O(\log |F|/n)$ , which is essential for retaining the fast $d_{DS}/n$ rate.
Direct Lower Bounds: It provides direct transductive lower bounds derived from Natarajan cubes and DS pseudo-cubes.

Significance
The paper resolves the open question of whether agnostic multiclass PAC and transductive learning obey the same statistical laws. It demonstrates that, up to logarithmic factors, the two models are equivalent in their dependence on the DS and Natarajan dimensions. This result is significant because it confirms that the "two-dimension law" is a fundamental property of multiclass learning, independent of whether the data is drawn i.i.d. (PAC) or fixed (transductive). The author notes that their result is information-theoretic and does not necessarily imply computational efficiency, nor does it provide a black-box reduction for all bounded loss functions, but it specifically exploits the structure of multiclass learning to close the gap between the two models.

Technical Summary: Two Dimensions Govern Agnostic Multiclass Transduction

More like this