引用

Zachary Izzo, Lexing Ying, James Zou. How to learn when data reacts to your model: performative gradient descent[J]. arXiv preprint arXiv:2102.07698, 2021.

摘要

执行分布转移（Performative distribution shift）可以捕获由 ML 模型选择导致的数据分布更改。由于模型和数据分布之间的交互作用，寻找最优模型参数比较困难。在这一领域的工作集中在寻找稳定点上，但执行稳定点可能不是最优解。因此本文引入了执行梯度下降(PerfGD)算法，这是第一个可以证明收敛到执行最优点的算法。PerfGD 显式地捕获了模型中的更改对数据分布的影响方式，并且操作简单。

1.引言

分布移位/数据集移位问题：底层数据分布中的更改可能会导致模型性能不佳。大多数之前的工作都集中在数据分布的外部变化。最近，研究人员试图解决分布转移的内生来源，即执行分布转移：数据分布的变化是由模型的选择引起的。

最初的论文和许多后续研究将执行设置视为一个动态的系统。建模者反复观察由他选择的模型参数所产生的数据分布，然后将这个诱导分布固定，通过减少其在固定分布上的损失来更新模型。这些工作所解决的主要问题是，在什么条件下这个过程稳定，即这个过程何时会收敛到一个模型，且该模型所诱导的分布是最优的？具有此特性的模型称为执行稳定点。

然而，专注于上述目标会忽略模型训练的主要目标:获得最小的执行损失（因部署的模型诱导的数据分布所产生的损失）。一般来说，执行稳定点远不是执行最优点。限制较少时，稳定点甚至可能不存在，此时寻找稳定点的算法可能会振荡或发散。

基于这些缺点，本文引入了一种新的算法：执行梯度下降(PerfGD)，该算法可以证明，在基于数据生成过程的现实假设下，该算法可以收敛到执行最优点。本文从理论和实证两方面论证了 PerfGD 相对于现有算法的优势。

2.设置与表示

2.1 交互模型与基本表示

交互模型：θ 表示模型参数空间，本文假设它是封闭的、凸的。设初始模型参数为 θ0。

D: Θ→P(Z)表示执行的分布图。即当展开参数为 θ 的模型时，接收到由 D(θ)绘制的 iid 数据。假设 D 是未知的，只能从数据中间接地观察它。观察数据表示为：

其中 Z 表示数据的样本空间。当 t = 0,1…T−1，仅使用之前模型参数 θs，s≤t 和数据集的信息计算 θt+1。数据集表示如下：

执行性 ML 的目的是有效计算模型参数：

其中下面公式表示执行损失：

θ1 表示模型参数，θ2 表示分布参数。

因此本文将模型部署数量 T 作为效率度量，目标是保持低部署数量。

另外，执行梯度的表示及规则为：

2.2 先前算法

论文《Performative prediction》中将执行预测问题标准化，引入了两种算法——重复风险最小化(RRM)和重复梯度下降(RGD)——用于计算邻近最优点。下面将介绍这些算法。

该文作者表明，在损失和分布位移的确定假设下，RRM 和 RGD 收敛于一个稳定点 θSTAB≈θOPT。然而，当这些假设失败时，RRM 和 RGD 可能收敛到离 θOPT 很远的一点，甚至根本不收敛。

3.PerfGD 一般式

本文主要目标是为真实执行梯度 ∇L =∇1L +∇2L 设计一个更准确的估计。由于关于 RGD 的 ∇1L 随机估计已经很准确，所以只需要估计 ∇2L，它对应了梯度中数据分布位移的部分。

假设 D(θ)有一个连续可微的密度 p(z;f(θ))，其中 p(z;w)的函数形式是已知的，f(θ)很容易从 D(θ)提取的样本中估计出来。例如，如果 D(θ)是一个指数族，它的密度为

对应于已知的函数

和未知函数 f(θ) = η(θ)。对于标准指数族，有从 D(θ)样本中估算自然参数 η(θ)的直接方法。因此，任何指数族都适合这个框架。

本文如无特别说明，默认假设

是均值变化和固定协方差的正态分布混合。

3.1.算法描述

对于任何向量的集合 v0, v1，…∈Rp 和任意两指标 i<j，本文将用 vi:j 表示矩阵，其列由 vi, vi+1，…vj，即

定义 1H∈RH 是由 H 个 1 组成的向量。考虑到模型参数 Θ 的空间是封闭的、凸的，定义 projΘ(θ)为 θ 在 Θ 上的欧几里得投影。使用这种表示法，算法 3 给出了 PerfGD 的伪代码。

3.2.推导

假设已知 p(z;w)对于任意的 w，D(θ)有密度 p(z;f(θ))。执行损失为

假设 p 和 f 连续可微，计算执行梯度:

其中

请注意:可以通过在 D(θ)样本上平均 ∇l 来获得 ∇1L 的估计数。对于 ∇2L，唯一的未知量是 f(θ)和 df/dθ。通过假设，f(θ)可以很容易从样本中估计出来，即存在一个估计函数，给定一个样本

返回

为了估计 df/dθ，使用有限差分近似。由泰勒定理知

通过对 ∆θ 求伪逆，得到导数的估计数:

我们要求这个系统是超定的，即 H≥p，以避免在估计 f 和从有限差分近似到导数的偏差中对噪声的过拟合。(H 是之前用于估计 df/dθ 的有限差分数，p 是 θ 的维数)

将 f(θ)和 df/dθ 的这些近似代入 ∇2L 的表达式中，就可以使用作者选择的方法计算或近似这个积分。一种普遍适用的选择是使用 reinforcement-style 近似：

由于 p 是已知的，∂2logp 也是已知的，可以通过样本

的期望求平均值来近似上述方程，将我们的近似替换为 f(θ)和 df/dθ。任何能够准确估计 ∇2L 的技术都是可以接受的，我们将看到在高斯分布的情况下，梯度的 REINFORCE 估计器是不必要的。我们将这个过程得到的全梯度的近似值 ∇L =∇1L +∇2L 写为：

4.理论结果

本节从理论上量化了 PerfGD 的性能。为简单起见,本节专注于特定情况，即 D(θ)= N(f(θ),σ2)是固定一维高斯方差,以及模型单一参数 θ∈R .本文使用单一前置步骤估计 df/dθ(H = 1)。

下面陈述对平均函数 f，损失函数 l 的假设，以及估计量 ˆf 与 f 的误差。

条件 1. 假设 f 的一阶导数和二阶导数有界。

条件 2. f 的估计量 ˆf 有界误差为：

条件 3. 损失有界：

条件 4. 梯度估计 ˆ∇L 下方和上方有边界：

条件 5. 真正的执行梯度的上界是 G：

条件 6. 真正的执行梯度是 LLip-Lipschitz：

最后，假设计算 ˆ∇L 所涉及的所有积分和期望都是精确计算出来的，因此误差仅来自于估计数 ˆf 和用于近似 df/dθ 的有限差分

本节将证明 PerfGD 收敛于一个近似的临界点，即:∇L≈0 的点。因此，条件 4 的下界可以看作是 PerfGD 的停止准则，即当梯度范数下降到阈值 g 以下时终止。作为主要定理的推论，本节将证明这个阈值可以取 g∝δ1/5。首先限定近似误差为 ˆ∇Lt，后续为:

引理 1：对于步长 η，执行梯度的误差为

接下来量化了 PerfGD 的收敛速度以及它最终收敛点的误差。

定理 2：设步长

PerfGD 的迭代满足

定理 2 表明，PerfGD 收敛于一个近似的临界点。对梯度范数的保证可以很容易地转化为 θ 到 θ opt 距离的界，并附带一些温和的附加假设。例如，如果 L 是 α-强凸，那么凸分析的标准结果表明|θt−θOPT|≤α−1|∇Lt|。证明可通过结合引理 1 的误差界和对 LLip-光滑函数的梯度下降进行分析。

最后，作为定理 2 的推论，可以看到我们可以选择 g∝δ1/5 作为停止判据

推论 3。当停止准则 g∝δ1/5 时，PerfGD 的迭代次数满足

这表明 PerfGD 中的误差在大约 T∝δ−4/5 迭代后将停止衰减。

5.应用 PerfGD

本节将通过实例展示：该简单框架可以在许多实际环境中轻松获得好的执行效果。本节使用具有固定协方差的高斯分布，即

使用 3.1 节的术语，对于 d 维高斯分布，有

且 f(θ) =µ(θ)是高斯分布的均值。

对 µ(θ)的估计量 ˆ 就是样本平均值:

特别值得注意的是 ∇2L 在本例中采取的形式。初步计算得出

上式表明，可以通过从 D(θ)中，对样本的期望内的表达式求平均值来近似 ∇2L，不需要使用 REINFORCE 技巧或其他更复杂的数值计算积分的方法。具体来说,有

本节以如上一般的形式给出下面的每一个实验。在下面的所有图中，阴影区域表示相关曲线在 10 次试验中平均值的标准误差。

5.1.简单示例:混合高斯和非线性平均值

取 l(z;θ) = θz 和 Θ =[−1,1]。

在第一个示例中,设

由于 µ 是非线性的，估计 dµ/dθ 较为困难。尽管如此，PerfGD 仍然找到了最佳点。结果如下面的图 1 所示。

对于第二个例子，设：

这里两个平均值在 θ 中都是线性的，即。

应用 PerfGD，其中每个点的真实集群分配是已知的;该情况下 PerfGD 精确地收敛到 θOPT，并达到最佳的执行损失。结果如下面的图 2 所示。

5.2.定价

θ 表示作为分销商所设定的各种商品的价格矢量。向量 z 表示顾客对每种商品的需求。目标是使预期收益 ED(θ)[θTz]最大化。假设 D(θ) = N(µ(θ)，Σ)，可以直接应用算法 3 和函数 ˆµ 和 ˆ∇L2 来计算最优价格

该实验在 d = 5 的高维环境中工作。定义 Θ = [0,5]d，µ(θ) =µ0−εθ。(也就是说，每一种商品的平均需求随着价格上涨而线性下降。)

结果如图 3 所示。对于这种情况，可以分析计算 θOPT 和 θSTAB。每个点的执行收益都显示在图的右侧。正如预期的那样，PerfGD 平滑地收敛到最优价格，而 RGD 收敛到唯一产生次优收入的固定点。在本例中，RRM(未显示)保持固定在 θRRM=[5,5，…5]T。

5.3.二元分类

假设目标是利用特征 x∈Rd 预测一个标号 y∈{0,1}。假设标号 yBernoulli(γ)，而 x|yN(µy(θ)，Σy)。执行性损失可以写成

可以将一般的 PerfGD 方法应用于上述式子中的每一项，得到一个近似的随机梯度。(将标签 y = 0 的数据特征作为第一项的数据集，将标签 y = 1 的数据特征作为第二项的数据集)

本处使用一个垃圾邮件分类示例的合成模型。使用逻辑模型对电子邮件进行分类，模型参数 θ = (θ0,θ1)T∈R2。给定一个实值特征 x，模型输出 hθ(x) = 1/(1 +e−θ0-θ1x)。让标签 y = 1{email 是垃圾邮件}。假设：

本实验设 f(θ) =µ1−εθ1。

结果如图 4 所示。PerfGD 对执行梯度的估计改进后，与 RGD 相比，执行损失大约减少了 9%。在这种情况下，RRM(未显示)在两个 θ 值之间振荡，这两个 θ 值都比 RGD 或 PerfGD 的执行损失大得多。

5.4.回归

假设 x 的边际分布与 θ 无关。假设 y|x~N(µ(x,θ),σ2)，则表现性损失为

内部期望具有应用 PerfGD 所需的形式。然而，由于 x 是连续的值，通常只有一个样本来近似上述式子中的内部期望，导致 3.2 节中 ∇L(θ)所需数量的估计存在严重偏差或不准确。两种选择:既可以使用消除所需数量偏差的技术以直接应用 PerfGD，也可以使用重新参数化技巧和修改后的 PerfGD。这里使用后一种方法。

假设响应 y 符合线性模型

执行损失可以被写作：

由于已经消除了分布对 θ 的依赖，可以很容易地计算出梯度:

我们可以首先通过正则化普通最小二乘来估计 β，然后通过有限差分来估计 dβ/dθ，如一般设置为：

简单起见，使用一维线性回归参数 θ∈r。特征 x 是从固定分布

中得出的，y|x 的执行系数 β(θ)的形式为 β(θ) = a0+ a1θ。用脊-正则化平方损失来表示 l。

结果如图 5。在这种情况下，θ OPT 和 θSTAB 之间有很大的差距。正如预期的那样，PerfGD 平滑地收敛到 θOPT，而在本例中，RGD 和 RRM 都收敛到 θSTAB。PerfGD 对 RGD 和 RRM 的改进导致了一个数量级以上的执行损失降低。

6.结论

本文讨论了数据分布受模型参数影响时的建模设置，即执行分布位移。本文介绍了一种新的算法 PerfGD，在对执行分布进行一些参数假设的情况下，能计算出更准确的执行梯度估计。本文证明了理论结果对梯度估计的准确性和方法的收敛性，并通过几个经验实例证实 PerfGD 优于现有的算法，如重复梯度下降和重复风险最小化。准确性和迭代需求实际上都是可行的，因为许多 ML 系统每隔几天就会进行定期更新。

本文提出了进一步研究的方向。未来工作的一个方向是将我们的方法扩展到非参数分布。另一个可能有效的方向是改进导数 df/dθ 的估计。最后，为处理高维数据而专门定制方法也是值得关注的。

致谢

本文由南京大学软件学院 2021 级硕士潘中颢翻译转述。

审核人：南京大学软件学院博士 刘佳玮