Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control

• URL: http://arxiv.org/abs/2302.00839v3
• Date: Tue, 25 Apr 2023 17:48:32 GMT
• Title: Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control
• Authors: Zhen Lin, Shubhendu Trivedi, Cao Xiao, Jimeng Sun
• Abstract summary: Many real-world multi-label prediction problems involve set-valued predictions that must satisfy specific requirements dictated by downstream usage. We focus on a typical scenario where such requirements, separately encoding $textitvalue$ and $textitcost$, compete with each other. We present a general pipeline, dubbed as FavMac, to maximize the value while controlling the cost in such scenarios.
• Score: 63.90454433380153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many real-world multi-label prediction problems involve set-valued predictions that must satisfy specific requirements dictated by downstream usage. We focus on a typical scenario where such requirements, separately encoding $\textit{value}$ and $\textit{cost}$, compete with each other. For instance, a hospital might expect a smart diagnosis system to capture as many severe, often co-morbid, diseases as possible (the value), while maintaining strict control over incorrect predictions (the cost). We present a general pipeline, dubbed as FavMac, to maximize the value while controlling the cost in such scenarios. FavMac can be combined with almost any multi-label classifier, affording distribution-free theoretical guarantees on cost control. Moreover, unlike prior works, it can handle real-world large-scale applications via a carefully designed online update mechanism, which is of independent interest. Our methodological and theoretical contributions are supported by experiments on several healthcare tasks and synthetic datasets - FavMac furnishes higher value compared with several variants and baselines while maintaining strict cost control. Our code is available at https://github.com/zlin7/FavMac

Related papers

• Efficient Multi-Party Secure Comparison over Different Domains with Preprocessing Assistance [10.27710213197667]
  A critical performance bottleneck in comparison protocols is their preprocessing phase.<n>Recent frameworks introduce a passive, non-colluding dealer to accelerate preprocessing.<n>We present the first dealer-assisted $n$-party LTBits (Less-Than-Bits) and MSB (Most Significant Bit) extraction protocols over both $mathbbF_p$ and $mathbbZ_2k$.
  arXiv  Detail & Related papers  (2026-02-23T08:45:47Z)
• Phase Transition for Budgeted Multi-Agent Synergy [41.486076708302456]
  Multi-agent systems can improve reliability, yet under a fixed inference budget they often help, saturate, or even collapse.<n>We develop a minimal and calibratable theory that predicts these regimes from three binding constraints of modern agent stacks.
  arXiv  Detail & Related papers  (2026-01-24T05:32:50Z)
• The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification [25.36548531839979]
  We study the problem of sequentially testing individuals for a binary disease outcome whose true risk is governed by an unknown logistic model.<n>Our goal is to minimize the total number of costly tests required while guaranteeing that the fraction of misclassifications does not exceed a prespecified error tolerance.<n>This establishes the first no-regret guarantees for error-constrained logistic testing, with direct applications to cost-sensitive medical screening.
  arXiv  Detail & Related papers  (2025-10-01T15:28:00Z)
• Backward Conformal Prediction [49.1574468325115]
  We introduce $textitBackward Conformal Prediction$, a method that guarantees conformal coverage while providing flexible control over the size of prediction sets.<n>Our approach defines a rule that constrains how prediction set sizes behave based on the observed data, and adapts the coverage level accordingly.<n>This approach is particularly useful in applications where large prediction sets are impractical such as medical diagnosis.
  arXiv  Detail & Related papers  (2025-05-19T21:08:14Z)
• Contextual Online Decision Making with Infinite-Dimensional Functional Regression [19.06054415343443]
  Contextual sequential decision-making problems play a crucial role in machine learning. We provide a universal admissible algorithm framework for dealing with all kinds of contextual online decision-making problems.
  arXiv  Detail & Related papers  (2025-01-30T14:05:20Z)
• Learning Networks from Wide-Sense Stationary Stochastic Processes [7.59499154221528]
  A key inference problem here is to learn edge connectivity from node outputs (potentials) We use a Whittle's maximum likelihood estimator (MLE) to learn the support of $Last$ from temporally correlated samples. We show that the MLE problem is strictly convex, admitting a unique solution.
  arXiv  Detail & Related papers  (2024-12-04T23:14:00Z)
• Conformal prediction for multi-dimensional time series by ellipsoidal sets [9.44133696606093]
  Conformal prediction (CP) has been a popular method for uncertainty quantification because it is distribution-free, model-agnostic, and theoretically sound. We develop a sequential CP method called $textttMultiDimS PCI$ that builds prediction $textitregions$ for a multivariate response.
  arXiv  Detail & Related papers  (2024-03-06T16:55:40Z)
• On Computationally Efficient Multi-Class Calibration [9.032290717007065]
  Project calibration gives strong guarantees for all downstream decision makers. It ensures that the probabilities predicted by summing the probabilities assigned to labels in $T$ are close to some perfectly calibrated binary predictor.
  arXiv  Detail & Related papers  (2024-02-12T17:25:23Z)
• The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation [12.197909808303411]
  We show that it is possible to produce a multicalibrated predictor for a continuous scalar distributional property $Gamma$ if and only if $Gamma$ is elicitable. On the negative side, we show that for non-elicitable continuous properties there exist simple data distributions on which even the true distributional predictor is not calibrated.
  arXiv  Detail & Related papers  (2023-02-16T18:59:16Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Measuring Model Fairness under Noisy Covariates: A Theoretical Perspective [26.704446184314506]
  We study the problem of measuring the fairness of a machine learning model under noisy information. We present a theoretical analysis that aims to characterize weaker conditions under which accurate fairness evaluation is possible.
  arXiv  Detail & Related papers  (2021-05-20T18:36:28Z)
• Hierarchically Modeling Micro and Macro Behaviors via Multi-Task Learning for Conversion Rate Prediction [14.494225676311448]
  Conversion Rate (emphCVR) prediction in modern industrial e-commerce platforms is becoming increasingly important. We propose a novel emphCVR prediction method by Hierarchically Modeling both Micro and Macro behaviors. $HM3$ can be trained end-to-end and address the emph SSB and emphDS issues.
  arXiv  Detail & Related papers  (2021-04-20T01:45:06Z)
• Masksembles for Uncertainty Estimation [60.400102501013784]
  Deep neural networks have amply demonstrated their prowess but estimating the reliability of their predictions remains challenging. Deep Ensembles are widely considered as being one of the best methods for generating uncertainty estimates but are very expensive to train and evaluate. MC-Dropout is another popular alternative, which is less expensive, but also less reliable.
  arXiv  Detail & Related papers  (2020-12-15T14:39:57Z)
• Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
  Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. Our work is based on randomized smoothing, which builds a provably robust classifier via randomizing an input. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.
  arXiv  Detail & Related papers  (2020-11-15T21:34:44Z)
• Towards Discriminability and Diversity: Batch Nuclear-norm Maximization under Label Insufficient Situations [154.51144248210338]
  Batch Nuclear-norm Maximization (BNM) is proposed to boost the learning under label insufficient learning scenarios. BNM outperforms competitors and works well with existing well-known methods.
  arXiv  Detail & Related papers  (2020-03-27T05:04:24Z)
• Ambiguity in Sequential Data: Predicting Uncertain Futures with Recurrent Models [110.82452096672182]
  We propose an extension of the Multiple Hypothesis Prediction (MHP) model to handle ambiguous predictions with sequential data. We also introduce a novel metric for ambiguous problems, which is better suited to account for uncertainties.
  arXiv  Detail & Related papers  (2020-03-10T09:15:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.