Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift

Summary

This manuscript presents convergence rates for kernel methods under covariate shift. Results fit quite a general framework, including common classification and regression losses. Two approaches are analyzed: (i) a usual M-estimator and (ii) an importance-sampling-like M-estimator. It is shown theoretically and empirically that the latter outperform the former.

Strengths

The analysis presented in this paper provides interesting theoretical results regarding learning under covariate shift, which is a contemporary topic. The manuscript is well organized; it explains clearly the problem, state the results while discussing the hypotheses and, at the end, illustrates the theoretical findings by a numerical experiment. I would like to stress that discussions regarding hypotheses are opportune and corollaries provide intelligible results. The take-home message, stating that the importance-sampling-like estimator is better that the naive one, is interesting and confirms practitioners’ intuition.

Weaknesses

Major remarks: 1) My main concern is about the novelty of the proofs: hypotheses (i) and (ii) look like straightforward tools to link expectations under the source distribution to the target distribution by linearity or Cauchy-Schwarz inequality. I had a very quick glance to the supplementary material and it confirmed this guess (although I admit that I may be wrong). I think that its important, in order to assess the contribution of the paper, that the authors explain the original derivations appearing in the proofs, with respect to techniques used for obtaining similar results without covariate shift (unfortunately, I have no reference in mind). 2) Another (minor) point is that Figure 1 does not seem to verify neither hypothesis (i) nor (ii) since $\phi(x)$ seems to explode when $x \to \infty$. If it is the case, it would be better to find another example (or at least to discuss this point). If it is not the case, it would be informative to explain it. Some suggestions of improvement: 1) $f^*$ is defined in Section 2.1, before the problem setting in Section 2.2. However, in practice, it corresponds to the optimal function under the target distribution, which is not clearly stated. I suggest to make it clear. 2) Although an informed reader understand definitions Line 113, it is not totally clear that expectations are conditioned by observed data. I suggest to had this information. 3) $D$ could be added after “Finite rank” in Table 1. 4) Line 264, it is not totally clear that “For the moment bounded case” correspond to Figure 3. I suggest to had it. Typographical remarks: 1) Extra “the” Line 5. 2) “that” instead of “that is” Lines 126, 131 and 132. 3) In Theorems 1-3, $\delta_n$ should satisfy an inequality that involves $\delta$ instead of $\delta_n$. 4) There are $\phi(\textrm x)$ instead of $\phi(\textrm x)^2$ Lines 212 and 223. 5) Full points are missing in captions.

Questions

1) What is $f_j$ Line 154? 2) What does $\psi_j \le Cj^{-2r}$ (Lines 201 and 235) mean, given that $\psi_j$ is a function? Is a norm missing? 3) Does the trends (evolution with respect to $n$) observed in Figure 2 (b)-(e) and Figure 3 (b)-(e) is of the order $\left( \frac{\log n}{n} \right)^q$ or $\left( \frac{\log^2 n}{n} \right)^q$ as exhibited in Table 1?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Limitations are not addressed.

Summary

The paper provides a unified analysis of convergence properties for different kernel-based estimators under covariate shift. The analysis covers different loss functions and is focused on standard and importance weighted empirical risk estimators. The former are specified in Eq. (1) and the latter in Eq. (3). The first assumption is pretty standard and requires a uniformly bounded kernel function. The second assumption enforces a locally strong convexity on the expected loss function relative to source and target marginal distributions (source available during training, target assumed to be shifted and available at test time). The assumptions that characterize the distribution shift are given on page 4 (lines 131 and 132): i) in the first case the importance weights are $\alpha$-uniformly bounded, ii) in the second case the second moment of the importance weight function is bounded. Theorem 1 gives convergence bounds relative to case i) under the assumptions above. Further assumption is made to give a more readable interpretation of the bound in Corollary 1 which ties the convergence rate to kernel spectrum decay. Theorem 2 gives a similar convergence result in a more difficult case ii), again under the assumptions listed above. Theorem 3 considers an estimator that uses importance weighted empirical risk estimator, with truncated importance weights to avoid issues with tail samples. It is for case ii) and bounded second moment of importance weights. The latter result indicates much tighter convergence rate than the one in Theorem 2 that considers standard estimator without importance weighting. Empirical analysis illustrates the tightness of the bounds on synthetically generated learning tasks and a real-case study.

Strengths

While I have not checked the proofs, the theoretical part of the paper is its strongest point. It is also an interesting characterization of distribution shift carried into the bounds and would be interesting to see what other more granular specifications are possible for future studies. A relative comparison between Theorem 2 and 3 also illustrates the utility of truncated importance weighted estimator, which might be important for practical applications.

Weaknesses

Empirical study might be the weakest part of the paper but given its nature should be fine. It might also be interesting to see how relevant are the assumptions on distribution shift relative to practical applications and datasets.

Questions

The formulation of theorems should be cleaned as currently there are symbols that have not been introduced properly. For instance, it is unclear what $\delta_n$ refers to here and how it is related to $\delta$. The authors have spent a fair amount of space to illustrate the bounds and allow for readers to build some intuition. However, still the clarity could be a bit improved by moving from Appendix C.4 the part that transforms Eq. (5) to (7). At first, I had the impression that the right hand side just will not converge under the assumption on $c_0$ and $\lambda$.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Adequately addressed

Summary

The authors study the covariate shift setting of nonparametric (kernel) methods (Regularized Empirical Risk Minimization with optional importance weighing) with an analysis which includes a wide array of losses and and two conditions on the importance function. They establish sharp convergence which corroborate other rates in literature. Additionally they provide experiments showing these rates in practice.

Strengths

- Quality: The authors extend the results to a wide array of losses and two types of covariate shift problems which is nice. - Clarity: The paper is well-written and notation makes it easy to follow

Weaknesses

- There are quite a bit of terms which are unknown in practice and they need to estimate the importance function which limits the practical impact of the method.

Questions

Could the authors clarify the discrepancy between the theorems and practice in terms of the importance function $\phi$? You mention that you use an estimated function as plugin, do you expect it should be possible to prove results when using a plugin instead of the real thing?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Same as in Questions section. No need for societal impact limitation.

Summary

This paper studies the generalization guarantees of non-parameteric methods in RKHS under covariate shift. Compared to previous work (Ma et al. AOS2023), the authors extend their results from the squared loss to general Lipchitz loss functions. The derived results show that - under the uniformly bounded case for the importantce ratio, the unweighted estimator achieves the optimal learning rates in the $L2(d PT)$ space, where $PT$ is the target distribution. - under the bounded second monment case, the above estimator is sub-optimal. - under a truncated ratio, a sharp learning rate can be achieved.

Strengths

- generalization analysis under covariate shift is derived from the squared loss to general loss functions - Under the the uniformly bounded case and bounded second moment case for the importantce ratio, the results can recover the result under the squared loss - the results are derived under the truncated case

Weaknesses

- Extension from the squared loss to general Lipschitz loss functions is based on Assumption 2. More discussion on this assumption is required for specific loss functions. If the space is limited, the discussion can be deferred to the appendix. - There are several parts unclear in the proof. For example, in the proof of Lemma C.1.2, the notations $P_n$ and $P$ are undefined in Eq.(2), and more details are needed for the first inequality in Eq. (2). - The proof idea and structure is almost the same as (Ma et al. 2023). For example, there is no significant difference between the proof of Theorem 3 and Lemma 2 in (Ma et al. 2023). This is because, under Assumption 2 and Eq. (10), the results under Lipschitz loss functions can be well controlled.

Questions

- Why does $\phi_n(x_i) \leq \phi(x_i)$ hold in line 193?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Thank you

I appreciate the response from the authors and especially the detailed comment on how to potentially derive bounds when using the empirical importance ratio. I will keep my score.