Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms

• URL: http://arxiv.org/abs/2305.19570v1
• Date: Wed, 31 May 2023 05:39:52 GMT
• Title: Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms
• Authors: Dheeraj Baby, Saurabh Garg, Tzu-Ching Yen, Sivaraman Balakrishnan, Zachary Chase Lipton, Yu-Xiang Wang
• Abstract summary: 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. 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.
• Score: 33.61487362513345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \emph{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.

Related papers

• Active Generalized Category Discovery [60.69060965936214]
  Generalized Category Discovery (GCD) endeavors to cluster unlabeled samples from both novel and old classes. We take the spirit of active learning and propose a new setting called Active Generalized Category Discovery (AGCD) Our method achieves state-of-the-art performance on both generic and fine-grained datasets.
  arXiv  Detail & Related papers  (2024-03-07T07:12:24Z)
• Online Feature Updates Improve Online (Generalized) Label Shift Adaptation [51.328801874640675]
  Our novel method, Online Label Shift adaptation with Online Feature Updates (OLS-OFU), leverages self-supervised learning to refine the feature extraction process. By carefully designing the algorithm, OLS-OFU maintains the similar online regret convergence to the results in the literature while taking the improved features into account.
  arXiv  Detail & Related papers  (2024-02-05T22:03:25Z)
• Adapting to Online Label Shift with Provable Guarantees [137.89382409682233]
  We formulate and investigate the problem of online label shift. The non-stationarity and lack of supervision make the problem challenging to be tackled. Our algorithms enjoy optimal dynamic regret, indicating that performance is competitive with a clairvoyant nature.
  arXiv  Detail & Related papers  (2022-07-05T15:43:14Z)
• Active learning for online training in imbalanced data streams under cold start [0.8155575318208631]
  We propose an Active Learning (AL) annotation system for datasets with orders of magnitude of class imbalance. We present a computationally efficient Outlier-based Discriminative AL approach (ODAL) and design a novel 3-stage sequence of AL labeling policies. The results show that our method can more quickly reach a high performance model than standard AL policies.
  arXiv  Detail & Related papers  (2021-07-16T06:49:20Z)
• Online Adaptation to Label Distribution Shift [37.91472909652585]
  We propose adaptation algorithms inspired by classical online learning techniques such as Follow The Leader (FTL) and Online Gradient Descent (OGD) 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.
  arXiv  Detail & Related papers  (2021-07-09T16:12:19Z)
• Online Continual Adaptation with Active Self-Training [69.5815645379945]
  We propose an online setting where the learner aims to continually adapt to changing distributions using both unlabeled samples and active queries of limited labels. Online Self-Adaptive Mirror Descent (OSAMD) adopts an online teacher-student structure to enable online self-training from unlabeled data. We show that OSAMD achieves favorable regrets under changing environments with limited labels on both simulated and real-world data.
  arXiv  Detail & Related papers  (2021-06-11T17:51:25Z)
• Coping with Label Shift via Distributionally Robust Optimisation [72.80971421083937]
  We propose a model that minimises an objective based on distributionally robust optimisation (DRO) We then design and analyse a gradient descent-proximal mirror ascent algorithm tailored for large-scale problems to optimise the proposed objective.
  arXiv  Detail & Related papers  (2020-10-23T08:33:04Z)
• Active Online Learning with Hidden Shifting Domains [64.75186088512034]
  We propose a surprisingly simple algorithm that adaptively balances its regret and its number of label queries. Our algorithm can adaptively deal with interleaving spans of inputs from different domains.
  arXiv  Detail & Related papers  (2020-06-25T15:23:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.