PaperlayerView exact revision on arXiv

Source-linked AI summary

Regularized Learning for Domain Adaptation under Label Shifts

Kamyar Azizzadenesheli, Anqi Liu, Fanny Yang, Animashree Anandkumar

arXiv:1903.09734v1cs.LGstat.ML

TL;DR

Label shift creates a domain-adaptation problem in which source and target label proportions differ, while target labels are unavailable. RLLS estimates importance weights from labeled source and unlabeled target data, regularizes them in small samples, and provides a dimension-independent generalization bound. On MNIST and CIFAR-10, it improves performance especially under large shifts and low target-sample sizes, though real-world conclusions are limited by the label-shift assumption.

  • Problem

    Label shift changes p(y) between source and target while p(x|y) remains invariant, raising questions about low-sample weight estimation, generalization guarantees, and weight uncertainty without target labels.

  • Method

    RLLS estimates importance weights using labeled source and unlabeled target data, regularizes their influence in low-sample settings, and trains a classifier on weighted source samples.

  • Results

    RLLS outperforms BBSL across MNIST and CIFAR-10 settings, with especially significant improvements for large shifts and low target-sample regimes.

  • Takeaways & Limitations

    RLLS provides a practical label-shift procedure with generalization guarantees and improved weight estimation and predictive performance in the reported image-dataset experiments.

  • Takeaways & Limitations

    The label-shift assumption may be too simplified for real-world data, and the experiments do not establish a conclusive effect of weighting on general predictive results.

Abstract

from arXiv · show

We propose Regularized Learning under Label shifts (RLLS), a principled and a practical domain-adaptation algorithm to correct for shifts in the label distribution between a source and a target domain. We first estimate importance weights using labeled source data and unlabeled target data, and then train a classifier on the weighted source samples. We derive a generalization bound for the classifier on the target domain which is independent of the (ambient) data dimensions, and instead only depends on the complexity of the function class. To the best of our knowledge, this is the first generalization bound for the label-shift problem where the labels in the target domain are not available. Based on this bound, we propose a regularized estimator for the small-sample regime which accounts for the uncertainty in the estimated weights. Experiments on the CIFAR-10 and MNIST datasets show that RLLS improves classification accuracy, especially in the low sample and large-shift regimes, compared to previous methods.

1 INTRODUCTION

The paper addresses label shift, where source and target label proportions differ while class-conditional inputs remain invariant, using labeled source and unlabeled target data. RLLS combines efficient weight estimation, regularization for low-sample settings, and dimension-independent generalization guarantees.

  • Motivation: Real-world deployment can shift target data away from the source distribution, including across regions, domains, hospitals, and time periods.Such shifts motivate adaptation methods for previously unobserved populations and datasets.
  • Problem setting: Label shift assumes p(x|y) = q(x|y) while p(y) changes between source and target, with target labels unavailable during adaptation.The source provides both inputs and outputs, whereas the target provides only inputs.
  • Applications: Label-shift applications include cloud deployment without control over label proportions and medical diagnosis across locations with changing disease distributions.The paper frames these settings around using abundant labeled source data and limited target information.
  • Open questions: Prior approaches leave open how to estimate weights with few samples, guarantee predictor generalization, and handle uncertainty in estimated weights.These gaps motivate a method applicable to large-scale data with statistical guarantees.
  • Contributions: RLLS proposes an efficient weight estimator, sample-size-dependent regularization, and a dimension-independent generalization bound for the final classifier.The method addresses the low-sample regime by controlling the influence of estimated weights.
  • Empirical results: For large target samples and large shifts, RLLS achieves an order of magnitude smaller weight-estimation error and at most 20% higher accuracy and F-1 score than baseline methods.For low target samples, partially applying regularized weights improves accuracy by at least 10% over fully weighted and unweighted methods.

2 REGULARIZED LEARNING OF LABEL SHIFTS (RLLS)

RLLS estimates label-shift importance weights from source and unlabeled target data, then regularizes them to account for finite-sample uncertainty. Its target generalization bound motivates partial weighting when sample sizes are small or weight estimates are unreliable.

  • Label shift assumes p(x|y) = q(x|y) while label probabilities p(y) and q(y) differ between source and target.
  • RLLS estimates importance weights through a classifier’s confusion matrix and target prediction frequencies, then trains a classifier using the estimated weighted empirical loss.The method splits source data between weight estimation and classifier training.
  • The estimator regularizes the shift as bw = 1 + λbθ, with λ controlling how strongly estimated weights influence training and depending on sample size.The procedure computes a measurement-error-adjusted shift estimate before applying this shrinkage.
  • RLLS improves prior guarantees by a factor of k and avoids the minimum sample-complexity requirement associated with BBSL.Its estimator accounts for covariate errors, while the regularized bound is smaller than the unregularized bound for small nq and np.
  • When confusion-matrix singular values are small, RLLS trusts estimated weights only at sufficiently high target sample sizes and believed shifts; otherwise it can use λ = 0.The practical procedure estimates σmin from the empirical confusion matrix, at additional complexity O(k3).
  • Theorem 1 bounds target excess loss by a generalization term plus a blend of true-shift magnitude and weight-estimation error.The bound is L(bh_b_w) − L(h*) ≤ ǫG + (1 − λ)∥θ∥2 + λǫθ.

3 EXPERIMENTS

Experiments on MNIST and CIFAR10 evaluate RLLS across label shifts, sample sizes, and regularization settings. RLLS generally improves over BBSL, especially under large shifts and limited target data, while the unweighted classifier can be preferable in some cases.

  • Experimental setup: Experiments use artificially shifted MNIST and CIFAR10 datasets, varying shift type, sample size, and regularization parameters.Source and target pools are sampled separately, with several non-uniform label-distribution strategies considered.
  • Source shift: For large shifts and 10,000 source and target samples, RLLS yields lower weight-estimation error and higher CIFAR10 accuracy than BBSL.Under Minority-Class source shifts, RLLS outperforms BBSL across shifts, although all methods deteriorate as the shift increases.
  • Target shift: Under Dirichlet target shifts, larger shifts can raise accuracy while reducing macro-F1 for methods that favor the majority class.For α = 0.01, BBSL and the unweighted classifier have low F-1 but high accuracy relative to RLLS; smaller α denotes a larger shift.
  • Low-sample regularization: For very few target samples, unweighted training performs best; for 10 ≤ nq ≤ 500, intermediate λ performs best; for nq > 1000, full weighting performs best.Regularization adapts the influence of estimated weights to their uncertainty across target sample sizes.
  • Low-sample regularization: Fully weighted methods improve sooner with better black-box predictors, whereas corrupted predictors require more target samples to compensate for poorer weight estimation.This behavior reflects the relation between the confusion-matrix eigenvalue σmin and target sample size nq.
  • Summary: Across MNIST and CIFAR10, RLLS outperforms BBSL, but unweighted samples can outperform both, and real-world conclusions remain limited by label-shift assumptions.The authors caution that their experiments do not establish how weighting affects predictive results when those assumptions are not satisfied.

4 RELATED WORK

Related work distinguishes label shift from covariate shift and highlights unresolved challenges in estimating label-importance weights and guaranteeing predictor performance. The paper positions RLLS as addressing these gaps with generalization guarantees for label shift.

  • Covariate-shift methods: Existing shift-correction methods can be computationally burdensome, incompatible with neural networks, or dependent on high-dimensional density-ratio estimation.Importance-weighting bounds may also be extremely loose when they require bounded second moments of q(x)/p(x).
  • Open questions: Prior label-shift work leaves open low-sample weight estimation, generalization guarantees for weighted predictors, and uncertainty handling.These questions motivate the paper’s theoretical and practical treatment of label shift.
  • Theoretical contribution: The paper states that it is the first to provide generalization bounds for label shift when target labels are unavailable.Earlier generalization analyses primarily addressed P = Q or other distribution-shift settings.

5 DISCUSSION

RLLS combines label-shift generalization guarantees with regularized importance weighting, while the discussion identifies practical and theoretical boundaries for the framework.

  • RLLS provides the first generalization guarantee for label shift and requires no prior knowledge of q(y)/p(y).
  • Its sample-size-dependent regularization improves the classifier in both small- and large-sample regimes.
  • The framework is positioned as a step toward handling label shifts, with active learning identified as a future extension.
  • The label-shift assumption may be too simplified because inputs can depend on unobserved attributes beyond the label.If such attributes are observed, the framework can perform importance weighting in the modified conditional setting.
  • Whether higher target accuracy implies greater robustness remains unclear, and the regularization choice is sample-size-based rather than data-driven.
  • In realizable over-parameterized settings with minimum-norm perfect interpolation, weighting empirical loss may not change the trained classifier.How importance weighting improves generalization in broader over-parameterized settings remains open.

A.0.1 CIFAR10 EXPERIMENTS UNDER TWEAK-ONE SHIFT AND DIRICHLET SHIFT

On CIFAR-10, RLLS estimates importance weights more accurately than BBSL across shift types, with its advantage increasing for larger tweak-one shifts.

  • RLLS generally has smaller weight-estimation MSE than BBSL across the tested CIFAR-10 shifts.Figure 5 compares tweak-one and Dirichlet source shifts against a uniform target, using h0 trained on the corresponding shifted source data.
  • As the shift increases, both RLLS and BBSL incur larger weight-estimation errors.
  • For tweak-one shifts, RLLS increasingly outperforms BBSL in both bias and variance as the shift grows.

A.1 MNIST EXPERIMENTS UNDER MINORITY-CLASS SOURCE SHIFTS FOR DIFFERENT VALUES OF p

MNIST experiments show that RLLS’s weight-estimation and accuracy advantages vary with minority-class shift magnitude and the source sample configuration.

  • At p = 0.001 with 10000 training and testing examples, RLLS usually achieves better weight estimation alongside better accuracy.The exception is the four-classes case, where both methods estimate weights poorly.
  • At p = 0.01, accuracy is similar when the minority class count is 1 or 2, but larger shifts reduce performance below the unweighted classifier.
  • At p = 0.005 with three or more minority classes, RLLS outperforms BBSL in weight estimation as the number of minority classes increases.The experiment uses 1000 training and testing examples and a classifier trained on tweak-one shifted source data with ρ = 0.5.
  • As the shift increases, all methods’ performance deteriorates, while RLLS’s advantage over the unweighted classifier grows.
  • Across all tested shifts in the p = 0.005 experiment, the RLLS-based classifier has higher accuracy than the BBSL-based classifier.

A.2 CIFAR10 EXPERIMENT UNDER DIRICHLET SOURCE SHIFTS

The CIFAR-10 Dirichlet-shift experiment evaluates weight estimation and classification under a relatively large source-label shift.

  • Figure 9 evaluates estimated-weight error and final classification performance for a CIFAR-10 Dirichlet source shift.The experiment uses 10000 training and testing examples and trains h0 on tweak-one shifted source data with ρ = 0.5.

A.3 MNIST EXPERIMENT UNDER DIRICHLET SHIFT WITH LOW TARGET SAMPLE SIZE

Under a Dirichlet shift with few target samples, intermediate regularization can outperform fully weighted training initially, while stronger corruption requires more target data for λ = 1 to dominate.

  • Regularization under low target sample size: λ = 1 takes over only after several hundred target examples, whereas some λ between 0 and 1 performs better earlier.The experiment uses 5000 training examples and α = 0.5.
  • Related evaluation: Figure 9 reports estimated-weight mean squared error and CIFAR10 accuracy under a Dirichlet-shifted source and uniform target.The black-box predictor h0 is trained on tweak-one shifted source data.
  • Effect of predictor corruption: More target samples are needed for λ = 1 to take over when the black-box predictor is more corrupted.The comparison varies black-box predictor quality under the Dirichlet shift.
  • Experimental setup: Figure 10 evaluates MNIST performance across target sample sizes and λ values for better, neutral, and corrupted predictors.The source is Dirichlet shifted and the target distribution is uniform.

B.1 PROOF OF LEMMA 1

The proof establishes Lemma 1 by relating finite-sample estimates of the measurement matrix and label vector to their population counterparts, then applying concentration bounds and singular-value control.

  • Optimization and identifiability: Choosing the feasible point θ′ = θ makes ∥Cθ − b∥2 = 0, providing an upper bound for the optimization argument.The proof then uses the minimum singular value to relate parameter error to measurement error.
  • Finite-sample estimates: Finite-sample estimates bC_h and b̂_h are defined in matrix and vector form using a hypothesis h.The estimates use indicator functions, with m = |D_q|.
  • Concentration control: Concentration lemmas bound the estimation errors of bC and b̂ simultaneously with probability at least 1 − δ.The proof invokes separate concentration results for the measurement matrix and label measurements.
  • Conclusion: The resulting asymptotic estimation term is controlled at order O(1/n), yielding the statement of Lemma 1.The supplied proof passage connects the order calculation directly to the lemma.

B.2 PROOF OF LEMMA 2

The proof develops concentration bounds for measurement and label estimates, then combines weighted-loss estimation and uniform-law arguments to control generalization, with an explicit caveat for violated label shift.

  • Measurement-matrix concentration: The measurement matrix is analyzed using matrix Bernstein concentration after applying a dilation technique to self-adjoint random matrices.The dilation preserves the relevant operator norm and enables application of Matrix Bernstein.
  • Label-measurement concentration: Label-probability estimates are treated as empirical means of multinomial one-hot vectors, with separate concentration bounds for the source and target measurements.The proof rewrites the label measurement as a difference between expectations under Q and P.
  • Generalization bound: The target excess-risk proof decomposes error into weight-estimation and finite-sample terms, bounding the latter through uniform laws and Rademacher complexity.Weighted losses are bounded using the importance-weight supremum and bounded-loss assumptions.
  • Uniform deviation control: The proof uses symmetrization, ghost samples, Doob martingales, and Freedman’s inequality to control deviations uniformly over the hypothesis class.The martingale increments are bounded using d∞(q||p), and the argument also handles the negated hypothesis class.
  • Assumption boundary: If the label-shift assumption is slightly violated, the stated generalization bound is expected to deviate from the theorem.The drift analysis introduces a deviation between the actual importance weight ω(X,Y) and the label-only weight w(Y).
Loading 1903.09734v1…