acceptodds
Under review as a conference paper at ICLR 2027

Matching under Metric Privacy

Abstract

We study minimum-total-distance matching between public and private points under local metric privacy. We compare perturbing original points, distance vectors, and a projected representation that preserves distances to the public candidates. We then correct the projected representation using one additional private distance. Its expected additional matching cost is , where , without distributional or boundedness assumptions on the private points. The correction controls errors in relative costs rather than individual locations. Two constructions reverse the ranking of projected and distance-vector reports, showing why reconstruction error alone does not explain matching quality. Synthetic experiments examine these comparisons and the tradeoff between public approximation and privacy noise.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
metric privacy, differential privacy, matching, assignment

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 4 reviews, above 27% of the others.
Reviewer_wuBvOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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.
  2. 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
AuthorsOpenReview ↗

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:

  • We supply a worst-case construction for all metric-private matching mechanisms and prove a theoretical lower bound on excess matching cost, thereby showing that Original point and Gumbel each obtain tight upper bounds in low- and high-dimensional settings, respectively.
  • We compare the mechanisms across 16 benchmark datasets and vary the sample size nn and data dimension dd to examine how their theoretical guarantees appear in practice.

Q1. Tightness, constants, and finite-size significance

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 nn and mm would also strengthen the result.

In Theorem 6, we prove that for every n≥2n\ge2, d≥1d\ge1, and ε>0\varepsilon > 0, there is a public set YY such that any εD\varepsilon D-private matching mechanism has a private input XX 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.
AuthorsOpenReview ↗

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 min⁡n,d\min\\{n,d\\} coordinates. Its excess-cost bound is 2ns/ε2ns/\varepsilon, where ss 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 2nlog⁡n/ε2n\log n/\varepsilon 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 ε\varepsilon from 0.250.25 to 1616. Those plots can be found in Appendix H.5, but we think it is most informative to see Figure 1 (top), which is at ε=8\varepsilon=8. 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 16.47716.477 on WDBC against Projected representation's 21.25621.256, and 16.72416.724 on Fashion-MNIST against 25.62525.625. Conversely, Wine favors the point mechanisms, with mean excess cost 16.43416.434 against Gumbel's 17.26517.265.

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.

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

The paper studies the problem of matching private data points with public ones while satisfying metric privacy. It examines three baseline approaches and proposed a new corrected projected representation approach. The idea is that, instead of focusing on preserving the true distance between public and private points, the paper argues that it is more important to preserve the differences between matching costs so that the right matching can be found more likely (even if the estimated distances may be much further from the real ones). The paper shows theoretically that the proposed scheme gives a better worst case bounds of the excess matching cost, which, however, does not translate to real utility gain in the experiments using pure synthetic data, when compared with some of the baselines.

Critical strengths
  1. The paper's insights about preserving relative matching costs instead of distances is insightful.

  2. The paper's scheme offers a better theoretical worst-case error bound.

Critical weaknesses
  1. The proposed scheme does not show consistent utility advantage over the baseline projected representation approach. In figure 2, the proposed scheme performs similar to or worse than the baseline. Figure 4 shows the proposed scheme's improvement under a particularly constructed data configuration, which does not convincingly show that the improved worst-case error bound translates into a meaningful utility gain in more general or practical settings.

  2. The paper's experiments are conducted exclusively on synthetic datasets. It would be helpful to also do experiments over real datasets, which will help better understand the performance differences between this paper's approach and the baselines.

  3. When showing the impacts of the privacy rate \epsilon, the paper varies \epsilon from 1 to 64 all the way to 256. Although the interpretation of \epsilon in metric privacy depends on the distance scale, it would be helpful if the paper could explain why these \epsilon values correspond to meaningful privacy protection in relevant applications.

  4. The experiments in figure 2 generate both the public and the private points in a four-dimensional subspace and then increase the total dimensions by appending zeros. This is particularly favorable for projection due to the used dimension reduction technique. It would be helpful to more systematically evaluate the proposed scheme when the public and private points have different high-dimensional structures, in particular when the public points do not have a strong low-dimensional structure.

Questions for authors

None

3 comments
AuthorsOpenReview ↗

Author's Response (1/2)

We appreciate the reviewer for their feedback. To address the weaknesses that they point out:

  1. We design a new mechanism, Gumbel matching, and prove its theoretical upper bound. We establish that the upper bounds for Original point and Projected representation are optimal on low-dimensional data (d≲log⁡nd \lesssim \log n) while Gumbel is optimal on high-dimensional data. Using real world datasets, we empirically validate their theoretical guarantee via experiments that vary the sample size nn and data dimension dd and show they are consistent.
  2. We compare all four mechanisms across 16 benchmark data sets and find that even across diverse distributions and dimensions, Original and Projected continue to dominate in low dimensions while Gumbel in high dimensions. Moreover, Gumbel retains this advantage in downstream applications, such as hypothesis testing, when data dimension is high.
  3. We add an appendix section describing both the theoretical and practical interpretation for ε\varepsilon, offering an explanation for going up to ε=16\varepsilon = 16.
  4. We revise our experiment for varying dimension; instead of appending zeros, we project downwards.

W1. Consistent utility advantage in general settings

The proposed scheme does not show consistent utility advantage over the baseline projected representation approach.

The reviewer’s concern motivated us to investigate Gumbel matching, which adds i.i.d Gumbel noise to all n2n^2 scalar distances. In Section 3.2, we describe this mechanism and prove

E[err⁡(σ^)]≤2nlog⁡nε.\mathbb{E}[\operatorname{err}(\widehat\sigma)]\le\frac{2n\log n}{\varepsilon}.

where err⁡(σ)=u(σ)−OPT⁡\operatorname{err}(\sigma)=u(\sigma)-\operatorname{OPT}. Recall that the Original point mechanism incurs an upper bound 2nd/ε2nd/\varepsilon (Theorem 2). By picking the mechanism with the smaller upper bound depending on dd vs. log⁡n\log n, together they incur

E[err⁡(σ^)]≤2nmin⁡d,log⁡nε.\mathbb{E}[\operatorname{err}(\widehat\sigma)]\le\frac{2n\min\\{d,\log n\\}}{\varepsilon}.

Through Theorem 6, we show that any mechanism can incur this error on some worst-case instance, proving its tightness.

Through experiments documented in Section 6.1, we vary the data dimension dd and sample size nn on Fashion-MNIST and Banknote dataset respectively.

  • From the trend in Figure 2 (a), we observe the “cross-over” between the Original point mechanism and Gumbel, where the former is better when d≲log⁡nd \lesssim \log n, while the latter when d≳log⁡nd \gtrsim \log n. In fact, Gumbel becomes exactly constant in dd as its upper bound suggests.
  • In Figure 2 (b), the true excess cost by the Point, Projected, and Gumbel mechanisms grow, but plateaus. For Point and Projected mechanisms, this is consistent with their theoretical bounds’ linear rate in nn (the plot’s y-axis is normalized by nn for visual ease). Gumbel’s cost curve appears to be either log⁡n\log n or even less, suggesting that it performs much better than its 2nlog⁡n/ε2 n \log n / \varepsilon upper bound on the Banknote dataset.

W2. Experiments on real datasets

It would be helpful to also do experiments over real datasets, which will help better understand the performance differences between this paper's approach and the baselines.

As part of the evaluation on 16 benchmark dataset, we vary ε\varepsilon from 0.25 to 16. Those plots can be found in Appendix H.5, but we think it is most informative to see Figure 1 (top), which is at ε=8\varepsilon=8. Here the datasets are ordered from lowest to highest in dimension. Similar to before, there is a trend where Gumbel continues to decrease in comparison to Original point, until it crosses over and becomes the best in high dimension (this happens on the ‘statlog’ dataset). Another observation is that Projected is always the better of the two in Original point and Distance vector, which validates its upper bound. Finally, even though both Gumbel and Distance are have upper bounds constant in dd, Gumbel incur lower excess cost, as its nlog⁡nn \log n upper bound suggests over Distance’s n2n^2. These are evidence for the distinct strengths of our mechanisms over the baselines.

In Section 7, we apply private matching with squared Euclidean costs to perform nonparametric two-sample hypothesis testing on Sonar, a real world high-dimensional dataset (d>log⁡nd > \log n). In Figure 3, we find that Gumbel is the strongest, able to achieve an average pp-value of 0.04630.0463. This suggests its low excess matching cost in high dimensions can translate to useful downstream applications.

AuthorsOpenReview ↗

Author's Response (2/2)

W3. Interpretation and calibration of ε\varepsilon

Although the interpretation of ε\varepsilon in metric privacy depends on the distance scale, it would be helpful if the paper could explain why these ε\varepsilon values correspond to meaningful privacy protection in relevant applications.

In Appendix B, we explain how ε\varepsilon depends on the distance scale: setting ε=log⁡c/r\varepsilon=\log c/r limits changes in output probabilities to a factor cc when inputs differ by distance at most rr.

Appendix B.2 gives a simple example. Suppose an attacker knows everyone's data and identities, except which of two known records belongs to which of two people. Before seeing the matching, either possibility is equally likely, so guessing succeeds with probability 5050\\%. Suppose we ask that observing the matching increase this probability to at most 7575\\%. If the two records are distance rr apart, it suffices to choose ε≤log⁡3/(2r)\varepsilon\le\log 3/(2r). The factor two accounts for exchanging both records.

On Sonar, the median distance between records is 1.77861.7786. The above requirement therefore calls for a small ε≈0.3\varepsilon\approx0.3. At ε=16\varepsilon=16, the same guarantee covers only distances up to 0.03430.0343. However, this is a very strong attack model. For a more realistic adversary with less side information, this can still provide useful privacy protection while preserving evidence for the two-sample test.

W4. Dimension scaling without zero padding

This is particularly favorable for projection…

In our revised experiments on Fashion-MNIST, we start with the full d=784d=784 and iteratively project down using random orthogonal projections. To keep the scale consistent at each dimension, we recenter and rescale so the pointset has an RMS of 1. This way, the experiment no longer favors the Projected point mechanism. This is described in Appendix H.2.

systematically evaluate the proposed scheme when the public and private points have different high-dimensional structures

Most of our selected benchmark datasets contain multiple labeled classes. For example, MNIST contains images of the digits 0–9. In each benchmark instance, we sample 128 records and form five different splits into 64 public and 64 private points. We do not use class labels when sampling or matching, so the two sides can contain different mixtures of classes. These repeated splits introduce variation in the class composition and geometry of the public and private point sets.

We look forward to the reviewer's thoughts on the revised manuscript.

AuthorsOpenReview ↗

Author's Follow-up

The reviewer questioned whether theoretical improvements translate into practical gains beyond specially constructed examples. Our 16 benchmarks now demonstrate a clear dimension-dependent advantage for different mechanisms, consistent with their theoretically optimal rates. The revised experiments in Figure 2 establish fair comparisons across varying dd while Appendix B provides a concrete calibration of ε\varepsilon. These results directly strengthen the case for a higher rating.

Reviewer_G7JnOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies matching for Euclidean points under local metric privacy. In particular, there are nn private points RR and nn public points QQ in Rd\mathbb{R}^d, and the goal is to compute a minimum-cost perfect matching between QQ and RR, where the cost of assigning public point qiq_i to private point rjr_j is ∥qi−rj∥2\|q_i-r_j\|_2. Each private point is released independently under local ϵ\epsilon-metric privacy, using only its own location and the public set QQ. The server then forms a perturbed cost matrix from the released reports and returns a minimum-cost assignment for this matrix. Utility is measured by the expected excess total matching cost over the non-private optimum.

The paper analyzes four mechanisms, though two of them are baselines. The first directly perturbs each private point with norm-Laplace noise and gives an expected excess cost bound of O(nd/ϵ)O(nd/\epsilon). The second releases a perturbed distance vector to all public candidates and gives a bound of O(n2/ϵ)O(n^2/\epsilon) for the p=∞p=\infty choice. The third projects each private point onto the public affine span and keeps the norm of the orthogonal component, which preserves all public-to-private distances and gives a bound of O(nmin⁡{n,d}/ϵ)O(n\min\{n,d\}/\epsilon). The fourth is a corrected projected representation: it subtracts squared distances to remove a shared noise term and releases one additional noisy distance to a selected public candidate. The proof of this corrected representation gives an expected excess cost bound of O(nmlog⁡(2n)/ϵ)O(n\sqrt{m\log(2n)}/\epsilon), where m=min⁡{k+1,d}m=\min\{k+1,d\} and kk is the dimension of the public affine span.

The paper also provides some constructions that compare the distance-vector and projected representations at the same public affine dimension. These examples show that the relative performance of the two representations can reverse depending on the geometry of the public and private points. Examples indicating that no single representation dominates for all point configurations.

Critical strengths

The theorems are clearly stated and correct.

Critical weaknesses

First, I have some concerns about the writing of this paper. I feel that several sections, especially the introduction, may have been generated with substantial AI assistance and would benefit from more human polishing. As it stands, the paper is somewhat hard to read and understand: the tone feels overly mechanical, the narrative lacks a human touch, and some sentences come across as obscure or hard to follow. I would like to point out a few examples:

  1. In the second paragraph, lines 30–35, the paper writes: "Differential privacy limits....the same privacy bound applies whether a record changes slightly or is replaced by a distant point. Metric privacy instead...." This reads as if metric privacy were not differential privacy, whereas it is in fact differential privacy with neighboring relations defined by Euclidean distance.

  2. The fourth paragraph begins with "A standard approach perturbs each point." This paragraph seems to introduce related work and motivate the optimization goal, but the writing makes it hard for me to grasp what prior work optimizes and why this is an issue in your setting. In particular, you write: "In Euclidean space, this approach minimizes mean squared reconstruction error among input-independent additive mechanisms satisfying the corresponding privacy constraint (Koufogiannis et al., 2015)." However, you do not define what "mean squared reconstruction error" is, nor what "the corresponding privacy constraint" refers to.

  3. In the fifth paragraph, beginning with "Optimizing the perturbation for utility offers a potential remedy...," the preceding sentences are really difficult to parse, for example, what is "expected service loss for a specified prior over a finite location set"? This sentence reads like a pile-up of things that are not explained in this context. It is not immediately clear to me how this relates to your problem. Furthermore, in this paragraph you write that "Matching loss instead depends on how all perturbed points are paired under the one-to-one constraint," yet you do not formally or informally define or motivate "matching loss" in advance, so this sentence is hard to follow.

  4. In the paragraph beginning with "Two observations guide our approach...," it would be helpful if you could elaborate more on your second point: "Second, when many pairings have similar costs, the optimizer can accommodate noise without paying much additional true cost."

Overall, I feel the introduction could be substantially improved and is not yet easy for a human reader to follow. In particular, since the problem is never formally defined in the introduction, everything from the fourth paragraph onward is hard to understand: it feels like you are motivating or selling something that has not yet been presented!

There are also some other places that seem a little strange besides the introduction. For example:

  1. On line 108, directly after Proposition 1, what is "At rate λ"? Was λ introduced anywhere before, or did I miss it? Also, why use the word "magnitude" instead of something like "noise"?

  2. In the statement of Theorem 3 (line 134), I do not see any point in writing p in the theorem statement; this parameter seems very redundant.

Second, the technical depth is a bit limited. Your first two algorithms are baselines; the third algorithm uses a nice observation that distances from a private point to a public point can be decomposed into the distances in the affine space spanned by the public points and a scalar vector, which reduces the dimension. This is nice, but I believe it was mostly inspired by (Narayanan & Nelson, 2019). I feel that the technical depth and contribution may fall short of the standard of a conference like ICLR, even in the old days without AI tools, let alone nowadays, when we can use AI to do proofs.

Narayanan & Nelson: Optimal terminal dimensionality reduction in Euclidean space, STOC '19.

Overall speaking, I feel this paper is not yet ready for publication until the introduction is thoroughly rewritten. With AI now being used to do math and write proofs, I feel it is even more important (and more the authors' responsibility) to make the writing more transparent to human readers so that we can learn from it well. In its current form, however, I do not think this paper accomplishes this.

Questions for authors

I do not have any questions whose answers could materially affect my assessment.

3 comments
AuthorsOpenReview ↗

Author's Response (1/2)

We thank the reviewer for their thoughtful and actionable feedback that has made it possible for us to significantly improve the clarity and depth of our manuscript.

In response to their concerns:

  • We introduce the research problem through stages—problem setting, research gaps, and contributions—to facilitate understanding of the technical ideas and communicate their importance.
  • We make additional technical contributions, including a worst-case lower bound for all metric-private matching mechanisms, Gumbel matching for central metric privacy, as well as extensions that make private matching applicable in nonparametric hypothesis testing.
  • We characterize the relationship between data dimension, matching cost, and the trust model under metric privacy.

W1. Presentation and problem motivation

Following the reviewer's suggestion, we have thoroughly rewritten the introduction section to improve its narrative and clarity.

  1. Make explicit that metric privacy extends differential privacy, in lines 035–039:

"Differential privacy protects against this by limiting how much the output distribution can change from an arbitrary replacement of any one data point (Dwork & Roth, 2014). Metric privacy extends this definition by scaling this limit on distinguishability with the distance between inputs: small changes in the input require small changes in the output distribution (Chatzikokolakis et al., 2013)."

  1. Define the optimization objective for matching, in lines 041–042:

"The goal is to release a matching σ:i↦j\sigma : i \mapsto j with small total matching cost ∑i∣xi−yσ(i)∣2\sum_i \\|x_i - y_{\sigma(i)}\\|_2 while satisfying metric privacy."

  1. Define reconstruction error and state its incompatibility with matching, in lines 054–059:

"...Laplace mechanism, which perturbs each point by x↦x+Zx \mapsto x + Z, for Z∼p(z)∝exp⁡(−ε∣z∣2)Z \sim p(z) \propto \exp(-\varepsilon\\|z\\|_2) (Hardt & Talwar, 2010; Chatzikokolakis et al., 2013). This mechanism satisfies metric privacy and notably minimizes the reconstruction error E[∣Z∣2]\mathbb{E}[\\|Z\\|^2] (Koufogiannis et al., 2015). While... suited to estimating aggregate statistics... matchings computed from them can incur substantial excess cost over the nonprivate optimum."

  1. Describe techniques using simple language that strengthens reader intuition, in lines 060–063:

"We observe that public points YY allow us to reduce the number of coordinates that require noise. Projecting the private points XX onto the affine span of YY and retaining their distances from that span preserves every distance between them. We can therefore…"

And in lines 064–067:

"When a trusted platform computes the matching, it can keep the private points internal and… We adapt Gumbel matching (Mena et al., 2018), based on the Gumbel-max trick, to add noise to n2n^2 edges rather than n!n! matchings."

  1. Remove the proof details, "Two observations guide our approach...," in favor of a result statement, for example, in lines 069–070:

"In addition, we construct worst-case instances of X,YX,Y that show our mechanisms attain the lowest asymptotic excess cost possible under metric privacy."

The proof is sketched after the formal statement in Theorem 6.

Other notation revisions and typos

  1. Clarify notation for the Laplace mechanism and Gamma distribution, in lines 131–133:

"When the norm is Euclidean, the noise decomposes as Z=RΘ\mathbf{Z}=R\boldsymbol{\Theta}, where R∼Gamma⁡(s,rate ε)R\sim\operatorname{Gamma}(s,\text{rate }\varepsilon) and Θ\boldsymbol{\Theta} is independently uniform on the unit sphere Ss−1\mathbb{S}^{s-1} (Awan & Slavković, 2021). For any chosen norm, the expected noise magnitude is E∣Z∣=s/ε\mathbb{E}\\|\mathbf{Z}\\|=s/\varepsilon."

  1. Correct typo from ∣⋅∣∞\\| \cdot \\|_\infty to ∣⋅∣p\\| \cdot \\|_p in Theorem 3.
AuthorsOpenReview ↗

Author's Response (2/2)

W2. Limited technical depth

A key contribution of our work is a problem formulation for private matching that lends itself to theoretical analysis and has practical applications. Comparing Original points, which adds Laplace noise directly to each point, with Distance vectors, which adds noise to each point's nn scalar distances to the public points, exposes the tradeoff between sample size nn and dimension dd through their upper bounds on excess matching cost, err⁡(σ)=u(σ)−OPT⁡\operatorname{err}(\sigma)=u(\sigma)-\operatorname{OPT}.

Using the projection technique of Narayanan & Nelson [1], we preserve all n2n^2 distances while adding noise to at most min⁡n,d\min\\{n,d\\} coordinates. The resulting excess cost bound is 2nmin⁡n,d/ε2n\min\\{n,d\\}/\varepsilon (Theorem 4), without explicitly switching between the two mechanisms to take advantage of the imbalance between nn and dd. Here, our contribution is to identify this representation as the right tool for private matching and establish its privacy and cost guarantees.

The potency of this formulation is further reflected in new results that we have established in our revision. We show that adding Gumbel noise to the same distance vector representation admits a tight performance guarantee under metric privacy (with matching upper and lower bounds). This essentially archives the same upper bound as the exponential mechanism, but with polynomial time complexity.

We point the reviewer to the revised manuscript for further details:

  • In Theorem 6, we construct a worst-case point set showing that every mechanism satisfying ε\varepsilon-metric privacy must incur E[err⁡(σ^)]=Ω!(nmin⁡d,log⁡nε)\mathbb{E}[\operatorname{err}(\widehat\sigma)]=\Omega\\!\left(\frac{n\min\\{d,\log n\\}}{\varepsilon}\right)
  • In Theorem 5, we prove that Gumbel Matching [2] is metric private and E[err⁡(σ^)]≤2nlog⁡nε.\mathbb{E}[\operatorname{err}(\widehat\sigma)]\le\frac{2n\log n}{\varepsilon}.
  • In Appendix G, we establish utility guarantees when the cost is Euclidean distance squared, ∣x−y∣22\\|x-y\\|_2^2. In Section 7, we apply private matching with squared Euclidean costs to perform nonparametric two-sample hypothesis testing [3] on a real world high dimensional dataset

These results characterize the optimal worst-case expected excess cost as Θ!(nmin⁡d,log⁡n/ε)\Theta\\!\left(n\min\\{d,\log n\\}/\varepsilon\right) and give a practical theory on data representation and the trust model. In low dimension, Original point already attains this bound with local metric privacy, allowing individuals to sanitize their data before submitting to an untrusted server. In high dimension, Gumbel matching attains this bound under central metric privacy, requiring a trustworthy server to receive the individuals’ unsanitized data. Therefore, the choice of embedding dimension for sensitive data depends directly on the trust model of the private matching application.

We look forward to the reviewer's thoughts on the revised manuscript.

[1] Shyam Narayanan and Jelani Nelson. Optimal Terminal Dimensionality Reduction in Euclidean Space. STOC, 2019.

[2] Gonzalo E. Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning Latent Permutations with Gumbel-Sinkhorn Networks. ICLR, 2018.

[3] Nabarun Deb and Bodhisattva Sen. Multivariate Rank-Based Distribution-Free Nonparametric Testing Using Measure Transportation. Journal of the American Statistical Association, 2023.

AuthorsOpenReview ↗

Author's Follow-up

The reviewer's initial rating rested on presentation and limited technical novelty. The introduction has been thoroughly rewritten, while our new lower bound and optimal Gumbel mechanism establish a fundamental relationship between data dimension and the local versus central privacy regimes. These results and techniques in our revision deserve another assessment.

Reviewer_WUPeOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies minimum-total-distance matching between public and private points under local metric differential privacy. It compares perturbations of original points, distance vectors, and a projected representation, then supplements the projected report with one privatized distance to improve cost reconstruction.

The main contributions are an upper bound on the expected additional matching cost and constructions demonstrating that projected and distance-vector mechanisms can reverse their performance ranking.

Critical strengths

This paper studies a task-specific private representation with an improved matching-cost guarantee. From theoretical aspect, it is interesting.

Critical weaknesses

My main concern is that the paper provides an upper bound on expected excess matching cost (Theorem 5), but I cannot find matching lower bound for the corrected mechanism or any empirical comparison between the bound and observed loss. I would consider raising my rating if the authors can address this concern.

The paper assumes that task locations are available to workers before they obfuscate their locations. While reasonable for publicly advertised tasks, this assumption may not hold in other spatial-crowdsourcing settings. For example, in To et al.’s framework (VLDB 2014), a trusted provider first releases a differentially private spatial index of worker locations, which the server then uses to select a region for geocasting task requests. Workers therefore do not need advance knowledge of the task set when their location data are obfuscated. It is more interesting to discuss whether/how the proposed method could accommodate this kind of workflow, as well as the settings in which task locations also need to be protected.

Questions for authors
  1. Could you provide a matching lower bound or an empirical comparison between the bound and observed excess matching cost?
  2. Can the method accommodate settings where workers obfuscate their locations before learning task locations? Also, can it support sensitive task locations, and what changes or additional assumptions would be needed?
1 comment
AuthorsOpenReview ↗

Author's Response

We thank the reviewer for their insightful questions about the necessity of a lower bound and the potential extensions useful for spatial task assignment.

To answer their concerns:

  1. We supply a worst-case construction for all metric-private matching mechanisms and prove a theoretical lower bound on excess matching cost (err(σ)=u(σ)−OPT\mathrm{err}(\sigma)=u(\sigma)-\mathrm{OPT}), thereby showing two of our mechanisms each obtain tight upper bounds in low- vs. high-dimensional settings respectively.
  2. We also empirically validate the asymptotic upper bounds by experiments that vary the sample size nn and data dimension dd.
  3. Finally, we explain how three of our mechanisms are applicable when task locations are also sensitive and give their upper bounds on excess matching cost.

Q1. Lower bound and comparison with observed excess cost

Could you provide a matching lower bound or an empirical comparison between the bound and observed excess matching cost?

In Theorem 6, we prove that for every n≥2n\ge2, d≥1d\ge1, and ε>0\varepsilon > 0, there is a public set YY such that any εD\varepsilon D-private matching mechanism has a private input XX on which it incurs:

=\Omega\\!\left(\frac{n\min\\{d,\log n\\}}{\varepsilon}\right).$$ Since the Original point baseline (adding Laplace noise to each private point in $x \in X$) has an upper bound $2nd/\varepsilon$ (Theorem 2), it is tight when $d < \log n$. This motivated us to ask whether another mechanism is tight when $d > \log n$. The answer is positive: we demonstrate the Gumbel matching in Section 3.2 does, achieving $$\mathbb{E}[\operatorname{err}(\widehat{\sigma})] =O\\!\left(\frac{2n \log n}{\varepsilon}\right).$$ Finally, we compared all mechanisms across 16 benchmark dataset; on two of which, Fashion-MNIST and Banknote, we vary the dimension $d$ and sample size $n$ to compare their true excess cost vs. their asymptotic upper bounds. We briefly describe the experiment design in Section 6.1, with details on data normalization at each step. From the results, plotted in Figure 2, we observe that: - As $d$ increases, the true excess cost by Original point mechanism (coinciding with Projected point mechanism) also increases, although below the upper bound’s linear rate. On the other hand, the excess cost by Gumbel matching follows its upper bound’s rate exactly up to scaling, becoming exactly constant after $d > \log n$. This is also the case with Distance vector, but with a higher constant. - As $n$ increases, the true excess cost by the Point, Projected, and Gumbel mechanisms plateaus. This is exactly the behavior for Point and Projected mechanisms as predicted by their upper bounds’ linear rate in $n$ (the plot’s y-axis normalizes by $n$ for visual ease). However, Gumbel’s cost curve appears to be either $\log n$ or even less, suggesting that it performs much better than its $2 n \log n / \varepsilon$ upper bound on the Banknote dataset. **Q2a. Privatization before task locations are known** > Can the method accommodate settings where workers obfuscate their locations before learning task locations? The Original point mechanism, which adds Laplace noise to each location, can be done without any knowledge of task locations. A later assignment computed from the sanitized locations and arriving public tasks is post-processing, thus preserving privacy. The problem setup in To et al. (2014) is different from ours in that the task locations arrive to the server one by one, so an assignment is attempted greedily and on-line. The problem we study is off-line bipartite matching, which requires the complete task set by definition. The problem without the task set is on-line matching, which uses substantially different definitions, like arrival horizon, regret, to even state even without privacy. Thus, it is not covered in our work. We raise this in the Discussion as an interesting future direction. **Q2b. Sensitive task locations** > Can it support sensitive task locations, and what changes or additional assumptions would be needed? In their current form, the Point, Projected, and Gumbel mechanisms can directly accommodate the privacy metric for protecting both $(X,Y) \in (\mathbb{R}^d)^{2n}$: $$D_{\mathrm{both}}\bigl((X,Y),(X',Y')\bigr) =D(X,X')+D(Y,Y').$$ In Appendix G.2, we give their excess cost upper bounds: | Mechanism | $\mathbb{E}[\mathrm{err}(\widehat\sigma)]$ | | --- | --- | | Original points | $4nd/\varepsilon$ | | Projected representation | -- | | Distance vectors | $4n^2/\varepsilon$ | | Gumbel | $2n\log n/\varepsilon$ | Original point and Distance vector doubles from because there are double the private points; Gumbel does not change because there are still $n^2$ pairs of distances. Finally, Projected representation cannot be used because it relies on $Y$ being public. We look forward to the reviewer's thoughts on the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.