Multiclass Transductive Online Learning

Steve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi · 2024

Read Multiclass Transductive Online Learning by Steve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01634.txt.

Description

Abstract We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2023b] only consider the case of binary and finite label spaces, respectively.

Catalog record

CREATORSteve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01634

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multiclass Transductive Online Learning Steve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi Abstract We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2023b] only consider the case of binary and finite label spaces, respectively. The latter work determined that their techniques fail to extend to the case of unbounded label spaces, and they pose the question of characterizing the optimal mistake bound for unbounded label spaces. We answer this question by showing that a new dimension, termed the Level-constrained Littlestone dimension, characterizes online learnability in this setting. Along the way, we show that the trichotomy of possible minimax rates of the expected number of mistakes established by Hanneke et al. [2023b] for finite label spaces in the realizable setting continues to hold even when the label space is unbounded. In particular, if the learner plays for T ∈ ℕ T\in\mathbb{N} rounds, its minimax expected number of mistakes can only grow like Θ ⁡ ( T ) \Theta(T) , Θ ⁡ ( log ⁡ T ) \Theta(\log T) , or Θ ⁡ ( 1 ) \Theta(1) . To prove this result, we give another combinatorial dimension, termed the Level-constrained Branching dimension, and show that its finiteness characterizes constant minimax expected mistake-bounds. The trichotomy is then determined by a combination of the Level-constrained Littlestone and Branching dimensions. Quantitatively, our upper bounds improve upon existing multiclass upper bounds in Hanneke et al. [2023b] by removing the dependence on the label set size. In doing so, we explicitly construct learning algorithms that can handle extremely large or unbounded label spaces. A key and novel component of our algorithm is a new notion of shattering that exploits the sequential nature of transductive online learning. Finally, we complete our results by proving expected regret bounds in the agnostic setting, extending the result of Hanneke et al. [2023b] . Keywords: Online Learning, Transductive Learning, Multiclass Classification 1 Introduction Imagine you are a famous musician who has released K\in\mathbb{N} songs. You are now on tour visiting T\in\mathbb{N} cities worldwide based on the pre-specified plan, each with unique musical preferences that you have some understanding of. At each city, you can perform only one song in your concert, and following each performance, the audience provides feedback indicating their preferred song from your repertoire. Your goal is to select the song that aligns with the majority’s taste in each city to maximize satisfaction. How can you effectively select songs to ensure the highest audience satisfaction across most cities having minimal assumptions? The above example and similar real-world situations, where entities operate according to a possibly adversarially chosen pre-specified schedule, can be formulated in a framework called Multiclass Transductive Online Learning . Formally, in this setting, an adversary plays a repeated game against the learner over some T\in\mathbbm{N} rounds. Before the game begins, the adversary selects a sequence of T instances (x_{1},\dots,x_{T})\in\mathcal{X}^{T} from some non-empty instance space \mathcal{X} (e.g. images) and reveals it to the learner. Subsequently, during each round t\in\{1,\dots,T\} , the learner predicts a label \hat{y}_{t}\in\mathcal{Y} from some non-empty label space \mathcal{Y} (e.g. categories of images), the adversary reveals the true label y_{t}\in\mathcal{Y} , and the learner suffers the 0-1 loss, namely \mathbbm{1}\{\hat{y}_{t}\neq y_{t}\} . Importantly, the label space \mathcal{Y} is not required even to be countable; we assume only standard measure theoretic properties for it. Following the well-established frameworks in learning theory, given a concept class \mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}} of functions c:\mathcal{X}\rightarrow\mathcal{Y} , the goal of the learner is to minimize the number of mistakes relative to the best-fixed concept in \mathcal{C} . If there exists c\in\mathcal{C} such that c(x_{t})=y_{t} for all t\in\{1,\dots,T\} , we say we are in the realizable setting, and otherwise in the agnostic setting. We briefly note that if the learner’s predictions are randomized, we focus on the expected value of the mentioned objective. In this paper, our main contribution is algorithmically answering the following question in the multiclass transductive online learning framework: Given a concept class \mathcal{C}\subseteq\mathcal{Y}^{\mathcal{X}} , what is the minimum expected number of mistakes achievable by a learner against any realizable adversary? For the special case of binary classification ( |\mathcal{Y}|=2 ), this question was first considered by Ben-David et al. [1997] and then later fully resolved by Hanneke et al. [2023b] . Additionally, Hanneke et al. [2023b] considered the case where |\mathcal{Y}|>2 , but did not resolve this question when \mathcal{Y} is unbounded. In fact, the bounds by Hanneke et al. [2023b] break down even when |\mathcal{Y}|\geq 2^{T} . As a result, Hanneke et al. [2023b] posed the characterization of the minimax expected number of mistakes in the multiclass setting with an infinite label set as an open question, which we resolve in this paper. 1.1 Online Learning and Multiclass Classification In this work, we study transductive online learning framework, where the adversary reveals the entire sequence of instances (x_{1},\dots,x_{T}) to the learner before the game begins. In the traditional online learning framework, the sequence of instances (x_{1},\dots,x_{T}) are revealed to the learner sequentially, one at a time. That is, on round t\in\{1,\dots,T\} , the learner would have only observed x_{1},\dots,x_{t} . The celebrated work of Littlestone [1988] introduced this framework for binary classification and quantified the best achievable number of mistakes against any realizable adversary for a concept class \mathcal{C}\subseteq\{0,1\}^{\mathcal{X}} in terms of a combinatorial parameter called the Littlestone dimension. Later, the work of Ben-David et al. [2009] showed that the Littlestone dimension of a concept class \mathcal{C}\subseteq\{0,1\}^{\mathcal{X}} continues to quantify the expected relative mistakes (i.e expected regret) for the mentioned framework in the more general agnostic setting. More recently, Daniely et al. [2012] and Hanneke et al. [2023a] extended these results to multiclass online learning in the realizable and agnostic settings, respectively. See Section A for more details. In traditional online classification, there are two sources of uncertainty: one associated with the sequence of instances, and the other with respect to the true labels. Ben-David et al. [1997] initiated the study of transductive online classification with the aim of understanding how exclusively label uncertainty impacts the optimal number of mistakes. Furthermore, removing the uncertainty with respect to the instances can significantly reduce the optimal number of mistakes. For example, for the concept class of halfspaces in the realizable setting, the optimal number of mistakes grows linearly with the time horizon T in the traditional online binary classification framework, while only growing as \Theta(\log T) in the transductive online binary classification framework. So, it is natural to reduce the optimal number of mistakes or extend learnable classes whenever we have additional assumptions. Notably, Ben-David et al. [1997] initially called this setting “offline learning”, but it was later renamed “Transductive Online Learning” by Hanneke et al. [2023b] due to its close resemblance to transductive PAC learning [ Vapnik and Chervonenkis, 1974 ; Vapnik, 1982 ; Vapnik, 1998 ] . See Section A for more details. While Ben-David et al. [1997] and Hanneke et al. [2023b] mainly focused on binary classification, in this work, we focus on the more general multiclass classification setting. Natarajan and Tadepalli [1988] ; Natarajan [1989] and Daniely et al. [2012] initiated the study of multiclass prediction within the foundational

Read the complete text