Research map / Label-efficient and robust learning / Recognition and long-tail
Consistent algorithms for multi-label classification with macro-at-$k$ metrics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a population-utility framework for macro-averaged multi-label metrics under a budget of exactly k predicted labels per instance, proves the optimal classifier form, and proposes a consistent Frank-Wolfe algorithm for it.
Problem
Optimizing complex macro-averaged multi-label metrics (e.g., macro-F1, macro-precision, macro-recall) when predictions must contain exactly k labels per instance; the budget constraint couples the per-label binary problems.
Approach
Shows the optimal budgeted classifier for a linear utility is top-k over affine transforms of label marginals, extends this to general (non-linear) confusion-tensor metrics via a compactness argument, and optimizes them with a Frank-Wolfe procedure over feasible confusion tensors that is statistically consistent.
Key results
- Frank-Wolfe classifiers achieve the best result on the target macro measure in most cases across Mediamill, Flickr, and RCV1-x at k in {3,5,10}.
- On the largest dataset (AmazonCat-13K), where most labels have fewer than 10 positives, simple power-law weighting heuristics sometimes outperform the Frank-Wolfe approach.
- The optimal macro-recall strategy recovered by the Frank-Wolfe method matches the closed-form solution in all cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Frank-Wolfe to optimize macro-at-k metrics | Multi-label classification benchmarks · Mediamill, Flickr, RCV1, and AmazonCat | target macro-at-k metric | Helped |
| Use Frank-Wolfe macro-at-k classifiers | Multi-label classification benchmarks · Mediamill, Flickr, RCV1, and AmazonCat | instance-wise measures | Mixed |
| Use Frank-Wolfe instead of simple power-law weighting | Macro-at-k classification · AmazonCat, the largest dataset | macro-at-k metric | Hurt |
| Use focal loss or asymmetric loss instead of binary cross-entropy | Multi-label classification · Reported benchmark tasks | macro measures | No clear effect |
| Use focal loss or asymmetric loss instead of binary cross-entropy | Multi-label classification · Reported benchmark tasks | instance-wise metrics | No clear effect |
| Use the Frank-Wolfe macro-recall classifier | Macro recall optimization · All reported cases | macro recall | No clear effect |
Surprising findings
- Frank-Wolfe optimization for macro measures can sacrifice instance-wise metrics such as precision@k, while improving the targeted macro metric.
- Focal and asymmetric losses preserve instance-wise performance but give only small gains on macro measures.
Limitations
- On the largest dataset with many rare labels, estimates of marginals and confusion matrices are inaccurate, so Frank-Wolfe underperforms simple heuristics.
- Consistency results rely on assumptions such as absolute continuity of label marginals and differentiable, strictly monotone metrics.
Experimental setup
Datasets: Mediamill Flickr RCV1-x AmazonCat-13K
Benchmarks: Mediamill Flickr RCV1-x AmazonCat-13K
Metrics: instance-wise precision@k instance-wise recall@k macro precision@k macro recall@k macro F1@k
Baselines: top-k BCE power-law weighted top-k log-weighted top-k focal loss asymmetric loss macro-recall optimal rule
Builds on: Frank-Wolfe algorithm multi-class consistent classification with constraints (Narasimhan et al.) Madow's sampling scheme focal loss asymmetric loss
Closest papers by meaning
- Online Metric Learning for Multi-Label Classification (AAAI 2020 · similarity 0.88)
- A General Online Algorithm for Optimizing Complex Performance Metrics (ICML 2024 · similarity 0.88)
- Generalization Analysis for Multi-Label Learning (ICML 2024 · similarity 0.86)
- Tight and Fast Bounds for Multi-Label Learning (ICML 2025 · similarity 0.85)
- Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classification (AAAI 2024 · similarity 0.85)
- Multi-Label Learning with Stronger Consistency Guarantees (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.