Topics in Differential Privacy

The great success of modern deep learning raises significant privacy concerns across numerous tasks. Differential privacy (DP) offers a mathematically rigorous framework for analyzing and developing private algorithms that work on datasets containing sensitive personal information. Nonetheless, despite the wide application of DP, there are several fundamental challenges that limit the performance of models learned with a DP constraint. This dissertation aims to address three critical challenges in differential privacy: The first challenge pertains to the composition of DP algorithms. Calculating the exact DP guarantees for the composition of DP algorithms is known to be #P-complete, yet large numbers of compositions are common in practice. We introduce the Edgeworth Accountant, the first DP accountant that provides accurate finite-sample privacy guarantee with optimal time complexity for large number of compositions of private algorithms. Compared to the state-of-the-art accountant based on fast Fourier transform, our Edgeworth Accountant achieves comparable accuracy with significantly improved time complexity. Additionally, it is more numerically stable for a large number of compositions due to its analytical nature. The second challenge concerns hyperparameter tuning with DP algorithms. Practitioners often overlook privacy leaks resulting from hyperparameter tuning, despite evidence demonstrating that hyperparameter choices can reveal private information about the underlying dataset. We propose the first adaptive hyperparameter tuning method that rigorously accounts for privacy loss while allowing practitioners to freely use existing non-DP hyperparameter tuning methods, such as Gaussian Process-based tuning. We demonstrate the trade-off between improved utility from adaptive information usage and the privacy loss incurred by the tuning behavior. The third challenge relates to the DP optimizers in deep learning. DP optimizers requires extra steps to protect the models against privacy attacks, yet come at the expense of substantial performance degradation compared to non-DP optimizers. We present a theoretical analysis of DP-SGD's convergence and reliability and introduce a novel clipping method, "global clipping," based on our analysis.