Towards Improved Risk Bounds for Transductive Learning

1 Introduction

Transductive learning is an important setting in statistic learning theory that has been widely used in many fields such as graph neural networks (GNNs) [Oono and Suzuki, 2020; Chien et al., 2020; Esser et al., 2021; Cong et al., 2021; Tang and Liu, 2023b] and semi-supervised learning [Li et al., 2021]. Different from sampled independent and identically distributed with replacement (i.i.d.), training examples in transductive learning settings are sampled independent and without replacement from a finite population and our goal is to reason from observed, specific training cases to specific test cases.

Theoretically, current issues regarding transduction learning remain understudied. Some works for transductive error bounds have been presented in transduction learning such as complexity-based bounds [Vapnik, 1982; Vapnik, 1999; El-Yaniv and Pechyony, 2009; Cortes and Mohri, 2006; Tolstikhin et al., 2014], stability-based bounds [El-Yaniv and Pechyony, 2006; Cortes et al., 2009], information theory [Tang and Liu, 2023a] and PAC-Bayesian bounds [Blum and Langford, 2003; Derbeko et al., 2004; B´egin et al., 2014]. There are some works [Blum and Langford, 2003; Cortes and Mohri, 2006] which consider the special case where the Bayes hypothesis has zero and is contained in the hypothesis class. But this assumption is clearly too restrictive in practice, where the Bayes hypothesis usually can not be assumed to be contained in the class. In fact, most results do not provide fast rates of convergence in the general transductive setting.

∗Corresponding author.

It is worth mentioning that [Tolstikhin et al., 2014] provided the general fast rates of convergence in transduction learning based on the traditional local technique given by [Bartlett et al., 2005]. However, this local technique requires the surrogate function (see Definition 4) ψm to be "sub-root", which might not be necessary. On the other hand, the Bernstein condition is also needed to derive the final results.

In this paper, we use functional technique to peeling the hypothesis space. Our novel peeling method does not rely on the "sub-root" assumption of the surrogate function or the Bernstein assumption of the loss function. We elaborate in detail that the results obtained by our peeling method will not be worse than those obtained by existing methods. Furthermore, under two common assumption hypothesis spaces: classes of polynomial growth and VC classes, we have obtained tighter bounds compared to the best results [Tolstikhin et al., 2014] that have already been obtained. In addition, our results can also be bounded by empirical excess losses, which, to our knowledge, is the first estimating the risk bounds in transductive learning.

Finally, we employ this novel functional based peeling technique to design a moment-penalized based estimator that considering the variance information. To the best of our knowledge, generalization results for algorithms that consider variance information have not been discussed in transduction learning.

Our contribution can be summarized as follow:

1. We use novel functional based peeling technique to derive better uniform localized convergence upper bounds in transductive learning without "sub-root" assumption and Bernstein condition.
2. For non-parametric classes of polynomial growth and VC classes, our results for empirical risk minimization (ERM) exhibit the improvement relative to the previous re-

sults [Tolstikhin et al., 2014] in some cases. We also obtain the risk bounds from empirical data instead of population data.

3. We design the moment-penalized estimator in transductive learning and provide the generalization bounds for this variance-dependent algorithm, which have not bee discussed before.

2 RelatedWork

The concentration inequalities for the supremum of the standard empirical process for sampling with replacement have been well studied in the literature including Talagrand's inequality [Talagrand, 1996] and its versions due to [Bousquet, 2002a; Bousquet, 2002b] and Section 12 of [Boucheron et al., 2013]. For transductive learning, we need a modified version on concentration inequalities for the supremum of the empirical process for sampling without replacement [Cortes and Vapnik, 1995; Tolstikhin et al., 2014]. Some works for error bounds have been presented based on these inequalities such as [Vapnik, 1982; Vapnik, 1999; Blum and Langford, 2003; Derbeko et al., 2004; El-Yaniv and Pechyony, 2009; Cortes and Mohri, 2006; Tolstikhin et al., 2014]. The first general bound studied the binary loss functions, presented in [Vapnik, 1982], was implicit in the sense that the value of the bound was specified as an outcome of a computational procedure. [Blum and Langford, 2003; Derbeko et al., 2004] developed several fast rates of PACBayesian bounds which critically depends on the prior distribution over the hypothesis class. [Cortes and Mohri, 2006] considered a transductive regression with bounded squared loss and obtain a generalization error bound. [Tolstikhin et al., 2014] provided the first general fast rates of convergence in transduction learning based on the traditional local technique [Bartlett et al., 2005], which required the Bernstein condition and the surrogate function ψm to be "sub-root". To the best of our knowledge, there has not been achieved in previous literature for general optimal upper bounds relaxing the Bernstein condition and the "sub-root" surrogate function assumption. Generalization bounds for algorithms that consider variance information also have not been discussed in transductive learning.

Besides we have to mention that transductive bounds based on algorithmic stability have been studied for classification in [El-Yaniv and Pechyony, 2006], and for regression in [Cortes et al., 2009]. However, both of them do not yield fast risk bounds.

3 Preliminaries

3.1 Notations

In standard i.i.d. problem, we assume that a random sample z follows an unknown distribution P with the data support Z. For each realization of z, let ℓ(·; z) be a real-valued loss function, defined over the hypothesis class W. Given n i.i.d samples {zi}ni=1 drawn from P as training set. Then the population risk and the empirical risk are as follows:

However, in transductive learning, the learner is provided with m labeled training points and u unlabeled test points. The objective of the learner is to obtain accurate predictions for the test points. Two different settings of transductive learning were given by [Vapnik, 1998]. One assumes that both the training and test sets are sampled i.i.d. from a same unknown distribution and the learner is provided with the labeled training and unlabeled test sets. Another assumes that the set consisting of N arbitrary input points without any other assumptions regrading its underlying source is given. In this paper, we study the second setting, as pointed out by [Vapnik, 1998], any upper generalization bound in the second setting can easily yield a bound for the first setting by just taking expectation.

Let's consider a finite set ZN = (XN, YN) containing N arbitrary input points. For each data point zi = (xi, yi), we have xi ∈ XN and its corresponding output yi ∈ YN serves as the label. From this set, we uniformly sample m < N elements Xm ⊂ XN without replacement, creating a dependency among the inputs within Xm. Naturally, we also sample the corresponding outputs Ym for the input examples in Xm. The resulting training set is denoted as Zm = (Xm, Ym) and the test set is denoted as Zu = (Xu, Yu).

For any w ∈ W and the loss function ℓ : W × Z → R bounded by [-B,B], the training error and the test error can be defined as

For technical reasons that will become clear later, we also define the overall error with regard to both the union of the training and test sets as

Then, the main goal of the learner in transductive setting is to select proper parameters to minimizing the test error Ru(w), which we will denote by w∗u . Since the labels of the test set examples are unknown, we can't compute Ru(w) and need to estimate it based on the training sample Zm. A common choice is to replace the test error minimization by empirical risk minimization ˆwm ∈ argminw∈W ˆRm(w) and to use it as an approximation of w∗u . For w ∈ W we define the excess risk in transductive learning:

From now on it will be convenient to introduce the following operators, mapping functions f (for example excess loss in Theorem 1) defined on z to R:

3.2 Empirical Process Theory to Generalization

In this subsection, we introduce classical empirical process theory to construct surrogate function by upper bounding the "local Rademacher complexity". Here we give the definition of Rademacher complexity for completeness.

Definition 1 (Rademacher complexity [Wainwright, 2019]). For a function class F that consists of mappings from Z to R and f ∈ F, define

and

as the Rademacher complexity and the empirical Rademacher complexity of F, respectively, where {vi}ni=1 are i.i.d. Rademacher variables and P(vi = 1) = P(vi = -1) = 1 2 .

Furthermore, we can apply Dudley's integral bound [Sridharan, 2010] to gain the upper bound on the local Rademacher complexity using the covering number of hypothsis class F. Here we introduce the definition of covering number and Dudley's integral bound.

Definition 2 (Covering number [Wainwright, 2019]). Assume (M,metr(·, ·)) is a metric space, and F ⊆ M. The ε-convering number of the set F with respect to a metric metr(·, ·) is the size of its smallest ε-net cover:

Assume that there is a function w∗N ∈ W satisfying RN(w∗N ) = infw∈W RN(w). Define the excess loss class F ∗ = {f : f(z) = ℓ(w; z) - ℓ(w∗N ; z), w ∈ W}.

Lemma 1 (Dudley's integral bound [Sridharan, 2010]). Given r > 0 and class F that consists of functions defined on Z,

4 Upper Bounds for Empirical Risk Minimization

In this section, we start with the novel functional based peeling method. We discussed this method and compare with traditional localized technique [Bartlett et al., 2005; Tolstikhin et al., 2014] in detail. Then we derive upper bounds for ERM in transductive learning and illustrate our fast rates in two common assumptions: non-parametric classes of polynomial growth and VC classes.

4.1 Functional based PeelingMethod

In uniform localized convergence procedure, we firstly define a real valued function ψm that upper bounds the uniform error within a localized region {f ∈ F : T(f) ≤ r}, T : F → R+ is a measurement functional.

Definition 3. Let ψm be a function that maps [0, +∞)×(0, 1) to (0, +∞), which possibly depends on the observed samples {zi}mi=1 . Assume ψm satisfies for arbitrary fixed δ, r, with probability at least 1- δ,

Traditional localized technique provided by Corollary 5.3 of [Bartlett et al., 2005] peels hypothesis space by a nondecreasing and nonnegative "sub-root" function such that r → ψ(r; δ)/√r is also nonincreasing for r > 0. We relax this assumption by a meaningful surrogate function instead, which removes the "sub-root" condition.

Definition 4 (Meaningful Surrogate Function). If a function ψ(r; δ) defined over [0, +∞) × (0, 1) is non-decreasing, non-negative and bounded with respect to r for every fixed δ ∈ (0, 1). This function is called a meaningful surrogate function.

Note that the excess loss class in Theorem 3 is itself nondecreasing and non-negative, and the boundedness requirement can always be met by setting ψ(r; δ) = ψ(4B2 ; δ) for all r ≥ 4B2 . Next, we give the main theorem.

Theorem 1. For the excess loss class F ∗ = {f : f(z) = ℓ(w; z) - ℓ(w∗N ; z), w ∈ W}, assume there is a meaningful surrogate function ψm(r; δ) that satisfies for all δ ∈ (0, 1), λ > 1 and for all r > 0, with probability at least 1 - δ

Then for any δ ∈ (0, 1) and r0 ∈ (0, 4B2 ), with probability at least 1- δ

Remark 1. The "cost" of this localized uniform convergence mainly from the additional logλ 4B2 λ r0 term, which only appear in the form log ( δ 2 logλ 4B2λ r0 ) in high-probability bounds, which is of a negiligible O(log logn) order in general. The proof technique is motivated by [Xu and Zeevi, 2024], which peels with a variable functional rather than a fix

value r∗ .

Then, we compare this theorem with existing result in [Tolstikhin et al., 2014] based on traditional local Rademacher complexities [Bartlett et al., 2005].

Theorem 2 ([Bartlett et al., 2005; Tolstikhin et al., 2014]). Assume that the loss function ℓ is bounded in the interval [0, 1] and there is a constant Be > 0 such that for every f ∈ F ∗ we have ENf 2 ≤ BeENf. Assume that there is a sub-root function ψm(r) such that

Let ˆR∗m be a fixed point of ψm(r). Then for any t > 0 with probability at least 1 - δ, we have

where λ > 1 is a constant to peeling the hypothesis space.

Remark 2. There are three issues we need to point out here. Firstly, Theorem 2 is a modified version of Theorem 11 in [Tolstikhin et al., 2014]. which gave a direct result under the empirical risk minimization algorithm. However, their proof satisfies uniformly over the hypothesis space F ∗ . For a more intuitive comparison between our results and theirs, here we give the modified results using their techniques uniformly over F ∗ , the differences between [Tolstikhin et al., 2014] and proof of Theorem 2 are given in Appendix.

Secondly, we want to point out that Theorem 2 assumes the bounded loss and the Bernstein condition. However, the bounded loss assumption can derive to the Bernstein condition. (Although it may be possible to assume the existence of smaller constants that satisfy the Bernstein condition on the bounded loss). Thus, in the following comparison, we will give the version of Theorem 1 that satisfies the Bernstein condition. Later in the rest of our paper, in order to highlight our core contribution, we will directly use the loss-bounded derivation of the constant that remove the Bernstein condition directly.

Finally, we notice that Theorem 11 in [Tolstikhin et al., 2014] includes an extra term O (Be log ( 1δ ) ( N m2 )), which is involved from the concentration inequality for sampling without replacement (See Lemma 3). But Theorem 1 in our paper only focuses on the peeling technique and has not yet brought in the concentration inequality to highlight our main technique. When comparing with Theorem 1, we take out the "peeling technique" in Theorem 2 and focus on the improvement of the peeling technique.

Remark 3. Now we start to compare Theorem 1 with Theorem 2 given in [Tolstikhin et al., 2014]. Overall, our results does not require the surrogate function ψm to be "subroot". Despite weaker assumptions, our results are typically "tighter" than Theorem 2 under the same assumptions. Here we explain in detail.

On one hand, under the "sub-root" assumption, and taking the optimal choice of K, Theorem 2 can be rewrite as

Under the same assumption ENf 2 ≤ BeENf and use Theorem 1 it is straightforward to have

where the first inequality applies the Bernstein condition. The second inequality holds because the surrogate function ψm is sub-root. The last inequality holds because ˆR∗m is the fixed point of Beψm(r, δ).

Then we can derive the conclusion that when ENf ≤ ˆR∗m Be , (EN - ˆEm)f is of order λ ˆR∗m Be both in Theorem 1 and Theorem 2. When ENf > ˆR∗m Be , (EN - ˆEm)f is of order √ λ ˆR∗mEN f Be in Theorem 2. However our results in Theorem 1 is of order ψm (λENf 2 ; δ), which is strictly improved because ψm (λEN f 2 ; δ) ≤ √ λ ˆR∗mEN f Be according to (1).

On the other hand, the removal of the "sub-root" requirement on ψm is also important. The "sub-root" inequality (the first inequality in (1)) becomes an equality when ψm(r; δ) = O (√ dr m ) in the parametric case, where d is the parametric dimension. However, when the hypothesis space F is "rich", ψm(r;δ) √r can be strictly decreasing but "sub-root" assumption only requires nonincreasing so that the "sub-root" assumption can become loose. For example, when F is a nonparametric class, we often have ψm(r; δ) = O (√ r1-ρ n ) for

some ρ ∈ (0, 1). Under this condition, the richer F is, the more loose the "sub-root" inequality is, which further lead to looser bounds. We will discuss the case in detail in Theorem 4.

4.2 Upper Bounds for Empirical Risk Minimization

In this subsection, we apply our results to the loss-dependent rates of empirical risk minimization (ERM) via a surrogate function ψm and its fixed point ˆR∗m, and further give new results on two important families of classes: parametric classes of polynomial growth and VC classes. We denote the effective loss L∗ = EN [ℓ(w∗N ; z) - infw∈W ℓ(w; z)] on full dataset.

Theorem 3. For the excess loss class F ∗ = {f : f(z) = ℓ(w; z) - ℓ(w∗N ; z), w ∈ W}, assume there is a meaningful surrogate function ψm(r; δ) that satisfies for all δ ∈ (0, 1) and for all r > 0, with probability at least 1 - δ

Then ˆwm ∈ argminW{ ˆRm(w)} satisfies for any δ ∈ (0, 1) and r0 ∈ (0, 1), with probability at least 1 - δ

Remark 4. Notice that the term r0 can be selected very small. For example, we can set r0 = B2 m4 , which can make it much smaller than ˆR∗m. ( ˆR∗m can be calculated according to classical empirical process theory and Dudley's integral bound [Sridharan, 2010] and is at least of order O(B2 log 1δ /m)). Under this situation, logλ 4B2 λ r0 is of order logm, which only appear in the form log ( 2 logλ 4B2 λ r0 δ )

in the final result, which is of order log logm and can be regarded as an absolute constant. Comparing with traditional localized Rademacher complexities [Bartlett et al., 2005; Tolstikhin et al., 2014], Theorem 3 can apply to broader settings. Since we bypass the "sub-root" assumption on ψm and adapt to the better parameter L∗ instead of traditional ENf.

To illustrate the noticeable gaps between our results and previous works, we compare them on two important families of classes: non-parametric classes of polynomial growth and VC classes. To bound meaningful surrogate function in Definition 4, we need to build a connection between the supremum of the empirical process from sampling without replacement and Rademacher complexities using modified concentration inequalities. Here we provide the following lemma for transductive learning.

Lemma 2. Let F be a class of functions that map Z into [-2B, 2B]. Assume that there is some r > 0 such that for every f ∈ F, V ar[f(zi)] ≤ r. Then for any δ ∈ (0, 1), with probability at least 1- δ

Moreover, the same results hold for the quantity supf∈F ( ˆEm - EN )f .

Remark 5. Lemma 2 uses classical empirical process theory to construct surrogate function by upper bounding the "local Rademacher complexity". Traditional concentration inequality for empirical process such as [Bartlett et al., 2005] are derived from standard Talagrand's concentration inequality, where we set the random variable to be supf(P - Pn)f and use symmetrization inequality for Rademacher complexity to build a connection between Esupf(P - Pn)f and RnF. However, we can't directly apply Talagrand's concentration inequality for supf(EN - ˆEm)f because this samples are independent without replacement. We derive the concentration inequality for empirical process in transductive learning, which is motivated by [Bartlett et al., 2005]. But we use the sub-gaussian type concentration for sampling without replacement in [Tolstikhin et al., 2014] instead of Talagrand's concentration inequality [Bousquet, 2002a; Bousquet, 2002b].

Then, we derive the bounds with two families of classes.

Theorem 4 (Non-parametric classes of polynomial growth). Consider a loss class ℓ ◦W with the metric entropy condition

under the conditions of Theorem 3, then for any δ ∈ (0, 12 ), with probability at least 1 - δ, we have

Furthermore, for any δ ∈ (0, 12 ), with probability at least 1 - δ, we have

Theorem 5 (VC classes). Consider a loss class ℓ ◦ W with the metric entropy condition

under the conditions of Theorem 3, then for any δ ∈ (0, 1 2 ), with probability at least 1 - δ, we have

Furthermore, for any δ ∈ (0, 1 2 ), with probability at least 1 - δ, we have

Remark 6. Firstly, we compare Theorem 4, Theorem 5 with existing work [Tolstikhin et al., 2014]. It is worth noting that we don't assume the Bernstein condition comparing with [Tolstikhin et al., 2014]. In fact, we have already discussed in Remark 3 that under the assumption of the Bernstein condition, the order of our results is the same as [Tolstikhin et al., 2014].

In fact, the technique of splitting the hypothesis space used in the proof of [Tolstikhin et al., 2014] comes from the classical method [Bartlett et al., 2005]. Using the same technique and removing the Bernstein condition, we can easily obtain the result 1

Similarly, using Dudley's integral bound [Sridharan, 2010] and Lemma 2 and solving r ≤ O (Bψm(r; δ)), we can derive the following two results.

For non-parametric classes of polynomial growth:

1 This classical result is different from [Tolstikhin et al., 2014] because we don't use the Bernstein condition.

For VC classes:

Here, A ≍ B means there exist two positive constants c1, c2 such that c1A ≤ B ≤ c2A. Then we will start the discussions.

For non-parametric classes of polynomial growth, we consider the following two cases:

When B ≍ 1 and L∗ ≍ m-a + u-a , where a is a positive constant. This case depicts a bounded loss with a small order for L∗ to obtain a tight bound. In this case, we can easily derive that when 0 ≤ a ≤ 1 1+ρ performs better than traditional result since our result is of order (L∗ ) 1-ρ 2 and traditional result is of order (L∗ ) 12 w.r.t. L∗ .

When B ≍ mb + ub and L∗ ≪ B2 where b is a positive constant. This case depicts that the worst-case boundedness parameter is considered to scale with m so that we want to reduce the dependence on B. In this case, when B 2 1+ρ ≤ L∗ ≪ B2 , our result also gains an improvement relative to the previous result. And the larger ρ is, the more improvement our results are. For example, when ρ is almost 1, and m ≍ u, our improvement can be as large as O(m 14 ).

For VC classes, we discuss the case that when L∗ ≥ ( B (log m+log u)a ), where a is a positive constant. We find that our results is log logm (or log logu) term instead of logm (or log u), which is strictly tighter than previous results.

Next, we notice that we don't know the population "effective loss" L∗ in practice. We denote the empirical "effective loss" ̂ L∗ = ˆEm [ℓ(w∗m; z) - infw∈W ℓ(w; z)] in this part and build a connection between the optimal upper bounds without the knowledge of L∗ .

Theorem 6 (Estimating loss-dependent rate from data). Note that term L∗ is defined as EN [ℓ(w∗N ; z) - infw∈W ℓ(w; z)] and denote ̂ L∗ = ˆEm [ℓ(w∗m; z) - infw∈W ℓ(w; z)]. Under the conditions of Theorem 3, then for any fixed δ ∈ (0, 1 2 ), with probability at least 1 - δ, we have

where c is an absolute constant.

Remark 7. The term B log 2 δ m in Theorem 6 is negligible, because ˆR∗m is at least of order B2 log 1 δ m for most practical applications. This order is unavoidable in traditional "local Rademacher complexity" analysis and twosided concentration inequalities. This generalization error bound shows that without knowledge of L∗ , one can estimate the order of our loss-dependent rate by using ̂ L∗ = ˆEm [ℓ(w∗m; z) - infw∈W ℓ(w; z)] as a proxy. Despite replacing L∗ by ̂ L∗ , other quantities in the bound remain unchanged in order.

5 Upper Bounds for Moment Penalization

The risk bounds provided in Section 4.2 consider the parameter L∗ within their ψm function (or ENf using traditional localized peeling techniques), which may still be much larger than the optimal variance V ∗ := Var[ℓ(w∗N ; z)]. An example is given in [Namkoong and Duchi, 2017] in i.i.d. problems where V ∗ = 0 and the optimal rate is at most O ( logm m ), while the excess risk bound of ERM is proved to be slower than O ( 1 √m ).

We follow the path of penalizing empirical second moment in standard minimization settings [Namkoong and Duchi, 2017; Xu and Zeevi, 2024; Foster and Syrgkanis, 2023] to design an estimator that achieves the bias-variance trade-off for transductive learning. In order to adapt to V ∗ , we use a sample-splitting two-stage estimation procedure which is inspired by the prior work in standard i.i.d minimization settings [Xu and Zeevi, 2024; Foster and Syrgkanis, 2023]. Without loss of generality, we assume the size of the whole dataset is 2N and the training dataset is 2m and split the training dataset into the primary dataset S and the auxiliary dataset S′ , both of which are of size m for training dataset and u for test dataset. We denote Em the empirical distribution of the primary dataset and ES′ the empirical distribution of the auxiliary dataset. Then we define the two-stage sample-splitting moment-penalized estimator.

Definition 5 (Two-stage Sample-splitting Moment-penalized Estimator). We use a sample-splitting two-stage estimation procedure.

• At the first stage, we derive a preliminary estimate of L∗0 := Eℓ(w∗N ; z) via the "auxiliary" data set S′ , which we refer to as ̂ L∗0 .
• At the second stage, we perform regularized empirical risk minimization on the "primal" data set S, which considering the moment penalization. Consider the excess loss class F ∗ = {f : f(z) = ℓ(w; z) - ℓ(w∗N ; z),w ∈ W}. Let ψm(r; δ) be a meaningful surrogate function that satisfies ∀δ ∈ (0, 1) and ∀r > 0, with probability at least 1 - δ,

Then give a fixed δ ∈ (0, 1), let the moment-penalized estimator ˆwMP be

Using the estimator provided in Definition 5, we can derive the following variance-dependent rate.

Theorem 7. Given arbitrary preliminary estimate ̂ L∗0 ∈ [-B,B], the generalization error of the moment-penalized estimator ˆwMP in Definition 5 is bounded by

with probability at least 1 - δ, where c0 is an absolute constant and the term ˆR∗m is the fixed point of 16Bψm (r; δ 2 log2 m+5 ).

Remark 8. Notice that we don't need the assumption that ψm is "sub-root" function in Theorem 7 and we can easily find that the first stage estimation error (̂ L∗0 - L∗0 )2 can be omitted if (̂ L∗0 - L∗0 )2 ≤ O( ˆR∗m).

Further more, to bound the first stage estimation error (̂ L∗0 -L∗0 )2 , we add the "sub-root" assumption in Theorem 8.

Theorem 8. Given arbitrary preliminary estimate ̂ L∗0 ∈ [-B,B], the generalization error of the moment-penalized estimator ˆwMP in Definition 5 is bounded by

with probability at least 1 - δ, where c0 is an absolute constant and the term ˆR∗m is the fixed point of 16Bψm(r; δ 2 log2 m+5 ).

Remark 9. Similarly, δ 2 log2 m+5 only appear in the form log log ( 2 log2 m+5 δ ) in the final result, which is of order log logm and can be regarded as an absolute constant for all practical purposes. We have to emphasize that the "sub-root" assumption is only used to bound the first-stage estimation error (̂ L∗0 - L∗0 )2 defined in Definition 5. We can also apply the Dudley's integral bound and derive the results for nonparametric classes of polynomial growth and VC classes.

Theorem 9 (Non-parametric classes of polynomial growth). Consider a loss class ℓ ◦W with the metric entropy condition

under the conditions of Theorem 8, then for any fixed δ ∈ (0, 12 ), with probability at least 1 - δ, we have

Theorem 10 (VC classes). Consider a loss class ℓ ◦ W with the metric entropy condition

under the conditions of Theorem 8, then for any fixed δ ∈ (0, 1 2 ), with probability at least 1 - δ, we have

Remark 10. The results for moment penalized estimator is similar to the ERM algorithm. And to the best of our knowledge, our results are the only generalization result in transductive learning that consider variance information. Similarly, we can derive the bound with the variance-dependent rate from data.

Theorem 11 (Estimating Variance-dependent Bounds from Data). Consider the empirical centered second moment

where ̂ L∗0 ∈ [-B,B] is the preliminary estimate of L∗ obtained in the first-stage, ψm is defined in Definition 5, For any fixed δ ∈ (0, 1), by performing the moment-penalized estimator in Definition 5, with probability at least 1 - δ2 ,

Remark 11. One should view Theorem 11 as a relaxation of the original variance-dependent rate in Theorem 8. We also notice that the "sub-root" assumption in Theorem 11 is not needed here as we do not discuss the precision of ̂ L∗0 .

6 Conclusion

In this paper, we develop a novel functional based peeling technique to derive better uniform localized convergence upper bounds in transductive learning without "sub-root" assumption for functions that upper bound the uniform error within a localized region. Our method can obtain tighter risk bounds comparing with existing work [Tolstikhin et al., 2014] for ERM. Furthermore, we design a novel estimator based on the second moment penalization and derive its generalization bounds, which are the first results in transductive learning.

Ethical Statement

There are no ethical issues.

Acknowledgments

This research was supported by National Natural Science Foundation of China (No.62476277), National Key Research and Development Program of China(NO. 2024YFE0203200), CCF-ALIMAMA TECH Kangaroo Fund(No.CCF-ALIMAMA OF 2024008), and HuaweiRenmin University joint program on Information Retrieval. We also acknowledge the support provided by the fund for building worldclass universities (disciplines) of Renmin University of China and by the funds from Beijing Key Laboratory of Big Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, from Engineering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education, from Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "DoubleFirst Class" Initiative, Renmin University of China, from Public Policy and Decision-making Research Lab of Renmin University of China, and from Public Computing Cloud, Renmin University of China.