  Complementary-label Learning (CLL) is a form of weakly supervised learning
that trains an ordinary classifier using only complementary labels, which are
the classes that certain instances do not belong to. While existing CLL studies
typically use novel loss functions or training techniques to solve this
problem, few studies focus on how complementary labels collectively provide
information to train the ordinary classifier. In this paper, we fill the gap by
analyzing the implicit sharing of complementary labels on nearby instances
during training. Our analysis reveals that the efficiency of implicit label
sharing is closely related to the performance of existing CLL models. Based on
this analysis, we propose a novel technique that enhances the sharing
efficiency via complementary-label augmentation, which explicitly propagates
additional complementary labels to each instance. We carefully design the
augmentation process to enrich the data with new and accurate complementary
labels, which provide CLL models with fresh and valuable information to enhance
the sharing efficiency. We then verify our proposed technique by conducting
thorough experiments on both synthetic and real-world datasets. Our results
confirm that complementary-label augmentation can systematically improve
empirical performance over state-of-the-art CLL models.
