In the predict-then-optimize environment, the parameters of an optimization task are predicted based on contextual features and it is desirable to leverage the structure of the underlying optimization task when training a statistical learning model. A natural loss function in this setting, called the “Smart Predict-then-Optimize” (SPO) loss, is based on considering the cost of the decisions induced by the predicted parameters, in contrast to standard measures of prediction error. While directly optimizing the SPO loss function is computationally challenging, we propose the use of a novel convex surrogate loss function, which we prove is consistent under mild conditions. We also provide an assortment of novel generalization bounds for the SPO loss function, including bounds based on a combinatorial complexity measure and substantially improved bounds under an additional strong convexity assumption.