# A Convex Loss Function for Set Prediction with Optimal Trade-offs Between Size and Conditional Coverage

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 22 Dec 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Classifier Calibration with ROC-Regularized Isotonic Regression](https://mlsanity.com/paper/2311.12436/) (2023)
- [Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise](https://mlsanity.com/paper/2406.03258/) (2024)
- [Notes on the H-measure of classifier performance](https://mlsanity.com/paper/2106.11888/) (2021)
- [On the relationship between multivariate splines and infinitely-wide neural networks](https://mlsanity.com/paper/2302.03459/) (2023)

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

- [On the Burden of Achieving Fairness in Conformal Prediction](https://mlsanity.com/paper/2605.14260/) (2026)
- [Super-Level-Set Regression: Conditional Quantiles via Volume Minimization](https://mlsanity.com/paper/2605.06210/) (2026)

## Abstract (arXiv)

We consider supervised learning problems in which set predictions provide explicit uncertainty estimates. Using Choquet integrals (a.k.a. Lov'asz extensions), we propose a convex loss function for nondecreasing subset-valued functions obtained as level sets of a real-valued function. This loss function allows optimal trade-offs between conditional probabilistic coverage and the ''size'' of the set, measured by a non-decreasing submodular function. We also propose several extensions that mimic loss functions and criteria for binary classification with asymmetric losses, and show how to naturally obtain sets with optimized conditional coverage. We derive efficient optimization algorithms, either based on stochastic gradient descent or reweighted least-squares formulations, and illustrate our findings with a series of experiments on synthetic datasets for classification and regression tasks, showing improvements over approaches that aim for marginal coverage.