Poster
Generalization Bounds in the Predict-then-Optimize Framework
Othman El Balghiti · Adam N. Elmachtoub · Paul Grigas · Ambuj Tewari

Thu Dec 12th 05:00 -- 07:00 PM @ East Exhibition Hall B + C #229
in Theory -- Learning Theory »

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.

Keywords: Theory -> Learning Theory · Optimization -> Convex Optimization

Author Information

Othman El Balghiti (Columbia University)
Adam N. Elmachtoub (Columbia University)
Paul Grigas (UC Berkeley)
Ambuj Tewari (University of Michigan)

More from the Same Authors