Nonconvex One-bit Single-label Multi-label Learning
This work addresses a challenging scenario in multi-label learning for machine learning applications, offering a significant improvement in efficiency but is incremental in advancing existing matrix sensing techniques.
The paper tackles the problem of multi-label learning with single one-bit labels per instance by formulating it as a one-bit rank-one matrix sensing problem, developing a non-convex algorithm that achieves linear convergence and nearly optimal recovery error with improved sampling complexity compared to prior methods.
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 $d_1$ features and $d_2$ classes, the proposed algorithm achieves $O(ε)$ recovery error after retrieving $O(k^{1.5}d_1 d_2/ε)$ 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.