Minimax semi-supervised confidence set for multi-class classification

Multiclass classification problems such as image annotation can involve a large number of classes.

In this context, confusion between classes can occur, and a single label classification may fail. In this talk, I will present a general device to build a confidence set classifier, instead of a single label classifier. 

In our framework the goal is to build the best confidence set classifier having a given expected size and the attractive feature of our approach is its semi-supervised nature - the construction of the confidence set classifier takes advantage of unlabeled data. 

Our study of the minimax rates of convergence under the combination of the margin and non parametric assumptions reveals that there is no supervised method that outperforms the semi-supervised estimator proposed in this work.

To further highlight the fundamental difference of supervised and semi-supervised methods, we establish that the best achievable rate for any supervised method is n^{-1/2}, even if the margin assumption is extremely favourable.

On the contrary, by using a sufficiently large unlabelled sample we are able to significantly improve this rate.