# Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2020.

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

- [Rethinking and Reweighting the Univariate Losses for Multi-Label Ranking: Consistency and Generalization](https://mlsanity.com/paper/2105.05026/) (2021)
- [Fine-grained Generalization Analysis of Vector-valued Learning](https://mlsanity.com/paper/2104.14173/) (2021)
- [Towards Understanding Generalization of Macro-AUC in Multi-label Learning](https://mlsanity.com/paper/2305.05248/) (2023)
- [Automated Multi-Label Annotation for Mental Health Illnesses Using Large Language Models](https://mlsanity.com/paper/2412.03796/) (2024)
- [Integrating Protein Sequence and Expression Level to Analysis Molecular Characterization of Breast Cancer Subtypes](https://mlsanity.com/paper/2410.01755/) (2024)
- [Automated Text Mining of Experimental Methodologies from Biomedical Literature](https://mlsanity.com/paper/2404.13779/) (2024)
- [Fairness-Aware Multi-Group Target Detection in Online Discussion](https://mlsanity.com/paper/2407.11933/) (2024)
- [On Next-Token Prediction in LLMs: How End Goals Determine the Consistency of Decoding Algorithms](https://mlsanity.com/paper/2505.11183/) (2025)
- [MoSAiC: Multi-Modal Multi-Label Supervision-Aware Contrastive Learning for Remote Sensing](https://mlsanity.com/paper/2507.08683/) (2025)
- [Private Multi-Winner Voting for Machine Learning](https://mlsanity.com/paper/2211.15410/) (2022)
- [Probabilistic Multi-Dimensional Classification](https://mlsanity.com/paper/2306.06517/) (2023)
- [A Consistent Lebesgue Measure for Multi-label Learning](https://mlsanity.com/paper/2402.00324/) (2024)
- [Multi-Label Transfer Learning in Non-Stationary Data Streams](https://mlsanity.com/paper/2509.08181/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

Various evaluation measures have been developed for multi-label classification, including Hamming Loss (HL), Subset Accuracy (SA) and Ranking Loss (RL). However, there is a gap between empirical results and the existing theories: 1) an algorithm often empirically performs well on some measure(s) while poorly on others, while a formal theoretical analysis is lacking; and 2) in small label space cases, the algorithms optimizing HL often have comparable or even better performance on the SA measure than those optimizing SA directly, while existing theoretical results show that SA and HL are conflicting measures. This paper provides an attempt to fill up this gap by analyzing the learning guarantees of the corresponding learning algorithms on both SA and HL measures. We show that when a learning algorithm optimizes HL with its surrogate loss, it enjoys an error bound for the HL measure independent of c (the number of labels), while the bound for the SA measure depends on at most O(c). On the other hand, when directly optimizing SA with its surrogate loss, it has learning guarantees that depend on O(√c) for both HL and SA measures. This explains the observation that when the label space is not large, optimizing HL with its surrogate loss can have promising performance for SA. We further show that our techniques are applicable to analyze the learning guarantees of algorithms on other measures, such as RL. Finally, the theoretical analyses are supported by experimental results.