Adapting to Generalized Online Label Shift by Invariant Representation Learning

The problem of online label shift, where label distribution evolves over time while the label-conditional density remains unchanged, has attracted increasing attentions. Although existing approaches have achieved sound theoretical guarantees and encouraging performance, the assumption of an unchanged conditional distribution may limit its application in broader tasks. In this paper, we investigate an extended variant named generalized online label shift (GOLS) problem, in which we relax the label shift assumption on the raw feature space and instead assume the existence of an unknown invariant representation such that conditional distribution of this representation given the label remains constant. To handle GOLS, our main idea involves capturing the inherently stable information from non-stationary streams, in the form of learning an invariant representation. Specifically, we design a novel objective to learn the invariant representation, which exploits the unique structure in GOLS. To optimize this objective, we propose an algorithm employing online ensemble paradigm to perform multi-resolution updates using various historical data windows, thereby enhancing the stability of the representation. This approach is theoretically guaranteed to achieve an optimal convergence rate. To improve the efficiency of the ensemble framework, we further propose a mask-based implementation for ensembling with DNNs. Experiments on benchmarks and real-world tasks validate the effectiveness of our approach.