A Trichotomy for List Transductive Online Learning
Authors: Steve Hanneke, Amirreza Shaeiri
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the problem of list transductive online learning. In this framework, the learner outputs a list of multiple labels for each instance rather than just one, as in traditional multiclass classification. In the realizable setting, we demonstrate a trichotomy of possible rates of the minimax number of mistakes. In particular, if the learner plays for T N rounds, its minimax number of mistakes can only be of the orders Θ(T), Θ(log T), or Θ(1). This resolves an open question raised by (Hanneke et al., 2024b). On the other hand, in the agnostic setting, we characterize the learnability by constructively proving the e O(T) upper bound on the minimax expected regret. Along this way, we also answer another open question asked by (Moran et al., 2023). To establish these results, we introduce two new combinatorial complexity dimensions, called the Level-constrained (L + 1)-Littlestone dimension and Level-constrained (L + 1)-Branching dimension, if the list size is L N. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Purdue University, West Lafayette, IN, USA. |
| Pseudocode | Yes | Figure 1: List Transductive Standard Optimal Algorithm (LTSOA) is a variant of Standard Optimal Algorithm (SOA) originally proposed by (Littlestone, 1988). Further, see the definition of Vx y for some V YX , x X, and y Y in the proof of Lemma A.1. In addition, see the definition of a sequence-dependent Level-constraint (L + 1)-Branching dimension in the proof of Lemma A.1. Figure 2: See the definition of Vx y for some V YX , x X, and y Y in the proof of Lemma A.3. In addition, see the definition of Sh(.) in the proof of Lemma A.3. |
| Open Source Code | No | The paper does not provide any statement regarding the release of source code, nor does it include links to any code repositories. |
| Open Datasets | No | Fix a non-empty set X as the instance space. Let L N be the size of the list. Also, fix a non-empty set Y equipped with a σ-algebra such that every subset of Y with cardinality L is measurable as the label space. We note briefly that, since our focus is on deterministic algorithms in the realizable setting, no measurability assumptions on Y are required. Following the well-established frameworks in learning theory, let C YX be a concept class. In particular, a 4-tuple Q = X, L, Y, C presents an instance of the list transductive online learning framework. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore, there are no mentions of dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not include any experimental results or mention any specific hardware used for computations. |
| Software Dependencies | No | The paper describes theoretical algorithms and proofs and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include any experimental setup details, hyperparameters, or training configurations. |