Optimal Fairness under Local Differential Privacy

技术摘要：局部差分隐私下的最优公平性

问题陈述
机器学习模型越来越多地依赖敏感属性（如种族、性别）进行高风险决策，这引发了对公平性和隐私性的担忧。虽然差分隐私（DP）是隐私保护的标准，但已有研究表明，中心化差分隐私可能会加剧不公平。相比之下，局部差分隐私（LDP）——即数据在离开用户设备前进行扰动——在与公平性交互方面的研究仍处于起步阶段。现有的基于 LDP 的公平性方法通常依赖于特定的机制，如广义随机响应（GRR）或随机响应（RR），并且往往局限于二元敏感属性。核心问题在于：如何设计最优的 LDP 机制，在保持非平凡效用的同时，最小化二元及多值敏感属性的数据不公平性，并从理论上建立这种数据不公平性的降低如何转化为分类公平性的提升。

方法论
作者提出了一个预处理框架，在模型训练前使用最优 L LDP 机制对敏感属性进行扰动。该方法分为理论推导和实验验证两部分：

1. 最优机制推导：

   • 二元属性： 对于二元敏感属性（$A \in \{0, 1\}$），作者推导出了一个闭式最优解。他们将问题表述为：在固定隐私预算 $\epsilon$ 的约束下，最小化扰动数据集与原始数据集之间的数据不公平性比例。最优机制被证明取决于数据分布（特别是标签在给定属性下的条件概率）和隐私参数。与标准的 RR 不同，最优机制并不一定对称地对待两个类别；它会根据哪个类别更普遍或更具歧视性，来调整报告真实值的概率。
   • 非二元属性： 对于多值属性（$A \in [k]$），问题被重新表述为一个最小-最大线性分式规划问题。其目标是在满足以下约束的情况下，最小化数据不公平性指标（特指定义 1 中的 $\Delta$）：
     • $\epsilon$-LDP 约束。
     • 行随机约束（概率之和为 1）。
     • 真实性约束（正确报告的概率 $\ge$ 错误报告的概率）。
     • 效用约束（将总误差概率限制在阈值 $\zeta$ 以内）。
       该优化问题通过分支定界法进行数值求解。

2. 与分类公平性的理论联系：
   本文建立了最小化数据不公平性与降低分类不公平性之间的理论联系。作者引入了判别-准确率（DA）最优分类器的概念——即在准确率和判别性方面都不被其他分类器严格支配的分类器。作者证明，对于 DA 最优分类器，在具有较低不公平性（特指较低的 $\Delta'$）的数据上进行训练，可以保证降低所得分类器的统计平价差距（statistical parity gap）。

3. 实验验证：
   提出的最优机制（OPT）在多种数据集（Adult, LSAC, COMPAS, Bank, Student Performance, German Credit）上使用 LightGBM 和逻辑回归进行了评估。

   • 基准测试： 将 OPT 与标准 LDP 机制（GRR/RR, Subset Selection）以及最先进的公平性干预方法（FairProjection, FairBalance）进行了对比。
   • 指标： 通过准确率（Accuracy）、统计平价（$\Delta_{SP}$）、机会均等（$\Delta_{EO}$）和平均机会均等（$\Delta_{MEO}$）来衡量性能。

核心贡献

• 最优机制设计： 本文为二元敏感属性提供了首个闭式最优 LDP 机制，并为非二元属性提供了一个可行的数值框架，以最小化数据不公平性。
• 理论证明： 文中证明了对于 DA 最优分类器，通过 LDP 预处理降低数据不公平性，可以直接导致分类不公平性的降低，从而弥合了隐私保护预处理与下游公平性之间的鸿沟。
• 实验优越性： 提出的 OPT 机制在减少不公平性的同时保持了与非私有基准相当的准确率，表现优于现有的 LDP 机制（GRR, SS）。
• 更优的权衡： 与专门的预处理（FairBalance）和后处理（FairProjection）公平性方法相比，OPT 在实现更优的准确率-公平性权衡的同时，还能保护敏感属性的隐私。

结果

• 二元属性： 在 Adult 和 LSAC 数据集上，OPT 在保持与 RR 和 SS 相当的准确率的同时，显著降低了统计平价和机会均等的差距（例如，在 LSAC 上几乎使差距减半）。
• 非二元属性： 对于多值属性（如种族、家庭收入），数值求解的 OPT 机制在较高的隐私预算（$\epsilon$）下，比 GRR 和 SS 实现了更低的公平性差距，且准确率损失微乎其微。
• 与公平性方法的比较： 在匹配准确率水平时，与 FairProjection（后处理）和 FairBalance（预处理）相比，OPT 通常能产生更低的公平性差距（例如，在 COMPAS 数据集上，与 FairProjection 相比，OPT 将 $\Delta_{SP}$ 从 26.8% 降至 24.3%）。在 Bank 数据集上，OPT 实现了更高的准确率（90.1% vs 84.5%）和更低的 $\Delta_{EO}$。
• 集成性： OPT 成功替换了 [13] 中两步框架中的 RR，展示了在仅有经过隐私化处理的敏感属性可用时的适应性。

意义与主张
本文主张，局部差分隐私是一种原则性且有效的预处理干预手段，用于增强公平性。与可能在本质上与公平性不兼容的中心化 DP 不同，LDP 提供了一种机制，使得隐私保护固有的随机性可以主动减轻数据不公平性。作者将这项工作定位为连接隐私保护预处理与分类公平性的直接纽带，证明了对敏感属性进行最优扰动是缓解偏差且不牺牲模型效用的简单而强大的工具。结果表明，LDP 不仅仅是一个隐私工具，更是机器学习流水线中实现公平性放大的可行策略。