On the Private Estimation of Smooth Transport Maps

Dear Reviewer,

We sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.

• Comment 1: The authors establish statistical guarantees for the proposed private transport map estimator. However, there is a lack of insight and clarification regarding these bounds, [...] and more detailed explanations.

  Response: We would like to point out that we included elements addressing this question between lines 359 and 362, where we exhibit the regime in which any private algorithm, regardless of the specifics, will necessarily experience performance degradation. We will enhance the discussion after Theorems 4.3 and 5.1 to better explain the bounds in different regimes. For instance, our upper bound recovers the usual optimal rate of estimation in the limit $\varepsilon \to \infty$ (i.e., no privacy). In the regime of high smoothness ($\alpha \to \infty$), we can see that a constant privacy budget does not affect utility. In intermediate regimes, we will ensure to detail this point using the inversion formula.

• Comment 2: However, the method is not novel; it is a routine development that combines Differential Privacy (DP) with existing transport map estimators.

  Response: Our work indeed combines existing transport map estimators with an established Differential Privacy mechanism, but its statistical analysis requires a careful link between these two components, which we believe results in a valuable contribution. The slight mismatch between our upper and lower bounds (which does not exist in non-private transport map estimation) arises as a direct consequence of the additional challenges posed by privacy constraints. A significant portion of the differential privacy literature consists of applying standard mechanisms (e.g., Gaussian, Exponential, etc.) to prescribed quantities, but the challenge lies in quantifying the utility of such procedures.

• Comment 3: The performance of the privately estimated map compared to the true map is shown in Figure 2. Although the estimated map visually appears close to the ground truth, there is no quantitative measure to assess the estimation error and confirm its optimality & The figures appear to show results from only a single run [...]

  Response: Our work is primarily theoretical in nature, and the experiments are mainly illustrative of the soundness of our approach. We will add a numerical figure of merit that measures the estimation error (e.g., the $L^2$ error between the two maps as a function of $n$). We can also include the standard deviation when averaging over multiple runs. However, we want to emphasize that the experiments serve to demonstrate that the proposed method is effective, at least in a toy example. The main contribution of the paper is to establish the first statistical bound for the problem at hand.

• Comment 4: To address privacy concerns, it could be interesting to evaluate the performance of the estimator in cases where the underlying distribution is heavily skewed.

  Response: We are unsure of what the reviewer means by "skewed" in this context. If "skewed" refers to cases where some regions have a high probability mass while others are nearly empty, this is indeed an interesting question. However, this scenario is excluded by our assumptions (see Definition 2.1), as it induces instabilities in the estimation procedure, even in the absence of privacy constraints. We believe this is a valuable question for future empirical research, but it is outside the scope of the current paper.

We would be happy to discuss any remaining questions during the author-reviewer discussion phase.

Dear Reviewer,

We sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.

• Comment 1: I could add that it would be nice to see which components of the bounds seem to dominate in which regimes over particular dimensions, sample sizes, etc. Not vital, in my opinion, however.

  Answer: We thank you for the suggestion. Since this point was raised in other reviews, we propose to extend the discussion in the relevant paragraph. For instance, our upper bound recovers the usual optimal rate of estimation in the limit $\varepsilon \to \infty$ (i.e., no privacy). In the regime of high smoothness ($\alpha \to \infty$), we can see that a constant privacy budget does not affect utility. In intermediate regimes, we will ensure to detail this point using the inversion formula.

• Comment 2: If I had to level one clarity complaint, it's that I would have included a few words about the construction of the finite covering family, namely how one maintains convexity of the functions.

  Answer: The construction of the covering (detailed in Section E.2) maintains convexity via the algorithm developed in lines 1194-1200. Alternatively, since the set of potentials of interest is closed and convex in a Euclidean space, it is possible to replace the presented procedure with a projection step, which is contractive and would allow us to gain a factor of $2$ in the constant.
  We emphasize that this construction mainly makes sense from a theoretical point of view in order to obtain the statistical upper bound. In practice, this construction can be challenging, and we recommend checking the convexity of the candidate potentials beforehand.

• Comment 3: Also, for reproduction's sake, it would be quite nice to include an implementation of the practical algorithm for the research community.

  Answer: We thank the reviewer for the suggestion. We will include the link to the code on our GitHub in the final version of this article.

• Comment 4: Explanation of rating: I found the paper to provide an interesting look at a heretofore unexplored problem. I did not give a higher rating than borderline accept, as it was unclear to me if the method is practically useful. For the one example displayed in Figure 2, I was surprised to see the degree of disagreement, given the use of $n=200000$ points. Additionally, I was a bit unsure of the degree of novelty in the theoretical construction, given that it builds so strongly off of a typical DP mechanism and the work of [Hutter and Rigollet 21].

  Answer: The degree of disagreement in Figure 2 is an artifact of the evaluation rather than of the estimation. We will update the figure with more precise evaluation and add figures of merit for the disagreement. Since the empirical evaluation was also pointed out by other reviewers, we plan to add to the final version a figure representing the error as a function of $n$, the sample size, as well as error bars.

  Regarding the degree of novelty in the theoretical construction, we refer to our response to Reviewer tgzq. For instance, the additional error related to privacy has to be precisely controlled in the estimation; this is the purpose of Lemma 2.5, which is crucial to linking smooth map estimation and the differentially private component.

  When it comes to practical applicability, we believe that our method should be split into two parts: an exploration phase and a selection phase. The exploration phase (the covering construction) can be challenging for practical problems. However, the selection phase (via the empirical semi-dual criterion) is perfectly applicable in practical scenarios where a prescribed set of candidate potentials has been suggested beforehand (e.g., via prior information).

We would be happy to discuss any remaining questions during the author-reviewer discussion phase.

Dear Reviewer,

We sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.

• Comment 1: These works look at the problem of private distribution estimation under Wp and were not included. I think they have tight rates and some efficient algorithms.

  Answer: We thank you for the suggested references and will include them in the relevant body of literature. After reviewing them, they unfortunately do not seem to exploit smoothness, which means they will probably not lead to better rates for our problem. However, it is possible that their numerical performance is stronger than that of the presented method.

• Comment 2: I think the novelty/significance [...] conference like COLT.

  Answer: Yes, the problem may seem a bit niche, but it still has some practical interest. The estimation of transport maps plays an important role in practical applications. Ensuring the privacy of such transport maps is particularly beneficial in applications involving the infringement of fundamental rights, such as bias analysis in machine learning algorithms. For instance, in [1] and [2], OT maps enable counterfactual analysis of discrimination. For a discussion about matching upper bounds, see our comment about the use of density estimators later in our response.

• Comment 3: I'm sure there is a simple reason why you use the extended domain $\tilde{\Omega}$ over $\Omega$, but I didn't see any discussion. Could you be explicit about that?

  Answer: In a nutshell, this is a consequence of estimating the transport map through smooth Brenier potentials: as the transport map is constructed as the gradient of the potential $T=\nabla f$, $f$ must be defined on a larger domain than $\Omega$ so that the gradient exists everywhere there. Thus, this is not linked to differential privacy but rather to transport map estimation through potentials. In fact, $\tilde{\Omega}$ could be chosen arbitrarily as long as $\Omega$ is included in its interior and it is a hypercube. The hypercube constraint arises from the support adequation condition described in Appendix A.

• Comment 4: It would be nice if the proof of Lemma 2.5 was split into a lemma capturing the needed argument from Hütter & Rigollet and then your own contribution.

  Answer: In the present proof, we try to clarify what is relevant for privacy and what simply follows the steps of Hütter & Rigollet. Unfortunately, since their result uses more advanced concentration tools than a uniform bound, we did not find a way to split the lemma in a way similar to a triangular inequality. Instead, we had to track the propagation of suboptimality in their proof and make the necessary measurability assumptions. We can add a remark after the result detailing which terms come from Hütter and Rigollet and which terms pertain to privacy.

• Comment 5: What about first doing private density estimation to obtain estimates $\hat{P}$ and $\hat{Q}$ that are accurate under $W_2$, then computing a smooth map for the $W_2(\hat{P}, \hat{Q})$... well studied under smoothness.

  Answer: Indeed, the approach proposed by the reviewer is sound. In fact, private density estimation has even been studied under smoothness (see [5]) for the $L^2$ loss with optimal rates. Furthermore, [4] demonstrated that density estimators can be used as suggested if they are sufficiently precise in $W_2$ distance. However, two problems arise: (i) the estimation must be in $W_2$ distance and not $L^2$, though we are confident that this should not be a problem as the techniques appear to be manageable with privacy, and (ii) it requires extra smoothness assumptions on the source and target distributions (on top of those on the map), limiting the applicability of the method. While this method is likely to yield optimal rates (at least in the one-sample setting where $P$ is known), we aimed to study the problem under the purest set of hypotheses. We can add a remark about this direction in the article.

• Comment 6: Can you resolve the complexity of this problem in 1D? Here, the connection to quantile functions should considerably simplify the problem.

  Answer: In 1D, it should be possible to import results from quantiles/CDFs since the transport map is known, but it is unclear whether this will be optimal.

We would be happy to discuss any remaining questions during the author-reviewer discussion phase.

[1] Transport-based counterfactual models, De Lara et al., JMLR 2024
[2] Fliptest: Fairness testing via optimal transport, Black et al., CFAT 2020
[3] Plugin estimation of smooth optimal transport maps, Manole et al., Annals of Stats., 2024
[4] Discrete Wasserstein barycenters: Optimal transport for discrete data, Anderes et al., Mathematical Methods of Operations Research 2016
[5] Privately Estimating Smooth Distributions on the Hypercube by Projections, Lalanne et al., ICML 2024

Dear Reviewer,

We sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.

• Comment 1: Only toy experiments are presented to illustrate how the proposed transport maps are close to the optimal ones. Unfortunately, these synthetic illustrations might not reflect practical performance, especially for modern high-dimensional ML problems. & Any plans to include experiments with real datasets or more realistic ML settings where DP OT maps are needed?

  Response: The experiments in the paper are primarily intended to illustrate the theoretical soundness of our approach. Specifically, the private estimator we consider has the advantage of yielding tractable statistical bounds. However, it may not be the most efficient choice from a numerical standpoint. This observation extends to minimax estimation of transport maps in general (even without privacy constraints), where entropic approximation performs best in practice but remains theoretically challenging. Exploring this further is an interesting direction for future research. To clarify the practical scope of our work, private maps can be used in fairness applications, for measuring population flux, and in other domains where transport maps may contain sensitive information on individuals.

• Comment 2: The theoretical analysis and presentation are clean, with transparent assumptions. The minimax bounds resemble those in (Hutter & Rigollet, 2021) with an additional differentially private term. However, this additional term is not tight, and the interaction between the privacy mechanism and function approximation remains somewhat unclear.

  Response: Privacy introduces an extra variance term, the magnitude of which depends on the dimension of the function approximation space. This same space also controls the bias of the estimation procedure, with its dependence tuned by smoothness. Consequently, the dimension of the functional space serves as a cutoff parameter that balances the bias-variance tradeoff. We will expand the discussion following Theorem 4.3 to clarify the different regimes of the bound and how the private bound differs from the classical case.

• Comment 3: Assuming the function class $\mathcal{F}$ is parameterized in a finite-dimensional space, and once the problem is formulated using empirical distributions, the semi-dual problem becomes a finite-dimensional convex optimization problem. Differentially private (DP) algorithms for convex optimization already exist and could, in principle, be applied directly.

  Response: Indeed, as noted, the problem is convex in $f$ and Lipschitz, and we have explored this direction. However, a key difficulty arises because $f^*$ (the Fenchel conjugate appearing in the optimization problem) does not have a closed-form expression in terms of the coefficients, nor does its gradient. Additionally, we were unable to establish gradient smoothness or strong convexity, which excludes the suggested references. Furthermore, the absence of strong convexity means that DP-SGD techniques are not in their most favorable cases. Adding regularization could improve this but such biased techniques fall out of the scope of this article. That said, since the objective function is convex and Lipschitz-continuous (see Eq. (40), where we establish a Lipschitz constant scaling as $2^{Jd/2}$), it is almost everywhere differentiable. This suggests that gradient-based optimization might be possible, (although computing $\nabla_{\text{coeffs}} f^*$ remains challenging). Whether such an approach would yield a favorable utility-privacy tradeoff remains an open question.

• Comment 4: The choice of the constant $J$ and the finite function set $C_{J,M}$ remains unclear throughout the paper. It is difficult to track how these quantities are selected, particularly since $J$ appears to depend implicitly on the dimension $d$ without an explicit derivation. Additionally, the "constant" $R$ is not formally defined (I couldn't find it), making it challenging to understand its role in function space discretization. Theorem 4.3, which should clarify these constants, does not explicitly detail their dependence, even in the proof. This lack of clarity significantly impacts the practical implementability of the proposed method.

  Response: The introductory paragraph of Section 2 clarifies what is considered a constant and what is not. Specifically, we precisely track all factors involving $J, n, \varepsilon$. The parameter $R$ controls the level of $\alpha$-smoothness, as defined in Equation (4). We will revise the relevant paragraph to make this clearer. For practical applications, as discussed in Section 6, we recommend selecting a set of candidate potentials and using our method as a selection tool.

We would be happy to discuss any remaining questions during the author-reviewer discussion phase.