PaperlayerView exact revision on arXiv

Source-linked AI summary

Smart "Predict, then Optimize"

Adam N. Elmachtoub, Paul Grigas

arXiv:1710.08005v5math.OCcs.LGstat.ML

TL;DR

The paper addresses the mismatch between prediction-error objectives and downstream optimization decisions. It introduces SPO and its convex SPO+ surrogate, proving consistency under mild conditions and reporting strong performance, while noting scope limitations in combining the framework with bias or robustness procedures.

  • Problem

    Machine-learning tools generally minimize prediction error without effectively accounting for how predictions are used in downstream optimization problems.

  • Method

    SPO uses optimization-problem structure to define decision error, while SPO+ provides a convex surrogate derived using duality theory.

  • Results

    SPO+ is statistically consistent with SPO under mild conditions and empirically performs well against standard predict-then-optimize approaches.

  • Takeaways & Limitations

    The framework offers an optimization-aware approach applicable to linear-objective polyhedral, convex, and mixed-integer optimization problems.

  • Takeaways & Limitations

    The paper identifies combining SPO with bias or robustness procedures in the presence of contextual data as challenging future work.

Abstract

from arXiv · show

Many real-world analytics problems involve two significant challenges: prediction and optimization. Due to the typically complex nature of each challenge, the standard paradigm is predict-then-optimize. By and large, machine learning tools are intended to minimize prediction error and do not account for how the predictions will be used in the downstream optimization problem. In contrast, we propose a new and very general framework, called Smart "Predict, then Optimize" (SPO), which directly leverages the optimization problem structure, i.e., its objective and constraints, for designing better prediction models. A key component of our framework is the SPO loss function which measures the decision error induced by a prediction. Training a prediction model with respect to the SPO loss is computationally challenging, and thus we derive, using duality theory, a convex surrogate loss function which we call the SPO+ loss. Most importantly, we prove that the SPO+ loss is statistically consistent with respect to the SPO loss under mild conditions. Our SPO+ loss function can tractably handle any polyhedral, convex, or even mixed-integer optimization problem with a linear objective. Numerical experiments on shortest path and portfolio optimization problems show that the SPO framework can lead to significant improvement under the predict-then-optimize paradigm, in particular when the prediction model being trained is misspecified. We find that linear models trained using SPO+ loss tend to dominate random forest algorithms, even when the ground truth is highly nonlinear.

1. Introduction

SPO integrates optimization structure into prediction-model training, measuring predictions by downstream decision error rather than prediction error. Its convex SPO+ surrogate is statistically consistent and empirically effective, especially under model misspecification.

  • Framework: The SPO framework trains prediction models using the nominal optimization problem’s objective and constraints, while preserving the predict-then-optimize paradigm.It explicitly uses optimization structure during training rather than changing the sequential decision workflow.
  • Framework: SPO loss measures the excess cost of the decision induced by predicted parameters relative to the optimal cost under the true parameters.In vehicle routing, this is the extra travel time caused by optimizing with predicted rather than true edge costs.
  • SPO+ loss: Because SPO loss can be nonconvex and discontinuous, the paper derives the convex, efficiently optimizable SPO+ surrogate using duality theory.The surrogate is designed for optimization problems with linear objectives, including linear, convex, and integer formulations.
  • Theory: Under mild conditions, minimizing SPO+ is equivalent to minimizing SPO, and the conditional mean E[c|x] minimizes both SPO+ and SPO Bayes risk.The paper also connects SPO and SPO+ to 0-1 and hinge losses in a special binary-classification case.
  • Empirical findings: Empirically, SPO+ can yield near-optimal decisions under model misspecification, with linear SPO+ models dominating random forests even when the ground truth is highly nonlinear.The framework’s value increases as model misspecification increases because it targets predictions that produce better optimization decisions.
  • Scope and future work: Combining SPO with bias or robustness procedures remains challenging with contextual data and is identified as worthwhile future research.The paper presents the framework as a foundation for operations-driven machine-learning tools in real-world optimization settings.

2. “Predict, then Optimize” Framework

The SPO framework models contextual optimization by predicting unavailable cost vectors from features, then solving the downstream problem using those predictions. It focuses on loss functions and training procedures that account for the optimization task.

  • Framework setup: The framework assumes a known feasible region and linear-objective optimization problem whose cost vector is unavailable when decisions are made.Features are observed instead, together with a conditional distribution for the unknown cost vector.
  • Framework setup: For each new feature vector, the decision maker seeks to solve a contextual stochastic optimization problem involving the conditional cost distribution.
  • Predict-then-optimize: Predict-then-optimize replaces the unavailable conditional mean cost vector with a prediction and solves the deterministic optimization problem using that prediction.
  • Framework goals: The framework studies suitable loss functions and algorithms for training prediction models whose outputs are used in downstream optimization.

1. Nominal (downstream) optimization problem, which is of the form

The nominal problem has a fixed, known feasible region and an unknown linear-objective cost vector inferred from contextual features. The framework formalizes prediction models, optimization oracles, and losses around this setup.

  • Nominal optimization problem: The nominal optimization problem uses decision variables w and cost vector c in a linear objective over a known feasible region S.
  • Scope: The methodology extends to combinatorial and mixed-integer optimization because linear optimization over a feasible set shares its optimal value with optimization over the set’s closed convex hull.
  • Optimization oracle: An optimization oracle w*(c) returns a solution for any input cost vector, with commercial solvers or specialized algorithms providing such oracles in several settings.
  • Prediction model: Training data pair contextual feature vectors with realized cost vectors, while a hypothesis class maps features to predicted cost vectors.
  • Loss design: Standard losses such as least squares ignore the nominal optimization structure, whereas the paper constructs losses that measure decision error by leveraging that structure.

3. SPO Loss Functions

The SPO loss evaluates prediction quality through downstream decision error rather than prediction error alone. Because direct SPO-risk minimization is difficult, the paper develops an oracle-independent formulation and a convex SPO+ surrogate.

  • SPO loss: The SPO loss measures the excess cost incurred when the decision optimized for predicted costs is evaluated under the realized costs.
  • SPO loss: Predictions with equal least-squares error can induce different decisions and different SPO losses because the optimization problem determines decision consequences.
  • SPO loss: The unambiguous SPO loss avoids dependence on a particular optimization oracle by using a worst-case tie-breaking formulation.
  • Connections: When the feasible set is [-1/2,+1/2] and costs are binary, the SPO loss exactly matches binary classification’s 0-1 loss.
  • Optimization difficulty: Direct empirical-risk minimization with the SPO loss is difficult because the loss may be discontinuous and is at least as hard as optimizing 0-1 loss.
  • Illustrative examples: In the illustrative nonlinear example, SPO-trained lines achieve zero training decision error despite fitting the data less closely than least-squares lines.
  • SPO+ loss: The SPO+ loss is a convex surrogate and upper bound derived through duality, and it can approximately minimize empirical SPO risk.
  • Theory: The paper reports consistency of SPO+ with respect to SPO under conditions and identifies the SPO+ decision boundary with the SPO boundary in a stylized example.

4. Consistency of the SPO+ Loss Function

The paper establishes Fisher consistency for SPO+ under explicit distributional and optimization assumptions, linking its population-risk minimizers to those of the true SPO loss.

  • Fisher consistency: Fisher consistency means that minimizing the surrogate Bayes risk also minimizes the true SPO risk.This definition formalizes the surrogate's statistical alignment with the decision-focused loss.
  • SPO minimizers: If the nominal optimization problem has a unique optimum, E[c|x] minimizes the true SPO risk, and any almost-surely equal predictor does likewise.This result motivates the target that SPO+ must recover under the theorem's assumptions.
  • Fisher consistency: Under Assumption 1, every SPO+ population-risk minimizer equals E[c|x] almost surely and minimizes the SPO risk.The assumptions require unique optimal solutions for E[c|x], conditional central symmetry and continuity, and a feasible region with nonempty interior.
  • Comparison with least squares: Least squares is also Fisher consistent, while experiments show SPO+ can outperform it by tailoring predictions to the optimization task.The paper therefore distinguishes population consistency from finite-sample performance under model misspecification.
  • SPO minimizers: For a cost-vector risk minimizer c*, every nominal optimum W*(c*) is optimal for P(c̄); conversely, uniqueness plus expected-cost optimality implies SPO-risk minimization.The equivalence relies on the linear objective and the stated uniqueness condition.
  • Assumptions and limitations: Central symmetry and continuity are jointly required in Proposition 6: either condition alone can permit an SPO+ minimizer that fails to minimize SPO risk.The appendix examples show failures when continuity or symmetry is considered without the other condition.

5. Computational Approaches

The paper gives two computational routes for SPO+ empirical-risk minimization: a duality-based reformulation and stochastic-gradient methods using an optimization oracle.

  • Optimization formulation: SPO+ empirical-risk minimization is convex when the SPO+ loss is convex and the regularizer is convex.The discussion focuses on linear predictors with optional regularization such as ridge, entrywise ℓ1, or nuclear norm penalties.
  • Stochastic-gradient methods: The stochastic-gradient route computes SPO+ subgradients by repeatedly calling the optimization oracle w*(·), without explicitly describing the feasible region S.This makes the approach applicable when S is complicated or represented implicitly.
  • Computational trade-offs: Explicit reformulations require inequality constraints for S, whereas stochastic-gradient methods scale better when the sample size or problem dimensions are very large.Interior-point conic solvers can provide high-accuracy solutions for small to medium instances but scale less well on large ones.
  • Duality-based reformulation: The reformulation route uses linear-programming duality to model the piecewise-linear convex SPO+ loss with tractable epigraph constraints.For polyhedral feasible regions, the reformulated problem can be solved using standard conic optimization machinery.
  • Duality-based reformulation: With common regularizers, the reformulated problem becomes a linear program for LASSO, a quadratic program for ridge, or a semidefinite program for the nuclear norm.These forms enable use of specialized optimization solvers.

6. Computational Experiments

Synthetic shortest-path and portfolio experiments compare SPO+ with least squares, absolute loss, and random forests under varying sample sizes, nonlinearities, and noise.

  • Experimental design: The experiments evaluate normalized test SPO loss on shortest-path and portfolio optimization problems using linear SPO+ models and three competing methods.Models are assessed on independent test sets, with the normalized loss based on the test set's full-information optimal cost.
  • Shortest path results: As polynomial degree and model misspecification increase, SPO+ generally performs best across instances except when n=5000, where random forests is comparable.At deg∈{1,2}, absolute loss, least squares, and SPO+ perform comparably, with least squares slightly better under noise ε̄=0.5.
  • Shortest path results: For n∈{100,1000}, random forests is usually worst, while at n=5000 it performs comparably to the simpler linear SPO+ model.An exception occurs at n=1000 and deg∈{6,8}, where random forests outperforms the other stated competitors.
  • Model misspecification: At higher polynomial degrees, least squares is sensitive to outliers, absolute loss is less sensitive, and SPO+ adapts better to model misspecification with n=1000.The reported pattern contrasts SPO+'s decision-focused training with random forests' slower nonparametric convergence.
  • Overall findings: Across the experiments, SPO+ is either close to the best method or dominates the alternatives, with its value increasing when model misspecification and data availability increase.The paper summarizes this as a suitable choice across the tested parameter regimes.

7. Conclusion

The SPO framework trains prediction models to minimize decision error by incorporating the downstream optimization problem’s structure. Its convex SPO+ surrogate is consistent with SPO and performs especially well under model misspecification, while future work remains open.

  • SPO incorporates the objective and constraints of the optimization problem into prediction-model training.
  • The framework targets decision error rather than prediction error and applies to problems with linear objectives, including integer optimization.
  • SPO+ is a convex loss derived from the nonconvex SPO loss using duality theory.
  • SPO+ is consistent with respect to the SPO loss, while least squares is also consistent and performs well when the ground truth is nearly linear.
  • SPO+ strongly outperforms all approaches empirically when there is model misspecification.
  • Future work includes more empirical testing, unknown constraint parameters, and nonlinear objectives.

A. Examples

The examples instantiate the framework in network flow and simple feasible regions, illustrating how decision error relates to classification and how SPO+ behavior depends on optimization-relevant dimensions and assumptions.

  • Network Flow: Network flow decisions route flow through a graph subject to flow-conservation and capacity constraints, with costs estimated from features.
  • Network Flow: A linear hypothesis class predicts cost vectors as f(x)=Bx, and least squares trains the model by minimizing mean squared error.
  • When one optimization dimension is irrelevant, every prediction differing only in that dimension can minimize SPO+ risk.
  • In the one-dimensional example, the SPO loss equals binary 0-1 loss because it is zero for matching signs and one otherwise.

B.2. Proof of Proposition 2.

The proof derives the relevant convex-analytic relation through a dual formulation, establishing monotonicity and the inequalities needed for Proposition 2.

  • The dual function q(α) is convex and monotone decreasing, with subgradient z*(ĉ)−ĉ^T w*(αĉ−c).
  • Optimal solutions for ĉ can be represented as the intersection of S with the halfspace ĉ^T w≤z*(ĉ).
  • The proof introduces a nonnegative Lagrange multiplier for the prediction-induced inequality constraint and forms the Lagrangian dual function.
  • Strong duality follows because the feasible region S is compact and convex, satisfying the cited theorem’s assumptions.
  • The proof uses the support function’s convexity and the subgradient relation involving w*(2ĉ−c) to establish the required bound.

B.5. Proof of Theorem 1.

The proof establishes Fisher consistency by showing that SPO+ risk minimizers equal the conditional mean cost vector, which minimizes SPO risk under a singleton-optimum assumption.

  • Under the stated assumptions, any SPO+ risk minimizer is almost surely the conditional mean function x↦E[c|x].
  • If W*(E[c|x]) is a singleton, the conditional mean minimizes conditional SPO risk.
  • Assumption 1.1 extends the conditional result to the population SPO risk with probability one over x.
  • The proof of the converse direction constructs a uniquely optimal perturbation and applies Jensen’s inequality to compare risks.
  • The resulting optimal-solution inclusion W*(c*)⊆W*(c̄) connects the constructed minimizer to the nominal optimization problem.

B.7. Proof of Proposition 6.

The proof establishes properties of the SPO+ risk using convexity, subgradients, symmetry, and strict positivity away from the mean cost vector.

  • Convexity allows the SPO+ risk’s subdifferential to be represented through expected subgradients of the SPO+ loss.The derivation expresses the subdifferential using expectations involving w∗(2ĉ−c) and w∗(c).
  • Under central symmetry of c around its mean c̄, the mean satisfies the SPO+ risk optimality condition.Symmetry gives E_c[w∗(c)] = E_c[w∗(2c̄−c)], implying 0 ∈ ∂R_SPO+(c̄).
  • For any nonzero perturbation Δ, continuity and a nonempty interior of S yield positive probability that the induced optimizers disagree.This disagreement makes the corresponding objective difference strictly positive.
  • Therefore, every c̄ + Δ with Δ ≠ 0 has larger SPO+ risk than c̄, making c̄ the unique minimizer.The proof concludes directly from the strict risk inequality.
  • The proof also invokes linear-programming strong duality to rewrite terms in the SPO+ formulation.Variables p_i are introduced to express the relevant linear functions explicitly.

C. Stochastic Gradient Approach

The paper trains linear prediction models with SPO+ using stochastic subgradient descent, requiring repeated access to an optimization oracle and supporting convex regularizers.

  • The objective combines empirical SPO+ losses with a regularization term λΩ(B), where convexity supports stochastic subgradient optimization.The loss is convex but may be nondifferentiable, while Ω is assumed subdifferentiable.
  • SPO+ linear regression admits computable subgradients based on the difference between optimizers under true and predicted costs.Proposition 8 uses 2(w∗(c_i) − w∗(2Bx_i − c_i)) together with a regularizer subgradient.
  • Algorithm 1 applies mini-batched stochastic subgradient descent by repeatedly sampling training examples and computing update quantities.The method initializes B, samples indices uniformly, chooses step sizes, and updates iteratively.
  • The main computational requirement is access to the optimization oracle w∗(·), used N times per iteration.This permits application when an efficiently computable oracle exists, including some combinatorial and mixed-integer problems.
  • For nonsmooth convex settings, the cited stochastic method provides an O(1/ε^2) iteration complexity guarantee for an ε-suboptimal averaged iterate in expectation.The guarantee concerns the averaged iterate and is stated for the relevant step-size regime.
  • Early stopping can select the averaged iterate with the smallest validation-set estimate of out-of-sample true SPO loss.The validation set monitors true SPO loss during training.

D. Experimental Details of Portfolio Optimization Application

The portfolio experiments synthetically generate nonlinear return relationships, factor and idiosyncratic noise, and varied sample sizes, degrees, and noise levels for evaluating SPO+ training.

  • The experiment uses d = 50 assets, five features, and a random binary matrix B∗ encoding the true model parameters.Each entry of B∗ is Bernoulli with probability 0.5 of equaling 1.
  • Feature vectors are sampled from a standard multivariate Gaussian distribution with independent entries.Specifically, x_i ∼ N(0,I_p).
  • The conditional mean return is polynomial in the features, with degree deg varied over {1,4,8,16}.The construction sets the mean returns through B∗x_i and a degree-dependent term.
  • Observed returns add factor noise and idiosyncratic Gaussian noise, producing covariance Σ = LL^T + (0.01τ)^2I_50 conditional on features.The factor-loading matrix L is generated with entries uniformly distributed on [−0.0025τ,0.0025τ].
  • The portfolio risk level is set to γ := 2.25 · w̄^TΣw̄, where w̄ is the equal-weight portfolio.The equal-weight portfolio is defined as w̄ := e/10.
  • The evaluation varies n ∈ {100,1000} and τ ∈ {1,2}, uses 50 independent trials per combination, and tests on 10,000 observations.No regularization is used; SPO+ is trained with SGD, while comparison optimization problems are solved with Gurobi.
Loading 1710.08005v5…