Advances in Information-Theoretic Differential Privacy: Composition and Calibration

Abstract

This thesis explores how methods from classical information theory and mathematical physics can be used to further the theory and practice of differential privacy. Differential privacy is a mathematically rigorous definition of privacy that has recently become the gold standard for private data analysis, and has been adopted by both governments and industry. Differential privacy adds intentional and carefully calibrated randomness into different parts of the data analysis pipeline with the purpose of ``masking'' the influence of any particular individual. This in turn makes the outcome of the data analysis pipeline a random variable, and a pipeline is private if it does not change by much in distribution when any individual is added/removed from the dataset. The first part of this thesis explores how differential privacy behaves under composition, that is, when the outcomes of many different randomized algorithms are released in tandem. It turns out that the well-known saddlepoint approximation from statistical physics can be used to asymptotically analyze how privacy evolves for these more complicated algorithms, and that solutions to the Schr"{o}dinger equation appear as the most private distributions for algorithms in the same asymptotic setting. The second part of this thesis explores an equivalent definition of differential privacy known as $f$-DP, which models differential privacy as a scientifically-minded adversary attempting to reconstruct datasets by setting up null and alternative hypothesis tests. This thesis extends various numerical techniques in differential privacy to the $f$-DP setting and advocates for the differential privacy community to calibrate algorithms using this framework due to its more intuitive formulation, which could increase the adoption of differential privacy.