Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms

Understand

This paper focuses on supervised and unsupervised online label shift, where the class marginals $Q(y)$ varies but the class-conditionals $Q(x|y)$ remain invariant.

• In the unsupervised setting, our goal is to adapt a learner, trained on some offline labeled data, to changing label distributions given unlabeled online data.
• In the supervised setting, we must both learn a classifier and adapt to the dynamically evolving class marginals given only labeled online data.
• We develop novel algorithms that reduce the adaptation problem to online regression and guarantee optimal dynamic regret without any prior knowledge of the extent of drift in the label distribution.