When Invariant Representation Learning Meets Label Shift: Insufficiency and Theoretical Insights

You-Wei Luo, Chuan-Xian Ren

Abstract

As a crucial step toward real-world learning scenarios with changing environments, dataset shift theory and invariant representation learning algorithms have been extensively studied to relax the identical distribution assumption in classical learning settings. Among the different assumptions on the essence of shifting distributions, generalized label shift (GLS) is the latest developed one which shows great potential to deal with the complex factors within the shift. In this paper, we aim to explore the limitations of current dataset shift theory and algorithms, and further provide new insights by presenting a comprehensive understanding of GLS. From a theoretical aspect, two informative generalization bounds are derived, and the GLS learner is proved to be sufficiently close to the optimal target model from the Bayesian perspective. The main results show the insufficiency of invariant representation learning and prove the sufficiency and necessity of GLS correction for generalization, which provide theoretical supports and innovations for exploring generalizable models under dataset shift. From a methodological aspect, we provide a unified view of existing shift correction frameworks and propose a kernel embedding-based correction algorithm (KECA) to minimize the generalization error and achieve successful knowledge transfer. Both theoretical results and extensive experiment evaluations demonstrate the sufficiency and necessity of GLS correction for addressing dataset shift and the superiority of the proposed algorithm.

Introduction

In classical machine learning, the foundational assumption is that training (source) and test (target) data are drawn from the same distribution. However, real-world applications frequently encounter "dataset shift," where environmental changes—such as varying lighting in computer vision or evolving demographics in tabular data—cause models to fail.

To combat this, researchers have traditionally relied on Invariant Representation Learning (IRL). The goal of IRL is to map data into a feature space where the source and target distributions are indistinguishable. While effective in many scenarios, most IRL methods operate under the assumption that class proportions (e.g., the ratio of "cats" to "dogs") remain constant. When these proportions change—a phenomenon known as Label Shift—standard alignment techniques can inadvertently misalign the data, forcing the model to make incorrect trade-offs. This paper investigates the Generalized Label Shift (GLS) setting, where both feature distributions and label proportions shift simultaneously, and demonstrates that standard IRL is fundamentally insufficient for these complex scenarios.

The Insufficiency of Invariant Representation Learning

A core contribution of this research is the formalization of why standard IRL fails under label shift. The authors present an "Impossibility Result" (Proposition 1), which states that if label shift exists, it is mathematically impossible to achieve both marginal invariance (making the entire feature clouds overlap) and conditional invariance (making class-specific clusters overlap) at the same time.

If a model prioritizes marginal invariance without accounting for label shift, it will inevitably suffer from a non-zero "error floor" on the target domain, regardless of the volume of training data. This theoretical insight proves that explicit label shift correction is not merely an optimization but a mathematical necessity for generalization in non-stationary environments.

Methodology: The KECA Algorithm

To address these limitations, the authors propose the Kernel Embedding-based Correction Algorithm (KECA). Unlike standard models that only utilize a transformation ($g$) and a classifier ($h$), KECA introduces a triplet model $(g, h, w)$, where $w$ represents importance weights for labels.

KECA operates through three primary mechanisms:

  1. Weight Estimation ($w$): The algorithm utilizes Black Box Shift Estimation (BBSE) to calculate the shift in label proportions. This is a critical step because target labels are unknown during training, requiring the model to estimate the shift based on feature distributions.
  2. GLS Correction via CMMD: The algorithm aligns distributions using Conditional Maximum Mean Discrepancy (CMMD) within a Reproducing Kernel Hilbert Space (RKHS). This ensures that specific classes in the source domain are aligned with their corresponding classes in the target domain, preventing the "cluster misalignment" common in marginal alignment methods.
  3. Warm-up Strategy: To resolve the dependency between good label estimation and good feature alignment, a warm-up phase is conducted on source data. This ensures that the initial pseudo-labels generated for the target domain are sufficiently reliable for the subsequent shift estimation.

Theoretical Insights and Bayesian Connection

Beyond the algorithm, the paper provides a Bayesian justification for GLS correction. The authors prove that a GLS-corrected learner is "sufficiently close" to the optimal target model. This suggests that the triplet model $(g, h, w)$ is the theoretically sound approach to minimizing the generalization bound when environments change. The research highlights that label weights are a requirement for successful knowledge transfer, providing a unified view of existing shift correction frameworks.

Experimental Results

The KECA framework was evaluated against standard benchmarks, including Office-31, Office-Home, and the large-scale VisDA-2017 dataset. To simulate real-world conditions, the authors introduced artificial imbalances by subsampling specific classes.

  • Office-Home: KECA achieved an average accuracy of 65.9%, significantly outperforming standard conditional alignment (CDAN), which reached only 56.3%.
  • VisDA-2017: On this synthetic-to-real challenge, KECA reached 72.4% accuracy, compared to 62.9% for CDAN.
  • Qualitative Analysis: t-SNE visualizations confirmed that KECA produces tighter and better-separated class clusters in the target domain. While models ignoring label reweighting often suffered from overlapping class boundaries, KECA maintained distinct separations even under significant shift.

Conclusion

This work demonstrates that invariant representation learning is insufficient when label distributions are non-stationary. By introducing the KECA algorithm and providing rigorous proofs for the necessity of GLS correction, the authors offer a new path forward for robust domain adaptation. Future research will explore extending these insights into Domain Generalization—where the target domain is entirely unseen—and Source-Free Domain Adaptation, where privacy constraints prevent access to original source data.

Summary updated

Abstract

As a crucial step toward real-world learning scenarios with changing environments, dataset shift theory and invariant representation learning algorithm have been extensively studied to relax the identical distribution assumption in classical learning setting. Among the different assumptions on the essential of shifting distributions, generalized label shift (GLS) is the latest developed one which shows great potential to deal with the complex factors within the shift. In this paper, we aim to explore the limitations of current dataset shift theory and algorithm, and further provide new insights by presenting a comprehensive understanding of GLS. From theoretical aspect, two informative generalization bounds are derived, and the GLS learner is proved to be sufficiently close to optimal target model from the Bayesian perspective. The main results show the insufficiency of invariant representation learning, and prove the sufficiency and necessity of GLS correction for generalization, which provide theoretical supports and innovations for exploring generalizable model under dataset shift. From methodological aspect, we provide a unified view of existing shift correction frameworks, and propose a kernel embedding-based correction algorithm (KECA) to minimize the generalization error and achieve successful knowledge transfer. Both theoretical results and extensive experiment evaluations demonstrate the sufficiency and necessity of GLS correction for addressing dataset shift and the superiority of proposed algorithm.
BibTeX
@article{luo2024when,
  author = {You-Wei Luo and Chuan-Xian Ren},
  title = {{When Invariant Representation Learning Meets Label Shift: Insufficiency and Theoretical Insights}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2024},
  url = {https://openreview.net/forum?id=q9RQ9KBLJJ},
}
Figure