# Consistent algorithms for multi-label classification with macro-at-k metrics

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 65 references that are in the map.
- First posted on arXiv 29 Jan 2024.

## Builds on (most cited first, 21 of 21)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Asymmetric Loss For Multi-Label Classification](https://mlsanity.com/paper/2009.14119/) (2020)
- [Inferring Networks of Substitutable and Complementary Products](https://mlsanity.com/paper/1506.08839/) (2015)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Macro F1 and Macro F1](https://mlsanity.com/paper/1911.03347/) (2019)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [Extreme Multi-label Learning for Semantic Matching in Product Search](https://mlsanity.com/paper/2106.12657/) (2021)
- [On the Bayes-optimality of F-measure maximizers](https://mlsanity.com/paper/1310.4849/) (2013)
- [On Missing Labels, Long-tails and Propensities in Extreme Multi-label Classification](https://mlsanity.com/paper/2207.13186/) (2022)
- [Surrogate regret bounds for generalized classification performance metrics](https://mlsanity.com/paper/1504.07272/) (2015)
- [Probabilistic Label Trees for Extreme Multi-label Classification](https://mlsanity.com/paper/2009.11218/) (2020)
- [Consistent Multiclass Algorithms for Complex Metrics and Constraints](https://mlsanity.com/paper/2210.09695/) (2022)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Surrogate Functions for Maximizing Precision at the Top](https://mlsanity.com/paper/1505.06813/) (2015)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Consistent Classification with Generalized Metrics](https://mlsanity.com/paper/1908.09057/) (2019)

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

- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [From Lazy to Prolific: Tackling Missing Labels in Open Vocabulary Extreme Classification by Positive-Unlabeled Sequence Learning](https://mlsanity.com/paper/2408.08981/) (2024)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

We consider the optimization of complex performance metrics in multi-label classification under the population utility framework. We mainly focus on metrics linearly decomposable into a sum of binary classification utilities applied separately to each label with an additional requirement of exactly k labels predicted for each instance. These "macro-at-k" metrics possess desired properties for extreme classification problems with long tail labels. Unfortunately, the at-k constraint couples the otherwise independent binary classification tasks, leading to a much more challenging optimization problem than standard macro-averages. We provide a statistical framework to study this problem, prove the existence and the form of the optimal classifier, and propose a statistically consistent and practical learning algorithm based on the Frank-Wolfe method. Interestingly, our main results concern even more general metrics being non-linear functions of label-wise confusion matrices. Empirical results provide evidence for the competitive performance of the proposed approach.