Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition
Hua Wang1 Sheng Gao1 Huanyu Zhang2 Milan Shen2 Weijie Su1 Jiayuan Wu1
Abstract
In privacy-preserving data analysis, many procedures and algorithms are structured as compositions of multiple private building blocks. As such, an important question is how to efficiently compute the overall privacy loss under composition. This paper introduces the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees for private algorithms. Leveraging the $f$ -differential privacy framework (Dong et al., 2022), the Edgeworth Accountant accurately tracks privacy loss under composition, enabling a closed-form expression of privacy guarantees through privacy-loss log-likelihood ratios (PLLRs). As implied by its name, this method applies the Edgeworth expansion to estimate and define the probability distribution of the sum of the PLLRs. Furthermore, by using a technique that simplifies complex distributions into simpler ones, we demonstrate the Edgeworth Accountant’s applicability to any noise-addition mechanism. Its main advantage is providing $(\varepsilon,\delta)$ -differential privacy bounds that are non-asymptotic and do not significantly increase computational cost. This feature sets it apart from previous approaches, in which the running tim
中文速览
差分隐私（differential privacy）在保护深度学习和联邦分析中用户数据隐私时，往往需要把成百上千个独立隐私模块串联起来，如何快速而精确地计算这种"组合"后的整体隐私损耗，是该领域的核心难题。本文提出"Edgeworth Accountant"方法，借助 f-差分隐私框架将隐私损耗转化为隐私损失对数似然比（PLLR）之和，再用 Edgeworth 展开（比中心极限定理收敛更快的分布近似工具）来刻画这个求和分布，从而给出隐私参数 (ε, δ) 的闭合解析表达式。实验结果表明，对于相同机制的组合，该方法仅需常数时间 O(1)；对于异构机制，也只需线性时间 O(m)，远优于现有基于快速傅里叶变换的方法，同时精度高于矩方法（moments accountant）和高斯差分隐私近似，并首次在 f-DP 框架内提供了有限样本（非渐近）的严格上下界。这一成果使大规模私有深度学习训练和联邦学习场景下的隐私核算既高效又可靠，为实际部署提供了更实用的理论保障。
原文 arXiv:2206.04236;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2206.04236v3