Analytical Composition of Differential Privacy via the Edgeworth Accountant
Many modern machine learning algorithms are composed of simple private
algorithms; thus, an increasingly important problem is to efficiently compute
the overall privacy loss under composition. In this study, we introduce the
Edgeworth Accountant, an analytical approach to composing differential privacy
guarantees of private algorithms. The Edgeworth Accountant starts by losslessly
tracking the privacy loss under composition using the $f$-differential privacy
framework, which allows us to express the privacy guarantees using privacy-loss
log-likelihood ratios (PLLRs). As the name suggests, this accountant next uses
the Edgeworth expansion to the upper and lower bounds the probability
distribution of the sum of the PLLRs. Moreover, by relying on a technique for
approximating complex distributions using simple ones, we demonstrate that the
Edgeworth Accountant can be applied to the composition of any noise-addition
mechanism. Owing to certain appealing features of the Edgeworth expansion, the
$(\epsilon, \delta)$-differential privacy bounds offered by this accountant are
non-asymptotic, with essentially no extra computational cost, as opposed to the
prior approaches in, wherein the running times increase with the number of
compositions. Finally, we demonstrate that our upper and lower $(\epsilon,
\delta)$-differential privacy bounds are tight in federated analytics and
certain regimes of training private deep learning models.