Background

在现实世界的优化应用中，机器学习与优化方法的结合已经成为决策分析的重要方法论。本文就是要讨论数据驱动下，带有不确定参数的优化问题。这种问题通常通过“Predict, then Optimize”的范式来解决。在涉及预测再优化问题中，机器学习方法的目的是最小化预测误差，并不关注如何将预测结果用于下游的优化问题中。

符号说明

决策变量；表示可行域； 表示特征向量的维度；表示训练样本数量； 表示优化问题的最优解集合~解集； 表示最优解，使得；

Predict, then Optimize Framework

架构的主旨在于，生成最小化决策误差而非预测误差的预测模型。转化为数学表述，决策者研究的目标：

给定特征的实例下， 是 的条件分布，优化问题目标函数的期望值等于基于 (即表示为)解决的优化问题的确定性版本的目标函数期望值。

  1. 给定名义优化问题：
  1. 训练数据形式
  2. 成本向量 预测模型 使得并定义一个类有
  3. 定义损失函数衡量成本向量预测值与真实成本向量的误差。 即求解优化问题确定最佳预测模型根据经验风险最小化原则，需要满足：
  • 给定真实成本向量 , 最可能的决策是 得到
  • 给定预测的成本向量 , 做出的决策是 得到
  • SPO损失函数定义为：
  • Alternate definition with no oracle dependence is also given, we break ties with worst-case (this avoids predicting 0 all for everything)

SPO损失函数

损失函数：衡量由于成本向量预测不精确而做出次优决策时产生的超额成本。

根据范式，计算流程：

  • 给定成本向量预测值；
  • 求解得到决策；
  • 计算；

但由于损失函数在计算过程中，可能的非凸性和不连续性，提出损失函数作为的凸替代，的几点性质如下：

  • ；
  • 是关于 的凸函数；
  • 给定， 在处的次梯度为

SPO+计算

求解SPO+ERM问题的方法：1. 基于对偶理论的凸优化方法；2. 基于梯度下降； 假设可行域为一个多面体区域 ，正则化问题等价：

16 Elmachtoub and Grigns: Smart -Prodiet, then Optimize” since for all . Clearly, replacing the constraint with in (il) results in an upper bound. Since this is true for all values of , then

In fact, one can show that inequality (治) is actually an equality using duality theory, and moreover, the optimal value of tends to . Intuitively, one can see that as gets large, then the term in the inner maximization objective becomes negligible and the solution tends to . Thus, as tends to , the inner maximization over can be replaced with maximization over , which recovers (5i). We formalize this equivalence in Proposition below.

Proposition 2 (Dual Representation of SPO Loss). For any cost vector prediction and realized cost vector , the function is monotone decreasing on , and the true SPO loss function may be expressed as

Using Proposition we shall now revist the SPO ERM problem (四) which can be written as

第一个等式来自以下事实：对于任何 。第二个等式来自以下观察：所有 个变量都趋向于相同的值，因此我们可以用一个变量替换它们，我们称之为 。第一个不等式来自命题 2 ，具体来说, 在 (6) 中设置 会导致 SPO 损失的上限（我们将在下文中重新讨论这个特定的选择）。最后，第二个不等式来自以下事实： 是 的可行解。 （9）中的加数表达式正是我们所说的 SPO+ 损失函数 ，我们在定义 3 中对其进行了正式陈述。

定义 3 (SPO+ Loss)。给定成本向量预测 c 和实际成本向量 损失定义为

回想一下， 是 S 的支持函数，即 使用此符号, SPO+ 损失可以等效地表示为 。

凸代理 SPO+ 损失函数推导的最后一步 (9) 涉及使用一阶展开式近似凹 (非凸) 函数 。也就是说，我们 应用边界 这可以看作是基于在 (处计算的超梯度对 的一阶近似，即 )。请注意，如果 则 , 这意味着当最小化 SPO+ 时, 直观地讲, 我们试图让 接近

因此，人们可能期望 是 的近乎最优解，因此，不等式 (9) 将是一个合理的近似值。事实上第 4 节在某些假设下提供了一致性属性，这些假设表明, 如果预测模型在足够大的数据集上进行训练, 则预测 确实合理接近 的预期值。

更正式地，我们让 D 表示 的分布，即 D, 并考虑真实 SPO 风险（贝叶斯风险）最小化问题的总体版本:

以及 SPO+ 风险最小化问题的人口版本:

注意这里我们对 没有任何限制，这意味着 H 由任何将特征映射到成本向量的可测函数组成。 定义4（费希尔一致性）。如果 ( 的贝叶斯风险的最小化器集合) 也最小化 (11)，则损失函数 ,被认为与损失具有费希尔一致性。

为了直观理解，我们让 和 分别表示 (11)和 (12) 的任意最优解。从 (1) 可以看出， 的理想值就是 。事实上, 只要 的最优解以概率 1 唯一（在 的分布上），即几乎肯定唯一，那么 确实是 (11) 的最小化器（参见命题 5）。此外 , 任何几乎肯定等于 的函数也是 (11) 的最小化器。在定理1中, 我们表明, 在假设 1 下, SPO+ 人口风险 (12) 的任何最小化器都必须几乎肯定满足 ，因此也最小化了 SPO 风险（11）。总之，在假设 1 下, SPO+ 损失与 SPO 损失是 Fisher 一致的。