Skip to Main content Skip to Navigation
Journal articles

Minimax semi-supervised set-valued approach to multi-class classification

Abstract : We study supervised and semi-supervised algorithms in the set-valued classification framework with controlled expected size. While the former methods can use only n labeled samples, the latter are able to make use of N additional unlabeled data. We obtain semi-supervised minimax rates of convergence under the α-margin assumption and a β-Hölder condition on the conditional distribution of labels. Our analysis implies that if no further assumption is made, there is no supervised method that outperforms the semi-supervised estimator proposed in this work – the best achievable rate for any supervised method is O(n−1/2), even if the margin assumption is extremely favorable; on the contrary, the developed semi-supervised estimator can achieve faster O((n/logn)−(1+α)β/(2β+d)) rate of convergence provided that sufficiently many unlabeled samples are available. We also show that under additional smoothness assumption, supervised methods are able to achieve faster rates and the unlabeled sample cannot improve the rate of convergence. Finally, a numerical study supports our theory and emphasizes the relevance of the assumptions we required from an empirical perspective.
Complete list of metadata
Contributor : Evgenii Chzhen Connect in order to contact the contributor
Submitted on : Saturday, April 27, 2019 - 11:53:45 AM
Last modification on : Friday, July 8, 2022 - 10:09:23 AM


Files produced by the author(s)



Evgenii Chzhen, Christophe Denis, Mohamed Hebiri. Minimax semi-supervised set-valued approach to multi-class classification. Bernoulli, Bernoulli Society for Mathematical Statistics and Probability, 2021, ⟨10.3150/20-BEJ1313⟩. ⟨hal-02112918⟩



Record views


Files downloads