# Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 98 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [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)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [EuroSAT: A Novel Dataset and Deep Learning Benchmark for Land Use and Land Cover Classification](https://mlsanity.com/paper/1709.00029/) (2017)
- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Leveraging Unlabeled Data to Predict Out-of-Distribution Performance](https://mlsanity.com/paper/2201.04234/) (2022)
- [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)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [On the Use of ArXiv as a Dataset](https://mlsanity.com/paper/1905.00075/) (2019)
- [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)
- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Mixture Proportion Estimation and PU Learning: A Modern Approach](https://mlsanity.com/paper/2111.00980/) (2021)
- [Adaptive piecewise polynomial estimation via trend filtering](https://mlsanity.com/paper/1304.2986/) (2013)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Online Adaptation to Label Distribution Shift](https://mlsanity.com/paper/2107.04520/) (2021)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [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)

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

- [ASAP: Unsupervised Post-training with Label Distribution Shift Adaptive Learning Rate](https://mlsanity.com/paper/2508.13445/) (2025)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [Online Feature Updates Improve Online (Generalized) Label Shift Adaptation](https://mlsanity.com/paper/2402.03545/) (2024)
- [Open Set Label Shift with Test Time Out-of-Distribution Reference](https://mlsanity.com/paper/2505.05868/) (2025)
- [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)
- [Online Non-convex Optimization with Long-term Non-convex Constraints](https://mlsanity.com/paper/2311.02426/) (2023)
- [Theory-inspired Label Shift Adaptation via Aligned Distribution Mixture](https://mlsanity.com/paper/2411.02047/) (2024)
- [Machine Unlearning for Streaming Forgetting](https://mlsanity.com/paper/2507.15280/) (2025)
- [Label Shift Estimation With Incremental Prior Update](https://mlsanity.com/paper/2604.01651/) (2026)

## Abstract (arXiv)

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. Our solution is based on bootstrapping the estimates of online regression oracles that track the drifting proportions. Experiments across numerous simulated and real-world online label shift scenarios demonstrate the superior performance of our proposed approaches, often achieving 1-3% improvement in accuracy while being sample and computationally efficient. Code is publicly available at https://github.com/acmi-lab/OnlineLabelShift.