Private Wasserstein Distance

The major weakness in this paper is that there is no formal privacy model and really no provable privacy guarantees. As far as I can infer, the intended privacy model is whether one party's data can be almost completely reconstructed. For the intended applications of federated learning or data market quality checks, that may be a very weak guarantee, as partial reconstruction of some records may be a significant breach (like in a medical database). Since one has to share an interpolating distribution (line 290), the choice of interpolated data points and coefficients (Eq 4) may leak significant information (for example it can be used to estimate t). To pass the bar, this paper needs a privacy model that is appropriate to its intended applications.

Another weakness is the paper is incredibly difficult to read. Some parts are notation-dense while other parts are handwavy. The notation is not always used consistently and not always defined. As a result, I may have not entirely understood everything. Examples include:

• #pi in Line 108
• Theorem 1 is not self-contained (for instance it doesn't define gamma or introduce sigma, so you have to keep looking elsewhere), the dependence of C on k is omitted in the big-O notation and is replaced by the vague non-quantitative "is negatively related to"
• The paper keeps switching between W, W_p, W^2 in an inconsistent use of notation. As p=2, there is no generality afforded by using p in the notation anywhere in the paper.
• Eq 9 sigma(pi*....) does not appear to be defined.
• Is corollary 2 missing text? Is it supposed to start as "Suppose each element of eta(mu) ..." or is there some other meaning to it?
• Corollary 1 appears to contradict the preceding discussion. First, "hat{W}_p(mu, nu) is an unbiased estimation " of what? of W(mu, nu)? How does it square with Eq 7 saying that it is as least as large (which, when combined with unbiasedness should mean that they are identical)?

1. In contrary to the contribution, the presentation sometimes feels a little too heuristic. It feels that some statements are not given formally, but are framed within discussions rather than theorems, which makes this paper less formal than it can be. For example (some were transformed into questions): a. The theoretical analysis section mainly consists of a discussion (only one theorem). I would expect elements such as complexity analysis, privacy analysis, etc, to be framed within formal statements.

2. While I think the broader applications are important, the authors do not present any specific results on experiment on them. I would therefore expect the discussion to be brief in the main paper, and elaborated on in the appendix.

technical:

1. I am not sure the citation format is good.
2. line 111 - ‘geodesic’ instead of ‘geodesics’
3. line 142 - ‘valuation’ - did you mean evaluation?
4. equation 6 should depepend in 't' somehow, it is not conveyed by the notation in any way.
5. line 188 - ‘6’ → ‘equation 6’
6. 196 - ‘computes’→’compute’
7. paragraph 187-199 is not easy to follow, while being crucial to the overall flow.
8. ‘proof is shown in appendix’ - refer to specific appendecies.
9. corollary 1 should be rewritten, perhaps in the sape of a list of conditions.
10. line 435 - ‘timeand’
11. line 938 - ‘our’ →’out’
12. 958-959- ‘worthy to note’→’noteworthy’

1. It appears that the method relies on certain assumptions, such as the availability of a global shared random distribution and the proportional relationship between interpolating measures. These assumptions might not be readily available in practical settings, potentially limiting the method’s applicability.

2. Although the paper discusses privacy benefits, it is unclear how much privacy can be guaranteed. The authors include some empirical analysis against some attacks. Is it possible to derive the privacy bound?

3. While the paper includes extensive experiments, it could benefit from more practical case studies that illustrate the real-world applicability of TriangleWad.

4. The presentation could be enhanced. The paper is dense with notations and formulas. It would be beneficial if the authors provided more intuitive explanations and practical examples.

1. There is no discussion about the privacy guarantee of the algorithm in a traditional view (such as Differential Privacy). In fact, the proposed algorithm is definitely not DP. It would be good to discuss whether there is a potential to convert the algorithm into DP with additional loss in accuracy.

2. The paper mainly focuses on W-2 Wasserstein distance. It would be good to clarify whether the algorithm still holds for other p. In practice, W-1 (i.e., Earth-Mover-Distance) is also important in practice.

3. The algorithm without leaking t is asymmetric, i.e., only one party does not reveal t, but the other party needs to reveal multiple t.

• The paper is not well-structured in my humble opinion. For instance, there are gaps between related questions and concerns (3.4 and then again 4.2.1), while a list of interesting but flow-breaking applications appear in the middle Section 3.5.

• Claims of improved privacy are not substantiated very well. The paper recognizes the issues with privacy claims but the arguments provided do not assuage validity concerns (empirical results are not proof of privacy). For instance

  • I think an attack similar to what authors present against FedWad (in Section 3.2) to learn $\mu$ from $\nu$ is possible. In fact, it seems the whole security argument comes from lack of iterations, and not the fundamental design of the proposed solution in Section 3.3

    • Page 8: TriangleWad does not calculate any interpolating measure between µ and ν, so the attacker can not use available information to identify the distribution of the raw data.

      This is a pretty weak argument. There are other pieces of shared information that the attacker can use. Including the shared $\gamma$ , and the fact that good performance is only possible when both parties have the same $t$ shows a pretty strong utility-privacy trade-off

  • 3.4 APPROXIMATE WASSERSTEIN DISTANCE WITH UNKNOWN t

    • The arguments in Section 3.4 are not satisfying in hiding the $t$ parameter. To me the only way to prove such a result, is to show that inverting (10) is not possible (which I have strong doubts on)

    • I do not have a concrete proof, but I believe you can construct seller distributions $\eta_{\nu_i} (s_j)$ such that you can invert the relationship can find $t_0$

• The formal presentation of the paper can be considerably improved. For instance,

  • Page 5: and it has a negative relationship with k

    • What does this mean in a formal proof?

  • Undefined Notation in $f_l^{\star}$ in eq.13. Lack of proper introduction of the "Monge" problem in the background.

• Empirical section shows improvement over the baseline but needs improvement. In particular,

  • I am skeptical of nearly all zero gaps reported in Table 1.

  • I was expecting a trade-off utility-privacy trade-off (for instance, as a result of the procedure in 3.4) however I do not think the method presented in Section 3.4 is validated in the empirical section at all.

  • None of the results have confidence intervals (or any other measure of uncertainty).

  • The paper relegating important empirical results to the appendix. For instance, the rather surprising result at the end of 4.2.2. (BTW, please include the full paper in the submission)

• Minor

  • The paper uses non-standard citations for ICLR

  • Bad formatting of citation as subject. For example on page 3:

    (11 ) proposes