Selected-Risk Calibration for Feasibility at Returned Decisions
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 , 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 of random inputs covered as few as 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
| Methane | Williams–Otto | Hanoi | |||||||
|---|---|---|---|---|---|---|---|---|---|
| budget | 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 |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| benchmark | seed | no margin | conformal margin | coverage | |
|---|---|---|---|---|---|
| Methane | 3 | 106/200 | 97/200 | 0.940 | |
| 5 | 71/200 | 74/200 † | 0.889 | ||
| 6 | 104/200 | 105/200 † | 0.914 | ||
| 7 | 109/200 | 110/200 † | 0.921 | ||
| 9 | 98/200 | 99/200 † | 0.906 | ||
| Williams–Otto | 3 | 72/200 | 69/200 | 0.914 |
| random | returned | below | matched | ||
|---|---|---|---|---|---|
| configuration | inputs | decisions | 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 |
| surrogate | random inputs | at | 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 | |
| benchmark | decision variables and bounds | constraints |
|---|---|---|
| Methane reactor | methane feed and helium sweep , both in cm 3 /h; temperature K; tube diameter cm; length cm | learned: benzene outlet flow ; operating: , , , |
| Williams–Otto | reactor volume ; scaled temperature ; fresh feeds ; purge fraction | learned: product flow |
| Hanoi network | eight group diameters in; the variables are , since the published pipe cost is linear in | learned: pressure head at every junction m |
| first certification | second certification | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| benchmark | seed | anchor | cert. | 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 | – | |
| convex hull | SRC correction | |||||
|---|---|---|---|---|---|---|
| benchmark | seed | cost | violations | cost | violations | |
| 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 | ||
Surrogate-Assisted Optimization
Surrogate-assisted optimization uses learned approximations to find strong solutions when experiments or simulations are costly.
See all 127 papers