cs.LGNov 5, 2026

Selected-Risk Calibration for Feasibility at Returned Decisions

Authors: Raghav Thind, Youran Sun, Ling Liang, Haizhao Yang

Organizations: Department of Computer Science, University of Maryland, College Park · Department of Mathematics, University of Maryland, College Park · Department of Mathematics, University of Tennessee, Knoxville · Department of Mathematics, Department of Computer Science, University of Maryland, College Park

Abstract

When an optimization problem uses a surrogate constraint, a decision that is feasible for the surrogate need not be feasible for the true constraint. We propose Selected-Risk Calibration (SRC), a framework that calibrates a learned constraint against the optimizer's returned decisions for objectives drawn from a given distribution. SRC guarantees that, with probability at least 1−δ1-δ, every margin it certifies on held-out objectives has selected risk, the probability that the returned decision is infeasible, of at most γγ. We also show that the random-input coverage guarantee of split conformal prediction does not bound the selected risk, and that likelihood-ratio reweighting for feedback covariate shift does not apply when the learned constraint is active at the returned decision. Our experiments show that a conformal margin covering about 90%90\% of random inputs covered as few as 17%17\% of the returned decisions, and every certified margin had a violation rate below its target on unseen objectives. Moreover, at equal cost, SRC's correction had fewer or equal infeasible solutions to the baselines in 57 of 62 comparisons. The SRC framework applies to any setting in which a surrogate model chooses a decision whose feasibility can be verified for a sample of instances.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 31, 2026

Efficient Conformal Calibration for Paired Recommendation Decisions

Risk control can suppress useful changes to a frozen recommendation rule. We study how to recover valid activation from the same observed fractional losses. Two specified internal calibrators can lose efficiency by compressing losses into their sum or clipping auxiliary inverse counts before averaging. We propose Averaged Conformal Risk Calibration, or ACRC, which averages before clipping. A product identity proves expected-risk validity, while pointwise bounds characterize the additional activation. For fixed populations sampled without replacement, we connect activation to signed utility under heterogeneous users and switching constraints. Near the budgets, positive population mean gain and the stated nondegeneracy conditions give positive leading-order utility increments despite sampling dependence. Across six datasets, changing only calibration improves discounted net utility by 0.0102260.010226 over raw and 0.0083370.008337 over RB. A separately frozen Jester confirmation gives 0.011025±0.0010820.011025 \pm 0.001082 over raw with the rule and filter fixed, using a five-seed approximate 95 percent paired interval. Against information-matched SCoRE selecting risk or reward scores, the mean utility difference is +0.015934±0.001440+0.015934 \pm 0.001440. These gains use more mean realized risk within the declared budgets. Upstream failures delimit the benefit: efficient calibration releases useful modifications when the proposals themselves have value.
Sep 29, 2026

ReCIRC: Rectified Conformal Risk Control

Many applications of black-box predictive models require controlling task-relevant error rates, such as missed lesion pixels in segmentation or missed labels in multilabel classification. Conformal risk control (CRC; Angelopoulos et al., arXiv:2208.02814) gives distribution-free guarantees for such losses, but it calibrates a single threshold shared by all inputs. Because conditional risk varies with the input, this marginal guarantee often overprotects easy cases and underprotects hard ones. We propose ReCIRC (Rectified Conformal Risk Control), which inverts each input's estimated local risk curve to reparameterize the calibrated threshold as a risk budget aa representing a common target conditional risk, and then applies CRC unchanged to the resulting family. ReCIRC retains CRC's finite-sample marginal guarantee regardless of the accuracy of the estimated curves, while accurate curves yield approximate conditional risk control and, under additional conditions, asymptotically exact conditional risk control; they also support a risk-calibration diagnostic. Across three synthetic and five real-data settings spanning segmentation, multilabel and multiclass classification, and regression, ReCIRC attained the lowest average worst-group risk and mean positive group excess in every setting, while maintaining marginal risk close to the target, whereas changes in prediction size were application-dependent.
Jun 7, 2026

A Joint Finite-Sample Certificate for Adaptive Selective Conformal Risk Control

Selective predictors answer on confident inputs and abstain elsewhere; deploying one safely needs a single finite-sample certificate that simultaneously upper-bounds the selected risk, lower-bounds the acceptance probability \pacc\pacc above a floor \pmin\pmin, and lower-bounds the deployment utility. This certificate must be valid under adaptive threshold selection from a finite grid of mm pairs on \ncert\ncert samples. We give such a certificate for bounded, possibly non-monotone losses by treating the selected risk directly as a ratio rather than through a Hoeffding-style range bound. The construction couples three confidence bounds: a variance-adaptive empirical-Bernstein bound on the ratio risk, a Clopper--Pearson bound on acceptance, and a two-sided closeness bound on utility. Together they lower-bound the certified policy's utility absolutely and to within 2\gammau2\gammau of the best over the certified set, both non-vacuous whenever feasible; a regime-scoped third leg matches an external oracle, informative only where the risk margin \gammar<α\gammar < α and vacuous at the headline operating points. Relative to the range-only Hoeffding-ratio construction this sharpens the acceptance-floor dependence from 1/\pmin1/\pmin to 1/\pmin1/\sqrt{\pmin}, and a closed-form corollary identifies a per-pair regime in which our risk bound dominates a Hoeffding conformal risk control (Hoeffding--CRC) selective bound. Empirically, on ImageNet (three ResNets) and COCO val 2017 panoptic, the certificate opens a +22+22 pp certified-acceptance frontier over Hoeffding--CRC and is ≈10×{\approx}10{\times} tighter than a non-vacuous matched-valid baseline; these gains are regime-scoped, not universal, and absent on ADE20K. The certifier runs in O(\ncertm)O(\ncert m) time.