Data Deletion for Linear Regression with Noisy SGD

Assume we are working on two different datasets: $D_{0}$, referred to as the original dataset, and $D_{1}$, known as the deleted dataset. Our goal is to find a point $v^{*}\in D_{0}$, which is called the perfect deleted point, such that the deletion of it will cause the minimum change on the final model, i.e., the distribution of model weights resulted from deleting $v^{*}$ is identical to the one when not deleting it, compared with all the other points.

However, it can be difficult and inefficient to directly find the perfect deleted point. Intuitively, for each data point $v_{i}\in D_{0}$, we need to delete it from the original dataset $D_{0}$ and use the deleted dataset $D_{0}\setminus v_{i}$ to train a new ML model. Among all the $n$ models we get from deleting each $v_{i}$, we want to find the data point $v^{*}\in D_{0}$ such that using the deleted dataset $D_{1}=D_{0}\setminus v^{*}$, we will obtain the most similar model, i.e., model weights, to the one trained with the original dataset $D_{0}$, compared with deleting all the other $n-1$ data points. We would need to repeat the same deleting-and-training process for $n$ times if we want to directly find the perfect deleted point, which is unnecessary as we propose an alternative approach in this paper that doesn’t require any additional deleting-and-training at all. We will discuss it in Section 4.2 in detail.

We are motivated to find the perfect deleted point because previous studies have shown that despite improvement of training performance using a larger training dataset (Ramezan et al., 2021; Foody et al., 2006), too much training data can cause overfitting if the model becomes too complex and learns noise or irrelevant patterns rather than generalizing well (Ying, 2019; Hawkins, 2004). Also, it will be more computationally-friendly and data-efficient if using a smaller training dataset (Acun et al., 2021; Zhu et al., 2016).

In this paper, we propose a novel method for finding the perfect deleted point with the following assumptions:

1. 1.

   The original dataset $D_{0}$ contains finitely many data points, i.e., $n$ is a positive integer that is not infinity.

2. 2.

   We are considering the classical linear regression task, i.e., point $v_{i}=(x_{i},y_{i})\in D_{0}$ where $x_{i}$ is the feature vector and $y_{i}$ is the label of corresponding $x_{i}$. Thus, the loss function of point $v_{i}$ for a ML model with model weights $w$ is

   $$l(w,v_{i})=(y_{i}-\langle w,x_{i}\rangle)^{2}.$$

   (3)

   The empirical risk given model weight being $w$ and dataset $D=\{(x_{i},y_{i})\}_{i=1}^{n}$ is defined as

   $$L(w;D)=\frac{1}{n}\sum_{i=1}^{n}l(w;(x_{i},y_{i})),$$

   (4)

   which evaluates the discrepancy between predicted outcomes and true outcomes of the whole dataset. The mean is taken over all individual losses here because it’s a common approach to use mean gradient in noisy SGD defined below.

3. 3.

   The ML model uses noisy gradient descent to minimize the empirical risk defined in equation (4) and update its weights in each step, i.e.,

   $$w_{1}=w_{0}-\gamma(\nabla L(w;D)+\eta)$$

   (5)

   where $\eta=N(0,\sigma^{2}I)$ is the Gaussian noise and $w_{0},w_{1}$ are model weights before and after noisy gradient descent respectively. Note we only consider one step of noisy gradient descent in this paper.

With the linear regression setting in Section 3.2, we first formally define how we can obtain the deleted dataset from the original dataset.

Given Definition 4 and equation (4), we next define the empirical risk and gradient for original and deleted dataset respectively.

Lemma 2 describes a basic relationship of original gradient and deleted gradient.

Since we only consider one step of noisy gradient update here and the initial weight $w_{0}$ doesn’t change whether or not we delete $v$, from equation (5) we know that in order to get similar model weights $w_{1}$ for original dataset $D_{0}$ and deleted dataset $D_{1}$, we need $\Delta w=w_{1}-w_{0}$ to be similar, i.e., have identical probability distributions. Equivalently, it means TNR and FNR considering the distributions of $D_{0}$ and $D_{1}$ should be close to each other, i.e., membership advantage of our perfect deleted point $v^{*}$ should be close to 0.

From Lemma 3, we notice that the absolute membership advantage depends on Type I error $\alpha$ and signal-to-noise ratio $d_{v}$, and Type I error $\alpha$, which by definition is the false positive rate (FPR), i.e., the probability of rejecting null hypothesis when it’s actually true, is therefore equivalent to our manually-picked significance level. So next we try to give an explicit formula for how to calculate signal-to-noise ratio $d_{v}$ by applying Lemma 2 to help us find the perfect deleted point.

From Lemma 3 and 4, we know we need to find data point $v$ such that $d_{v}$ calculated from it using equation (8) will minimize the absolute membership advantage $|Adv(v)|$. By simple calculation, we know $d_{v}$ should be close to $\Phi^{-1}(1-\alpha)-\Phi^{-1}(\alpha)=2\Phi^{-1}(1-\alpha)$ so that $|Adv(v)|$ will be minimized, i.e., close to 0. Therefore, the perfect deleted point problem can be reformulated as: we want to find point $v^{*}\in D_{0}$ such that

$v^{*}=\mathop{\arg\min}\limits_{v\in D_{0}}|d_{v}-2\Phi^{-1}(1-\alpha)|$

Next we formally propose Algorithm 1 to find the perfect deleted point in the original dataset $D_{0}$. To find the perfect deleted point, we need to first obtain signal-to-noise ratio $d_{v}$ for each data point $v\in D_{0}$ by applying Lemma 4. Then by Lemma 3, we choose a significance level and use it as the Type I error $\alpha$. Finally for each data point $v$, we compare the distance between $d_{v}$ and $2\Phi^{-1}(1-\alpha)$, and the one with the smallest distance gives the perfect deleted point $v^{*}$. Note we introduce a hyper-parameter $\delta$ here to quantify the tolerance we can have for the largest acceptable distance, i.e., if the smallest distance $|d_{v}-2\Phi^{-1}(1-\alpha)|$ for all $v\in D_{0}$ is bigger than $\delta$, then we say there’s no perfect deleted point in the dataset. So now instead of directly training $n$ models separately using deleted datasets and comparing their model weights to the original model weights for each data point, our approach only needs to compute signal-to-noise ratio $d_{v}$ and compares its value to $2\Phi^{-1}(1-\alpha)$ for all data points in one training step, which only takes $O(n)$ time and $O(n)$ space for one step of noisy SGD training, where $n$ is the size of the original dataset. Thus our approach for finding the perfect deleted point is more time and space efficient than the direct approach.

In order to understand how perfect deleted point will affect the training performance, we first propose the following concept of absolute membership error that quantifies how different a point $v$ is from being the perfect deleted point.

Based on this definition, absolute membership error of the perfect deleted point $\epsilon_{v^{*}}$ should be close to 0 by analysis in Section 4.2. From now on, we denote $\epsilon_{v^{*}}$ by $\epsilon^{*}$ for brevity. We propose the following Lemma to bound the change of training loss for deleting point $v$.

The novel part of Lemma 5 is that given several candidates for the perfect deleted point, i.e., they all give very similar $d_{v}$, the one with the smallest $l_{2}$ feature norm, i.e., $||x_{v}||_{2}$, is always better because the lower bound of change of training loss is decreased if we decrease $||x_{v}||_{2}$. The upper bound is also decreased if we decrease $||x_{v}||_{2}$ because individual loss $l(w;v)$ is non-negative, meaning the part after $\frac{1}{n-1}L(w;D_{0})$, which is $-\frac{1}{n-1}l(w;v)$, is therefore negative. So decreasing the denominator $||x_{v}||_{2}$ will decrease the upper bound as well. In other words, deleting the one with the smallest $l_{2}$ feature norm will improve training performance the most potentially because it has smaller both lower and upper bound for increment of empirical risk.

Also, given the same training dataset, i.e., same $B$, the perfect deleted point gives the tightest bound for change of loss after deletion compared with other points because $\epsilon^{*}\leq\epsilon_{v}$. In other words, we can have an accurate estimate of how the perfect deleted point will affect training performance by setting $\epsilon^{*}=0$ before even finding the exact perfect deleted point.

In this section, we try to understand how the perfect deleted point will bring about privacy issues in the training process.

From Lemma 6, we observe that assume privacy budget must be non-negative, then as long as the absolute membership error $\epsilon_{v}$ is non-negative, it can achieve the smallest lower bound $0$ for privacy budget. In other words, if we have several candidates for the perfect deleted point, i.e., they all give very similar $d_{v}$, then the one with positive absolute membership error will be considered as the best option for the perfect deleted point because it may potentially distort privacy guarantees to the minimum degree compared with deleting other points. Note we don’t know exactly whether it’ll cause the smallest privacy budget because we only know it can achieve the smallest lower bound for privacy budget, so only theoretically can it lead to a smaller privacy budget.

To better visualize how the perfect deleted point will affect the model weights, we generate a 2D synthetic dataset with 200 samples in this case as the original dataset $D_{0}$, where the $x$ coordinate of all these points is randomly picked within the range $[0,10]$ with seed $40$. To get the $y$ coordinate, we assume the true model behind our generated dataset is $y=3.1415926535x$ since we are dealing with classic linear regression here. Then we use Gaussian noise with mean $0$ and standard deviation $2$, amplifies its magnitude by $10$, and add it to the true $y$ coordinate to generate the synthetic $y$ coordinate. The scatterplot of our generated dataset looks like Figure 1. Although this is a simple dataset that may not mimic the real world dataset, it suffices to analyze the perfect deleted point problem on it in this paper as it satisfies all the assumptions in the given linear regression scenario.

The hyperparameters we used in this experiment are listed here: initial weight $w_{0}=0$, learning rate $\gamma=0.01$, Gaussian noise $\eta=N(0,4)$, Type I error $\alpha=0.01$, and tolerance $\delta=100$. Since this is a stochastic algorithm and we want to get the distribution of weights, we run the 1-step noisy SGD for 100 iterations to understand the overall behaviour of it.

To understand the effect of perfect deleted point, we first focus on the distribution of model weights after deleting it and compare it with the distribution of model weights when we don’t delete any point. We use the distribution of model weights when we randomly delete a data point as a benchmark to better demonstrate the potential of perfect deleted point compared with all the other points. Secondly, we repeat the same finding-and-deleting process for multiple steps of noisy SGD to augment the effect of the perfect deleted point as deletion of one data point may not affect much compared with no deletion and random deletion because of the size of original dataset $D_{0}$ mitigates the impact.

Figure 2 and Table 1 demonstrate the distribution of model weights in different cases both visually and statistically. From the first row Figure 2, we see in one step of noisy SGD, all three cases demonstrate a similar normal distribution, which is proved by the mean and variance of the first three lines in Table 1. It is because the deletion of a single data point in $D_{0}$ which contains 200 samples only posts a trivial effect on the distribution of model weights. From the next two rows of Figure 2, we see that as the number of noisy SGD steps increases, the weight distribution of perfect deleted point resembles much more closely to no deleted point compared with random deleted point. This means that our perfect deleted point is indeed “perfect” in the sense of preserving model weight after deletion compared with other points. When we look at the highlighted numbers in the third column of Table 1, we can see that as number of noisy SGD steps increases, the variance of distribution of model weights using random deleted point grows larger, which means the normal distribution becomes ”flatter” and we are more likely to get random weights after more random deletion. But by the convergence of noisy SGD, we know this is not acceptable, which again shows the advantage of perfect deleted point.

However, if we look at the highlighted number in the second column of Table 1, we see that despite having small variance, the mean of distribution of model weights after 50 steps using perfect deleted point shifts tremendously compared with both no and random deleted point, which gives a slightly different model weight distribution compared with no deleted point. To address this problem, we increase the Type I error $\alpha$ to 0.05, and Figure 3 plots the corresponding result.

As we can see, the mean becomes much smaller and the whole distribution is therefore much similar to the one with no deleted point. An intuitive explanation behind it may be that as we increase Type I error $\alpha$, we increase significance level as well, which allows us more room to make mistakes using perfect deleted point in many steps of noisy SGD, i.e., deleting more points, thus improving statistical power of our perfect deleted point. This trade-off between $\alpha$ and mean may lead to potential future work and needs more rigorous investigation.