Reviews: Generalization Bounds in the Predict-then-Optimize Framework

This paper considers a learning framework called predict-then-optimize. The problem in this setting is that parameters which are used in making predictions are not necessarily at hand when predictions should be made (costs of taking certain roads at particular moment are needed when a route has to be planned), and should be predicted before optimizing over them (in previous example, costs in the past are known and associated with other features known also at the moment). The interesting part of the framework is, that the learning problem used in learning the costs uses a loss function over error on the decision of the optimizer (SPO loss), instead of a direct error over the learned cost. In this framework, the authors provide several generalization bounds in different settings over a linear objective function, such as when feasible region where problem is solved is either polyhedron or any compact and convex region. They further work with stronger convexity assumptions and in their framework generalize margin guarantees for binary classification, and also give two modified versions of the SPO loss.