Research map / Optimization / Optimizers
From Inverse Optimization to Feasibility to ERM
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.
Reduces contextual inverse linear programming (CILP) to convex feasibility solved by alternating projections, then to ERM on a smooth convex PL loss, giving linear convergence and generalization guarantees, validated on Warcraft shortest path and perfect matching.
Problem
Contextual inverse linear programming: learn a model mapping context to LP cost vectors so that the LP's optimal decisions match observed optimal decisions; standard autodiff fails because LP solutions are piecewise constant in the costs.
Approach
Uses KKT optimality conditions to define the convex set of cost vectors consistent with each observed decision, reduces CILP to convex feasibility (alternating projections for linear models), and then to minimizing a smooth, convex, PL squared-distance loss so that first-order methods (SGD/AdaGrad/Adam) and stability-based generalization bounds apply.
Key results
- On Warcraft SP and PM, the proposed method consistently achieves lower decision loss than ST, BB, MOM and SPO+ across tasks (reported qualitatively in the main text).
- In estimate loss, the method outperforms all baselines except SPO+ on shortest path, and is comparable to SPO+ on the other tasks, while SPO+ uses ground-truth costs.
- Theory: linear convergence of alternating projections/GD to a point in the intersection C∩F, and h(theta) is 1-smooth, convex and PL with mu = lambda_min of the normalized feature covariance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use margin chi=1 in KKT-based constraint set (vs. no margin) | CILP reduction (linear model) · Warcraft Shortest Path / Perfect Matching | decision-loss | No clear effect |
| Replace SGD-style ERM training on KKT-based loss with the proposed method (vs. ST, BB, MOM, SPO+ baselines) | Warcraft Shortest Path · decision-loss, train and test | decision-loss | Helped |
| Proposed method compared to baselines on estimate-loss | Warcraft Shortest Path · estimate-loss | estimate-loss | Mixed |
| Proposed method uses only KKT/ERM with no access to ground-truth cost c* (vs. SPO+ which uses c*) | estimate-loss comparison · Warcraft Shortest Path / Perfect Matching | estimate-loss | Mixed |
| Use ERM loss with PL-based linear convergence vs. SGD on general smooth convex loss (theory) | CILP reduction · theory | convergence rate | Helped |
| Use the proposed sub-optimality gap instead of Gamma_1 (theory) | sub-optimality metric · theory | sub-optimality | No clear effect |
Surprising findings
- The paper notes that MOM, though nominally not requiring ground-truth costs, uses c* in its implementation, so its performance is overestimated in the comparison.
- The authors argue the earlier suboptimality measure (Gamma_1) is not a valid metric because predicted costs can shrink toward zero to reduce it.
Limitations
- Theoretical guarantees hold only for linear models; deep networks are non-convex and the guarantees are not established for them.
- Solving the QP projection onto the KKT set is time-consuming, and the experiments exclude QPTL as it is too slow on large problems.
- Assumes known constraint matrices (A, b); unknown constraints are left for future work.
Experimental setup
Datasets: Warcraft shortest path dataset MNIST perfect matching dataset synthetic shortest path synthetic fractional knapsack
Benchmarks: Warcraft shortest path MNIST perfect matching synthetic shortest path synthetic fractional knapsack
Metrics: decision loss estimate loss wall-clock time per epoch
Baselines: ST MOM BB SPO+ QPTL
Builds on: SPO+ maximum optimality margin implicit differentiation perturbed optimizers / blackbox differentiation
Closest papers by meaning
- Inverse Optimization via Learning Feasible Regions (ICML 2025 · similarity 0.87)
- Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.85)
- Smart Surrogate Losses for Contextual Stochastic Linear Optimization with Robust Constraints (NeurIPS 2025 · similarity 0.85)
- Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.84)
- Scalable Kernel Inverse Optimization (NeurIPS 2024 · similarity 0.84)
- Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound (NeurIPS 2025 · similarity 0.84)
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.