Research map / Learning theory and algorithms / Prediction and decision losses
Smart Surrogate Losses for Contextual Stochastic Linear Optimization with Robust Constraints
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.
Extends SPO/SPO+ to contextual linear optimization with predicted robust constraints, using conformal uncertainty sets, a convex SPO-RC+ surrogate, and truncation plus KMM importance reweighting.
Problem
Contextual stochastic linear optimization where the constraint parameters are uncertain and predicted from context, so decisions may be infeasible under the true constraint parameters; standard SPO/SPO+ assume only objective uncertainty.
Approach
Define a feasibility-sensitive SPO-RC loss over contextual conformal uncertainty sets, a convex SPO-RC+ surrogate proven Fisher consistent, and train on truncated data (true constraint parameter inside the uncertainty set) with KMM importance weights to correct sample selection bias.
Key results
- On l2 fractional knapsack, PTO yields 45.00% infeasible solutions versus 0.02% for MSE, RF, and SPO-RC+ trained on the importance-reweighted data.
- SPO-RC+ on the reweighted dataset outperforms SPO-RC+ on the truncated dataset in nearly every scenario, especially at training size n=1000.
- For l1 knapsack, SPO-RC+ outperforms MSE as cost complexity increases; solution caching cuts training time substantially with only slight degradation in NormSPORCTest.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use robust constraints instead of predict-then-optimize with predicted constraints | Fractional knapsack · Fractional knapsack, ℓ2 conformity score, test set (size 3000), deg_c=4 | infeasibility (%): 45.00 -> 0.02 | Helped |
| Train SPO-RC+ on importance-reweighted truncated data instead of the original dataset | SPO-RC+ · Toy fractional knapsack, feasibility-guaranteed region (x<0.5) | NormSPORCTest: 16.7% -> 0.2% | Helped |
| Use importance-reweighted data rather than truncated data | SPO-RC+ · Fractional knapsack, ℓ2 conformity score | NormSPORCTest | Helped |
| Train with SPO-RC+ rather than MSE as cost complexity increases | Linear cost-prediction models · Fractional knapsack, ℓ1 conformity score | NormSPORCTest | Helped |
| Train with SPO-RC+ rather than MSE | Linear cost-prediction models · Alloy production | NormSPORCTest | Mixed |
| Train with SPO-RC+ rather than MSE for simple cost functions | Linear cost-prediction models · Fractional knapsack, ℓ1 conformity score, low polynomial degree | NormSPORCTest | Mixed |
| Use randomized solution caching during SPO-RC+ training (ablation) | SPO-RC+ · Fractional knapsack, ℓ1 conformity score | NormSPORCTest | Hurt |
| Use randomized solution caching during SPO-RC+ training (ablation) | SPO-RC+ · Fractional knapsack, ℓ1 conformity score | training time | Helped |
Surprising findings
- For small cost-function complexity, MSE slightly outperforms SPO-RC+ in the l1 knapsack experiments.
Limitations
- Applies only to problems with a linear objective.
- Two-step procedure learns the uncertainty set independently of the cost coefficients.
- Experiments use only synthetic data and small problems.
Experimental setup
Datasets: synthetic fractional knapsack instances (d=5, p=10) synthetic alloy production instances (brass, Zinc and Copper)
Benchmarks: fractional knapsack (l2 and l1 conformity scores) alloy production (brass)
Metrics: NormSPORCTest infeasibility percentage training time
Baselines: MSE PTO random forest
Builds on: SPO SPO+ conformal prediction Kernel Mean Matching PyEPO
Closest papers by meaning
- Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.87)
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.87)
- Contextual Linear Optimization with Bandit Feedback (NeurIPS 2024 · similarity 0.86)
- Stochastic Bayesian Optimization with Unknown Continuous Context Distribution via Kernel Density Estimation (AAAI 2024 · similarity 0.86)
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization (AAAI 2024 · similarity 0.85)
- Learning Polyhedral Conformal Sets for Robust Optimization (NeurIPS 2026 · 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.