Reduced Cost Influence Functions for Predict-then-Optimize under Noisy Data
Organizations: Operations Research Center Massachusetts Institute of Technology Cambridge, MA 02139
Abstract
Machine learning models deployed in decision-making pipelines, from vehicle routing to dynamic pricing to clinical decision support, must remain reliable in the face of low-quality training data. We study a predict-then-optimize setting in which an upstream model predicts the cost vector of a downstream linear program, with a large pool of noisy training data supplemented by a small curated set of clean data. We introduce Reduced Cost Influence Functions (RCIFs), which combine influence functions from robust statistics with the geometry of linear optimization to estimate how each training point shifts downstream decisions. Building on this, we propose a reweighting algorithm that uses RCIFs to downweight harmful training points and reduce downstream regret. Experiments on random linear programs and shortest-path problems show that our approach reduces regret, and accompanying theory characterizes properties of RCIFs and identifies regimes favorable to our method relative to baselines.
Figures & tables
| Method | Random LP | Shortest Path | NN Upstream |
|---|---|---|---|
| Iterative Exp. Directed | 0.3451 0.0133 | 0.9437 0.0172 | 1.4511 0.0187 |
| Exp. Two-Sided | 0.3535 0.0129 | 1.0009 0.0175 | 1.4211 0.0196 |
| Directed | 0.3531 0.0129 | 0.9825 0.0171 | 1.3958 0.0217 |
| Unweighted | 0.3564 0.0130 | 1.0029 0.0169 | 1.4317 0.0198 |
| RC Weight | 0.3549 0.0131 | 1.0035 0.0169 | 1.4255 0.0227 |
| Validation Only | 0.4184 0.0191 | 0.9989 0.0181 | 1.4208 0.0228 |
| Method | deg = 1 | deg = 2 | deg = 4 |
|---|---|---|---|
| Iterative Exp. Directed | 0.9437 0.0172 | 0.4856 0.0135 | 0.2899 0.0115 |
| Exp. Two-Sided | 1.0009 0.0175 | 0.5682 0.0152 | 0.3393 0.0127 |
| Directed | 0.9825 0.0171 | 0.5347 0.0132 | 0.3208 0.0122 |
| Unweighted | 1.0029 0.0169 | 0.5715 0.0145 | 0.3483 0.0135 |
| RC Weight | 1.0035 0.0169 | 0.5713 0.0145 | 0.3496 0.0138 |
| Validation Only | 0.9989 0.0181 | 0.5284 0.0146 | 0.3782 0.0147 |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | ||||
|---|---|---|---|---|
| Iterative Exp. Directed | 0.9089 0.0172 | 0.9437 0.0172 | 0.9992 0.0211 | 1.0275 0.0160 |
| Exp. Two-Sided | 0.9528 0.0172 | 1.0009 0.0175 | 1.0580 0.0191 | 1.0817 0.0208 |
| Directed | 0.9357 0.0170 | 0.9825 0.0171 | 1.0433 0.0189 | 1.0568 0.0187 |
| Unweighted | 0.9573 0.0170 | 1.0029 0.0169 | 1.0610 0.0194 | 1.0784 0.0208 |
| RC Weight | 0.9575 0.0171 | 1.0035 0.0169 | 1.0604 0.0192 | 1.0780 0.0210 |
| Validation Only | 0.9989 0.0181 | 0.9989 0.0181 | 0.9989 0.0181 | 0.9989 0.0181 |
| Method | |V| = 5 | |V| = 10 | |V| = 20 | |V| = 50 | |V| = 100 | |V| = 150 | |V| = 200 |
|---|---|---|---|---|---|---|---|
| Iterative Exp. Directed | 1.0595 0.0140 | 1.0051 0.0127 | 0.9707 0.0123 | 0.9354 0.0120 | 0.9088 0.0107 | 0.8751 0.0107 | 0.8688 0.0111 |
| Exp. Two-Sided | 1.0050 0.0109 | 0.9935 0.0116 | 0.9789 0.0125 | 0.9586 0.0135 | 0.9458 0.0118 | 0.9228 0.0117 | 0.9127 0.0124 |
| Directed | 1.0015 0.0129 | 0.9756 0.0111 | 0.9659 0.0115 | 0.9520 0.0124 | 0.9389 0.0117 | 0.9071 0.0116 | 0.8964 0.0121 |
| Unweighted | 0.9857 0.0119 | 0.9736 0.0113 | 0.9714 0.0119 | 0.9627 0.0125 | 0.9516 0.0122 | 0.9282 0.0121 | 0.9184 0.0124 |
| RC Weight | 0.9855 0.0120 | 0.9732 0.0112 | 0.9713 0.0117 | 0.9634 0.0126 | 0.9515 0.0122 | 0.9280 0.0120 | 0.9179 0.0124 |
| Validation Only | 1.1854 0.0137 | 1.1710 0.0145 | 1.2471 0.0155 | 1.0366 0.0142 | 0.9563 0.0105 | 0.8940 0.0115 | 0.8871 0.0107 |
| Method | |V| = 5 | |V| = 10 | |V| = 20 | |V| = 50 | |V| = 100 | |V| = 150 |
|---|---|---|---|---|---|---|
| Iterative Exp. Directed | 1.0964 0.0146 | 1.0600 0.0132 | 1.0254 0.0126 | 0.9745 0.0117 | 0.9334 0.0107 | 0.9120 0.0121 |
| Unweighted | 1.0234 0.0133 | 1.0159 0.0113 | 1.0137 0.0116 | 0.9995 0.0122 | 0.9873 0.0114 | 0.9719 0.0120 |
| Validation Only | 1.1854 0.0137 | 1.1710 0.0145 | 1.2471 0.0155 | 1.0366 0.0142 | 0.9563 0.0105 | 0.8940 0.0115 |
| Method | = 0.1 | = 0.2 | = 0.3 | = 0.5 |
|---|---|---|---|---|
| Iterative Exp. Directed | 0.3746 0.0176 | 0.3865 0.0180 | 0.3978 0.0195 | 0.4230 0.0181 |
| Exp. Two-Sided | 0.3774 0.0181 | 0.3893 0.0182 | 0.4037 0.0185 | 0.4331 0.0180 |
| Directed | 0.3771 0.0182 | 0.3896 0.0180 | 0.4010 0.0187 | 0.4341 0.0184 |
| Unweighted | 0.3764 0.0181 | 0.3896 0.0186 | 0.4053 0.0183 | 0.4333 0.0179 |
| RC Weight | 0.3772 0.0186 | 0.3906 0.0190 | 0.4046 0.0184 | 0.4333 0.0178 |
| Validation Only | 0.4173 0.0197 | 0.4173 0.0197 | 0.4173 0.0197 | 0.4173 0.0197 |
| Method | |V| = 5 | |V| = 10 | |V| = 20 | |V| = 50 | |V| = 100 | |V| = 150 |
|---|---|---|---|---|---|---|
| Iterative Exp. Directed | 0.6033 0.0331 | 0.5311 0.0258 | 0.4640 0.0221 | 0.4230 0.0181 | 0.3693 0.0185 | 0.3632 0.0160 |
| Exp. Two-Sided | 0.4774 0.0255 | 0.4704 0.0225 | 0.4491 0.0209 | 0.4331 0.0180 | 0.3848 0.0183 | 0.3758 0.0164 |
| Directed | 0.4766 0.0251 | 0.4667 0.0227 | 0.4498 0.0207 | 0.4341 0.0184 | 0.3835 0.0183 | 0.3737 0.0165 |
| Unweighted | 0.4576 0.0232 | 0.4618 0.0219 | 0.4503 0.0203 | 0.4333 0.0179 | 0.3830 0.0183 | 0.3752 0.0165 |
| RC Weight | 0.4596 0.0236 | 0.4609 0.0218 | 0.4501 0.0208 | 0.4333 0.0178 | 0.3838 0.0184 | 0.3750 0.0168 |
| Validation Only | 9.8179 0.4086 | 7.9994 1.3074 | 0.6616 0.0284 | 0.4173 0.0197 | 0.3570 0.0190 | 0.3602 0.0159 |
| Method | Random LP | Shortest Path |
|---|---|---|
| Iterative Exp. Directed | 0.3527 0.0158 | 1.2412 0.0204 |
| Exp. Two-Sided | 0.3514 0.0155 | 1.2430 0.0196 |
| Directed | 0.3514 0.0155 | 1.2424 0.0195 |
| Unweighted | 0.3522 0.0156 | 1.2412 0.0194 |
| RC Weight | 0.3519 0.0155 | 1.2410 0.0194 |
| Validation Only | 0.4173 0.0197 | 1.4459 0.0177 |
| Method | LP, Gauss. = 0.3 | Shortest, Gauss. = 0.2 | Shortest, Directional = 0.4 |
|---|---|---|---|
| Iterative Exp. Directed | 0.3451 0.0133 | 0.9085 0.0164 | 0.8509 0.0164 |
| Directed | 0.3531 0.0129 | 0.9459 0.0168 | 0.8547 0.0161 |
| Unweighted | 0.3564 0.0130 | 0.9600 0.0158 | 0.8591 0.0164 |
| Clean ERM (oracle) | 0.2785 0.0109 | 0.8257 0.0152 | 0.8257 0.0152 |
| Huber | 0.2952 0.0108 | 0.9266 0.0163 | 0.8730 0.0156 |
| Trimmed ERM | 0.2865 0.0118 | 0.8544 0.0141 | 0.8977 0.0158 |
Predict-Then-Optimize
Predict-then-optimize trains or evaluates predictors by how well their outputs support downstream decisions under constraints.
See all 43 papers