A Unified Perspective of Surrogates for Decision-Aware Learning via Directional Gradients

One of the key challenges in decision-focused learning is that for many problems of interest (like linear optimization with an uncertain objective), the decision-loss is ill-behaved, piecewise constant, and NP-Hard to optimize. Consequently, numerous authors have proposed various surrogate loss functions to approximate the decision loss, often based on ad hoc approximations and heuristic reasoning. In this talk, we present a unifying and principled framework for these surrogate losses. Specifically, we show that the (ill-behaved) can be is equivalent to a particular directional gradient of a plug-in functional, and we can derive an entire family of surrogate losses by invoking different zeroth-order approximations for this gradient. We call the resulting surrogates "Perturbation Gradient" losses, and provide difference-of-convex functions representation. Several popular losses are either special cases of a perturbation gradient loss, or a particular convexification of a perturbation gradient loss (e.g., SPO+, Fenchel-Young Loss, Differentiable Black Box Optimizers). Leveraging this relationship, we can provide novel performance guarantees for many of these methods, and, most importantly, suggest simple, computationally cheap modifications to the original losses that lead to substantive computational improvements in practice.