Have it your way: Individualized Privacy Assignment for DP-SGD

Summary

This paper designs variants of differentially private SGD to satisfy different privacy expectations, e.g., users can choose one from high, medium, or low levels of privacy. There are two variants of DP-SGD, one changes the sampling probability of different groups, and the other changes the clipping threshold of different groups.

Strengths

1. The Sample and Scale methods are easy-to-implement. Their design aligns nicely with the fact that DP-SGD adds noise to the aggregated gradient, instead of separate noise for individual gradients. 2. Experiments on several common vision datasets show that individualized DP-SGD is better than DP-SGD with a uniform (the smallest) privacy parameter. The authors also run membership inference attacks to show that groups with smaller privacy parameters do have better empirical privacy. 3. The paper is very well written and easy to follow.

Weaknesses

1. The privacy expectations in the current version are independent of model accuracy. In practice, the minority groups, whose accuracy is usually worse, may prefer stronger privacy than other groups. What would happen if the group with the worst accuracy has the strongest/weakest privacy expectation? One way to implement this is to extend the experiments in Appendix D.2 by assigning a larger/smaller privacy parameter to the class with the worst non-private accuracy. 2. The privacy expectation itself may be data dependent and hence the individualized privacy assignment cannot be made public, as the authors discussed in Line 68 – Line 73. For example, in a medical dataset, users diagnosed with certain diseases may have higher privacy expectations. 3. The authors use a shallow convolutional network for the experiments. It would be better to see whether the results still hold for deep learning models, e.g., ResNets or transformers. 4. The authors only report the average accuracy. It would be better if the authors could show the accuracy of different groups. A recent line of work shows that DP has disparate impact on model accuracy [1]. Will the groups with smaller privacy assignments lose more accuracy? [1]: Differential Privacy Has Disparate Impact on Model Accuracy. https://arxiv.org/abs/1905.12101

Questions

See Weaknesses

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Summary

This paper proposes extensions of the DP-SGD algorithm to support individualized differential privacy (called the IDP-SGD approach). Unlike traditional differential privacy, which imposes a single privacy budget epsilon to all data points, the data points may now have different privacy budgets. Two extensions are proposed. First, the Sample method adjust the sampling rates of data points depending on their privacy budgets. Second, the Scale method adjusts the individual clip norms to effectively add individualized noise. The noise itself cannot be directly individualized due to the DP-SGD algorithm behavior of adding per-batch noise. Experiments show that IDP-SGD outperforms DP-SGD and IPATE in terms of utility and can be complemented with privacy accounting techniques.

Strengths

* Proposes novel extensions of DP-SGD to support individualized privacy. * The Sample and Scale methods are easy to deploy and have theoretical guarantees. * Experiments show that IDP-SGD outperforms baselines (DP-SGD and I-PATE) and can be used with privacy accounting.

Weaknesses

W1) The core contributions of the paper are not contained in the main part of the paper. * The theoretical analysis should be more specific because the proposed individual privacy notion with the extended $\delta$ term is different from previous personalized DP and conventional DP. In the proof of Theorem G.1., the original SGM seems to be about conventional DP and RDP, but the author simply applied it to individual privacy without specific proof about its properties. * The paper shows the algorithm that finds parameters, but it does not provide a way to adapt the parameter to the original DP-SGD. Because DP-SGD uses a single sample rate and a single clip norm, adapting multiple sampling rate and clipping norm is also a new mechanism. It seems that a more specific explanation is needed in terms of implementation. For example, the original DP-SGD assumes Poisson sampling in principle, but approximates it due to computational cost. However, this is possible because the sampling probability is fixed, and it seems necessary to explain how to transform this to satisfy independent sampling. * It is difficult to know the exact process of the algorithm. Algorithm 3 is a very important part of the paper, but it is difficult to understand properly because it is omitted in the main part. W2) It is not clear how theoretically optimal Sample and Scale are. Looking at Table 1, $\epsilon_p$ of Sample and Scale could have a loose bound depending on the $\sigma_{\mathrm{SAMPLE}}$ and $\sigma_p$ values, respectively. It would be helpful to actually see what these values are in the experiments. W3) In Algorithm 1, the paper says that getSampleRate is equivalent to the Opacus function get_noise_multiplier without a detailed description, but the two functions seem to return different objects. The function getSampleRate returns a sample rate, but the Opacus function get_noise_multiplier returns noise_mutiplier $\sigma$. W4) The comparison between Sample and Scale is not clear enough. The two methods are introduced and only empirically compared, and it seems that Sample mostly dominates Scale (according to Table 2). Looking at the overall algorithm, both techniques look similar in terms of efficiency. Then when should one use Scale? W5) Also, a natural approach seems to be combining Sample and Scale where the sampling and clip norms are both adjusted. Why not use this combination? W6) The notion of individualized privacy ($\epsilon_p$, $\delta$)-DP seems to be confused with the original ($\epsilon$, $\delta$)-DP. This confusion leads to other confusions, e.g., whether ($\epsilon_1$, $\delta$)-DP in Theorem 3.1. and ($\epsilon_P$, $\delta$)-DP in Theorem 3.2. mean individual privacy or conventional DP. W7) The experimental setup of only using up to three privacy budgets seems limiting. What happens if there are many more than three budgets? W8) Some reference number is wrong. For example, in the last paragraph of the proof of Theorem G.1, Mironov et al. is [21] or [22], not [20].

Questions

Q1) What is the actual name of ({$\epsilon_1$,...,$\epsilon_n$}, $\delta$)-DP and ($\epsilon_p$, $\delta$)-DP? Are they Individualized Privacy or something else? If they are Individualized Privacy, why did the authors change the term “Personalized DP” to “Individualized Privacy” even though you referred to the Personalized DP paper? Q2) How can getSampleRate function be equivalent to the function get_noise_multiplier in Opacus? getSampleRate seems to return sample rate with input argument noise multiplier, while get_noise_multiplier returns noise_multiplier sigma. Q3) The comparison between DP-SGD and the proposed algorithms is as expected because DP-SGD assumes the same privacy level over all data points. Are there any results related to computational cost? Q4) A detailed description of the properties of each Sample and Scale is lacking. Sample seems to be superior overall in performance. Is there any reason to introduce the Scale technique? Or, what are the advantages of the Scale method compared to the Sample method? Q5) What is Thm. 4 and Thm. 11 from Mironov et al. [21] in the proof of Theorem G.1.? I could only find Proposition and Lemma in the paper. Did you mean [22]? Q6) How can you simply prove Theorem G.1. and Theorem G.2. without proving some basic theorems or properties of newly designed privacy notion? I don't think previous DP techniques can be applied to individual privacy directly. The authors just directly use the conversion technique from RDP to ($\epsilon$,$\delta$)-DP of previous works as a technique for the individual privacy conversion even though the privacy notion is new.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors discuss limitations.

Summary

This paper proposed two variants of DP-SGD by manipulating the sampling rate and the gradient clipping bound for different groups to achieve the goal of having different privacy budgets for those groups and improving the overall performance of DP-SGD. The authors proved theoretical privacy guarantees for both variants. They also conducted an extensive experimental evaluation to showcase the advantage of their methods in many aspects.

Strengths

1. The authors considered an important problem, having different privacy budgets for different groups of people to boost the overall utility, and proposed two algorithms to achieve the goal. The privacy guarantee of the algorithms is proved. Both algorithms are easy to implement and look novel although intuitive to me. 2. The experiments in this paper are adequate for the evaluation of the proposed methods. The results are well-organized and visualized, which supports the validity and the advantage of the methods, and the details are provided enough for reproducibility. I understand and appreciate that the authors put most of the valuable experimental results in the appendix due to the page limitation. 3. The writing and the organization of the content are good.

Weaknesses

1. The composition theorem for Algorithms 1 and 2 is not proved or discussed in this paper. The proofs of Theorem G.1 and G.2 look okay to me although I think more explanations would make it more friendly to the general audience. However, I think there is still a need to show the composition theorem similar to the results in Feldman and Zrnic [9]. Moreover, if it is not much work for rewriting related parts of the paper, I think a more strict way to account for the privacy budget usage is by the Rényi Filter [9], i.e., individual RDP instead of RDP. 2. Section 4.2 uses membership inference to empirically verify the privacy protection for the claimed DP guarantee, but the results in Figure 2 do not explicitly show the protection separately for each group ($\varepsilon=10$ and $\varepsilon=20$) compared with the DP guarantee. The authors may show the curves under two additional settings: vanilla DP-SGD with $\varepsilon=10$, and vanilla DP-SGD with $\varepsilon=20$. Then compare the two solid curves in Figure 2 with the two additional curves respectively. 3. Both Algorithms 1 and 2 will potentially change the objective function of SGD (although DP-SGD with the gradient clipping has already changed it). There is no discussion on how specific choices of privacy budget distribution will affect the convergence and final performance of the optimization. This is important since it is related to the privacy-utility tradeoff. Please see my comment in *Limitations*. Minor weaknesses: 1. Line 66. I think Table 7 is the same as Table 2 which is in the main text, not the appendix. 2. Line 86. $\log 1/\delta$ -> $\log(1/\delta)$ 3. Line 98, equation (2). The inequality holds with many constraints on $\alpha$. See Theorem 11 in Mironov et al. [21] 4. Algorithm 1. The authors wrote: it is equivalent to Opacus' function get_noise_multiplier while Algorithm 2 is also equivalent to the same function. I think there is a typo. 5. Algorithm 1, Line 5. I think this is more like a grid search which always decreases $\sigma_{\mathrm{sample}}$, while a binary search would be better. 6. Line 209. The notation $\stackrel{\text{!}}{=}$ is not defined. 7. Line 767 in Section G.2. $\sum_{L\subset D}$ -> $\sum_{L\subset D'}$ --- I have read the rebuttal which addressed my questions and the weakness concerns.

Questions

1. In Line 379, could you explain the meaning of 'batch gradient descent'? Is it different from SGD? If yes, maybe it can be replaced with the word 'full-batch gradient descent' or just 'gradient descent'. 2. In Table 8, we can see that for the first two rows, the accuracy decreases for classes 1-9 with a higher privacy budget of class 0 compared with the results with the same privacy budget of class 0. The same phenomenon exists in other rows. Intuitively, the higher budget of other classes should provide more information for the classifier so that the accuracy for each group would increase. Could you provide more insight into why this intuition is incorrect under this setting?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

1. The discussion of the incentive and consequence of people choosing weak privacy protection is not enough in the main text. I found the content in Section D.2 very interesting since it aligned with my intuition: the more privacy being sacrificed, the better utility could potentially be obtained. Also, the results in Table 8 show that having a group with a higher privacy budget will affect the utility of other groups, which could lead to problems like the Prisoner's dilemma where people in the dataset have to give a higher privacy budget in order to maintain their original utility given the fact that other people are willing to have a higher privacy budget.

Summary

This paper proposes two variants of Differentially Private Stochastic Gradient Descent (DP-SGD) to train machine learning models that satisfy approximate personalized differential privacy (PDP), following the definition of Jorgensen et al. [15]. In contrast to vanilla DP-SGD where all points in the training dataset are assigned a global, uniform privacy budget $\varepsilon$, the authors consider a scenario where points are split into privacy groups $\{\mathcal{G}_1,\ldots,\mathcal{G}_P\}$ and each group $\mathcal{G}_p$ is assigned a different privacy budget $\varepsilon_p$. This allows individuals who contribute training data to specify their privacy preferences, reflecting the variety of privacy attitudes among users observed in past surveys. To achieve PDP the paper modifies DP-SGD in one of two ways: 1. **Sample** method: adjusting the sampling rate used to construct mini-batches, so that points in groups with a higher privacy budget are sampled more often than points in groups with lower privacy budget (and thus, stringent privacy preference). 2. **Scale** method: adjusting the noise multiplier to scale the variance of noise added in a per-point basis. Rather than doing this directly, which would be inefficient, the method achieves the same effect indirectly by scaling the clipping norm of per-point gradients. These modifications are such that given target group privacy budgets and a number of training steps, the mini-batch noise multiplier in DP-SGD can be chosen so that the privacy budget for each group is exhausted at the end of training, maximizing utility. The paper evaluates **Scale** and **Sample** on CNNs trained over MNIST, SVHN and CIFAR-10 using 3 privacy groups with budgets $\varepsilon_p = p$ for $p \in \lbrace1,2,3\rbrace$, distributing points into groups according to proportions used in prior work. This evaluation shows top-1 accuracy improvements ranging between 1-5% over vanilla DP-SGD with a uniform privacy budget $\varepsilon_1 = 1$ (which guarantees PDP, but underutilizes the budget for the other two groups). The methods also compare favorably to Individualized PATE [5], which uses different techniques but achieves the same privacy guarantee. The paper also demonstrates that the empirical evaluation of membership inference attacks against models trained with PDP using the above two methods shows the expected gap between groups with different privacy budgets. Finally, the authors discuss how to combine individual privacy assignment with individual privacy accounting as done by Feldman and Zrnic [10] for batch gradient descent. The supplemental material provides implementations of **Scale** and **Sample** in the Opacus library as well as scripts to reproduce the results in the paper.

Strengths

1. **First DP-SGD variants designed to achieve personalized differential privacy** There is abundant literature for adapting differentially private mechanisms for general data analysis to achieve personalized differential privacy as well as for computing personalized differential privacy guarantees for training data points in ML models. While PDP accounting alone can be used to improve model utility modestly (see Feldman and Zrnic [10]), as far as I know the only other method that trains models with individual privacy assignments is Individualized PATE [5] which uses significantly different techniques. 2. **Original combination of existing mechanisms** The **Sample** mechanism is inspired by the "Sampling" mechanism of Jorgensen et al. [16], while **Scale** is inspired by the "stretching" mechanism of Alaggan et al. [2]. Combining these mechanisms with DP-SGD is relatively straightforward, but has not been done before. 3. **Problem is well motivated and solution is contextualized relative to prior work** The authors discuss related work up front, explain how their solution fits into the existing literature, and justify their contributions. 4. **Complete algorithmic descriptions of proposed methods** The paper describes the adaptations of DP-SGD in sufficient detail, including pseudocode and justifications for design decisions. 5. **Demonstrates utility gains compared to alternative solutions** The empirical evaluation on image classification tasks demonstrates a modest utility gain compared to alternative baselines. 6. **Comprehensive supplemental material** The Appendix includes valuable additional discussions. The accompanying code is a significant extension to an existing library and demonstrates the practicality of the techniques.

Weaknesses

1. **Limited empirical evaluation** The empirical evaluation is limited to convolutional architectures trained from scratch for image classification. It is unclear how the paper findings hold for other architectures, modalities, tasks, or practically relevant scenarios, such as fine-tuning. 2. **Modest utility gains** The utility gains with respect to vanilla DP-SGD are modest (1-5%). The comparison to alternative baselines with simpler implementations in Appendix E shows even more modest gains. For instance, simply training sequentially on each group separately using DP-SGD achieves accuracies only 0.3-0.41% below the best of **Sample** and **Scale** (see Table 12). It is unclear to what extent these differences are statistically significant, whether comparable effort has been put in hyperparameter tuning, and whether mild modifications to this alternative baseline could outperform **Sample** and **Scale**. 3. **Unsupported claims about the confidentiality of privacy preferences** The authors argue that privacy preferences (i.e., per-group privacy budgets) should be kept private and claim that their modifications of DP-SGD do not leak information about privacy preferences because untrusted parties only interact with the final trained model. This claim is unsupported by proof (compare this to Allagan et al. [2], which prove a similar guarantee explicitly) and is made with respect to a different adversary model than the privacy guarantees of training data in DP-SGD, which consider adversaries that observe noisy gradients released at every training iteration, not only the final model. ## Minor comments - Given the number of references to numbered lines in Algorithm 3, it would be convenient to include the listing in the body of the paper. - l.76: "[D]iffer in any one record" is ambiguous. Consider making clear that you use the add/remove neighboring relation. That is, $D,D'$ are adjacent if $D = D' \cup \{x\}$ for some record $x$, or vice versa. - l.79: "DP bounds privacy leakage for any individual". This is only true under the assumption that an individual contributes at most one record. - l.86: The original conversion from $(\alpha, \rho)$-RDP to $(\varepsilon, \delta)$-DP of Mironov [21] is suboptimal. Balle et al. [A, Theorem 21] provide a tighter conversion (which is the one Opacus uses). - Table 1: $\sigma_{\rm SAMPLE}$ should read $\sigma_{\rm sample}$. - Algorithm 1: Missing inputs: scaling factor $s_i$, target sample rate $q$. - Algorithm 1: In l.1, you could initialize $\sigma$ using $\textit{getNoise}$ as $\sigma \gets \textit{getNoise}(\varepsilon_1, \delta, q, I)$. - Algorithm 1: In l.4 $G_p$ should read $\mathcal{G}_p$. - l.190: "our Sample [method]" - l.209: While I have seen it being used before, I think that the notation $\stackrel{!}{=}$ is far from being conventional. - l.215: "[W]e still require the expected average sampling rate to remain $q$ to obtain constant mini-batch size $B$". As you said just before, the mini-batch size isn't constant, $B$ is the **expected** size. Rather, you want the expected mini-batch size in IDP-SGD to be the same as in vanilla DP-SGD with sampling rate $q$. - l.225: There's an extra closing parenthesis. - l.232: DPSGD should read DP-SGD. - l.260: Use \{$\sigma_1,\ldots,\sigma_P$\} rather than $\sigma_p$-s. - l.313 (and subsequently): "Lira" should read "LiRA" - Numbers in bibliographic references are shifted between the paper and the full paper (with Appendix) provided as supplemental material. - Appendix, Algorithm 3: In line 11, $\theta_T$ should be $\theta_I$. - l.566: $\sigma_{\rm in}$, $\sigma_{\rm out}$ should read $\sigma^2_{\rm in}$, $\sigma^2_{\rm out}$, respectively. - l.576: "Line 3 in Algorithm 3" should be "Line 8 in Algorithm 3" - l.591-596: $G_p$ should read $\mathcal{G}_p$. - l.691: "Appendix E.3" should read "Table 12" - Table 10: How can it be that you get a statistically significant negative $\Delta$ for one of the models? That would reverse the relation between the two privacy groups.

Questions

1. **Confidentiality of privacy budgets** The paper argues that IDP-SGD preserves the confidentiality of group privacy preferences, at least against parties that only interact with the final trained model. However, intuitively, models trained with a uniform privacy budget of $\varepsilon=1$ and models trained on the same data but increasing the privacy budget for a single group from $\varepsilon=0.1$ to $\varepsilon=100$ will likely perform noticeably different on that group. Can you provide a proof that IDP-SGD satisfies some form of confidentiality for privacy preferences that makes explicit the adversary model and assumptions? 2. **LiRA AUC scores** Carlini et al. [6] report LiRA results on models trained with DP-SGD and $\epsilon = 8$ (not far from one your choices of $\epsilon = 10$), with a significantly lower AUC score of 0.503 compared to the score of 0.537 that you report. Even for $\varepsilon > 5000$, their best result has a lower AUC score of 0.527. Could you explain this difference?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately address societal impact but only some limitations. A paragraph at the end of the introduction discusses the need for openly communicating privacy risks and regulatory supervision. This points to Appendix A, which discusses broader impacts in the light of prior studies and some limitations: evaluation on standard benchmarks with simulated privacy preference distributions; practical impact measured via membership inference attacks only. I think that the limited nature of the evaluation on CNN models trained from scratch on visual tasks should also be brought up front, as the results might differ in other settings.

Sharing Additional Results Regarding the Combination of Sample and Scale

To further illustrate how we addressed the point about combining our Sample and Scale methods, we implemented the combination that we described in the rebuttal. We allow to weight the different methods to arbitrary fractions (e.g., 50% Sample, 50% Scale), and derive the privacy parameters such that all privacy groups exhaust their respective budgets at the end of the specified number of iterations. We ran additional experiments to showcase the advantage of combining both methods. We used the MNIST dataset and the first privacy setup (0.34, 0.43, 0.23) with privacy budgets {1,2,3} and weighted our methods as indicated in the table below. | Sample (weight in %) | Scale (weight in %) | Test Accuracy (in %) | |------------|-----------|---------------| | 0 | 100 | 97.78+-0.08 | | 25 | 75 | 97.75+-0.10 | | 50 | 50 | 97.80+-0.10 | | 75 | 25 | 97.80+-0.10 | | 100 | 0 | 97.81+-0.09 | The baseline (first and last rows) are taken from Table 2 in the original submission, while the additional three rows in between with the new results represent average test accuracy and the standard deviation over ten independent random runs over different weights (w) assigned to the respective method.. Our results demonstrate a clear progression from the lower performing Scale approach to the better performing Sample. This aligns with expectations based on our implementation, where we combine the methods based on the parameters found for them sequentially. Note that each of our methods has its advantages and disadvantages and the combination of both methods provides more options to balance (dis)advantages. For example, when some points’ sample rates are extremely small, then the model might never see those points during training and the combined method could reduce this possibility while still improving over the Scale-only method.

Thank you for the response!

W1. Now I understand the composition results in this paper. W2. This table looks good to me. W3. Yes. I understand the difficulty here. My concern is more about the characterization of the utility loss for groups with lower privacy budgets. If the convergence (e.g., the decrease of train loss) is slower for the groups with lower privacy budget, then DP-SGD may need a longer time to converge which also affects the choice of the number of iterations of SGD. I understand that this may be out of the scope of this paper but still raises my concern. Based on your explanation for W1, I have increased my score from 5 to 6.