Nonconvex One-bit Single-label Multi-label Learning

An important topic in the multi-label learning research is how to exploit the relationship between different classes of labels in order to improve the learning accuracy or reduce the number of required labels. When labels are partially observed, the low-rank matrix model is one of the most popular models to deal with missing labels. As human-labeling is usually expensive and time-consuming, it is critical to design a robust algorithm which is able to learn the underlying low-rank matrix model on datasets with noisy heavily missing labels. In this work, we consider an extreme scenario where each training instance only has one single label being annotated in binary set 1 out of multiple classes of labels. This scenario is often encountered in realworld systems but less discussed in literatures. For example, it is rare for a user to annotate a news article or a piece of music with many tags, especially when the user is not paid for his annotation. The problem becomes challenging when we have a large number of features and classes. Over the past decades, a number of multi-label learning approaches have been proposed under different settings.