Research map / Learning theory and algorithms / Prediction and decision losses
Conformal Inverse Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes conformal inverse optimization, which calibrates a conformal uncertainty set over parameter directions from decision data and solves a robust forward problem to prescribe decisions with bounded actual and perceived optimality gaps.
Problem
Classic inverse optimization returns a point estimate of unknown parameters, and the prescribed decisions can have arbitrarily large actual and perceived optimality gaps, reducing adoption.
Approach
Learn a conformal uncertainty set (a spherical cap around a point estimate, with calibrated angle) from decision data using a calibration problem with coverage guarantees, then solve a robust forward optimization over that set to prescribe decisions.
Key results
- On shortest path, conformal IO improves AOG by 20.1-30.4% and POG by 15.0-23.2% over classic IO across target confidence levels.
- On knapsack, conformal IO improves AOG by 40.3-57.0% and POG by 13.5-20.1% over classic IO.
- In the illustrative example, classic IO has AOG growing linearly with u (e.g., 35 at u=100) while conformal IO achieves AOG 0.00 at all u.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use calibrated uncertainty sets with robust forward optimization instead of prescribing from point estimates | Shortest Path · Synthetic shortest path | AOG: 20.1--30.4% | Helped |
| Use calibrated uncertainty sets with robust forward optimization instead of prescribing from point estimates | Shortest Path · Synthetic shortest path | POG: 15.0--23.2% | Helped |
| Use calibrated uncertainty sets with robust forward optimization instead of prescribing from point estimates | Knapsack · Synthetic knapsack | AOG: 40.3--57.0% | Helped |
| Use calibrated uncertainty sets with robust forward optimization instead of prescribing from point estimates | Knapsack · Synthetic knapsack | POG: 13.5--20.1% | Helped |
| Replace point-estimate FO prediction with calibrated-set RFO prediction | Shortest Path · Synthetic shortest path | prediction time per decision: 0.01 (0.00) -> 0.63 (0.12) | Hurt |
| Replace point-estimate FO prediction with calibrated-set RFO prediction | Knapsack · Synthetic knapsack | prediction time per decision: 0.01 (0.00) -> 0.44 (0.15) | Hurt |
| Use a larger validation set for uncertainty-set calibration (ablation) | Conformal IO · Synthetic shortest path and knapsack | coverage calibration | Helped |
| Increase confidence level gamma from 0 toward 50% (ablation) | Conformal IO · Synthetic shortest path and knapsack | AOG and POG: 50% | Helped |
| Increase confidence level gamma beyond 50% (ablation) | Conformal IO · Synthetic shortest path and knapsack | AOG and POG: 50% | Mixed |
| Use Conformal IO with a small dataset (160 total training and validation examples) (ablation) | Conformal IO · Synthetic shortest path | AOG and POG: 160 | No clear effect |
Surprising findings
- Classic IO with the sub-optimality loss can yield arbitrarily large AOG and POG even with asymptotically correct parameter estimates, and distributionally robust IO does not fix this.
- With small datasets (N=160), conformal IO offers no benefit over classic IO because data are split between estimation and calibration.
Limitations
- Focuses on objective functions linear in the unknown parameters.
- Robust forward problem is computationally more expensive than the original forward problem (about 0.4-0.6 s per decision).
- Requires feasibility of the calibration problem; observed decisions must be optimal for some parameter in the bounded set.
Experimental setup
Datasets: synthetic shortest path instances synthetic knapsack instances
Benchmarks: synthetic shortest path synthetic knapsack
Metrics: actual optimality gap (AOG) perceived optimality gap (POG) empirical coverage computation time
Baselines: classic inverse optimization (sub-optimality loss) PFYL
Builds on: inverse optimization with sub-optimality loss predict-then-optimize / PFYL conformal prediction distributionally robust inverse optimization
Closest papers by meaning
- Learning Polyhedral Conformal Sets for Robust Optimization (NeurIPS 2026 · similarity 0.88)
- ROOT: Rethinking Offline Optimization as Distributional Translation via Probabilistic Bridge (NeurIPS 2025 · similarity 0.86)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.86)
- Tight Generalization Bounds for Noiseless Inverse Optimization (NeurIPS 2026 · similarity 0.86)
- Adaptive Conformal Inference by Betting (ICML 2024 · similarity 0.85)
- Inverse Optimization via Learning Feasible Regions (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.