- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper introduces Ball-DP, which replaces the definition of adjacency in DP from differing in 1 sample to differing in 1 sample within distance r. The authors show theoretically that under the ERM setup, the optimal finite-prior MAP reconstruction scheme can be derived for Gaussian output noise, along with bounds on reconstruction success probability. With this restricted adjacency, Ball-DP requires less Gaussian noise than standard DP at the same , but only within the radius r. Experiments validate this claim by showing that higher utility is obtained with comparable reconstruction success using a ridge-prototype classifier. Here, the attacker is assumed to know all data points except 1 and that the missing entry is from a known finite set of candidates.
Critical strengths
The experiment is aligned with the theory and shows clear improvement when we only need local protection. Moreover, Ball-DP provides an interesting theoretical framework in these scenarios, the extra r parameter makes the scope of privacy more explicit.
Critical weaknesses
Ball-DP by means of restricting the definition of adjacency seems not completely new, without the term this seems to be a special case of Blowfish Privacy ([1], Equation 7). The paper does not explicitly clarify what is new beyond this existing framework.
Moreover, the experimental section does not clearly explain how utility is evaluated, the details needs to be clearer.
[1] He, X., Machanavajjhala, A., & Ding, B. (2013). Blowfish privacy: tuning privacy-utility trade-offs using policies. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.
Questions for authors
- What is the precise relationship to Blowfish’s distance-threshold case, how much does Ball-DP improve beyond this.
- The paper claims comparable reconstruction robustness, but the protection is limited to radius , which is already a weaker guarantee. How does connect to real-world examples? Would the results hold under less informed settings, such as the attacker having a continuous prior or less knowledge about other samples?
- Based on my understanding of the paper, the experiments shows that with less protection radius, we can have higher utility. With the privacy measurements already associated with r, this feels trivial. Could additional experiments be provided to provide insights beyond this trivial gain? Such as a real-world motivated privacy measument utilizing this parameter.
4 comments
Gentle reminder for follow-up
Dear Reviewer,
We appreciate your time and effort in reviewing our manuscript. Your feedback has helped us improve the manuscript, and we are grateful for that.
We were wondering if our rebuttal has addressed your concerns. If that's not the case, or if you have other concerns, we would be happy to respond to them before the discussion period ends. While we do not explicitly ask to change your rating, we hope that if you have found our response satisfactory then you would indicate that by raising the score.
Thank you once again for your valuable feedback. We know that providing a constructive review takes a non-trivial amount of time and effort, and we really appreciate it.
Best regards,
Authors
The rebuttal substantially improves the evaluation, but after accounting for Blowfish and Pufferfish, the main novelty of the new definition is weakened a lot. The remaining contributions are the theoretical analysis and an empirical audit, but the experiments primarily quantify an expected policy–utility trade-off. With theory and experiments being the main contributions, I currently still find the overall novelty/significance below the ICLR acceptance threshold.
The theorem in the paper seems similar to existing ReRo guarantees, but with a localized version (e.g., Reconstructing Training Data with Informed Adversaries, Balle 2022). Could the authors identify some key novelties of the theory? And could the authors provide a significantly different guarantee with Ball-DP that differs in scale and not just by a multiplier of ? I could consider raising my score if significant contribution and novelty is observed in the theory, but would like to maintain my current rating for now.
Thank you for your feedback
Dear Reviewer,
We really appreciate your valuable feedback, which has helped in improving the original manuscript. For now, we do not have such an explicit guarantee, but the scale is implicit in (the obvious guess). It'd be interesting to work it out explicitly though.
Thank you very much for your time and effort in reviewing our paper, and importantly, for following up on our rebuttal.
Best regards,
Authors
We thank the reviewer for the careful review and the questions on the meaning of r. All references below are to the revised manuscript.
W1 / Q1 (Blowfish). See the general response, point 1.
W2 (utility evaluation). Utility is measured by the accuracy of the released model on a hold-out test set, averaged over ten Gaussian release seeds. Section 5 now states this explicitly.
Q2 (real-world meaning of r; less informed attackers). The radius is a design parameter chosen by the defender, like (ε,δ): it states how much reconstruction is tolerable. It enters the Ball-ReRo guarantee (η,γ) directly, which bounds how well the attacker can localize the target within its radius-r neighborhood. In practice, r is set so that the ball contains the alternatives that must remain indistinguishable. The new App. E (MNIST and CIFAR-10, q50 and q80) shows what this means qualitatively: at q50, the protected alternatives are other images of the same class with similar appearance, e.g., stroke style for digits, or viewpoint, background, and color for CIFAR-10, while records with a different style or composition fall outside.
The theorems hold for any ball-supported prior, including continuous ones, and for any reconstruction loss and tolerance. The informed adversary is the strongest case: the bounds hold for every D−, so an attacker that is uncertain about D− is also covered.
Q3 ("trivial" gain). That less protection buys utility is expected; what the paper provides is a way to make this trade-off explicit and certifiable for reconstruction. For a Gaussian release, the certificate depends only on Δr/σ, so a release with a weak global DP guarantee can still certify strong robustness against local reconstruction, and r is the parameter to report. The new fixed-support audit (App. D) quantifies the trade-off on identical candidate sets for each benchmark (Figure 7): at ε=1, the mean normalized accuracy gain is ΔU=0.245 for a normalized increase in exact-ID success of ΔL=0.016; ΔU falls to 0.109 at ε=4 and to 0.043 at ε=8.