The idea of differential privacy is to add noise to the result of a query about a data set, so that the noise masks information about any individual in a data set. The level of noise must be proportional to the maximum impact any individual can have on the result of the query. This sensitivity metric depends entirely on the query, not on the input data.
Determining this maximum impact can be challenging, if not downright intractable. It is therefore useful to design queries in a manner that make it straightforward to determine their sensitivity.
In an ML pipeline, there are multiple stages at which we can insert noise to achieve differential privacy: on the training data, during training, on the trained model, or on the model outputs. Of these, we can probably discard adding noise to the training data since this high-dimensional data would need a lot of noise for masking, and we should avoid adding noise to the weights of the trained model.
Adding noise to outputs is entirely feasible, assuming that we can determine the model's overall sensitivity score. This allows training the model with true data, giving us good convergence and optimal model performance. I'll discuss the issue of multiple queries later.
In contrast, the idea of DP-SGD is that we can inject this noise during the training. During training of a neural network, we know exactly how much influence any individual can have on the model outputs. This influence is characterized as the gradient that will be used for updating the weights. These gradients will typically be very small, especially since they are dampened by the learning rate. Additionally, DP-SGD clamps the gradients to a known interval, giving us hard bounds that we can use to determine sensitivity. Thus, the level of noise required to differential privacy is also very small, allowing us to train a model with potentially slower convergence but still very good overall performance.
Importantly, the DP-SGD approach allows us to show that the trained model itself is differentially private. Nothing we can do with the model will break the differential privacy guarantees, so that its outputs don't need additional noise to achieve differential privacy.
Let's contrast this with adding noise afterwards.
- Determining the sensitivity of the model as a whole is more difficult than determining the sensitivity of gradients. Differential privacy requires us to be pessimistic, meaning that we will likely arrive at looser bounds for the sensitivity, meaning that we will have to add more noise.
- More noise means that the differentially-private query outputs have less value.
- If multiple queries are possible, it is necessary to prevent the distribution of responses from being recovered.
This point about multiple queries is discussed briefly in the linked article about DP-SGD:
However as we’ve discussed earlier, the privacy loss would accumulate every time you queried the model, so you’d have to add noise proportional to the number of queries.
To understand this, let's consider a flawed attempt at adding nose to a true query result in order to achieve some level of privacy:
model = ...
std_deviation = ... # based on model sensitivity + privacy budget
def predict(input):
true_result = model(input)
anonymized_result = noise() * std_deviation + true_result
return anonymized_result
Asking for multiple predictions for the same input might give use an empirical distribution of output values:
frequency
^ =
| =
| = ==
| = ====
| ===============
+------------------> output
It's not difficult to take a guess where in that output space the true output might be. Thus, if repeated queries are allowed, the added noise can be defeated.
There are two categories of approaches for fixing this:
We can re-interpret the query for which we need to determine sensitivity from a single query to a series of queries. Since multiple queries could leak more data, we would need correspondingly more noise for masking. For example, this might spread out the empirical distribution further, providing less information about the true value:
frequency
^
|
|
| ======= ==
| ================
+------------------> output
Unfortunately, adding more noise means making the query outputs less valuable. And as the number of queries grows, the required noise for masking would approach infinity. This could be avoided by enforcing a hard limit on the number of queries, but we'd still require a lot of noise, and this might not be possible in practice (especially when considering that multiple attackers can collude, so this limit cannot be per-attacker, but must be a global limit on the number of all queries ever made).
We can determine noise in a way so that repeated queries will always return the exactly same noisy output, avoiding any additional leakage through repeated queries. For example, we might change our prediction function:
saved_anonymized_results = {}
def predict(input):
if input not in saved_anonymized_results:
true_result = model(input)
saved_anonymized_results[input] = noise() * std_deviation + true_result
return saved_anonymized_results[input]
This would lead to an empirical output distribution like the following, i.e. a delta distribution:
frequency
^ =
| =
| =
| =
| =
+------------------> output
There are still some issues with this.
For example, it might require a substantial amount of storage over the lifetime of the model. This can perhaps be mitigated by using the input as a seed for a random number generator that samples the noise.
More importantly, if similar input values can be expected to have similar output values, then we could still recover the output distribution for an input by sampling nearby inputs (e.g. predict(input + epsilon) for many small but distinct values for epsilon). Note that neural networks generally have exactly this property, since they operate on real numbers and must use differentiable activation functions for efficient training.
All of this illustrates that trying to determine a query's true sensitivity can be quite challenging unless that query is carefully designed. So while we could add noise afterwards to the output of a model, DP-SGD gives us tight bounds on sensitivity, and correspondingly allows us to get by with less noise than some other approaches.
