Marginal singularity and the benefits of labels in covariate-shift

Transfer Learning addresses common situations in Machine Leaning where little or no labeled data is available for a target prediction problem—corresponding to a distribution Q, but much labeled data is available from some related but different data distribution P. This work is concerned with the fundamental limits of transfer, that is, the limits in target performance in terms of (1) sample sizes from P and Q, and (2) differences in data distributions P, Q. In particular, we aim to address practical questions such as how much target data from Q is sufficient given a certain amount of related data from P, and how to optimally sample such target data for labeling. We present new minimax results for transfer in nonparametric classification (i.e., for situations where little is known about the target classifier), under the common assumption that the marginal distributions of covariates differ between P and Q (often termed covariate-shift). Our results are first to concisely capture the relative benefits of source and target labeled data in these settings through information-theoretic limits. Namely, we show that the benefits of target labels are tightly controlled by a transfer-exponent γ that encodes how singular Q is locally with respect to P, and interestingly paints a more favorable picture of transfer than what might be believed from insights from previous work. In fact, while previous work rely largely on refinements of traditional metrics and divergences between distributions, and often only yield a coarse view of when transfer is possible or not, our analysis—in terms of γ—reveals a continuum of new regimes ranging from easy to hard transfer. We then address the practical question of how to efficiently sample target data to label, by showing that a recently proposed semi-supervised procedure—based on k-NN classification, can be refined to adapt to unknown γ and, therefore, requests target labels only when beneficial, while achieving nearly minimax-optimal transfer rates without knowledge of distributional parameters. Of independent interest, we obtain new minimax-optimality results for vanilla k-NN classification in regimes with nonuniform marginals.