Dec, 2023
通过多阶段采样技术（MUST）增强隐私、效用和计算效率的平衡
Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency through MUltistage Sampling Technique (MUST)
Xingyuan Zhao, Fang Liu
TL;DR应用一种随机算法对数据集的子集进行处理，而不是整个数据集，是提高发布信息隐私保护性的一种常见方法。我们提出了一种名为 MUltistage Sampling Technique（MUST）的子采样方法类别，用于差分隐私（DP）上的隐私增强（PA）问题。我们通过对几种 2 级 MUST 过程（MUST.WO，MUST.OW 和 MUST.WW）进行全面分析，即在第 I 阶段从原始数据集中有（W）或没有（O）替代地进行采样，然后在第 II 阶段从第 I 阶段中选择的子集中进行有（W）或没有（O）替代地进行采样。我们还通过 Fourier accountant 算法分析了重复应用 MUST 时的隐私组合。我们的理论和实验结果表明，在 ε 方面，MUST.OW 和 MUST.WW 比包括泊松抽样、无替代抽样和有替代抽样的常见一级抽样过程具有更强的 PA 性能，而在 δ 方面，结果因情况而异。我们还证明 MUST.WO 在 PA 中等效于有替代抽样。此外，由 MUST 过程生成的最终子集是一个多集，由于涉及有替代抽样，可能包含相同数据点的多个副本，这增强了对需要对不同数据点（如梯度下降）进行复杂函数计算的算法的计算效率。我们的效用实验表明，在相似的隐私损失下，与一级子抽样方法相比，MUST 在保留隐私的输出方面提供了相似或改进的效用和稳定性。在需要差分隐私保证时，MUST 可以无缝集成到随机优化算法或涉及并行或同时子抽样的方法中（如 bagging 和子抽样引导）。