Abstract
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
(2017), which called it the Smart Predict-then-Optimize (SPO) loss. Since the
SPO loss is nonconvex and noncontinuous, standard results for deriving
generalization bounds do not apply. In this work, we provide an assortment of
generalization bounds for the SPO loss function. In particular, we 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 set, have poor dependence on the
dimension. By exploiting the structure of the SPO loss function and an
additional strong convexity assumption on the feasible region, we can
dramatically improve the dependence on the dimension via an analysis and
corresponding bounds that are akin to the margin guarantees in classification
problems.
Description
[1905.11488] Generalization Bounds in the Predict-then-Optimize Framework
Links and resources
Tags
community