Learning and Unlearning via Noisy Gradient Descent

Abstract:

The growing threat of privacy attacks that are capable of exfiltrating large portions of training data from machine learning models today necessitates robust privacy protection techniques and certifications. This challenge is further amplified in production settings due to the dynamic nature of constantly changing training data, requiring models to be periodically updated to reflect changes. As full retraining is often prohibitively expensive, efficient privacy-preserving ML algorithms for training and machine unlearning for updates are in high demand.

My research investigates the Noisy Gradient Descent (Noisy-GD) algorithm as a solution towards addressing these needs. Our first contribution is a deep dive into Noisy-GD's training privacy dynamics. We formalize the relationship between noise and gradients, deriving a privacy bound that converges exponentially, a significant improvement over traditional composition bounds that degrade over time. This analysis demonstrates not only tightness but also Noisy-GD's ability to achieve the best possible utility under differential privacy constraints.

Our second focus is on using Noisy-GD for machine unlearning, the process of selectively removing data influence. We expose two fundamental flaws in current machine unlearning definitions that undermine the spirit of the Right to be Forgotten and could lead to privacy breaches. To rectify this, we propose a new, provably sound data deletion guarantee. We thoroughly analyze the complex interplay between differential privacy, deletion privacy, utility, and computational efficiency when using Noisy-GD for unlearning. A key finding highlights that for certain models (convex losses with regularization), Noisy-GD can handle an arbitrary number of deletions while retaining the optimal DP-utility trade-off, all at a fraction of the cost of retraining.

Finally, our third focus is on unifying the various competing notions of differential privacy—(ε,δ)-DP, Rényi DP, and Privacy Loss Distribution (PLD) tail—into a novel interpretation that is suitable for modern privacy analysis. Specifically, we show that these popular notions of DP are primal and dual formulations of each other in terms of Laplace transforms. The Laplace transform expressions of DP provides an elegant framework for reasoning about DP and its properties. To demonstrate the power of this perspective we will discuss a new composition theorem for (ε,δ)-DP that is tight—even in the constants—and improves upon the result of Kairouz et al. (2015), which was previously considered optimal.