acceptodds
Under review as a conference paper at ICLR 2027

Transductive Learning Over Unbounded Losses: An Unbounded Transductive Local Complexity Approach

Abstract

We develop Unbounded Transductive Local Complexity (UTLC) for transductive learning with unbounded losses, such as squared-loss regression without norm constraints. We first develop a novel variance rescaling method to extend the existing Sharper Transductive Local Complexity (STLC) yang2026stlc concentration to unbounded loss functions. Under standard localization and Bernstein conditions, a single complexity fixed point controls empirical risk minimization. UTLC is applied to two transductive learning problems with squared-loss. For Transductive Kernel Learning (TKL) over an unbounded set in a Reproducing Kernel Hilbert Space (RKHS), UTLC gives spectral excess-risk rates for unbounded squared loss, including controlled positive ridge chosen from training labels. UTLC with bounded loss on a fixed RKHS ball recovers the rate of \citet[Theorem 5.2]yang2026stlc only as a special case under the same assumptions for \citet[Theorem 5.2]yang2026stlc. UTLC also renders a sharp rate for noisy unbounded TKL with i.i.d. sub-Gaussian noise in labels. With independent inputs and a two-sided polynomial population Eigenvalue Decay Rate (EDR), UTLC attains the minimax optimal rate on bounded RKHS signal sets, matching a Gaussian-noise lower bound under the same polynomial population EDR. The learner optimizes over an unbounded RKHS set, and its squared loss is unbounded. To the best of our knowledge, this is the first transductive local-complexity analysis to establish minimax optimal bounds for noisy TKL with unbounded squared loss.

Primary area:
learning theory
Keywords:
Transductive Learning, Unbounded Transductive Local Complexity, Unbounded Losses, Empirical Risk Minimization, Minimax Optimal Rate

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_N3ZiOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies transductive learning with unbounded losses. It extends the Sharper Transductive Local Complexity (STLC) framework of Yang (2026) using a variance-rescaling technique. The idea is to rescale functions from different variance ranges into a class with a finite envelope, apply an existing concentration inequality, and then transfer the bound back to the original class. The paper first establishes a concentration bound for unbounded function classes (Theorem 4.1) and an excess-risk bound for empirical risk minimization under a Bernstein condition (Theorem 4.2). It then considers kernel regression with squared loss and an unbounded RKHS optimization domain. Theorem 4.3 gives spectral excess-risk bounds and allows a positive ridge parameter chosen using training labels. For noisy kernel regression, Theorem 4.4 establishes a test prediction error rate of O(m−2β/(2β+1))O(m^{-2\beta/(2\beta+1)}) under polynomial eigenvalue decay and sub-Gaussian noise. The paper also gives an input-dependent ridge choice and a matching minimax lower bound under additional assumptions. The results are supported by mathematical proofs and analytical examples. There are no numerical experiments.

Critical strengths
  1. A useful concentration argument for unbounded function classes.

The variance-rescaling construction in Lemma B.2 is the strongest technical contribution. It converts variance-localized parts of an unbounded class into one class with a finite envelope. Theorem 4.1 then obtains a uniform concentration result without assuming a finite envelope for the original class.

This is a meaningful extension of the existing STLC analysis, provided the localized complexity condition can be verified. The construction may be useful beyond the kernel examples studied here.

  1. Detailed spectral and minimax analysis for kernel regression.

Theorem 4.3 uses differences between subset solutions to construct a projected kernel spectrum. This can remove directions that do not affect the relevant prediction differences, potentially giving a tighter bound.

Theorem 4.4 and Theorem D.5 also provide matching prediction-error rates under the stated eigenvalue decay and Gaussian-noise assumptions. The input-dependent ridge choice in Equation (4.10) is useful because it does not require knowing the population eigenvalue decay exponent.

Critical weaknesses
  1. It is unclear whether the new unbounded concentration result is needed for the main applications.

In the proof of Theorem 4.3, the authors restrict the analysis to the convex hull of subset solutions. Lemma D.1 shows that the normalized excess-loss class has a bounded envelope, with (B_\infty(G^\star)\leq 2).

In the proof of Theorem 4.4, the authors apply UTLC to the class (h_v(i)=v(x_i)^2/\kappa^2), with (|v|_{\mathcal H_K}\leq 1). This class satisfies (0\leq h_v(i)\leq 1). The result is then extended to arbitrary RKHS differences using homogeneity.

Both applications therefore use the bounded-envelope part of Theorem 4.1. Since these constructed classes are bounded, the existing bounded STLC concentration theorem appears relevant as well.

The paper does not clearly explain which step in these two applications genuinely requires the new unbounded extension. It may be possible to obtain the main kernel results using bounded STLC together with the authors' localization, projection, and ridge-regression arguments.

  1. The general infinite-envelope bound has a significant limitation for imbalanced splits.

When the envelope is infinite, Theorem 4.2 introduces the term

\tau_s=\frac{(n-1)s^2}{\min(m,u)^2}, \qquad s=x+\log 2.

For example, when (u=m^2) and (x) is fixed, this term remains of constant order as (m) increases. The resulting bound may therefore fail to establish vanishing excess risk even when the local-complexity fixed point tends to zero.

This is important because a key advantage of the preceding STLC framework is its ability to handle imbalanced training and test sizes.

The applicability of the general result also depends on the centered-square localization condition in Equation (4.1). Lemma A.4 shows that this condition can fail under natural variance localization.

Example C.5 establishes that an infinite-envelope squared-loss class can satisfy the assumptions, but the selected ERM has zero excess risk on every subset. It therefore provides limited evidence of how useful the new bound is for a nontrivial learning problem.

Questions for authors
  1. Can the main kernel results be derived using bounded STLC after the reductions already used in your proofs?

  2. Can the authors clarify the usefulness of the infinite-envelope bound for strongly imbalanced splits?

  3. What is the specific gain of Theorem 4.4 over existing inductive kernel ridge regression results?

7 comments
AuthorsOpenReview ↗

Our Response, Part 1

We appreciate the review which acknowledges our contribution and the suggestions in this review. The raised issues are addressed below.

Weakness (1): "It is unclear whether the new unbounded concentration result is needed for the main applications."

Response. We agree with the reviewer that Yang's bounded STLC [1] can supply the concentration in both kernel proofs of Theorems 4.3-4.4 after the novel elements of selected-solution and normalization reductions used in Theorems 4.3-4.4 of the original paper are established.

We have revised Theorems 4.1 and 4.2 to generalize the selected solution restriction, common loss normalization, and uniform scale restoration used in the original kernel proofs. While these novel elements are limited to Transductive Kernel Learning (TKL) in the original proofs of Theorems 4.3-4.4, their generalized forms in the new Theorems 4.1-4.2 can be applied to general application scenarios with TKL being a special case. As a result, the revised Theorems 4.3-4.4 depend on the revised Theorems 4.1-4.2.

In this revised paper, we provide (1) generalized Theorem 4.1, which abstracts the normalization and uniform restoration used in the original proof of Theorem 4.4 into a general statement with function-dependent positive scales; (2) generalized Theorem 4.2, which generalizes the selected-solution restriction and common loss normalization used in the original proof of Theorem 4.3.

In this manner, the revised Theorem 4.3 is derived from Theorem 4.2, and Theorem 4.4 is derived from Theorem 4.1.

Generalized Theorem 4.1 and Theorem 4.2

Theorem 4.1 abstracts the normalization and uniform restoration used in the original proof of Theorem 4.4 into a general statement with a positive scale for each function. Its variance and localized complexity assumptions are verified on the normalized class, and its conclusion restores every original function’s scale on one event. Theorem 4.2 applies Theorem 4.1 with the common loss scale a(gf)=La(g_f)=L on a subclass containing all prescribed minimizers, preserving the original learner, test oracle, and losses. The two deviation orientations, empirical optimality, and Bernstein absorption yield the first two branches of Equation (4.5). Separate moment arguments yield the third and fourth under the same ERM hypotheses.

The kernel proofs verify these general hypotheses. Selected hull construction, projection, spectral calculations, and the ridge comparison remain specific to Theorem 4.3. The squared difference majorant, ridge equation, noise estimates, and empirical ridge analysis remain specific to Theorem 4.4, while Theorem D.5 supplies the minimax construction. Bounded STLC can supply concentration after these reductions.

Example C.8 and Proposition C.9 establish applicability and rate attainment for unbounded losses with infinite centered envelopes, showing the sharpness of the excess risk bound, Equation (4.5) of Theorem 4.2. In particular, Proposition C.9 provides two matching constructions under the imbalanced regime m=o(n)m=o(\sqrt n). The fourth branch of Equation (4.5) is attained as the minimum for every 0<θ≤10<\theta\le1, and the third branch of Equation (4.5) is attained as the strictly smallest branch at θ=1\theta=1. Both constructions and their proofs appear in Section C.4. Thus Equation (4.5) cannot be uniformly improved in order for the specified ERM with its original test oracle over these classes, establishing sharpness beyond the applications in the kernel proofs.

The two kernel proofs for Theorems 4.3-4.4 use this framework as follows:

  1. Theorem 4.3 applies Theorem 4.2. Let C=F0sel\mathcal C=\mathcal F_0^{\rm sel} be the convex hull of the zero-ridge subset solutions and gf=ℓf−ℓfn⋆g_f=\ell_f-\ell_{f_n^\star} the excess over the full-sample minimizer. For positive residual maximum L0L_0, Lemma D.1 gives Var⁡n(gf)≤4L0Pngf\operatorname{Var}_n(g_f)\leq4L_0P_ng_f and B∞(gf:f∈C)≤2L0B_\infty(\\{g_f:f\in\mathcal C\\})\leq2L_0, where PnP_n is the full-sample average. Its projected spectral calculation verifies both scaled localized TC conditions. Theorem 4.2 applies with L=L0L=L_0, Bernstein constant 44, and exponent 11, using its second, finite-envelope branch. The proof of Theorem 4.2 invokes Theorem 4.1 on the original excess functions with the common scale a(gf)≡La(g_f)\equiv L and normalized majorant ψ(r)=Ψ(Lr)/L\psi(r)=\Psi(Lr)/L, where Ψ\Psi is the scaled TC majorant in Equation (4.4). The deterministic ridge comparison then transfers the zero-ridge bound on the same event. The case L0=0L_0=0 is handled separately.
AuthorsOpenReview ↗

Our Response, Part 2

  1. Theorem 4.4 applies Theorem 4.1. Under K(x,x)≤κ2K(x,x)\leq\kappa^2, assign each nonzero RKHS difference dd the raw function hd(i)=d(xi)2h_d(i)=d(x_i)^2 and restoration factor ad=κ2∥d∥HK2a_d=\kappa^2\lVert d\rVert_{\mathcal H_K}^2. The normalized functions are bounded by one, and the proof applies the one sided assertion of Theorem 4.1 with a(hd/ad)=1a(h_d/a_d)=1 after verifying both localized TC conditions with W(hd/ad)=Pn(hd/ad)W(h_d/a_d)=P_n(h_d/a_d). Restoring the scale gives adW(hd/ad)=Pnd2a_dW(h_d/a_d)=P_nd^2. Theorem 4.1 therefore controls all original differences on one event, including the fitted difference depending on split and noise. The ridge equation and noise bound complete the proof, with no diameter or residual-maximum condition.

The kernel results contribute selected-solution geometry, projected spectral bounds, and training-label ridge selection in Theorem 4.3. For noisy regression, Theorem 4.4 gives a conditional test prediction guarantee with an input-dependent ridge, and Theorem D.5 proves a matching transductive lower bound. The scaled and restricted formulations incorporate these reductions while preserving the original optimization problems and losses.

Weakness (2): "The general infinite-envelope bound has a significant limitation for imbalanced splits."

Response. We agree that the original τs\tau_s remainder did not establish convergence in the reviewer's example. We have strengthened Theorem 4.2 under exactly the same assumptions in the revised paper so that Theorem 4.2 gives a sharp excess risk bound under its conditions.

In particular, we put p=min⁡(m,u)p=\min(m,u), ρ=rL/L\rho=r_L/L, and Φθ(v)=max⁡v,v1/(2−θ)\Phi_\theta(v)=\max\\{v,v^{1/(2-\theta)}\\}. For every x≥1x\ge1, the two additional alternatives give, with probability at least 1−exp⁡(−x)1-\exp(-x),

\le L C_B \min\left\\{ \Phi_\theta(\delta_L+\tau_s),\\, \Phi_\theta(\delta_L)+b\frac{s}{p},\\, \Phi_\theta\\!\left(\rho+\frac{\exp(x)}{p}\right),\\, \Phi_\theta\\!\left(\exp(2x)\rho\right) \right\\}. \tag{1}$$ The above bound (1) is a copy of Equation (4.5) of Theorem 4.2 of the revised paper. Neither $\Phi_\theta\\!\left(\rho+\frac{\exp(x)}{p}\right)$ nor $\Phi_\theta\\!\left(\exp(2x)\rho\right)$ on the RHS of (1) contains $n/p^2$, and both apply when the envelope is infinite. Proposition C.2 proves $\rho<\infty$ under the assumed finite majorant. As a result, at fixed confidence, the fourth branch\$\\Phi\_\\theta\\!\\left(\\exp(2x)\\rho\\right)\$ is always finite for every fixed $x$, including the case when $b=\infty$ or the imbalanced regime such that $\tau_s \to \infty$ when $m=o(\sqrt n)$ and $n \to \infty$. **The sharpness of the excess risk bound (1), including the unbalanced regime**. In the revised paper, Example C.8 establishes sharpness of (1) for the specified ERM on an unbounded loss class with an infinite centered envelope. At fixed $s = x + \log 2$, (C.15) gives $\Phi_\theta(\delta_L + \tau_s) \asymp_s (d/p)^{1/(2-\theta)}$. The ERM attains this order in expectation and has a matching lower bound with fixed positive probability, as stated in (C.16) and (C.17). Proposition C.9 proves sharpness under $m = o(\sqrt{n})$ with isotropic inputs. Part (i) uses a fixed loss to attain the fourth branch $\Phi_\theta(\exp(2x)\rho)$ as the minimum for every $0 < \theta \le 1$. Part (ii) attains the strictly smallest third branch $\rho + \exp(x)/p$ at $\theta = 1$. In both parts, the loss class is unbounded and the centered envelope is infinite. These results show that the excess risk bound (4.5) cannot be uniformly improved in order for the specified ERM with its original test oracle over classes with unbounded losses and an infinite centered envelope. Both constructions and their proofs appear in Section C.4. To address the concern regarding Lemma A.4, we note that **Lemma A.4 also gives a constructive remedy for the localization issue so that Equation (4.1) is satisfied.** For its scalar family $h_t=tz$, $t\geq0$, where $P_nz=0$ and $P_nz^2=1$, replace $V_2(h_t)=t^2$ by $V_4(h_t)=t^2+t^4$. The constraint $V_4(h_t)\leq r$ implies both $t\leq\sqrt r$ and $t^2\leq\sqrt r$. Consequently, both TC levels admit a common majorant $c\sqrt r$ for a finite constant $c$, with fixed point $c^2$. The original class still has infinite envelope. The lemma therefore demonstrates how a larger surrogate repairs the failure of quadratic localization. Theorem 4.1 retains that surrogate in its deviation penalty. For Theorem 4.2, the Bernstein-linked localization must be verified separately, as it is in the kernel proof.
AuthorsOpenReview ↗

Our Response, Part 3

To address the concern about the original Example C.5, we have proposed Example C.8 in the revised paper. Example C.8 establishes feasibility of Assumption 1 on an infinite-envelope class with nonzero ERM excess. For every 0<θ≤10<\theta\le1, it uses full dimensional isotropic inputs, scores fa,w(x)=asign⁡(w⊤x)f_{a,w}(x)=a\operatorname{sign}(w^\top x) with a≥0a\ge0, and a fixed loss depending on the prediction and label. The verification takes C=F\mathcal C=\mathcal F, the entire class. Put q=2/θq=2/\theta and φ(a)=aq/q+a2q/(2q)\varphi(a)=a^q/q+a^{2q}/(2q). Each individual loss is finite, the full sample oracle is the zero predictor, and, for every amplitude and admissible direction,

\operatorname{Var}_n(g_{a,w})=\frac52a^2 \le B\varphi(a)^\theta,\qquad B=\frac52q^\theta.$$ Thus Assumption 1 holds on the full class with $L=1$, while its centered envelope satisfies $B_\infty(\mathcal G_\star)=\sup_{a\ge0}2a=\infty$. The same class satisfies both localized TC conditions of Theorem 4.2 at every radius, and the centered-square TC is strictly positive at every positive radius. For balanced splits $m=u=p=4dk$, with $d\ge2$ and $k\ge1$, its fixed point is $r_L=d/(2p-1)$ and $$\mathbb E\\,\mathcal E_{\mathcal U}(\widehat f_m) \asymp (d/p)^{1/(2-\theta)} \asymp_s\Phi_\theta(\delta_L+\tau_s),$$ for fixed $s=x+\log2$, $x\ge1$. Moreover, $$\Pr\\!\left\\{\mathcal E_{\mathcal U}(\widehat f_m)\ge \frac5{192}(d/p)^{1/(2-\theta)}\right\\}\ge\frac7{384}.$$ These statements use the original test empirical oracle and probability over the random split. They resolve the zero-excess objection to the original Example C.5: the selected ERM has nonzero excess with probability bounded away from zero and attains the predicted rate, which vanishes as $d/p\to0$. **Question 1:** "Can the main kernel results be derived using bounded STLC after the reductions already used in your proofs?" **Answer.** Yes, the main kernel results can be derived after proving the new elements in the original proofs of Theorems 4.3-4.4, including selected-hull geometry, both localized TC conditions, and the projected spectral and ridge comparisons for Theorem 4.3, and the uniform scaling and ridge/noise argument for Theorem 4.4. These new elements have been generalized into the new generalized Theorems 4.1-4.2 in the revised paper, with the TKL results, Theorems 4.3-4.4, as the applications of Theorems 4.1-4.2. **Question 2:** "Can the authors clarify the usefulness of the infinite-envelope bound for strongly imbalanced splits?" **Answer.** The revised generic bound now handles the reviewer's regime directly, without requiring a finite envelope reduction. At fixed $x$, its fourth branch in (1) converges when $r_L/L\to0$ and $B,L$ remain bounded, with no restriction on $n/p^2$. In a general case, since $\rho<\infty$ under the assumed finite majorant, at fixed confidence, the fourth branch\$\\Phi\_\\theta\\!\\left(\\exp(2x)\\rho\\right)\$ in (1) is always finite for every fixed $x$, including the case when $b=\infty$ or the imbalanced regime such that $\tau_s \to \infty$ when $m=o(\sqrt n)$ and $n \to \infty$. Theorem 4.4 also retains its noisy prediction rate for every $u\ge m$ under its input and noise assumptions, without requiring bounded zero ridge diameter $D_0$ or residual maximum $L_0$. **Question 3:** "What is the specific gain of Theorem 4.4 over existing inductive kernel ridge regression results?" **Answer.** Theorem 4.4 gives a prediction guarantee on the complementary test set for the standard random training/test split under a transductive learning setup, conditional on all observed inputs, for a ridge computed from those inputs. Theorem D.5 supplies a matching lower bound for learners with access to the same inputs. Optimal regularized least-squares rates and minimax analysis are established by [2]. In [3], Theorems 1 and 2 bound, respectively, empirical error on the labeled design and population $L^2$ error for their early-stopped estimator. Proposition 5 gives an empirical-error guarantee for Kernel Ridge Regression (KRR) with complexity-based regularization. The rate exponent and adaptive regularization therefore have established precedents. However, these results do not directly offer prediction error bounds on the complementary test set under a transductive learning setup when the ridge also uses test inputs. Our proof controls this error across the random split and gives the following guarantees:
Reviewer_BHBZOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

NOTE: Either this paper is written only for experts in a very special subdomain of transductive learning (that might be way outside my expertise), or this paper is just poorly written: After reading the author(s)' writing of Problem Setup on Page 3 and the Section 2 for Notation before that for more than five times, I still have no idea on what is the setting considered in this paper from these writings: For example, What is assumed of the loss function l, which is never quantified? When writing l_f(i) = l_f(x_i,y_i), is the y_i only for the label given by the groundtruth or can be extended for other labels? What are the properties of prediction class assumed (I can only infer for introduction or Section 2 that the label space y_i is also in R.).

Well, let me try giving my best reinterpretation of the possible Problem Setup considered in this paper. If I got it wrong, I am sorry.

The basic transductive learning setting for supervised learning/regression is the following: For a data space X and label space Y, let F be a hypothesis class of functions of form X --> Y. Now consider a data set (with possibly multiplicity) U = {x_1,...,x_{m+u}), and an unknown/hidden target hypothesis function f* in F, a uniform random subset S of m points from U is selected, and their labels are given according to f*, to form the training set. Then the transductive learning task is to build a model either from F or even outside F is to predict the labels of data points in X\S. The sample size m is usually much larger than u.

Note that for transductive multi-classification, Y can be an abstract set of labels, with a "loss function" l: Y\times Y ----> R^+0. For the regression-line problem, likely considered in this paper, Y is a subset of R^+0. One could either use absolute value or other loss functions over Y (possibly like in this paper.) The paper also seems to consider a noisy version of this setting.

It is my understanding that the main contribution of this paper is to the regression-like case where Y is a subset of R and the loss function l(Y,Y) may be unbounded. To handle the unboundness, the paper used scaling techniques and introduced the measure of "Unbounded Transductive Local Complexity" to characterize the prediction (generalization) error of the learning algorithm. From my understanding, the main learning algorithm is derived and enhanced from the ERM based framework to achieve some notion of "uniform convergence".

I think this paper may have some substantial technical contribution. However, unfortunately, based on the current writing, and conditioned on my limited knowledge, I am not able to appreciate the main contributions.

Critical strengths

Seems to improve and generalize the NIPS paper by Yingzhen Yang. Even sharper bounds for transductive learning and its applications. In Advances in Neural Information Processing Systems (NeurIPS), 2026.

Critical weaknesses

Either this paper is written only for experts in a very special subdomain of transductive learning (that might be way outside my expertise), or this paper is just poorly written: After reading the author(s)' writing of Problem Setup on Page 3 and the Section 2 for Notation before that for more than five times, I still have no idea on what is the setting considered in this paper from these writings: For example, What is assumed of the loss function l, which is never quantified? When writing l_f(i) = l_f(x_i,y_i), is the y_i only for the label given by the groundtruth or can be extended for other labels? What are the properties of prediction class assumed (I can only infer for introduction or Section 2 that the label space y_i is also in R.).

Questions for authors

Can you provide a rigorous and self-contained (at least everything is quantified) problem setup and statement of the main theorem?

4 comments
AuthorsOpenReview ↗

Our Response, Part 1

We appreciate the review and the suggestions in this review. The raised issues are addressed below.

We have added Appendix E, “Self Contained Problem Setup and Main Statements,” which defines the domains, observations, probability space, learner, and risk, then states Theorems 4.1–4.4 with all assumptions, constants, and quantifiers in one place.

Weakness and question. In response to your question “...Can you provide a rigorous and self-contained (at least everything is quantified) problem setup and statement of the main theorem”, we address the components of this concern below.

1. What are the loss and prediction class? Fix integers d≥1d\ge1 and m,u≥2m,u\ge2, with n=m+un=m+u. We use X⊆Rd\mathcal X\subseteq\mathbb R^d, Y⊆R\mathcal Y\subseteq\mathbb R, and a nonempty class F\mathcal F of predictors f:X→Rf:\mathcal X\to\mathbb R. Predictions need not belong to Y\mathcal Y, and labels need not be nonnegative. The prescribed loss ℓ(t,y)\ell(t,y) takes a prediction and an admissible label as arguments. Every evaluated loss ℓ(f(xi),yi)\ell(f(x_i),y_i) must be finite. The generic theorems allow signed losses. The kernel applications use ℓ(t,y)=(t−y)2\ell(t,y)=(t-y)^2. The generic class need not be finite, convex, or norm bounded. The empirical risk minimization (ERM) theorem explicitly assumes existence of the selected minimizers and the variance and complexity conditions below. “Unbounded” means that the supremum over predictors can be infinite even though every individual sample loss is finite.

2. What does yiy_i mean, and what is random or observed? Fix an indexed population ((xi,yi))i=1n((x_i,y_i))_{i=1}^n. In ℓf(i)=ℓ(f(xi),yi)\ell_f(i)=\ell(f(x_i),y_i), yi∈Ry_i \in \mathbb R is the actual ground truth label at index ii. The loss is defined for other admissible labels, but the sample averages use these fixed labels. Repeated inputs are allowed, including equal inputs with different labels. A training index set M\mathcal M is uniform over the (nm)\binom{n}{m} subsets of size mm, and U=[n]∖M\mathcal U=[n]\setminus\mathcal M. The learner observes all inputs and only the training labels. The generic guarantees randomize only this split: they assume neither i.i.d. sampling nor a hidden target f∗∈Ff^{\ast}\in\mathcal F generating the labels. They allow either ordering of mm and uu and do not require m≫um\gg u.

3. What algorithm and main theorem are being stated? Theorem 4.2 analyzes ordinary ERM, f^m∈arg⁡min⁡f∈FPMℓf\widehat f_m\in\arg\min_{f\in\mathcal F}P_{\mathcal M}\ell_f, where PAP_A averages over indices in AA. Its target is the excess risk EU(f^m)=PUℓf^m−min⁡f∈FPUℓf\mathcal E_{\mathcal U}(\widehat f_m)=P_{\mathcal U}\ell_{\widehat f_m}-\min_{f\in\mathcal F}P_{\mathcal U}\ell_f. The test minimum is a comparator, not information supplied to the learner. Likewise, fn⋆f_n^\star minimizes the full-sample empirical loss and is not assumed to generate the labels.

Appendix E.3 states the exact hypotheses. A fixed subclass C⊆F\mathcal C\subseteq\mathcal F contains the prescribed full-sample minimizer and the prescribed minimizer for every subset of size mm or uu. Write PnP_n for the full-sample average and Var⁡n(h)=Pn(h−Pnh)2\operatorname{Var}_n(h)=P_n(h-P_nh)^2. For gf=ℓf−ℓfn⋆g_f=\ell_f-\ell_{f_n^\star}, the condition is Var⁡n(gf)≤BL2−θ(Pngf)θ\operatorname{Var}_n(g_f)\le BL^{2-\theta}(P_ng_f)^\theta for every f∈Cf\in\mathcal C, with L,B>0L,B>0 and 0<θ≤10<\theta\le1. A finite subroot majorant Ψ\Psi must control both signed localized transductive complexities and the scaled centered-square complexity at every radius. Appendix E.2 defines these quantities and E.3 displays the complete conditions. The analytical restriction preserves the learner and test comparator over the original F\mathcal F.

For every fixed x≥1x\ge1, the theorem bounds the excess risk with probability at least 1−exp⁡(−x)1-\exp(-x) over the split. Appendix E.3 reproduces all four branches of Equation (4.5) and defines every parameter. For example, its last branch is EU(f^m)≤LCBΦθ(exp⁡(2x)ρ)\mathcal E_{\mathcal U}(\widehat f_m)\le LC_B\Phi_\theta(\exp(2x)\rho), where ρ=rL/L\rho=r_L/L, rLr_L is the fixed point of Ψ\Psi, Φθ(v)=max⁡v,v1/(2−θ)\Phi_\theta(v)=\max\\{v,v^{1/(2-\theta)}\\}, and CB=384(4+219)2max⁡1,BC_B=384(4+\sqrt{219})^2\max\\{1,B\\}. Appendix E.2 also states the uniform deviation theorem, including its function scales and probability levels.

AuthorsOpenReview ↗

Our Response, Part 2

4. How does the noisy kernel setting differ? Appendix E.4 now states both kernel theorems, including Theorem 4.3's projected spectrum and training-label ridge rule, and Theorem 4.4's conditional, rate, and expectation guarantees. Theorem 4.3 treats arbitrary fixed labels and squared loss over the full sample kernel span, with no norm constraint in the reproducing kernel Hilbert space (RKHS). Theorem 4.4 additionally assumes i.i.d. inputs and yi=f∗(xi)+εiy_i=f^{\ast}(x_i)+\varepsilon_i, where the fixed signal f∗f^{\ast} belongs to the RKHS and the zero-mean sub-Gaussian noises are i.i.d. and independent of the inputs and split. Its target is the signal prediction error u−1∑i∈U(f^(xi)−f∗(xi))2u^{-1}\sum_{i\in\mathcal U}(\widehat f(x_i)-f^{\ast}(x_i))^2, and this application assumes u≥mu\ge m. The signal model is specific to the noisy application; the generic excess-risk theorem requires no realizability assumption.

Thanks for adding appendix E, which helped me to gain a better understanding of the paper.

However, for now I will stay with my overall evaluation.

AuthorsOpenReview ↗

Thank you for your response, and our further clarification

Dear Reviewer BHBZ,

Thank you for confirming that Appendix E helped clarify the paper. We have now added an explicit reference in the main text directing readers to Appendix E, which collects the problem setup, explicit assumptions on the loss function and prediction class, and quantified statements of all four main theorems.

Further, we have enriched Appendix E, which now make the following key points very explicit.

  1. More Explicit Explanations about the Assumptions for Loss and Prediction Class. We have explained the assumptions about the losses and the prediction classes more explicitly in "Assumptions on the loss function ℓ\ell" and "Assumptions on the prediction class F\mathcal F" of Appendix E. Every evaluated sample loss must be finite, but the generic loss need not be uniformly bounded, convex, differentiable, or Lipschitz. The prediction class consists of real valued functions and may be infinite and unbounded. For ERM, minimizer existence is required, and the Bernstein and localized complexity conditions are imposed on a fixed subclass containing all prescribed minimizers.

  2. Precise guarantees. The appendix specifies the observations, randomness, risk comparators, assumptions, confidence guarantees, and constant dependencies. The four statements cover Theorems 4.1-4.4, including uniform concentration (Theorems 4.1), ERM excess risk (Theorems 4.2), spectral kernel excess risk with regularization chosen from training labels (Theorems 4.3), and noisy kernel prediction error (Theorems 4.4).

Our contribution is the sharp excess risk analysis for transductive learning with unbounded losses. To the best of our knowledge, this is the first time that sharp excess risk bounds are obtained for transductive learning with unbounded losses. At fixed confidence, matching examples attain the ERM bound in the stated balanced and strongly imbalanced regimes, including classes with an infinite centered envelope. This establishes sharpness in order for the specified Empirical Risk Minimization (ERM) and its original test comparator in those regimes. The corresponding bounded loss rates of Yang’s STLC (2026) [3] are recovered as special cases under the same assumptions used in those results. For noisy kernel learning, we additionally establish prediction rates with matching minimax lower bounds under the stated signal, noise, and spectral assumptions.

We hope such explicit formulations and explanations make the contributions easier to assess.

We respectfully point out that our presentation of the problem setup of transductive learning on Page 3 and the Section 2 of the original submission follows the presentation of the same or similar transductive problem setup in the standard literature, including [1,2,3]. We would appreciate your reassessment of this paper in light of these clarifications and results, with Appendix E in the revised paper. If concerns remain about the main text, assumptions, or mathematical statements, we would really appreciate specific pointers so that we can address them directly.

Thank you very much for your time!

References

[1] Tolstikhin et al. Localized complexities for transductive learning. COLT 2014.

[2] Yingzhen Yang. A new concentration inequality for sampling without replacement and its application for transductive learning. ICML 2025.

[3] Yingzhen Yang. Even sharper bounds for transductive learning and its applications. NeurIPS 2026.

Reviewer_monYOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Unbounded Transductive Local Complexity (UTLC), extending existing transductive local complexity analysis from uniformly bounded loss classes to potentially unbounded losses. The main technical contribution is a variance-rescaling technique that transforms functions with different variance levels into a class with a finite envelope, enabling the application of existing bounded-loss concentration inequalities.

Critical strengths
  1. A meaningful theoretical extension of transductive local complexity to unbounded losses.
  2. Strong theoretical guarantees for unbounded transductive kernel learning.
Critical weaknesses
  1. The applicability of the general UTLC bounds depends on nontrivial localization assumptions whose practical scope remains unclear.
  2. The relationship between the general unbounded-loss bounds and the sharp rates obtained in the kernel learning applications could be clarified.
Questions for authors
  1. How restrictive is the localized transductive complexity condition for general unbounded-loss problems?
  2. Under what conditions can the additional confidence term in Theorem 4.1 be improved?
  3. How essential are the eigenvalue decay and regularization assumptions for the minimax result?
3 comments
AuthorsOpenReview ↗

Our Response, Part 1

We appreciate the review which acknowledges our contribution and the suggestions in this review. The raised issues are addressed below.

Thank you for recognizing the extension to unbounded losses. We clarify the localization requirements, their role in the kernel applications, and the assumptions behind the minimax rate.

Weakness (1): "The applicability of the general UTLC bounds depends on nontrivial localization assumptions whose practical scope remains unclear."

Question (1): "How restrictive is the localized transductive complexity condition for general unbounded-loss problems?"

We would like to emphasize that while our general UTLC bounds require certain conditions, these conditions have their counterparts in the literature of transductive learning and supervised learning with bounded losses. Furthermore, the revised paper provides concrete examples satisfying these conditions.

In particular, Our Theorem 4.1 requires a common subroot majorant satisfying Equation (4.1), which can be achieved by suitably enlarging the function VV. Lemma A.4 in Appendix A gives an example showing that an infinite-envelope class satisfies Equation (4.1). Equation (4.1) is a standard condition widely used in local Rademacher complexity (LRC)-based analysis for both supervised learning [1] and transductive learning [2,3] with bounded loss functions.

Theorem 4.2 further gives sharp excess risk bounds for Empirical Risk Minimization (ERM), which requires Assumption 1, including the existence of full sample minimizers in Assumption 1(1) and the Bernstein variance control on a fixed subclass in Assumption 1(2).

In the explanation after Theorem 4.2, we give Example C.8 which satisfies Assumption 1 for linear threshold scores with an infinite envelope and nonzero ERM excess. Lemma D.1 verifies Assumption 1 for Transductive Kernel Learning (TKL) after restriction to the convex hull of the subset solutions and division by a common loss scale. Furthermore, when the subclass C=F\mathcal C = \mathcal F and L=1L = 1, Assumption 1 is the standard Bernstein geometry condition used broadly in prior LRC-based analyses for both supervised learning [1] and transductive learning [2,3] with bounded loss functions.

Weakness (2): "The relationship between the general unbounded-loss bounds and the sharp rates obtained in the kernel learning applications could be clarified."

Question (2): "Under what conditions can the additional confidence term in Theorem 4.1 be improved?"

Theorems 4.3-4.4 are our results in kernel learning with TKL. Theorem 4.3 applies Theorem 4.2 to the convex hull of the selected subset solutions. Lemma D.1 verifies Bernstein geometry and both complexity conditions after a common loss normalization. The branch Φθ(δL)+bsp\Phi_\theta(\delta_L)+b\frac{s}{p} of Equation (4.5) yields the projected spectral bound at zero ridge. A deterministic comparison gives twice that bound plus 2ε22\varepsilon^2 at positive ridge, where ε\varepsilon is the prescribed prediction tolerance. The learner and test oracle still optimize over the original unrestricted kernel span.

Theorem 4.4 directly applies Theorem 4.1 to normalized squared prediction differences bounded by one, then restores the original prediction units. Combining this uniform comparison with the ridge equation and noise control yields the signal prediction rate.

More precisely, put p=min⁡{m,u}p=\min\{m,u\}, n=m+un=m+u, and let bab_a be the centered envelope of the normalized class h/a(h)h/a(h) in Theorem 4.1. Equation (4.2) of Theorem 4.1 has the additional contribution term c1a(h)min⁡{A(n−1)x2/p2,bax/p}c_1a(h)\min\{A(n-1)x^2/p^2,b_ax/p\}, with A,x≥1A,x\ge1 and c1c_1 as defined there. A finite bab_a replaces the quadratic confidence term $c_1a(h) A(n-1)x^2/p^2 $ by a term c1a(h)bax/pc_1a(h)b_ax/p linear in x/px/p without the factor n−1n-1, even if the original class has infinite envelope. Both kernel learning results in Theorems 4.3-4.4 are based on the improvement through a finite bab_a with the confidence term c1a(h)bax/pc_1a(h)b_ax/p.

For ERM, Equation (4.5) of Theorem 4.2 also gives the moment branches Φθ(ρ+exp⁡(x)/p)\Phi_\theta(\rho+\exp(x)/p) and Φθ(exp⁡(2x)ρ)\Phi_\theta(\exp(2x)\rho) under the same ERM hypotheses. Here ρ=rL/L\rho=r_L/L is the normalized fixed point and Φθ(v)=max⁡{v,v1/(2−θ)}\Phi_\theta(v)=\max\{v,v^{1/(2-\theta)}\}. These avoid the potentially large confidence term (n−1)/p2(n-1)/p^2 even for infinite envelopes. At fixed confidence, the fourth branch of Equation (4.5), Φθ(exp⁡(2x)ρ)\Phi_\theta (\exp(2x)\rho), tends to zero when ρ→0\rho\to0 and the loss scale LL and Bernstein constant BB stay bounded.

AuthorsOpenReview ↗

Our Response, Part 2

Question (3): "How essential are the eigenvalue decay and regularization assumptions for the minimax result?"

Population eigenvalue decay is unnecessary for the guarantee in Equation (4.11) of Theorem 4.4. Under its i.i.d. input and sub Gaussian noise model with u≥mu \ge m, define ν^j=λj(K/n)\widehat\nu_j=\lambda_j(\mathbf K/n) from the observed Gram matrix K\mathbf K and Δm=min⁡0≤Q≤n{Q/m+m−1∑j>Qν^j}\Delta_m=\min_{0\le Q\le n}\{Q/m+\sqrt{m^{-1}\sum_{j>Q}\widehat\nu_j}\}, where QQ is an integer. The ridge λ^m(x)=x/m+Δm\widehat\lambda_m(x)=x/m+\Delta_m gives Equation (4.11) in Theorem 4.4, conditional on all inputs. The bound retains the signal norm and noise variance proxy explicitly. Even without eigenvalue decay, K(x,x)≤κ2K(x,x)\le\kappa^2 gives Δm≤κ/m\Delta_m\le\kappa/\sqrt m by taking Q=0Q=0.

For the population kernel eigenvalues νj\nu_j, the upper bound νj≤a+j−2β\nu_j\le a_+j^{-2\beta} for all j≥1j\ge1, with a+>0a_+>0 and β>1/2\beta>1/2, specializes this spectral guarantee to rate m−αm^{-\alpha}, where α=2β/(2β+1)\alpha=2\beta/(2\beta+1). Ridge balances regularization bias against noise amplification. The oracle choice λm=m−α\lambda_m=m^{-\alpha} uses β\beta, but the empirical choice λ^m=8log⁡(m)/m+Δm\widehat\lambda_m=8\log(m)/m+\Delta_m needs neither β\beta, the signal norm, nor the noise level. It attains the same rate in expectation and with probability at least 1−4m−81-4m^{-8}.

For the matching minimax statement, Theorem D.5 adds a lower spectral bound νj≥a−j−2β\nu_j\ge a_-j^{-2\beta} with a−>0a_->0 and Gaussian noise of positive variance, and fixes a signal ball ∥f∗∥HK≤μ0\|f^*\|_{\mathcal H_K}\le\mu_0 with μ0>0\mu_0>0. The lower spectral bound supplies sufficiently many difficult directions for the polynomial lower rate. The lower bound of the order m−αm^{-\alpha} by Theorem D.5 covers every measurable predictor using all inputs and only training labels, including randomized predictors. The signal ball defines the minimax parameter set, while our learner's optimization domain remains unrestricted in RKHS norm. Together, Theorems 4.4 and D.5 establish the matching rate under these specified conditions.

References

[1] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. Annals of Statistics, 2005.

[2] Yingzhen Yang. A new concentration inequality for sampling without replacement and its application for transductive learning. ICML 2025.

[3] Yingzhen Yang. Even sharper bounds for transductive learning and its applications. NeurIPS 2026.

AuthorsOpenReview ↗

Thank You and Author-Reviewer Discussion Reminder

Dear Reviewer monY,

We hope this message finds you well, and you just had a great Tuesday!

As a gentle reminder, tomorrow (11/18) is the final day of the Author-Reviewer Discussion period. We would like to thank you again for the time and effort you have devoted to reviewing our submission.

We believe we have addressed all of the issues and questions you raised during the review process in our rebuttal. We would be very grateful if you could take a moment to evaluate our responses before the discussion period concludes.

If there are any remaining questions, concerns, or points that you feel have not been adequately addressed, please let us know. We will respond as promptly as possible and are happy to provide any additional clarification needed.

Thank you again for your thoughtful feedback and consideration.

Regards,

The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Thank You and Summary of Final Revisions

Dear Reviewers and Area Chair,

Thank you for your careful reviews and constructive discussion. We have addressed all the concerns from the three reviewers. We summarize the revisions and recorded reviewer responses below.

(1) Reviewer N3Zi. We agree that bounded STLC supplies concentration for Theorems 4.3 and 4.4 after the proposed reductions in the original proofs of the kernel results of Theorems 4.3-4.4. In our initial response, we provided generalized Theorems 4.1-4.2 which generalize the selected solution restriction, common loss normalization, and uniform scale restoration used in the original kernel proofs of Theorems 4.3-4.4. While these novel elements are limited to Transductive Kernel Learning (TKL) in the original proofs of Theorems 4.3-4.4, their generalized forms in the new Theorems 4.1-4.2 can be applied to general application scenarios with TKL being a special case. As a result, the revised Theorems 4.3-4.4 depend on the revised Theorems 4.1-4.2.

The reviewer confirmed that the revised bound for imbalanced splits and the new examples with nonzero excess risk addressed two main concerns in the initial review and indicated an inclination to raise the rating from 2 to 3, assuming the new proofs support the results, while retaining a question about how much the new framework adds beyond these reductions.

To address the reviewer's follow-up concerns about how much the new framework adds beyond these reductions, we emphasize that the generalized Theorems 4.1-4.2 have novel results which are beyond the specific reductions used in the original proofs of Theorems 4.3-4.4. In particular, Theorem 4.2 generalizes the selected solution restriction and common loss normalization from the original proof of Theorem 4.3 to general loss and prediction classes. Combined with Theorem 4.1 which abstracts the normalization and uniform restoration used in the original proof of Theorem 4.4 and the additional moment arguments, this yields the first sharp transductive ERM excess risk bound in Equation (4.5), permitting unbounded losses and an infinite centered envelope. Equation (4.5) of Theorem 4.2 is the first sharp transductive ERM excess risk bound with unbounded loss, to the best of our knowledge.

(2) Reviewer BHBZ. First of all, even though the reviewer found the problem setup on Page 3 and the Section 2 not easy to follow, we respectfully point out that our presentation of the problem setup of transductive learning on Page 3 and the Section 2 of the original submission follows the presentation of the same or similar transductive problem setup in the standard literature, including [1,2,3].

To help the reviewer better understand this paper, we added Appendix E and a main text reference. Appendix E of the revised paper specifies the assumptions, labels, observations, split randomness, selected minimizers, risk comparators, and quantified statements of all four main theorems. It also distinguishes generic ERM, without a realizability assumption, from noisy kernel prediction. The reviewer acknowledged that Appendix E helped them gain a better understanding of the paper, while retaining their overall evaluation without giving any reason.

While we appreciate the reviewer’s time and effort in reviewing our paper, we respectfully disagree with their evaluation, as it overlooks most of the paper’s technical merits and contributions, which were acknowledged by the other two reviewers.

(3) Reviewer monY. We clarified that the conditions required by our general UTLC bounds have their counterparts in the literature of transductive learning and supervised learning with bounded losses. Furthermore, the revised paper provides concrete examples satisfying these conditions. We also explained the relationship between the general unbounded-loss bounds and the sharp rates obtained in the kernel learning applications, and how the additional confidence term in Theorem 4.1 can be improved. Even though the reviewer has not responded to our response, we have addressed all the concerns.

We will faithfully incorporate all promised revisions and would be happy to address any remaining questions or concerns.

Thank you again for your time and consideration.

Regards,

The Authors

References

[1] Tolstikhin et al. Localized complexities for transductive learning. COLT 2014.

[2] Yingzhen Yang. A new concentration inequality for sampling without replacement and its application for transductive learning. ICML 2025.

[3] Yingzhen Yang. Even sharper bounds for transductive learning and its applications. NeurIPS 2026.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.