How can we gauge how good a machine unlearning algorithm is?
Using differential privacy to construct a gauge meter for machine unlearning.
Machine unlearning addresses the concept of removing undesirable behaviors from a model without retraining it from scratch. This has far reaching impacts, spanning from computation cost reduction to reduced training time. Ideally, the time taken to unlearn should be less than the time taken to retrain, which makes the cost savings scale linearly with the size of the model.
Unlearning, as a function, works by taking the trained model, as well as the data that contains the undesirable qualities (bad data) and outputs a model that has little to no information about the aforementioned bad data. However, to ascertain the ‘goodness’ of our machine unlearning algorithm, we need to come up with a guarantee would tell us by how much our unlearned model varies from the gold standard i.e. a model trained from scratch without the data we are tying to forget- (lets label the data -U).
Empirically, the naïve yet natural baseline of unlearning, where we retrain the model from scratch, gives us the best possible unlearned model i.e. it can be said to have never before “seen” U and is therefore, not likely to generalize well on it, moreover it is unlikely expose any information about U to an attacker who has access to the model weights (Whitebox attack) or model outputs (Blackbox attack).
Consequently, to determine how good any unlearning algorithm (A’ ) is, we compare the unlearned model from the algorithm A’ to a retrained model through an equation inspired by the definition of differential privacy.
Differential privacy, proposed by Dwork & Roth (2006), requires that given two datasets, X and X’ -that only differ in one user’s data-, for a randomized algorithm M that takes in a dataset and outputs some information, S, about the dataset, the output of M should not change drastically when X is swapped for X’ or vice versa. Instead, we should have roughly the same probability of observing the same output S, whether the input dataset is X or X’ so as preserve the privacy of the omitted individual’s data.
The above statement is formalized by the following equation:
Where ε > 0 and δ ∈ (0, 1) quantify the privacy guarantee. Ideally the smaller values, the better the privacy; meaning the more (ε, δ) are small, the more S on either side of the equation become more equal. Intuitively, an algorithm M being (ε, δ)-Differentially private means that its output does not reveal much about any particular user’s data.
For a more comprehensive understanding of differential privacy, please read the full paper here.
Hence, the guarantee we use for evaluating any unlearning algorithm borrows heavily from the above differentially private equation with few variations:
- Instead of looking at the differences in probability of the extracted information, S, we look at the probability of the distribution of model weights(W), of the unlearned and retrained model to be similar, or the distribution of the model outputs of both the former and latter to be similar.
- Instead of the randomized algorithm M, being constant and the dataset (X,X’) swapped, we hold the dataset (S) constant and swap out the algorithms(unlearning, retraining) but other parts of the equation stay the same with some small additions.
Therefore, any algorithm is (ε, δ) -unlearning algorithm if :
Where, ideally, the probability of the distribution of weights(W) of a model from the unlearning algorithm is closer to/similar to the distribution of the weights of a retrained model.
To intuitively explain the equation, the first part of the equation where unlearning happens:
- A(S) is a (randomized) learning algorithm which, given a dataset S , outputs original model parameters A: S → W
- A’ is an unlearning algorithm that takes in unlearning requests U ⊆ S, and the learned model A(S) as well as some statistics about the original dataset T(S)- which could be available or not- to output the unlearned model parameters W’.
In the second part, we equate the retraining process as:
where:
- A(S\U) is an algorithm that receives the dataset where the data to be unlearned is removed. S is the whole dataset, U ,the datapoints we want to remove, thus (S\U) represents the datapoints we want to retain.
- A’ then receives an empty set of unlearning requests ∅ instead of U, since those have already been removed from the training data, as well as the retrained model, and additional statistics T about the dataset (S\U)
ε > 0 and δ ∈ (0, 1) quantify the unlearning guarantee. Ideally the smaller the values, the better the unlearning algorithm, because intuitively, the closer the distributions of the unlearning and retraining equation are, the smaller the values of (ε, δ).
We can then use the values (ε, δ), to determine how good our unlearning algorithm is. Smaller values would indicate a better algorithm as the output would be closer to the retrained model, while larger values would indicate a worse algorithm
In conclusion, differential privacy proposes a guarantee that helps to provide a lower bound for machine unlearning. It is important differentiate, however, the role of differential privacy in machine learning which is entirely different and of which is not in the scope of what this article covers. Till next time, cheers.
References:
[1] Dwork C. , Differential privacy. In International colloquium on automata, languages, and programming (2006), https://www.cis.upenn.edu/
[2] Sekhari, A., Acharya, J., Kamath, G., & Suresh, A. T. , Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing, (2021), arXiv
[3] Huang, Y., & Canonne, C. L., Tight Bounds for Machine Unlearning via Differential Privacy, (2023), arXiv preprint arXiv:2309.00886.
[4] Aitsam, M. , Differential privacy made easy. (2022), In 2022 International Conference on Emerging Trends in Electrical, Control, and Telecommunication Engineering (ETECTE) (pp. 1–7). IEEE.
