Adapting to Online Label Shift with Provable Guarantees

• URL: http://arxiv.org/abs/2207.02121v1
• Date: Tue, 5 Jul 2022 15:43:14 GMT
• Title: Adapting to Online Label Shift with Provable Guarantees
• Authors: Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, Zhi-Hua Zhou
• Abstract summary: 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.
• Score: 137.89382409682233
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The standard supervised learning paradigm works effectively when training data shares the same distribution as the upcoming testing samples. However, this 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.

Related papers

• An adaptive transfer learning perspective on classification in non-stationary environments [3.5897534810405403]
  We consider a semi-supervised classification problem with non-stationary label-shift. In this work we explore an alternative approach grounded in statistical methods for adaptive transfer learning. We establish a high-probability regret bound on the test error at any given individual test-time, which adapt automatically to the unknown dynamics of the marginal label probabilities.
  arXiv  Detail & Related papers  (2024-05-28T11:57:29Z)
• Learning with Imbalanced Noisy Data by Preventing Bias in Sample Selection [82.43311784594384]
  Real-world datasets contain not only noisy labels but also class imbalance. We propose a simple yet effective method to address noisy labels in imbalanced datasets.
  arXiv  Detail & Related papers  (2024-02-17T10:34:53Z)
• 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)
• Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms [33.61487362513345]
  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.
  arXiv  Detail & Related papers  (2023-05-31T05:39:52Z)
• All Points Matter: Entropy-Regularized Distribution Alignment for Weakly-supervised 3D Segmentation [67.30502812804271]
  Pseudo-labels are widely employed in weakly supervised 3D segmentation tasks where only sparse ground-truth labels are available for learning. We propose a novel learning strategy to regularize the generated pseudo-labels and effectively narrow the gaps between pseudo-labels and model predictions.
  arXiv  Detail & Related papers  (2023-05-25T08:19:31Z)
• Rethinking Precision of Pseudo Label: Test-Time Adaptation via Complementary Learning [10.396596055773012]
  We propose a novel complementary learning approach to enhance test-time adaptation. In test-time adaptation tasks, information from the source domain is typically unavailable. We highlight that the risk function of complementary labels agrees with their Vanilla loss formula.
  arXiv  Detail & Related papers  (2023-01-15T03:36:33Z)
• Unsupervised Domain Adaptive Salient Object Detection Through Uncertainty-Aware Pseudo-Label Learning [104.00026716576546]
  We propose to learn saliency from synthetic but clean labels, which naturally has higher pixel-labeling quality without the effort of manual annotations. We show that our proposed method outperforms the existing state-of-the-art deep unsupervised SOD methods on several benchmark datasets.
  arXiv  Detail & Related papers  (2022-02-26T16:03:55Z)
• 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)

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.