# Nonconvex One-bit Single-label Multi-label Learning

arXiv: https://arxiv.org/abs/1703.06104 · HTML: https://mlsanity.com/paper/1703.06104/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2017.

## Built on by (most cited first, 2 of 2)

- [Multi-Label Learning from Single Positive Labels](https://mlsanity.com/paper/2106.09708/) (2021)
- [Spatial Consistency Loss for Training Multi-Label Classifiers from Single-Label Annotations](https://mlsanity.com/paper/2203.06127/) (2022)

## Abstract (arXiv)

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.