mlsanityData to 14 Oct 2026

Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms

arXiv 2305.19570 ↗First posted 31 May 2023stat.ML cs.LGcited by 11

Not on the map. Why?

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.

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

44 of 98 references.

References · 44

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017On Calibration of Modern Neural Networkscited by 4,960
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  4. 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,307
  5. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,218
  6. 2017EuroSAT: A Novel Dataset and Deep Learning Benchmark for Land Use and Land Cover Classificationcited by 1,496
  7. 2020WILDS: A Benchmark of in-the-Wild Distribution Shiftscited by 1,375
  8. 2019Class-Balanced Loss Based on Effective Number of Samplescited by 1,245
  9. 2019Introduction to Online Convex Optimizationcited by 803
  10. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  11. 2018Detecting and Correcting for Label Shift with Black Box Predictorscited by 366
  12. 2018Learning from positive and unlabeled data: a surveycited by 219
32 more
  1. 2013Non-stationary Stochastic Optimizationcited by 175
  2. 2022Leveraging Unlabeled Data to Predict Out-of-Distribution Performancecited by 145
  3. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  4. 2019Regularized Learning for Domain Adaptation under Label Shiftscited by 120
  5. 2020A Unified View of Label Shift Estimationcited by 119
  6. 2015Strongly Adaptive Online Learningcited by 107
  7. 2019On the Use of ArXiv as a Datasetcited by 103
  8. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  9. 2020Dynamic Regret of Convex and Smooth Functionscited by 90
  10. 2016Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradientcited by 66
  11. 2021Mixture Proportion Estimation and PU Learning: A Modern Approachcited by 52
  12. 2013Adaptive piecewise polynomial estimation via trend filteringcited by 47
  13. 2014Trend Filtering on Graphscited by 45
  14. 2022Parameter-free Mirror Descentcited by 45
  15. 2021Online Adaptation to Label Distribution Shiftcited by 44
  16. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 40
  17. 2020Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functionscited by 33
  18. 2021Non-stationary Online Learning with Memory and Non-stochastic Controlcited by 33
  19. 2022Domain Adaptation under Open Set Label Shiftcited by 32
  20. 2019Online Forecasting of Total-Variation-bounded Sequencescited by 31
  21. 2023RLSbench: Domain Adaptation Under Relaxed Label Shiftcited by 30
  22. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 28
  23. 2018Smoothed Online Optimization for Regression and Controlcited by 26
  24. 2022Adapting to Online Label Shift with Provable Guaranteescited by 26
  25. 2016Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smootherscited by 20
  26. 2015A Chaining Algorithm for Online Nonparametric Regressioncited by 16
  27. 2022Domain Adaptation under Missingness Shiftcited by 13
  28. 2016Online Isotonic Regressioncited by 9
  29. 2021An Optimal Reduction of TV-Denoising to Adaptive Online Learningcited by 9
  30. 2022Unsupervised Learning under Latent Label Shiftcited by 9
  31. 2022Second Order Path Variationals in Non-Stationary Online Learningcited by 7
  32. 2020Non-stationary Online Regressioncited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 6; 2026: 2.

11 papers.

  1. 2025ASAP: Unsupervised Post-training with Label Distribution Shift Adaptive Learning Ratecited by 3
  2. 2025Adaptive Estimation and Learning under Temporal Distribution Shiftcited by 2
  3. 2024Online Feature Updates Improve Online (Generalized) Label Shift Adaptationcited by 1
  4. 2025Open Set Label Shift with Test Time Out-of-Distribution Referencecited by 1
  5. 2025Knowledge Distillation of Uncertainty using Deep Latent Factor Modelcited by 1
  6. 2025Bayesian-based Online Label Shift Estimation with Dynamic Dirichlet Priorscited by 1
  7. 2026Gradient-Variation Regret Bounds for Unconstrained Online Learningcited by 1
  8. 2023Online Non-convex Optimization with Long-term Non-convex Constraintscited by 0
  9. 2024Theory-inspired Label Shift Adaptation via Aligned Distribution Mixturecited by 0
  10. 2025Machine Unlearning for Streaming Forgettingcited by 0
  11. 2026Label Shift Estimation With Incremental Prior Updatecited by 0