Research map / Learning theory and algorithms / Combinatorial and search optimization
Overcoming the Optimizer's Curse: Obtaining Realistic Prescriptions from Neural Networks
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.
Adds a Local Outlier Factor realism constraint, reformulated as a single linear/quadratic constraint, to optimization over ReLU networks, and solves it with an adaptive sampling over realistic polytopes.
Problem
Optimizing over-parameterized neural networks for decision-making yields unrealistic prescriptions far from the data manifold (the Optimizer's Curse), and exact MIP approaches do not scale to large ReLU networks.
Approach
Reformulates the LOF inlier constraint as a single linear or quadratic constraint around training points, restricts search to polytopes induced by the ReLU network that contain a realistic training point, and adaptively samples these polytopes using a per-polytope upper bound so only a few LPs/SOCPs are solved.
Key results
- Adaptive sampling (AdSampling) finds the realistic solution with the highest objective in 60 of 80 MNIST experiments, versus 20 for projected gradient ascent (PGA) and 0 for the other baselines.
- On CIFAR-10 networks, AdSampling finds the best realistic solution in 31 of 40 experiments, versus 9 for PGA.
- Restricting to realistic polytopes with the Theorem 4.3 upper bound reduces the search space by 87.5% to 99.9% depending on the network.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive sampling instead of PGA | realistic prescription optimization for pretrained ReLU networks · MNIST | number of experiments with highest-objective realistic solution: 20 -> 60 | Helped |
| Use adaptive sampling instead of PGA | realistic prescription optimization for pretrained ReLU networks · CIFAR-10 | number of experiments with highest-objective realistic solution: 9 -> 31 | Helped |
| Use adaptive sampling instead of MIP | realistic prescription optimization for pretrained ReLU networks · MNIST | number of experiments with highest-objective realistic solution: 0 -> 60 | Helped |
| Use adaptive sampling instead of MIP | realistic prescription optimization for pretrained ReLU networks · CIFAR-10 | number of experiments with highest-objective realistic solution: 0 -> 31 | Helped |
Surprising findings
- The exact MIP method only returned solutions for the smallest networks within the time limit, with average optimality gaps of 307.78% and 1029.98% on 3x50 and 3x100 MNIST networks.
Limitations
- MIP-based exact methods do not scale beyond small networks.
- Realism is defined by LOF with threshold t, which is user-chosen (t=1.2 in experiments).
- Extension to general differentiable models relies on projected gradient ascent without optimality guarantees.
Experimental setup
Datasets: MNIST CIFAR-10 ImageNet
Benchmarks: MNIST CIFAR-10 ImageNet
Metrics: number of times finding the realistic solution with highest LOF inlier classification (scikit-learn LOF) optimality gap for MIP
Baselines: MIP (Fischetti & Jo) PGA Simulated Annealing SPSA Genetic Algorithm Big-M+cuts (Anderson et al.) Tsay et al. equal-size partition
Builds on: Fischetti & Jo MIP formulation of ReLU networks Local Outlier Factor Anderson et al. big-M with cuts projected gradient ascent
Closest papers by meaning
- Reduced Cost Influence Functions for Predict-then-Optimize under Noisy Data (NeurIPS 2026 · similarity 0.86)
- A Little Robustness Is All You Need: Leveraging Predictions for Contextual Optimization (NeurIPS 2026 · similarity 0.85)
- Outliers with Opposing Signals Have an Outsized Effect on Neural Network Optimization (ICLR 2024 · similarity 0.85)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.84)
- DFF: Decision-Focused Fine-Tuning for Smarter Predict-Then-Optimize with Limited Data (AAAI 2025 · similarity 0.84)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (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.