# Adapting to Online Label Shift with Provable Guarantees

arXiv: https://arxiv.org/abs/2207.02121 · HTML: https://mlsanity.com/paper/2207.02121/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 85 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 30 of 36)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Regularized Learning for Domain Adaptation under Label Shifts](https://mlsanity.com/paper/1903.09734/) (2019)
- [A Unified View of Label Shift Estimation](https://mlsanity.com/paper/2003.07554/) (2020)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Mixture Proportion Estimation via Kernel Embedding of Distributions](https://mlsanity.com/paper/1603.02501/) (2016)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Open-environment Machine Learning](https://mlsanity.com/paper/2206.00423/) (2022)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Class-prior Estimation for Learning from Positive and Unlabeled Data](https://mlsanity.com/paper/1611.01586/) (2016)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Online Adaptation to Label Distribution Shift](https://mlsanity.com/paper/2107.04520/) (2021)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Non-stationary Online Learning with Memory and Non-stochastic Control](https://mlsanity.com/paper/2102.03758/) (2021)
- [Online Forecasting of Total-Variation-bounded Sequences](https://mlsanity.com/paper/1906.03364/) (2019)
- [Minimizing Dynamic Regret and Adaptive Regret Simultaneously](https://mlsanity.com/paper/2002.02085/) (2020)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)

## Built on by (most cited first, 26 of 26)

- [Adapting to Continuous Covariate Shift via Online Density Ratio Estimation](https://mlsanity.com/paper/2302.02552/) (2023)
- [Model Assessment and Selection under Temporal Distribution Shift](https://mlsanity.com/paper/2402.08672/) (2024)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Capturing Conversion Rate Fluctuation during Sales Promotions: A Novel Historical Data Reuse Approach](https://mlsanity.com/paper/2305.12837/) (2023)
- [Fully Test-time Adaptation for Tabular Data](https://mlsanity.com/paper/2412.10871/) (2024)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [ASAP: Unsupervised Post-training with Label Distribution Shift Adaptive Learning Rate](https://mlsanity.com/paper/2508.13445/) (2025)
- [Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach](https://mlsanity.com/paper/2504.07261/) (2025)
- [OASIS: Open-world Adaptive Self-supervised and Imbalanced-aware System](https://mlsanity.com/paper/2508.16656/) (2025)
- [Fed-ADE: Adaptive Learning Rate for Federated Post-adaptation under Distribution Shift](https://mlsanity.com/paper/2603.01040/) (2026)
- [An Adaptive Method for Weak Supervision with Drifting Data](https://mlsanity.com/paper/2306.01658/) (2023)
- [Online Feature Updates Improve Online (Generalized) Label Shift Adaptation](https://mlsanity.com/paper/2402.03545/) (2024)
- [Knowledge Distillation of Uncertainty using Deep Latent Factor Model](https://mlsanity.com/paper/2510.19290/) (2025)
- [Bayesian-based Online Label Shift Estimation with Dynamic Dirichlet Priors](https://mlsanity.com/paper/2511.18615/) (2025)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [Adapting to Covariate Shift in Real-time by Encoding Trees with Motion Equations](https://mlsanity.com/paper/2404.05168/) (2024)
- [An adaptive transfer learning perspective on classification in non-stationary environments](https://mlsanity.com/paper/2405.18091/) (2024)
- [Theory-inspired Label Shift Adaptation via Aligned Distribution Mixture](https://mlsanity.com/paper/2411.02047/) (2024)
- [Privacy Drift: Evolving Privacy Concerns in Incremental Learning](https://mlsanity.com/paper/2412.05183/) (2024)
- [A Guide to Failure in Machine Learning: Reliability and Robustness from Foundations to Practice](https://mlsanity.com/paper/2503.00563/) (2025)
- [Machine Unlearning for Streaming Forgetting](https://mlsanity.com/paper/2507.15280/) (2025)
- [Should Bias be Eliminated? A General Framework to Use Bias for OOD Generalization](https://mlsanity.com/paper/2507.17001/) (2025)
- [GeoTTER: Leveraging Local Geometry of Optimal Transport for Zero-Shot Classification](https://mlsanity.com/paper/2609.13518/) (2026)

## Abstract (arXiv)

The standard supervised learning paradigm works effectively when training data shares the same distribution as the upcoming testing samples. However, this stationary assumption is often violated in real-world applications, especially when testing data appear in an online fashion. In this paper, we formulate and investigate the problem of online label shift (OLaS): the learner trains an initial model from the labeled offline data and then deploys it to an unlabeled online environment where the underlying label distribution changes over time but the label-conditional density does not. The non-stationarity nature and the lack of supervision make the problem challenging to be tackled. To address the difficulty, we construct a new unbiased risk estimator that utilizes the unlabeled data, which exhibits many benign properties albeit with potential non-convexity. Building upon that, we propose novel online ensemble algorithms to deal with the non-stationarity of the environments. Our approach enjoys optimal dynamic regret, indicating that the performance is competitive with a clairvoyant who knows the online environments in hindsight and then chooses the best decision for each round. The obtained dynamic regret bound scales with the intensity and pattern of label distribution shift, hence exhibiting the adaptivity in the OLaS problem. Extensive experiments are conducted to validate the effectiveness and support our theoretical findings.