- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies minimum-cost bipartite matching between public and private points under local metric privacy. The authors compare several private representations and propose a corrected projected representation that releases an additional privatized distance to a selected public point. The proposed method improves the expected additive matching-loss bound from O(nm/\varepsilon) to O(n\sqrt{m\log n}/\varepsilon). The paper also provides theoretical constructions and synthetic experiments to compare the mechanisms.
Critical strengths
- The proposed correction improves the dimension dependence of the worst-case matching-loss bound while preserving local metric privacy, without boundedness or distributional assumptions on private points.
- The paper provides constructions demonstrating that different private representations can have substantially different matching losses, including a provable asymptotic advantage for the corrected mechanism in a particular setting.
Critical weaknesses
- When m=\Theta(n), the bound remains O(n^{3/2}\sqrt{\log n}/\varepsilon), and even the average excess-cost upper bound grows with n. The paper does not establish whether this dependence is necessary or whether the improved bound provides meaningful guarantees at practical problem sizes. The absence of a corresponding lower bound makes it difficult to assess the significance of the theoretical improvement.
- The corrected mechanism does not consistently outperform the simpler projected baseline. While it shows substantial gains in a specially constructed setting, the improvements in other configurations are limited or absent.
Questions for authors
- The theoretical improvement is asymptotic, but its finite-sample significance remains unclear. A comparison of the explicit bounds, including constants, at the evaluated problem sizes would help assess the actual strength of the guarantee. Clarification on the tightness of the dependence on n and m would also strengthen the result.
- The corrected mechanism does not always outperform the simpler projected baseline. While it performs well in the specially constructed setting, the gains in other experiments are relatively modest. It remains unclear when the additional correction is worth the extra privacy budget.
2 comments
Author's Response (2/2)
Q2. When the additional complexity is useful
The corrected mechanism does not always outperform the simpler projected baseline. It remains unclear when the additional correction is worth the extra privacy budget.
The revised comparison focuses on mechanisms with distinct strengths in data representation and the trust model. Projected representation preserves all public-to-private distances while adding noise to at most coordinates. Its excess-cost bound is , where is the number of retained coordinates (Theorem 4). This takes advantage of a low-dimensional public affine span while allowing individuals to sanitize their data before submitting it to an untrusted server.
For high-dimensional matching, we use Gumbel matching, which adds Gumbel noise to the same distance-vector representation and achieves the bound above. It requires no additional distance report to a selected public candidate or split of the privacy budget between that distance and a point report. Instead, it uses a trusted server that receives the private points and releases only the matching.
As part of the evaluation on 16 benchmark datasets, we vary from to . Those plots can be found in Appendix H.5, but we think it is most informative to see Figure 1 (top), which is at . Here the datasets are ordered from lowest to highest in dimension. There is a trend where Gumbel improves in comparison to Original Point and becomes the best on the high-dimensional benchmarks. For example, Gumbel gives mean excess cost on WDBC against Projected representation's , and on Fashion-MNIST against . Conversely, Wine favors the point mechanisms, with mean excess cost against Gumbel's .
These comparisons give a practical theory on data representation and the trust model. In low dimension, Original Point already attains the optimal error order with local metric privacy. In high dimension, Gumbel matching attains this order under central metric privacy. Projected representation further reduces the number of coordinates requiring noise when the public affine span permits it. The choice of mechanism therefore depends on the dimension and geometry of the data and whether the application has a trusted server.
We look forward to the reviewer's thoughts on the revised manuscript.
Author's Response (1/2)
We thank the reviewer for their questions about the tightness of the bounds and the practical choice of mechanism. To answer their concerns:
Q1. Tightness, constants, and finite-size significance
In Theorem 6, we prove that for every n≥2, d≥1, and ε>0, there is a public set Y such that any εD-private matching mechanism has a private input X on which it incurs
\geq \frac{n\min\\{d,\log n\\}}{256\varepsilon},$$ where $\operatorname{err}(\sigma)=u(\sigma)-\operatorname{OPT}$. Since the Original point baseline has an upper bound $2nd/\varepsilon$ (Theorem 2), it is tight when $d\le\log n$. Gumbel matching achieves the upper bound $2n\log n/\varepsilon$ (Theorem 5), which is tight when $d > \log n$. By picking the mechanism with the smaller upper bound depending on $d$ vs. $\log n$, together they incur $$\mathbb{E}[\operatorname{err}(\widehat{\sigma})] \le\frac{2n\min\\{d,\log n\\}}{\varepsilon}.$$ These results characterize the optimal worst-case expected excess cost as $\Theta\\!\left(n\min\\{d,\log n\\}/\varepsilon\right)$. Dividing by $n$, the upper bound on average excess cost per pair is $2\min\\{d,\log n\\}/\varepsilon$. At fixed dimension, this becomes independent of $n$ once $\log n\ge d$. Even when the public affine dimension grows with $n$, Gumbel's average excess-cost bound is only $2\log n/\varepsilon$. We also compare the explicit bounds with observed excess cost at the evaluated problem sizes. For example, in the Fashion-MNIST sweep at $n=800$, $d=4$, and $\varepsilon=16$, the Original Point bound is $400$, compared with an observed mean excess cost of $76.365$ and a mean excess cost of $840.827$ for a uniformly random matching. Table 11 lists the explicit bound, observed excess costs, and random reference at every evaluated dimension. Through experiments documented in Section 6.1, we vary the data dimension $d$ and sample size $n$ on Fashion-MNIST and Banknote, respectively. In Figure 2 (a), the point mechanisms become less accurate as dimension grows, while Gumbel approaches a dimension-independent plateau. In Figure 2 (b), the average excess costs of the point mechanisms and Gumbel gradually flatten as $n$ increases. These experiments show how the dependence on dimension and sample size appears on real data, while the lower bound establishes its worst-case necessity.