Nonconvex One-bit Single-label Multi-label Learning

We study an extreme scenario in multi-label learning where each training instance is endowed with a single one-bit label out of multiple labels. We formulate this problem as a non-trivial special case of one-bit rank-one matrix sensing and develop an efficient non-convex algorithm based on alternating power iteration. The proposed algorithm is able to recover the underlying low-rank matrix model with linear convergence. For a rank-k model with d1 features and d2 classes, the proposed algorithm achieves O(ε) recovery error after retrieving O(k1.5d1 d2/ε) one-bit labels within O(kd) memory. Our bound is nearly optimal in the order of O(1/ε). This significantly improves the state-of-the-art sampling complexity of one-bit multi-label learning. We perform experiments to verify our theory and evaluate the performance of the proposed algorithm.