Research map / Learning theory and algorithms / Prediction and decision losses
Cardinality-Aware Set Prediction and Top-$k$ Classification
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.
Introduces cardinality-aware top-k set prediction with a cost-sensitive target loss, proposes cost-sensitive comp-sum and constrained surrogates with H-consistency bounds, and tests them on CIFAR-10/100, SVHN, and ImageNet.
Problem
Learning accurate top-k set predictors whose cardinality adapts per input while keeping average set size low, which is an instance-dependent cost-sensitive problem that is intractable to optimize directly.
Approach
Define a target loss combining top-k classification error with a log/linear cardinality cost, then optimize cost-sensitive extensions of comp-sum and constrained surrogate losses, and prove H-consistency bounds for both the fixed-k top-k setting and the cardinality-aware setting.
Key results
- On CIFAR-100, CIFAR-10 and SVHN the cardinality-aware algorithm matches the 98% accuracy of top-k classifiers with roughly half the cardinality.
- On ImageNet it reaches the same 95% accuracy as top-k classifiers with about two-thirds of the cardinality.
- The cardinality-aware algorithm achieves higher accuracy than top-k classifiers at every cardinality tested.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cardinality-aware selection instead of a fixed top-k classifier | Top-k prediction · CIFAR-100, CIFAR-10, and SVHN | cardinality at the same accuracy: roughly only half of the cardinality | Helped |
| Use cardinality-aware selection instead of a fixed top-k classifier | Top-k prediction · ImageNet | cardinality at the same accuracy: only two-thirds of the cardinality | Helped |
| Decrease the trade-off parameter λ | Cardinality-aware algorithm · CIFAR-10, CIFAR-100, ImageNet, and SVHN | accuracy | Helped |
| Use linear cardinality cost k instead of logarithmic cost log(k) (ablation) | Cardinality-aware algorithm · CIFAR-10, CIFAR-100, ImageNet, and SVHN | accuracy versus cardinality | No clear effect |
Surprising findings
- The choice between linear and logarithmic cardinality costs has negligible impact on performance.
Limitations
- Threshold-based instantiation only evaluated in early experiments in the appendix
- Theoretical bounds for mean absolute error and generalized cross-entropy scale with the number of classes or set predictors
- Logistic-type comp-sum losses are not realizable H-consistent for top-k when k>1 per the paper's discussion
Experimental setup
Datasets: CIFAR-10 CIFAR-100 SVHN ImageNet
Benchmarks: CIFAR-10 CIFAR-100 SVHN ImageNet
Metrics: top-k accuracy average cardinality
Baselines: top-k classifiers conformal prediction
Builds on: comp-sum losses constrained losses H-consistency bounds conformal prediction
Closest papers by meaning
- On the consistency of top-k surrogate losses (ICML 2020 · similarity 0.86)
- Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction (ICML 2026 · similarity 0.85)
- Top-k Hierarchical Classification (AAAI 2017 · similarity 0.84)
- Consistent Polyhedral Surrogates for Top-k Classification and Variants (ICML 2022 · similarity 0.84)
- Loss Functions for Top-k Error: Analysis and Insights (CVPR 2016 · similarity 0.84)
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 2024 · similarity 0.84)
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.