Convergence analysis for complementary-label learning with kernel ridge regression

Complementary-label learning (CLL) aims at finding a classifier via samples with complementary labels. Such data is considered to contain less information than ordinary-label samples. The transition matrix between the true label and the complementary label, and some loss functions have been developed to handle this problem. In this paper, we show that CLL can be transformed into ordinary classification under some mild conditions, which indicates that the complementary labels can supply enough information in most cases. As an example, an extensive misclassification error analysis was performed for the Kernel Ridge Regression (KRR) method applied to multiple complementary-label learning (MCLL), which demonstrates its superior performance compared to existing approaches.