EUVIMEDEUVIMED entdecken
Crossref

Generalization Bounds in the Predict-Then-Optimize Framework

Othman El Balghiti, Adam N. Elmachtoub, Paul Grigas, Ambuj Tewari

Mathematics of Operations Research · 2023-11 · 48 (4) · 2043-2065

DOI: 10.1287/moor.2022.1330 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2023-11. Verfasst von Othman El Balghiti und 3 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 28 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 is 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. Because the SPO loss is nonconvex 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. Funding: O. El Balghiti thanks Rayens Capital for their support. A. N. Elmachtoub acknowledges the support of the National Science Foundation (NSF) [Grant CMMI-1763000]. P. Grigas acknowledges the support of NSF [Grants CCF-1755705 and CMMI-1762744]. A. Tewari acknowledges the support of the NSF [CAREER grant IIS-1452099] and a Sloan Research Fellowship.

Zitieren

APA

Balghiti, O. E., Elmachtoub, A. N., Grigas, P., & Tewari, A. (2023). Generalization Bounds in the Predict-Then-Optimize Framework. Mathematics of Operations Research, 48(4), 2043-2065. https://doi.org/10.1287/moor.2022.1330

Vancouver

Balghiti OE, Elmachtoub AN, Grigas P, Tewari A. Generalization Bounds in the Predict-Then-Optimize Framework. Mathematics of Operations Research. 2023;48(4):2043-2065. doi:10.1287/moor.2022.1330

BibTeX
@article{Balghiti2023,
  author = {Balghiti, Othman El and Elmachtoub, Adam N. and Grigas, Paul and Tewari, Ambuj},
  title = {Generalization Bounds in the Predict-Then-Optimize Framework},
  journal = {Mathematics of Operations Research},
  year = {2023},
  volume = {48},
  number = {4},
  pages = {2043--2065},
  doi = {10.1287/moor.2022.1330}
}
Kostenlos starten →