Privacy Sandbox Attribution Reporting API 中的摘要报告优化

近年来，隐私沙盒计划旨在探索广告商衡量其广告活动效果的负责任方式，旨在弃用第三方 Cookie（但须与英国竞争和市场管理局解决任何竞争问题）。Cookie是网站存储在用户设备上的包含用户偏好的小数据块；它们可用于提供更好的浏览体验（例如，允许用户自动登录）以及提供相关内容或广告。隐私沙盒试图通过提供一种隐私保护替代方案来解决人们对使用 Cookie 跟踪整个网络浏览数据的担忧。

许多浏览器使用差异隐私(DP) 来提供不依赖 cookie 进行广告转化衡量的隐私保护 API，例如归因报告 API (ARA)。ARA 会加密各个用户操作并将其收集到汇总摘要报告中，该报告可估算衡量目标，例如归因于广告系列的转化次数和价值（网站上的有用操作，例如购买商品或注册邮件列表）。

配置 API 参数（例如，在不同转化之间分配贡献预算）的任务对于最大限度地提高摘要报告的效用非常重要。在“ Privacy Sandbox 归因报告 API 中的摘要报告优化”中，我们引入了一个用于对摘要报告进行建模的正式数学框架。然后，我们将最大化摘要报告效用的问题公式化为优化问题，以获得最佳 ARA 参数。最后，我们使用真实和合成数据集评估该方法，并证明与基线未优化摘要报告相比，其效用显著提高。

ARA 摘要报告

我们使用以下示例来说明我们的符号。假设有一家名为Du & Penc的虚构礼品店，它使用数字广告来吸引客户。下表记录了他们的假日销售情况，其中每条记录都包含展示特征，包括 (i) 展示 ID、(ii) 广告活动和 (iii) 广告展示的城市，以及转化特征，包括 (i) 购买的商品数量和 (ii) 这些商品的总美元价值。

Du & Penc 的印象和转换特征日志。

数学模型

ARA 摘要报告可以通过四种算法建模：（1）贡献向量、（2）贡献边界、（3）摘要报告和（4）重建值。贡献边界和摘要报告由 ARA 执行，而贡献向量和重建值由 AdTech 提供商执行 - 使企业能够购买和销售数字广告的工具和系统。这项工作的目的是协助 AdTech 优化摘要报告算法。

贡献向量算法将测量结果转换为离散化和缩放的 ARA 格式。缩放需要考虑每次展示的总体贡献限制。这里我们提出了一种剪辑和执行随机舍入的方法。该算法的结果是可聚合键和值的直方图。

接下来，贡献限制算法在客户端设备上运行，并对归因报告强制执行贡献限制，任何超出限制的贡献都将被丢弃。输出是归因转化的直方图。

摘要报告算法在服务器端的可信执行环境中运行，并返回满足 DP 的噪声聚合结果。噪声是从离散拉普拉斯分布中采样的，为了强制隐私预算，一份报告只能查询一次。

最后，重建值算法将测量值转换回原始比例。重建值和贡献向量算法由 AdTech 设计，两者都会影响从摘要报告中获得的效用。

ARA 摘要报告的说明性用法，其中包括贡献向量（算法 A）、贡献边界（算法 C）、摘要报告（算法 S）和重建值（算法 R）。算法 C 和 S 在 API 中已修复。AdTech 设计了 A 和 R。

错误指标

在选择误差度量来评估近似值的质量时，需要考虑几个因素。为了选择特定的度量，我们考虑了误差度量的理想属性，这些属性可以进一步用作目标函数。考虑到理想属性，我们选择了𝜏 截断均方根相对误差(RMSRE𝜏) 作为其属性的误差度量。请参阅论文以了解详细讨论和与其他可能度量的比较。

优化

为了优化以 RMSRE𝜏 为衡量标准的效用，我们为每个切片选择一个上限参数C和隐私预算 𝛼。两者的组合决定了实际测量值（例如总价值为 3 美元的两次转换）如何在 AdTech 端进行编码，然后传递给 ARA 进行贡献边界算法处理。RMSRE𝜏 可以精确计算，因为它可以用剪辑偏差和噪声分布的方差来表示。按照这些步骤，我们发现固定隐私预算 𝛼 或上限参数 C 的 RMSRE𝜏 是凸的（因此可以有效地获得另一个参数的误差最小化值），而对于联合变量（C，𝛼），它变为非凸的（因此我们可能并不总是能够选择最佳参数）。无论如何，任何现成的优化器都可用于选择隐私预算和上限参数。在我们的实验中，我们使用scipy.optimize库中的SLSQP最小化器。

合成数据

通过在转换数据集上进行测试，可以对不同的 ARA 配置进行实证评估。但是，出于隐私方面的考虑，访问此类数据可能会受到限制或速度变慢，甚至根本无法访问。解决这些限制的一种方法是使用复制真实数据特征的合成数据。

我们提出了一种通过对真实世界转化数据集进行统计建模来负责任地生成合成数据的方法。我们首先对真实转化数据集进行实证分析，以发现 ARA 的相关特征。然后，我们设计了一个管道，利用这种分布知识来创建可以通过输入参数定制的逼真的合成数据集。

该管道首先生成幂律分布的展示次数（步骤 1），然后针对每次展示生成泊松分布的转化次数（步骤 2），最后针对每次转化生成对数正态分布的转化值（步骤 3）。利用数据集相关参数，我们发现这些分布与广告数据集特征非常匹配。因此，可以从历史或公共数据集中学习参数并生成用于实验的合成数据集。

总体数据集生成步骤及其特征以供说明。

实验评估

我们在三个真实数据集（Criteo、AdTech Real Estate 和 AdTech Travel）和三个合成数据集上评估我们的算法。Criteo 包含 1500 万次点击，Real Estate 包含 10 万次转化，Travel 包含 3 万次转化。每个数据集分为一个训练集和一个测试集。训练集用于选择贡献预算、裁剪阈值参数和转化次数限制（真实数据集每次点击只有一次转化），并在测试集上评估误差。每个数据集使用展示特征划分为多个切片。对于真实数据集，我们为每个切片考虑三个查询；对于合成数据集，我们为每个切片考虑两个查询。

对于每个查询，我们选择 RMSRE𝝉 𝜏 值为训练数据集上查询中值的五倍。这确保了误差度量对数据重新缩放的不变性，并允许我们通过对每个特征使用 𝝉 来组合来自不同尺度特征的误差。

真实世界数据集的散点图显示了观察到转化值的概率。拟合曲线代表最佳对数正态分布模型，可有效捕捉数据中的潜在模式。

结果

我们将基于优化的算法与简单的基线方法进行了比较。对于每个查询，基线使用相等的贡献预算和固定的训练数据分位数来选择裁剪阈值。我们的算法在现实世界和合成数据集上产生的误差都比基线低得多。我们基于优化的方法可以适应隐私预算和数据。

在三个真实世界数据集和三个合成数据集上，我们的算法和基线的隐私预算 RMSREτ 为 {1, 2, 4, 8, 16, 32, 64}。与使用固定分位数作为剪切阈值并在查询之间平均分配贡献预算的基线相比，我们的基于优化的方法始终能够实现更低的误差。

结论

我们研究了 ARA 中摘要报告的优化，目前该系统已部署在数亿个 Chrome 浏览器上。我们提出了 ARA 捐款预算优化问题的严格公式，目的是为研究人员提供强大的抽象概念，以促进实际改进。

我们的方案利用历史数据在差异隐私下约束和扩展未来数据的贡献，这种方案非常通用，适用于广告以外的场景。基于这项工作的一种方法是使用过去的数据来学习数据分布的参数，然后应用从该分布中得出的合成数据进行隐私预算，以便查询未来数据。请参阅论文和随附代码以了解详细的算法和证明。

致谢

这项工作是与 Badih Ghazi、Pritish Kamath、Ravi Kumar、Pasin Manurangsi 和 Avinash Varadarajan 合作完成的。我们感谢 Akash Nadan 的帮助。