- 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 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
- 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.
- 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
- 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.
- 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
-
Can the main kernel results be derived using bounded STLC after the reductions already used in your proofs?
-
Can the authors clarify the usefulness of the infinite-envelope bound for strongly imbalanced splits?
-
What is the specific gain of Theorem 4.4 over existing inductive kernel ridge regression results?
7 comments
Our Response, Part 2
- Theorem 4.4 applies Theorem 4.1. Under , assign each nonzero RKHS difference the raw function and restoration factor . The normalized functions are bounded by one, and the proof applies the one sided assertion of Theorem 4.1 with after verifying both localized TC conditions with . Restoring the scale gives . 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 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 , , and . For every , the two additional alternatives give, with probability at least ,
\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.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 , it uses full dimensional isotropic inputs, scores with , and a fixed loss depending on the prediction and label. The verification takes , the entire class. Put and . 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:
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)=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). The fourth branch of Equation (4.5) is attained as the minimum for every 0<θ≤1, and the third branch of Equation (4.5) is attained as the strictly smallest branch at θ=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: