# Generalization Bounds in the Predict-then-Optimize Framework

arXiv: https://arxiv.org/abs/1905.11488 · HTML: https://mlsanity.com/paper/1905.11488/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 30 of 54)

- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [A Survey of Contextual Optimization Methods for Decision Making under Uncertainty](https://mlsanity.com/paper/2306.10374/) (2023)
- [High-Dimensional Prediction for Sequential Decision Making](https://mlsanity.com/paper/2310.17651/) (2023)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Integrated Conditional Estimation-Optimization](https://mlsanity.com/paper/2110.12351/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Estimate-Then-Optimize versus Integrated-Estimation-Optimization versus Sample Average Approximation: A Stochastic Dominance Perspective](https://mlsanity.com/paper/2304.06833/) (2023)
- [Decision-Focused Learning with Directional Gradients](https://mlsanity.com/paper/2402.03256/) (2024)
- [Data-Driven Sample Average Approximation with Covariate Information](https://mlsanity.com/paper/2207.13554/) (2022)
- [Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming](https://mlsanity.com/paper/2301.11260/) (2023)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [TaskMet: Task-Driven Metric Learning for Model Learning](https://mlsanity.com/paper/2312.05250/) (2023)
- [Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms](https://mlsanity.com/paper/2305.07730/) (2023)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Dissecting the Impact of Model Misspecification in Data-driven Optimization](https://mlsanity.com/paper/2503.00626/) (2025)
- [A Note on Task-Aware Loss via Reweighing Prediction Loss by Decision-Regret](https://mlsanity.com/paper/2211.05116/) (2022)
- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [A Training-free Method for LLM Text Attribution](https://mlsanity.com/paper/2501.02406/) (2025)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Optimizer's Information Criterion: Dissecting and Correcting Bias in Data-Driven Optimization](https://mlsanity.com/paper/2306.10081/) (2023)
- [PROPEL: Supervised and Reinforcement Learning for Large-Scale Supply Chain Planning](https://mlsanity.com/paper/2504.07383/) (2025)
- [Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning](https://mlsanity.com/paper/2106.03279/) (2021)
- [Prescribing net demand for two-stage electricity generation scheduling](https://mlsanity.com/paper/2108.01003/) (2021)
- [From Inverse Optimization to Feasibility to ERM](https://mlsanity.com/paper/2402.17890/) (2024)
- [Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.17200/) (2024)
- [The Bias-Variance Tradeoff in Data-Driven Optimization: A Local Misspecification Perspective](https://mlsanity.com/paper/2510.18215/) (2025)
- [Decision-Focused Sequential Experimental Design: A Directional Uncertainty-Guided Approach](https://mlsanity.com/paper/2602.05340/) (2026)
- [A Solver-Free Training Method for Predict-then-Optimize](https://mlsanity.com/paper/2606.19587/) (2026)
- [Application-Driven Learning: A Closed-Loop Prediction and Optimization Approach Applied to Dynamic Reserves and Demand Forecasting](https://mlsanity.com/paper/2102.13273/) (2021)

## Abstract (arXiv)

The predict-then-optimize framework is fundamental in many practical settings: predict the unknown parameters of an optimization problem, and then solve the problem using the predicted values of the parameters. A natural loss function in this environment is to consider the cost of the decisions induced by the predicted parameters, in contrast to the prediction error of the parameters. This loss function was recently introduced in Elmachtoub and Grigas (2022) and referred to as the Smart Predict-then-Optimize (SPO) loss. In this work, we seek to provide bounds on how well the performance of a prediction model fit on training data generalizes out-of-sample, in the context of the SPO loss. Since the SPO loss is non-convex and non-Lipschitz, standard results for deriving generalization bounds do not apply. We first derive bounds based on the Natarajan dimension that, in the case of a polyhedral feasible region, scale at most logarithmically in the number of extreme points, but, in the case of a general convex feasible region, have linear dependence on the decision dimension. By exploiting the structure of the SPO loss function and a key property of the feasible region, which we denote as the strength property, we can dramatically improve the dependence on the decision and feature dimensions. Our approach and analysis rely on placing a margin around problematic predictions that do not yield unique optimal solutions, and then providing generalization bounds in the context of a modified margin SPO loss function that is Lipschitz continuous. Finally, we characterize the strength property and show that the modified SPO loss can be computed efficiently for both strongly convex bodies and polytopes with an explicit extreme point representation.