Research map / Learning theory and algorithms / Prediction and decision losses

Learning Polyhedral Conformal Sets for Robust Optimization

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Conformal prediction sets · 0 citations (OpenAlex)

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.

Learns polyhedral conformal uncertainty sets (max-affine nonconformity scores) by minimizing the downstream robust decision loss, then restores finite-sample coverage via recalibration on an independent split, with a suboptimality-gap bound.

Problem

Robust optimization needs uncertainty sets that are both statistically valid (coverage) and not overly conservative for the downstream decision; standard conformal sets are task-agnostic and ignore decision structure.

Approach

Parameterize the conformal nonconformity score as a max-affine (polyhedral gauge) function of residuals, learn its hyperplanes by directly minimizing the induced worst-case decision loss on a learning split, and recalibrate the radius on an independent split to recover validity after data-dependent selection.

Key results

• Recalibrated decision-aware polyhedron attains coverage close to the nominal 90% level across tasks, while the ablation without recalibration can fall below target coverage.
• Among valid methods, the proposed method achieves competitive or lowest worst-case cost; smaller-volume sets (PCP, size-aware polyhedron) do not consistently yield lower worst-case cost or regret.
• Theory: finite-sample coverage of the recalibrated set and a suboptimality-gap bound of order O_P(m^{-1/2} + sqrt(log n / n)) plus optimization tolerance.

Surprising findings

• Smaller-volume uncertainty sets do not necessarily yield lower downstream worst-case cost or regret, since volume minimization can discard directions important for the decision.

Limitations

• Focus on polyhedral geometry may be less suitable for highly nonlinear uncertainty.
• Exact MIP reformulation is computationally expensive for large calibration sets; the scalable pinball surrogate is approximate.
• Theoretical bound contains unknown constants, so it guides data splitting rather than giving quantitative suboptimality.

Experimental setup

Datasets: synthetic heteroscedastic nonlinear regression data UCI Energy Efficiency

Benchmarks: synthetic robust decision tasks (linear, quadratic-regularized, newsvendor) UCI Energy Efficiency

Metrics: empirical coverage average worst-case cost average regret set volume wall-clock time

Baselines: Bonferroni boxes conformal boxes/balls PCP F-CROMS PICNN scores size-aware polyhedron polyhedron without recalibration

Builds on: split conformal prediction SAA / scenario approximation column-and-constraint generation pinball loss quantile regression

Closest papers by meaning

• Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.88)
• Optimal transport-based conformal prediction (ICML 2025 · similarity 0.88)
• Generative Conformal Prediction with Optimized Coverage Allocation (NeurIPS 2026 · similarity 0.88)
• Conformal Prediction in The Loop: A Feedback-Based Uncertainty Model for Trajectory Optimization (NeurIPS 2025 · similarity 0.87)
• Robust Conditional Conformal Prediction via Branched Normalizing Flow (NeurIPS 2026 · similarity 0.87)
• Conformal Prediction with Learned Features (ICML 2024 · similarity 0.87)