DP Approach 1: Sufficient Statistics

When the data is centered around zero, the regression parameters become relatively simple: ${\beta }_1=\frac{{\sum }_i{x}_i{y}_i}{{\sum }_i{x}_i^2}$, and ${\beta }_0={\sum }_i{y}_i/n-{\beta }_1{\sum }_i{x}_i$.

The naive approach is to try to add noise directly to ${\beta }_1$, with noise calibrated according to the sensitivity of ${\beta }_1$. This breaks down when you try to derive the sensitivity of the regression coefficient ${\beta }_1$. The sensitivity of ${\beta }_1$ is no smaller than in the case where X’ differs from X by one record:

If all $x_i$ are zero, then the quantity $\frac{{\sum }_i{x}_i{y}_i}{{\sum }_i{x}_i^2}$ is undefined, and therefore so is the sensitivity.

A common approach to avoid the issue of undefined sensitivity is to replace individual point estimates in the formula, and then postprocess to get an estimate of the final statistic.

Denote the DP estimate for $S_{xy}={\sum }_i{x}_i{y}_i$ as ${\tilde{S}}_{xy}$, and similarly for ${\tilde{S}}_{xx}$. These point estimates can be post-processed to approximate ${\beta }_1$:

The sensitivity of ${\tilde{S}}_{xy}$ is now a direct substitution and simplification from the definition of sensitivity.

We first consider the case where one record is added:

This derivation makes use of an assumption that all $x_i$ and $y_i$ are bounded between $[-b,b$]. A similar derivation for the case where one record is removed works out to the same sensitivity, meaning the overall sensitivity is $b^2$. Another similar derivation for $S_{xx}$ results in the same sensitivity in the add/remove model.

Now that you have the sensitivities of each of your point estimates $S_{xy}$ and $S_{xx}$, you can use your knowledge to make DP releases of these quantities with an additive noise mechanism, and post-process these estimates into ${\beta }_1$.

import numpy as np
from opendp.measurements import make_base_laplace
from opendp.mod import enable_features
enable_features("contrib")

def dp_beta1_via_plugin(x, y, b, epsilon):
    x, y = np.clip(x, -b, b), np.clip(y, -b, b)

    # noise scale is multiplied by 2 to account for the composition
    # both dp estimators happen to share the same noise distribution
    laplace_mech = make_base_laplace(scale=2.0 * b ** 2 / epsilon)

    # make the point releases
    dp_Sxy = laplace_mech(sum(x_i * y_i for x_i, y_i in zip(x, y)))
    dp_Sxx = laplace_mech(sum(x_i**2 for x_i in x))

    # post-process
    return dp_Sxy / dp_Sxx

The total privacy expenditure is the basic composition of the privacy expenditure for releasing $S_{xy}$ and the privacy expenditure for releasing $S_{xx}$. Privately estimating unknown quantities in ${\beta }_0$ follows the same routine, making use of prior DP algorithms for individual point estimates, and then performing post-processing.

Multivariate Regression

The concepts behind simple linear regression can be extended for when you have multiple predictors, letting $x_{ij}$ denote the predictors of y. This scenario is called multivariate regression. In this section, you will learn to extend the “plug-in approach” for multivariate regression, and also loosen the assumption that the data is centered around zero.

This time, consider a private dataset consisting of m predictors for y. You would like to solve for $\beta =[{\beta }_0,...{\beta }_m$], such that $\beta ={\mathrm{argmin}}_{\beta }{\sum }_{i=1}^n{({\beta }_i·x_i-y_i)}^2$.

The ordinary least squares solution for estimating a linear regression model is $\beta ={\left(X^{T}X\right)}^{-1}Xy$.

This formula is a generalization of the univariate case above, where X is the design matrix, with two columns:

• a column of ones to estimate the bias term

• the input vector x

Then the quantity $X^{T}X$ is

This statement simplifies, since each value in the resulting matrix can be expressed as a sum:

Recall that the inverse of a 2x2 matrix $\left.\begin{array}{cc}a& b\\ c& d\end{array}\right]$ can be found using the rule

and we can use this statement to calculate the inverse of $X^{T}X$:

To complete the estimator, we need to calculate $Xy$:

Using the previous definitions of $S_y$ and $S_{xy}$, we can express this quantity as

$Xy=\left.\begin{array}{c}{S}_y\\ S_{xy}\end{array}\right]$

This simplifies to:

DP Approach 2: Theil-Sen Estimator

Another approach for estimating DP regression coefficients is via a privatized version of the Theil-Sen estimator. The Theil-Sen estimator first makes a random pairing of each point with another point in the dataset. A slope is computed for each pairing, and the median of this set of slopes is used as the final estimate of the slope.

This algorithm is amenable to differentially private techniques, by breaking it into three pieces

1. a transformation from your dataset to a dataset of pairs

2. a transformation from a dataset of pairs to a vector of slopes

3. a DP median mechanism on the vector of slopes

If you plot the dataset of pairs, it looks like this:

import matplotlib.pyplot as plt
import numpy as np

dataset_size = 20
x = np.random.normal(size=dataset_size)
y = x * np.random.normal(loc=1., scale=0.4, size=dataset_size) + 3
dataset = np.stack([x, y]).T

# Randomly construct pairings
np.random.shuffle(dataset)

# This assumes that dataset size is even:
dataset_of_pairs = np.array(np.array_split(dataset, 2))

for p1, p2 in zip(*dataset_of_pairs):
    slope = (p1[1] - p2[1]) / (p1[0] - p2[0])
    plt.plot([p1[0], p2[0]], [p1[1], p2[1]], label=f"{slope:.2f}")
plt.legend()
plt.show()

The legend shows the corresponding dataset of slopes.

First, consider the stability of a dataset transformation to a dataset of pairs. If an individual may influence at most k records in the input dataset, then in the worst case, the individual may influence up to k pairs.

The transformation from a dataset of pairs to a dataset of slopes is a stable row-by-row transformation. Therefore, it can be argued formally that if an individual can influence at most k records in the input dataset, then the individual can influence at most k slopes.

The final step to estimate ${\beta }_1$ is an application of the DP median mechanism covered previously.

${\beta }_0$ can be estimated with plug-in point estimates and postprocessing, as in Approach 1.

Using Gradient Descent to Learn Parameters

In the previous example, you found the point (x, y) that minimized a function f. In this case, the data points (x, y) were your data - the inputs to your function. A more useful scenario is finding parameters for a function that minimize error relative to a data set. This means that instead of finding a point (x, y) that minimizes a function, you will find the parameters $\alpha$ and $\beta$ that minimize a function f relative to a data set $(x_0,y_0),(x_1,y_1),....,(x_N,y_N)$.

Consider simple linear regression, where you want to learn the best parameters for $f\left(x\right)={\beta }_0+{\beta }_1{x}_1+{\beta }_2{x}_2$. Here, you aren’t minimizing this function itself - you are instead minimizing the function that calculates the error between the regression’s estimation and the observed data. For example, let’s use the Mean Squared Error as a starting point:

$E=\frac{1}{n}{\sum }_{i=0}^n{(y_i-({\beta }_0+{\beta }_1{x}_1^i+{\beta }_2{x}_2^i))}^2$

where $y_i$ is the true observed value.

Since you want to find the best parameters to match the data, you will take the gradient relative to the parameters themselves:

$\frac{\partial E}{\partial {\beta }_0}=\frac{-2}{n}{\sum }_{i=0}^n(y_i-{\beta }_0-{\beta }_1{x}_1^i-{\beta }_2{x}_2^i)$

$\frac{\partial E}{\partial {\beta }_1}=\frac{-2}{n}{\sum }_{i=0}^n{x}_1^i(y_i-{\beta }_0-{\beta }_1{x}_1^i-{\beta }_2{x}_2^i)$

$\frac{\partial E}{\partial {\beta }_2}=\frac{-2}{n}{\sum }_{i=0}^n{x}_2^i(y_i-{\beta }_0-{\beta }_1{x}_1^i-{\beta }_2{x}_2^i)$

Then at each step, you update the parameters ${\beta }_0,{\beta }_1,{\beta }_2$ using the now-familiar gradient descent:

$({\beta }_0,{\beta }_1,{\beta }_2)\to ({\beta }_0,{\beta }_1,{\beta }_2)-\gamma (\frac{\partial E}{\partial {\beta }_0},\frac{\partial E}{\partial {\beta }_1},\frac{\partial E}{\partial {\beta }_2})$

import numpy as np

# Prepare a dataset
ideal_params = [4., 2., -3.]
dataset_size = 100  # assuming known dataset size

data_x = np.random.normal(size=[dataset_size, 2])
data_y = np.hstack([np.ones(dataset_size), data_x]) @ ideal_params

# Discover params via gradient descent
num_steps = 10

params = np.zeros(3)
for _ in range(num_steps):
    instance_level_grads = gradient(data_x, data_y) # n x 2 array
    df_dx = dp_mean(instance_level_grads[:, 0])
    df_dy = dp_mean(instance_level_grads[:, 1])

    params -= gamma * np.array([df_dx, df_dy])

Stochastic Gradient Descent

While gradient descent is a powerful tool for finding the minimum of a function, it has its limitations. Look back to the gradient calculation step in the previous chapter, and note that it requires iterating over the entire data set for each of the parameters. This is only practical for small data sets over a low number of dimensions. Otherwise, the process can become computationally burdensome.

Imagine you are trying to minimize the error over hundreds of parameters and a data set with millions of entries - this would quickly become untenable. For example, a problem with 100 parameters and a data set of 100,000 rows would mean 100 * 100,000 = 10,000,000 calculations to compute the gradient. Further, this step will often be carried out hundreds or thousands of times in order to converge to an approximation of the minimum. Even 100 steps would mean doing 100 * 10,000,000 = 1 billion calculations! We clearly need something more efficient.

Thankfully, there is a technique called stochastic gradient descent, where the gradient is approximated via a random shuffling of the data. Rather than iterate over the entire data set, this algorithm first randomly permutes the data set, then takes a random sampling of the permuted data. Gradient descent is then performed on this random sample, leading to an approximation of the true gradient. Consider the efficiency challenge mentioned in the previous paragraph - if you have a problem with 100 parameters and 100,000 data points, the total number of calculations needed becomes unreasonable. However, if you take a random sample of 1000 data points and approximate the gradient, your total number of calculations drops from 1 billion to (100 parameters) * 1000 (data points) * 100 (iterations) = 10 million, a substantial improvement in speed over regular gradient descent.

When using multiple small subsets of the data (often called batches), the process is called mini batch gradient descent. In mini batch gradient descent, each iteration involves splitting the data set into multiple small subsets and calculating the gradient for each batch. This technique lends itself easily to parallelization - imagine you have 10 minibatches to calculate gradients over. You can have each calculate in parallel, and then average the results together.

Privatizing the Gradient Descent Process

You are already familiar with the DP concepts necessary to privatize the gradient descent algorithm. In this case, you will just be using the DP mean on each component of the gradient to privatize the training process.

The following code snippet does exactly this - for each iteration of gradient descent, it takes the DP mean of the x component and the DP mean of the y component of the gradient. Then, instead of taking a step in the direction of the gradient, it takes a step in the direction of a vector of these DP means. Think of this like taking little random steps to the left and right as you walk down a hill - it will no longer be the fastest route from top to bottom, but predicting your path will be harder for someone trying to follow behind you.

Minimum Viable DP Gradient Descent

This section demonstrates a rudimentary DP gradient descent algorithm. The presentation here focuses on simplicity at the expense of utility. The next chapter will make adjustments to the algorithm that make it practically useful, by increasing the complexity.

Gradient descent iteratively updates each weight (parameter) in the network:

$w_{t+1}=w_t-gra{d}_t·\gamma$

Where $w_t$ is the weight parameter after $t$ steps.

Based on this formula, each of the parameters in models trained with gradient descent can be decomposed into the sum of some initial random value $w_0$ and a set of updates from each training step: $w_t=w_0+{\sum }_t-gra{d}_t·\gamma$. The training process can be made differentially private by replacing each $gra{d}_t$ with $DPgra{d}_t$. This holds because of the closure of privacy guarantees under postprocessing: Since the initial random noise $w_0$ is chosen independently from the data, and each update is a postprocessing of a DP release, then $w_t$ is a postprocessing of multiple private gradient releases. The total privacy expenditure to train $w_t$ is the composition of the privacy losses used to release each $DPgra{d}_t$, for all gradient releases up to $t$.

Now take a closer look at how to compute a single DP gradient. In each training step, the gradient is a dataset transformation from a batch of $k$ sensitive records to a batch of $k$ gradients, where each gradient corresponds to one record. Computing $DPgrad$ is straightforward: compute the DP mean of this batch of gradients using techniques you are already familiar with.

import opendp.prelude as dp
import numpy as np

dp.enable_features("contrib")

data_size = 1_000
x = np.random.normal(loc=0, scale=2, size=data_size)
y = x * 2 + 3

w_slope, w_scale = 0.0, 0.0
learning_rate = 0.01
num_steps = 500

input_space = (
    dp.vector_domain(dp.atom_domain(T=float), size=data_size),
    dp.symmetric_distance(),
)
dp_mean = (
    input_space
    >> dp.t.then_clamp((-1.0, 1.0))
    >> dp.t.then_mean()
    >> dp.m.then_laplace(scale=0.5)
)
per_query_epsilon = dp_mean.map(2)

for i in range(num_steps):
    y_pred = w_slope * x + w_scale
    error = y_pred - y
    w_slope -= learning_rate * dp_mean(2 * x * error)
    w_scale -= learning_rate * dp_mean(2 * error)

print("params:", w_slope, w_scale)
print("total epsilon:", per_query_epsilon * 2 * num_steps)

Unfortunately, implementing this in practice with modern deep learning frameworks is more difficult because they typically do not provide a way to access the gradients corresponding to each individual input (before aggregation). Access to this more granular gradient is necessary for the DP mean because the DP mean needs to clip the gradient before aggregating in order to keep the sensitivity finite. This is one of the motivations for bespoke libraries for differentially private training, like Tensorflow-Privacy and Opacus.

Using PATE to train a differentially private model

The PATE framework is easy to implement and provides differential privacy during inference for any machine learning technique you apply it to. However, there is one significant limitation: each prediction made spends part of the total privacy budget. This means that there is a limit to how many times this model can be used to make predictions.

This problem can be solved by creating a student model that learns from the teacher models predictions. Since the student model is post-processing the differentially private data, the final student model is differentially private, and can be used as many times as desired without affecting the privacy budget.

Let’s assume the availability of a private labelled dataset and a public unlabelled dataset. The student model is trained as follows:

1. Label the public unlabelled dataset utilizing PATE framework, trained on the private labelled dataset.

2. Use the dataset labelled in the previous step to train a student model.

The following diagram shows this process: the public unlabeled data is sent to the teacher models, which generate a DP histogram of labels. From this histogram, a label is added to the data and sent to train the student model.

Figure 7-3. Differentially private learning with PATE framework for classification.

The student model can be deployed to respond to any prediction queries from end users. Most importantly, the private data and teacher models can safely be discarded. Notice that the overall privacy budget is now fixed to a constant value once the student has completed its training. An additional important characteristic of the student model is that an adversary with access to the student’s model weights and parameters could in the worst-case only recover the labels on which the student model was trained. The labels in this case are all differentially private, which is guaranteed by the noisy aggregation mechanism.

In this chapter, you have learned about approaches for building differentially private machine learning models. This often involves modifying existing models, in particular, transforming linear regression and stochastic gradient descent algorithms to be differentially private. Another approach, highlighted in this chapter, is PATE, a general framework for transforming any learning task into a differentially private learning task. On the implementation side, you’ve learned about Opacus as a tool for implementing DP-SGD and PATE.

Now that you are familiar with the basics of DP machine learning, you are ready to learn about the nuances of implementing DP machine learning models in the real world. You will need to take a variety of factors into account during the model training process. In the next chapter, you will learn about budget composition, batching and hyperparameter tuning. The next chapter also provides several code examples for the techniques introduced in this chapter. By the end of next chapter, you will be able to train your own differentially private learning model.