Online Learning with Set-Valued Feedback

• URL: http://arxiv.org/abs/2306.06247v4
• Date: Tue, 18 Jun 2024 22:11:04 GMT
• Title: Online Learning with Set-Valued Feedback
• Authors: Vinod Raman, Unique Subedi, Ambuj Tewari,
• Abstract summary: We study a variant of online multiclass classification where the learner predicts a single label but receives a textitset of labels as feedback. We show that unlike online multiclass learning with single-label feedback, deterministic and randomized online learnability are textitnot equivalent even in the realizable setting.
• Score: 18.054632903107546
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a variant of online multiclass classification where the learner predicts a single label but receives a \textit{set of labels} as feedback. In this model, the learner is penalized for not outputting a label contained in the revealed set. We show that unlike online multiclass learning with single-label feedback, deterministic and randomized online learnability are \textit{not equivalent} even in the realizable setting with set-valued feedback. Accordingly, we give two new combinatorial dimensions, named the Set Littlestone and Measure Shattering dimension, that tightly characterize deterministic and randomized online learnability respectively in the realizable setting. In addition, we show that the Measure Shattering dimension characterizes online learnability in the agnostic setting and tightly quantifies the minimax regret. Finally, we use our results to establish bounds on the minimax regret for three practical learning settings: online multilabel ranking, online multilabel classification, and real-valued prediction with interval-valued response.

Related papers

• Smoothed Online Classification can be Harder than Batch Classification [18.054632903107546]
  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.
  arXiv  Detail & Related papers  (2024-05-24T10:37:39Z)
• Pseudo-Labeling and Contextual Curriculum Learning for Online Grasp Learning in Robotic Bin Picking [47.4409816260196]
  SSL-ConvSAC combines semi-supervised learning and reinforcement learning for online grasp learning. We demonstrate promise for improving online grasp learning on bin picking tasks using a physical 7-DoF Franka Emika robot arm with a suction gripper.
  arXiv  Detail & Related papers  (2024-03-04T21:41:27Z)
• One-bit Supervision for Image Classification: Problem, Solution, and Beyond [114.95815360508395]
  This paper presents one-bit supervision, a novel setting of learning with fewer labels, for image classification. We propose a multi-stage training paradigm and incorporate negative label suppression into an off-the-shelf semi-supervised learning algorithm. In multiple benchmarks, the learning efficiency of the proposed approach surpasses that using full-bit, semi-supervised supervision.
  arXiv  Detail & Related papers  (2023-11-26T07:39:00Z)
• DualCoOp++: Fast and Effective Adaptation to Multi-Label Recognition with Limited Annotations [79.433122872973]
  Multi-label image recognition in the low-label regime is a task of great challenge and practical significance. We leverage the powerful alignment between textual and visual features pretrained with millions of auxiliary image-text pairs. We introduce an efficient and effective framework called Evidence-guided Dual Context Optimization (DualCoOp++)
  arXiv  Detail & Related papers  (2023-08-03T17:33:20Z)
• A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
  We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. We give a new scale-sensitive dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability.
  arXiv  Detail & Related papers  (2023-07-07T20:11:07Z)
• Label Inference Attack against Split Learning under Regression Setting [24.287752556622312]
  We study the leakage in the scenario of the regression model, where the private labels are continuous numbers. We propose a novel learning-based attack that integrates gradient information and extra learning regularization objectives.
  arXiv  Detail & Related papers  (2023-01-18T03:17:24Z)
• Maximising the Utility of Validation Sets for Imbalanced Noisy-label Meta-learning [16.318123642642075]
  We propose a new imbalanced noisy-label meta-learning (INOLML) algorithm that automatically builds a validation set by maximising its utility. Our method shows significant improvements over previous meta-learning approaches and sets the new state-of-the-art on several benchmarks.
  arXiv  Detail & Related papers  (2022-08-17T08:02:53Z)
• Label Matching Semi-Supervised Object Detection [85.99282969977541]
  Semi-supervised object detection has made significant progress with the development of mean teacher driven self-training. Label mismatch problem is not yet fully explored in the previous works, leading to severe confirmation bias during self-training. We propose a simple yet effective LabelMatch framework from two different yet complementary perspectives.
  arXiv  Detail & Related papers  (2022-06-14T05:59:41Z)
• One Positive Label is Sufficient: Single-Positive Multi-Label Learning with Label Enhancement [71.9401831465908]
  We investigate single-positive multi-label learning (SPMLL) where each example is annotated with only one relevant label. A novel method named proposed, i.e., Single-positive MultI-label learning with Label Enhancement, is proposed. Experiments on benchmark datasets validate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2022-06-01T14:26:30Z)
• Contrastive Test-Time Adaptation [83.73506803142693]
  We propose a novel way to leverage self-supervised contrastive learning to facilitate target feature learning. We produce pseudo labels online and refine them via soft voting among their nearest neighbors in the target feature space. Our method, AdaContrast, achieves state-of-the-art performance on major benchmarks.
  arXiv  Detail & Related papers  (2022-04-21T19:17:22Z)
• SLADE: A Self-Training Framework For Distance Metric Learning [75.54078592084217]
  We present a self-training framework, SLADE, to improve retrieval performance by leveraging additional unlabeled data. We first train a teacher model on the labeled data and use it to generate pseudo labels for the unlabeled data. We then train a student model on both labels and pseudo labels to generate final feature embeddings.
  arXiv  Detail & Related papers  (2020-11-20T08:26:10Z)

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.