Data Value Estimation on Private Gradients

Response Part (1/2)

Dear reviewer hHZY,

We sincerely thank you for taking time to provide your review and for acknowledging the motivation of our work and its contribution to formalizing differentially private data valuation through uncertainty.

We would like to address your concerns in the following.

---

1. Empirical Results

The empirical results only feature a handful of datapoints on 2 relatively simple benchmark datasets (ML evaluation), V being deterministic and model parameters fixed etc. I would like to see more a) utility functions covered, b) larger dataset sizes and c) range of epsilon values.

Thank you for your suggestions. We wish to clarify that our experimental results include several datasets, including Covertype, Brease cancer, Diabetes, CIFAR-10, and MNIST. These datasets are commonly used in related works, e.g. [1,2,3,4] in your reference. We evaluated both continuous utility functions (negative loss) and discrete ones (accuracy) across various models, including logistic regression, CNNs, and ResNet18, as detailed in Figure 3. For models, we consider a variety of model families including logistic regression, CNN, and ResNet18, which are also considered in [1,2,3,4].

Regarding a broader range of $\epsilon$ values, we included additional results in Appendix D.5, showing that for $\epsilon \geq 1$, our method achieves significant improvements in data value estimates, while for $\epsilon=0.1$, performance deteriorates as expected in the high-privacy regime.

Following your suggestion, we have conducted an additional experiment using a multi-layered perceptron (MLP), which we present in the following subsection.

---

2. Comparison with different Clipping Norms

You may consider adding another baseline model to discuss the comparative utility loss of clipping vs noise.

Thank you for suggesting the additional experimental setting. We have conducted an experiment using a custom 2-layered MLP with ReLU activation to test the performance as we gradually increase the clipping norm $C$ while fixing $\epsilon=1$. For other parameters, we use $k=400$, $n=100$, $q=0.5$.

From the experimental results, we observe that for both naive DP-SGD and our method, the data value estimates become less accurate as $C$ increases. This is expected as greater clipping norm results in greater Gaussian noise per-step. Though, for $C > 1$, the performance drop is relatively small.

---

3. Comparison with Baseline DP Method in MIA

Moreover, there seems to be no comparison to traditional DP and the only one you are comparing against is the uncalibrated non-private method which already has pretty poor performance to begin with.

Thank you for pointing out the comparison with traditional DP (DP-SGD). To clarify, the i.i.d. method in our experiments refers to data valuation using the plain DP-SGD algorithm. For the MIA experiment, we provide the following comparative results:

It can be observed that traditional DP-SGD achieves reasonable MIA protection, as expected. However, the key challenge in using DP-SGD for data valuation lies in controlling the scaling of estimation uncertainty, which our work specifically addresses. Due to space constraints, we focused on data value estimation as the primary contribution of our work.

---

4. Presentation of Algorithm 1

algorithm 1 is difficult for me to digest: are all 3 colors integrated into it already or are they mutually exclusive drop-ins which we need to evaluate separately?

Thank you for raising this conrern. We apologize for any confusion. All 3 colors are integrated, as explained in lines 353-354. To improve clarity, we have labeled each section with explicit "if-else" clauses in the revised version.

Thank you for your response and for raising additional questions. We are delighted to hear that our previous response was largely satisfactory.

We address your additional concerns as follows.

---

1. DP Algorithm of [2]

Thank you for pointing this out. To clarify, we observed that while the authors mention the DP version of VoG and PLSS in Section 4.7 of [2], they do not provide experimental results to demonstrate the effectiveness of these proposed DP version. We acknowledge that our original phrasing was imprecise, and we have updated the revision to better reflect this observation.

---

2. AUC Results for MIA

Thank you for making this interesting observation. The results sometimes fall below $0.5$ due to numerical issues. Specifically, the ROC AUC is computed using a trapezium summation method over the TPR against FPR as the threshold changes. In cases where attack scores are closely clustered, small changes in the threshold can result in significant differences in TPR and FPR. This can cause the computed AUC to be smaller than the true AUC, as the trapezium summation aggregates a discrete number of intervals. A similar phenomenon can be found in Table 3 of [5] where some reported AUROC values are below $0.5$.

[5] Wang et. al., Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation, NeurIPS 2023.

---

We hope the above has addressed your concern and improved your opinion of our work. We are happy to discuss with you for any further questions.

Dear reviewer nG37,

We sincerely thank you for taking your time to provide the review and for recognizing the interesting problem addressed in our work, as well as our theoretical contributions.

We would like to address your concerns in the following.

---

1. Prior Work with Correlated Noise

the existence of prior work that also carefully generates the correlated noise to reduce the variance of released statistics suggests that there might be room for further improvement in the proposed approach.

Thank you for highlighting this point. We acknowledge that several prior works have explored adding correlated noise in the context of counting problems or online learning, as noted in our related work section. A key contribution of our work lies in the theoretical characterization of the use of correlated noise specifically within the data valuation setting under DP-SGD, a problem not directly addressed by prior research.

We agree with you that there can be potential further improvement in our algorithm and we hope to further explore it in our future research.

---

2. Bias of the Estimator

I am curious to know how the proposed approach affects the bias of these gradients. Especially, as the proposed algorithm takes the average of gradients evaluated in the preceding locations in the optimization trajectory, the proposed approach may increase the bias. It will be interesting if the authors can show that this is not the case.

Thank you for raising this interesting question on the bias of our estimator! Indeed, our estimator is biased. We wish to also highlight that the naive DP-SGD estimator is also biased, since utility $V$ is often not a linear function of $\tilde{g}$.

To provide a detailed comparison, we have improved our theoretical analysis and included a bias bound for our method in Propositions 5.2 and 5.3, highlighted in red. For Lipschitz-smooth $V$, we can bound the bias of the naive DP-SGD by $O(\log k)$. For our method, we have improved our theoretical analysis by incorporating a result on the bound of bias in Proposition 5.2 and Proposition 5.3, in red. We show that the bias of our method is $O(\log k + \sigma_g^2)$ without burn-in and $O((1-q)\log (1/q) + \sigma_g^2)$ with burn-in.

While our bias has an additional $\sigma_g^2$ term than the naive DP-SGD, the term is a constant and does not grow with $k$. As such, controlling the linear scaling of estimation uncertainty is more crucial for improving the quality of estimates.

---

3. Presentation of Figures

The graphs presented in the paper are not properly labeled. While the captions provide some explanation, it's still not easy to read and interpret the graphs. The figures should be self-contained and interpretable on its own.

Thank you for pointing this out. We apologize the inconvenience in reading the figures. We have added the labels to all axes and improved the captions of all figures in the revised version. This should make the figures self-contained and more interpretable.

---

4. Derivation of $X^*$

How is the proposed solution $X^*$ derived? Is it a solution (or an approximation solution) of constrained optimization problem that minimizes the estimation uncertainty?

Thank you for your question. $X^*$ is an approximate solution of Proposition 5.2. In the formal version of Proposition 5.2, (Proposition C.10), an exact form of $X$ is provided. As $k \to \infty$, the exact solution tends to $X^*$.

---

5. Choice of Hyperparameter $q$

In Figure 3, the performance of proposed method with burn-in seems to drastically decrease when q is set too high. Is there a rule of thumb for setting this hyperparameter?

Thank you for your question. The performance drastically drops when $q$ is too high because insufficient samples remain (after burn-in) for an accurate estimation. Drawing on standard practices in burn-in techniques (e.g., in MCMC), a common practice is to discard the first 20%-50% of the samples, i.e, choosing $q \in [0.2,0.5]$.

---

We hope our response has been adequate in addressing your concerns. We are happy to further discuss with you for any other questions that you might have.

Dear reviewer eWxj,

We sincerely thank you for taking time to provide your review and for recognizing the clarity of our motivation and problem setting, as well as the comprehensiveness of our experiments.

We would like to address your concerns in the following.

---

1. Clarification on the Sub-Gaussian Assumption

The statement of assumptions is unclear. In Proposition 5.2, the authors state that the isotropic sub-gaussian assumption is made for the distribution but then introduce the covariance matrix $\Sigma$. Does isotropic mean that the covariance is the identity matrix?

Thank you for raising this point. We apologize for the confusion. In our revised version, We have corrected the name from "isotropic" to "diagonal". Our assumption only requires the gradients to be independent, which implies that all off-diagonal entries in the covariance matrix are $0$. We appreciate your bringing this to our attention and hope the revised terminology resolves any confusion.

---

2. Comparison with the Binary Counting Mechanism

I wonder whether the previously proposed binary counting mechanism can also achieve the same performance bound as the proposed adaptive mechanism under this assumption, since it seems that the main task in this setting is to continually release a sequence of averaged gradient to reduce the variance.

Thank you for raising this interesting question! While the binary counting mechanism shares some similarities with our problem setting as it addresses a continuous release problem, there are key distinctions that differentiate it from our approach:

• Trusted central server: The binary counting mechanism requires a trusted central server since raw gradients must be shared internally before being privatized. In contrast, our method does not require a trusted central server, as gradients are privatized before being released.

• Integration with DP-SGD: The binary counting mechanism aggregates raw data, which inherently differs from the DP-SGD framework. DP-SGD does not involve aggregating raw gradients in the same manner, making it not naturally compatible with the binary counting mechanism.

However, assuming the presence of a trusted central server and that the model is updated using the aggregated gradient in one batch, we believe that the binary counting mechanism can achieve sub-linear estimated uncertainty as well. Here is a rough sketch of the proof: For each set $S$ and an individual data point $x$, to find the marginal contribution $V(S \cup \{x\}) - V(S)$, we can build a p-sum tree and use that to find the noisy aggregate

$\tilde{g}_{S \cup \{x\}}$

and $\tilde{g}_{S}$, each of them having a variance of size $O(\log{k})$ instead of $O(k)$ with naive DP-SGD. Since any polynomial of logarithmic of $k$ grows slower than linear $k$, for most utility functions $V$ including logistic regression and linear regression, we have $\text{Var}(V) = o(k)$. One can then derive that the estimation uncertainty is sublinear.

---

We hope our response has adequately addressed your concerns. We are delighted to discuss with you any further questions that you may have.

Response Part (1/2)

Dear reviewer wKAq,

We sincerely thank you for taking time to provide the review and for recognizing the interesting aspects of our work, its clear connection to prior research, and that our non-trivial techniques present useful applications.

We would like to address your concerns in the following.

---

1. Interpretation of Estimation Uncertainty (Eq. 3) and Proposition 5.3

I did not understand why this notion of estimation uncertainty (Eq 3) is meaningful. An algorithm that always returns $\psi_j=0$ is perfectly private and has no variance. So I don't know how to interpret Proposition 5.3, which says that we can bound the variance by a constant. Is that good? Perhaps the correlated noise technique is simply bringing us closer to the $\psi_j=0$ example?

Thank you for raising this insightful question. While setting $\psi_j=0$ always results in zero variance, it has substantial bias. To complement our focus on minimizing estimation uncertainty, we have enhanced our theoretical analysis to include bounds on the bias of our method (see our revised Propositions 5.2 and 5.3, highlighted in red). Specifically, with burn-in, our method achieves an estimation bias of $E[\psi_j^* - \psi_j] = O((1-q)\log (1/q) + \sigma_g^2)$. Note that this bound does not grow with $k$.

As a side note, the naive DP-SGD method also introduces bias, as most utility functions $V$ are not linear in $\tilde{g}$. With Lipschitz-smooth $V$, the naive DP-SGD algorithm achieves a bias bound $E[\psi_j^* - \psi_j] = O(\log k)$.

The core problem we address in our work is that even when $\sigma_g$ is moderate, current naive estimation method fails to produce accurate estimates because of linear scaling in estimation uncertainty. Since the estimation bias is already bounded by a constant, our work naturally focuses on minimizing estimation uncertainty.

---

2. Rank Preservation Under Differential Privacy

Data value estimation of under a simple binary model...Both the Remark on p4 and Appendix B.4 suggest one can accurately preserve the ranks under differential privacy (so that valuable data receives higher estimates). But, as the above example shows, privacy also constrains our ability to do this.

We appreciate your comment. We wish to clarify that the claim that our method "accurately preserve" the ranks is a comparative statement relative to the naive MC approach. As demonstrated in our experiments and supported by our constant-bound estimation uncertainty, our method achieves significantly better rank preservation. We do not claim "perfect" rank preservation and we agree with you that it remains a challenge due to the inherent constraint of DP.

To address your feedback, we have revised the relevant passages (see lines 214-216) to explicitly clarify the limit of our claim and avoid potential misunderstandings.

---

3. Assumptions on Sub-Gaussian Distribution

Propositions 5.2 and 5.3 assume the following: for a given point , its gradient estimates are iid and sub-Gaussian about a fixed mean...the distribution is isotropic, so isn't $\Sigma$ the identity?

Thank you for pointing this out. To clarify, we have revised the text to explicitly state that $\Sigma$ is "diagonal," not the identity matrix. The diagonal sub-Gaussian assumption involes two components: (1) the gradients are independent, and (2) each gradient follows a sub-Gaussian distribution.

To demonstrate that the assumption can hold in practice, we provide some empirical results. For independence, we compute the 50 percentile of absolute correlation coefficient between gradients. For sub-Gaussianess, we conduct a concentration test where we compare the area under curve of $P(|g - \bar{g}|) > t$ v.s. $t$ and that of a Gaussian (i.e., $e^{-t^2/(2σ_g^2)}$ v.s. $t$). For sub-Gaussian distribution, the former should be smaller than the latter. For RestNet18, we randomly select $10000$ parameters to compute the gradient statistics due to computational constraint.

It can be observed that while there is correlation between gradients, they are not significant. The gradients also exhibit a sub-Gaussian according to the tail-decay test.

Response Part (2/2)

---

Props 5.2 and 5.3 assume that the gradients are sub-Gaussian with identity covariance, which is a weaker assumption than the independent coordinates you discuss in another comment.

Thank you for this observation. We wish to clarify that we have updated the assumption in Propositions 5.2 and 5.3 to specify a "diagonal" sub-Gaussian distribution (see our earlier response). The term "isotropic" in the original version was a mis-spelling. Our proofs have consistently relied on the assumption that gradients are diagonal sub-Gaussian random variables with varying variances and $0$ covariance.

---

I'm not sure about the proof where this assumption shows up, on p33: I don't see why the fourth moment of $z_t'^4$ is strictly bounded by that of $z_t^4$.

Thank you for your question. The fourth moment of $z_t'^4$ is strictly bounded by that of $z_t^4$ due to the sub-Gaussian assumption, as shown in Lemma 1.4 of [1]. Intuitively, sub-Gaussian distributions exhibit smaller higher moments than Gaussian distributions due to their stronger tail-decay properties.

In our proof, we acknowledge a slight oversight in omitting the constant in the inequality, as we focused on the asymptotic bound. We have now amended the proof and included a more detailed derivation. Specifically, we should have $\mathbb{E}[z_t'^4] \leq \frac{16}{3} \mathbb{E}[z_t^4]$.

---

I'm not sure I was able to correctly parse the description of your sub-Gaussian test experiments. However, I do not feel this is an important point.

Thank you for this feedback. The sub-Gaussian test experiment demonstrates that the diagonal sub-Gaussian distribution approximately holds in practice. Specifically, we report the correlation coefficient and tail-decay statistics. The small correlation coefficients suggest that gradients exhibit near-independence, while the mean AUC of gradients being smaller than that of a corresponding Gaussian distribution supports strong tail-decay and the sub-Gaussian property.

---

Summary of Key Clarification

We summarize our key clarifications to your concerns:

1. Our definition of estimation uncertainty captures the uncertainty of data value estimates caused by DP noise. Our central claim, supported by Proposition 5.1, is that controlling estimation uncertainty is a necessary but not sufficient condition for achieving high-quality data value estimates. While alternative methods (e.g., setting $\psi=0$ or $k=1$) may achieve low estimation uncertainty, they do not necessarily result in better data value estimates. This distinction is crucial, as establishing necessary conditions is as important as identifying sufficient ones.

2. Our proofs rely on the assumption that gradients follow a diagonal sub-Gaussian distribution, which enables bounding noise moments via Gaussian random variable bounds. Our experimental results further support this assumption, showing that gradients are approximately uncorrelated and exhibit sub-Gaussian behavior.

---

We hope these clarifications address your concerns and improve your understanding of our work. We welcome any further questions or feedback and would be happy to discuss these points in more detail.

[1] Chapter 1, Lecture Notes on Sub-Gaussian Random Variables. MIT OpenCourseWare. Accessible at: https://ocw.mit.edu/courses/18-s997-high-dimensional-statistics-spring-2015/a69e2f53bb2eeb9464520f3027fc61e6_MIT18_S997S15_Chapter1.pdf

Response Part(1/2)

Thank you for your thoughtful feedback. We would like to address your questions and clarify our responses as follows:

---

I feel there is a mismatch between (i) the theoretical results and (ii) their purpose and discussion. The quantity called "estimation uncertainty" I still find rather un-interpretable. For example, it does not reflect the analyst's uncertainty about the value of point , nor does it capture uncertainty about value estimation in the absence of privacy noise (since the noise changes the trajectory).

Thank you for raising this concern. We would like to clarify that the estimation uncertainty captures the uncertainty about the value of an estimate through its definition as conditional variance. Importantly, we do not define estimation uncertainty to capture uncertainty in the absence of privacy noise; rather, it is specifically intended to reflect the uncertainty induced by privacy (see lines 203-207).

By defining estimation uncertainty in this way, a high level of estimation uncertainty directly corresponds to substantial uncertainty in the estimation of data value due to differential privacy (DP). Consequently, reducing estimation uncertainty is necessary to improve data value estimates (see lines 208-210), although the converse may not hold.

We would greatly appreciate it if you could indicate specific instances in the paper where you perceive a "mismatch".

---

If I want to minimize the "estimation uncertainty," why don't I simply iid noise with $k=1$? Informally, we know the answer relates to the quality of optimization, but this type of question seems to be missing from the paper. It's not clear what questions this conditional variance term addresses.

Thank you for your question. We wish to re-emphasize that we do not claim that minimizing estimation uncertainty necessarily yields the best data value estimates (see lines 212-217). To provide an explicit statement of what estimation uncertainty entails, we have the following:

Under certain utility functions, low estimation uncertainty is a necessary but not sufficient condition for obtaining high-quality data value estimates.

This statement follows directly from Proposition 5.1.

While alternative methods (e.g., using $k=1$ in your example) could potentially achieve lower estimation uncertainty, our work specifically addresses the naive Monte Carlo (MC) approach. A thorough comparison with methods outside the MC framework would require additional analysis, which is beyond the scope of this work.

---

I don't understand the "bias" analysis that shows up in Props 5.2 and 5.3, either.

Thank you for raising this point. The bias analysis in Propositions 5.2 and 5.3 serves as a complementary result, highlighting the bias of our estimator. In our earlier response, we assumed that your query was related to the bias of our proposed estimator, given your example of setting $\psi=0$, which results in zero estimation uncertainty but introduces substantial bias.

Based on your response, we now understand that you may be questioning whether our definition of estimation uncertainty appropriately facilitates comparisons between our method and alternatives like setting $\psi=0$. We reiterate that while controlling estimation uncertainty is necessary, it alone does not guarantee accurate data value estimates. However, failing to control estimation uncertainty invariably leads to poor estimates. A thorough comparison with methods outside of the MC framework is beyond the scope of this work.

---

Looking back, I believe I would have been more receptive to this paper if it was introduced as fundamentally practical in nature, with the math presented later as a way to give confidence to the empirical results.

Thank you for recognizing the empirical results presented in our work. We would like to clarify that our empirical results are grounded in the theoretical framework we establish. This framework specifically addresses the problem of linearly scaling estimation uncertainty in the naive MC approach, which causes the noise induced by DP to escalate. We emphasize that while we solve a practical problem, our method is not practical in nature, but based on properly defined theoretical results (Proposition 5.2 and Proposition 5.3). We would like to emphasize the significance of the theoretical results, as highlighted in other parts of this response.

---

Any future versions of this work should include definition of multivariate sub-Gaussian distributions.

Thank you for this suggestion. We have included a definition of multivariate sub-Gaussian distributions at their first mention in our revised version (see lines 330-332).

Response Part (2/2)

Further Comment on the Merit of Our Theory

While we acknowledge that demonstrating the sufficiency of a specific objective for achieving better data value estimation is an exciting direction for future research, we note that significant contributions in the machine learning literature often begin with necessary conditions as their theoretical foundation. For instance, loss minimization is generally a necessary, but not sufficient, condition for good model performance. Similarly, in our work, the focus on necessary conditions provides a robust starting point for theoretical exploration and practical implementation, even as we recognize that future progress will likely depend on establishing stronger sufficiency results to fully address the problem.

We hope these clarifications resolve your concerns. Please let us know if further elaboration is required.