2021/07/09 by Ruihan Wu, Chuan Guo, Wu, Ruihan +5 · 8 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2107.04520
openalex publication_date 2021/07/09 · arxiv created 2022/01/05 · arxiv updated 2022/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Machine learning models often encounter distribution shifts when deployed in the real world. In this paper, we focus on adaptation to label distribution shift in the online setting, where the test-time label distribution is continually changing and the model must dynamically adapt to it without observing the true label. Leveraging a novel analysis, we show that the lack of true label does not hinder estimation of the expected test loss, which enables the reduction of online label shift adaptation to conventional online learning. Informed by this observation, we propose adaptation algorithms inspired by classical online learning techniques such as Follow The Leader (FTL) and Online Gradient Descent (OGD) and derive their regret bounds. We empirically verify our findings under both simulated and real world label distribution shifts and show that OGD is particularly effective and robust to a variety of challenging label shift scenarios.