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
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−δ, 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% of random inputs covered as few as 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
Figure 1: The construction behind Theorem 1 , drawn with q^=0.8 . The shaded triangle is the true feasible region {h≤0} , and the horizontal line h^+q^=0 is the upper edge of the deployed set {h^+q^≤0} . The vertical line u=q^ separates the points where the conformally padded surrogate bounds h from those where it does not; the strip to its right has probability 1−q^ under P . Every objective drives the solver onto the horizontal line, and the sign of β decides which end. Objectives with β<0 all land in the uncovered strip.
Figure 2: Coverage of a split-conformal margin at level 0.90 , five repetitions per configuration. (a) Large markers are means and small markers represent each single run ( † : see Appendix D ). (b) Coverage at the returned decision as the penalty driving the optimizer away from the boundary grows with λ .
Figure 3: Certification bound Uˉ against the violation rate on fresh objectives, for the 30 margins with a fresh evaluation. Dashed lines mark γ=0.12 and the dotted line is Uˉ equal to the fresh rate. No certified margin (circle) lies above γ , but every rejected margin (cross) does.
Methane
Williams–Otto
Hanoi
budget /C⋆
0.25
0.55
1.0
0.25
0.55
1.0
0.25
0.55
1.0
SRC correction ∗
0.42
0.27
0.07
0.18
0.08
0.08
0.35
0.20
0.10
C-MICL [ 12 ]
0.48
0.42
0.33
0.36
0.33
0.34
0.42
0.43
0.44
C-MICL refit ‡
0.49
0.31
0.12
0.36
0.35
0.23
0.43
0.42
0.43
W-MICL [ 12 ]
0.47
0.35
0.27
0.34
0.25
0.20
0.43
0.22
0.07
Locally weighted [ 30 ]
0.52
0.47
0.38
0.31
0.23
0.21
0.35
0.20
0.08
Table 1: Violation rates at matched cost (lower is better). Each rate is averaged over the seeds on which the method could be compared with SRC’s correction; rates in italics use fewer than five seeds. Bold marks the lowest rate in each column. Budgets are fractions of C-MICL’s own cost C⋆ . ‡ Our controls.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
benchmark
seed
q^
no margin
conformal margin
coverage
Methane
3
+0.374
106/200
97/200
0.940
5
−0.083
71/200
74/200 †
0.889
6
+0.071
104/200
105/200 †
0.914
7
+0.175
109/200
110/200 †
0.921
9
+0.340
98/200
99/200 †
0.906
Williams–Otto
3
+0.008
72/200
69/200
0.914
Appendix
Table 2: The surrogate deployed without a margin ( h^≤0 ) and with the conformal margin ( h^+q^≤0 ): violations among 200 objectives per seed, and the margin’s coverage of 800 random held-out inputs. † Runs where the margin gives more violations than no margin.
random
returned
below
matched
configuration
inputs
decisions
0.90
boundary
drop
Methane / symbolic / scalar
0.910
0.53–0.71
5 of 5
0.875–0.920
0.205–0.353
Methane / MLP / scalar
0.955–0.990
0.19–0.60
5 of 5
0.855–0.990
0.325–0.703
Methane / MLP / normalized
0.955–0.990
0.17–0.46
5 of 5
0.790–0.933
0.330–0.703
Methane / symbolic / normalized
0.980–0.990
0.80–1.00
1 of 5
0.987–1.000 (2 of 5)
0.000–0.187
Williams–Otto / symbolic / scalar
0.895
0.74–0.78
5 of 5
0.993–1.000
0.220–0.255
Appendix
Table 3: The coverage diagnostic, summarized over the five repetitions of each configuration. Where matched-boundary points were found in fewer than five repetitions, the number is given in brackets.
surrogate
α
random inputs
at x⋆
gap
mean objective
min
max
min
max
min
max
min
max
symbolic
0.20
0.740
0.740
0.500
0.680
+0.120
+0.300
22.789
32.398
0.15
0.835
0.835
0.530
0.700
+0.150
+0.320
23.043
32.656
0.10
0.910
0.910
0.530
0.710
+0.190
+0.370
23.355
32.971
0.05
0.955
0.955
0.580
0.780
+0.170
+0.370
23.716
33.335
0.02
0.965
0.965
0.630
0.800
+0.180
+0.350
24.292
33.915
Appendix
Table 4: The α sweep on methane over five repetitions, reported as the minimum and maximum across them. The gap is (1−α) minus coverage at x⋆ , so a positive gap is coverage promised but not delivered, and the mean objective is minimised, so a larger value is worse.
benchmark
decision variables and bounds
constraints
Methane reactor
methane feed v0 and helium sweep vHe , both in [450,1500] cm 3 /h; temperature T∈[997.18,1348.12] K; tube diameter d∈[0.5,2] cm; length L∈[10,100] cm
eight group diameters Dg∈[12,40] in; the variables are xg=Dg1.5∈[41.57,252.98] , since the published pipe cost is linear in D1.5
learned: pressure head at every junction ≥30 m
Appendix
Table 5: Benchmarks. Each learned constraint is written as h(x)≤0 .
first certification
second certification
benchmark
seed
anchor
θ
v/300
Uˉ
cert.
v/300
Uˉ
cert.
fresh
Methane
3
0.25
0.00
53/300
0.252
no
54/300
0.255
no
39/200
3
0.50
0.00
7/300
0.063
yes
4/300
0.047
yes
4/200
3
0.75
0.25
7/300
0.063
yes
4/300
0.047
yes
3/200
4
0.25
0.00
15/300
0.100
yes
15/300
0.100
yes
–
4
0.50
0.00
9/300
0.073
yes
13/300
0.091
yes
–
Appendix
Table 6: All 40 margins of the certification study. Each margin is certified twice, on two independent sets of 300 objectives; “cert.” says whether Uˉ≤γ=0.12 at level δ/K with K=40 , which holds exactly when v≤19 . The last column counts violations on fresh objectives.
convex hull
SRC correction
benchmark
seed
cost
violations
cost
violations
p
Methane
3
0.0508
17/200
0.0189
43/200
1.6e-04
0.0550
16/200
0.0189
43/200
6.6e-05
0.0597
9/200
0.0189
43/200
3.1e-07
5
0.0421
37/200
0.0379
0/200
1.5e-11
0.0468
34/200
0.0379
0/200
1.2e-10
Appendix
Table 7: The convex-hull trust region of OptiCL against SRC’s correction. For each of the hull’s three settings per seed, SRC’s correction is taken at its most expensive setting that costs no more than the hull. The p -value is from an exact McNemar test on the 200 shared objectives.
School of Cyber Security and Information Law Chongqing University of Posts and Telecommunications Chongqing 400065, China · Department of Information, Xinqiao Hospital Army Medical University (Third Military Medical University) Chongqing 400037, China