acceptodds
Under review as a conference paper at ICLR 2027

Ball Differential Privacy - How to Mitigate Data Reconstruction with Less Noise

Abstract

Vector embeddings of raw records, while not human-readable, do not preserve privacy of records: an adversary can reconstruct training records from a released model. Differential privacy (DP) is the principled defense, but its noise is calibrated to the worst-case indistinguishability; obscuring arbitrary single-record substitutions, including those far outside the set of plausible alternatives relevant to a reconstruction adversary. The result is noise far larger than what reconstruction robustness requires, which degrades accuracy without a corresponding security benefit against reconstruction attacks. To mitigate this limitation of standard DP, we propose Ball-DP: indistinguishability over single-record substitutions restricted to a ball of radius according to a distance metric in the embedding space. A deployment facing only local reconstruction threat can choose a small , thereby reduce noise and recover wasted accuracy. The radius makes the scope of the privacy claim explicit against reconstruction attacks; standard DP is recovered when covers the entire admissible record domain. We provide noise calibrations for regularized convex learning problems for Ball-DP, and derive the corresponding reconstruction-robustness certificates (named Ball-ReRo) – upper-bound on an attacker's reconstruction success. By deriving the optimal finite-prior MAP reconstruction attack, we conduct empirical auditing of Ball-ReRo certificates for several benchmark learning tasks. We observe that calibrating noise to Ball-DP significantly improves utility, with marginal impact on reconstruction robustness.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, training data reconstruction, reconstruction robustness, privacy-preserving machine learning, convex empirical risk minimization, output perturbation, embedding privacy

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_YKCaOpenReview ↗
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 (ϵ,δ)(\epsilon,\delta), 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 δ\delta 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
  1. What is the precise relationship to Blowfish’s distance-threshold case, how much does Ball-DP improve beyond this.
  2. The paper claims comparable reconstruction robustness, but the protection is limited to radius rr, which is already a weaker guarantee. How does rr 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?
  3. 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 rr parameter.
4 comments

We thank the reviewer for the careful review and the questions on the meaning of rr. 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 rr; less informed attackers). The radius is a design parameter chosen by the defender, like (ε,δ)(\varepsilon,\delta): it states how much reconstruction is tolerable. It enters the Ball-ReRo guarantee (η,γ)(\eta,\gamma) directly, which bounds how well the attacker can localize the target within its radius-rr neighborhood. In practice, rr is set so that the ball contains the alternatives that must remain indistinguishable. The new App. E (MNIST and CIFAR-10, q50q50 and q80q80) shows what this means qualitatively: at q50q50, 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−D^-, so an attacker that is uncertain about D−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/σ\Delta_r/\sigma, so a release with a weak global DP guarantee can still certify strong robustness against local reconstruction, and rr 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\varepsilon=1, the mean normalized accuracy gain is ΔU=0.245\Delta U=0.245 for a normalized increase in exact-ID success of ΔL=0.016\Delta L=0.016; ΔU\Delta U falls to 0.109 at ε=4\varepsilon=4 and to 0.043 at ε=8\varepsilon=8.

AuthorsOpenReview ↗

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 rr? 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.

AuthorsOpenReview ↗

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 κ\kappa (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

Reviewer_3dmvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Ball-DP, which imposes the same indistinguishability on single-record replacements whose distance does not exceed a specified radius. The authors derive sensitivity bounds and a Gaussian output perturbation mechanism for regularized convex learning, together with reconstruction-success bounds under ball-supported priors. Experiments on seven fixed-embedding benchmarks demonstrate utility improvements from restricting the protected neighborhood and evaluate reconstruction risk through attacks.

Critical strengths
  1. An explicit formulation of privacy for local changes. Ball-DP provides a clear framework for protecting a record against substitution by multiple alternative values within a specified neighborhood. Making the radius an explicit privacy parameter helps articulate which content changes are protected.

  2. A clear separation between the protection scope and indistinguishability strength. The radius determines the protected adjacency relation, while epsilon and delta specify a uniform indistinguishability bound over that relation. This separation is straightforward to interpret.

  3. Theoretical analysis connecting the definition, mechanism, and reconstruction risk. The paper derives sensitivity bounds for convex ERM under the proposed adjacency relation and establishes upper bounds on reconstruction success.

Critical weaknesses
  1. The novelty of the Ball-DP is insufficiently established. Ball-DP is closely related to metric-DP. For example, the distance-dependent bound in [1] already implies a uniform indistinguishability within the radius. Ball-DP retains a uniform requirement within the radius without requiring progressively stronger guarantees for closer pairs. Although the paper acknowledges this distinction, it remains unclear how much conceptual novelty follows from it.

  2. The framing of DP as naturally aligned with MIA is misleading. I find the characterization of DP as “naturally aligned with MIA” problematic. DP provides a self-contained, formal indistinguishability guarantee over neighboring datasets, whose meaning does not depend on a particular inference task or attack algorithm. Robustness against MIA can be a consequence of this guarantee, and empirical MIA evaluations can illustrate its practical effects. However, this does not justify presenting MIA resistance as the defining objective of DP. The paper’s contrast between DP for MIA and Ball-DP for reconstruction attacks conflates the semantics of a privacy definition with particular applications of its guarantees. The motivation would be more convincing if grounded in the sensitive information to be protected, the admissible changes to a record, and the justification for restricting protection to a local neighborhood.

  3. The empirical evaluation has a limited scope. Although the experiments cover seven datasets, the principal results concern a ridge-prototype model trained on fixed public embeddings. The evaluation does not cover end-to-end deep learning or DP-SGD, leaving the method’s applicability and utility advantages in these settings unresolved.

[1] Andrés, Miguel E., et al. “Geo-indistinguishability: Differential privacy for location-based systems.” Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. 2013.

Questions for authors
  1. Can the authors tell the difference between the privacy definition of Ball-DP and Geo-Indistinguishability mentioned above? Since it can also imply a uniform indistinguishability within the radius.

  2. Can the motivation be stated more explicitly in terms of privacy protection?

  3. Can the approach be extended to end-to-end deep learning or DP-SGD? If such extensions are beyond the current scope, could the authors clarify the principal theoretical and practical obstacles?

2 comments

We thank the reviewer for the thoughtful review and the helpful comments on positioning. All references below are to the revised manuscript.

W1 / Q1 (metric-DP, Geo-indistinguishability). Geo-indistinguishability is εd\varepsilon d-metric-DP. It implies (r,εr,0)(r,\varepsilon r,0)-Ball-DP, but not conversely: Ball-DP requires no stronger protection for closer pairs and makes no claim beyond rr, which is exactly Blowfish's distance-threshold policy. The revised Introduction positions Ball-DP primarily against Blowfish and Pufferfish, and the novelty lies in the reconstruction guarantees (see general response, point 1).

W2 (MIA framing). We agree and have revised the wording. We do not criticize DP: indistinguishability provides tight protection against membership inference. Our point is that a reconstruction adversary needs more than membership; it must distinguish the target from alternatives in a local neighborhood, so the adjacency can be restricted accordingly. The same Gaussian mechanism with small noise can then certify local reconstruction robustness even though its global guarantee is weak. For example, on our benchmarks the release that is Ball-DP at ε=2\varepsilon=2 with r=q50r=q50 satisfies standard DP (radius 2B2B) only at ε≈3.5\varepsilon\approx3.5–8.48.4 (IMDb to MNIST).

Q2 (motivation in terms of privacy protection). The sensitive information is the content of a record, not the fact of participation; the substitutions to protect are its plausible alternatives, i.e., same-label records within distance rr. Restricting protection to this neighborhood is justified because side information already narrows the target to such alternatives, and a reconstruction is a breach only if it localizes the record more precisely than the defender tolerates. For instance, revealing that a photo shows a dog may be acceptable, while its breed must stay hidden (see examples of images in Appendix E for more intuition on what kind of protection Ball-DP provides). The Introduction now states this motivation explicitly.

W3 / Q3 (scope, DP-SGD). Ridge prototypes ground Ball-DP in a setting where both the sensitivity and the Bayes-optimal attack are in closed form; we also evaluate logistic and squared-hinge heads (App. F). For DP-SGD, per-step sensitivity and Rényi composition carry over directly: clipping is non-expansive, giving per-step sensitivity min⁡(Lzr,2C)\min(L_z r,2C). The main theoretical obstacle is composing reconstruction robustness, since the attacker's baseline κ\kappa evolves across rounds as its posterior sharpens, so per-step certificates do not simply chain. The practical obstacle is that LzL_z is unknown for nonconvex representation learning. Section 7 now discusses both.

AuthorsOpenReview ↗

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

Reviewer_juLCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Ball-DP to defend against data reconstruction attacks on convex models trained over fixed embeddings. The motivation is that standard DP may add more noise than necessary. It protects arbitrary record replacements across the whole domain, even when a reconstruction attacker only cares about nearby candidates. Ball-DP in this paper instead only protects same-label replacements within a radius r. The authors show that the sensitivity of strongly convex ERM scales linearly with r, and they also give upper bounds on the reconstruction success rate for Gaussian output perturbation. They test the method on seven embedding datasets and show better accuracy than standard DP, while keeping MAP attack success below the theoretical bound.

Critical strengths

The math and proofs are clean and easy to follow. The authors adapt standard strong-convexity sensitivity and Gaussian reconstruction bounds to a ball-supported prior in a natural way. Also, choosing the ridge-prototype classifier is a great design choice because its sensitivity and the MAP attack both have exact closed forms, Table 2 tests the certificate against the Bayes-optimal attacker for the stated finite prior rather than a heuristic.

The paper tackles a very well-motivated problem. The gap between worst-case DP and real reconstruction risk is an important topic. The authors are also upfront about the limitations of their setup. For example, they clearly state that labels are unprotected under Eq. (2), calibration values must be public or privatized, and the analysis only covers one-shot convex models on fixed embeddings rather than DP-SGD.

Critical weaknesses

To the best of my knowledge, defining neighboring datasets via a distance threshold is not a new idea. The proposed adjacency definition is very close to Blowfish privacy, which is not cited or discussed in the paper (see reference 1). Blowfish already defines a distance-threshold policy that connects two records if their distance is within a threshold, and shows that policy-specific sensitivity can be much smaller than global sensitivity, while standard DP is recovered when the graph is complete. So if we set the threshold to r and only connect same-label records, it essentially gives the r-adjacency in Definition 3.1 (see Pufferfish in reference 2, and the taxonomy in reference 3).

Right now, this paper (Section 1, lines 103–107, and Section 6) only compares Ball-DP with metric DP. I agree that applying this idea to convex ERM and Gaussian reconstruction bounds is still useful, but the paper should credit these prior frameworks and explain what is new beyond them. This affects my rating because the Ball-DP definition is claimed as the first main contribution.

References:

He, X., Machanavajjhala, A., & Ding, B. (2014). Blowfish privacy: Tuning privacy-utility trade-offs using policies. ACM SIGMOD 2014.

Kifer, D., & Machanavajjhala, A. (2014). Pufferfish: A framework for mathematical privacy definitions. ACM TODS 39(1).

Desfontaines, D., & Pejó, B. (2020). SoK: Differential privacies. PoPETs 2020(2).

The empirical audit in Section 5.4 changes the noise level and the attack candidate set at the same time. The paper claims that Ball-DP improves accuracy with "marginal impact on reconstruction robustness". However, when we reduce noise for a smaller radius r, privacy protection for records outside the ball (t>r) naturally gets weaker (Proposition 3.7).

In the audit, Ball-DP at q_50, q_80, and q_95 is tested on candidate sets sampled inside its own ball, while Standard DP is calibrated to the same-label diameter and tested on the q_80 candidates. Because the candidate sets change with the radius, only the q_80 column and the Standard DP column test the same attack task. Even on this matched comparison, Ball-DP at q_80 has higher attack success rates than Standard DP in 17 of the 21 settings (e.g., 0.373 vs. 0.278 on CIFAR-10 at ϵ=8, and 0.218 vs. 0.163 on MNIST at ϵ=4; in Table 2).

To really support the robustness claim, all methods should be tested on a fixed candidate set. It would be nice to show a few raw text or image examples inside a radius-r ball so readers can see what level of similarity is actually protected. This weakness affects my rating most, because "less noise with comparable robustness" is the main message of the paper.

Questions for authors

I would consider raising my score if the authors can address these questions below:

1. How do Definition 3.2 and Theorem 3.5 relate to the distance-threshold policy in Blowfish privacy? 

2. In Table 2, could you evaluate Ball-DP (e.g., at q_50) and Standard DP on the exact same candidate set? Specifically, if we fix D^-, the prior, and the 10 candidates, how do the two methods compare on a local candidate set (q_50) versus a wider one (q_95 or the full same-label diameter)? 

3. How were the policy radii and empirical diameter obtained in the experiments (e.g., for the image datasets)? Were they computed directly from the private training set, from a separate public split, or through a differentially private procedure? Section 3.1 notes that data-dependent calibration values need to be public or privatized. Also, please clarify whether the embeddings are normalized, and report the actual q_50, q_80, and q_95 values along with their ratios to 2B. Since distances often concentrate in high-dimensional spaces, seeing these numbers would really help clarify how much the radii differ in practice and how much noise they actually save. 

4. Under Eq. (2), cross-label replacements have infinite distance, so setting r=2B still only covers same-label replacements. However, Proposition 3.3, which states that Ball-DP implies standard DP when r≥2B, uses the plain Euclidean metric without labels. Does your "Standard DP" baseline also assume fixed/public labels, or does it protect arbitrary replacements including label changes? If it is the latter, how do you account for cross-label replacements in the sensitivity calibration?
2 comments

We thank the reviewer for a thoughtful review and concrete suggestions for the audit. All references below are to the revised manuscript.

W1 / Q1 (Blowfish). See the general response, point 1. Theorem 3.5 is the convex-ERM (ℓ2\ell_2, minimizer-level) counterpart of Blowfish's policy-specific sensitivity.

W2 / Q2 (audit on a fixed candidate set). We agree. In Figure 3 and Table 2, only the q80q80 and Standard-DP bars share the same supports (D−D^-, prior, and 10 candidates); the q50q50 and q95q95 bars use supports inside their own balls and test different attack tasks. We now state this in Section 5.4, together with the fact that less noise does raise exact-ID success on the shared supports (17 of 21 settings).

We also ran the audit you suggested (new Section 5.5 and App. D, Table 3, Figure 6). We fix D−D^-, the prior, and the 10 candidates, and attack Ball-DP (q50q50) and Standard DP on identical trials with the same noise draw, on the local q50q50 ball and on the wider q80q80 and q95q95 balls, with Standard DP calibrated to 2B2B as in Table 1. Mean normalized increase in exact-ID success ΔL\Delta L:

supportε=1\varepsilon=1ε=2\varepsilon=2ε=4\varepsilon=4
q50q500.0160.0340.067
q80q800.0150.0380.079
q95q950.0190.0380.088

You are right that protection for substitutions beyond the radius (t>rt>r) is weaker: the release is (t,εt,δt)(t,\varepsilon_t,\delta_t)-Ball-DP, with εt\varepsilon_t growing with t/rt/r (Proposition 3.7). Empirically, however, q50q50 release degrades gracefully outside its ball. The support-specific certificate, which remains valid beyond the calibration radius (Theorem H.5), holds within sampling error: 32 of 36 rates are below it, and the 4 exceptions (at ε=1\varepsilon=1, where the certificates are close to chance) exceed it by at most 0.010. With m=100m=100 candidates on MNIST (App. D.1), the attack is close to chance (0.010.01) for both mechanisms: ΔL\Delta L (normalized increased attack success) is at most 0.003 at ε=1\varepsilon=1 and 0.008 at ε=2\varepsilon=2, while the normalized accuracy gain is unchanged (0.259 and 0.070).

Raw examples inside the ball. Thank you for this suggestion; we added them (App. E, Figures 8–11). For MNIST and CIFAR-10 at r=q50r=q50 and q80q80, each figure shows one anchor per class with three same-label records inside the ball and three outside, together with their embedding distances. Inside q50q50, the protected alternatives are other instances of the class with similar coarse appearance, e.g., slanted, narrow zeros around a slanted, narrow zero, or aircraft photographed from below against a pale sky. Records outside the ball differ more in writing style or scene composition. The figures also show the limits of the policy: the label is not protected, and the boundary is defined in embedding space, so some records just outside it still resemble the anchor.

Q3 (radii). The radius is a design parameter chosen by the defender, like (ε,δ)(\varepsilon,\delta); in a deployment it is fixed in advance rather than estimated from the private records (Section 3.1). To span a range of policies, the experiments use the 50th, 80th, and 95th percentiles of same-label distances, computed on the public half of the test split, which is disjoint from the training data; the other half is the hold-out set. Embeddings are not normalized per record; they are rescaled by a single public factor so that ∣∣x∣∣2≤B=1|| x ||_2\le B=1. Table 8 shows that q50/2Bq50/2B ranges from 0.28 (MNIST) to 0.60 (IMDb) and q95/2Bq95/2B from 0.36 to 0.68. Distances concentrate (q95q95 exceeds q50q50 by 12–27%), but the noise reduction relative to 2B2B is a factor of 1.7–3.5 at q50q50.

Q4 (labels). The Standard-DP comparator uses the same label-preserving sensitivity at the global radius, so both mechanisms treat labels as public; cross-label replacements are protected by neither. Proposition 3.3 states the unlabeled Euclidean case, and Section 3.1 now says this explicitly. Protecting labels would require more noise for Standard DP, so our comparison favors the baseline.

AuthorsOpenReview ↗

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

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank the reviewers for their careful reading. We have uploaded a revised manuscript in which all changes are highlighted in blue; section, table, and figure numbers below refer to it. Three points were raised by several reviewers; we address them here and the remaining questions individually.

1. Relation to Blowfish and Pufferfish. We agree and have revised the paper accordingly. Without constraints, (r,ε,0)(r,\varepsilon,0)-Ball-DP coincides with Blowfish privacy under the distance-threshold policy with threshold rr, and hence, by Theorem 4.4 of He et al. (2014), with the corresponding Pufferfish instantiation over product distributions; our label-preserving metric removes the cross-label edges. Ball-DP extends this policy to (ε,δ)(\varepsilon,\delta). We now cite Blowfish, Pufferfish, and the SoK of Desfontaines & Pejó, and no longer present the definition as a contribution. Our contribution is the operational value of the definition against reconstruction:

  • Ball-ReRo certificates. We bound the attacker's reconstruction success relative to its oblivious baseline κ\kappa, via Ball-DP, Ball-RDP, and a direct Gaussian bound. These certificates do not follow immediately from the pairwise semantics of Blowfish or Pufferfish: two candidates in a ball of radius rr can be 2r2r apart, which costs e2εe^{2\varepsilon}, whereas comparing each candidate to the ball's anchor costs only eεe^{\varepsilon} (Theorem 4.5).
  • Gaussian calibration under approximate and Rényi DP for strongly convex ERM (Theorems 3.5–3.6, App. H.2). Blowfish considers pure DP with Laplace noise for sums, kk-means, and histograms. Beyond the radius, the Gaussian release keeps δ\delta fixed (Proposition 3.7), whereas chaining Blowfish's bound inflates δ\delta via group privacy.
  • An exact Bayes-optimal finite-prior MAP audit for the closed-form ridge-prototype head.

2. Accuracy versus reconstruction trade-off (Reviewers juLC, YKCa). We agree with juLC that only the q80q80 and Standard-DP bars of Figure 3 are attacked on identical supports, and that on these supports Ball-DP has higher exact-ID success (17 of 21 settings). The accuracy gain is therefore not free: it is the price of restricting protection to radius rr. Like (ε,δ)(\varepsilon,\delta), the radius is a design parameter chosen by the defender: it states how close to the true record a reconstruction may get before it counts as a breach.

To quantify this trade-off, we added a fixed-support audit (App. D): for each trial, we fix D−D^-, the prior, the 10 candidates, and the noise draw, and attack Ball-DP (q50q50) and Standard DP (2B2B, as in Table 1). Since accuracy and exact-ID success have different baselines and ceilings, we normalize both: ΔU=Δa/(a⋆−1/C)\Delta U=\Delta a/(a^\star-1/C) is the accuracy gain as a fraction of the range between chance and non-private accuracy, and ΔL=Δs/(1−1/m)\Delta L=\Delta s/(1-1/m) is the increase in exact-ID success as a fraction of the range between the oblivious baseline and a noiseless release. Averages over the four main-text benchmarks on the q50q50 support (Section 5.5; Table 4, Figure 7):

ε\varepsilonΔU\Delta U (accuracy)ΔL\Delta L (exact-ID success)
10.2450.016
20.2140.034
40.1090.067

At ε=8\varepsilon=8, ΔU\Delta U falls to 0.043. The benefit is therefore concentrated in the high-privacy regime ε≤2\varepsilon\le2, and we have restricted our claims accordingly (abstract, contributions, Introduction, Sections 5.4–5.5).

3. What does the radius protect? (Reviewers juLC, YKCa). The new App. E shows, for MNIST and CIFAR-10 at r=q50r=q50 and q80q80, same-label records inside and outside the ball for one anchor per class (Figures 8–11). Inside q50q50 are instances of the class with similar appearance (stroke style for digits; viewpoint, background, and color for CIFAR-10); records outside differ more in style or composition.

Summary of revisions (in blue in the revised manuscript).

  • Abstract, Introduction, contributions: Ball-DP as Blowfish's distance-threshold policy extended to (ε,δ)(\varepsilon,\delta); contributions are the certificates, calibration, and audits; empirical claims restricted to ε≤2\varepsilon\le2; revised MIA framing.
  • Introduction and Related Work: Blowfish, Pufferfish, the SoK, and Geo-indistinguishability.
  • Section 3.1: results hold for any metric satisfying Assumption 3.4; with the label-preserving metric, r≥2Br\ge2B gives DP with public labels.
  • Section 5: hold-out accuracy; the radius as the defender's design parameter; radii computed on a public split.
  • Section 5.4: shared supports in Figure 3. New Section 5.5 and App. D: fixed-support audit with the normalized trade-off (Tables 3–5, Figures 6–7); m=100m=100 on MNIST (App. D.1).
  • New App. E: policy radii and their ratios to 2B2B (Table 8), and records inside and outside the ball (Figures 8–11).
  • Section 7: obstacles for DP-SGD (composition of reconstruction robustness; unknown LzL_z).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.