A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning

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

(1) “…many notations which may be hard to digest for readers. There are also many typos.”

Thank you for your suggestions. We have proofread this paper and fixed all the typos. In particular, all the typos in your “Other Comments Or Suggestions” have been fixed.

(2) “The proof is technical and not easy to follow. For example, in Section B.2, the paper introduces…

Following your suggestion, we will add more explanations and motivations to give readers a better understanding of the notations and their roles in our proofs. In particular, $E(h,\mathbf d, \mathbf d^{(i)})$ is the change of the test-train loss if only the $i$-th element of $\mathbf d$ is changed (that is, $\mathbf d$ is cbanged to $\mathbf d^{(i)}$). The reason we introduced $E(h,\mathbf d, \mathbf d^{(i)})$ is that it is needed in the computation of the upper variance $V_+(Z)$, and such upper variance $V_+(Z)$ will be used in the exponential version of the Efron-Stein inequality (Eq. (23)) to derive the upper bound of the logarithm of the moment generating function of $Z-E[Z]$. Such upper bound of the moment generating function of $Z-E[Z]$ will in turn be used to derive the test-train bound for transductive learning in the proof of Theorem 3.1.

Furthermore, please also kindly refer to part (1) of our response to Reviewer PUBb for a detailed roadmap of our proofs.

(3) “The result only shows advantage when m and u are imbalanced. For the typical setting with m and u of the same order…”

The key advantage of our transductive learning bounds in this paper over those in [Tolstikhin et al., 2014] is that our bounds are sharper than those in [Tolstikhin et al., 2014] for unbalanced training/test features. It is important to note that our bounds, such as the excess risk bound for transductive kernel learning in Theorem 4.1, address both unbalanced and balanced training/test features in a unified framework.

(4)”…The paper does not consider more practical applications such as graph neural networks.”

Following the suggestion of this review, we will add another application to linear Graph Neural Networks (GNNs) for a transductive node classification task in the final version of this paper.

Addressing Other Comments Or Suggestions

We will fix all the typos and reformat Eq. (1). $r^*$ in Theorem 3.6 is the $r^*$ in Theorem B.11, which will be defined before Theorem 3.6 in the final version of this paper. We will add the assumption that $f$ is convex in Theorem A.6.

$V_+(Z)$ defined in Theorem A.2 is the “upper variance” of the random variable $Z$ as a function of $n$ independent random variables $X_1,\ldots, X_n$. In particular, $V_+(Z)$ measures the variance of $Z$ when $X_i$ is changed to another sample $X'_i$ for all $i \in [n]$.

$\psi$ is defined as $\psi(x) = x(e^x-1)$ which will be added to Proposition A.4.

References

[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.

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

(1) Minimax Optimal Lower Bound for Transductive Kernel Learning

We consider the following setup for Transductive Kernel Learning (TKL) wherein we will derive the minimax optimal lower bound for this setup with a matching upper bound by Theorem 3.5. Such results would show that Theorem 3.5 gives sharp upper bound.

Transductive Setting: Suppose that the full-sample $\mathbf X_n = (\mathbf x_i, i \in [n])$ are i.i.d. samples distributed uniformly on the unit sphere $\mathcal S^{d-1}$ in $\mathbb R^d$. This is one standard transductive setting considered in [Tolstikhin et al., 2016] where transductive lower bound is given.

Suppose that kernel $K$ is defined on $\mathcal S^{d-1}$ such that the eigenvalue of the integral operator associated with $K$ is $\lambda_j \asymp j^{-2\alpha}$ with $\alpha > 1/2$. For example, $2\alpha = d/(d-1)$ holds for the arccosine kernel. We consider the function class $\mathcal F = \mathcal H_{\mathbf X_m} \cap \mathcal H_K(\mu)$ with a positive constant $\mu$. We assume that the target function $f^* \in \mathcal H_K(\mu)$ and $y_i = f^*(\mathbf x_i) + w_i$ where $w_i$ for $i \in [n]$ are i.i.d. Gaussian noise with mean $0$ and variance $\sigma^2$. $\mathcal U_f$ and $\mathcal L_f$ are the test loss and the training loss defined as $\mathcal U_f = \sum_{\mathbf x \in \mathbf X_u} (f(\mathbf x)-f^*(\mathbf x))^2$ and $\mathcal L_f = \sum_{\mathbf x \in \mathbf X_m} (f(\mathbf x)-f^*(\mathbf x))^2$.

We have the following minimax lower bound. “With high probability” means that the probability goes to $1$ with $m \to \infty$.

Theorem (Minimax Lower Bound). Suppose $u \ge \Theta(m^{(2d+1)/(2d-1)})$, then with high probability, $\inf_{f \in \mathcal F}\sup_{f^* \in \mathcal H_K(\mu)}\mathcal U_f \ge \Theta(m^{-d/(2d-1)})$.
Proof. First of all, let $E(f-f^*)^2$ be the $L^2$-distance between $f$ and $f^*$ in the $L^2$ space. Then we have $\inf_{f \in \mathcal F } \sup_{f^* \in \mathcal H_K(\mu)} E(f-f^*)^2 \ge \Theta(m^{-d/(2d-1)})$ by repeating the proof of the standard minimax lower bound in [Wainwright 2019] (e.g. Example 15.23). Then for every $f \in \mathcal F$ there exists $\hat f^*(f) \in \mathcal H_K(\mu)$ such that $E(f- \hat f^*(f))^2 \ge \Theta(m^{-d/(2d-1)})$. We apply the standard concentration inequality so that $\mathcal U_{f} - E(f-\hat f^*(f))^2 \ge -\Theta(1/{\sqrt u})$ holds for all $f, \hat f^*(f)$ with high probability. With $u \ge \Theta(m^{(2d+1)/(2d-1)})$, we have $\mathcal U_{f} \ge -\Theta(m^{-(d+0.5)/(2d-1)}) + E(f- \hat f^*(f))^2 \ge \Theta(m^{-d/(2d-1)})$ holds for all $f$ and $\hat f^*(f)$, completing the proof.

Based on our Theorem 3.5, we have the matching upper bound below. Suppose $g_{\mathbf \beta(T)}$ is the kernel regressor obtained by performing $T$ steps of gradient descent on the training objective $L(\mathbf \beta) = \sum_{\mathbf x \in \mathbf X_m} (g_{\mathbf \beta}(\mathbf x) – y(\mathbf x) )^2$ where $g_{\mathbf \beta}(\cdot) = \sum_{\mathbf x \in \mathbf X_m} K(\cdot,\mathbf x) \mathbf \beta(\mathbf x)$. For a training point $\mathbf x$, $\beta(\mathbf x)$ and $y(\mathbf x)$ are the coefficient and the label of this point.

Theorem (Matching Upper Bound). Suppose $T \asymp \Theta(m^{d/(2d-1)})$ and $g = g_{\mathbf \beta(T)}$. Then with high probability, $\mathcal U_{g} \le \Theta(m^{-d/(2d-1)})$.

Proof. By the proof of part (a) of [Raskutti et al., 2014] we have the training loss which satisfies $\mathcal L_{g} \le \Theta(m^{-d/(2d-1)})$. By repeating the proof of Theorem 4.1, the bound for $\mathcal L_{g}$, and applying Theorem 3.5, we obtain $\mathcal U_{g} \le \Theta(m^{-d/(2d-1)})$.

(2) Addressing Other Issues

We will explain the notations with their motivations. Algorithm 1 generates the test features $\mathbf X_u$ with indices in $\mathbf Z_{\mathbf d}$ sampled without replacement. $h^2$ appears in our Transductive Complexity (TC) because we used the exponential version of the Efron-Stein inequality to derive our transductive bounds which involve the square of loss functions. We note that using the bounds for TC in Theorem 2.1, we achieve the transductive bounds sharper than the current state-of-the-art in [Tolstikhin et al., 2014] and the minimax optimal bound in part (1) of this response.

References

[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.

[Tolstikhin et al., 2016] Tolstikhin, I. Oi, Lopez-Paz, D. Minimax Lower Bounds for Realizable Transductive Classification. arXiv:1602.03027, 2016.

[Raskutti et al., 2014] Raskutti, G., Wainwright, M. J., and Yu, B. Early stopping and non-parametric regression: an optimal data dependent stopping rule. JMLR 2014.

[Wainwright 2019] M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.

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

(1) Proof Roadmap

Following the suggestion, we will give a detailed proof roadmap in the final main paper. In particular, we first obtain a novel concentration inequality of the test-train process in Theorem 3.1. Applying the peeling strategy to Theorem 3.1, we obtain the first transductive learning bound in Theorem 3.2 which involves the surrogate variance operator $\tilde T_n$ and the Transductive Local Complexity (TLC). By taking a particular form of the surrogate variance operator in Eq. (12), we obtain the refined transductive learning bound in Theorem 3.5 under the standard assumption (Assumption 1) with bounded loss functions. The excess risk bound in Theorem 3.6 is then a consequence of Theorem 3.5 and the auxiliary results in Theorem B.11. The excess risk bound for transductive kernel learning in Theorem 4.1 is obtained by applying Theorem 3.5 and Theorem 3.6 to the transductive kernel learning task. We will also provide an illustration of the above roadmap in the final version of this paper for better understanding of our proof roadmap and proof strategies.

(2) Applications of the Transductive Learning Bounds in This Paper

We would like to mention that the transductive learning bounds in this paper have been applied to transductive kernel learning with the excess risk bound for transductive kernel learning in Theorem 4.1. We will add another application to linear Graph Neural Networks (GNNs) for a transductive node classification task in the final version of this paper.

(3) “…, since we want to bound the LHS and the LHS "appears again" in the bound.”

We respectfully point out that the LHS of our transductive bound is usually the test loss, and the RHS is usually the sum of the training loss and $r$ which is the fixed point of some sub-root function. We agree that such $r$ involves both the training features and the test features, but this does not suggest that the LHS to be bounced also appears on the RHS. In particular, the LHS is the test loss computed on the test features and the labels on the test features, while $r$ is computed on the training features and the test features (without the labels on the test features). In this sense, we respectfully disagree that LHS "appears again" in the RHS (the bound). We also remark that the learner for a transductive learning task can access both the training and the test features. For an example, in our excess risk bound for the transductive kernel learning in Theorem 4.1, $r = r(u,m,Q)$ is defined in terms of the eigenvalues of the gram matrix $\mathbf K$ over the full sample including the training features and the test features. Such $r(u,m,Q)$ can in fact be estimated from $\mathbf K$ as the transductive learning algorithm has access to the full sample. Even though both the LHS (the test loss) and the RHS ($r(u,m,Q)$) depend on the test features, $r(u,m,Q)$ does not involve the labels on the test features, so the derived bound for the LHS is still reasonable and sharper than the current state-of-the-art in [Tolstikhin et al., 2014].

References

[Tolstikhin et al., 2014] Tolstikhin, I. O., Blanchard, G., and Kloft, M. Localized complexities for transductive learning. COLT 2014.

We appreciate the positive review and the suggestions in this review. We will add a "Related Work" section to the final version of this paper following your suggestion. We will also discuss the application of our transudative learning bounds to linear Graph Neural Networks (GNNs) for a transudative node classification task in the final version of paper.