- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the following problem: given a pair-wise distance matrix between the elements of a dataset, privately release all pairwise distances. Privacy follows the DP definition but introduces a ρ-neighrbor relation, such that the adjacent datasets have identical elements apart from one point that may change by at most ρ.
To do this, the paper proposes a simple approach: add Gaussian noise to each pair-wise distance, project the result into a pseudometric space (if necessary) and release the result. The paper shows that this achieves an optimal (up to logarithmic factors) error bound. Then it discusses applications in MSTs and clustering. Finally, it experimentally evaluates the additive error, the cost of projection and compares to Zou et al. for MSTs.
Critical strengths
-
Optimal Solution: The paper provides an optimal yet simple solution for the difficult problem of releasing the pair-wise distance metric. In other words, if one wishes to release all distances, the Gaussian mechanism is the natural and optimal approach. Moreover, the paper generalizes on any distance metric, instead of focusing on particular metrics as prior works.
-
Multiple instantiations: The paper discusses possible use cases (MSTs and clustering; with interesting lower/upper bound analysis) and provides different approaches with varying accuracy-privacy-running time trade-offs (Table 1).
-
Ablation on projection mechanisms: The paper evaluates with different projection mechanisms giving insights on which one is preferable.
Critical weaknesses
-
Limited Scalability: Modern ML applications require vast datasets. The proposed mechanism does not scale well as , the size of the dataset increases. For example: (a) the noise scales with , (b) Exponential complexity in some use cases, (c) faster (still polynomial) mechanisms degrade the acurarcy-privacy trade-off as increases (e.g. k-median recursive). I understand the difficulty of the problem but for an ML conference I find practically for ML tasks particularly important.
-
Limited novelty of the mechanism: The proposed mechanism is not novel: the paper combines the known Gaussian mechanism and largely known projections to pseudometric spaces. The main contribution lies on the theoretical side: the generalization of results to any metric space.
-
Insufficient evaluation: Evaluation focuses on small datasets and considers a single other work to compare against.
Questions for authors
Questions:
-
Does your mechanism scale well for modern ML tasks with increased ? If not, how (e.g. heuristics, approximations) can it be applied to larger datasets and with what cost in accuracy/privacy? Show running time, accuracy and privacy with the full MNIST/CIFAR-10 datasets.
-
How does your mechanism compare to Zou et al. with varying (instead of )?
-
Evaluate on other metrics against related work. For example, you can instantiate on different metrics and compare against "Perturb-and-Project: Differentially Private Similarities and Marginals" of V. Cohen et al. or "Optimal bounds for private mini-mum spanning trees via input perturbation" of Pagh et al.
-
The number of noise seeds is small: increase the number of seeds and report +- std.
Suggestions for future work/improvements:
-
To gain space, I would keep lines 434-437 and refer to Table 3 (placed in the Appendix) as justification. Table 3 evaluates different (known) design choices for the proposed instantiation.
-
Line 410: You have already assumed in Prop 2.1. and Theorem 1 that . Thus experiments with larger offer limited value as they do not match the theory.
3 comments
We report the additional experiments and address the evaluation questions below.
Experiments (Weakness and Q1)
The main computational cost in the image experiments is constructing the input distance matrix: each pair requires solving an optimal transport problem for the Wasserstein-1 distance. This cost also applies to non-private methods using the same input. To demonstrate this, we evaluated CIFAR-10 subsets with , with , , and three noise seeds.
All times below are in seconds. The noise column averages perturbation times across both methods and three seeds; MDS and Fréchet report mean repair times.
| Pairs | W₁ construction | Gaussian noise | MDS | Fréchet | |
|---|---|---|---|---|---|
| 2,000 | 1,999,000 | 57.459 | 0.034 | 1.116 | 0.406 |
| 5,000 | 12,497,500 | 424.570 | 0.198 | 29.613 | 19.528 |
| 10,000 | 49,995,000 | 1,613.153 | 0.863 | 243.513 | 160.211 |
At , nearly 50 million optimal transport computations take 1,613 seconds, versus less than one second for Gaussian perturbation and 244/160 seconds for MDS/Fréchet repair. Distance construction accounts for 87%/91% of the respective totals.
These results show that, once the distance matrix is available, the privacy step adds little computational overhead and is scalable. In fact, to our best knowledge, input perturbation is the most efficient mechanism in DP (comparing to exponential mechanism, DP-SGC, private multiplicative weight, etc.)
Comparison with Zou et al. for varying and Pagh et al. (Q2, Q3)
We originally fixed and varied because Zou et al.'s accuracy depends on through the JL projection, whereas ours does not. We have now added a comparison varying , using Zou et al.'s Euclidean generator with , , , and . We also compare with Pagh et al. as suggested. The table reports mean additive error over the exact original MST, with standard deviations across five repetitions.
| Ours: No repair | Zou et al. | Pagh et al. | |
|---|---|---|---|
| 100 | 979.4 ± 35.6 | 2,302.1 ± 225.4 | 2,396.6 ± 286.1 |
| 300 | 4,635.7 ± 152.4 | 6,454.6 ± 299.5 | 7,057.0 ± 381.5 |
| 500 | 7,283.9 ± 204.6 | 12,447.6 ± 1,018.0 | 12,700.2 ± 339.9 |
| 700 | 15,559.7 ± 617.3 | 19,952.7 ± 1,377.9 | 23,113.8 ± 516.9 |
| 1,000 | 21,247.4 ± 526.4 | 26,734.2 ± 1,038.3 | 31,139.5 ± 1,798.9 |
Our "No repair" variant (Gaussian perturbation followed by Kruskal) achieves lower mean excess tree weight than both baselines at every tested size. At , the reductions are 20.5% relative to Zou et al. and 31.8% relative to Pagh et al. The mean running times at were 0.064, 0.079, and 0.070 seconds, respectively for three methods.
Number of noise seeds
In the paper we already use three noise seeds and five repetitions, we will add the standard deviation. The above results are also obtained via the same setting.
Dear reviewer, As the author–reviewer discussion period ends today, we would appreciate hearing whether our response addresses your concerns. Thank you!
We thank the reviewer for the careful review and helpful comments. We address the theoretical and presentation questions below and report the experiments in a separate response.
We agree that an O(n) entrywise error becomes large for very large datasets. However, as the reviewer also notes, this rate is optimal if one wishes to release all pairwise distances by Theorem 2. The same is true for the downstream tasks, where our upper bounds are matched by lower bounds that also grow with n (Table 1). In this sense, the dependence on n comes from the privacy model, which cannot be treated as a weakness of our algorithms.
Regarding running time, we agree that the k-clustering algorithms based on exhaustive search take exponential time. We include them to show that input perturbation can achieve the tight bounds. For practical use, we also provide polynomial-time algorithms based on recursive metric compression (Table 1). Their additive error carries an extra nη factor for any fixed 0<η<1/2, at the cost of a larger constant approximation factor. We note that some growth in n is unavoidable here as well, by our lower bound.
We agree that the mechanism itself is not new, and we do not claim novelty for it. Our main contribution is the versatility: we show that one simple mechanism is already near-optimal for a range of problems on general metrics.
Establishing this requires a separate analysis for each problem. For the upper bounds, we need to control how the noise propagates through each post-processing step, e.g., through metric repair, or through the hierarchical clustering objective, where we use the fact that every tree has the same score on a unit-weight metric.
For the lower bounds, each problem requires its own hard instance, e.g., the two-star construction for MST and the planted structures for hierarchical clustering. These arguments build on standard tools, but we believe that adapting them to each problem is not trivial, and that the resulting near-tight picture is a useful contribution.
We thank the reviewer for the presentation suggestion and will consider moving Table 3 to the appendix while keeping the discussion in Lines 434–437.
For ε>1, our experiments use the analytic Gaussian calibration of Balle and Wang (ICML'18), which remains valid in this regime. We will clarify its distinction from the ε≤1 assumption in our stated bounds.