Example 1 (Universal Rates for Linear Multiclass Classification) 
Let us define the class of linear classifiers with \(k\)  labels in \(\mathbb {R}^d\)  as \(L = \lbrace  h_W(x) = \arg \max (W x) | W \in \mathbb {R}^{k \times d} \rbrace \) .
We first remark that the Natarajan dimension of \(L\)  is \(\widetilde{\Theta }(kd)\)  as noted for instance in [1]} and so for fixed \(k,d\) , this is a Natarajan class.
Let us discuss the complexity of learning this class in the universal setting. It is important to note that our characterization of universal multiclass learning depends only on whether the two proposed trees are infinite or not. In particular, we note that class \(L\)  has an infinite multiclass Littlestone tree and a finite Natarajan tree (since it can only shatter a finite number of points as a Natarajan class).
We also remark that if we consider the class of linear multiclass classifiers over \(\mathbb {N}^d\)  (a discrete geometric space), then this class does not even have an infinite multiclass Littlestone tree and hence is learnable at an exponentially fast rate. To see this, one can use the one-versus-one reduction and observe that any classifier \(h_W\)  corresponds to a collection of \(\binom{k}{2}\)  binary classifiers which are halfspaces in \(\mathbb {N}^d\)  where \(h_W^{i,j}(x) = \textnormal {sgn}((W_i - W_j) x)\)  for any \(i < j\) . Then, due to realizability, one can use an argument from infinite Ramsey theory (see Example 2.10 from [2]}) and prove that after a finite number of mistakes, they can detect the correct halfspace for any pair \(i<j\) . Aggregating these predictors, we get a multiclass linear classifier that enjoys an exponentially fast learning rate.

