A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning
Authors: Yingzhen Yang
Venue: ICML 2025 poster (2025)
Keywords: Concentration Inequality
Sampling Without Replacement
Transductive Local Rademacher Complexity
Transductive Learning
Primary area: theory->learning_theory
TL;DR: We present a new concentration inequality for the supremum of the empirical process associated with sampling without replacement, and apply our new concentration inequality to prove sharper generalization bound for transductive kernel learning.

Abstract: We introduce a new tool, Transductive Local Complexity (TLC), to analyze the generalization performance of transductive learning methods and motivate new transductive learning algorithms. Our work extends the idea of the popular Local Rademacher Complexity (LRC) to the transductive setting with considerable and novel changes compared to the analysis of typical LRC methods in the inductive setting. While LRC has been widely used as a powerful tool in the analysis of inductive models  with sharp generalization bounds for classification and minimax rates for nonparametric regression, it remains an open problem whether a localized version of Rademacher complexity based tool can be designed and applied to transductive learning and gain sharp bound for transductive learning which is consistent with the inductive excess risk bound by (LRC). We give a confirmative answer to this open problem by TLC. Similar to the development of LRC, we build TLC by first establishing a novel and sharp concentration inequality for supremum of empirical processes for the gap between test and training loss in the setting of sampling uniformly without replacement. Then a peeling strategy and a new surrogate variance operator are used to derive the following excess risk bound in the transductive setting, which is consistent with that of the classical LRC based excess risk bound in the inductive setting.
As an application of TLC, we use the new TLC tool to analyze the Transductive Kernel Learning (TKL) model, and derive sharper excess risk bound than that by the current state-of-the-art. As a result of independent interest, the concentration inequality for the test-train process is used to derive a sharp concentration inequality for the general supremum of empirical process involving random variables in the setting of sampling uniformly without replacement, with comparison to current concentration inequalities.

A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning
Yingzhen Yang'
Abstract
result of independent interest, the concentra- tion inequality for the test-train process is used to derive a sharp concentration inequality for the general supremum of empirical process involv- ing random variables in the setting of sampling uniformly without replacement, with comparison current concentration inequalities.
We introduce new tool, Transductive Local Complexity (TLC), to analyze the generaliza- tion performance of transductive learning meth- ods and motivate new transductive learning al- gorithms. Our work extends the idea of the popular Local Rademacher Complexity (LRC) (Bartlett et al., 2005) to the transductive setting with considerable and novel changes compared to the analysis of typical LRC methods in the inductive setting. While LRC has been widely used as a powerful tool in the analysis of in- ductive models with sharp generalization bounds for classification and minimax rates for nonpara- metric regression, it remains open problem whether localized version of Rademacher com- plexity based tool can be designed and applied to transductive learning and gain sharp bound for transductive learning which is consistent with the inductive excess risk bound by (LRC) (Bartlett et al., 2005). We give a confirmative answer this open problem by TLC. Similar to the devel- opment of LRC (Bartlett & Mendelson, 2003), we build TLC by first establishing a novel and sharp concentration inequality for supremum of empirical processes for the gap between test and training loss the setting of sampling uniformly without replacement. Then a peeling strategy and surrogate variance operator used de- rive the following excess risk bound in the trans- ductive setting, which is consistent with that of the classical LRC based excess risk bound in the inductive setting. As an application of TLC, we use the new TLC tool to analyze the Transduc- tive Kernel Learning (TKL) model, and derive sharper excess risk bound than that by the cur- rent state-of-the-art (Tolstikhin et al., 2014). As
1. Introduction
We study transductive learning in this paper, where the learner has access both labeled training data and un- labeled test data, and the task is to predict the labels of the test data. Obtaining tight generalization bound for transductive learning is an important problem in sta- tistical learning theory. Tools for inductive learning, such as Rademacher complexity and VC dimension, have been used for transductive learning, including empirical risk minimization, transductive regression, and transduc- tive classification (Vapnik, 1982; 1998; Cortes & Mohri, 2006; El-Yaniv & Pechyony, 2009). On the other hand, it is important to employ localized version of Rademacher complexity, such as Local Rademacher Complexity (LRC) (Bartlett et al., 2005), to obtain sharper generation bound for transductive learning, such as (Tolstikhin et al., 2014).
The classical work (LRC) (Bartlett et al., 2005) presents the following sharp bound for the excess risk of empirical risk minimizer î for inductive learning follows: for every x 0, with probability at least 1 exp(-x).
Excess Risk of f& e Fixed Point of the Sub-Root
Functions for Certain Empirical Process + x
(I)
where θ only hides constant factor, and N is the size of the training data. Given the fact that LRC is capable of achieving various minimax rates for M-estimators in tasks such as nonparametric regression in the inductive regime, we propose to solve the following interesting and important question for LRC based transductive learning:
"chooo of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA. Correspondence Yingzhen Yang <yingzhen.yangg asu.edu>>
Proceedings of the 1and International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
learning. Two novel technical elements are proposed to establish such sharp bound: (1) Transductive Local Com- plexity (TLC), which renders particularly sharp bound for transductive learning using the peeling strategy on the func- tion class with a new surrogate variance operator; (2) a novel and sharp concentration inequality for the bound for the supremum of the empirical loss which is the differ- ence between the test loss and the training loss, that is, suPREh (4% - (,), where H is a function class, 4% Lg are the test loss and the training loss associated with the predictor h E H. We refer to such empirical process as the test-train process in the sequel. It is remarked that the ex- isting local complexity based transductive learning method (Tolstikhin et al., 2014) is based on the bound for the supre- mum of the empirical process which is the difference be- tween the training test loss and the population loss, that is, supReR 2h: L, (h) s4Pheh 4%² L.. (h), where Ln (h) is the average loss of h on the entire data. Our novel concentration inequality for the test-train process presented in Theorem 3.1 is derived using new techniques based on a novel and interesting property of the test-train process involving random variables in the setting of sampling uni- formly without replacement and using the exponential ver- sion of the Efron-Stein Stein incquality ((Boucheron et al., 2003, Theorem 2)) twice to derive the variance of the test-train process. As an application of our sharp bound for excess risk for generic transductive learning, we derive a sharp ex- cess risk bound for transductive kernel learning by Theo- rem 4. in Section 4, which is sharper than current state-of- the-art (Tolstikhin et al., 2014).
Can we have a sharp LRC based generalization bound for the excess risk of transductive learning as that for the inductive setting?
The most relevant result which addresses the above open problem, to the best of our knowledge. is presented in (Tol- stikhin et al., 2014, Corollary 14), where the excess risk bound is given as the following inequality which happens with high probability:
Excess Risk of i
11 +
n
!
-Tm
Tu
11
m
m
Here rm and r are the fixed points of upper bounds for cer- tain empirical processes, where m, are the size of training data and test data. It is remarked that the above bound may diverge due to the undesirable factors of e/m and n u be- fore the fixed points. With m or u grows in a much slower rate than n with n = u + m, n/mm- m r + n/uu r'm may not converge to O. An example for the standard transductive kernel learning is given in Section As a result, there is a remarkable difference between the current oatt--oftthe-rr excess bound (2) in the transductive setting and the excess risk bound (1) in the inductive setting, and the latter always converges to 0 under standard learning models. We note that the excess risk bound in (Tolstikhin et al., 2014, Corol- lary 13) still diverges when m = of Vn) or u o(yn)) as m. u + OC.
Our main result is the following sharp bound for the excess risk below, such that with the same high probability as the inductive bound (I),
Second, as result of independent interest, we derive sharp concentration inequality for the general supremum of empirical process involving random variables (RVs) in the setting of sampling uniformly without replacement in The- orem 5.1 in Section 5. Our new concentration inequality is sharper than the two versions of the concentration inequal- ity in (Tolstikhin et al., 2014), and this result is based on our new concentration inequality for the test-train process introduced above.
Excess Risk of f (rr + Im +
x
(16) in Theorem 3.6.
u m min uu, m)
Here Tm, Tu, are the fixed points of upper bounds for certain empirical processes, which all converge to 0 with a fast rate as the case in the popular inductive learning mod- els. As a result of the sharp excess risk bound (3), we give a confirmative answer to the above open problem.
It is worthwhile to mention that concentration inequali- ties about sampling without replacement have been actively studied the literature (Bardenet Maillard, 2015; Tol- stikhin, 2017), including those on the multislice which are based on the modified log-Sobolev inequalities (Sambale & Sinulis, 2022). Compared to (Tolstikhin, 2017), our bound in Theorem 5.1 in Section 5 is sharper using similar ar- gument in Section 5. Furthermore, in contrast with our re- sults, the supremum of empirical process involving sam- pling without replacement is not addressed in (Bardenet & Maillard, 2015).
1.1. Summary of Main Results
Our main results are summarized as follows. This sum- mary also features a high-level description of the ideas we have developed to obtain the detailed technical results in Section 3.
First, we present the first sharp bound for the excess risk of empirical minimizer for transductive learning using lo- cal complexities based method inspired by LRC (Bartlett et al., 2005), and such bound (3) is consistent with exist- ing sharp bound for excess risk bound (1) for inductive
2

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
1.2. Notations
ment, and the remaining features are the test features de- noted by X. = X, X In the next paragraph we speci- ficy the sampling process of X,, of size u sampled uniformly without replacement. Then it follows by symmetry that X,m. are sampled uniformly from x, without replacement.
We use bold letters for matrices and vectors, and regular lower letter for scalars throughout this paper. The bold letter with single superscript indicates the corresponding column of a matrix, e.g. A; is the i-th column of matrix A, and the bold letter with subscripts indicates the corre- sponding element of a matrix or vector. We put an arrow on top of a letter with subscript if it denotes a vector, e.g., x; denotes the i-th training feature. We also use Z(i) to denote the i-th element of a vector Z, and Z(i : j) de- notes the vector formed by elemenets of Z with indices be- tween and j inclusively. Span A) is the column space of matrix A. ||-I1r- and I1-Ilp denote the Frobenius norm and the vector (P-norm or the matrix p-norm. Var [-] de- notes the variance of random variable. In is x n identity matrix. I[ ([E) is an indicator function which takes the value of if event E happens, or O otherwise. The complement of set A is denoted by A, and |A| is the car- dinality of the set A. (-) is the trace of a matrix. We de- note the unit sphere in d-dimensional Euclidean space by gd-1 = fx: x E Rdd ||I|| = 1}. Let (X (P) denote the space of square-integrable functions on Sdl11 with prob- ability measure (, and the inner product (.-))ac and 11-1,,0 are defined as (f. L) = -gg- (()))())d)())))) and I1/lIi2 == fge-1 1 (x))d
random subset of X.,
Let d = [di...... d,]] E No be a random vector, and {dr] are u independent random variables such that de takes values in [i nl uniformly at random. Algorithm I, which is adapted from (EI-Yaniv & Pechyony, 2009) and deferred to the next subsection, specifies how to obtain Za [I), ...., Za(")] E No as the first u ele- ments of uniformly distributed permutation of [n]. so that Za are the indices of u test features sampled uniformly from X,, without replacement. Let Z be a vector, we use [Z] denote a set containing all the elements of the vec- tor Z regardless of the order of these elements in Z. Let Za [n] \ {Za} be the indices not in {Za]. It has been verified in (EI- Yaniv & Pechyony, 2009) that the all the points in X., == {xx²) { 'EZza which are selected by indices
in {Za), are selected from X,, uniformly at random among all subsets of size u, and X,, serves as the test features. As
result, X.. = X,,
X,, =X,
{ x; ieZu are m training
features sampled uniformly from X,, without replacement. The training features together with their labels, (yx (e are given to the learner as a training set. We denote the la- beled training set by Sm = { (x..i))
< co. PA is the or- thogonal projection onto a linear space A, and A is the linear subspace orthogonal to A. (z and Il-Ila denote the inner product and the norm in the Hilbert space H. we write a = (b) such that S Cb, Ô indicates there are specific require- ments in the constants of the O notation. = o(b) and a = (b) indicates that lim la/b] = O and lim |a/b| = oo respectively. a x b or a = @(b) denotes that there ex- ists constants (1, C2 > such that og S a S ozb. (m) for 1 S S m is the combinatory number of selecting ie different objects from m objects. g+ is the set of all non- negative real numbers, and N is the set of all the natural numbers. We use the convention that Σi = 0 if p > or q = 0. [m : n| denotes all the natural numbers between m and n inclusively, and we abbreviate [1 nz] as [n]]
iz Jezza called the test set. The learner's goal is to predict the labels of the test points in X,, based on S.. UX
X., is also
S b if there exists a constant C > 0
This paper studies the sharp generalization bounds of trans- ductive learning algorithms. We assume that all the points in the full sample X,, are distinct. Given a prediction func- tion f defined on X, we define the following loss func- tions. For simplicity of notations, we let g() = g(x;, (1x;, Ms)
or g(i) = 9(x.) for a function g defined on X x y or X. we write E ʃ as E and let (t( be the loss on the i-th data point. Let H. be a class of functions defined on X x Y. For any set A C [m], we ()m)(A) define c/ (A) == 1/m- Σ hii)) when |A| = m, and
(((x;)). y:)
2. Problem Setup of Transductive Learning
SEA
u (A) = _ Σ h(i when |A| = u. The average loss
We consider a set Smtu == { (x,, (i) 1=1 - where yi is the label for the point x,. Let n m m++ u. xi i= C X' C Rdd, [ui)__ C y C. TR where X.Y are the input and output spaces. The learner is provided with the (un- labeled) full sample X,, : xx i=1 Under the stan- dard setting of transductive learning (El-Yaniv & Pechy- ony, 2009; Tolstikhin et al., 2014), the training features X,, of size m are sampled uniformly from X,, without replace-
m+
1EA
and average squared loss associated with h are defined
+ When as (h) = 1 1 (h) = "
h = Lj. c (Za) and 111h) (Za) are the training loss and the test loss of the prediction function f. We have Ea ( (za) = E. [ (Za) = (h).
{x:]
3

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
2.1. Sampling Random Set Uniformly Without Replacement
defined
The sampling strategy in (EI- YEn-vaniv& & Pechyony, 2009) is adopted to sample points from the full sample Xn uni- formly at random among all subsets of size u, which is described in Algorithm 1. Let Za be the vector returned by Algorithm 1. Then {Za} } is the set of the indices of the test features, and Za is the set of the indices of the training features.
. (H) =
Ed
sup R LEEH
I.. (H) = Ea
LheH
sup R
u.
R (H) == Ea
sup R Rm.al h
(M)(H) = -Ea
sup R.
LhE
LiEH
(5)
where R == 1/u Σ h(Za(i)) (n).)). B B =
1=1
m
1/m Σ h Za (1)) - Lh),,, and Ry = - -
Algorithm 1 The RANDPERM Algorithm in Yaniv & Pechyony, 2009), which obtains Za E No as the first u elements of uniformly distributed permutation of [n] by sampling independent random variables di...., du.
;=1
R_ Rm,ah == - - a
We remark that the proposed Transductive Complexity (TC) is fundamentally different from the transductive ver- sion of the Rademacher complexity in (EI- Yaniv Pechy- ony, 2009, Definition in the sense that our TC is defined the random training set test set, while the counterpart in (El-Yani Yaniv & Pechyony, 2009, Definition 1) operates on the entire full sample.
1: Za < RANNDERM(())
2: input: u
3: initialize: I [n]. d, Za E N are initialized as zero vectors.
4: for i i- i..,...,2 do Sample d, uniformly from [ ni.
d(i) = d. (i) = I(d)).
Let Y = (Vi...., Yu with each Y, sampled uniformly and independently from [n] with replacement for all e [u]. Similary, Y (Y Ym) with each Y; sampled uniformly and independently from [m] with replacement for all i [m/] The following theorem relates the TC defined in Definition 2.2 to the usual inductive Rademacher com- plexity.
Swap the values of I()) and (d))).
5: end for
6: return Za
2.2. Basic Definitions
Theorem 2.1. Let o (o:))=m maxx(,.)) be iid Rademacher ((ind)
We hereby define basic notations for Transductive Com- plexity. Let d' [d'...., ... d',] be independent copies of d, and (+)) = [dl,...,d supremum of the empirical process of the gap between the test loss and the training loss as
variables.
Define
R. =
1 Σ o,,((Y) and
d', di+t,..., du). We define the
(iind) Y. h = Σ oY,)). Then
{at (H), R, (7)) < 2 (a((ind)(H) (H),
g(d) = sup NCH
(Za) (Za) (m))
Za
(4)
max
max ( (H), R. (H)) S 20g (H),
(6)
where (/aa) (Za) ( =
1
Σ Mii is the test loss,
where Di(i (ind) (HL)
By o suphew R. (ind)
o, yan
(Z()a)
(ind) Rm
(H) Ey , suPnEh R(ind) 11
c/.T (Za) = 1 h(i) is the training loss. g(d)
EE (
Remark 2.2. (imul)) (H) and (ind)) (H) are the Rademacher complexity in the inductive setting. It is remarked that (6) indicates that the established sym- metrization inequality of inductive Rademacher complex- ity also holds for the transductive complexity defined in Definition 2.2. For simplicity of notations if no confusion arises, we also write 22
is also referred to as the test-train process. We then de- fine Rademacher variables and Transductive Complexity (TC), and then relate TC to the conventional inductive Rademacher complexity.
Definition 2.1 (Rademacher Variables). Let {ox J be n i..dd random variables such that Pr[a, = 1] = Prfa;
(ind)
(H)
E supneu (ind))
-1] = 2. and they are defined as the Rademacher vari- ables.
and gffind) (ind) (7l E suPNEH
(ind) a. Yon)
The Transductive Complexity is defined below.
We define the sub-root function below, which will be exten- sively used for deriving sharp bounds based on transductive local complexity.
Definition 2.2 (Transductive Complexity). The four types of Transductive Complexity (TC) of function class H are
4

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Definition 2.3 (Sub-root (unction,(Bartlet
al., 2005, Definition 3.1)). A function s/: [0, oo) [0, oo) is sub- root if is nonnegative, nondecreasing and if sh(r) vr is non-
the empirical process for the H is derived with the expo- nential version of the Efron-Stein inequality ((Boucheron et al., 2003, Theorem 2)), and we use (Boucheron et al., 2003, Theorem 2) again along with the bound for V+(() to derive the sharp bound for g(d).
increasing for r 0.
3. TLC Excess Risk Bound for Generic Transductive Learning
3.2. The First Bound by Transductive Local Complexity
In this section, we first introduce our new concentration in- equality for the test-train process as Theorem 3.1 in Sec- tion 3.1. We then apply Theorem 3.1 to obtain Theo- rem 3.2, which presents the bound for the test-train process involving the fixed points of certain sub-root functions as the upper bounds for the TC of localized function classes. Based on Theorem 3.2, the generalization bound and ex- cess risk bound for generic transductive learning are pre- sented in Theorem 3.5 and Theorem 3.6, respectively.
Using Theorem 3.1 and the peeling strategy in the proof of (Bartlett et al., 2005, Theorem 3.3), we have the following bound for the test-train process involving the fixed points of sub-root functions as the upper bounds for the TC of localized function classes.
Theorem 3.2. Suppose K > 1 is fixed constant, and (h): H - R+ is a functional such that (h) S T, (h) for all h E H. Let dia be a sub-root function and let ru be the fixed point of vha-- Let 4/m be another sub-root function and let Im be the fixed point of t'm. Assume that for all 2 Tu.
3.1. Concentration Inequality for the Test-Train Process
Let H be a class of functions defined on X' x y and for any h E H. 0 < [h(i)] S Ho for all i E [n] with a positive number Hp. For technical reason we let Ho 2 2/2 throughout this paper, which achieved by setting Ho = max (2v2, max |/(t))}- Without special notes the function class H is separable in this pa- per. Given the function class H. we define the function class H22 = [1:2 & E H} as the "squared version" of H. We then have the following concentration inequality for the test-train process gd). We consider two cases throughout this paper, that is, m >> 2² or >>> m².
va(r) 2 max
Ea L
sup
R Rtaah
) (8)
R Rital
Ea
sup
Lh (N)S
and for all r 2 Tms
(n(r) 2 max
Ed
sup (h))
Rm
Ea
sup
Rit
Theorem 3.1 (Concentration Inequality for the Test-Train Process (4)). Assume that there is a positive number >> O such that SuPNER Tx (h2) < r. Suppose that m >> u² or >> m Then for every x > 0, with probability at least 1 - exp( xx) - (min {m, wt) 2 max {m, u} over d,
Suppose that m x² or u > m². Then for ev-
ery > O, with probability at least 1 exp(-2x) (min fm, a²)² maxx {m, u) over d, for every h H.
g(d) < Ea [d) + V min {u, m)
5ræ
(1) (Za)
c (m) (aa) +
In(h) K
+ + (Fu +
Bt A minu(um) (H2)
2ar min {u, {u.m}
8F3.
CT
(10)
+ 2v2 inf a>0
+ min {u, m}
min {m, u}
a
where co, C1 are absolute positive constants depending on K, and Cj also depends Hp-
(7)
(.) are the Transductive Complexity de- fined in (5), and H² 2h2 h E H..
Here Rt (.)),,
Remark 3.3. Tn(-) is termed surrogate variance opera- tor, and it is an upper bound for the usual variance operator T(.). (r(rr) is the sub-root upper bound for the TC for a localized function class, { E H: F,,(h) I $r}. where ev- ery function h has its functional value (a) bounded by r. In this sense, (r. is the upper bound for the TC of a localized function class, so we attribute the results of The- orem 3.2 to Transductive Local Complexity (TLC). The same comments also apply to then (r).
Key Innovations in the Proof of of Theorem 3.1. Proof of Theorem 3.1 is deferred to Section B.2 of the appendix, and it is based on the a novel combinatorial property of the test-train process revealed in Lemma B.I and Lemma B.2. Such property is used to derive the upper bound for the variance of g()), (g). Such upper bound also involves another empirical process for the class H2, The bound for
5

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
3.3. Sharp Excess Risk Bounds using Transductive Local Complexity (TICC for Generie Transductive Learning
Let th be sub-root function and Ta is the fixed point of tha- Let ymm be another sub-root function and I'm is the fixed point of V'm Assume that for all 2 Tax
We apply Theorem 3.2 to the transductive learning task introduced in Section 2, and derive sharp bound for the excess risk. Suppose we have a function class F. which contains all the prediction functions. We assume I Ey(i) I Lo for all f E F and all i E [r]] through- out this paper, and Lu 2 2v2. Given d, we define fa.u = arg = (1) (Za) as the oracle predictor with minimum loss on the test set X and fa.m. = arg min JEF yez L,,
bu(r) 2 max
Ed
sup J:: NEA, (r)sSSr
Bi
R
Ed
sup
(13)
h: 2..
and for all mms
c(m)) (Za) as empirical minimizer, that is, the predictor with minimum loss on the training data Xm. The excess risk of fa is defined by
(m(()
2 max
Fdd
sup h: MEA. (h))
Rmaa
Ed
sup
Rthhah??
(14)
8(fa.)) =u (Za) - -2( (Za). ulw) Fa
(11)
h: REAF
Suppose that m w² or u >> m². Then for ev- ery x > O, with probability at least 1 exp(-x) (min {m, uz)² max {m, u} over d, for every h E Ar,
Furthermore, we define the function class A5 = (h: h = Et - ffa J1, E F}. For = Ey l/2 Ar, define in (12) novel surrogate variance operator as functional (h): A R+ such that T,, (h) < (h). As a result, we can apply Theorem 3.2 to the functional class Ay and obtain the following theorem, which states the upper bound for the test-train process with prediction functions as the difference of loss functions with two pre- dictors from F. The following assumption, which is the standard assumption adopted by existing local complexity based methods for both inductive and transductive learn- ing (Bartlett et al., 2005; Tolstikhin et al., 2014) for perfor- mance guarantee of transductive learning with loss func- tions -(,-),, is introduced below.
uhah (Za) S c/)m) (Za) +
2B Ln Cnlesi - -1;))
K
2B +
C
K L (l - l.:) ) co (ra + rm) + min {m, u)
(15)
where co, ei are absolute positive constants depending on K, and ej also depends on Lo-
Combining Theorem 3.5 and Theorem B.11 in the ap- pendix, have the following excess risk bound for the empirical minimizer fa.m.
Assumption (Main Assumption).
(1) There is a fune- tion f E F such that fz inf fer (ll))).
Theorem 3.6. Suppose that Assumption holds and m >>> u² or >> m², K is a fixed constant. Then for every 0, with probability at least 1 - 3 exx((=x) (min (m, ut)² /max {m, u} over d. the excess risk El f(famm satisfies
(2) There is a constant B such that for any h E AF. Tw (h) < (h), where A = (4, 16-le Czz f F). Remark 3.4. Assumption is not restrictive, it is the stan- dard assumption also used in (Tolstikhin et al., 2014). In addition, Assumption 1(2) holds if the loss function e(s,))
E(fa,m) s (ru n rm)) + 4Be2r*
C3
K
min {m, u}
Lipschitz continuous in its first argument and a uniform convexity condition on f, for example, Ely' y) (y' -y)
(16)
where r* is specified by Theorem B.11 in the appendix,
Applying Theorem 3.2 to the function class Az, we obtain the following theorem.
C3 = c + 4Bcz/ (B82//K K is a positive constant, Co, C1, C2 are the positive constants Theorem 3.5 and Theorem B.11 1.11 the appendix.
Theorem 3.5. Suppose that Assumption holds, and K 1 is fixed constant. For h Er. l222 2 A with f /2 E F. let
Proof. (16) follows by plugging the upper bounds (75) for L Ta - -E=:) and L, (f ) in Theorem B.1 1.11 to (15) in Theorem 3.5.
(h)
inf fiffEF: f/1 -h
2BC, -c;:) 2BCrnl,,
Eg;))
We remark that (16) is consistent with the sharp bound for excess risk for inductive learning (1), and there are only
(12)
6

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
constant factors on the fixed points ru and Tm- In con- trast, the existing local complexity based excess risk bound (2) for transductive learning involves undesirable factors n/u and n/m, which can make the bound (2) diverge un- der standard learning models, such as the Transductive Ker- nel Learning (TKL). In the next section, we apply the TLC based sharp excess risk bound (16) to TKL.
u m². Then for every x 0, with probability least 1-3 -33xxy exp(-=x)- (min {m, u/}² mmax (m, u) over d. we have the excess risk bound
E(fa.m) S co
min r(u, m, Q) + min {m, w² ) (17) pssssn
I
where
r(u,m, =
4. TLC Excess Risk Bound for Transductive Kernel Learning
m
n Σ
Rg
Σ
n
We apply the results in Section 3.3 to obtain the sharper risk bound for transductive kernel learning in Theorem 4.1 than that in the current state-of-the-an (Tolstikhin et al., 2014).
q=Q-1
q=
q=Q-1
+
u
m
Background in RKHS and Kernel Learning. Let HK be the Reproducing Kernel Hilbert Space (RKHS) as- sociated with K, where K: X' x X' + R is a pos- itive definite kernel defined on the compact set X x X, and we assume X' compact in this section. Let
C5 an absolute B', Lo. L,
positive
constant
depending on
Comparison with current sfate-of-the-art. We now com- pare our excess risk bound (17) for TKL to the following excess risk bound obtained by the current state-of-the-art method for TKL (Tolstikhin et al., 2014), which is also based on local complexity method for transductive learn- ing. (Tolstikhin et al., 2014) shows that with high probabil- ity,
Hx,, = Σ K(, xi)as fai)i= CR be the usual RKHS spanned by (K(()x)))
the full sample X, = {x,] [x i=1 Let the gram matrix of K over the full
sample be K E Raxn K, _(x,,x,) x,) for i.j E [m]. and K,, = LK. Let d1 2 22.... 2 An > 0 be the eigen- values of Kn, and maxxex x(x,x) = < co. We then have X1 S tr (K,) I T8- For a positive number 1e, de- fine (x(P) = E HK| Ill S ud). we consider the function class Hx. (4) = Hx. (14) 0 Hx. for TKL.
E {(a.m
50
- +
n2
+
m
m
m
1
n
Σ
Q +
g=Q+1
r 5
min OSQSs
18 = u or m.
8
Results. The following assumption is standard when an- alyzing the LRC based excess risk bounds, which is also adopted in (Bartlett al., 2005; Tolstikhin et al., 2014).
(18)
It is emphasized that both our excess risk bound (17) and (18) in (Tolstikhin et al., 2014) are derived under the same assumptions, Assumption 1 (1) and Assumption 2, and our result requires the additional assumption that u > m² or >> u². It can be observed that our bound (17) is free of the undesirable factors of n/u and n/m in (18). Moreover, it is well-known by standard results on the population and empirical Rademacher complexities (Bartlett et al., 2005; Mendelson, 2002) that when the full- sample X, are sampled uniformly from the unit sphere with X' 3d-1 and the kernel K is a dot-product ker-
Assumption 2. (1) The loss T--Lipschitz in its first argument, that is,
function ((:-)) is
[e(f(x),) v) {(f(x), S LI - s(x)) for all F.
(2) There is constant B' such that for any f F, To - f B'C,, (z))
can be verified that Assumption 2 implies Assumption (2), so that the former is stronger than the latter. We now let the empirical minimizer fa.m and the oracle predictor fa be defined using the function class J Hx., (n). The fol- lowing theorem states the sharp bound for the excess risk ((Fa,m) for TKL based on Assumption I (1) and Assump- tion 2.
Σ
nel, then minos
++
n 22/(2a+1)
n
with > 1/2. In this well studied case, the RHS of (18) diverges with = on (n or m = o (n (12++1)), when u, m. + co. On the other hand, our excess risk bound (17) always converges to as u, m - so because
Theorem 4.1. Suppose that Assumption (1) and As-
sumption 2 hold. Suppose K is a positive definite kernel on X x X. Suppose that for all f E Hxx, (p). 0 Ef(i) I Lo
for all i E [m], and Lo 2 2/2. Suppose that m > u² or
r(u, n, Q) S
7

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
5. Concentration Inequality for Supremum of Empirical Process Involving RVs Sampled Uniformly Without Replacement
It follows from (21) and the above inequality that for the second version,
Suppose that H. is a function class bounded by Ho 2 2v2 such that L. (h) = 0 for all h H. Let gd(d)
(d) Ed [d]]
SuPдeи , (Za). The following theorem gives sharp bound for such general empirical process Iu (d). Such re- sult follows from the concentration inequality for the test- train process in Theorem 3.1.
2(r + 2 ( (())) s 21
)
t
2m²
3 +
(22)
n
Theorem 5.1. Suppose SuPNEh (h) S r, and let H2² = {?²: h E H}. Suppose that m > u² or u > m Then for every x > 0, with probability at least 1 - exp(-x) (min (m, x))² max {m, u) over d.
As result, the RHS of (20) diverges when o(vn), and the RHS of (22) diverges when m = w/ (V)) as u, m + oc. In contrast, the RHS of our bound (19) con- verges to under many standard learning models by not- ing that (1) A Aminnu...) (H(2) can be bounded by the induc-
(d) - EEa [d)) 2 m
tive Rademacher complexity of 722 9i / min(amm) (H²),, us- ing Theorem 2.1; (2) the inductive Rademacher complexity D (ind) min[u.m) (H(2) usually converges to 0 at fast rate, such
( min { u, m}
H min (H2
act min {u, (u,m)) m))
+ inf a>u
+ min {u, m]
as O/VI/ min {u, m)), for many standard learning mod- els (Bartlett & Mendelson, 2003), when combined with the contraction property of the inductive Rademacher com- plexity (e.g., Theorem A.5).
(19)
Proof. (19) follows immediately by (66) in Lemma B.10 and noting that C, (h) = O.
6. Conclusion
We hereby compare the existing concentration inequalities for supremum of empirical process in (Tolstikhin al., 2014). There are two versions of such inequalities in (Tol- stikhin et al., 2014, Theroem 1), which are presented as follows. For the first version, with probability at least 1- ex)((tt)).
We present Transductive Local Complexity (TLC) to derive sharp excess risk for transductive learning. TLC is based on our new concentration inequality for the supremum of empirical processes for the gap between the test and the training loss in the setting of sampling uniformly without replacement. Using a peeling strategy and a new surrogate variance operator, sharper excess risk bound, compared to the current ofate-of-the-rr, for generic transductive learn- ing with bounded loss function is derived. As an result of independent interest, a sharp concentration inequality for the general supremum of empirical process involving ran- dom variables in the setting of sampling uniformly without replacement is derived using the concentration inequality for the test-train process, with comparison to the current concentration inequalities.
2nrl u
gu (d) E. [d)( s $2
(20)
For the second version in (Tolstikhin et al., 2014, Theroem 2), with probability at least 1 exp(-t),
9n (d) Ey(:)
Fu (Y()))
2(r + 2 Ia (Y(W))] $
t
(21)
3'
A Acknowledgments
where g(Y (()( = supnem 1 h(Y)) the supremum
This work is supported by the 2023 Mayo Clinic and Ari- zona State University Alliance for Health Care Collabo- rative Research Seed Grant Program under Grant Award Number AWD00038846.
of empirical process with iid random variables (b)( Because we always expect the deviation between gu (d) and its expectation, the gap between Ey [g. (Y()) and Ea (d) is offered by (Tolstikhin et al., 2014, Theroem 3) as follows:
Impact Statement
This paper presents work whose goal is to advance the the- oretical understanding of sharp generalization capability of transductive learning.
Exii)) Du (Y(3)] Ea [d)) < 2m
8

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
References
Tolstikhin, O. Concentration inequalities for sam- ples without replacement. Theory of Probability & Its Applications, 61(3):462-481, 2017. doi: 10.1137/ S0040585X977988877.
Bardenet, R. and Maillard, O.-A. Concentration inequali- ties for sampling without replacement. Bernoulli, 21(3): 1361-1385, 2015. ISSN 13507265, 15739759.
Tolstikhin, O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. In Balcan, M., Feldman, V., and Szepesvári, C. (eds.), Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pp. 857-884. JMLR.org, 2014.
Bartlett, P. L.. and Mendelson, S. Rademacher and gaus- sian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 482, March 2003.
Bartlett, P. L.., Bousquet, O., and Mendelson, S. Lo- cal rademacher complexities. Ann. Statist., 33(4):1497- 1537, 08 2005.
Vapnik, V. Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics). Springer- Verlag, Berlin, Heidelberg, 1982.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities using the entropy method. The Annals of Probability, 31(3):1583-1611 2003.
Springer-Verlag,
ISBN 0387907335.
Cortes, C. and Mohri, M. On transductive regression. In Proceedings of the 19th International Conference Neural Information Processing Systems, NIPS*06, pp. 305-312, Cambridge, MA, USA, 2006. MIT Press.
Vapnik, V. N. Statistical Learning Theory. Wiley- Interscience, 1998.
Yang. Y. Improved generalization bound for transductive
learning by transductive local complexity and its appli- cations. arXiv preprint arXiv:2309. 16858, 2025. URL https://arxiv: http:///aaaa...orr/aa///00...19
El-Yaniv, R. and Pechyony, D. Transductive rademacher complexity and its applications. J. Artif. Int. Res., 35(1): 193-234, jun 2009.
Gross, D. and Nesme, V. Note on sampling without re- placing from finite collection of matrices. CoRR, abs/1001.2738, 2010. URL http::/aaxxv..rrt abs/1001.273B.
Hoeffding, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 1963.
Ledoux, M. and Talagrand, M. Probability in Banach Spaces: isoperimetry and processes. Springer, Berlin, May 1991.
Massart, About the constants in talagrand's concentra- tion inequalities for empirical processes. Annals of Prob- ability, Apr 2000.
Mendelson, S. Geometric parameters of kernel machines. In Kivinen, J. and Sloan, R. H. (eds.), Computational Learning Theory, 15th Annual Conference Computa- tional Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings, volume 2375 of Lecture Notes in Computer Science, pp. 29 43. Springer, 2002.
Sambale, H. and Sinulis, A. Concentration inequalities on the multislice and for sampling without replace- ment. Journal of Theoretical Probability, 35(4):2712- 2737, Dec 2022. ISSN 1572-9230. doi: 10.1007/ 101959-021-011399

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
We present the basic mathematical results required in our proofs in Section A, then present proofs of results in this paper in Section B.
A. Mathematical Tools
We introduce the basic concentration inequality which we used to develop the main results of this paper. Let X1, x.,..., Xn are independent random variables taking values in a measurable space X, and let Xī denote the vec- tor of these n random variables. Let f: x + be some measurable function. We are concerned with concentration of the random variable Z f(X1, x-) Let Xi, X2...., X₂ denote independent copies of X1, X2.... ................................ X,, and write
= f(1 XI-1, X2, ..))
Theorem A.1. (Boucheron et al., 2003, Theorem 2), the exponential version of the Efron- Stein inequality) For all 0 > and À E (0, 1/0),
X0
AV+
log E (exp (A (Z E [()) -
log
E
exp
(23)
XO
Theorem A.2. (Boucheron et al., 2003, Theorem 5,Theorem 6)) that
Assume that there exist constants a 2 and b > 0 such
(Z) E
Σ
n
Z )Z)))
1 [[222003 xx
s aZ
Then for any E (0, 1/a),
X
log (exp (X(Z - E [(])) <
(aE [7| + b).
(24)
aX
and for all / >>0 O,
-t2
Pr Z > E [Z] 1 S exp
(25)
4aF. [7]
+ 4b 2at
Moreover,
(Z = E
Σ 2 z(0)
11 [[22z003 X1
S s((Z)
holds for nondecreasing function v. Then, for all t 0,
2 4E [u 2)
Pr 7
E 7
t)
exp
(26)
Remark A.3. While a > O in the original Theorem 5 of (Boucheron et al., 2003), one can use the same proof this theorem to show that (25) holds for a = 0 with 0. V+ (Z) defined in this theorem is the "upper variance" of the random variable as a function of independent random variables X1, X2,..., X,. particular, V+ measures the variance of Z when X; is changed another sample X; for all i [ro].
Proposition A.4. (Logarithmic Sobolev inequality (Boucheron al., 2003, Proposition 10)), which a variant proposed by (Massart, 2000)) For all À I,
AE IZ exp(AZ) (exp log exp(AZ))
(xp(A
E (xx((22) (-x(z ((())))()) 11 [122200)]
(27)
where vxx) = a(e² - -1).

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Theorem A.5 (Contraction Property of Inductive Rademacher Complexity (Ledoux & &allggand, 1991)). Suppose g is Lipschitz continuous with [g(x)) ا(v)و L x y|- Then
p (g H) v LR (H),
9 gi(ind)
(g o H) S L
(ind) (H).
Theorem A.6 ((Hoeffding. 1963, Theorem 4), (Gross Nesme, 2010, Section D)). Let {X and {Yi) be sampled from a population {4]==1 S X t I2 without replacement and with replacement respectively, Suppose f is continuous and convex on X, then
n
f
Σ
X
Σ
Y
(28)
B. Proofs
B.1. Proof of Theorem 2.1
(Vi...., Yu) be independent random variables with each Y; for i E [u] sampled uniformly from [n] with replacement. Let Y(w) [Y Y.l be independent copies of Y(s), and
Proof of Theorem 2.1. We prove the first bound in (6). We let Y
(0) { be countable dense subset of H ) max(u.m) be iid Rademacher variables. Let Ha 11 J j21
E IR for E [n]. and let {Qiteetui and (Qihetu be sampled from (ci) without replacement and with replacement respectively. Then follows from Theorem A.6 that
such that Ho = H. We define c
h (1) (..
jE[M]
2 which means that
]
E
Σ
E
Ed
max JE[M]]
((())
(Za) - C.,(h 1000
< By(
max sE[Md]
4 (V.)
(0) h
-..0)))))))))
2
with f(x) maX Xj being a convex function for x E I due to the fact that {Za} is random set of size u sampled
uniformly from [n]] without replacement. We note that both sequences maxxj[[]] (u) (Za) L. (h,)))
and
M21
max 4 4 -x)
are nondecreasing in terms of M. Letting M + co, it then follows from
M
Levi's monotone convergence theorem and the fact that the first element both sequences are integrable that
Ed
sup He
(Za)
(Za) - Ca((t))
< Ex
sup hE Hoo
Σ ((X)) - Cc,(h))
Because Hg is dense in H. we have
(Za)) (Za) cn((1i)
Σ M(Y.) -
Ea sup
< Eytw)
sup
(29)
LEW
hEH
i=1
As result, we have
(((w) (Za) - cc((1))
Rt (H) = E.
sup
LIEH
1
Ey(())
sup
h(Y)) - Cn(h)
hEw
i=1
Σ moxs)
Ey(w)
sup
h(Y:) - Eycoy
kEH
iml

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
]
E Byi,) Y(C)
sup WEH
Σ MYY) - 100)
i=1
1=1
④
oi (1((.) - M(Y3))
EY Y(()
sup u hEW
1=1
sup NEH
och((Yi)
+ By l
sup NEW
Σ o,1(()))
( (H).
(30)
Here ① follows from (29). is due to yoy 1/u Σ MYY) = (h)... 3 due to the Jensen's 's inequality, and 4
==1
due to the definition of the Rademacher variables, All the other bounds for R (H), Ri (H), and Ri, (H) in (6) can be proved in a similar manner.
B.2. Concentration Inequality for Test-Train Process: Proof of Theorem 3.1
Let H be the function class defined in Section 3 of the main paper. For all h E H. we define
E'hh, d, ()) = =u, (Za) c/ (Za) -u,, (Zato) + c/(m) (Zac)
the change of the test-train loss if cl is changed to d(() Then we have the following lemma showing the values of Fhh, d, ())) under four specific cases. This lemma is based the fact that there can be at most only one pair of different elements in { (aa} and [Zac). ).
Lemma B.1. For any h H. there are four cases for the value of E(h, d, d()) for i [u].
Case E(h, d, (()) ( 1 (h(Za(1)) (ZZao(((i)))
df + d/ (()) S u, u(i > u.
Case 2: E(h, d (: + m) (h(Za(p(t)) h(Zaco (1)))
if + d, p(i s uii u
Case F(h d, d ( 1. (h(Za(1)) h a(Zam)
ifd d,, p(i) > u, gi) u,
Case 4: E(h, d, d ()) = 0.
df d' or p(i). ((i) S
Here
((1) = min (1' E [i + 1, u]: Zao =1}, i),
(31)
p(i) = min (i' E (i + 1, Za (1)) 1).
(32)
In (31) and (32), use the convention that the min over empty set returns +00.
Proof. It can be checked by running Algorithm that Za and Zate) can differ at most by element. As reminder, let {Z} denote a set containing all the elements of vector Z regardless of the orders of these elements in Z.
By the definition in (31) and (32), when p(i) < then Zuto (p(t)) = Za(i). When q(i) < then Za (a())i) = Zy (i). To see this, when p(i) Σ u, the element (t) would be picked up at a location i' = p()) E (i, u] in Z That is,
Z (p(1)) = (i). When (1) & u, the element Z (t) would be picked up at a location = (()) E (i, u] in Za That is, Za (a((()) Zaco (1).
12

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
As a result, when d; = di, or p(i), u, then {Za} a and Egg, d, d O, which proves Case 4. Otherwise, when d' * d and only one element of (p(1), {()) is not co, then the conditions of Case Case 1 hold.
When the conditions of Case hold, the pair of different elements in {Za} and {Zac) } is (l(Za(p(i)) (ZZao (i))}. When the conditions of Case hold, the pair of different elements in {Za} and { (Zac } is (h(Za (Zao It follows that both Case 2 and Case hold.
If d' o d, and both p(i) and gi)) are xc, then the only element of {Za} not in [Zaco) } is Za and the only element of {Zat)] } not in {Za} a (i). so that Case holds.
The proof of Theorem 3.1 needs sampling m elements from the full sample Xx, uniformly without replacement as the training features. To this end, let d -d,,...,dm, dmm] N be random vector, and {
{ J=
independent random variables such that d; takes values in [ : ni] uniformly at random. If we invoke function RANDPERM in Algorithm I with input changed from u to m, then Z = (ANDPERM()) are the first m elements of a uniformly distributed permutation of [n]. We use Za [n] \. { to denote the indices not in {Za)- Similar to {Za} introduced in Section 2, { (Za) is a random set of size sampled uniformly from [x]] without replacement. Let d' [d'...., ...]] be independent copies of d. and d = [di....,d 1 d' det1...., dm).
For all h E H. we define
Ehh, a, a (m)) (Za) - U1 (Za) (m)) (Zas)) + +U
(Zac)).
(33)
Similar to the four cases in Lemma B. it follows by repeating the argument in the proof of Lemma B.1 that we have the following four cases for E as stated in the following lemma.
Lemma B.2. For any E H. there are four cases for the value of E(h, ()) for E [m].
Case 1: E(h, d, (()) (5 + ) (h(Za(t) h hZ am (7(1)))
if + d; 7(1) < m() m,
Case 2: B(h, d, d ( + ) (M(Za - (()((()))
df + d' p(i) 5 m, q(1) m.
Case 3: Bh,, d, ) (t + ) (M( (i) h (Z (1))
df # d; p(i) m, q(1) m.
Case 4: B(h, d, d 0.
d = d; or p(1). (i) S m,
where
(() = min (i' [i+ 1, m]: Za (i') =i} (() = min ( [ 1, m]: Zz()") = i}.
(34)
(35)
and similar to (31)-(32) in Lemma B.1, we use the convention that the min over empty set returns +oc.
We need the concept of chain associated with d. d. the following surrogate processes, and the following lemmas, Lemma B.3-Lemma B.6, before the proof of Theorem B.7 and Theorem B.8.
jq. is defined to be a chain in [N] associated with v if ju = v(ix-i 1) holds for all à E [2 : Q] when Q 2 2. We define the event as the event that there exists a chain {ir...., } in [u] associated with d with 2 < Q' < u. Similarly, let ŋ denote the event that there is chain {Ji,... . } in [m]] associated (QQ), ((Q) are defined for chains of length not less than general Q in (Yang, 2025). It also
A set [ii,..., } C [M]. where j1 < j2 <
with d with 2 Q'
follows from (Yang, 2025) that Pr [9] S u² /m when > u², and Pr ② S m² /u when >> m².
13

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
We define surrogate process (d, H') for class of functions Ht with ranges in [0, H'] (H' > as
Ed = 1. (d (')
E Q
(36)
suphew L (h)
d E Ω
We also define a surrogate process fm (d, H() for a class of functions H' with ranges in [0, (H' > 0) as
Tm (d,)))) = 4m (m,d, (d, H')
d o i
(37)
SUPNEH L (h)
d E Ω
Lemma B.3. For any h E H. let An, = {ie [u]: E(h, d, ) satisfies Case 2 in Lemma B.1} and An. = {ie [m]: E(h, d, d satisfies Case 2 in Lemma B.2). Then have
Σ (k(Za(p(i))))
(M(Z((i))) if o Ω
(38)
i
Σ (k(Za((ti)))
(i))² i á
(39)
iEAR,
Proof. This lemma follows from (Yang, 2025, Lemma B.6, Lemma B.11).
Lemma B.4. For function class H', we define
ta (d, = sup
(u( (w) (Za) f.((h) (h))
(40)
hE
4m (d, H²) = sup
(m) (Za) fn((h))
(41)
Then
Ea (d,,d, H() Rt (H'),
Ea Im (dd pC'] -ii (H').
(42)
Moreover, for g(d) defined in (4), we have
Ea [g(d)) - (H)
(H) + 9,m (H).
(43)
Proof. Ea (d)( = R. (H') follows from the definition of Transductive Complexity in (5). We have
Ea fm (d, (d,
(m,
Ea
sup NEW
(c) (m)) (Za) Ln((t))
(c(()) (Za) cn((1)) = Rtt (H²)..
Ea
sup
kEH
where the second last equality is due to the fact that {Za} and [aa} have the same distribution, that is, they are sets of size m sampled uniformly from [n] without replacement. This proves (42).
We now prove (43). We first have
Ea [9(d)]
E.
sup NEH
(1," (Za) (Za) c(()) (Za))
(u(," (Za) - Cn(h) + Cn(h) ((m)) (Za)
Ed
sup LeE
Ea
sup LiEH
(u( (1) (Za) (h)
Ea
sup kEe
C., (h) (m))) (Za)
9xd (H)
(76)
14

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
-R Rm (H)
Here ! follows from the addiiiiit of supremum.
Lemma B.5 ((Yang, 2025, Lemma B.8, Lemma B.13) with Q= 2). Let 76' be a class of functions with ranges in [0, H'),
and Lu, Iy are defined in (40) and (36). Suppose suP (h) S r for 0. Then
2H' X2 (Ea [ (d, H() + +r)
log Ea lexp (A (d, H') Ea (d. H HDD)
(44)
u 2H'X
holds for all À E (0, ()HH")) where the surrogate process t. defined in (36). Similarly,
2/1 [a Im (d, H() +r)
log Ej exp (* (fm.((d H() Ba Fm (d, H) [(]))] =
(45)
m 2H'
holds for all X E (0, m/ (2H1")),, where the surrogate process Im defined in (37)
Lemma B.6 (Special case of (Yang. 2025, Lemma B.7, Lemma B.12) with Q 2). For any h E H. let
1r {i [u] Case 1 defined in Lemma B.1 satisfied}.
Ar, {i E [m]] Case 1 defined in Lemma B.2 is satisfied}.
Then with probability at least 1 - Pr [92]. for all h E H. we have
E
(10 Z a0 (1)))
nw Tn
(h),
Σ
(g(za)(((()))
2nu T, (h),
(46)
m
m
jEAA.
m2
(h(Za ac (i)))²
à
nm
Tr, (h),E
Σ iE
(h(Zam) (+(1)))
2nm (h)
(47)
The following theorem states the concentration incquality for the supremum of the test-train process g(d) when >> u². Theorem B.7, Suppose suрлeи Ta (h²) Sr. over d.
m > u², then for all x >> O, with probability at least 1 - exp((=x)) Pr [9t]
5rx
R (H²)
2a.
8H
sd < E. (odd) + +8 + 2 inf as0
(48)
Proof. This theorem follows from the proof of (Yang, 2025, Theorem 5.1) with the special case that Q = 2.
The following theorem, Theorem B.8, states the concentration inequality for the supremum of the test-train process g(d) when u >> m². Many technical details in the proof of Theorem B.7 are reused in the proof of Theorem B.8. The major
difference is that consider different supremum of empirical process, supлEи (u)" (M) (Za)
(m)) (Za)): instead of
(dd as in the proof of Theorem B.7, to handle the case that 2 m.
Theorem B.8. Suppose SuPNEM over d.
Ta (h) & r. If >> m then for all x > 0, with probability at least -xcxp( exp((xr) (x)) Pr 5
5rx
*t (?(2)
2axr m
8H3ar
(dd < E [g(()) + V m
+ 2 inf a20
+
(49)
a
m
Proof. This theorem follows from the proof of (Yang, 2025, Theorem 5.2) with the special case that Q 2.
Proof of Theorem 3.1 (7) follows by combining the upper bound (48) in Theorem B.7 for the case that > u² and
the upper bound (49) for the case that > m² in Theorem B.8. In particular, note that when Q = 2. Pr [ u² 2//m
when > u², and Pr ② < m²/u /uu when >> m².
15

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
B.3. Proof of Theorem 3.2
Below are the definitions and lemmas useful for the proof of Theorem 3.2.
For 0, define the function class
H(r) = (w h helh )
(50)
where w<h) min {I>*: k r, 2 [hi with >>1
Define
U+ = sup sEH(")
(Za) - cL (Ta)
(51)
Lemma B.9. Fix A K > 1, and r > 0. If U2 S x
then
XR
(h)
=0 (Za) S _
Za
Vh H.
(52)
AK
K
Proof. (h) S r. then whh) =1 r and s = r wib) h = h. Therefore, U$* S 2/2 Ut (h) (Za) - clmL) (Za)
S (Za)
and (52)
X
holds since (h)= 2 0 for all h E H.
If Th (b) v. then wh) r with (h) (rA*-2, Again, it follows from U 5 that
4 - _m Za
and we have
r
Tn (h)
( (Za) (Za)
(m))
(Za)
K
K
and (52) still holds.
Proof of Theorem 3.2. Let r be chosen such that r 2 max frai mm Let = wiih H(), then we have Tx S r. hb
To see this, if (h) S r, then wh) r and s h, so (s) < Tn (h) Sr. Otherwise, if T2 (h) r, then s X* where
is such that (h) (r**-1, (rx)). follows that (*) (h) (h( r2
X S r. follows that (s(s) S r for all
X A
E H())
We first consider the case that m 2 u. It follows from (43) in Lemma B.4 that Ea [U;]] S (H()) + Rm (H( Applying (7) in Theorem 3.1 with a to the function class H()) then for all x > with probability at least e=
U+ s S (H()) + +0(R((4)) n. (1 +
(v
+
(53)
where = h E H.))
Define the function class H(r y) = { E a Fr()) s w)- Let T be the smallest integer such that TA 2 To =
suPneh (h). Io = 0o, then set = co. We have
a (H( S
sup hEH(O.r)
Rtah
+
sup
R²t w(h)
Rtal
hEH(r;
T
< E
Rtale hEH((,r)
sup
R
E
hE7 w(h) Rt
sup
0=
16

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
T + (r())
Σ x
(r
1=0
(r(()
1 1/2
x x-1
(54)
Here ! is due to whhh 2 r\ and E suph: P.(0)s22tt1 R Ryd 1 S (u(r)tt)) @ is due to the fact that the sub-root function d satisfies Vu I (r) for a > 1.
Setting À = 4 on the RHS of (54), we have
at (H(()) S (r/((r) S TT
(55)
The last inequality follows from v'((r) S [ VIT because 2 Tu. Following a similar argument,
T +
22
Ri (HL (1)
E
sup NEH((,r))
E
sup AE
w(h)² R2t
aaah
t=0
vhu (r)
Σ x 2 th (12
T
(r)
1+21/2
Σ
-3/122
(56)
t=0
Here I is due to nohh) rx and E. (suph: (r) function d satisfies (ar) s (r) for 1.
R 112
S (n((+)))
2 is due to the fact that the sub-root
Again, setting À 4 on the RHS of (56), we have
23 (a(r) S
23
(H, - 7
Vrtw.
(57)
7
Similar to the argument for R. (H(()), since 2 Tm. we have
(H S 5
(58)
follows from (53), (55), (57), and (58) that
U. < ((Vrru)) + (0(Tmm)) +
+ ( + +
(V
T3
= P(r).
(59)
Let ro be the largest solution P(r) X for the fixed K 1. We have
Smn= = AK² (((vT))
(O(VTT)+ + (((T)) (V/
)) +
-
r
2
O(Kx)
(60)
Then ri 2 max (rus J. Setting r ri in (59), we have
2
+
T1 = AK (O(VTw)+ + O(VTm) + (12) XK
+ + x
follows from Lemma B.9 that
T1 (h)
4, (Za)= S (())
Za
XK
K
17

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
T (h)
(
c(m)
Zd
+
+ AR (((vra)+ + @(vm)) + +
+
+
K
(h)
<
(m)
(Za)
+ co (Nu + rm) wh H.
(61)
K
Regarding the other case that u 2 m, we repeat the argument above and obtain the same upper bound as (61) with m and swapped:
(Za)
(m))
(aa)
(h)
co (ru + rm) +
c1
wh H.
(62)
K
m
(10) the follows from (61) and (62).
B.4. Sharp TLC Excess Risk Bound for Generic Transductive Learning
Proof of Theorem 3.5. We first check that Ta (h) S (h). For any h E H. by the definition of (T)hh) in (12), for every
& > 0, there exist fi, f2 E F such that = l f2. and (L, - -r==) + 2BL, - -fz)) < Th)h) + Therefore,
(h) = Cn (llg, - (2)2))
< 2Th (e,, - -(za) + 2T' (e12 ((;))
< 22BLn (x:)) 2BLn(lfz (z:) < (h) +
where the first inequality follows from the Cauchy-Schwarz inequality, and the second inequality is due to Assumption 1(2). follows that T, (h) & (h).
As result, we can apply Theorem 3.2 with (-) defined in this theorem. Then (15) follows from Theorem 3.2.
Lemma B.10. Suppose Assumption holds and m >> u² >> m Define
(4,00 (u) (Za) - (h)
9.1 (d) = sup
(63)
NEH
9m (d) = sup
(h) ((m) (Za))
(64)
NeH
9u
(d) sup
(C.(h) 4 (Za)
(65)
kcH
Suppose supnEæ (h) S r. Then for every x 0, with probability at least - -xx((xp)) - (min fm, ut)? max {m, u} over d.
R min (n.) (7(2)
g.t (d) - Ea Lggh (d) I m n
ax
+ inf asu
+
+ min {u, m]
(66)
min Min fu, m]
a
min {u, m]
where H4 max {.,03 0}.
Furthermore, let H. = Aj, Hu.m be a sub-root function and r" is the fixed point of v.um Assume that for all r 2 r",
vl max
E
sup
R h
E
sup A: BE.
Rmaah
(C) h: hE BC.
E
sup h: BC.
B min min[u,m) [u.m),a
(67)
Then for any fixed constant 1, there exists an absolute positive constant ε₂ depending on K, Lo such that for every O, with probability least exp(-x) (min {m, u))² max (m, u) over d.
(d) < BC, (h)
+ 22 r min { u. m
(68)
K
18

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning Similarly, with probability least 1 exp(-x) -mmin {m, u))² / max {m, u) over d.
(h)
(r" (+++ min {u, m3
Tu (d) -
+ 02
(69)
K
Proof. We have Iu (d)
n2t n gd).. therefore.
9 (d) - Ea (d) m (g(d) Ea lod)))),
where g is defined in (4). Then (66) follows from (7) in Theorem 3.1. It can be verified that
9m
sup hEH
(4, (Za) Ls (m))
(Za)
Zd
gd),
where the first equality is due to the fact that (Za) and { [aa] are both sets of size a sampled uniformly from [n] without
replacement. Here diss indicates the random variables on both sides follow the same distribution. As a result, E2 9m gm(d) =
u/n- Ea [d) and
Im (d) - Eaa (mm(d) (d))
dist u (o(d) Ea [g(d)))
and it follows from (7) in Theorem 3.1 that
9i min m, (H2))
9m (d) - Eaa (m [d) S
+ inf as0
(70)
min [u.m}
min {u, m)
min {u, m)
We further have
m
(m)m) (Za) (1 (Za))
9T (d)
sup NEW
(71)
as the test set, then we can repeat the proofs of Theorem B.7 and Theorem B.8, and obtain the following concentration inequality. For every >> 0, with probability at least 1 exp(-
Taking x; i=
as the training features and
x
ieZa
(min {m, 2
max {m, ) over d.
(m)
Za
21 (Za)
Ed (mm)
(Za) (T (Za)
99 min(u,m) (H22
ax
$ min
+ inf as0
+ min (u, m]
(72)
[u, m)
min (u, m]
follows from (71) and (72) that
xオ mu (722)
9. (d) Ed 9 (d)] < V min {u, m}
+ inf
(73)
a>u
a
min {u, m}
min {u, m)
Furthermore, we have F2 Im (ā)) = 9,m (H) and Ea 10, (d)) = (H))
For any & E H = Aj. such that h h l, t,z with f e F, we set (h) (C). It follows from Assumption 1(2) that
Tn (h) & T, (h) for all h E Aj.
19

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
We
note
that
suPh: NEA3, (B)))))) Rtt min (u.m ) 122 Aj.
0, suPh: HEAY,BC,(M))) Ry,a
and
SuPh: mmaa 2 holds because 0 E
With tr.m given in this theorem, by repeating the proof
of Theorem 3.2 to (70) and (73), we have
gm(d)= S (h
+02
K
min (u, m.
Bhn
T r"+ min (u, [u. m)
9u (d) S
+
C2
K
where K > 1 is fixed constant, and ट2 is positive constant depending on K and Lo-
Theorem B.11. Suppose that Assumption holds and m u² u > m² Let Vu,m be a sub-root function and r* is the fixed point of uu Assume that for all 2 r",
Vum (r) 2 max E
sup h: h. (k)
B ,E
sup h: BL. (h
R
E
sup h: BEA,,BBn (N)
B² Riiaa mintu.m),a
(74)
Then for every x > with probability at least -2exp(-x) (min u)2 /// max {m, u).
(l - 5 +
02 + - fa -1:)) S 02 (r*
I
(75)
m
where is an absolute positive constant which depends on B and La-
Proof. Let H = Aj. It follows from (69) in Lemma B.10 that with high probability, for all h E H.
(h) - U4 (Za)
(Za) < Bhn(h)
+ Eg 61 min {u, m}
K
holds for fixed constant > 1, and T2 depends on K and Tog. We set h Pa.a fyz the above inequality, and note
that (/(") (Za) ((() (Za) f (Za) < 0 due the optimality of Ja... Let K B, then the first upper bound in (75)
is proved by the above inequality with constant 62 = / (1 B/K).
Moreover, it follows from (68) in Lemma 1.10 that with high probability, for all h E H.
Ch)
(m) (Za)
(h)
02 (r' min {u, m)
since {Za} and {Za} follow the same distribution and they are all random sets of size sampled uniformly from [n]]
without replacement. We set = Ja.m - f; in the above inequality, and note that c/ (Za) fa
((m)
(Za)
- (aa) <
(())
due to the optimality of fa.m. Let > B, then the second upper bound in (75) is proved by the above incquality with the same constant C2 = / (1 K))
B.5. TLC Excess Risk Bound for Transductive Kernel Learning
Before presenting the proof of Theorem 4.1, we introduce the definition about convex and symmetric sets below, as well Lemma B. 12 which lay the foundation of the proof of Theorem 4.1.
Definition B.1 (Convex and Symmetric Set). A set X convex if ax + +11- & for all a E [o, 1]. X is symmetric - C X.
20

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Lemma B.12. Let F Hx.(u)) For every r > O,
By
sup TET:Ta(Is)
R (ind) ow)
S pu(r),
(76)
where
Σ X
Gu(r) = Q: USQSn
min
rQ
+ p
q Q=Q+1
(77)
u
Similarly, for every O,
E Ey(m),
sup |EF: Tulfisr
R(fin)
S (m))),
(78)
where
Σ
(m)r) = min Q: OsQSn
rQ V m
+ m
q Q+1
(79)
m
Proof. We have
u
=151) Σ
u
(ind) (.) f
u Σ (rf((x)) =
(.,
o.K(
(80)
i=1
HK
Because { (g())]
FA21 k21
an orthonormal basis of H.k for any 0 S Q S n, we further express the first term on the RHS of
(80) as
f
o, (( xr.)
Σ
L. (0) (Y
+ (F
(81)
HK
Hx
1==1
Hx
where
(f, 2a) Hx
2y:
Q=1
(1))
o(((xxx)); Bg
4
HK
v (Q σ) =
O XY.), (.x)),))).....
2g
4
Q+1+1
Hx
Define the operator T.: Hx Hx by 1/n Σx_ K(, (xxx for any f E Hg. It can be verified that o2 is the eigenfunction of T, with the corresponding eigenvalue X, for g E [n]. We have
(Tnts)) Hx -11 n K(. K(;x2))(x..11
-T,(f).
Hx
21

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
As result,
Q
Vv 1=1
2g (f,
Lg) 2
Xa
(f.
L9 Hx
1
Xg (f. 29/ HK = -Tnff.fmu = Tx((f) S r,
(82)
HK
2=1
q=1
which holds for all such that (,) r. Combining (80)-182), we have
R (n()))) Yoo
E
sup [EF: (r
1
Σ Ag (f, (g o
By o |1000
.
sup JEF: TT
Hx
Hx
Eyo, | .0) Hx
+ 1|
| Hx
$ /VEYYw
+ plb
(83)
where ① is due the Cauchy-Schward inequality.
We have
( o K,, xY.).
①
E Ey(os, o
Ex(
Σ
K(, xy,),
Dg
Hx
ii
- Ey(w)
Σ B (xx:)
u
1 n
D3 (x(x))
( Dg p = -g.
(84)
Here ! is due to the fact that E [o,]] for all E [n]. follows from (84) that
2
Ey(w) a (10)
1
E
Σ
12
o o (x Fy
Hx
Vu
1
X
9-1
Hx
Q
2
E
Eyto), o
Σ
K xv.), P4
Vu
u
Rg
1=1
ii=1
Q
(85)
where ① is due to the Jensen's inequality, 2 is due to the fact that E [ov] 0 for all i [n]. Similarly, we have
Ey
.r)
E
By
o
(x,x),);,, Dg
Hx
Vu
9=Q+1
1=1
Hk.
2
1
E
Ey(w),o
Σ
Σ o (:, xx.), og
u
v u
u
q=Q-1
Hx.
22

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Σ
Q=Q+1
(86)
follows from (83), (85), and (86) that
_ ))
rQ
q Q+1
E Ed
sup [EF: T.(f)sr
f,
min Q: nsQ
(87)
u
which completes the proof of (76). (78) can be proved by a similar argument.
The following corollary will also be necessary for the proof of Theorem 4.1. We can have the, 4m Theorem 3.5 as the upper bounds for inductive Rademacher complexities using Theorem 2.1, leading this corollary.
Corollary B.13. Under the same conditions of Theorem 3.5, for every x 0, with probability least exp(-x) (min {m, u/}²/ max {m, u}. (15) still holds for all 2 Tu-
Vu(r) 2 max E
sup h: hEAr (T))) (t)s
R (ind) o(Y(
E
sup h: hEAr P. (h)
(ind) Yoyt
(88)
and for all 2 Tm.
4m (r) 2 2 max
E
sup hEAr T. Sl)r
R (ind) o, e.
,E
sup h: hEA (M)
(nd) Y Yo tom /22
(89)
Here Tu: I' are the fixed points th and t'm respectively.
Instead of proving Theorem 4.1, we will prove the more detailed version of Theorem 4.1 as shown the following theorem.
Theorem B.14. Suppose that Assumption (1) and Assumption 2 hold. Suppose K is a positive definite kernel on X' x X. Suppose that for all f E Hx,, (u). 0 S (ii) < Lo for all E [m]. and Lo 2v2. Suppose that m >> u² or u m². Then for every x > 0, with probability at least 1 exp(-x) - (min {m, u))² max {m, u} over d,
BL²
u (1)) (Za) S (Za)
h
Za
+
(Cnlen - -1::)+ Cn(lf2 - es=))
K
C1
+ min r(u, m, Q) + min {m, u} 0SQ5n
vh E AHx. (n)
(90)
where C3 is an absolute positive number depending on B', Lo, L,, nr, and
Σ
Σ
X
ruu m, m) =
1 - ) m
+
q= Q=Q++ Q+1
q=
+1
u
m
In particular, with probability at least 3 exxp(=x) 3 (min {m, u))? max {m, u} over d, with h Sa. fa.. in (90), we have the excess risk bound
E(Ja.m) S cs
min r(u, m. Q) + min {m, u USQSn
(91)
where C5 is an absolute positive constant depending on B', Lo, L p.
23

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Proof of Theorem B.14. It follows from Assumption 2 that for all h 45. Tw(h) < ,, h f cz: with fi, f2 F. Then (h) (T fr=) S (,2 fA) Ln,, lxz)) B (h).
(h). To see this, let
This inequality indicates that Assumption 1 (2) holds with B = B²L As a result, Assumption holds.
We now apply Theorem 3.5 and Corollary B.13 with the function class F = Hx., (1) and (-) defined in (12) with
B = B²I.2. Let h = ft l E Ar with f2 E F, and T, (h) S r. By the definition T. there exist fI, f2 E F such that h = Eg ft2 and 2BC (f - fx;;) (B - cx:) S r' for arbitrary r' > v. For simplicity of notations we set
r' 1.lr. Let {or) (mr))a(uu max(u, be iid Rademacher variables. For we have
R(ind) a.Y(
2Ed
sup h: hT.
!
R(ind) a. (eg (5a)
sup fikEE:: 2BLalln +2 2B (s))s'
< 2.y("),a
sup FIEF: ( S1.1222
x. (e,, - ((ūs)
(ind)
R (ind)) Y (ezz - es;))
+ 2E (u))
sup SEEF: C,ll11 )l..1//2
1 Y(u) (f f(i)
(w)
sup |EF: (
8L tw),
R (ind) SEF: B&
sup
Y
4 <
rB1
8L
(92)
8B
Here ! is due to the definition of Tm. @ due to the contraction property in Theorem A.5 and the fact that the loss function f(-, -) is L-Lipschitz continuous, and B1 is positive constant such that B1 1.1B'. ② follows by noting that (f /-2 F because F is symmetric and convex. Gu in @ is defined in (77) in Lemma B.12.
It follows from (92) that
R (ind)
rBB
2 (t),
Y(o) Fx
sup
< 8T.
8B
By a similar argument and noting that (e,, - 22 <(()) -l,;) 2 + (e,2 -g: ()) we have
-
R Riidd) 12
2E 2E
sup
A: FN)
R(ind) (v) (en, - -1;:)
< (
sup IEF: (---
S 16LonEyio),a
sup [EF: T.l::..(--)seB.pp
R(ind) Y (en - kz:)
rBi
S I32TnTip
(93)
8B
where ! due to the contraction property in Theorem A.5 and < E, < Lo for all f E F and i E [m]. Define (r) = max {8LG. ( (BB) L2 (>²) } = L'@a (B with L' == max (8L, L). It can be verified that Pa a sub-root function by checking the definition of the sub-root function.
24

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
Similarly, have
2E (m)
sup h:: (T.
((ind) Yr,)
S 8L
TBI
8B
H ((ind)) Y h?
rBB
(m))
sup h: MEA,, (h)Sr
I L2
8B
Pm (rBi) is also sub-root function. Let Tux be the fixed point of Pu. and Pm respectively. We define (p(r) = Pu(r) + Pm (r), then (p is also sub-root function. Let r be the fixed point of pp, then r 2 max (ru, mm Since both yuu and Pm are nondecreasing functions, we have
and (r) = max {8Lim
rBB
3.
(rB:
SB
8B
(() f
pw (r) fm (r) 2 (r()r)) Pm (Tm) Tu + Tm-
It then follows from the above inequality and Corollary B.13 that, for all h E A5 we have
_ (Za) S L. (mm) (Za)
(Za)=
2B K (Ln(en lx:) + Lu (C12 (1z)) + cor min (m.
C1
(94)
Let ST' Then it follows from (Bartlett et al., 2005, Lemma 3.2) that 0 S S sprr). Therefore, by the definition of p. in (77) and Pm in (79). for every S Q S n we have
X
P
+
PB 8Bm
+
+
q
+
9
g=Q+1
8Bu
Solving the above quadratic inequality for r', have
Σ q=Q+1
Xg
Σ
Rg
r S 2
1 -+-1 + Cs
9=Q+1
Eør(u, m, Q),
(95)
where K3 is positive constants depending on B', To, I,, n. (95) holds for every 0 S Q n, so it follows from (94) and (95) that
u (Za)
(Za) s c.
(m) (Za)
2B K
(Ln(en, - =1;) + Cn - -lr:))
n
Σ
Xg
e ( +-++ 11
q=Q++
9=Q+1
C min (m, u}
min + CgCg uSQ<n
(96)
m
1
which proves (90) with C3 = CoC3.
When h = fa. fa.. then we can set fi = Fa.m and f2 = Fa.n in (96).
We now derive the upper bounds for Ln Ey;) and L, Cu - Egz)) using Theorem B. Applying Theorem 2.1. we need to find the sub-root function thu.m such that
(r) 2 max
EE
sup b: BC,
R. (id)) Y y
.E
sup h: he BL. (k)
R. (nd)) or (e
E
sup
R. (imd)
a, Y (anin mu (unintu..)]
11?
h: ReAt, (h)
25

---

A New Concentration Incquality for Sampling Without Replacement and Its Application for Transductive Learning
By repeating the argument in (92) and (93), have
R
Xg
Σ
(r)
min USQSn
rQ
TQ
Q=Q+1
p
q=Q+1
m
m
Let r* be the fixed point of V.,m. Any r' S r* satisfies r' S θ (minososn r(u, m, Q)). As result, it follows from (75)
in Theorem B.11 that, with probability least 2exp(-x) 2 (min {m, u))² max {m,
-1::) 02 (0
(0 min r(u, m, 2)) [ Ca -x:)) S02 (0 osQsn
min r(u, m. 2.. asQSn
Ca -l::) Soz
m
(97)
We note that c(m)
Za S 0 due the optimality of Ja Applying the upper bound in (97) to (96) proves (91).
26


Reviews:
[{"review_id": "fLq7YVnfKG", "reviewer": "Reviewer_sB2h", "summary": "The main contribution of this paper is presenting a new tool, Transductive Local Complexity (TLC), to analyze the generalization of transductive learning algorithms. In the way, the authors proved a new concentration inequality with certain advantages that may be of independent interest. They also showed a few applications of their new tool and concentration inequality.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the positive review and the suggestions in this review.  We will add a \"Related Work\" section to the final version of this paper following your suggestion. We will also discuss the application of our transudative learning bounds to linear Graph Neural Networks (GNNs) for a transudative node classification task in the final version of paper.", "claims_and_evidence": "I verified the correctness of the proofs of theorems in section 3. Moreover, the applications make sense to me.", "methods_and_evaluation_criteria": "The evaluation criteria are natural.", "theoretical_claims": "I verified the correctness of the proofs of theorems in section 3.", "experimental_designs_or_analyses": "This is a theoretical paper without any experiment.", "relation_to_broader_scientific_literature": "Transitive learning is a fundamental topic in learning theory. Any good result in this context will be valuable. This paper provides a new tool for analyzing the generalization of transductive learning algorithms.", "essential_references_not_discussed": "I think you need to add a related work section to your paper. For instance, see the subsection Background in the following paper: https://arxiv.org/abs/2405.05190.", "other_strengths_and_weaknesses": "This is a solid theoretical paper. I think it is a good contribution to the field of statistical learning theory.", "other_comments_or_suggestions": "I suggest adding another application. Maybe something related to neural networks?", "questions_for_authors": "I do not have any specific question.", "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": {"ethical_review_concerns": "-"}}, {"review_id": "r3g3Z4GjeO", "reviewer": "Reviewer_PUBb", "summary": "The paper presented an improvement of concentration inequality for sampling without replacement. More particular, the improvement is compared to the work of Tolstikhin et al,, 2014, in which, its upper bound of excess risk shown does not have the ratio between  test and train data size over the whole given data size.  Section 4 gives similar results for transductive kernel learning and section 5 contains results for sampling uniformly without replacement of empirical process. It is purely theoretical paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review and the suggestions in this review. The raised issues are addressed below.\n\n**(1)  Proof Roadmap**\n\nFollowing the suggestion, we will give a detailed proof roadmap in the final main paper.  In particular, we first obtain a novel concentration inequality of the test-train process in Theorem 3.1. Applying the peeling strategy to Theorem 3.1, we obtain the first transductive learning bound in Theorem 3.2 which involves the surrogate variance operator $\\tilde T_n$ and the Transductive Local Complexity (TLC). By taking a particular form of the surrogate variance operator in Eq. (12), we obtain the refined transductive learning bound in Theorem 3.5 under the standard assumption (Assumption 1) with bounded loss functions.  The excess risk bound in Theorem 3.6 is then a consequence of Theorem 3.5 and the auxiliary results in Theorem B.11. The excess risk bound for transductive kernel learning in Theorem 4.1 is obtained by applying Theorem 3.5 and Theorem 3.6 to the transductive kernel learning task.  We will also provide an illustration of the above roadmap in the final version of this paper for better understanding of our proof roadmap and proof strategies.\n\n**(2) Applications of the Transductive Learning Bounds in This Paper**\n\nWe would like to mention that the transductive learning bounds in this paper have been applied to transductive kernel learning with the excess risk bound for transductive kernel learning in Theorem 4.1. We will add another application to linear Graph Neural Networks (GNNs) for a transductive node classification task in the final version of this paper. \n\n**(3) “…, since we want to bound the LHS and the LHS \"appears again\" in the bound.”**\n\nWe respectfully point out that the LHS of our transductive bound is usually the test loss, and the RHS is usually the sum of the training loss and $r$ which is the fixed point of some sub-root function. We agree that such $r$ involves both the training features and the test features, but this does not suggest that the LHS to be bounced also appears on the RHS. In particular, the LHS is the test loss computed on the test features and the labels on the test features, while $r$ is computed on the training features and the test features (without the labels on the test features). In this sense, we respectfully disagree that LHS \"appears again\" in the RHS (the bound). We also remark that the learner for a transductive learning task can access both the training and the test features. For an example, in our excess risk bound for the transductive kernel learning in Theorem 4.1, $r = r(u,m,Q)$ is defined in terms of the eigenvalues of the gram matrix $\\mathbf K$ over the full sample including the training features and the test features. Such $r(u,m,Q)$ can in fact be estimated from $\\mathbf K$ as the transductive learning algorithm has access to the full sample. Even though both the LHS (the test loss) and the RHS ($r(u,m,Q)$) depend on the test features, $r(u,m,Q)$ does not involve the labels on the test features, so the derived bound for the LHS is still reasonable and sharper than the current state-of-the-art in [Tolstikhin et al., 2014].\n\n **References**\n\n[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.", "claims_and_evidence": "Since the proofs are put in the appendix and without a paragraph presenting/summarizing/comparing the techniques of this work over the work of Tolstikhin et al,, 2014 and popular works in concentration inequalities, I find it is difficult to follow the argument and the flow of the paper over 25 pages of the Appendix. This might be due to my lack of experience on transductive learning, although I am familiar with most types of concentration inequalities. Despite of these, I think the proofs are well-ordered and appear to be neat. Although the authors point out some key steps in the proofs, but for me it is difficult to connect the dots.", "methods_and_evaluation_criteria": "New method of proof is presented.", "theoretical_claims": "I could not check all the proofs, I did read some part of the Appendix,  I believe they are correct.", "experimental_designs_or_analyses": "No experiments or analyses.", "relation_to_broader_scientific_literature": "This work is mostly related to the work of Tolstikhin et al., 2014. I am not aware/ do not know  of further/broader application except ones in the paper.", "essential_references_not_discussed": "Important related works are Tolstikhin et al, 2014 and El-Yaniv & Pechyony, 2009, and some concentration inequalities. Techniques in those works are essential to understand this work.", "other_strengths_and_weaknesses": "Strength: the new approach to tackle the concentration inequality in a particular setting. \n\nWeakness: no presented application.", "other_comments_or_suggestions": "No", "questions_for_authors": "For all concentration inequalities presented in the paper, the LHS is  an empirical loss, the RSH is an expected loss plus some terms. One of the key term is $r$, which is upper bound for the loss of the train and test data. So $r$ is related to the LHS as well. At this point, I find the inequality is not in \"usual\" form, since we want to bound the LHS and the LHS \"appears again\" in the bound.", "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": "EKO5VY3dWe", "reviewer": "Reviewer_Dn1f", "summary": "This paper studies the generalization of transductive learning. To do so, this paper proves a new concentration inequality for the test-train process, which is used to derive a sharp concentration inequality for the general supremum of empirical process involving random variables in the setting of sampling uniformly without replacemenn. Then, this paper uses Transductive Local\nComplexity (TLC) along with the concentration inequality to provide an excess risk analysis for the empirical risk minimizer of Transductive learning.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review and the suggestions in this review. The raised issues are addressed below.\n\n**(1) Minimax Optimal Lower Bound for Transductive Kernel Learning**\n\nWe consider the following setup for Transductive Kernel Learning (TKL) wherein we will derive the minimax optimal lower bound for this setup with a matching upper bound by Theorem 3.5. **Such results would show that Theorem 3.5 gives sharp upper bound**.\n\nTransductive Setting: Suppose that the full-sample $\\mathbf X_n = (\\mathbf x_i, i \\in [n])$ are i.i.d. samples distributed uniformly on the unit sphere $\\mathcal S^{d-1}$ in $\\mathbb R^d$.  This is one standard transductive setting considered in [Tolstikhin et al., 2016] where transductive lower bound is given. \n\nSuppose that kernel $K$ is defined on $\\mathcal S^{d-1}$  such that the eigenvalue of the integral operator associated with $K$ is $\\lambda_j \\asymp j^{-2\\alpha}$ with $\\alpha > 1/2$. For example, $2\\alpha = d/(d-1)$ holds for the arccosine kernel. We consider the function class $\\mathcal F = \\mathcal H_{\\mathbf X_m} \\cap \\mathcal H_K(\\mu)$ with a positive constant $\\mu$.  We assume that the target function $f^* \\in \\mathcal H_K(\\mu)$ and $y_i = f^*(\\mathbf x_i) + w_i$ where $w_i$ for $i \\in [n]$ are i.i.d. Gaussian noise with mean $0$ and variance $\\sigma^2$. $\\mathcal U_f$ and $\\mathcal L_f$ are the test loss and the training loss defined as $\\mathcal U_f  = \\sum_{\\mathbf x \\in \\mathbf X_u} (f(\\mathbf x)-f^*(\\mathbf x))^2$ and $\\mathcal L_f  = \\sum_{\\mathbf x \\in \\mathbf X_m} (f(\\mathbf x)-f^*(\\mathbf x))^2$.\n\nWe have the following minimax lower bound. “With high probability” means that the probability goes to $1$ with $m \\to \\infty$.\n\n**Theorem (Minimax Lower Bound)**. Suppose $u \\ge \\Theta(m^{(2d+1)/(2d-1)})$, then with high probability, $\\inf_{f \\in \\mathcal F}\\sup_{f^* \\in \\mathcal H_K(\\mu)}\\mathcal U_f  \\ge \\Theta(m^{-d/(2d-1)})$.  \nProof. First of all, let $E(f-f^*)^2$ be the $L^2$-distance between $f$ and $f^*$ in the $L^2$ space. Then we have $\\inf_{f \\in \\mathcal F } \\sup_{f^* \\in \\mathcal H_K(\\mu)}  E(f-f^*)^2  \\ge \\Theta(m^{-d/(2d-1)})$ by repeating the proof of the standard minimax lower bound in [Wainwright 2019] (e.g. Example 15.23). Then for every $f \\in \\mathcal F$ there exists $\\hat f^*(f) \\in \\mathcal H_K(\\mu)$ such that \n$E(f- \\hat f^*(f))^2  \\ge \\Theta(m^{-d/(2d-1)})$. We apply the standard concentration inequality so that \n$\\mathcal U_{f} - E(f-\\hat f^*(f))^2   \\ge -\\Theta(1/{\\sqrt u})$ holds for all $f, \\hat f^*(f)$ with high probability. \nWith $u \\ge \\Theta(m^{(2d+1)/(2d-1)})$, we have $\\mathcal U_{f} \\ge -\\Theta(m^{-(d+0.5)/(2d-1)}) + E(f- \\hat f^*(f))^2 \\ge \\Theta(m^{-d/(2d-1)}) $ holds for all $f$ and $\\hat f^*(f)$, completing the proof.\n\nBased on our Theorem 3.5, we have the matching upper bound below. Suppose $g_{\\mathbf \\beta(T)}$ is the kernel regressor obtained by performing $T$ steps of gradient descent on the training objective\n$L(\\mathbf \\beta) = \\sum_{\\mathbf x \\in \\mathbf X_m} (g_{\\mathbf \\beta}(\\mathbf x) – y(\\mathbf x)  )^2$ where $g_{\\mathbf \\beta}(\\cdot) = \\sum_{\\mathbf x \\in \\mathbf X_m} K(\\cdot,\\mathbf x) \\mathbf \\beta(\\mathbf x)$. For a training point $\\mathbf x$, $\\beta(\\mathbf x)$ and $y(\\mathbf x)$ are the coefficient and the label of this point.\n\n**Theorem (Matching Upper Bound)**. Suppose $T \\asymp \\Theta(m^{d/(2d-1)}) $ and $g = g_{\\mathbf \\beta(T)}$. Then with high probability, $\\mathcal U_{g} \\le \\Theta(m^{-d/(2d-1)})$.\n\nProof. By the proof of part (a) of [Raskutti et al., 2014] we have the training loss which satisfies $\\mathcal L_{g} \\le \\Theta(m^{-d/(2d-1)})$. By repeating the proof of Theorem 4.1, the bound for $\\mathcal L_{g}$, and applying Theorem 3.5, we obtain \n$\\mathcal U_{g} \\le \\Theta(m^{-d/(2d-1)})$.\n\n**(2) Addressing Other Issues** \n\nWe will explain the notations with their motivations.  Algorithm 1 generates the test features $\\mathbf X_u$ with indices in $\\mathbf Z_{\\mathbf d}$ sampled without replacement. $h^2$ appears in our Transductive Complexity (TC) because we used the exponential version of the Efron-Stein inequality to derive our transductive bounds which involve the square of loss functions. We note that using the bounds for TC in Theorem 2.1, we achieve the transductive bounds sharper than the current state-of-the-art in [Tolstikhin et al., 2014] and the minimax optimal bound in part (1) of this response.\n\n**References**\n\n[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.\n\n[Tolstikhin et al., 2016] Tolstikhin, I. Oi, Lopez-Paz, D. Minimax Lower Bounds for Realizable Transductive Classification. arXiv:1602.03027, 2016.\n\n[Raskutti et al., 2014] Raskutti, G., Wainwright, M. J., and Yu, B. Early stopping and non-parametric regression: an optimal data dependent stopping rule. JMLR 2014.\n\n[Wainwright 2019] M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I have checked part of the proof.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\nThis paper is written well.\n\nTransductive learning is important in machine learning. Better bounds are provided, including sharper concentration inequalities for sampling without replacement and sharper generalization bounds for Transductive learning.\n \nWeaknesses:\n\nThere are too many symbols which makes this paper hard to read.\n\nWhat is the difference between the strategy of sampling without replacement and Algorithm 1?\n\nIs the bound in Theorem 3.5 sharp? For the term \\frac{x}{\\min\\{m,u\\}},  would \\min\\{m,u\\} in the denominator make it suboptimal?\n\nWhy the Rademacher complexity is also defined on h^2. This is different from the case of inductive learning. \n\nWhy the authors claim that their concentration inequalities and generalization bounds are sharp? There are no lower bounds given.", "other_comments_or_suggestions": "Although this paper studies an important problem, there is much I do not understand. I will revise my score based on the author's response.", "questions_for_authors": "See the above", "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": "6jWuGapQnW", "reviewer": "Reviewer_etXN", "summary": "The paper studies transductive learning where the training examples and testing examples are drawn from a given dataset without replacement. The problem builds generalization guarantees for transductive learning based on local Rademacher complexities. To this aim, the paper first develops a new concentration inequality for sampling without replacement, based on which the paper gives generalization bounds as well as excess risk bounds. The main contribution is to develop rates fast rates under Bernstein-type conditions. Applications to kernel learning are also given.\n\n## After rebuttal\n\nThank you for your reply to my comments. It would be beneficial if the authors can include more relevant discussions with related work on concentration of sampling without replacement.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review and the suggestions in this review. The raised issues are addressed below. \n\n**(1) “…many notations which may be hard to digest for readers. There are also many typos.”**\n\nThank you for your suggestions. We have proofread this paper and fixed all the typos. In particular, all the typos in your “Other Comments Or Suggestions” have been fixed.\n\n**(2) “The proof is technical and not easy to follow. For example, in Section B.2, the paper introduces…**\n\nFollowing your suggestion, we will add more explanations and motivations to give readers a better understanding of the notations and their roles in our proofs. In particular, $E(h,\\mathbf d, \\mathbf d^{(i)})$ is the change of the test-train loss if only the $i$-th element of $\\mathbf d$ is changed (that is, $\\mathbf d$ is cbanged to $\\mathbf d^{(i)}$). The reason we introduced $E(h,\\mathbf d, \\mathbf d^{(i)})$ is that it is needed in the computation of the upper variance $V_+(Z)$, and such upper variance $V_+(Z)$ will be used in the exponential version of the Efron-Stein inequality (Eq. (23)) to derive the upper bound of the logarithm of the moment generating function of $Z-E[Z]$. Such upper bound of the moment generating function of $Z-E[Z]$ will in turn be used to derive the test-train bound for transductive learning in the proof of Theorem 3.1.\n\nFurthermore, please also kindly refer to part (1) of our response to Reviewer PUBb for a detailed roadmap of our proofs. \n\n**(3) “The result only shows advantage when m and u are imbalanced. For the typical setting with m and u of the same order…”**\n\nThe key advantage of our transductive learning bounds in this paper over those in [Tolstikhin et al., 2014] is that our bounds are sharper than those in [Tolstikhin et al., 2014] for unbalanced training/test features. It is important to note that our bounds, such as the excess risk bound for transductive kernel learning in Theorem 4.1, address both unbalanced and balanced training/test features in a unified framework.\n\n**(4)”…The paper does not consider more practical applications such as graph neural networks.”**\n\nFollowing the suggestion of this review, we will add another application to linear Graph Neural Networks (GNNs) for a transductive node classification task in the final version of this paper. \n\n**Addressing Other Comments Or Suggestions**\n\nWe will fix all the typos and reformat Eq. (1). $r^*$ in Theorem 3.6 is the $r^*$ in Theorem B.11, which will be defined before Theorem 3.6 in the final version of this paper. We will add the assumption that $f$ is convex in Theorem A.6. \n\n$V_+(Z)$ defined in Theorem A.2 is the “upper variance” of the random variable $Z$ as a function of $n$ independent random variables $X_1,\\ldots, X_n$. In particular,  $V_+(Z)$ measures the variance of $Z$ when $X_i$ is changed to another sample $X'_i$ for all $i \\in [n]$.\n\n$\\psi$ is defined as $\\psi(x) = x(e^x-1)$ which will be added to Proposition A.4.\n\n\n\n **References**\n\n[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.", "claims_and_evidence": "The claim is supported by theoretical analysis such as concentration inequalities for sampling without replacement, generalization bounds and excess risk bounds.", "methods_and_evaluation_criteria": "The paper uses several methods such as concentration inequalities, local Rademacher complexity and peeling arguments. These methods are appropriate to develop fast rates for transductive learning.", "theoretical_claims": "I only checked The proof of Theorem 2.1, which is correct. I did not check other parts of the proof.", "experimental_designs_or_analyses": "This is a theoretical paper and there are no experimental results.", "relation_to_broader_scientific_literature": "The paper is an extension of [R1], which also considered transductive learning based on local Rademacher complexity. The paper made a clear comparison with [R1], showing the advantage of the result in some special case. In particular, the theoretical result is stronger when the number of training examples and the number of testing examples are imbalanced. The paper gives examples to show that the excess risk bound in this paper always converges to 0, while the bound in [R1] can diverge when the ratio of training dataset size is too large or too small. \n\n\n[R1] Tolstikhin, Ilya, Gilles Blanchard, and Marius Kloft. \"Localized complexities for transductive learning.\" Conference on Learning Theory. PMLR, 2014.", "essential_references_not_discussed": "As far as I see, the paper gives discussions with all the essential references.", "other_strengths_and_weaknesses": "**Strength**\n- The paper gives new concentration inequality which only considers the deviation between the error in the training dataset and test dataset, without considering the error in test dataset. This seems to be better than the deviation considered in [R1] as it does not introduce $n/u$ and $n/m$, where $m$ is the size of training dataset, $u$ is the size of testing dataset and $n=u+m$. This is interesting if either $u$ or $m$ is very small.\n- The derived generalization bounds and excess risk bounds are stronger than the existing results if either $u$ or $m$ is small.\n\n**Weakness**\n- The paper is not well written, and involves many notations which may be hard to digest for readers. There are also many typos.\n- The proof is technical and not easy to follow. For example, in Section B.2, the paper introduces $E[h,d,d^{(i)}]$. However, the paper does not give explanations on the motivation and how it is used in the proof.\n- The result only shows advantage when $m$ and $\\mu$ are imbalanced. For the typical setting with $m$ and $\\mu$ of the same order, the paper does not give improvements.\n- The paper only gives applications to traditional transductive kernel learning problems. The paper does not consider more practical applications such as graph neural networks.", "other_comments_or_suggestions": "- abstract: \"are use\"\n- abstract: \"we have As an application\"\n- Eq (1) is too small\n- line 84: \". under the same assumptions\"\n- Theorem A.6: there should be an assumption that $f$ is convex.\n- Thm 3.6: what is the meaning of $r^*$?\n- line 501: \"to develop Let\"\n- Section 6: \"As an result\"\n- Eq (32): the meaning of $V_+$ is not given\n- Eq (27): the meaning of $\\psi$ is not given\n- line 790: \"Here (1) follow\"\n- line 1065: :inequality follow:", "questions_for_authors": "Is it possible to give applications to graph neural networks, which are natural examples of transductive learning?", "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 main contribution of this paper is presenting a new tool, Transductive Local Complexity (TLC), to analyze the generalization of transductive learning algorithms. In the way, the authors proved a new concentration inequality with certain advantages that may be of independent interest. They also showed a few applications of their new tool and concentration inequality.
Decision: Accept (poster)