Improved Risk Bounds with Unbounded Losses for Transductive Learning

There are several major technical drawbacks.

1. While this paper claims that the risk bounds for transductive learning are for unbounded loss functions, the assumptions required for the results are essentially designed for bounded loss functions. For example, the main results Theorem 3 and Theorem 4 need the assumption that $E[f^2] \le B E[f]$. It is well known that such assumption, $E[f^2] \le B E[f]$, holds mainly for bounded loss functions, such as that in the classical local Rademacher complexity work (Bartlett Local Rademacher Complexities, AOS 2005). It turns out that while the paper claims risk bounds for "unbounded loss", but the results rely on the assumption which mainly hold for bounded loss functions.

2. It is well known that Rademacher complexity or local Rademacher complexity based methods derive distribution-free risk bounds that do not need distributional assumptions. In contrast, the risk bounds in the main results Theorem 3 and Theorem 4 require sub-Gaussian and sub-exponential loss functions. It is not clear which loss functions are sub-Gaussian or sub-exponential, and such restriction on the loss functions can significantly limit the application scope of the derived bounds.

3. There are no detailed comparison to the current state-of-the-art risk bounds for the main results in Theorem 3 and Theorem 4, such as the existing transductive bounds in (Tolstikhin et al. 2014, Localized Complexities for Transductive Learning. COLT 2014). Without comparison to prior art, the significance of these results is not clear and questionable.

4. The risk bounds in the main results, Theorem 3 and Theorem 4, do not convergence to 0 under the case that $m = N^{\alpha}$ or $m = N^{\alpha}$ with $\alpha \in (0,1/2]$, and they even diverge to $\infty$ if $\alpha \in (0,1/2)$. This is in a strong contrast to existing risk bounds for excess risk bounds where such bounds should always at least converge to $0$, and it is really misleading to claim such risk bounds are improved ones.

The paper lacks numerical results to support the derived risk bounds. Additionally, as it does not provide lower bounds for the risk, it remains unclear whether the resulting bounds could be further improved.

There are some typos in the paper:

Line 221: we mainly "follows" Line 222: we "introduced" Line 405: w_1^{T+1} -> w^{T+1}

1. The authors do not offer any motivation for addressing unbounded loss. A discussion on why this is an important and relevant problem to study would be beneficial.

2. It is unclear what the significance of Theorems 3 and 4 is. Let’s consider Theorem 3 as an example. Given other terms, the upper bound can at best be $\frac{N^2 \log\left( \frac{1}{\delta}\right)}{m^2 u}.$ The authors claim this bound is state-of-the-art for $m = o(N^{2/5})$. If we set $m = N^{1/5} = o(N^{2/5})$, then $u = N - N^{1/5} \leq N$, and the upper bound is at least $\geq \frac{N^2 \log\left( \frac{1}{\delta}\right)}{N^{2/5} \cdot N} \geq N^{3/5} \log\left( \frac{1}{\delta}\right).$

Given that this is the highest the proven upperbound can be, it is difficult to see why such a bound would be of interest as $N$ can be quite large, making the bound potentially vacuous. I may likely be missing something here, and I would be happy to engage with the authors during the discussion session to gain further clarity and adjust my score.

Weaknesses:

• Limited scope of unbounded loss functions:

  • Analysis is restricted to sub-Gaussian and sub-exponential functions (and sub-Weibull in appendix)
  • Other important classes of unbounded loss functions are not addressed

• Insufficient comparison with prior work:

  • The paper overlooks crucial related work, particularly [1] (Maurer & Pontil, 2021). While [1] focuses on inductive settings, their theoretical foundations appear relevant. A comparative analysis between Theorems 1 and 2 and the results in [1] is needed.

• Limited Contribution:

  • The current contribution of theoretical analysis in the GNN framework is limited. The current results are general and independent of the Graph properties.

Minor Comments:

• In Assumption 3, "α-Hölder" is misspelled
• Add the explanation of Hoeffding's reduction method to the appendix
• Use "Boundedness" instead of "Boundness"
• Use "techniques" instead of "technologies"
• Line 221 "We mainly follows the traditional technique..." --> "We mainly follow the traditional technique"

References:

• [1] Maurer, A., & Pontil, M. (2021). Concentration inequalities under sub-gaussian and sub-exponential conditions. Advances in Neural Information Processing Systems, 34, 7588-7597.