Universal Multiclass Transductive Online Learning

• URL: http://arxiv.org/abs/2605.30479v1
• Date: Thu, 28 May 2026 18:51:53 GMT
• Title: Universal Multiclass Transductive Online Learning
• Abstract summary: We consider the problem of universal transductive online classification with a possibly label space.<n>This setting considers online learning, with the sequence of instances known to the learner in advance.
• Score: 32.4543379850765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.

Related papers

• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  We consider the problem of learning an unknown subset $N_texttarget$ of a domain in an online setting.<n>This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback.<n>We show that a hypothesis class is learnable in this setting if and only if it has finite Vapnik-Chervonenkis dimension.
  arXiv  Detail & Related papers  (2026-05-10T14:28:05Z)
• On Improving Neurosymbolic Learning by Exploiting the Representation Space [54.16389421332958]
  We study the problem of learning neural classifiers in a neurosymbolic setting where the hidden gold labels of input instances must satisfy a logical formula.<n>One challenge is that the space of label combinations can grow exponentially, making learning difficult.<n>We propose a technique that prunes this space by exploiting the intuition that instances with similar latent representations are likely to share the same label.
  arXiv  Detail & Related papers  (2026-02-08T13:56:47Z)
• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Understanding Aggregations of Proper Learners in Multiclass Classification [4.422219522591412]
  Multiclass learnability is known to exhibit a properness barrier.<n>Recent advances in binary classification have demonstrated that this requirement can be satisfied using aggregations of proper learners.<n>We show that a single ERM requires $Omega left(fracd_G ln (1 / delta)epsilonright)$ samples.
  arXiv  Detail & Related papers  (2024-10-30T07:12:02Z)
• The Dimension of Self-Directed Learning [18.701165230774325]
  We study the self-directed learning complexity in both the binary and multi-class settings. We develop a dimension, $SDdim$, that exactly characterizes the self-directed learning mistake-bound for any concept class. We demonstrate several learnability gaps with a central focus on self-directed learning and offline sequence learning models.
  arXiv  Detail & Related papers  (2024-02-20T21:59:41Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  We present new upper and lower bounds on the number of learner mistakes in the transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes a sequence of instances to be labeled at the start of the game, and this sequence is known to the learner.
  arXiv  Detail & Related papers  (2023-11-10T23:27:23Z)
• Simple online learning with consistent oracle [55.43220407902113]
  We consider online learning in the model where a learning algorithm can access the class only via the emphconsistent oracle -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far.
  arXiv  Detail & Related papers  (2023-08-15T21:50:40Z)
• Multi-Label Knowledge Distillation [86.03990467785312]
  We propose a novel multi-label knowledge distillation method. On one hand, it exploits the informative semantic knowledge from the logits by dividing the multi-label learning problem into a set of binary classification problems. On the other hand, it enhances the distinctiveness of the learned feature representations by leveraging the structural information of label-wise embeddings.
  arXiv  Detail & Related papers  (2023-08-12T03:19:08Z)
• Multiclass Online Learning and Uniform Convergence [34.21248304961989]
  We study multiclass classification in the adversarial online learning setting. We prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite.
  arXiv  Detail & Related papers  (2023-03-30T21:35:48Z)
• List Online Classification [13.358536176734999]
  We study multiclass online prediction where the learner can predict using a list of multiple labels. We characterize learnability in this model using the $b$-ary Littlestone dimension. As part of our work, we adapt classical algorithms such as Littlestone's SOA and Rosenblatt's Perceptron to predict using lists of labels.
  arXiv  Detail & Related papers  (2023-03-27T16:56:57Z)
• Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning [66.05472746340142]
  This paper analyzes how multi-layer neural networks can perform hierarchical learning _efficiently_ and _automatically_ by SGD on the training objective. We establish a new principle called "backward feature correction", where the errors in the lower-level features can be automatically corrected when training together with the higher-level layers.
  arXiv  Detail & Related papers  (2020-01-13T17:28:29Z)

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.