Transductive Learning is Compact
Authors: Julian Asilis
Siddartha Devic
Shaddin Dughmi
Vatsal Sharan
Shang-Hua Teng
Venue: NeurIPS 2024 poster (2024)
Keywords: Sample Complexity
Compactness
One-Inclusion Graphs
Metric Space
Transductive Learning
PAC Learning
Primary area: learning_theory
TL;DR: We demonstrate that the transductive sample complexity of learning a hypothesis class is exactly equal to the sample complexity of learning its most difficult "finite projection," for a wide range of losses.

Abstract: We demonstrate a compactness result holding broadly across supervised learning with a general class of loss functions: Any hypothesis class $\mathcal{H}$ is learnable with transductive sample complexity $m$ precisely when all of its finite projections are learnable with sample complexity $m$. We prove that this exact form of compactness holds for realizable and agnostic learning with respect to all proper metric loss functions (e.g., any norm on $\mathbb{R}^d$) and any continuous loss on a compact space (e.g., cross-entropy, squared loss). For realizable learning with improper metric losses, we show that exact compactness of sample complexity can fail, and provide matching upper and lower bounds of a factor of 2 on the extent to which such sample complexities can differ. We conjecture that larger gaps are possible for the agnostic case. Furthermore, invoking the equivalence between sample complexities in the PAC and transductive models (up to lower order factors, in the realizable case) permits us to directly port our results to the PAC model, revealing an almost-exact form of compactness holding broadly in PAC learning.

Transductive Learning Is Compact
Julian Asilis USC asilis@usc edu
Siddartha Devic USC devicGusc.edu
Shaddin Dughmi USC shaddinQusc.ed edu
Vatsal Sharan USC vsharanQusc.edd edu
Shang-Hua Teng
USC shanghua@usc. edu
Abstract
We demonstrate compactness result holding broadly across supervised learning with general class of loss functions: Any hypothesis class H. is learnable with transductive sample complexity m precisely when all of finite projections are learnable with sample complexity m. We prove that this exact form of compactness holds for realizable and agnostic learning with respect to any proper metric loss function (c.g.. any norm Id) and any continuous loss compact space (e.g., cross-entropy, squared loss). For realizable learning with improper metric losses, we show that exact compactness of sample complexity can fail, and provide matching upper and lower bounds of a factor of 2 on the extent to which such sample complexities can differ. We conjecture that larger gaps possible for the agnostic case. Furthermore, invoking the equivalence between sample complexities in the PAC and transductive models (up to lower order factors, in the realizable case) permits us to directly port our results to the PAC model, revealing an almost-exact form of compactness holding broadly in PAC learning.
1 Introduction
Compactness results in mathematics describe the behavior by which, roughly speaking, an infinite system can be entirely understood by inspecting its finite subsystems: An infinite graph is k-colorable precisely when its finite subgraphs are all k-colorable [De Bruijn and Erdös, 1951], an infinite collection of compact sets in IR has non-empty intersection precisely when the same is true of its finite subcollections, etc. In each case, compactness reveals a profound and striking structure, by which local understanding of problem immediately yields global understanding.
We demonstrate that supervised learning in the transductive model enjoys such structure. First, let us briefly review the transductive model, close relative of the PAC model. In the realizable setting with a class of hypotheses H S y it defined by the following sequence of steps:
1. An adversary selects unlabeled data S (#1 .ff......2. .n) ) E X and hypothesis h e H.
2. The unlabeled datapoints S are displayed the learner.
3. One datapoint z; is selected uniformly random from S. The remaining datapoints
S_ = (æ1..... 24-1, I..
and their labels under are displayed the learner.
4. The learner prompted to predict the label of æ; i.e., h(xz).
The expected error incurred by the learner over the uniformly random choice of x; is its transductive error on this learning instance, from which one can easily define the transductive sample complexity of learner and of hypothesis class.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Notably, transductive learning, originally introduced by Vapnik and Chervonenkis [1974] and Vapnik [1982], is fundamental approach to learning with deep theoretical connections the PAC model. We study the transductive model as employed by the pioneering work of Haussler et al. [1994], who introduced the celebrated one-inclusion graph (OIG) to study transduction and used it to derive improved error bounds for VC classes. More recently, transductive learning and OIGs have been used to (among other work) establish the first characterizations of learnability for multiclass classification and realizable regression [Brukhim et al., 2022, Attias et al., 2023], to prove optimal PAC bounds across several learning settings [Aden-Ali et al., 2023b], and to understand regularization in multiclass learning [Asilis et al., 2024]. (See also Daniely and Shalev-Shward [2022], Montasser et al. [2022]. Aden-Ali et al. [2023a].) The transductive model also naturally generalizes to the agnostic setting, much like PAC learning, as articulated by Asilis et al. [2024].
[2014], Alon et al.
1.1 Contributions
Our results involve comparing a hypothesis class H. to its "finite projections." Formally, for a hypothesis class H S y² and any finite collection of unlabeled data S C X, we refer to the finite subsets of HI s as finite projections of H. Note that H is being "made finite" at two levels: first by restricting its functions to a finite region S C X' of the domain, and second by passing to a finite subset of g. Thus, any finite projection of H. e.g. F C H|s, is necessarily a finite set of behaviors, [F] < co, regardless of whether H|s in its totality is infinite (as may easily occur if y is infinite).
As our cornerstone result, we demonstrate in Theorem 3.6 that for the case of supervised learning with a large class of proper' metric loss functions (including any norm on Rd or its closed subsets; see Definition 3.2) a class H. can be learned with transductive sample complexity m precisely when the same is true of all its finite projections. In fact, in Theorem 3.7 we extend our results to arbitrary continuous losses on compact metric spaces, e.g., cross-entropy loss on finite-dimeniionll probability spaces and squared lg loss compact subsets of Rd, For learning over arbitrary label spaces, we demonstrate in Theorems 3.8 and 3.9 that compactness fails: for realizable learning with metric losses, provide matching upper and lower bounds of factor of 2 the extent to which such transductive sample complexities can differ. Our lower bound transfers directly to transductive learning in the agnostic case, for which we conjecture that larger gaps in sample complexity are possible.
We stress that our compactness results are exact in the transductive model, avoiding dilution by asymptotics or even by constants. In addition, there is a growing body of work relating sample complexities in the transductive and PAC models, by which our results directly transfer in black-box manner [Asilis et al., 2024, Aden-Ali et al., 2023b, Dughmi et al., 2024]. Notably, for realizable learning with any bounded loss, PAC sample complexities differ from their transductive counterparts by most a logarithmic factor in 6, the confidence parameter. Combined with our results, this reveals an almost-cxact form of compactness for realizable PAC learning, as we describe in Section 3.4.²
Our results hold for improper Iearners, i.c., learners that are permitted to emit a predictor outside the underlying class H. Curiously, compactness of sample complexity can be seen to fail strongly when one requires that learners be proper, using the work of Ben-David et al. [2019]. This demonstrates a structural difference between proper and improper learning; see Appendix B for further detail.
Our compactness results are underpinned by generalization of the classic marriage theorems for bipartite graphs which may be of independent mathematical interest. The original marriage theorem, due to Philip Hall [Hall, 1935], articulates a necessary and sufficient condition for the existence of a perfect matching from one side of finite bipartite graph to the other. Subsequently. Marshall Hall [Hall Jr, 1 1948] extended the same characterization, referencing only finite subgraphs, to infinite graphs of arbitrary cardinality, provided the side be matched has finite degrees the characterization being false otherwise, as can be seen by a simple countable example. This characterization therefore serves as a compactness result for matching on such infinite graphs. The proof of M. Hall features an involved analysis of the lattice of "blocking sets", and invokes the axiom of choice through Zorn't 's lemma. Simpler proofs have since been discovered: a topological proof by Halmos and Vaughan
'We warn that we will shortly be overloading the term "proper", as we discuss proper metric spaces and proper functions between metric spaces. We also note that our notion of properness is unrelated to losses which incentivize predicting the true probability. from e.g. Blasiok al. [2023]. (And unrelated to proper improper learners; we consider improper learners throughout the paper. which can emit predictors outside the class H.) 'Note too that any future improvements to the connections between the PAC and transductive models, whether in the realizable or agnostic settings, will be automatically inherited by our results in a black-box manner.

---

[1950] which invokes the axiom of choice through Tychonoff's 's theorem, and an algebraic proof by Rado [1967] which also uses Zorn's lemma. At the heart of our paper is a compactness result (Theorem 3.3) for variable-assignment problem which generalizes both supervised learning and bipartite matching: one side of bipartite graph indexes infinitely many variables, the other indexes infinitely many functions that depend on finitely many variables each, and the goal is to assign all the variables in a manner that maintains all functions below a target value. Our proof draws inspiration from all three of the aforementioned proofs of M. Hall's theorem, and goes through Zorn's 's lemma.
1.2 Related Work
The transductive approach to learning dates to the work of Vapnik and Chervonenkis [1974] and Vapnik [1982], and has inspired a breadth of recent advances across regression, classification, and various other learning regimes; see our introduction for brief overview. Regarding transductive sample complexities, Hanneke et al. [2023] recently demonstrated a trichotomy result for optimal transductive error rates in the online setting of Ben-David et al. [1997]. In contrast, we focus on the classical (batch) setting, as described in Section 2.2.
Perhaps most related to the present work is Attias et al. [2023], which introduces the 7-OIG dimension and demonstrates that it characterizes learnability for supervised learning problems with pseudometric losses. Notably, this is the first general dimension characterizing learnability across essentially the entirety of supervised learning. The y-OIG dimension itself establishes a qualitative form of compactness as it is defined using only the finite projections of class - but we note that it has not been shown to tightly characterize the sample complexity of learning. Furthermore, it is analyzed only for realizable learning, which is in general not equivalent to agnostic learning (e.g.. for regression). Our work, in contrast, establishes exact compactness for the sample complexity of transductive learning for both the realizable and agnostic settings, with respect to a general class of loss functions. Moreover, in Appendix B we extend our results to certain cases of distribution-famil learning, including realizable learning of partial concept classes.
2 Preliminaries
2.1
Notation
For a natural number n E N. [m] denotes the set {l,...,n}, For a predicate P, [P] denotes the Iverson bracket of i.e. [P] when P is true and otherwise. When 7 is set, <ow denotes the set of all finite sequences in Z, i.e., zKw = - Z For a tuple S = (Z1...., zn). we use S-; to denote S with its ith entry removed, i.e., S_, = (2)..... 2 21+1 .,,)
2.2 Transductive Learning
Let us recall the standard toolkit of supervised learning. A learning problem is determined by a domain X. label space y. and hypothesis class H C y The clements of H. are functions X' + Y;; such functions are referred to as hypotheses or predictors. Learning also requires a loss function E (or d) from y/ x y' to R20. which often endows )' with the structure of a metric space. Throughout the paper, we permit X' to be arbitrary. A labeled datapoint is a pair (r, y) E X' x y and an unlabeled X. A training set, training sample, is tuple of labeled datapoints <w A learner is a function from training sets to predictors, i.e., A : (X' x y)vw + y
datapoint is an element
S E (X x <)) Definition 2.1. Realizable transductive learning is defined as follows: An adversary selects s= (x:)sE(n) E X2 and a hypothesis h E H. The unlabeled datapoints are displayed to the learner. Then one datapoint H, is selected uniformly at random from S, and the remaining datapoints and their labels under h are displayed to the learner. Lastly, the learner is prompted to predict the label of Ii i.e., h(xz).
We refer to the information of hS,h) as in Definition 2.1 an instance of transductive learning, and to F, as the (randomly selected) test datapoint and S_, the (randomly selected) training datapoints. The transductive error incurred by learner A on an instance (S, h) is its average error over the uniformly random choice of test datapoint, i.e.,
Trans (A) S.S.
1
Σ M()) :E|m]
3

---

where A(S-s,h) h) denotes the output of A on the sample (zy, h(zz))) rates and sample complexity.
Having defined transductive error, it is natural define
Definition 2.2. The transductive error rate of a learner A for H is the function EA, N - IR T.Taa defined by (n. supsex", bEH SSh (A). The transductive sample complexity of a learner
A for H is the function ITTrans, ( min(m E N EA,z((1) Se, Vm'' 2 m].
Definition 2.3, The transductive error rate of a class H is the minimal error rate attained by any of its learners, i.e., (H(n) = inf [A.H(n). The transductive sample complexity TTTaans : RR N of H is the function mapping to the minimal m for which En I c.for all m 2 m. That is,
TTTrans, (t) = min/m EN =x((m)) S 6, Vm' 2 m).
We say that H. is learnable in the realizable case with transductive sample function when (V S mle) for all
Informally, agnostic transductive learning is the analogue in which the adversary is permitted to label the data in S arbitrarily, and in which the learner need only compete with the best hypothesis in H. We defer the formal definition Section 3.3.
3 Compactness of Learning
We present the central result of the paper in this section: the transductive sample complexity of learning a compact property of a hypothesis class. Section 3.1 we study compactness of realizable supervised learning over proper loss functions, and demonstrate strong compactness result: class H learnable with transductive sample complexity m if and only if all its finite projections are learnable with the same complexity. In Section 3.2 we examine the case of realizable supervised learning over improper loss functions and prove a negative result: the previous compactness result no longer holds in this more general setting. Nevertheless, compactness, up to a factor of 2, for (improper) metric losses. Moreover, we show exact compactness for the special case of the (improper) 0-1 loss funetion, i.e., multiclass classification possibly infinite label sets. Notably, this recovers M. Hall's classic matching theorem for infinite graphs [Hall Jr, 1948] corollary to our central result. In Section 3.3 examine analogues of our results for agnostic learning, and in Section 3.4 we transfer our results to the PAC model via standard equivalences, obtaining approximate compactness of sample complexities. Due space constraints, we defer an extension of our results to distribution-famll PAC learning to Appendix B.
demonstrate approximate form of
arbitrary,
3.1 Realizable Learning With Proper Loss Functions
We first consider the case of loss functions é y y + E2 defined on proper metric space y Definition 3.1. A metric space is proper if its closed and bounded subsets are all compact.
related notion is that of a proper map between metric spaces.
Definition 3.2. A function f X Y between metric spaces is proper if it reflects compact sets, Le., f- (U) C X is compact when U C Y is compact.
We remark that proper spaces sometimes referred Heine- -orel spaces, and that their examples include d endowed with any norm, all closed subsets of I2 (under the same norms), and all finite sets endowed with arbitrary metries. Further discussion of proper metric spaces is provided in Appendix A. The central technical result of this subsection is a compactness property concerning assignments of variables to metric spaces that maintain family of functions below a target value
Theorem 3.3. Let L be collection of variables, with each variable E E L taking values in metric space Mt. Let R be a collection of proper functions, each of which depends upon finitely many variables in L and has codomain Rzo- Then the following conditions are equivalent for any >> O.
1. There exists an assignment of all variables in L which keeps the output of each function R greater than
2. For each finite subset R' of R, there exists an assignment of all variables in L, which keeps the output of each function r' E R'' greater than

---

Proof. (1.) = (2.) is immediate. Before arguing the reverse direction. some terminology: partial assignment of variables is an assignment of variables for a subset of L. A partial assignment is said to be completable with respect to R' C R if its unassigned variables can all be assigned so that all functions r' Rt are kept below 6. A partial assignment finitely completable if is completable with respect to all finite subsets of R. This is a pointwise condition: the completions are permitted to vary across H's subsets.
Lemma 3.4. Given a finitely completable partial assignment with an unassigned variable, one such variable can be assigned while preserving finite completability.
Proof. Fix any unassigned variable E L: we will assign it while preserving finite completability. For each set R' S R. let (&) consist of those assignments of that preserve completability with respect to R'. By the assumption of finite completability, we have that Nr (f) is non-empty for all finite R'. We claim furthermore that Nw (f) is compact for finite R'.
To why, let R'I k and let f,..... en be the variables in L upon which the functions in R' depend. Suppose without loss of generality that & = & and that nodes li+1,-... Lm have already been assigned. Consider the function fr : [T Me, - IR. mapping assignments of the E,...., l to the outputs they induce on the functions in R'. (Notably, this includes the assignments already made for li+1...., -m-) As the functions in R' are proper, including when fixing some of their inputs, fR' is as well.
Thus f ([0, el*) is compact, as its projection onto its first coordinate. That set is precisely RR (f), demonstrating our intermediate claim. We thus have a family of compact, non-empty sets I (Nr (f)= : Rt' C R. [R'| < oo). Note that finite intersections of elements are non-empty, as n NR. (1) 2 NU. R, (4) + 0.
In metric spaces, an infinite family of compact sets has non- non-empty intersection if and only if the same holds for its finite intersections. Thus, by compactness of each element of Z. the intersection across all of I is non-empty. That is, there exists an assignment for l which is completable with respect to all finite subsets of R. The claim follows.
We now complete the argument using Zorn's lemma. Let be the poset whose elements are finitely completable assignments, where Φ1 S Φ2 if Φ2 agrees with all assignments made by Φ1 and perhaps assigns additional variables. Note first that chains in P have upper bounds. In particular, let C P be a chain and define de to be the "union" of assignments in C, i.e., Φc leaves l unassigned if all o E C leave unassigned, otherwise assigns é the unique element used by assignments in
Clearly de serves as an upper bound of C, provided that dc E P. To see that de E P, fix a finite set Rt C R. R' is incident are those which are assigned by 9e, and let Φ1,..., Φ; E C be assignments which assign (i.e., do not leave free) the respective nodes f,....,y, Ly Then, C is totally ordered, must be that one of $1...., O; assigns all of the variables fI,...,&, L. That is, there exists Φj E C which agrees with de in its action on E,,..., ......,,u, em As dj E P, it must be that Φj is completable with respect Rt' Then de is also completable with respect to R', as R' depends only upon f
finite collection of nodes in L., say f1,..., lm Suppose f1...., l
Thus, invoking Zorn's 's lemma, P has maximal element Φmax- By Lemma 3.4, it must be that Φmax does not leave a single variable unassigned, otherwise could be augmented with an additional assignment. There thus exists total assignment that is finitely completable. As it has free variables, it must indeed be maintaining all functions in R below e. The claim follows.
Remark 3.5. A corollary to Theorem 3.3 is that the same claim holds when the target values vary over the functions r E R, as translations and scalings of proper functions Z ++ R. are proper.
5

---

L
(0,0, ?)
R
(1,0, ?)
(0, 0,,
(0, 1,)
(1, 0,000)
(0,
(1,3,0)
(0, 1,0)
(2,0,0)
(3,
Figure 1: Depiction variables and functions which model transductive learning, for sequence of unlabeled datapoints |S| = 3 such that H|s contains the behaviors (0, O, 0), (1, 0, 0). and (0, 1,0). Arrows denote functional dependence, i.e., each r R depends upon its incident variables.
Theorem 3.6. Let X be an arbitrary domain, y label set, and d loss function such that (Y, d) is proper metric space. Then the following equivalent for any H. S y and m: R=0 - N:
is learnable in the realizable case with transductive sample function m. 2. For any finite X C X and finite H'' C H|x, H' is learnable in the realizable case with transductive sample function m.
(2.) is immediate. For the reverse direction, fix an and set n m(c). Then fix a sequence of unlabeled datapoints S E X" suffices to demonstrate that a transductive learner for H on instances of the form {(S, ((S,)))eR can be designed which attains error 6.
Proof. (1.)
We will capture the task of transductively learning H on such instances by way of a certain collection R of functions and L of variables. Each variable E E will be permitted take values in 3, while each function r E R depends upon exactly n variables in L and outputs values in R20- More precisely, let f = H|s and L = -s- H.s. These serve merely as representations for the functions in R and variables in L, not their true definitions (which will be established shortly). Note now that by suppressing the unlabeled datapoints of S, we can equivalently represent elements of R sequences in ) and elements of T. as sequences in (> U (?))" )" In this view, each element of L. is precisely an element of R which had exactly one entry replaced with a "?" See Figure
Now, to model transductive learning, fix element E R represented by (VI,..., Vn) )m Then we will define r to be a function depending upon the variables f,,...,y, en E L,, where & (Wi...., -.- ?, Vi+1...... Mn). Given assignments for each of the variables E,, f,.... Ln as values in y -semnntically, completions of their "?" entries - the node then outputs the value L. d(yi, L,). The two erucial observations the action of a learner responding to a query at test time, and the output of node r equals the error of learner when is the ground truth.
as follows: assignment of each e L corresponds precisely to
Thus, remains show that the variables in L can all be assigned so as to keep the outputs of the functions in R less than The condition (2.) grants that this is true for each finite collection of functions R' C R. Now note that the functions r E are proper, as each such r continuous and reflects bounded sets, and as y itself is proper. Invoke Theorem 3.3 to complete the proof.
Theorem 3.6 establishes an exact compactness in learning with respect a flexible class of metric loss functions. One may note, however, that some non-metric losses are of central importance to

---

machine learning, including the squared error on compact subsets of R (which violates the triangle inequality) and the cross-entropy loss for fiiieedimennsinal distributions (which not symmetric). We now provide a modified form of Theorem 3.6 which captures these loss functions, in which the loss function by is permitted to differ from the underlying metric d on V. (F.g., such that d the usual Euclidean norm on a compact subset y of IRd and Ey is any continuous loss function.)
Theorem 3.7. Let X be an arbitrary domain, (V, d) compact metric space, and H. S yy* hypothesis class. Let by y x x - R>0 be loss function employed for learning that is continuous with respect to the metric d. Then the following are equivalent for any m: Rz0 + N:
1. H is learnable in the realizable case with transductive sample function m.
2. For any finite X C X and finite Ht' C H|x, H' is learnable in the realizable case with transductive sample function m.
Proof. We adopt precisely the perspective of Theorem 3.6, seeing transductive learning modeled as variable assignment problem with the same variables L and functions Rt. To invoke Theorem 3.3, it remains only to show that the functions r E are proper. First note continuous function from a compact space to R is automatically proper, as closed subsets of compact sets are compact. Now recall that each E a sum of scaled copies of by with one input fixed. As each such function is continuous, r itself is continuous and thus proper.
3.2 Realizable Learning With Improper Loss Functions
It is natural to ask whether the requirement that Y' be a proper metric space is essential Theorem 3.6 or merely an artifact of the proof. We now demonstrate the former: for arbitrary metric losses, the error rate of learning H. can exceed that of all its finite projections by factor of 2. Recall that EH N + Rzo denotes the transductive error rate of learning a class H. i.c., {x(n) denotes the error incurred by an optimal learner for H on (worst-case) samples of size n.
Theorem 3.8. There exists a hypothesis class H C DN metric loss function d on V, and N such that for any finite X C X and finite H' C Hlxx, (n(n) 2 2 [n)(
Let us describe the main idea of Theorem 3.8, whose proof is deferred to Appendix C.I. The crucial step lies in the creation of the label space y = R U S, where R is an infinite set whose points are all distance 2 apart, and S is an infinite set whose elements are indexed by the finite subsets of R, e.g.. as in S E S for finite R' C R. For all such R', define sre to be distance 1 from the elements of R', distance 2 from the other elements of R, and distance from all other points in S. Then y indeed forms metric space, and it is straightforward to see that, for instance, the class of all functions from a one-element set to y is more difficult to learn than its finite projections (equivalently, finite subsets).
We now prove a matching upper bound to Theorem 3.8, demonstrating that a factor of 2 is the greatest possible gap between the enror rate of H and its projections when the loss function is metric.
Theorem 3.9. Let y be label set with metric loss function and H C yx a hypothesis class. Fix : + R20. and suppose that for any finite X C X and finite H' C H.x, H!' has transductive error rate Ew E. Then H has transductive error rate &H < E.
The proof of Theorem 3.9 is deferred to Appendix C.2, but let us briefly sketch the main idea. Fix N, S. X and set {(n). Consider again the collection of functions R HHls and variables L= -s H/ Sr as described in the proof of Theorem 3.6. By the premise of the theorem, for any finite subset R' C Rt there exists an assignment of variables L > )' which maintains all functions in R' below e. Each such assignment induces an apportionment of error to each function in R², i.c., vector of length with positive entries summing to For variables ,,...., Ln. this apportionment tracks the contribution of each & to the output of r. The central technical step of the proof is to demonstrate that one can assign apportionments to each node r E R such that any finite subset of the apportionments can be satisfied by an assignment of variables - Y. Then let & = (J/1...., V/-1,, ?, Vi+1.... ..., Un) be a variable. We assign to the value ő such that the function (g) : Vr f. 1:-1..... yn) has minimal budget apportioned to f, among all such ÿ. From an invocation of the triangle inequality, this learner at most doubles the output of any r E R.
H'' depending upon
Recall from Section 3.1 that proper metric spaces are sufficiently expressive to describe many of the most frequently studied label spaces, including R2 (equipped with any norm) and its closed subsets.
7

---

What, then, is typical example of a label space which fails to be proper? Perhaps the most natural example is multiclass classification over infinite label sets, i... 3' equipped with the discrete metric (V- v²) = y * v']. We will now demonstrate, however, that the particular structure of multiclass classification can be exploited to recover an exact compactness result in the style of Theorem 3.6. Notably, we do so by invoking M. Hall's classic matching theorem for infinite graphs, which for good measure we show to be a special case of our Theorem 3.3.
Definition 3.10. Let G (L R. E) be a bipartite graph. An R-matching set E' S of disjoint edges which covers R. A graph with an R-matching is said to be R-matchable.
Definition 3.11. A bipartite graph G = (LUR, E) is finitely R-matchable ffr each finite subset R' of R, there exists a set E' S E of disjoint edges which covers R'.
M. Hall's theorem states that an infinite bipartite graph G is R-matchable if and only if it is finitely R-matchable, provided that all nodes R have finite degree. Before proving M. Hall's theorem by way of Theorem 3.3, we establish an intermediate lemma.
Lemma 3.12. Ler G = (LU R. E) be a bipartite graph such that all nodes r R have finite degree and G is finitely R-matchable. Then there exists collection of edges E' S E such that G' (LU R, E') is finitely R-matchable and all nodes in G' have finite degree.
The proof of Lemma 3.12 deferred to Appendix C.3, but its intuition fairly simple: by P. Hall's theorem, G' is finitely R-matchable precisely when Hall's condition holds, i.e., |N((R)) 2 |R'| for all finite R' S [Hall, 1935]. Thus any & E T. which not incident to a Hall blocking set can be removed from G' while preserving Hall's condition and finite R- m--macchbbility Proceeding in this way, nodes can be removed until each remaining point, f's incident edges can be safely restricted to those which are incident with Ry, finite set.
is contained in Hall blocking set Ry At this
We now prove M. Hall's theorem as a consequence of our Theorem 3.3.
Theorem 3.13 (Hall Jr (1948]). Let G (L U R. E) be bipartite graph in which all nodes E R have finite degree. Then G has an R-matching if and only if it is finitely R-matchable.
Proof. The forward direction is clear. For the reverse, suppose G is finitely R-matchable. Then may assume as consequence of Lemma 3.12 that the nodes in L have fimite degree as well. Let us think of each node f E L variable residing in the discrete metric space on its neighbors. We will also think of each node E R as a function of its neighbors, which outputs the number of neighbors that have not been assigned is proper, and furthermore that any function out of such space is automatically proper. Then invoke Theorem 3.3 with e(r)
itself. Note that the discrete metric space on finitely many elements
deg(r) to complete the proof. (See Remark 3.5.)
Let C y be a classification problem, i.e., employing the 0-1 loss function. Then the following are equivalent for any m: R>0 + N:
Corollary 3.14.
1. H is learnable in the realizable case with transductive sample function m.
2. For any finite X C X and finite Ht' C H|x, H' is learnable in the realizable case with transductive sample function m.
Proof. Certainly (1.) - (2.). Then suppose (2.) and fix S E X Now consider the bipartite graph G (LU R. E) with R H|s. = Us*ss, H|s and where edges in E connect functions agreeing on common inputs. Then a learner for instances of the form {(S, h)) he amounts precisely to choice of incident node (equivalently, edge) for each f E L. Furthermore, such learner attains error I precisely when its selected edges contribute indegree at least d = n (1 - c) to each node in R. Using a splitting argument (i.e., creating d copies of each node in R), this is equivalent to asking for an R-perfect matching in graph which, by (2.), is finitely m-matchable. Note that each node in R has degree oc and appeal to Theorem 3.13 to complete the proof.
8

---

3.3 Agnostic Learning
Our discussion thus far has restricted attention to realizable learning: what can be said of the agnostic case? In short, all results from Sections 3.1 and 3.2 can be claimed for agnostic learning (with nearly identical proofs), with the exception of Theorem 3.9. To begin, let us briefly review transductive learning in the agnostic case. See Asilis et al. [2024] or Dughmi et al. [2024] for further detail. Definition 3.15. The setting of transductive learning in the agnostic case is defined as follows:
1. An adversary selects a collection of labeled datapoints S E (X x y)Ew.
2. The unlabeled datapoints in S are all revealed to the learner.
3. One labeled datapoint (Ii, We) is selected uniformly at random from S. The remaining labeled datapoints S_, are displayed to the learner.
4. The learner is prompted to predict the label of 24-
Notably, transductive learning in the agnostic case differs from the realizable case in that the adversary is no longer restricted to label the datapoints in S using a hypothesis H. To compensate for the increased difficulty, and in accordance with the PAC definition of agnostic learning, a learner is only judged relative to best-in il-ss performance across H. Formally,
1 Σ e(h(z)),))) y.).
Trans (A)
Σ ((A(S_.)(z)) u) VE(M)
inf
NER T2
sE(m)
Furthermore, one can use nearly identical reasoning as in the proofs of Theorems 3.6 and 3.7 to see that agnostic transductive learning described by system of variables T. and functions R. In particular, set R = )" and let L C (> U {?})" contain all sequences with exactly one "?" Then a function r (y) ......... yr.) depends upon the variables (Li)siin) where and rel,...,, f.) = - Eie(m) dy(y,, f.) inf 7 Σie(n) ((h(x))y)))
(yl...... Vi-1, ?, B441..... Bn)
Now, as in the realizable case, a learner A corresponds precisely to an assignment of each variable é E L to value in y², and A incurs agnostic transductive error at most if and only if the outputs of all nodes in R are maintained below c. Under the conditions of Theorems 3.6 or 3.7, exact compactness of sample complexity thus comes as an immediate consequence of Theorem 3.3 and our preceding discussion. Furthermore, when y bears a discrete metric, learning reduces to an assignment problem in graphs, and exact compactness follows from a straightforward splitting argument applied to M. Hall's matching theorem (as in Corollary 3. 3.). We thus have the following theorem.
Theorem 3.16. Let y and the loss function satisfy the conditions of Theorem 3.6, Theorem 3.7, or Corollary 3.14. Then the following conditions are equivalent for any H. S y and m: R - N:
1. H is learnable in the agnostic case with transductive sample function m.
2. For any finie X C. X and finite H' S Hlx, H' is learnable in the agnostic case with transductive sample function m.
Regarding improper metric losses, note that our lower bound from Theorem 3.8 transfers directly to the agnostic case, it established for hypothesis class for which agnostic learning is precisely as difficult as realizable learning. We conjecture that larger differences in such error rates - perhaps of arbitrarily large ratio are possible for the agnostic case.
3.4 PAC Learning
Though our results have thus far been phrased in the language of transductive learning, we now demonstrate that they may be easily extended (in an approximate manner) to Valiant's celebrated PAC model [Valiant, 1984]. The PAC model makes use of probability measures D over X' Y, for which the true error incurred by predictor h is defined as LD (h) = E< ((h(z),)) v).
Definition 3.17. Let D be collection of probability measures over X' x y and H S y hypothesis class. learner A is a PAC learner for H. with respect to if there exists a sample function m (0, 2 + N such that the following holds: for any D E D and e,8 E (0, 1)², a D-i.i.d. sample with |S| 2 mn(e, )) such that, with probability at least 1 - over the choice of S,
Ln(A(S)) < inf Lp (h) +

---

Agnostic PAC learning refers to the case in which ID consists of all measures over X x V, and realizable PAC learning to the case in which == {D: miny Ln(h)= 0}.
Definition 3.18. The sample complexity of learner A with respect to hypothesis class H. mPPA,. (0, 1) + N, is the minimal sample function it atlains as a learner for H. The sample complexity of a class H. is the pointwise minimal sample complexity atlained by any of its learners, i.e, (E, 8) = minA MP,C,A(E,0).
As previously mentioned. transductive learning bears a close connection to PAC learning: see Asilis et al. [2024] and Dughmi et al. [2024] for further detail on their approximate equivalence.
Lemma 3.19 (Asilis et al. [2024, Proposition 3.6)). Let X be a domain, y a label set, and H S y hypothesis class. Fix loss function taking values in [0, 1). Then the following inequality holds for all 8 E (0, 1) and the constant 2 2.718:
MTrrans,7
e (E
66+ & mp.c,a((e s (m (E/2) log
We now follow through on porting our results from the transductive model the PAC model. The following is an immediate consequence of applying Lemma 3.19 to Theorems 3.9 and 3.7.
Corollary 3.20. Let X be domain, Y label set, and H. S y a hypothesis class. Suppose that the loss function & is bounded and satisfies either of the following conditions:
* E is a metric on V, or
. d) is compact metric space and is continuous with respect this topology.
Then if all finite projections of "H are learnable with realizable PAC sample function m (0, - N. H. is learnable with sample complexity ((m( 1e 1 l log(1/5))
Let us mention briefly that the connection between transductive learning and PAC learning may be as tight in the agnostic case as in the realizable case. Through a straightforward use of Markov's inequality and repetition argument, one can show that agnostic PAC sample complexities exceed transductive by at most a factor of 1/e, but this is an unimpressive bound.
Conclusion
In this work, we studied the conditions under which the sample complexity of learning a class H can be detected by examining its finite projections. Notably, we established exact compactness results for transductive learning with a broad class of proper or continuous loss functions, across both realizable and agnostic learning. Using bounds relating the transductive and PAC models, we were able to transfer many of our results (in an approximate form) to realizable PAC learning. We leave as an open problem whether compactness of agnostic transductive sample complexities can fail by more than a factor of 2 for arbitrary (improper) metric losses. Additional future work includes better understanding the relationship between the transductive and PAC models in the agnostic case, and examining compactness for loss functions which do not satisfy any of our properness, metric, or continuity conditions (though they may be of somewhat limited interest in learning theory). It would also be of interest to study the compactness of error rates in settings other than supervised learning, such online or unsupervised learning.
Acknowledgments and Disclosure of Funding
Julian Asilis was supported by the Simons Foundation and by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE- 184-1844487. Siddartha Devic was supported by the Department of Defense through the National Defense Science & Engineering Graduate (NDSEG) Fellowship Program. Shaddin Dughmi was supported by NSF Grant CCF. 2009060. Vatsal Sharan was supported by NSF CAREER Award CCF-2239265 and an Amazon Research Award. Shang-Hua Teng was supported in part by the Simons Investigator Award from the Simons Foundation. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and not necessarily reflect the views of any of the sponsors such as the NSF.
10

---

References
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. The one- inclusion graph algorithm is not always optimal. In The Thirty Sixth Annual Conference Learning Theory, pages 72-88. PMLR, 2023a.
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal pac bounds without uniform convergence. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203-1223. IEEE Computer Society, 2023b. 2
Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658-671. IEEE, 2022. 14
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In The Thirty Seventh Annual Conference Learning Theory. PMLR, 2024. 2, 9, 10,
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, and Grigoris Velegkas. Optimal learners for realizable regression: PAC learning and online learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. 3
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. Machine Learning, 29:45-63, 1997.
Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka, and Amir Yehudayoff.. Learnability can be undecidable. Nature Machine Intelligence, 1(1):44-44 48, 2019. 2, 14,
Gyora M Benedek and Alon Itai. Learnability with respect to fixed distributions. Theoretical Computer Science, 86(2):377-389, 1991. 13
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. When does optimizing proper loss yield calibration? Advances in Neural Information Processing Systems, 36, 2023. 2
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Ychudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943 925.9555555 IEEE, 2022. 2
Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR, 2014. 2, 14
NG De Bruijn and P Erdös. A colour problem for infinite graphs and problem in the theory of relations. Indigationes Mathematicae, 13:371-373, 1951.
Shaddin Dughmi, Yusuf Kalayci, and Grayson York. Is transductive learning equivalent to pac learning? arXiv preprint w:Xiv:2405.05/90 2024. 2, 10
P. Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26-30, 1935. doi: https://doi.org/100
http:///rrrrr..11//////s11111110 1112/jmm//11-00.7.22 2, 8, 18
Marshall Hall Jr. Distinct representatives of subsets. Bulletin of the American Mathematical Society,
54(100;922-926, 1948. 2, 4,8
Paul Halmos and Herbert Vaughan. The marriage problem. American Journal of Mathematics, 72(1):
214-215, 1950. 2
Steve Hanneke, Shay Moran, and Jonathan Shafer. A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 2023.
David Haussler, Nick I Littlestone, and Manfred K Warmuth. Predicting (0. 1)-functions on randomly drawn points. Information and Computation, 115(2):248-222 1994. 14
Tosca Lechner and Shai Ben-David Impossibility of characterizing distribution learning-a simple solution to long-standing problem. arXiv preprint arXiv:2304.08711 2023. 13
11

---

Omar Montasser, Steve Hanneke, and Nati Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. Advances Neural Information Processing Systems, 35: 37458-37477 2022. 2
Richard Rado. Note on the transfinite case of hall's theorem on representatives. J. London Math, Soc, 42:321-324, 1967.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 2711):1133411114 1984.
Vladimir Vapnik. Estimation of dependences based on empirical data: Springer series in statistics (springer series in statistics), 1982. 2,
Vladimir Vapnik and Alexey Chervonenkis. Theory of pattern recognition, 1974. 2, 3
Robert Williamson and Ludvik Janos. Constructing metrics with the heine-borel property. Proceed- ings of the American Mathematical Society, 100(3):67--773, 1987. 13
12

---

A Proper metric spaces
Several of our results concern proper metric spaces. Let us expand briefly upon this condition, and present an equivalent definition.
Definition A.I. A metric space (V,d) is proper if either of the following equivalent conditions hold:
1. For all VV. Y closed and bounded then it is compact.
2. For any y E V and 0, the closed ball B,(y) {u/ ey= d(y. v/) S compact.
Note that the conditions are indeed equivalent. That (1.) implies (2.) is immediate. Supposing (2.), note that any closed and bounded subset Y a closed subset of some closed ball, and thus compact.
We now discuss various sufficient conditions in order for a metric space to be proper.
Lemma A.2. Let (y, d) be a metric space. Any of the following conditions suffice to ensure that (Y, d) be proper metric space.
1. y is compact.
2. y is finite.
3. y is a closed subset of proper metric space.
Proof. y is compact, then its closed subsets are compact. J finite, then it compact, If ) is a closed subset of proper metric space y", then its closed and bounded subsets are compact in } and thus compact in y
Recall now that Rd endowed with the usual Euclidean norm proper metric space, owing to the Heine-Borel theorem. Invoking the equivalence of all norms on IR", it follows that R endowed with any norm enjoys the structure of proper metric space.
Corollary A.3. The following classes of metric spaces are proper:
1. All finite metric spaces.
2. All compact metric spaces.
3. IRd, with any norm.
4. Any closed subset of Rd, with any norm.
Regarding necessary conditions for propereess note that all proper metric spaces are complete. Thus subsets of Rd which are not closed will not be proper, e.g., O C RR. See, e.g., Williamson and Janos [1987] for additional discussion and properties of proper metric spaces, which sometimes referred to as Heine-Borel metric spaces.
B Distribution-famill Learning
The analysis of PAC learning with respect to more flexible distribution classes than the realizable and agnostic cases falls largely under the purview of distribution-familly learning [Benedek and Itai, 1991]. Formally, a problem in distribution-family learning of a class H C y is defined by a family of distributions Di over X, such that unlabeled datapoints are drawn from distribution D ID and labeled by hypothesis h E H. (in the realizable case) or arbitrarily (in the agnostic case).
Notably, distribution- family learning has infamously resisted any characterization of learnability, combinatorial or otherwise, for the 40 years since its inception. In fact, there is some evidence to suggest that no such characterization may exist [Lechner and Ben-David 2023]. Furthermore, it is setting in which uniform convergence fails to characterize learning, rendering ineffective many the standard and most celebrated techniques of learning theory.
Nevertheless, we now demonstrate that compactness sheds light on the problem of distribution-family learning, at least for the case of well-behaved distribution classes.
13

---

Definition B.1. A famity of distributions D over a set 2 is well-behaved whenever S = (Z1..... zn) lies in the support of some E ID, then SS), the uniform distribution over S, lies in ID well.
Definition B.1 is sufficiently flexible that we may apply it to distribution-famil learning with 2 X or to PAC learning over arbitrary distribution classes ID with 2 = X x y. Though may appear overly restrictive at first glance, note that well-behavedness is satisfied not only for ordinary PAC learning in the agnostic and realizable cases, but also for learning of partial concept classes in the realizable case [Alon et al., 2022] and for the EMX learning of though EMX learning is not presented as a supervised learning problem in Ben-David et al. [2019], it can be seen as a binary classification problem over domain X' for which H. consists of those functions outputting finitely many I's and ID contains all realizable, discrete distributions placing all y-mass on the label 1.
et al. [2019]. In particular,
Crucially, well well-behavedness permits us to study PAC learning by way of transductive error.
Proposition B.2. Let H C yd be hypothesis class and De a well-behaved family of distributions which are realizable (i.e., inf (h) = D'D E D). Fix a loss function taking values in [o, 1]. Then the following inequality holds for all e, E (0, 1) and the constant 2.718:
MT (c 8)) S MPAC.H
O H (c/2) logg(18)))
Proof. The proof is nearly identical to that of [Asilis et al., 2024, Proposition 3.6]. In particular, let mExp, H denote the sample complexity of learning H in the expected error regime (i.e., (E equals the number of datapoints needed to incur expected error most e). Then we have
EExp, H + 5) S mP.Ac. 6) S O (m (e log(1/5))-
The first inequality follows immediately from the fact that the loss function is bounded above by 1. The second inequality follows from a repetition argument, i.e., learner attaining expected error S e/2 on samples of size n can be boosted to attain expected error I with probability 2 1 1 8 by using an additional factor of (log(1 /8)) many samples, described in [Daniely and Shalev-Shwarde 2014].
We now show that mxxp. H (c) and MTrrns, (c) are essentially equivalent, i.e., that
mExp,H (c) S MTTrass x(() ())= S MExx,HH(/
The first inequality follows inequality from a standard leave-one-out argument of Haussler et al. [1994]. For the second inequality, let A be an optimal learner in the expected error paradigm, and note that a transductive learning instance S = (Iii, y: Jejj)) can be solved as follows: Given training set S-, and test point zj, return (z;), where T is sample of points drawn independently and uniformly at random from S_j- The crucial observation is that mimics an i.i.d. sample drawn from S, as such sample will happen to avoid x; with probability 2 1/c. Thus the transductive error of our described learner can exceed that of A by at most a factor of e.
Note that Proposition B.2 holds for the natural definition of transductive learning with respect to D. ie., in which the adversary must select a sequence of unlabeled datapoints S E X²" which lic in the support of some D DD. It is now immediate from the proof of Theorem 3.6 that distribution-fami learning is a setting in which the transductive sample complexity of learning is H equals the sample complexity of learning its most challenging finite projections. In the following, we let Dxxx S ID denote the distributions of D which place full measure on X X.
Theorem B.3. Let X be an arbitrary domain, y a proper metric space, and H S yxx a hypothesis class. Let ID be family of bell-behaved, realizable distributions. Then the following are equivalent for any m R500 + N:
1. H is learnable with respect to DD with transductive sample function
2. For any finite X C X and finite H' S Hlxx, H' learnable with respect DIx with transductive sample function m.
As in Section 3.4, Proposition B.2 applied to Theorem B.3 immediately yields an almost-exact form of compactness for distribution-family PAC learning with realizable and well-behaved distribution classes. This demonstrates that the learnability of even problems as exotic as EMX learning can be detected by examining all their finite projections, provided that restrictions are placed upon
14

---

learners. In Ben-David et al. [2019], however, learners were required to only emit hypotheses in H. Our work demonstrates that the nature of their undecidability result in which the learnability of a class H. is determined entirely by its cardinality, despite all its projections being easily learned. could otherwise not appear in supervised learning with metric losses.
C Omitted proofs
C.1 Proof of Theorem 3,8
Proof. Set X' N and let y be the metric space defined as follows. y R U S, where R is an infinite set whose points are all distance 2 apart. S is an infinite set whose points are indexed by fimite subsets of R. e.g., in sgr S for finite R' C R. For all such R', define sg. be distance from the elements of Rt, distance 2 from the other elements of R, and distance 1 from all other points in rnsitive-definite symmetric,
S.. Note that indeed forms a metric space as its distance function and only uses the non-zero values of and 2. (In particular, the triangle inequality is satisfied as an automatic consequence of the latter fact.) Now fix
R and & E N. Define H. S y to consist of all those functions which output 7 on all inputs > k. Notably, any h E H may take arbitrary values on æ k.
Let us first analyze the sample complexity of learning a finite projection of H. Fix finite X C X and finite H. H|x. Then, as and H'' are each finite, the images of all the H'' are contained in finite set Y' S V. Let Y' decompose as Y' = R' U.S. S' with R' S R, S' C S. Then the following learner attains error < on instances of size n.
A: (X' x y) yd
8R' x < k,
S - x +
x > k.
In particular, for any & S. k: and h E H', d(A(S)(=)) < 1, while for any x >> k: A(S) emits the correct prediction by definition of H. Furthermore, we may assume without loss of generality that transductive learning instances do not contain repeated datapoints, as these only lessen the difficulty of learning. Thus any sample S has at most & unlabeled datapoints [k:]. and the previous analysis demonstrates that H' be learned with error f when |S| n.
n
On the other hand, for the case of learning H. itself, there exist n such that the worst-case error incurred by any learner on |S| = n is at least 2k In particular, take 1. As y has radius 2 and transductively learning H. with n = is guaranteed to incur an error of at least 2 in the worst case. (That is, by taking S = {a} with k.) Thus, for n and any finite projection H' we have (n) < 1 and (x(n)) 2, and the claim follows.
n furthermore for any y y there exists y/ E y with d(y,
C.2 Proof of Theorem 3.9
Before commencing with the proof, let us establish some terminology and supporting lemma. Fix hypothesis class H along with E X and e > 0. Recall the collection functions It = H and variables L =-= H|s which capture the structure of transductive learning instances of the form {(S, h) Hev,, described in the proof of Theorem 3.6. In this setting, for any number > 0. we will let a-apportionment refer to a vector = .f,,...,,.. with x; 2 O and Σ z4 We may suppress a and refer simply to apportionments.
Given an a-apportionment v for a node r E R, we will say that an assignment of variables in L satisfies this apportionment if the output of as function decomposes according More explicitly, recall that r (y1...., yn) depends upon the variables (Li)aEjn) S L, where
e, = (yi..... 11-1, ?, ,e,....., yn) and
1 Σ d 4.)
r(e (n)=
=
n
Then assignment of variables (6i + y satisfies (#1...., x..) if ddy,,, 4.) x; for all i e [n). Intuitively, tracks the manner in which produces its output. Similarly, given
15

---

apportionments for various nodes in R, we say that a given assignment of variables satisfies the apportionments if it satisfies each of them at once.
With a slight abuse of terminology, we say that a node r E R without an apportionment is satisfied by an assignment of variables I. + 3' if its output is most under the assignment. There should be no risk of confusion, as it will always be clear whether a given node E R is endowed with an apportionment
not. In similar fashion to Theorem 3.6, we say a partial assignment of apportionments is an assignment of apportionments to subset of R. An assignment which happens be total is referred to as a total assignment of apportionments. A partial assignment Φ is satisfiable with respect to R' S R if there exists an assignment of variables L - y such that all nodes in R' are satisfied. (I.e., have their apportionments satisfied if equipped with one, and are otherwise simply maintained below e.) We say á is finitely satisfiable if it is satisfiable with respect to all finite subsets of R.3
Lemma C.1. Let X be domain, Y a metric space, and H C y hypothesis class. Fix S X and the corresponding collections of functions R = HIs and variables = = (t HIs Let 5 > O. If R is finitely satisfiable, when none of its elements are endowed with apportionments, then there exists total assignment of (c + 8) appooriionnsntss to which is finitely satisfiable.
Proof. We appeal to Zorn's lemma. The argument relies crucially upon the fact that any partial assignment of (E + -ppoorooooisn which is finitely satisfiable can augmented by assigning an additional apportionment to unassigned function in R.
Lemma C.2. Let & be a partial assignment finitely satisfiable and leaves fanction in R unassigned. Then one such unassigned variable can receive an (e + opapporrion while preserving finite satisfiabllity
( apppottiiones to R which is
Proof. Fix an unassigned variable r E R. along with a finite collection of nodes R' S R. Let R' = Rg U R1, where the nodes in Rg are unassigned by & (i.e., need only be maintained below c). and those in R₁ are assigned by ø (i.e., need be maintained below + 8 and furthermore have their apportionments respected). Let A(R') denote the collection of variable assignments + y which satisfy all nodes in R' along with r. By the supposition that ø is finitely satisfiable, A(R') is non-empty.
Now let D(R') denote all e-apportionments for r that are satisfied by an assignment in A A(R'). Informally, these are the e-apportionments with which we could endow r, if we only needed to consider the nodes R'. Then let cI))(R)) denote the closure of & R') in RR,"" and consider the family of sets
I = (cI( R'S S R. [R)
Each set I E I is compact, as it is closed and bounded. Furthermore, finite intersections of such sets are non-empty, as
k cl( 2 ((R)) 2
k
R T
n
R i=1
Then there exists an e-apportionment E ranges over all finite subsets of R. As we took the closures of the sets ((R',. this does not suffice to guarantee us that O (RR)) is non-empty. Let us now increase each of the entries of v by an arbitrarily small amount, say 8/n, and call the resulting (c + 8) appoortiionnentt v".
N (cI(((R)) where the intersection
For any finite R' C Rt recall that v E cl()(R))), meaning there exist assign- ments satisfying R' and r which induce e-apportionments on r of arbitrarily small proximity to v. As v" strictly exceeds v in each coordinate, then there exists an assignment satisfying R' which also satisfies v²_ And R' was chosen arbitrarily, so the claim follows.
NNotbbly, this is pointwise condition, not a uniform one. The satisfying assignments are permitted to vary across the finite subsets of R.
16

---

Consider now the poset P whose elements are finitely satisfiable partial assignments of (e + 6)- apportionments R. The partial ordering such that Φ1 S Φ2 if Φ2 agrees with all assignments of apportionments made by Φ1 and perhaps assigns additional apportionments. It is straightforward to see that chains P have upper bounds: let C - P be a chain and define de to be the "union" of assignments in C, i.e., de leaves R unassigned if all & E C leave r unassigned, otherwise it assigns r to the unique apportionment used by the assignments in C.
Certainly de serves as an upper bound for C, provided that Φc E P. To see that de E P. fix a finite set R' C R. Suppose S S R' the collection of nodes in R' which receive (e + 6) apportionmennt from Φc. Each s E S receives an apportionment from a o, E C. Then, as C' is chain and {Ø, hes S C is finite set, there exists an s' E S with 6.. max ( JEs. By the definition of the partial order with which we endowed P. S then agrees exactly with de when restricted to the set R'. As Or E P, R' satisfiable with respect to Øs' and thus satisfiable with respect to dç. As R was selected arbitrarily, we have that de is finitely satisfiable, meaning Φe E P and chains indeed have upper bounds.
Then, invoking Zorn's lemma, P contains a maximal element d By Lemma C.2, it must be that émax does not leave any function in R unassigned, otherwise it could be augmented with an additional apportionment, contradicting maximality. Thus there exists a total assignment of (E + 00) aappoortionnennss which is finitely satisfiable, completing the argument.
We are now equipped to prove Theorem 3.9 itself.
N, and let {(n). We will exhibit learner A for H attaining error at most 2e + 5 on samples of size n, for arbitrarily small 0. To this end, fix one such 5 > 0 and an S E X and recall the system of functions R and variables T. which capture learning on transductive instances of the form functions in R as R H|s and the variables in L. L Us -=--=nn 1Hlss- As described in the proof of Theorem 3.6, we may suppress the unlabeled datapoints in the definitions of R and S, and represent each E R as an element of y and each l as an element of (Y {?})r with exactly one "?", Recall too that each function r E R, represented by (yI,..., Mn) E )"m depends upon the variables en E L, where
Proof. Let H. be in the theorem statement, fix
{(S, )) That is, we represent the
4 (V1.... ... U1-1, Me.1............................ -.a)
Upon assigning each such variable & to an element of y (semantically, a completion of its "?" entry corresponding to query at test time) the function outputs the value
n
dy(Ut.
n
The central observation is that defining a learner A for H which attains error < 2c + 5 amounts precisely to assigning each variable in L to value in Y such that the functions in R are all maintained below 2c + 8. By the premise of the theorem, this collection of functions and variables is finitely satisfiable. That is, for each finite R' C R. there exists an assignment of all variables L + 3 such that all functions in It' are maintained below e. Then, by Lemma C. there exists an assignment of (E + ( apporiinttssstttts to each function in R which is finitely satisfiable.
Now fix a node E L: we will demonstrate how to assign it to a value of y. Note that & influences a potentially infinite collection of functions (rahee S R. Each such function has an apportionment of error for L. Call these values {Ar Recall that each node for i E I computes its error incurred on é relative to a label yi E y. Now choose an index N E 7 such that An inf, X S 8/3. We then set f = yN-
In order to analyze this assignment, fix an arbitrary E I and consider the set R' (r,, ry). By finite satisfiability of our system of (E + a/33)-appo there exists an assignment of variables
*Strictly speaking, the definition of error rate involves an infimum, meaning we are only guaranteed that the functions in Rt can be maintained arbitrarily close to e. It is straightforward to see that this suffices for our purposes, however, Lemma C.I results in the addition of an arbitrarily small term anyway.
17

---

L + satisfying the functions in R'. Let y be the value of variable E in this assignment. We have:
dy(e, un) = dy(uN, 9i)
S dy(uN. + d(y', vi)
S AN + A,
- inf A + 3
+ x
2 2 +
Now assign all variables in L in this manner, and consider an arbitrary node E R with error apportionment .,,..., An for each of the variables upon which it depends. Then, using the above analysis, r evaluates at most
8 2 A
(e+ +
8 + 2- 0
22
3
completing the argument.
C.3 Proof of Lemma 3.12
Proof. Fix a bipartite graph G (LUR, E) such that all nodes in R have finite degree and G is finitely R-matchable. We will demonstrate the existence of subgraph G' = (LU R, E') of G such that G' is finitely R-matchable.
First note that is finitely R-matchable if and only if P. Hall's condition holds for all finite subsets R' of R. That is, if and only if (R)) 2 [ where (R') denotes the set of neighbors R' has in L. by Hall [1935]. We refer to a finite subset R' of R as a blocking set if [N) = R', |. We say
node& & E L is contained in blocking set if there exists blocking set R' such that & (RR)..
Now consider all nodes in L; if there exists node E L such that & not in any blocking set, then can be removed from L while preserving Hall's condition in the graph (i.e., while preserving finite R--atchabilitty. Repeatedly removing nodes from
this way and applying Zorn's 's lemma, we arrive at collection of nodes L' C L such that Hall's condition is preserved and each node in L is contained in a blocking set. Call the resulting graph G'.
Now fix a node e L' and pick a blocking set T C R containing / E L'. We remove all edges incident to é which are not incident to R'. Let us demonstrate that the remaining graph G" remains finitely R-matchable, i.e., satisfies Hall's condition. Suppose not, so that there exists finite set C violating Hall's condition. Then, as G' satisfies Hall's condition, it must be that is incident to S in G' but not in G". Furthermore, it must be that S is a blocking set in G', as was R. Then consider the set U in G". We have:
[N(SUT) IN(S) U(T))
< [(SS) +
< [N(S)]++ + (N(T) (4)
< |7|+
<|SU
producing contradiction with Hall's condition for G'. Note that the third line makes use of the fact that ((S)) ()TSS) as clearly [N (N((S) 2 (N(TT))) and furthermore E (N(T) \ (N) owing to the fact that is incident to both and S but not due to a node in T n (otherwise l would have remained incident to S in G").
We are thus permitted to perform the operation on any single node L' to make its degree finite while preserving Hall's condition. As any failure of Hall's condition finitely many nodes in L', it follows that we can do so for all nodes of L' concert. The resulting graph is subgraph of G which is finitely R-matchable and for which all nodes have finite degree, as desired.
be detected by way of
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are formally proven within the body of the paper (including the appendix).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: All our results are theoretical, and stated with their full set of required assump- tions. Absent such assumptions, make it clear that our results do not apply. (E.g., by conjecturing that larger gaps between sample complexities may be possible in the agnostic case.)
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All our results are stated with their full set of assumptions and equipped with complete proof (in some cases, deferred to the appendix).
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips..
casssoiiniyyyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. htc//ublicggguiiiice
(CodeSumiission
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / //w.ries..../// httpppubiicBthicsGuutttie
Question:
Answer: [Yes]
Justification: Our research does not involve datasets human participants. Furthermore, the research does not directly contribute to the development of new models or technology.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
There is no societal impact of the work performed, as it is purely theoretical in nature. Our research does not directly contribute the development of new models or technology.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does release, directly contribute the release of, any data models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does not include the involvement of any human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work does include the involvement of any human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "8fKCGJGM6s", "reviewer": "Reviewer_Rcdh", "summary": "This document explores the concept of compactness in the context of transductive learning, a model closely related to the PAC model in supervised learning. The authors demonstrate that for a broad class of loss functions, a hypothesis class can be learned with a specific transductive sample complexity if and only if all its finite projections (subsets of the hypothesis class restricted to finite data sets) can be learned with the same sample complexity. This result holds for realizable and agnostic learning settings, with specific bounds provided for realizable learning with improper metric losses. The authors highlight the significance of this “exact” compactness result, as it avoids dilution by asymptotics or constants. They further connect their findings to the PAC model, revealing an almost exact form of compactness for realizable PAC learning. The paper also discusses the implications of proper versus improper learners, demonstrating a structural difference in terms of compactness. The paper's core lies in generalizing the classic marriage theorems for bipartite graphs, which provides a foundation for the compactness results.", "questions": "This paper presents a compelling theoretical analysis of compactness in transductive learning. However, as a reviewer, I have some questions and suggestions for the authors to consider:\n\n1. Generalizability of Compactness Results:\n\nQuestion: The paper focuses on a broad class of loss functions. Could the authors provide more concrete examples of loss functions that fall within this class and those that do not? This would help readers understand the practical implications of the results.\n\nSuggestion: It would be beneficial to briefly discuss the results' limitations, particularly in terms of the specific loss functions that are not covered.\n\n2. Implications of Proper vs. Improper Learners:\n\nQuestion: The paper mentions a structural difference in compactness between proper and improper learners. Could the authors provide a more detailed explanation of this difference? How does it impact the practical application of the results?\n\nA dedicated section or subsection discussing the implications of proper vs. improper learners for compactness would be very valuable.\n\n3. Practical Applications:\n\nQuestion: While the paper focuses on theoretical results, discussing potential practical applications of the compactness results would be helpful. How can these results be used to design more efficient transductive learning algorithms?\n\nSuggestion: A brief discussion of potential applications, even if speculative, would enhance the paper’s relevance and impact.\n\n5. Future Directions:\n\nQuestion: The paper mentions a conjecture about more significant gaps between sample complexities in the agnostic case. Could the authors elaborate on this conjecture and discuss potential approaches to proving it?\n\nSuggestion: A section on future directions, outlining potential extensions and open problems, would add value to the paper.", "limitations": "While the paper does not include a dedicated “Limitations” section, the authors have effectively integrated discussions of limitations throughout the paper, particularly in the introduction and conclusion. \n\nThe authors have adequately addressed the limitations of their work. They clearly state the assumptions required for their theoretical results and acknowledge that these results may not hold in more general settings. Notably, they acknowledge the potential for larger gaps between sample complexities in the agnostic case, demonstrating their awareness of the field's challenges. They also discuss the limitations of their approach in terms of its applicability to different learning settings.\n\nHowever, the paper does not discuss any potential negative societal impacts of their work. This is understandable, given that the paper focuses on theoretical results in transductive learning, which is a relatively abstract field. However, it would be beneficial for the authors to briefly consider the potential applications of their work and any potential negative societal impacts that might arise.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper presents a compelling and rigorous analysis of compactness in the context of transductive learning. The authors contribute significantly by demonstrating an “exact” compactness result, which avoids the limitations of asymptotic or constant-based approaches. This result is particularly noteworthy for its broad applicability to a comprehensive class of loss functions and its relevance to both realizable and agnostic learning settings.\nHere’s a breakdown of the paper’s strengths across different dimensions:\nOriginality: The paper’s originality is a key strength, stemming from its unique approach to proving compactness in transductive learning. The authors' generalization of the classic marriage theorems for bipartite graphs serves as a foundation for their key results, introducing a novel framework that establishes a precise connection between the learnability of a hypothesis class and the learnability of its finite projections, a result that has not been previously demonstrated.\nQuality: The paper is of high quality, exhibiting rigorous mathematical proofs and clear exposition. The authors' careful definition of their assumptions and provision of complete proofs for all their theoretical results demonstrate a thoroughness that ensures the validity and reliability of their findings.\nClarity: The paper is well-written and easy to follow. The authors effectively introduce the concepts of transductive learning and compactness, providing clear definitions and explanations. The structure of the paper is logical, guiding the reader through the key results and their implications.\nSignificance: The paper’s importance lies in its contribution to our understanding of the fundamental principles of transductive learning. The “exact” compactness result provides a powerful tool for analyzing the learnability of hypothesis classes in this setting. This result can potentially impact future research in transductive learning, particularly in semi-supervised and active learning areas.\nOverall, this paper presents a valuable and original contribution to the field of transductive learning. Its rigorous analysis, clear exposition, and significant implications make it a strong candidate for publication.", "weaknesses": "This paper presents a strong theoretical contribution, but it would benefit from a more nuanced discussion of its limitations and potential applications.\n\nWeaknesses:\n\nLimited Scope of Applications: While the paper establishes a powerful compactness result for transductive learning, it doesn’t delve into the practical implications of this finding. The authors could strengthen their work by exploring how this result translates to real-world scenarios. For instance, they could discuss specific transductive learning algorithms where this compactness property is particularly relevant or analyze the impact of different loss functions on the sample complexity.\n\nLack of Empirical Validation: The paper focuses solely on theoretical analysis. While this is valuable, it would be significantly enhanced by including empirical studies to demonstrate the practical relevance of the compactness results. Even a small-scale simulation could provide valuable insights into the behavior of transductive learners under different conditions.\n\nComparison to Existing Work: The paper could benefit from a more thorough comparison to existing work on compactness in learning theory. While the authors mention the PAC model, they could provide a more detailed discussion of how their results relate to existing compactness results in that framework. This would help clarify the novelty and significance of their contribution.\n\nDiscussion of Assumptions: The paper clearly states its assumptions, but it could benefit from a more in-depth discussion of their limitations. For example, the authors could explore the impact of relaxing the assumption of realizable learning or discuss the potential implications of using improper learners.\n\nActionable Insights:\n\nExpand on Applications: The authors should dedicate a section to discussing potential applications of their compactness results in real-world transductive learning problems. This could involve analyzing specific algorithms, exploring the impact of different loss functions, or discussing the implications for different data distributions.\n\nInclude Empirical Studies: Even a small-scale simulation could provide valuable insights into the practical relevance of the compactness results. This would strengthen the paper’s impact and demonstrate the applicability of the theoretical findings.\n\nStrengthen Comparison to Existing Work: The authors should provide a more detailed comparison to existing work on compactness in learning theory, particularly in the context of the PAC model. This would help clarify the novelty and significance of their contribution.\nDiscuss Assumption Limitations: The authors should dedicate a section to discussing the limitations of their assumptions. This could involve exploring the impact of relaxing the assumption of realizable learning or discussing the potential implications of using improper learners.\n\nBy addressing these points, the authors can significantly enhance the impact and relevance of their work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t6JhxYyoDo", "reviewer": "Reviewer_7sdt", "summary": "This work studies the transductive learninng model. In this model, given  a domain $X,Y$ and $H\\subset Y^X$ the adversary choses data $(x_i,y_i)$ (in the realizable setting the adversary can chose the labels after the reveal to the learner). The adversary then uniformly at random hides one data point.  The goal of the learner is to use the remaining samples to predict the hidden label. The authors first show a compactness result showing that if all the finite subsets $X'$ are learnable in the projected class, i.e., $H|X'$ with sample complexity $m$ then the same is true for the whole class. They provide a similar result for the agnostic case. Finally, the authors present a result connecting transductive learning with PAC learning.", "questions": "See 1 in weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This work provides some fundamental results for the transductive learning.  This work is well written.", "weaknesses": "1. 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). \n2. I do not believe that this submission is relevant to the neurips community, maybe the authors should consider submitting to COLT.\n3.Furthermore, I believe that more results are needed to make this a complete submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and attention in reviewing the paper. \n\n> 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).\n\nWe 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. \n\n1. 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. \n\n2. 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. \n\n> I do not believe that this submission is relevant to the neurips community, maybe the authors should consider submitting to COLT. \n\nWe 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. \n\nPerhaps 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oL3jkvsJwy", "reviewer": "Reviewer_B4fj", "summary": "The paper studies transductive learning with general real-valued loss functions. The paper shows that:\n(1) for proper metric loss functions and continuous loss functions defined on compact spaces, the sample complexity of (realizable and agnostic) transductive learning a class H is exactly the same as the sample complexity of learning \"finite projections\" of H.\n(2) for improper metric loss functions: there is a tight gap of 2. \n(3) extensions of the above to the PAC learning model.", "questions": "See comments above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think that these are nice generic results that contribute to the literature on transductive learning. Effectively, the results seem to suggest that for classes of loss functions considered in this paper, it suffices to focus attention on constructing transductive learners for finite subsets of the hypothesis class H. \n\nThe result where there is a gap of 2 (Theorem 3.8 and 3.9) is particularly interesting.", "weaknesses": "Below, I include some comments that may help improve the paper when addressed. \n\nGiven that the main results of the paper deals with a class H and \"finite projections\" of H, I think that it is important to formally define and explicitly write down what \"H|_S\" is. Furthermore, given that the label space Y may be infinite, H|_S may be infinite as well, in the sense that we have infinitely many projections of H onto S. I think that it is important to clarify this point, and I find it a bit misleading to refer to H|_S as a \"finite projection\".\n\nThe definition of transductive learning (Def 2.1, 2.2, 2.3) when unpacked boils down to defining transductive learning with respect to any n, S \\subseteq X^n, and any H|_S. So, with this in mind, when looking at Theorem 3.6 and 3.8, it seems like they can be reduced to the following:  \nFor any n, and any S \\subseteq X^n,\n1. H|_S is learnable with error rate epsilon.\n2. For all (finite) H' \\subset H|_S, H' is learnable with error rate epsilon. \n\nWhat I am trying to highlight is that the results seem to be establishing equivalence between transductive learning the (potentially) infinite H|_S and transductively learning the finite subsets of H|_S. I think the authors should carefully clarify what \"H is learnable in the realizable case with transductive sample function m\" means. This should be included with the current Def 2.1-2.3. \n\nAdditionally, it seems that talking about error rate in transductive learning instead of sample complexity makes more sense, because as the paper defines the model (Def'n 2.1 and line 25), the adversary chooses n. So, one can just focus on smallest achievable error rate as a function of n.\n\n------------------------------------------------------------\n\nBased on authors' rebuttal, I raise my score to 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and attention in reviewing the paper. \n\nWe 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. \n\nThe 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$.) \n\nWe 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. \n\nThank 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!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gxFLMLFEYX", "reviewer": "Reviewer_JpD2", "summary": "The paper looks at the question of whether or not the transductive sample complexity is compact in the sense that the transductive sample complexity globally can be deduced from understanding the tranductive sample complexity of finite instances of transductive learning. More formally transdictive learning is the setting where the learner is revealed a labelled dataset $S_i$ with one variables $x_i$ missing and is then querried to predict the label of the  $x_i$, where all the labels $y_1,\\ldots,y_n$ are determined by some $h\\in\\mathcal{H}$ i.e. $y_{j}=h(x_j)$. The goal is now create a learned $A$ which takes as input the $S_i$ and $x_i$ and for some loss $L: \\mathcal{Y}\\times \\mathcal{Y}\\rightarrow R_{0\\geq }$,  minimize $L(A,S,h)=\\sum_{i}^{n} L(A(S_i,x_i),h(x_i))$ for any $h\\in \\mathcal{H}$ and $S\\subset \\cup_{i=1}^{\\infty}\\mathcal{X}^{i}$. This can also be seen as a game where a adversary picks $h\\in\\mathcal{H}$ and $S\\subset  \\cup_{i=1}^{\\infty} \\mathcal{X}^{i} $ and then look at the expected value of the loss of a learner which is given $S_i$ and propmt the label of $x_i$ for a random $i\\sim |S|$. The sample complexity of transductive learning is now for $\\varepsilon$ defined as\n\n $$m(\\varepsilon)=\\min\\{m\\in\\mathbf{N}: \\inf_{A} \\sup_{h\\in\\mathcal{H},S\\in\\mathcal{X}^{m}} L(A,S,h)\\leq \\varepsilon\\}$$\n\n\n\nThe paper shows that the transductive sample complexity is compact in the following sense: For suitable loss functions(metric losses, contious losses on compact spaces, the zero one loss) the transductive sample complexity of a hypothesis class $\\mathcal{H}$ $m()$ is the same as for any finite $X\\subset \\mathcal{X}$ and finite $H'\\subset \\mathcal{H}|_{X}$ having transductive sample complexity $m()$. They also show this for the agnostic setting of transductive learning, and distribution-families and furthermore show how PAC-learning can be studied from a point of view of finite projections of $\\mathcal{H}$. The authors also give an example of where the transductive sample complexity is not compact - but close to.", "questions": "Line 48: Why is $\\mathcal{H}_{S}$ nessarily finite? What if $\\mathcal{Y}$ is infinite?\n\\newline\n\nLine 174-175: In the definition of completable partial sisignment: Is it that there exist an assignment of the unassigned variables such that for all $r\\in R'$ this assignment is such that $r$ is less than $\\varepsilon$ or is it for all $r\\in R'$ there exists and assigment of the unassigned variables such that $r$ is less than $\\varepsilon$?\n\nLine 195: Why isn't it $|R'|<\\infty$ instead of $|R|\\leq \\infty$ so excluding $=$? \n\nLine 207: Do you have to be in $\\mathcal{P}$ to be an upper bound?\n\nLine 212-213: Why isn't: That is, there exists $\\phi_{j} \\in C$ which agrees with $\\phi_{C}$ in\nits action on $l_{1}, \\ldots, l_{i}$. As $\\phi_{j}\\in P$, it must be that $\\phi_{j}$ is completable with respect to $R'$ .i.e. there exists assignments to $l_{i+1}\\ldots,l_{m}$ \"such that $\\leq \\varepsilon$\", but since $l_{i+1},\\ldots,l_{m}$ are free variables of $\\phi_{C}$ and $\\phi_{C}$ upper bound $\\phi_{j}$ so especially agree $\\phi_{j}$ on $l_{1},\\ldots,l_{i}$ the variables $l_{i+1},\\ldots,l_{m}$ can also be assigned such that $\\phi_{C}$ is\nalso completable with respect to $R'$ with the same assignment of the variables $l_{i+1},\\ldots,l_{m}$ as $\\phi_{j}$. Sorry if it is saying the same.\n\nLine 216: total in what sense? \n\nTheorem 3.6: Can you please provide the set of variables $L$ and $R$ in the proof of Theorem 3.6?(Formally)\n\nLine 244: Why is the $\\inf$ always attained? \n\nLine 246: Why does $r$ reflects bounded sets- because it is a function of a norm on $\\mathcal{Y}$ - so cant be to fare $(O(\\varepsilon))$ from the fix argument - i.e. in a bound ball around that?\n\nLine 331: The condition about disjointness in a R-matching I struggle with - could you try to explain why each $R$ only has one $l$ insident, when it has a degree larger than $1$?\n\nLine 352-354: Out of curiosity, why is it that 2 and 3 are not combined?  \n\n(not a very concrete question and out of curiosity so if time is limited not need to be answered): The finding is also very broth and theoretical (a strength). I am curious if the idea of studying the transductive sample complexity \"locally\" instead of \"globally\" have been used before in the analysis of the transductive sample complexity - the authors meantions in the related work section the $\\gamma-OIG$ - is the analysis of $\\gamma-OIG$ for instance done in this way.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: \n\nThe paper states that they are the first to discover exact connection of the compactness of transductive sample complexity in the realizable and agnostic setting. \n\n\nQuality and Clarity: \n\nThe paper is well written and things are nicely defined and explained. \n\nSignificance: \n\nThe idea about connecting tranductive sample complexity seems novel and interesting.", "weaknesses": ".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and attention in reviewing the paper. We will address your questions in order.\n\nLine 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. \n\nLine 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.\n\nLine 195: That is a typo, the inequality should be strict – thank you! \n\nLine 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$. \n\nLine 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.\n\nLine 216: Total in the sense of assigning *all* variables, i.e., not leaving any variables unassigned. We will clarify this in the paper. \n\nTheorem 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)$. \n\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)$. \n\nLine 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. \n\nLine 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.)\n\nLine 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$. \n\nLine 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. \n\nLocal 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.  \n\nThe $\\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). \n\nThank you again for your detailed questions and comments! They will all be taken into account to improve the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors show a "compactness" result for transductive learning for a range of settings and loss functions. Roughly speaking, they show the sample complexity of transductive learning is m iff it is m for all of its "finite projections" (which means to characterize sample complexity it is enough to look at finite subsets of the class). "Compactness" is a rather mathematical concept and is a bit far from usual NeurIPS papers. However, the reviewers found the techniques and results interesting and relevant to the theory community. As such, I also recommend acceptance.

Reviewer Rcdh's comment were not used in the decision making by the AC.
Decision: Accept (poster)