We deal with the settings of universal learning and partial concept classes, two fundamental questions [1]}, [2]} which are witnessed in real-life applications, nevertheless the classical theory fails to explain. Our results raise various interesting questions for future work (apart from open-question). First, it would be interesting to extend our results to the agnostic setting. Second, for the universal setting, we believe it is an important next step to shed light towards multiclass universal learning with an unbounded number of labels (whose uniform learnability was recently characterized by [3]}).
We shortly mention that the analysis of the exponential case
still holds even for a countably infinite number of labels.
Moreover, for the partial concepts setting, the work of [2]} leaves numerous fascinating open questions for the binary setting that can be asked in the multiclass setting too. In general, our work along with its seminal binary counterparts [1]}, [2]} shows that the algorithmic landscape occuring in practice is quite diverse and the ERM principle is provably insufficient. It is important to come up with principled algorithmic strategies that bring theory closer to practice.
