技术摘要：具有背包约束的差分隐私子模最大化问题

1. 问题定义

本文研究了差分隐私（DP）框架下的**具有背包约束的子模最大化（SMK）**问题。

• SMK 背景： 给定一个包含 $n$ 个元素的基集 $N$，一个子模目标函数 $f: 2^N \to \mathbb{R}$，一个代价函数 $c: N \to \mathbb{R}_{>0}$，以及一个预算 $B$，目标是找到一个子集 $S \subseteq N$，使得 $\sum_{v \in S} c(v) \leq B$ 且 $f(S)$ 最大化。该问题是 NP-hard 的，广泛应用于特征选择、数据摘要和影响力最大化等机器学习应用中。
• 隐私设置： 目标函数 $f_D$ 取决于敏感数据集 $D$。算法必须输出一个解 $S$，同时满足 $(\epsilon, \delta)$-差分隐私，确保当 $D$ 中单个个体的数据发生变化时，输出分布的变化可以忽略不计。
• 范围： 本研究同时考虑了**单调（monotone）和非单调（non-monotone）**目标函数。

2. 方法论与技术挑战

作者指出，标准的 DP 子模最大化技术（通常针对基数约束设计）对于背包约束而言是次优的，主要由于两个核心挑战：

1. 密度得分的变动敏感度： 在背包设置中，算法通常根据“密度”（边际收益除以代价）来选择元素。与敏感度统一的基数约束不同，密度得分 $f(u|S)/c(u)$ 的敏感度与元素代价 $c(u)$ 成反比。简单地应用标准选择机制（如指数机制）会导致产生与 $\Delta f \cdot (B/c_{\min})$ 成比例的加性误差，从而导致对最大可行解规模 $k$ 的依赖关系并非最优。

   • 解决方案： 作者采用了**广义报告噪声最大值（GRNM）**机制（Raskhodova & Smith, 2016）。该机制能够适应单个候选者的敏感度，确保加性误差随所选候选者的特定敏感度缩放，而非基于最坏情况的界限。

2. 组合瓶颈： 最先进的非隐私单调 SMK 算法（例如 Two-Guess-Greedy）需要 $O(n^2)$ 次迭代来猜测最优元素。标准的进阶组合定理会导致误差项随 $n$ 的多项式级增长，从而抵消了隐私带来的收益。

   • 解决方案： 作者利用了广义隐私选择框架（Cohen et al., 2023）。通过随机化每次枚举步骤被调用的次数，他们将隐私损失与子程序总数解耦，实现了对 $n$ 具有多项式对数依赖关系的加性误差。

3. 核心贡献与算法

A. 单调目标函数

论文提出了两种针对单调情况的算法：

1. DP-2GG (算法 2)： “两猜贪婪”（Two-Guess-Greedy）算法（Feldman et al., 2023）的差分隐私适配版本。

   • 机制： 它遍历所有规模至多为 2 的子集 $Y \subseteq N$。对于每个 $Y$，它在剩余实例上运行一个隐私化的密度贪婪子程序（算法 1）。最终解是从这些子程序的噪声输出中通过广义选择框架选出的。
   • 保证： 实现最优的 $(1 - 1/e)$-近似。
   • 复杂度： $O(\beta^{-1} n^3 k)$ 次查询。
   • 误差： 加性误差随 $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$ 缩放，通过消除对 $n$ 和 $1/c_{\min}$ 的多项式依赖，改进了前人的工作。

2. DP-DG+ (算法 7)： 一种基于 Density-Greedy+ 的快速单次遍历算法。

   • 机制： 执行一次隐私化的密度贪婪遍历，并使用报告噪声最大值（RNM）在部分解及其可行单元素扩展中选择最佳解。
   • 保证： 实现 $1/2$-近似。
   • 复杂度： $O(nk)$ 次查询。
   • 误差： 具有与单调情况相当的改进后的加性误差。

B. 非单调目标函数

本文引入了首个具有可证明保证的非单调 SMK 差分隐私算法。

• 算法： DP-SDG (算法 3)，是非隐私 SmkRan 算法（Han et al., 2021）的隐私化适配版本。
• 机制： 它使用 GRNM 进行基于密度的选择。选中的元素以 $1/2$ 的概率被加入解中（随机丢弃），以处理非单调性。关键在于，即使边际收益变为负值（由于噪声），它也会继续迭代，并使用 RNM 从所有部分解及其扩展中选择最佳解。
• 隐私分析： 为了处理选择步数的不确定性，作者推导了一个集中不等式，表明总迭代次数在随机意义下被几何随机变量之和所控制，并集中在 $O(k)$ 附近。
• 保证： 实现期望下的 $1/4$-近似。
• 复杂度： $O(nk)$ 次查询。
• 误差： 加性误差与单调情况相当。

4. 结果与实证评估

理论结果

作者在表 1 中将他们的结果与先前的工作（特别是 Sadeghi & Fazel, 2021）进行了对比。关键改进包括：

• 近似比： 匹配了已知最优的非隐私比例（单调情况为 $(1-1/e)$，非单调情况为 $1/4$）。
• 加性误差： 显著改善了对基集大小 $n$ 的依赖关系（多项式对数级 vs 多项式级）以及对最大可行解规模 $k$ 的依赖关系（随 $k^{1.5}$ 缩放 vs $k$ 或更差）。
• 查询复杂度： 关于 $n$ 和 $k$ 是多项式级的，而先前用于单调 SMK 的工作依赖于需要 $O(2^n)$ 次查询的多元线性扩展精确评估。

实证结果

算法在利用曼哈顿 100,000 个 Uber 接单位置的数据集进行的网约车优化任务上进行了评估。

• 效用： 当 $\epsilon \geq 0.1$ 时，DP 算法（DP-2GG, DP-DG+, DP-SDG）实现的效用与它们的非隐私对应版本（2GG, DG+, SmkRan）相当，显著优于随机基准。在 $\epsilon=0.2$ 时，DP-2GG 的表现与非隐私 2GG 的差距仅为 2%。
• 可扩展性： DP-DG+ 和 DP-SDG 在查询次数上随基集大小 $n$ 呈线性增长，证实了它们相比于更耗查询的 DP-2GG 具有实际的效率。

5. 重要性与声明

本文声称填补了差分隐私组合优化领域的关键空白：

1. 首个可证明的非单调 SMK 算法： 它建立了非单调 SMK 在差分隐私下的第一个可证明保证。
2. 改进的单调界限： 它既提高了单调 SMK 算法的效用（加性误差），也提高了其查询复杂度，摆脱了以往方法中指数级查询复杂度的限制。
3. 处理背包约束： 它证明了通过使用广义选择机制和集中不等式，可以克服背包约束带来的特定挑战（变化的敏感度和组合瓶颈），从而实现与基数约束设置相当的效率。

作者指出，虽然他们在 $k$ 上的加性误差依赖关系与已知最优的多项式时间算法（在基数约束设置下）相匹配，但关于在有限敏感度下是否能实现更好的 $k$ 依赖关系仍是一个开放性问题。他们还建议将这些技术扩展到结合背包约束和垫片（matroid）约束的情况，作为未来的研究方向。