Abstract

In the Superset Label Learning (SLL) problem, weak supervision is provided in the form of a superset of labels that contains the true label. If the classifier predicts a label outside of the superset, it commits a superset error. Most existing SLL algorithms learn a multiclass classifier by minimizing the superset error. However, only limited theoretical analysis has been dedicated to this approach. In this paper, we analyze Empirical Risk Minimizing learners that use the superset error as the empirical risk measure. SLL data can arise either in the form of independent instances or as multiple-instance bags. For both scenarios, we give the conditions for ERM learnability and sample complexity for the realizable case.