# Local Rademacher Complexity for Multi-label Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Oct 2014.

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

- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [Generalization and Estimation Error Bounds for Model-based Neural Networks](https://mlsanity.com/paper/2304.09802/) (2023)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Multi-class Classification with Fuzzy-feature Observations: Theory and Algorithms](https://mlsanity.com/paper/2206.04311/) (2022)
- [How Label Imbalance Shapes Geometry: A General Spectral Analysis of Multi-Label Neural Collapse](https://mlsanity.com/paper/2605.01897/) (2026)

## Abstract (arXiv)

We analyze the local Rademacher complexity of empirical risk minimization (ERM)-based multi-label learning algorithms, and in doing so propose a new algorithm for multi-label learning. Rather than using the trace norm to regularize the multi-label predictor, we instead minimize the tail sum of the singular values of the predictor in multi-label learning. Benefiting from the use of the local Rademacher complexity, our algorithm, therefore, has a sharper generalization error bound and a faster convergence rate. Compared to methods that minimize over all singular values, concentrating on the tail singular values results in better recovery of the low-rank structure of the multi-label predictor, which plays an import role in exploiting label correlations. We propose a new conditional singular value thresholding algorithm to solve the resulting objective function. Empirical studies on real-world datasets validate our theoretical results and demonstrate the effectiveness of the proposed algorithm.