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

CardsList
  1. Efficient Conformal Calibration for Paired Recommendation Decisions

    Oct 31, 2026Xinyu Qiao, Yichen Lin, Zhewen Chen +2Conformal Risk ControlPost-Hoc Calibration

  2. ReCIRC: Rectified Conformal Risk Control

    Sep 29, 2026Bruno Marcondes e Resende, Helton Graziadei, Thiago Rodrigo Ramos +1Conformal PredictionConformal Risk Control

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

    Jun 7, 2026Xiaoli Yu, Jiamiao LiuSelective PredictionConformal Risk Control