{
  "id": "2108.08887",
  "version": "v1",
  "published": "2021-08-19T19:25:46.000Z",
  "updated": "2021-08-19T19:25:46.000Z",
  "title": "Risk Bounds and Calibration for a Smart Predict-then-Optimize Method",
  "authors": [
    "Heyuan Liu",
    "Paul Grigas"
  ],
  "categories": [
    "cs.LG",
    "math.OC",
    "stat.ML"
  ],
  "abstract": "The predict-then-optimize framework is fundamental in practical stochastic decision-making problems: first predict unknown parameters of an optimization model, then solve the problem using the predicted values. A natural loss function in this setting is defined by measuring the decision error induced by the predicted parameters, which was named the Smart Predict-then-Optimize (SPO) loss by Elmachtoub and Grigas [arXiv:1710.08005]. Since the SPO loss is typically nonconvex and possibly discontinuous, Elmachtoub and Grigas [arXiv:1710.08005] introduced a convex surrogate, called the SPO+ loss, that importantly accounts for the underlying structure of the optimization model. In this paper, we greatly expand upon the consistency results for the SPO+ loss provided by Elmachtoub and Grigas [arXiv:1710.08005]. We develop risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss, which provide a quantitative way to transfer the excess surrogate risk to excess true risk. By combining our risk bounds with generalization bounds, we show that the empirical minimizer of the SPO+ loss achieves low excess true risk with high probability. We first demonstrate these results in the case when the feasible region of the underlying optimization problem is a polyhedron, and then we show that the results can be strengthened substantially when the feasible region is a level set of a strongly convex function. We perform experiments to empirically demonstrate the strength of the SPO+ surrogate, as compared to standard $\\ell_1$ and squared $\\ell_2$ prediction error losses, on portfolio allocation and cost-sensitive multi-class classification problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-19T19:25:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "risk bounds",
      "smart predict-then-optimize method",
      "calibration",
      "achieves low excess true risk",
      "loss achieves low excess true"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}