Classifying data into multiple different classes is a fundamental problem in machine learning
that has many real-life applications,
such as image recognition, web advertisement and text categorization.
Due to its importance, multiclass classification has been an attractive field of research
both for theorists [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]} and for practitioners [8]}, [9]}, [10]}. Essentially, it boils down to
learning a classifier \(h\)  from a domain \(\mathcal {X}\)  to a label
space \(\mathcal {Y}\) , where \(|\mathcal {Y}| \ge 2,\)  and the error is measured by the probability that
\(h(x)\)  is incorrect.
In this work, we focus on the setting where the number of labels
is finite and we identify \(\mathcal {Y}\)  with \( [k] := \lbrace 0,1,...,k\rbrace \)  for some
constant \(k \in \mathbb {N}\) .
