It is clear that the above result implies theorem:tri-main.
We remark that not only the achievable rates are different compared to the uniform setting, but also the algorithms we use
to get these rates differ vastly from ERM.
We sketch the main techniques in section:tri-sketch. For the formal proof, see section:tri-proof.
We briefly summarize our main
technical contributions in this setting: using the pre-described complexity
measures of \(\mathcal {H}\) , we introduce novel Gale-Stewart games (see section:notation and preliminaries for a definition) which lead to new learning algorithms
that achieve the optimal learning rates. Also, we extend the lower
bounds from [1]} that hold for binary classification
to the multiclass setting using our combinatorial measures. Our constructions raise interesting questions about how
the equivalence between various combinatorial dimensions, like the Graph
dimension and the Natarajan dimension, which is established in the PAC
setting translates to the universal setting. For further details, we refer to section:overview and section:gl-trees.
