Smoothed Online Classification can be Harder than Batch Classification

• URL: http://arxiv.org/abs/2405.15424v1
• Date: Fri, 24 May 2024 10:37:39 GMT
• Title: Smoothed Online Classification can be Harder than Batch Classification
• Authors: Vinod Raman, Unique Subedi, Ambuj Tewari,
• Abstract summary: We show that smoothed online learning is as easy as learning in the iid batch setting under PAC model. We construct a hypothesis class that is learnable in the iid batch setting under the PAC model but is not learnable under the smoothed online model.
• Score: 18.054632903107546
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online classification under smoothed adversaries. In this setting, at each time point, the adversary draws an example from a distribution that has a bounded density with respect to a fixed base measure, which is known apriori to the learner. For binary classification and scalar-valued regression, previous works \citep{haghtalab2020smoothed, block2022smoothed} have shown that smoothed online learning is as easy as learning in the iid batch setting under PAC model. However, we show that smoothed online classification can be harder than the iid batch classification when the label space is unbounded. In particular, we construct a hypothesis class that is learnable in the iid batch setting under the PAC model but is not learnable under the smoothed online model. Finally, we identify a condition that ensures that the PAC learnability of a hypothesis class is sufficient for its smoothed online learnability.

Related papers

• A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
  Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity. Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks. We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
  arXiv  Detail & Related papers  (2024-02-06T15:45:27Z)
• Semi-Supervised Class-Agnostic Motion Prediction with Pseudo Label Regeneration and BEVMix [59.55173022987071]
  We study the potential of semi-supervised learning for class-agnostic motion prediction. Our framework adopts a consistency-based self-training paradigm, enabling the model to learn from unlabeled data. Our method exhibits comparable performance to weakly and some fully supervised methods.
  arXiv  Detail & Related papers  (2023-12-13T09:32:50Z)
• Shrinking Class Space for Enhanced Certainty in Semi-Supervised Learning [59.44422468242455]
  We propose a novel method dubbed ShrinkMatch to learn uncertain samples. For each uncertain sample, it adaptively seeks a shrunk class space, which merely contains the original top-1 class. We then impose a consistency regularization between a pair of strongly and weakly augmented samples in the shrunk space to strive for discriminative representations.
  arXiv  Detail & Related papers  (2023-08-13T14:05:24Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  This work is inspired by the foundation of PAC and is motivated by the existing regression learning issues. The proposed approach, denoted by epsilon-Confidence Approximately Correct (epsilon CoAC), utilizes Kullback Leibler divergence (relative entropy) It enables the learner to compare hypothesis classes of different complexity orders and choose among them the optimum with the minimum epsilon.
  arXiv  Detail & Related papers  (2023-03-28T15:59:12Z)
• CLIPood: Generalizing CLIP to Out-of-Distributions [73.86353105017076]
  Contrastive language-image pre-training (CLIP) models have shown impressive zero-shot ability, but the further adaptation of CLIP on downstream tasks undesirably degrades OOD performances. We propose CLIPood, a fine-tuning method that can adapt CLIP models to OOD situations where both domain shifts and open classes may occur on unseen test data. Experiments on diverse datasets with different OOD scenarios show that CLIPood consistently outperforms existing generalization techniques.
  arXiv  Detail & Related papers  (2023-02-02T04:27:54Z)
• Complementary Labels Learning with Augmented Classes [22.460256396941528]
  Complementary Labels Learning (CLL) arises in many real-world tasks such as private questions classification and online learning. We propose a novel problem setting called Complementary Labels Learning with Augmented Classes (CLLAC) By using unlabeled data, we propose an unbiased estimator of classification risk for CLLAC, which is guaranteed to be provably consistent.
  arXiv  Detail & Related papers  (2022-11-19T13:55:27Z)
• Prototypical Classifier for Robust Class-Imbalanced Learning [64.96088324684683]
  We propose textitPrototypical, which does not require fitting additional parameters given the embedding network. Prototypical produces balanced and comparable predictions for all classes even though the training set is class-imbalanced. We test our method on CIFAR-10LT, CIFAR-100LT and Webvision datasets, observing that Prototypical obtains substaintial improvements compared with state of the arts.
  arXiv  Detail & Related papers  (2021-10-22T01:55:01Z)
• 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)
• Class-Incremental Learning with Generative Classifiers [6.570917734205559]
  We propose a new strategy for class-incremental learning: generative classification. Our proposal is to learn the joint distribution p(x,y), factorized as p(x|y)p(y), and to perform classification using Bayes' rule. As a proof-of-principle, here we implement this strategy by training a variational autoencoder for each class to be learned.
  arXiv  Detail & Related papers  (2021-04-20T16:26:14Z)
• Training image classifiers using Semi-Weak Label Data [26.04162590798731]
  In Multiple Instance learning (MIL), weak labels are provided at the bag level with only presence/absence information known. This paper introduces a novel semi-weak label learning paradigm as a middle ground to mitigate the problem. We propose a two-stage framework to address the problem of learning from semi-weak labels.
  arXiv  Detail & Related papers  (2021-03-19T03:06:07Z)

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.