Transductive Learning is Compact

Thank you for your time and attention in reviewing the paper. We will address your questions in order.

Line 48: $H|_S$ can indeed be infinite when $Y$ is infinite. For this reason, we refer only to finite subsets of $H|_S$ as finite projections of $H$. That is, a finite projection of $H$ refers to both restricting to a finite collection of points in the domain and restricting to finitely many behaviors on those points (lines 45-48). We will add further clarification to the beginning of Section 1.1.

Line 174-175: It is defined as the first option you mentioned: there exists an assignment of unassigned variables satisfying all functions in $R’$. I.e., the assignment is permitted to depend upon the choice of $R’$, but it may not depend upon particular functions in $R’$. We will clarify this further in the next draft.

Line 195: That is a typo, the inequality should be strict – thank you!

Line 207: Yes, an element must be in the poset $P$ in order to be an upper bound, as it must be in $P$ in order to be comparable to any elements in $P$.

Line 212-213: Yes, you are exactly correct! Unfortunately we must be slightly terse at times owing to the page limit. We will further clarify this step in the next version of the paper.

Line 216: Total in the sense of assigning all variables, i.e., not leaving any variables unassigned. We will clarify this in the paper.

Theorem 3.6: Formally, $L$ is a set of variables which are valued in $Y$ and which are indexed/parameterized in the following manner: L = \cup_{S' \subseteq S, |S'| = n-1} H|_{S'}. So each variable $\ell \in L$ is represented by a tuple of the form $(y_1, \ldots, y_{i-1}, ?, y_{i+1}, \ldots, y_n)$.

$R$ is a collection of functions, indexed/parameterized by $R = H|_S$. The function $r \in R$ which is represented by $(y_1, \ldots, y_n)$ depends upon the $n$ variables $\ell \in L$ whose representing vectors agree with that of $r$ except for a “?” in one of its entries. (Formally, the representing vectors of $r$ and $\ell$ have the same values in the non-"?" entries of $\ell$.) Lastly, we define the output of $r$ on these variables $\ell_1, \ldots, \ell_n$ as $\frac 1n \sum d(y_i, \ell_i)$.

Line 244: By assuming condition (2.), we have that all finite projections of H can be learned to error $\leq \epsilon$ using $n = m(\epsilon)$ many samples. This is equivalent to condition (2.) of Theorem 3.3 for the system of variables and functions we describe, allowing us to conclude condition (1.). In that sense, we do not need to worry about infimums.

Line 246: Exactly: the pre-image of bounded sets must be bounded because the function uses the norm on Y. (E.g., the pre-image of $[0, \epsilon]$ contains only points within distance $\epsilon$ of $r = (y_1, \ldots, y_n)$ in each coordinate.)

Line 331: Each node in $R$ is permitted to have multiple incident nodes in $L$. An $R$-matching, however, consists of only one choice of incident edge for each node in $R$. The requirement is that these chosen edges be disjoint, i.e., that they each connect to distinct nodes in $L$. The essence of Theorem 3.13 is that the existence of such $R$-matchings can be detected locally. That is, $R$-matchings exist precisely when $R’$-matchings exist for all finite $R’ \subseteq R$.

Line 352-354: At the level of information, it would indeed be equivalent to combine steps 2 and 3 (or even to remove step 2 entirely). We mention step 2 primarily to emphasize that the learner has access to all unlabeled datapoints in $S$, call them $S_X$. This allows it to, for instance, construct the OIG of $H$ on $S_X$ after step 2 and orient it optimally, and then use the information of step 3 to get a prediction for the unlabeled test point. This is often how transductive learning is described in the literature, but in the absence of step 2 the learner could equivalently just wait until after step 4 to see all unlabeled data, construct the OIG, orient it, and perform inference all in one go. It is primarily a matter of preference/exposition.

Local transductive sample complexity: Excellent question. One-inclusion graphs and the transductive model are in some sense intrinsically local, as they only study the performance of learners on finite regions of the domain. (As opposed to the PAC model, which considers performance with respect to distributions with possibly infinite support.) Our results can be viewed as stating that the transductive model can be made even more local by restricting focus to finite regions of the domain and only finitely many behaviors on the domain. (I.e., to finite subgraphs of one-inclusion graphs.) To our knowledge, this is as local a perspective as one could hope to achieve.

The $\gamma$-OIG is defined and analyzed using largely the same perspective as for classical OIGs. There, the key difference is that the loss function is not the 0-1 loss but rather the absolute loss on the interval $Y = [0, 1]$. The key idea behind the $\gamma$-OIG is to turn this continuous loss into a discrete one by thresholding: losses below $\gamma$ are rounded to 0 and losses above $\gamma$ are rounded to 1. ($\gamma$ is thought of as a scale parameter ranging from 1 to 0.) This permits the authors to simplify the problem and to use ideas and techniques from discrete math (e.g., graph theory).

Thank you again for your detailed questions and comments! They will all be taken into account to improve the paper.

We thank the reviewer for their time and attention in reviewing the paper.

We note that $H|_S$ is the collection of all functions in $H$ restricted to the datapoints $S$. Indeed $H|_S$ can easily be infinite, in which case it is not a finite projection of $H$. We instead refer to the finite subsets of $H|_S$ as the finite projections of $H$, as we describe at the beginning of Section 1.1 (lines 45-48). We will clarify this point further in the next version of the paper; thank you.

The reviewer’s restatements of Theorems 3.6 and 3.8 are indeed correct. We will clarify the meaning of “$H$ is learnable in the realizable case with transductive sample function $m$” alongside Definitions 2.1-2.3 to avoid confusion. (In particular, it means that $H$ has a realizable transductive learner with sample complexity at most $m$.)

We agree that discussing error rates and sample complexities is equivalent, across both the transductive and PAC models. We chose to phrase our results in terms of sample complexities rather than error rates, in part arbitrarily and in part as it is roughly a convention in the community. We indeed could have equivalently phrased all results in terms of error rates throughout the paper.

Thank you again for your comments on improving the exposition of the paper – they are very helpful and will be taken into account as we update the paper!

We thank the reviewer for their time and attention in reviewing the paper.

The authors do not convinced me about the importance of this model. The authors should explain why this model is important, what it explains that other models does not (i.e., the classical PAC learning).

We argue that the transductive model is itself influential and insightful. Moreover, it is intimately related to the PAC model such that even those readers with an exclusive attachment to the PAC model would derive insight from our work. We tried to communicate both of these points in the paper, though acknowledge that there is room for improvement, as the review notes. We elaborate on both of these points below in order to address the reviewer’s concern.

1. The transductive approach to learning has a rich and deep history, dating to the seminal works of Vapnik and Chervonenkis ‘74 and Vapnik ‘82. Our particular model was first used by Haussler et al. ‘94 and has since been employed to derive numerous insights for PAC learning as well as other models of learning. We note that it offers several advantages relative to the PAC model, including its emphasis on labeling a single datapoint at test time, rather than emitting an entire hypothesis (i.e., the inductive vs. transductive approaches to learning). This perspective has seen renewed interest in recent years with the rise of such techniques as few-shot learning, which focuses on a model’s performance at a single test point (e.g., “Realistic Evaluation of Transductive Few-Shot Learning”, NeurIPS 2021). In fact, by focusing solely on prediction, the transductive model emphasizes improper learning by default, a notable advantage given the necessity of improper learning in settings such as multiclass classification (Daniely and Shalev-Shwartz 2014). Furthermore, the transductive model is closely related to the one-inclusion graph, a combinatorial technique that has given rise to fundamental insights across learning theory, including the first dimension to characterize multiclass learnability (the DS dimension; Brukhim et al. 2022), the first minimax optimal robust learner (via the global one-inclusion graph; Montasser et al. 2022), and the first dimension to characterize learnability for realizable regression (the \gamma-OIG dimension; Attias et al., 2023) — to name only a few examples. Lastly, the transductive model is arguably conceptually simpler than the PAC model, as it merely requires learners to attain error less than epsilon on each sample, and avoids any involvement of marginal distributions, integrability issues, confidence parameter delta, etc.

2. The transductive model bears intimate connections to the PAC model. We note that any results concerning transductive sample complexities automatically transfer to the PAC model in a black-box manner with only minor losses (lines 60-65, Lemma 3.19). Consequently, our work demonstrates an almost-exact form of compactness for sample complexities holding broadly in the PAC model (Corollary 3.20). We believe that this makes our work of central interest even to those who have an exclusive attachment to the PAC model of learning.

I do not believe that this submission is relevant to the neurips community, maybe the authors should consider submitting to COLT.

We respectfully disagree with the reviewer on this point. We note that NeurIPS has published several works analyzing the transductive model and the one-inclusion graph in recent years, many of which our paper cites and builds directly upon. These include “A trichotomy for transductive online learning” (NeurIPS 2023), “Optimal learners for realizable regression: PAC learning and online learning” (NeurIPS 2023), “Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization” (NeurIPS 2023), and “Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes” (NeurIPS 2022), among others.

Perhaps more importantly, we believe that our work demonstrates a far-reaching structural property of sample complexities which would be of interest to many members in the NeurIPS community, both theoretically inclined and beyond. We believe that collectively, our results form an original and meaningful contribution to learning theory, as requested in NeurIPS’ call for papers.