On the Private Estimation of Smooth Transport Maps
Authors: Clément Lalanne
Franck Iutzeler
Jean-Michel Loubes
Julien Chhor
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Optimal Transport
Statistics
Primary area: social_aspects->privacy

Abstract: Estimating optimal transport maps between two distributions from respective samples is an important element for many machine learning methods. 
To do so, rather than extending discrete transport maps, it has been shown that estimating the Brenier potential of the transport problem and obtaining a transport map through its gradient is near minimax optimal for smooth problems. 
In this paper, we investigate the private estimation of such potentials and transport maps with respect to the distribution samples.
We propose a differentially private transport map estimator with $L^2$ error at most $n^{-1} \vee n^{-\frac{2 \alpha}{2 \alpha - 2 + d}} \vee (n\epsilon)^{-\frac{2 \alpha}{2 \alpha + d}} $ up do polylog terms where $n$ is the sample size, $\epsilon$ is the desired level of privacy, $\alpha$ is the smoothness of the true transport map, and $d$ is the dimension of the feature space. 
We also provide a lower bound for the problem.

On the Private Estimation of Smooth Transport Maps
Clément Lalanne' Franck Iutzeler'
Jean-Michel Loubes 21 Julien Chhor
Abstract
textbooks (Villani, 2003; Villani et al., 2009; Santambrogio, 2016; Peyré & Cuturi, 2019) for a general introduction to optimal transport and its computational aspects.
Estimating optimal transport maps between two distributions from respective samples is an impor- tant element for many machine learning methods. To do so, rather than extending discrete transport maps, it has been shown that estimating the Bre- nier potential of the transport problem and obtain- ing transport map through its gradient is near minimax optimal for smooth problems. In this pa- per, we investigate the private estimation of such potentials and transport maps with respect to the distribution samples. We propose differentially private transport map estimator achieving an L error of at most n -1 n 2a-2#a (ne) 20-4 up to poly-logarithmic terms where n is the sam- ple size, e the desired level of privacy, o is the smoothness of the true transport map, and d is the dimension of the feature space. We also provide lower bound for the problem.
Because its utility in measuring geometrical discrepancies between measures, and because of recent algorithmic devel- opments (Cuturi, 2013; Altschuler et al., 2017: 77: Dvurechen- sky et al., 2018), it has become standard tool in Computer Science (Feydy et al., 2017; Lavenant et al., 2018; Solomon et al., 2015; 2016), Machine Learning (A (Alaux et al., 201 8; Alvarez-Melis et al., 2018; Arjovsky et al., 2017: Cañas Rosasco, 2012; Gordaliza al., 2019; Flamary et al., 2018; Genevay et al., 2018: Grave al., 2019; Janati et al., 2019; Montavon al., 2016; Schmitz al., 2018; Staib al., 2017: Le et al., 2024) and Statistics (del Barrio et al., 2024;
Del Barrio et al., 2024; Cazelles et al., 201 8: del Barrio et al.,
2019; Klatt et al., 2020; Kroshnin et al., 2019; Panaretos & Zemel, 2019; Ramdas et al., 2017; Rigollet Weed, 2018; Seguy & Cuturi, 2015; Tameling & Munk, 2018; Weed Berthet, 2019: Zemel Panaretos, 2019).
When dealing with real-world data, the true distributions P and Q are often accessible only through samples (Courty et al., 2017a; 2014; 2017b; Damodaran et al., 2018; Forrow et al., 2019; Perrot et al., 2016; Seguy et al., 2018; Hütter & Rigollet, 2021). In this article, we suppose that we have access to
1. Introduction
Given two probability measures P, on Rd,, the question of "how to optimally move the mass" from P to Q, i.. to find a map To Rdd - Rd that solves the Monge (Monge, 1781) problem
Lid. X X X ~ P and Yi...., Yn
Lid. ~
Q
/ J2d s.t. Ty P
To E argmin
- ([([)>=<]<PPp)
(1)
such that the X,s and the Y,s mutually independent.' ! In this scenario, the problem (1) cannot be solved directly to ob- tain an optimal transport map; instead, it must be estimated using the available samples. To do so, a crude approach would be to replace P and Q with their empirical counter- parts. This approach has two main drawbacks: first, it does not specify how move points across the entire support of P; second, it is affected by the curse of dimensionality (Niles-Wee Weed & Rigollet, 2022). To resolve these issues, (Hütter & Rigollet, 2021) proposed incorporating smooth- ness and regularity assumptions into the optimal transport map To and leveraging functional estimators.
where Ty P denotes the push-forward of P by T is of high interest in both theoretical and more numerical branches of mathematics. The problem is referred to as an Optimal Transport Problem, and the optimal mapping To is referred to as the Optimal Transport Map: we refer the reader to the
"Institut de Mathématiques de Toulouse, UMR5219, Uni- versité de Toulouse, CNRS, UPS, F-31062 Toulouse Cedex 9, France FINRIA. France 'Toulouse School of Economics, Uni- versité Toulouse Capitole, France. Correspondence to: Clément Lalanne <element.lalanee @ math.uniy www.uuiiioooous.ff......
For simplicity, we take the same number of samples for both distributions. Our results naturally extend to the case where the two sample sizes different, the cost of using more involved notation.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Private Estimation of Smooth Transport Maps
At the same time, deriving estimators from real user data raises new challenges, especially regarding privacy. It is well-documented that sharing statistics based such data without adequate protections can lead to serious privacy leakages (Narayanan & Shmatikov, 2006; Backstrom et al., 2007; Fredrikson et al., 2015; Dinur & Nissim, 2003; Homer et al., 2008; Loukides et al., 2010; Narayanan & Shmatikov, 2008: Sweeney, 2000; Wagner& & Eckhoff, 2018: Sweeney, 2002).
1.2. Related Work
Differential Privacy and Statistics/Learningg Over the past decade, there has been growing interest in estimating various quantities while ensuring differential privacy. Ex- amples of relevant works include, but are not limited to, the following references (Wasserman & Zhou, 2010; Bar- ber & Duchi, 2014; Diakonikolas et al., 2015; Karwa & Vadhan, 2018; Bun et al., 2019; 2021; Kamath et al., 2019; Biswas al., 2020; Kamath et al., 2020; Acharya al., 2021; Lalanne, 2023; Aden-Ali al., 2021; Cai et al., 2019;
In the context of transport maps estimation, ensuring privacy is highly beneficial for applications involving infringement of fundamental rights as in bias analysis of machine learn- ing algorithms. For instance, in (De Lara et al., 2024) or (Black et al., 2020), optimal transport maps enable to build counterfactual individuals assess whether an algorithm is prone to discrimination and to mitigate its effect.
Brown et al., 2021; Cai et al., 2019; Kamath et al., 2022a; Lalanne et al., 2023c;d; Lalanne & Gadat, 2024; Singhal, 2023; Kamath et al., 2023; 2022b).
More specifically, this article falls into the scope of private nonparametric statistics (Tsybakov, 2009), where the quan- tities of interest live in infinite dimensional vector spaces, necessitating the use of approximation techniques along- side estimation. The problem of non-parametric density estimation under differential privacy has been studied in various works (Wasserman & Zhou, 2010; Barber & Duchi, 2014; Lalanne et al., 2023b; Lalanne & Gadat, 2024), both in the setting of this article and the setup of local pri- vacy (without a trusted server) (Evfimievski et al., 2003; Kasiviswanathan et al., 2008; Duchi et al., 2013; 2016; Bu- tucea et al., 2019; Kroll, 2021; Schluttenhofer & Johannes, 2022; Györf & Kroll, 2023). Additional works include studies on nonparametric regression (Berrett et al., 2021; Györfi & Kroll, 2022), nonparametric tests (Lam- (Lam-Weil et al., 2022), interactions between robustness and privacy (Chhor & Sentenac, 2023) and recent advances in locally private Bayesian modeling (Beraha al., 2023).
To mitigate these concerns, differential privacy (DP) (Dwork et al., 2006) has become the benchmark to ensure privacy protection. DP introduces randomness into computations, ensuring that the released statistics are determined not solely by the dataset but also by the added randomness. This lim- its the influence of any single data point on the outcome, thereby preserving privacy. Major organizations, includ- ing the US Census Bureau (Abowd, 2018), Google (Er- lingsson et al., 2014), Apple (Thakurta et al., 2017), and Microsoft (Ding et al., 2017), have embraced this methodol- ogy.
This work investigates the problem of estimating smooth optimal transport maps from samples under differentially privacy. In particular, we prove that the optimal estimation rate is expected to degrade under specific regimes.
To the best of our knowledge, our work is the first to address private estimation of smooth transport maps with statistical guarantees. A noteworthy exception is the article (Xian et al., 2024) which uses elements of optimal transport in a private way in order to obtain fairness with statistical guarantees. Their approach is discussed in the next paragraph.
1.1. Contributions
The main contributions of this article can be summarized as follows:
A Differentially Private Estimator for Transport Maps. We introduce a private mechanism (under so- called pure differential privacy) which is aimed solv- ing the problem of smooth optimal transport maps esti- mation (see Section 3). This estimator is then adapted to be implementable in practice in Section 6.
Differential Privacy and Optimal Transport A line of work (Rakotomamonjy & Ralaivola, 2021), building on the ideas from (Harder et al., 2021) provides privacy guarantees for the values of the sliced Wasserstein distance and MMD, respectively.
We analyze this estimator in Section 4 and provide an upper bound on its conver- gence rate.
Statistical Upper Bound.
On another note, other research has explored task-specific private methods utilizing optimal transport. For instance, (Sebag al., 2023) employs the sliced Wasserstein distance for data generation using an approach based on gradient flows. Additionally, (Tien et al., 2019) addresses differen- tially private domain adaptation via optimal transport by perturbing the optimal coupling between noisy datasets.
Minimax Lower Bound. We provide in Section 5 a minimax lower bound on the private optimal transport map problem in order to characterize the difficulty of the problem.
More recently, (Xian et al., 2024) investigated fair and pri-
2

---

On the Private Estimation of Smooth Transport Maps
vate regression, using tools from optimal transport theory. More precisely, they build private histogram estimators of the distributions P and Q and then compute the maps to their Wasserstein barycenter (which has applications in fair- ness) Their work is not directly related to our study, since the authors focus on fairness guarantees rather than on the problem of learning transport maps.
Brenier's theorem (Brenier, 1991) ensures that the solution to Problem (1) is transport map To Voo where fo is convex function. Furthermore, fo can be equivalenty obtained by solving the semi-dual problem
/ [(z)dP(x) + (
fo E argmin
(2)
=:((1)
Beyond these efforts, optimal transport has also been ex- plored within novel privacy paradigms outside the scope of our work (Pierquin et al., 2024; Kawamoto & Murakami, 2019; Yang et al., 2024).
s.t. SEL
where for all y
(w) = (x, v) - f(z) zEi
(3)
1.3. Notation
The symbols N, E. R and C are respectively used to refer to the sets of natural numbers (including 0), relative numbers, real numbers, and complex numbers. For any E N, (S) denotes the set of functions from a space to C that are k times continuously differentiable, and C (S) (*) is defined as NkeNC* (S)) Whenever applicable, V and 2 are used to refer to gradient and Hessian operators, respectively. For subset S of a normed vector space, |S] refers to supaes || for the inherited norm. For any set S. # (S) denotes its cardinality. For a family F' of vectors, Span(4") refers to the smallest vector space containing F. For a closed convex set of an Hilbert space, Projc refers to the convex projection onto C. The Hölder norm of order a on S (see Appendix B in (Hütter & Rigollet, 2021)) is denoted by [S]- For measure μ.. (|))(w)) is the usual L norm with reference measure Jr. With a small overlap of notation, for a measurable S C [dd, ||=]l refers to the L norm with reference measure 1 where À is Lebesgue's s measure. The asymptotic regimes are considered when - +00 and nc + +00.
is the Fenchel-Legendre transform of f:a see e.g. (Rüschendorf & Rachev, 1990). In this problem, is called the (Brenier) potential.
In order to estimate transport maps through Brenier po- tentials and obtain convergence rates, we need to enforce some regularity conditions, which we detail below. First, we require the first probability distribution be absolutely continuous with lower and upper bounded density.
Definition 2.1 (Admissible source distributions). We denote by .M the set of probability measures P on Rd that are sup- ported on Ω that are absolutely continuous w.r.t. Lebesgue's measure and whose density pr verifies M S pr I M for almost all x in Z.
Furthermore, we control the bias by imposing smoothness assumptions the optimal transport map. The following definition introduces the class of admissible smooth trans- port maps.
Definition 2.2 (Admissible smooth transport maps). We denote by T the set of differentiable mappings T: Ω + Rd such that = Vf for some differentiable convex function f: + Rd and
2. Smooth Transport Maps Estimation
In this section, we cover some basic theory on optimal trans- port and the minimax estimation of smooth transport maps. Following (Hütter & Rigollet, 2021), we set the feature space² Ω [o, 1]d and define á = [- 2j The notation M (resp. R) will refer to a positive constant strictly greater than 2 (resp. Identity (ā)) throughout the paper. The constants will hide terms that depend on 22 52, M,, and d, which was also the case in (Hütter & Rigollet, 2021).
[[((T)] S M, Vr E
e E â, M 3 f2f(z) = M,
(Q) = 1.
Furthermore, for a > 1 and R > 1, we define
i [a] times differentiable, and [T S R
Ta(R) TET:
2.1. Semi-Dual Problem and Smoothness
In the case where P and Q are supported in Ω and are absolutely continuous with respect to Lebesgue's 's measure,
In words, admissible transport maps have to be bounded (first item), come from smooth and strongly convex poten- tial (second item), and have stable support (third item). In
AAs in (Hütter& & Rigollet, 2021), Z can be replaced by any bounded and connected Lipschitz domain. In this case, 52 can be replaced by an hypercube containing Q in its interior.
We restrict the sup á because we are considering extended functions as Appendix A (Hütter & Rigollet, 2021).
3

---

On the Private Estimation of Smooth Transport Maps
addition, will assume that the optimal transport map be- longs the set Ta (R) of admissible transport maps whose Hölder norm of order is bounded by R.
Given pair vhr and th of smooth enough mother and father wavelets with compact supports, define wavelet Hilbert basis of (2R)) of the form
2.2. Empirical Semi-Dual
(V JJNNKEZA
(8)
Hütter & Rigollet (2021) observed that the objective in (2) consists of the sum of an expectation over / and pectation over Q, which can thus be approximated using Monte-Carlo averages. This led them to propose an estima- tor of the form
where Vj. GP is finite. The exact construction presented in Appendix B of (Hütter & Rigollet, 2021), with complements given in the present Appendix A. We do not include it in the main body of this article to understanding the core message.
believe that it is not essential
To = Vio
(5)
Importantly, since we are interested in guarantees in (Ω) rather than I,² (TR)),)), and because the supports of the father and mother wavelets are compact, the basis can restricted
where
fo E argmin
1
f f(x,) + Σ (M)
to the indices such that l E Kj for some finite K2 Z²
am1
Thus, defining
SS()) [Sff)Xinss X1n))
Vy Span ( (o.))ssJ,KKK...
s.t. VEV
and where Vo c (RR is a functional space to be specified later. Note that S and 5 are linked by the relation
yields a sequence of finite-dimensional nested approxima- tion spaces.
The estimator proposed by Hütter & Rigollet (2021) is the solution of (6) where Vo is replaced with V,, n X(MM) We denote the solution of the resulting problem and its associ- ated transport map by fa and fu == fu,, respectively.
Af. S(f) = EX Nim (S(f)Xim Yim)
(7)
Controlling the deviations 3 from its expectation, as well as using S()) S( effectively as a for the transport maps suboptimality, typically requires regularity of the admissible potentials. This is formalized in the following definition mirroring Definition 2.2.
Finally, measuring the utility (or error) of a candidate trans- port map T by its squared L2PP) distance
f / ddP
U(T,To) =
(10)
Definition 2.3 (Admissible potentials). We denote by XM( the set of twice continuously differentiable functions f: Ω + R such that Væ E i
we can guarantee that such a transport map estimator has a (near) minimax optimal rate.
Theorem 2.4 (Th. 2 of (Hütter & Rigollet, 2021)). For any a > 1, the minimax rate of smooth optimal transport map estimation is
1f(x) s 2M²
IVf(2)]l s M,
# 3 (z) < M.
inf sup T PEM.ToETa
Ex Yim CCT,Io)) 2
1 - Vn
20-243
2u
(11)
Next, we specify how Vo can be chosen obtain an imple- mentable estimator.
Moreover, if P E M and To E To the estimator Tr fa defined above achieves this rate up to polylogarithmic factors. Here, the constants also hide dependence on R.
2.3. Wavelet Decompositions and Subspace Approximations
2.4. Towards the Analysis of a Private Estimator
In line with standard approaches in nonparametric estima- tion, and in order to exploit the smoothness of the optimal map, Hütter & Rigollet (2021) suggested using successive approximations over nested subspaces V1 C 1/2 C... C V, C C (RR) of (R*)., where 2 1 denotes an integer controlling the resolution of the approximation space.
In this paper, we extend this approach to the context of differential privacy. We derive private estimator fpri for the optimal Brenier potential and deduce the corresponding private optimal transport map Ppriv = V To understand how privacy will affect the utility of the estimation, we propose the following risk decomposition.

---

On the Private Estimation of Smooth Transport Maps
Lemma 2.5. Suppose that there exists random variable Priv independent of all the other sources of randomness such that fpri is (Kim, Yim, mmeasurble and there exists U 2 O that is Priv-measurable such that
Here, 0 is parameter that controls the privacy level:
Lower values of correspond to more private mechanisms M.
We will rely on the standard report noisy max mechanism (Dwork & Roth, 2014; McSherry & Talwar, 2007; McKenna & Sheldon, 2020; Ding et al., 2021). We give its version instantiated with Laplace noise below.
((frrilX Yim) - $(fs| X 1o X1m) SU
(12)
Suboptimolity the semi daal
Lemma 3.2 (Report Noisy Argmin with Laplace Noise). Let f1..... fN be queries with sensitivities that are uniformly bounded by A, that is, for any of neighboring datasets D~ D' for any i E (I,...,m) n.
almost surely. If Ppav E
almost surely, then
EximYis [[(Iprie To)2)
2 U (d 2) In(1 + On)
1
[f( f((D) SA.
(15)
+
(13)
n
Then, if Li...., LN are independent and identically dis- tributed random variables with standard Laplace distribu- tion, the mechanism i defined as
inf (2V)nX(2M)
d(T, To)²
Priv-almost surely for some positive constant C. Here, Exim, Yun denotes the expectation w.r.t. the data, i.e. condi- tional on Priv.
24 L4
i(D E argmin (((D) +
(16)
is E-DP, with the convention that we return random index in the argmin when it is not unique.
Proof. See Appendix C.I.
In particular, we will use this mechanism as a building block to construct private estimator of fa-
In the next section, we propose a private estimator fpiv and explain how to control 5( X1sm: Yi..) S(fs]X Y1m). In particular, this estimator will satisfy the hypotheses of Lemma 2.5.
3.2. Noisy semi-dual estimator
In this section, construct our private estimator, building the empirical semi-dual one presented above.
The first step is to provide an upper bound on the sensitiv- ity of ((])Xi: Yı.),, which is established in the lemma below.
3. Private Estimator
This section presents some background on differential pri- vacy and introduces our private estimator.
Lemma 3.3 (Sensitivity of the semi-dual objective). For any f E X(MM), it holds that
3.1. Differential Privacy
S(f|Xim YLm) S(f(X Mi..)
sup (N Mm. Vin.)
Given (randomized) mechanism M (i.e. conditional kernel of probabilities), dom (M) denotes its domain (i.e. the set of admissible inputs) and codom (M) refers to its codomain (i.e. the set of admissible outputs). The set dom (M) represents the space of all possible data sets and equipped with a binary symmetric relation ~ called neighboring relations. Informally, two datasets are neighbor- ing if they contain the same data except for most one indi- vidual. Formally, we say that (XI:.) Y1.1) ~ (X Yim)) if dham ((X ((Xi,, YI (Xi... Y(.,)) S 1, where dram (5-) to denote the Hamming distance,
< 211/ V 2/
(17)
Proof. See Appendix D.2.
Now, recalling Section 2.3, let CJ.M be a finite subset of V, (2M). We can enumerate this set as
CJ.M = (fi.....ff(Cuuu)
(18)
Considering independent random variables Li...., L with Laplace distribution that are also inde- pendent of all the other sources of randomness, define
Definition 3.1 (Differential Privacy (Dwork et al., 2006)).
Given 2 0, a randomized mechanism M dom (M)
codom (M) is e-differentially private (or e-DP) if for all D ~ D' E dom (M) and all measurable S C codom (M)
âpri (D) E argmin { ((flI)) + 32M² V 36d
we have
L.
ne
(19)
PM (M(D) E S) S PM (M(D') ES
(14)
for i (1...., (Ct,M)
5

---

On the Private Estimation of Smooth Transport Maps
Theorem 3.4 (Privacy of the noisy semi-dual estimator). The mechanism returning the pair
for some constant C that does depend on or d
(fpv Si Tpri V feov
(20)
Proof. See Appendix E.2
c-DP.
4.2. Main result
We now have all the pieces to bound the error of Triv. In- deed, we can apply Lemma 2.5 with an lower bound on the empirical semi-dual error (U) that depends on (i) the resolution of the covering, and (ii) the uncertainty created by privacy max [[4]]...., ( The remaining ap- proximation bias ixf d(T,To) controlled as in (Hütter & Rigollet, 2021).
Proof. It follows as a direct consequence of Lemma 3.2
and of Lemma 3.3 that épri is c-DP. Hence, (fpiv. Ppa.) is e-DP by the post-processing property of differential privacy (Dwork & Roth, 2014).
We will use the estimator defined in Equation (20) our estimator for both the optimal Brenier potential and the optimal transport map.
Theorem 4.3. Let P E E,, To E Ta By choosing 6 appro- priately, the estimator Tpiv has utility satisfyyng
question that remains unanswered in this section is how choose and CJ,M- So far, we have treated these quanti- ties as hyperparameters. The next section explains how to choose them in order to optimize the bias-variance trade-off.
(1 11To - 1pvv1122
S 2222-200 (2 In(n)
1 2d In(n))
4. Statistical Upper Bound
n
(24)
for J larger than sufficiently large constant that also depend on R.
This section details the construction of CJ.M and gives an upper bound on the utility of the proposed private estimator.
Proof. See Appendix E.3
4.1. Covering construction
We now construct the set CJ.Ms such that it forms a 5- covering the space Vy n (2M) with respect to the empirical criterion Xmm Yım). Specifically, we aim to ensure that CJ,M C. Vy (2M)) and that
Ignoring poly-logarithmic terms and treating R as con- stant for conciseness, we can optimize over J to obtain an asymptotic upper bound on the error as follows
(f [To Ppiv 12PP))
Af EV, (22M), CJ.M s.t.
(21)
(25)
[S(f)Xi: YI..) S(f(X Yi.)) 88.
S n 24 V (nc)
A first step towards this goal is to observe that ((-IX1nn, Yi.)) is Lipschitz-comtinouus with respect to the 0 norm, as shown in the following lemma.
Remark 4.4. It is possible obtain similar bounds that hold with high probability with minimal adaptations to the proofs.
Lemma 4.1. For any f2 E X2MM).
8(fiXimn YISH 3(f2|X ) mmm) < 21 fi - f21lo0
5. Lower Bound
(22)
Packing arguments from (Hütter & Rigollet, 2021) as well as coupling arguments (Acharya et al., 2018; 2021; Lalanne et al., 2023a) can be applied to handle the DP nature of the constraint, and yield the following lower bound.
for any dataset (Xims Yum).
Proof. See Appendix E.1
Thus, 8 > O-covering of Vy (2M) for ((.1x1.n Yim) can be built from & --ooeering of Vy (2M) for I| Iloo. The following lemma bounds the cardinality of a specific covering of this form.
Theorem 5.1 (Lower Bound). Asymptotically,
( |1Tb - Tpriv ||=dP inf sup Tew P.E.TOETa
(26)
Lemma 4.2. There exists a 8-covering of VJ n X(2M) for || Io of cardinality at most N where
2 V (NE)
n
122d
where the infimum is taken over all estimators Tpav' 's that are cDP..
In(N) $ 2d In
+1
(23)
8
6

---

On the Private Estimation of Smooth Transport Maps
Kernel density estimator
density estimator Y1:-
0.4
022
0.2
1.48
1.28
Densty
1.08
0.48
0.28
-0.4
0.2
-0.2
[-1/2 12P
[-1/2.121
n 200000, 0j = 02 = 0.005, o
0.1.
Figure I. Kernel density estimators of the samples used in the experiments
Proof. See Appendix F.1
tential f may not always have a closed-form expression. To address this issue, (Hütter & Rigollet, 2021) approximate f by restricting the supremum in its definition to a grid.
We observe that the term in ne in the lower bound above does not match the corresponding term in the upper bound (25). It remains unclear which, if any, these bounds is tight. However, it is worth noting that similar coupling arguments have given optimal lower bounds in other non- parametric problems (Lalanne et al., 2023b; Lalanne & Ga- dat, 2024). We thus believe that the lower bound is more likely to be optimal than the upper bound.
This subsection develops similar ideas adapt this method to the context of differential privacy.
Let ( C Ω be finite approximation set. In practice it is taken to be uniform grid. We then define
figna (v)
sup (z, f(x), by e Ω. r
(27)
Following this conjecture, the suboptimality may arise from a suboptimal analysis of the estimator, a suboptimal choice of covering, or limitations of the proposed estimator itself. Furthermore, our estimator is, the best of our knowledge, the only one that has been proposed to solve the problem.
Note that the sensitivity analysis in Lemma 3.3 still holds under this approximation the Fenchel dual.
We represent potentials by storing their discretization fignia) on the grid (gid)) Their gradients are approximated using finite differences, denoted by V (igid))
Another consequence of this lower bound is that the esti- mation is provably degraded by privacy (even with the best estimator) when
Since we now only store the value of the potential and its (approximate) dual on grid, we need to clip the points to this grid. We thus denote by X x(gri)) and (grid) 1:m the modified versions of the datasets X1.n and Y1. where each point is replaced with its closest neighbor in (grid).
Im 2nd
6. Experiments
This section focuses on how to numerically approximate fpav and ppvv defined (20) and presents numerical results illustrate the proposed method.
Finally, if one wishes to apply Lemma 3.3 but cannot guar- antee that f E (2M)) we propose introducing a clipping constant in order to safeguard privacy.
This procedure leads the following practical algorithm: Start with finite family of candidate discretized potentials
6.1. Discretization
The main difficulty in computing fpiv and Tpay is that the Penchel-Legendee transform f" of candidate Brenier po-
F= {S(gid) S(rrid)
(28)

---

On the Private Estimation of Smooth Transport Maps
True Optimal Parsport Map
Private Transport Estimator
0.2
02
-04
-04
0.2
0.0
0.2
0.4
5.0
0.4
14. 2027
C 1/2 AR27
On the left: The true optimal transport map between the underlying distributions in the Gaussian attraction / repulsion model described in Section 6.2. On the right: The transport map that is privately estimated using the approximation algorithm described in Section 6.1. For the numerical values, ( is uniform grid in 1122, 1 1/2| with 642 points, 1.,
200000, a1 a2 0.005, d1 02 0.1. T 2000, and C 0.25.
Figure 2. Optimal Transport Map VS Estimated Private Map
then compute
Then, random potential is generated by sampling two independent copies M1, ~N(0,, aT2). This defines the "true" potential, which is the target of the estimation.
i E argmin { ((gni)) ( (ignd), i x (erid) ((erid)) 4C Li
(29)
We then sample n i..d. uniform random variables X1s1 over [-1/2, 1/2j², and generate the observations Yim by applying the gradient of the previously defined potential to n new i.i.d. uniform random variables over [-1/2, 1/2]2. This is illustrated in Figure 1, where represent two kernel density estimators constructed on the datasets X and YI... respectively.
where for any f. X1.n and Yin
1
Kf1 V1.) = (gnno
- f(X,)
i=1
Proj P Fignay (Y)
(30)
We then apply the algorithm defined Section 6.1 where is a collection of T independent potentials that are generated according the same distribution as the true potential.
and where L1,...; , Ln are independent Laplace random variables. By Lemma 3.2, à e-DP, and by post-processing, so is T == ( which we use as an estimator.
The result of the algorithm and the optimal transport map are represented in Figure 2. This simulation con- firms that the estimated transport map is close to the optimal one. The code used to generate those results can be found at /https:: / com/ clemlal/ Pri orr.vatesnochirraaspptttaapprpgp
6.2. Gaussian Attraction / Repulsion Model
We illustrate the behavior of the estimator 7 defined in Section 6.1 on the following model, which we refer to as the Gaussian attraction/repulsion model.
We begin with simple quadratic potential (x) } ||| for which the mapping induced by its gradient is the identity. For any μ and > 0, denoting the Gaussian potential by fx(2),, = e [l==-1) potentials of the form
7. Conclusion
In this paper, we have introduced private estimator for the problem of privately estimating smooth optimal transport maps. We have analyzed the utility of this estimator and derived lower bound on the difficulty of the statistical prob- lem. Finally, we proposed an adaptation of this theoretical estimator that is implementable in practice.
we consider
fx 02 11, H1, 02) fquad (z) + aafw((z/))))) 02f 02)
(31)
where 01 02 01, U2 are positive numbers and μ1, A2 E Rdd are location parameters.
This work opens up several research directions. One of them is the quest for an optimal private mechanism, and
8

---

On the Private Estimation of Smooth Transport Maps
another one is the design of numerically efficient algorithms. In both cases, we believe that investigating regularization techniques such as entropic regularization would be an im- portant step forward as it could help stabilize the problem, reduce the amount of privacy noise, and enable the use nu- merically efficient algorithms such as Sinkhorn's 's algorithm (Cuturi, 2013).
ple complexity of privately learning unbounded high- dimensional gaussians. In Feldman, V., Ligett, K., and Sabato. S. (eds.), Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132
of Proceedings of Machine Learning Research, pp. 185- 216. PMLR, 2021. URL hhtpp:htttpptttt http:///pocceeeeeeeeeeee m.r. www.press//ee.eee vv12 /ae//aadn-aaee wwwlllll...... html.
Alaux, J., Grave, E., Cuturi, M., and Joulin, A. Unsu- pervised hyperalignment for multilingual word embed- dings. CoRR, abs/ 1 .01 1244,, 2018. URL. /htt///:
Acknowledgements
This paper has been partially funded by the Agence Na- tionale de la Recherche under grants ANR- ANR-I7-EURE-0010 (Invsstisemments d' Avenir program), ANR-23 -BR-23-CE23-0029 Regul-IA, and NNR-24-CE23-1522 MAD. The authors also acknowledge the support of the AI Cluster ANITI (ANR-19- PI3A-0004). In addition, we thank the anonymous reviewers for the constructive discussions that led, in particular, to the addition of Appendix G and Appendix H.
arxiv. mxxiv.org/bbs 1811. 01124.
Altschuler, J. M., Weed, J., and Rigollet, P. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1964 1974, 2017. URL hhttps://proceeest
Impact Statement
This paper presents work whose goal advance the field of Frivacy-Preserving Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
neurips.c http://cccc/aaape////////// 491442df5f88c6ea0 8e8 Abstract.
Alvarez-Melis, D., Jaakkola, T. S., and Jegelka, S. Structured optimal transport. In Storkey, A. J. and Pérez-Cruz, F. (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, volume 84 of Proceedings of Ma- chine Learning Research, pp. 1771-1780. PMLR, 2018. URL htth:htttp//r/eeed//i ngs . m1 wwl.r.rees//ee alvarez meseez-meeiiseee html.
References
Abowd, J. M. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD In- ternational Conference on Knowledge Discovery & Data Mining, pp. 2867-2867, 2018
Acharya, J., Sun, Z., and Zhang, H. Differentially private testing of identity and closeness of discrete distributions. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Infor- mation Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 6879- 6891, 2018. URL partps://proceediee neurips. oc/ wttp::/pppppp..//eeeee Abstract html.
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein gen- erative adversarial networks. Precup, D. and Teh, W. (eds.), Proceedings of the 34th International Conference Machine Learning, 1CML 2017, Sydney, NSW, Aus- tralia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 214-221.3 PMLR, 2017. URL http/htt////// http::::/ppocpeeedeeemmom mllr www....resss/00 ar arjovaky17a. html.
Backstrom, L., Dwork, C., and Kleinberg, J. M. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Williamson, C. L., Zurko, M. E., Patel-Schneider, P. F., and Shenoy, P. J. (eds.), Proceedings of the 16th International Confer- ence on World Wide Web, WWW 2007, Banff. Alberta, Canada, May 8-12, 2007, pp. 181-190. ACM, 2007. doi: /10. 700.1445/242277212222533 doi 1tt.:///1...1115/22222...111
Acharya, J., Sun, 7.,, and Zhang, H. Differentially private Assouad, Fano, and Le Cam. In Feldman, V., Ligett, K., and Sabato, S. (eds.), Algorithmic Learning Theory, 16- 19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp- 48-78. PMLR, 2021, URL /http:/ /proceedinss..c.. mlr. prwss/eeee...... / / acharyalla html.
URL /https://
Barber, R. F. and Duchi, J. C. Privacy and statisti- cal risk: Formalisms and minimax bounds. CORR,
Aden-Ali, I., Ashtiani, H., and Kamath, G. On the sam-

---

On the Private Estimation of Smooth Transport Maps
abs/1412.4451, 2014. URL htttt::://axxiv.oor/// 0bss1412.4457/
9778d5d21 0atr5s2221:0000bbaaaaa 7be 7bee39333 cestract.htm...
Beraha, M., Favaro, S., and Rao, V. Meme for bayesian non- parametric mixture modeling under differential privacy. arXiv preprini urXiv:2310.09818 2023.
Bun, M., Kamath, G., Steinke, T., and Wu, Z. S. Pri- vate hypothesis selection. IEEE Trans. Inf. Theory, 67 ())1181-20000, 2021. doi: /11.1111//11/000022222 33049802. URL /tttts:t///t// http://doo.ooggo www.orgg/1000 010000.1199/111 20211. 3049802.
Berrett, T. B., Györfi, L.,, and Walk, H. Strongly universally consistent nonparametric regression and classification with privatised data. Electronic Journal of Statistics, 15 (1):2430 2453, 2021. doi: /https: / /doi. /0g/ 121 /2 21-211155 EEJ51 845.
Butucea, C.,, Dubois, A., Kroll, M., and Saumard, A. Lo- cal differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids. CoRR, toss/1933.0127,, 2019. URL abs / 1 1903. 01927.
URL
Biswas, S., Dong, Y., Kamath, G., and Ullman, J. R. Coinpress: Practical private mean and covariance estimation. Larochelle, H., Ranzato, M., Hadsell, R., Balean, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Sys- tems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL /https:/ http:s/////cceciggss...m
Cai, T., Wang, Y., and Zhang, L.. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. CoRR, abs/ htss/1922.04495 2019. URL /tttp:ttt//////// araiiiiiv... www.i.oorgg..ooooooooooooooooooo /eerrg/aa /abss////////// / 902. 95.
Cañas, G. D. and Rosasco, L. Learning probability measures with respect to optimal transport metrics. In Bartlett, P. L., Pereira, F. C. N., Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6,
neurips.. cc/ a684eceee (eweee7772222278888888383 Abstract. html.
Black, E., Yeom, S., and Fredrikson, M. Fliptest: fairness testing via optimal transport. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 111-121, 2020.
2012, Lake Tahoe, Nevada, United States, pp- 2501-
2509, 2012. URL /https::
neurips 1ttriipscccppapeee221111111
Brenier, Y. Polar factorization and monotone rearrangement of vector-valued functions. Communications on pure and applied mathematics, 44(4):375-417, 1991.
cittract.htmll
Cazelles, E., Seguy, V., Bigot, J., Cuturi, M., and Papadakis, N. Geodesic PCA versus log-pea of histograms in the wasserstein space. SIAM J. Sci. Comput., 40(2), 2018. doi: /10.1137/17M1 1434559 URL /tttt/:t/////// //tps:////o /ooii /ttp:/oro//////////o////o./oo 10. 10. 1434599
Brown, G., Gaboardi, M., Smith, A. D., Ullman, J. R., and Zakynthinou, L. Covariance-awart private mean estimation without private covariance estimation. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 7950- 7964, 2021. URL btstps://proceeddie neurips.. oe/ pttppappe//22///aahh/ 027788005000005591100006611111 Abstract.htun
Chhor, J. and Sentenac, Robust estimation of discrete distributions under local differential privacy. In Interna- tional Conference on Algorithmic Learning Theory, pp. 411-446 PMLR, 2023.
Courty, N., Flamary, R., and Tuia, D. Domain adaptation with regularized optimal transport. In Calders, T., Es- posito, F., Hüllermeier, E., and Meo, R. (eds.), Machine Learning and Knowledge Discovery in Databases Euro- pean Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part 1, volume 8724 of Lecture Notes Computer Science, pp. 274 289. Springer, 2014. doi: /10.1007/998--3-622-446 18. URL /wttts:t/////// //t:://o.oo oogoiiorrg/an 100 101.0.1011999880 662-44844 4284-448---21 18.
Bun, M., Kamath, G., Steinke, T., and Wu, Z. S. Private hypothesis selection. Wallach, H. M., Larochelle, H., Beygelzimer, A., d' A'ccééé Buc, F,, Fox, E. B., and Gamett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14,, 2019, Vancouver, BC, Canada, pp. 156 167, 2019. URL /https:/ /tttpp::ppopoceaaaae /proceedings. neurips. oe/ pcpppppp/201999 /
Courty, N., Flamary, R., Habrard, A., and Rakotomamonjy.
Joint distribution optimal transportation for domain
10

---

On the Private Estimation of Smooth Transport Maps
adaptation. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017a. URL http:htttpss//prceeeediiee
Del Barrio, E., González Sanz, A., and Loubes, J.-M. Cen- tral limit theorems for semi-discrete wasserstein distances. Bernoulli, 30(1):554-580, 2024.
Diakonikolas, I., Hardt, M., and Schmidt, L. Differentially private learning of structured discrete distributions. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2566- 2574, 2015. URL
neurriissssnnnnn.............m cc cc/papper_files//eeeeeeeeossseee pttpappe_fille//ppprr///////// 5tt.e:0000.0aaa0000ee3eeed11d1e. Paper. pdf.
Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. Optimal transport for domain adaptation. IEEE Trans. Pattern Anal. Mach. Intell., 39(9):15331165 2017b. doi: 100.100/TPAMM2201.2655550 doi. org/10. 1 1w11119/PAATT 201 2615921.
URL /https://
neurips. /ooxippp.cc/papee/////////// 2 htstract.html.
Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. In Burges, C. J. C., Bottou, L., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 2292- 2300, 2013. URL /tttttttt////tttttttttttttt/tttt http:////cccc.....////ee/
Ding, B., Kulkarni, J., and Yekhanin, S. Collecting telemetry data privately. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3571- 3580, 2017. URL
neurips.. oc pttppappee/013/aaaeeeeeeeeeeeeee
neurips cc.rippscc/paaee Swwuiips.cc/aaper///00/ http///aape//////aa/////
Abstract html.
Abstract.htm.
Damodaran, B., Kellenberger, B., Flamary, R., Tuia,
D., and Courty, N. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Ferrari, V., Hebert, M., Sminchisescu, C., and Weiss, Y. (eds.), Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part IV, volume 11208 of Lecture Notes in Computer Science, pp. 467-483 Springer, 2018. doi: URL /https:// doi org. 0..0 1007 00000007799933-33000 0ttp:://.....000000--00000001000
Ding, Z., Kifer, D., E., S. M. S. N., Steinke, T., Wang, Y., Xiao, Y., and Zhang, D. The permute-and mecha- nism is identical to report-noisy-man with exponential noise. CoRR, 100.s22220000000 2021. a arxiv. wwt.voorgabb///oo 21022 221..//220000000.0...
Dinur, and Nissim, K. Revealing information while preserving privacy. In Neven, F., Beeri, C., and Milo, T. (eds.), Proceedings of the Twenty-Second ACM VIGACT-SIGMODDSIGGAR Symposium on Prin- ciples of Database Systems, June 9-12, 2003, San Diego CA, USA, pp. 202-210. ACM, 2003. doi: /10. 1145/773153.773113, URL /https: /ttpa////dooor/////// 10.1145/773153, 7733173.
De Lara, L., González-Sanz A., Asher, N., Risser, L., and Loubes, J.-M. Transport- based counterfactual models. Journal of Machine Learning Research, 25(136):1-59) 2024.
del Barrio, E., Gordaliza, P., Lescornel H., and Loubes, J. Central limit theorem and bootstrap procedure for wasserstein's 's variations with an application to struc- tural relationships between distributions. J. Multivar. Anal., 169:341-362, 2019. doi: /10.1016/..MVA.2018 09.014. URL /https::// http:///.o.oooo....e.oo 1016/1. jmva. 2018 19.09.000 014.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Lo- cal privacy and statistical minimax rates. In 51st An- nual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Allerton Park & Retreat Center, Monticello, IL, USA, October 2-4, 2013, pp. 1592. IEEE, 2013, doi: /10. /10.1109/AAllerton |00t///Allllooo221..7777711 URL /httts:://///// /oii org 100 1ttp://1.11199//1111. 2013.67367 6736718.
del Barrio, E., González-Sanz, A., and Loubes, J.-M. Cen- tral limit theorems for general transportation costs. In Annales de I'Institut Henri Poincare (B) Probabilites et statistiques, volume 60, pp. 847-873. Institut Henri Poincaré, 2024.
Duchi, J. C., Wainwright, M. J., and Jordan, M. I. Minimax optimal procedures for locally private estimation. CoRR, abs/1604 0200900,..22..... 2016. URL /http://///////// htttt::/arxxv..rr aariv..rg// abs/1604 022.11004.0290.. 02390.

---

On the Private Estimation of Smooth Transport Maps
Dvurechensky, P. E., Gasnikov, A. V., and Kroshnin, A. Computational optimal transport: Complexity by accel- erated gradient descent is better than by sinkhomn's 's al- gorithm. In Dy, J. G. and Krause, A. (eds.), Proceed- ings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssenn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1366-1375. PMLR, 2018. URL / httphhtttpp//ppccpeppeppepeeeeee http//proeeeenn...e/ee ngs m0.. press// v80 2.00/vurrccennskyll 8a html.
(12):1923-1945, 2018. doi: /10. /10.1007//100994--8-55777
1. URL /https:/t: /tt.///o....o///// http///t.......///////oo 1007 00.00000/111 s0099 118-5717-2
Forrow, A.,, Hütter, J., Nitzan, M., Rigollet, P., Schiebinger, G., and Weed, Statistical optimal transport via factored couplings. In Chaudhuri, K. and Sugiyama, M. (eds.), The 22nd International Conference on Artificial Intelli- gence and Statisties, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Ma- chine Learning Research, pp. 2454 2465. PMLR, 2019. URL /ttt/:ttp/////// proceedinnggg mlr. r. press/ /v89 forrowl 9a. .ttl.
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, 2014. doi: /10.1566104400000042 URL /https://dob wwgpii.rrg//o// C. 0055561000000044000
Fredrikson, M., Jha, S., and Ristenpart, T. Model inver- sion attacks that exploit confidence information and basic countermeasures. In Ray, I., Li, N., and Kruegel, C. (eds.), Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pp. 1322-1333, ACM, 2015. doi: /10.1145/2810003228 doi org. 10. 11..0..1115111111 28136677
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. Cal- ibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, vol- ume 3876 of Lecture Notes in Computer Science, pp. 265- 284. Springer, 2006. doi: /10.1007/1168187888 14. URL /https: / ttwddoi.orgo .rgg 100.0///00010077711111888888
URL /https:// //
Genevay, A., Peyré, G., and Cuturi, M. Learning gen- erative models with sinkhorn divergences. In Storkey, A. J. and Pérez-Cruz, F. (eds.), International Confer- ence on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Ca- nary Islands, Spain, volume 84 of Proceedings of Ma- chine Learning Research, pp. 1608-1617. PMLR, 2018. URL /http:t////////// / pttpppeeooennssse/// www.m....p.ssseeee. genevay Ba html.
Erlingsson, Ú. Pihur, V., and Korolova, A. RAPPOR:
randomized aggregatable priaay-pressevvng ordinal re- sponse. Ahn, G., Yung, M., and Li, N. (eds.), Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014. pp. 1064. ACM, 2014. doi: 01114445726662277266644444 URL /https: doi.org/100.145/26000 2660933488866688 2600448.
Gordaliza, P., del Barrio, E., Gamboa, F,, and Loubes, J. Obtaining fairness using optimal transport theory. In Chaudhuri, K. and Salakhutdinov, R. (eds.). Pro- ceedings of the 36th International Conference chine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Ma- chine Learning Research, pp. 2357-2366 PMLR, 2019. URL /http: http///poeeeeceneeeee/eeeeeeesee www. wwl...pres//ve gordal za 9a .html.
Evfimievski, A., Gehrke, J., and Srikant, R. Limiting pri- vacy breaches in privacy preserving data mining. In Pro- ceedings of the Twenty-Second ACM VGGMOD-SIGACE SIGART Symposium on Principles of Database Systems, PODS '03, pp. 211-222, New York, NY, USA, 2003, As- sociation for Computing Machinery. ISBN 1581136706. doi: /tt. /10..1145/733155.777144 URL /ttttt::////// //doi. org/10. 11311.111144777115.777....
Ma-
Feydy, J., Charlier, B., Vialard, F., and Peyré, G. Op- timal transport for diffeomorphic registration. In De- scoteaux, M., Maier-Hein, L., Franz, A. M., Jannin, P., Collins, D. I.,, and Duchesne, (eds.), Medical Im- age Computing and Computer Assisted Intervention MICCAI 2017 20th International Conference, Que- bec Ciry, QC, Canada, September 11-13, 2017, Pro- ceedings, Part I, volume 10433 of Lecture Notes in Computer Science, pp. 291-299. Springer, 2017. doi: /10. 110.1007/9988-33319-611122- 34. URL /https://////// doi, oww.oorg/10.. http:/10.1100//0000
Grave, E.., Joulin, A., and Berthet, Q. Unsupervised align- ment of embeddings with wasserstein procrustes. In Chaudhuri, K. and Sugiyama, M. (eds.), The 22nd In- ternational Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Ma- chine Learning Research, pp. 1880-1890. PMLR, 2019. URL http:httt////ceeeeeeee grave19a.htm..
ml prw.s/pssssee..ee. vB9/
3-
Györfi, L. and Kroll, M. On rate optimal private regres- sion under local differential privacy. arXiv preprint arXiv:2206.00/ 2022.
Flamary, R., Cuturi, M., Courty, N., and Rakotomamonjy. A. Wasserstein discriminant analysis. Mach. Learn., 107
12

---

On the Private Estimation of Smooth Transport Maps
Györfi, L. and Kroll, M. Multivariate density estimation from privatised data: universal consistency and mini- max rates. Journal of Nonparametric Statistics, 0(0):
Kamath, G., Liu, X., and Zhang, H. Improved rates for differentially private stochastic convex opti- mization with heavy-tailed data. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C.. Niu, G., and Sabato, S. (eds.), International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Bal- timore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 10633-10660. PMLR, 2022a. URL /https:: hittts::/proceeeingg mir.press/v16t 1r1162/kamat222a htm.l.
1-23, 2023. doi: 700.18001044223322222266666
URL. /ttttt:://///// ht/oii.ogg//...0 1ttp://11..110111111111 2022.21533 2163634.
Harder, F., Adamczewski, K., and Park, M. Dp-merf: Dif- ferentially private mean embeddings with randomfeatures for practical preeeeving data generation. In Inter- national conference on artificial intelligence and statis- tics, pp. 1819-1827. PMLR, 2021.
Kamath, G., Mouzakis, A., and Singhal, V. New lower bounds for private estimation and a gen- eralized fingerprinting lemma. In NeurlPS, 2022b.
Homer, N., Szelinger, S., Redman, M., Duggan, D., Tembe, W., Muehling. J. Pearson, V., Stephan, D. A., Nelson, F. and Craig, D. W. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays, PLoS Genet, 4 (8)ee100016) 2008
URL /nttp://papers.nit nips. hc//ppper_iille/ppprr//////////2
94422782199666991344411333333323 Abst Abstract-Conferene html.
Kamath, G., Mouzakis, A., Regehr, M., Singhal, V., Steinke, T., and Ullman, J. R. nla--variance-privacy trilemma for statistical estimation. CoRR, /tto///331.133344 2023, doi: /10.0/6500AAAXX122200111382 URL /https:///////// doi org / 1.000.4855500 205/55///xxiv/ wtw.aawwww............. 20t.
Hütter, J.-C. and Rigollet, P. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2):
1166 - 1194, 2021. doi: 110.1211400-0011999 URL /https://don http:///.ooo........oo 1214/211112000 20 AOS1997.
Janati, H.. Cuturi, M. and Gramfort, A. Wasserstein regularization for sparse multi-task regression. In Chaudhuri, K. and Sugiyama, M. (eds.). The 22nd In- ternational Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan. volume 89 of Proceedings of Ma- chine Learning Research, pp. 1407-1416. PMLR, 2019. URL /tttt:tt/////// htttt::/ppoceeediiie httpp//poceennnnse/ee/eeee mlr seress/v89) janatil9e 19....99... html.
Karwa, V. and Vadhan, S. P. Finite sample differentially private confidence intervals. In Karlin, A. R. (ed.), 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pp. 44:1-44:9. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018. doi: /10.4230/ LIPIcs. 2018.44. URL /wttps::////ttt /ttp:p::///.i..oo .or. 10 10.4230/LIPICsS ITCS CTTSS.218... 2018.44.
Kallenberg, O. Lectures the coupling method (torgny lindvall). SIAM Review, 35(3):525-527 1993. doi: /10.1137/1031121 URL /tttts::///// ht////i.ogg//////// 1137/1035121.
Kasiviswanathan. S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn pri- vately? In 2008 49th Annual IEEE Symposium on Foun- dations of Computer Science, pp. 531-540, 2008. doi: 110.109/FOCCS20000
Kamath, G., Li, J., Singhal, V., and Ullman, J. R. Privately learning high-dimensional distributions. In Beygelzimer, A. and Hsu, D. (eds.), Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Ma- chine Learning Research, pp. 1853-19022 PMLR, 2019. URL /ttt//tt//////// pwtppeooocedeeee ngs. ml ptess/v99/ kamath19a. html.
Kawamoto, Y. and Murakami, T. Local obfuscation mech- anisms for hiding probability distributions. In Sako, K., Schneider, S. A., and Ryan, Y. A. (eds.), Com- puter Security ESORICS 2019 24th European Sympo- sium on Research in Computer Security, Luxembourg, September 23-27, 2019, Proceedings, Part I, volume 11735 of Lecture Notes in Computer Science, pp. 128- 148. Springer, 2019. doi:
Kamath, G., Singhal, V., and Ullman, J. Private mean estimation of heave- distributions. In Aber- nethy, J. D. and Agarwal, S. (eds.), Conference Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pp. 2235. PMLR, 2020. URL hhtp::/ /ttht/pppp/pcceeeaeiittt/ /ptpccpeeiiggsssseeeeeee mlr. prrss/ v1 2.5k/amateo th2 aa. html.
7. URL /https: / /ooi org/10 10 1007 0000007/7700 9-78//7733333 3- 1300229599-017
Klatt, M., Tameling, C., and Munk, A. Empirical regu- larized optimal transport: Statistical theory and applica- tions. SIAM J. Math. Data Sci., 2(2): 443, 2020. doi: 100.113711M1228888. URL /https::////ttcc http::::///ooooooo// 10. 14,1117/111 9M1 278788.
13

---

On the Private Estimation of Smooth Transport Maps
Kroll, M. On density estimation a fixed point under local differential privacy. Electronic Journal of Statistics, 15 (1):1783 1813, 2021. doi: /10.121421-ESS1880 URL /https:
Le, T., Nguyen, K., Sun, S., Han, K., Ho, N., and Xie, X. Diffeomorphic mesh deformation via effi- cient optimal transport for cortical surface reconstruc- tion. In The Tweifth International Conference on Learn- ing Representations, ICIR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL /https:/ openreview net forum? ?inimmiid=gaeee d-gghRR8UUUQ
1214/21-BJ51880.
Kroshmin, A., Spokoiny, V. G., and Suvorikova, A. L. Statistical inference for bures-wasserstcin barycen- ters. The Annals of Applied Probability, 2019. URL /tttts::tt//// pttt:s::/app.semmttiissssss seemanticscoolar..oom CozpusID:88524500
Loukides, G., Denny, J. C., and Malin, B. The dis- closure of diagnosis codes can breach research par- ticipants' privacy. J. Am. Medical Informatics As- soc., 17(3):322-327, 2010. doi: /10.1136/jamia... 002725. URL /tttps: /tttpss:/doi..oo http:///oo..rgg1.1133333
Lalanne, On the tradeoffs of statistical learning with privacy. Theses, Bcole normale supérieure de Iyon- ENS LYON, October 2023. URL /tttps://ttteeeeee
jami a
hal. sc
Lalanne, C. and Gadat, S. Privately Learning Smooth Distri- butions on the Hypercube by Projections. In ICML 2024 st International Conference on Machine Learning, pp- 39 p., Vienna, Austria, July 2024. URL /https:// hal wccsccieenn www.ecceeeehaaaeeee 04549279
Manole, T., Balakrishnan, S., Niles-Weed, J., and Wasser- man, L. Plugin estimation of smooth optimal transport
maps, 2024. URL /https::////t// /ttp///axvvvvv/vv///aa/eeeeeeaaa http///awiv..../aaa...../.. 12364.
McKenna, R. and Sheldon, D. Permute-and-flip: A mechanism for differentially private selection. In Larochelle, H., Ranzato, M., Hadsell, R., Bal- can, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, tual, 2020. URL hnttps::/proceeeiing
Lalanne, C., Garivier, A., and Gribonval,
the Statistical Complexity of Estimation and Testing under Privacy Constraints. Transactions Machine Learn- ing Research Journal, April 2023a. URL /https:// hal. www.nceeeeiccccccccc wwweeencchhlleae Saaneeehal-3335 - 94374.
Lalanne, C., Garivier, A., and Gribonval, R. About the cost of central privacy in density estimation. Transac- tions on Machine Learning Research, 2023b. ISSN 2835-8856. URL /https:// / http//pppeeeeeeeeeeeeeeeee forum? www.dduuugMvvv..
neurips neurips.cc/papeeeee hctpp/pe///p/////aaaaaa
(440021100eee773000666116688888 Abstract. html..
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007). October 20-23, 2007, Providence, RI, USA, Proceed- ings, pp. 94-103. IEEE Computer Society, 2007. doi: /10. 20.1109//CC.2207..11 URL /tttttt:///oi...// 10. www.1199/FOOOO 2007 41.
Lalanne, C.. Garivier, A., and Gribonval, R. Private Sta- tistical Estimation of Many Quantiles. In ICML 2023 Machine Learning, Honolulu, United States, July 2023c. URL /tttt/:t/////////// hal. swwenceeeeeecccee...co.....ecc.e hal-aahhhah htt.a///ehha--191111111
40th International Conference
Lalanne, C., Gastaud, C., Grislain, N., Garivier, A., and Gribonval, R. Private Quantiles Estimation in the Pres- ence of Atoms. Information and Inference, August 2023d. doi: /10. 1033///maaaa//aaad0300.. URL /https:// hal. www.ecieeceeeccceecee.....occcee http//aal--3337//
Monge, G. Mémoire sur la théorie des déblais et des rem- blais. De l'Imprimeiie Royale, 1781.
Montavon, G., Müller, K., and Cuturi, M. Wasserstein training of restricted boltzmann machines. In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Infor- mation Processing Systems 29: Annual Conference Neural Information Processing Systems 2016. December 5-10, 2016, Barcelona, Spain, pp. 3711- 3719, 2016. URL hnttps::/proceedinnn neurips. neurips.cc/pane /ctps//ccccppppe.////aaa.. 7282062220166512554407628882828 Abstract html.
Lam-Weil, J., Laurent, B., and Loubes, J.-M. Minimax opti- mal goodness-of-feeee of-ftt testing for densities and multinomials under local differential privacy constraint. Bernoulli, 28(1):579-600 2022.
Lavenant, H., Claici, S., Chien, F.,, and Solomon, J. Dy- namical optimal transport on discrete surfaces. ACM Trans. Graph., 37(6),250, 2018. doi: /10.1145/3272127. 3275064. URL /https:///// /dii http//ii.oro...11111/ 3272127. 0372127.327506. 3275064.
14

---

On the Private Estimation of Smooth Transport Maps
Narayanan, A. and Shmatikov, V. How break anonymity of the netflix prize dataset. CoRR, abs/cs/0610105,, 2006. URL http//tttt////// ptattp://axiivi
http.U////ttppp/ppcceeiigg ml www.mmrrrrp.. press// v139/ vL13//rakotommmooiiyyll.l.
2021. URL
Ramdas, A., Trillos, N. G., and Cuturi, M. On wasser stein two-sample testing and related families of nonpara- metric tests. Entropy, 19(2):47, 2017. doi: /10.3390/ E19020047. URL /ttt:/:://////ttt http:///ooooooooooooooo.. 3390/ e e19020047.
Narayanan, A. and Shmatikov, V. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA, pp. 111-125. IEEE Com- puter Society, 2008. doi: /10.1109/SSP.008.33. URL /https: http////...r///1.111////////// 1109//1...P.... 2008.33.
Randal-Williams, O. Algebraic topology. Lecture Notes, 2024. URL /https: portts::/www... dpmms. c cam ac. uk/ http://teaccinnnootesssessss
Niles-Weed, J. and Rigollet, P. Estimation of Wasserstein distances in the Spiked Transport Model. Bernoulli, 28
Rigollet, P. and Weed, J. Entropic optimal transport is maximum-likelihood deconvolution. Comptes Rendus Mathematique, (56(1)): 2018. ISSN 1631- 073X. doi: http://////diiiooo////o/o/t//maa
(4):2663 - 2688, 2022. doi: 110.315021-BEJ14333 URL chttps:///oi... htt.//i.oggg/..//// 00. 2150/21-BBBS
Panaretos, V. M. and Zemel, Y. Statistical aspects of wasserstein distances. Annual Review of Statis-
URL /tttps::www..eceenncddeeeecc scceanee//rrtcdee////////1111113
lies and Its Application, 6(Volume 6, 2019):
405-431, 2019. ISSN 2326-831X. doi: /htips://
Rüschendorf, L. and Rachev, S. T. A characterization of random variables with minimum 12-distance. Journal of
dbi.org/10.1144/ammnn 4/000///////eeessssttt---0111-/3 104938.
URL content/jourmals/100.11 http:///0..114///a.eeeeeee annurev- 030-:---is-007----10
org/
multivariate analysis, 32(())48 54, 1990.
Santambrogio, F. Optimal Transport for Applied Math- ematicians. Birkhäuser Cham/Springer, 2016. doi: 10.1100799883331922002
Perrot, M. Courty, N., Flamary, R., and Habrard, A. Mapping estimation for discrete optimal transport. In Lee, D. D., Sugiyama, M., von Luxburg, U.. Guyon, I., and Garnett, R. (eds.), Advances in Neural Infor- mation Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 4197- 4205, 2016. URL
Schluttenhofer, S. and Johannes, J. Adaptive pointwise density estimation under local differential privacy, 2022.
Schmitz, M. A., Heitz, M., Bonneel, N., Mboula, F, M. N., Coeurjolly, D., Cuturi, M., Peyré, G., and Starek, J. Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learn- ing. SIAM J. Imaging Sci., 11(1):643-678, 2018. doi: 110.113/17M114000 140431. URL 10. 1137 71 7M1777114444 140431.
neurips.cc/ ca/ htpps/////ppee//////sssss//// htw.aa//aaasffaaffool22eeaee Abstract.ht..
Peyré, G. and Cuturi, M. Computational optimal trans- port: With applications to data science. Foundations and Trends@ in Machine Learning. 11(5-6)3355-600 2019. ISSN 1935-8237. doi: /10. /10.1551//2200000773 URL /http:/ / /xxx doi. org/10.g...... 10.
Sebag, I., Pydi, M. S., Franceschi, J., Rakotomamonjy, A., Gartrell, M., Atif. J.. and Allauzen, A. Dif- ferentially private gradient flow based on the sliced wasserstein distance for paraamerettic generative mod- eling. CoRR. abs/2312.08227, 2023. doi: /10.48550/ ARXIV.2312.08227. URL. /https:t//////// /tte:://ooooooo org/10. 48550/arXiv 2312. 08227.
Pierquin, C., Bellet, A., Tommasi, M., and Boussard, M. Rényi pufferfish privacy: General additive noise mech- anisms and privacy amplification by iteration via shift reduction lemmas. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL /https:// openreview
Seguy, V. and Cuturi, M. Principal geodesic analysis for probability measures under the optimal transport metric. Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 3312- 3320, 2015. URL hnttps://proceedingg neurips. cctppapper/.l.//aaa... Abstract. html.
Rakotomamonjy, A. and Ralaivola, L. Differentially pri- vate sliced wasserstein distance. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtall Event, volume 139 of Proceedings of Machine Learning Research, pp. 8810 8820. PMLR,
15

---

On the Private Estimation of Smooth Transport Maps
Seguy, V., Damodaran, B. B., Flamary, R., Courty, N., Ro- let, A., and Blondel, M. Large scale optimal transport and mapping estimation. In 6th International Confer- ence on Learning Representations. ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL /https:// openreview wwtpeevwwwwwwweeeereeeeeeeee wtt.::mmmmmmmi1li.1pplm.
Thakurta, A. G., Vyrros, A. H., Vaishampayan, U. S., Kapoor, G., Freudiger, J., Sridhar, V. R., and Davidson, D. Learning new words. Granted US Patents, 9594741, 2017.
Tien, N. L., Habrard, A., and Sebban, M. Differentially private optimal transport: Application to domain adap- tation. In Kraus, S. (ed.), Proceedings of the Twenty- Eighth International Joint Conference Artificial Intel- ligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 2852-2858. ijcai.org, 2019. doi: /10.24963/UCAI. 2019/395. URL /https::////tttt /tw.//oooooooo (01aii.011//3
Singhal, V. A polynomial time, pure differentially pri- vate estimator for binary product distributions. CoRR, abs/2304.06787, 2023. doi: /10.48550/ARXIV23004 06787. URL. /tttts:://dttttt org/ 488550/ arXiv. 2304 06787.
http::/ddooooogg//// wrg/10.gg//.oooo 24963/
Tsybakov, A. B. Introduction Nonparametric Estimation.
Solomon, J., de Goes, F., Peyré, G., Cuturi, M., Butscher, A., Nguyenn A., Du, T., and Guibas, L. J. Convolutional wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans. Graph., 34(4):66:1-
Springer series in statistics. Springer, 2009. ISBN 978-0-
387-79051-0. doi: 110.1007//13794, URL /https::////
doi.org/1i /10 007/b13794
66:11, 2015. doi: /wt.111...11111911 URL /https:// doi org/oorgg/oooo 15/ / 27 66963.
Villani, C. Topics in Optimal Transportation. Graduate studies in mathematics. American Mathematical Society,
2003. ISBN 9781470418045, URL HRRL/htts://boo
Solomon, J., Peyré. G., Kim, V. G., and Sra, S. Entropic metric alignment for correspondence problems. ACM Trans. Graph., 35(4):7::1-72113, 2016. doi: /10.1145/ 2897824.2922903, URL /https:/ / /ttpioooo/....////////////////1/ 2ttp://89992...22222
Villani, C. et al. Optimal transport: old and new, volume 338. Springer, 2009, ISBN 978-35540-71049-3, doi: N0011007997833554-7700555
Staib, M., Claici, S., Solomon, J., and Jegelka, S. Parallel streaming wasserstein barycenters. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA. USA. pp. 2647-2658, 2017. URL htt::/tttt////t/ neurips.cccppper//222. /ttp:////////tt//p////eeeg//o/// /proceedinss. 25387055922133Ba334468818 Abstract.htm..
Wagner, I. and Eckhoff, D. Technical privacy metrics; A systematic survey. ACM Comput. Surv, Swrv,, 51)3555::373 2018. doi: / URL /wttt/tt/////// //di. org/10 10 1145/1116223
Wasserman, I.. A. and Zhou, S. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38, 2010. doi: /10.1198/ jasa.2009 iasa.2009. URL /https: / ddw..oor//0000 1 1198/ jasa. 2009 em08651.
Weed, J. and Berthet, Q. Estimation of smooth densities in wasserstein distance. In Beygelzimer, A. and Hsu, D. (eds.), Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Pro- ceedings of Machine Learning Research, pp. 3118-311 3119. PMLR, 2019. URL /http::///////// http:://pocceednee mlr. press/ve /v9s/v99// 9/we//l1111 9a html
Sweeney, L. Simple demographics often identify people uniquely. Health (San Francisco), 67 6334200)):1-34, 2000.
Sweeney, L. k-anonymity: A model for protect- ing privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst., 10(5):557-577, 2002. doi: /10.1142/
S021 50218488502001648. URL /https://////// /tts://dooii /tt..oooiooo/////////o/o 10.14428021448820010
Xian, R., Li, Q.. Kamath, G., and Zhao, H. Differen- tially private post-processing for fair regression. In Forty-first International Conference on Machine Learn- ing, ICML 2024, Vienna, Austria, July 21-27, 2024. Open- Review.net, 2024. URL //ttts:://// openreview. net/ http:/oooummmddeeeeeeeeeeee
Tameling, C. and Munk, A. Computational strategies for statistical inference based on empirical optimal trans- port. In 2018 IEEE Data Science Workshop, DSW 2018, Lausanne, Switzerland, June 4-6, 2018, pp. 175- 179. IEEE, 2018. doi: /10.1109/DSW2011 8439912.
Yang, C., J., and Zhou, A. Wasserstein differential pri- vacy. In Wooldridge, M. J., Dy, J. G., and Natarajan, S. (eds.), Fiirty-Fggtth AAAI Conference on Artificial
URL /https:/ / wwt.:////o..../////////1/. 2018. 8439912.
16

---

On the Private Estimation of Smooth Transport Maps
Intelligence, AAAI 2024, Thirty-Sixth Conference on In- novative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Ar- tificial Intelligence, EAAI 2014, February 20-27, 2024, Vancouver, Canada, pp- 16299-16307. AAAI Press, 2024. doi: 110.1609AAAAALL3811152222555 URL /https:// doi. boi.orrg10, www1///000.........
29565.
Zemel, Y. and Panaretos, V. M. Fréchet means and Pro- crustes analysis in Wasserstein space. Bernoulli, 25(2):
932 976, 2019. doi: /10.315011--EJJ100 URL
/https: http://doo..og///////// 3150/17 BB51109.
17

---

On the Private Estimation of Smooth Transport Maps
A. Details on Wavelet Decomposition
In this article, we adopt the same conventions for functional spaces as (Hütter Rigollet, 2021). In particular, we encourage the reader to consult Appendix in (Hütter Rigollet, 2021) for formal definitions of the functional spaces considered in this paper.
A notable difference from (Hütter & Rigollet, 2021) is that all the functions considered in this work are supported on Q which is hypercube rather than more general Lipschitz domain. Therefore, we can restrict the wavelet basis to functions whose support is included in & only, thus avoiding overlaps with the complement: for any function in this basis, its support either included in S2 in $2 U aΩ.
As consequence, if f E Vy, and if )x.si denotes its wavelet coefficients in the corresponding wavelet basis, then
)
(32)
B. Technical Tools
Lemma B.1. There exists an open neighborhood O of in 1884 such that
MEO
=
|det + M) - - (rr(M) ||
(33)
where O only affected by the choice of ||
Proof. By computing the partial derivatives of M + det(Ly + M) in the canonical basis of [R9 we immediately that the gradient of M + det(T, + .) at O for the Euclidean structure induced by the Frobenius inner product is la- Consequently, since M + det(T, + M) is C (it has polynomial expression in the coefficients of M),
det(I, M) 1 + tr(M) + ([)
(34)
The equivalence of norms in finite dimension allows us to conclude.
Lemma B.2. Let LI....,,IM be M independent random variables with Laplace distribution (that is, with pdf + 2 ce-1d)
w.t.t Lebesgue's 's measure). Then
E
max i=I.....
Lil
51+ x1+In(N)
(35)
Proof. Let 8 2 0, by independence,
max
|L $8 =P n
(1L,) S $0)
N....NN N
N
(36)
(([L <))
1
(1 - 6)
18

---

On the Private Estimation of Smooth Transport Maps
Thus,
= 1
E
max |12l
P max !=
[14] > 6)
d8
= .
10,+00)
S (0,+
1 (1 - e- d8
(1 1 (1 - -2) )) du
10.1)
(37)
(1 u) maax(0,1-Nu))
f ((0.1) (1 (1-mang max(0, Nu))
du
u
= -.² (1- 11-max(0.1) -N)) du + {[ (1 max(0, Nu))
du
u
$ 1 (1++)(N).....)
1-9 jk.jgg its wavelet coefficients for compactly supported mother and father wavelets, and with support adequation to 52 as described in Appendix A. Then
Lemma B.3. Let f E J,, and denote by ("r
11 399 Dasalloo 11 )a.. S 11 S ><
(38)
Proof.
ll
1
f2
Vol i
Parseval
1
11 (()2))))...)) )..i.
(39)
Vol
52
11 1-9 )as.alle
(1 ( )oollloo
The inequality
|| 2 (1(77:9) Ja.i.oloo
(40)
comes from Lemma 24 in (Hütter & Rigollet, 2021).
C. Proofs of Section 2
C.1. Proof of Lemma 2.5
Following subsection 5.4 in (Hütter & Rigollet, 2021), we use || == |l -11xa(p)) and we define
VS, So()) = s(f) - -((6), $6( = 5(f]X Vi.) - S(fl (fo Vi.)).
(41)
Vr 2 0, J)(T9) ( (, So(l) - +2)
(42)
and
i y So(f)
(43)
Furthermore, we define f = fu E V, (2MM) and, for a > 0, we also let
== s + (1 -s)f, where
(44)
o+ ||
IV v
19

---

On the Private Estimation of Smooth Transport Maps
Following the same steps as in Proposition 11 from (Hütter & Rigollet, 2021), obtain
V pMiV Vfll
IV.. vfl = = f VfIl
(45)
0 +
V Spri
vʃll
and
So(fa) 40 + |V V =: =²
(46)
follows that, f. E FT( and, therefore, f F)( since we have So(f) - So(fe) S r² by the definition of f. We now turn to controlling the error of the semi-dual. We have
S(fa) = fpw)) + (1-s)$(f)
S (S(fpiv Y1:) S(f)Xim Yim)) +S((f) (1 111-s)33 ())((f)
(47)
< U + S(J)
where the last inequality comes from the optimality of f for the empirical semi-dual problem.
Hence,
Su(fa) - So(f) +2
[So(f) - So(f) SEFr(r2)
sup
(48)
The rest of the proof follows the same lines as the end of Section 5.4 in (Hütter & Rigollet, 2021), replacing So (f() with So(f) U and f with fpnv-
D. Proofs of Section 3
D.1. Proof of Lemma 3.2
This result is folklore in the literature differential privacy, we include its proof for the sake of completeness. To simplify notation, let us look at the case where the scaling factor front of the Laplace random variables in (15) is one. The general case will be obtained by scaling. Let D D' be pair of neighboring datasets, let [I....,N). We will condition on (e All that follow holds almost surely.
P (i(D) = k| (Tx))))))))) P (N (Ja(D) + La < (c) + Lue (bxx))))
(49)
Notice that took strict inequalities (<) because Lx absolutely continuous w.r.t. Lebesgue's measure conditionally on (Tee 4k, and hence, ties occur only with null probability.
Thus,
P (i(D) = 1o)( )o4K)) = P
L* < min (fx - fa(D) + Lwn) (Lw))res))
K'gk
(50)
minur (DD)) c -1
Hence, two cases occur
Case A: minw*4 (Dw fa(D) Lw)) 50
P (i(D) = kk *k((
1
(51)
Case B: minua de (fw(D) fa(D) Lxr) >
P (i(D) = 11(
=1
(52)
2
20

---

On the Private Estimation of Smooth Transport Maps
Now, we can look the ratio P(((D)=R((()))))))) First, we can notice that P(((""=a((())))))))
( mmin K'
(min K'zk - Jn(DD (b(() (aii))((mjp (Jw((D') (D=( + Lx+) $2a
(53)
Indeed, since the sensitivities of (fk)* are uniformly bounded, for any k' + k.
- = (D) A) (fx(D') - A) = fi²(D') fa((D)) + 22
(54)
and taking the minimum yields half the result. The other half is given by swapping D and D'. Then, by using (DD as a short for ming * (Dw fi( + Lg=), we can look at the following four cases:
Case 1: ((D), <
(i(D) (((Le))AsK))
(51) 3 ee((D)
JellDa S cD(D))-((D) (53) 2
(55)
P (i(D') (((
Case 2: <0< I(D)
(i(D) kl( )x (514215)
1 (e((D)
/ (D)))
2
(((D))((())
(56)
P (i(D") k((Lx)NHH)
-
e-(D) 7 (DD))(())
Since ((D) <D)<0<<(D))
(D))-((D <1.
(57)
Furthermore, a simple study of the function x + 2 _ ((D') on (-x,, 0) shows that it is non-increasing (because t(D') > 0), and thus that
((D)
e -(DD)) ((D) > 1 e 2
1
-(('))
1 2
(58)
In the end,
P ((DD) kl(Lw) )R(
S ((D))
(53)
S 20
(59)
P (i(D") = (((LL))
Case 3:
P (i(D) b1(Lw) )
K(D)
(D)- c (DD)
2 (DD))(()
(51)2(52)
P (i(D') = k((L))44K)
Je((D)
(DDD)-((D ((())
_ (())
((D)
(60)
(1) ((D) 2
I ((D)
< 24
21

---

On the Private Estimation of Smooth Transport Maps
Case 4: ((D),(D)) >
(i(D) = ((((L))
z (())
(52)
P ((D)) = k:((x))))))
2 -
min (D'))((D) 6-4D))
e 36 (e-((D)-UD) (D)) (-(D) 1 3
1 (e-((D)-(D))
2K()
3
(61)
(
(l((D)-<(D))
(53)
S 22
Thus, we have shown that P((D)=N((Lu)ees (eze) S625.
((
Integrating over (Ly +1 yields
E Deeee
(P (i((()= kb ((( S 2 E (P (Pi(D')
kk (( (x
(62)
which translates to Finally, since this is true for any k, i c-DP when A $ This concludes the proof by scaling appropriatetly.
P (i(D)= =k) s eAp (i(D')= =k)
(63)
D.2. Proof of Lemma 3.3
Let (X1:x) Y1m) ~ (Xis. Vi...) be two neighboring datasets. By defimition, they contain the same data points except for one individual. Suppose first that Vi.. = Vim and that, for some E [n]]. the datasets X1.. and X differ the i-th coordinate only. Then the term f|lf is obtained by noting that, by the triangular inequality
[SU((X Ylm S(f((Xtmm 1im 1I = 1 ( -
fll
n
In the opposite case, it holds that Xim = X1.. and that the datasets Yim and Yi., differ in one of the coordinates i E [m]] We first prove that f is Lips-hips on Ω.
Let y1,92 E Q, let æ e 8
(x, ve) - f(x) (z, f/1
822 + (x,, v2) f(x)
Cauchy Schware
I
|| |1 - 3/2l + (zz 122 f(x)
(64)
< 1Qllin vell + (x. f(x)
Thus, taking the sup with respect to z on the left-hand side and on the right- hand side yields
(v1) S (6ll w2ll (z2),
(65)
and since y/1 and 3/2 play symmetric roles,
(x2) < [61ll11 -22l + fv1)))
(66)
[ Lipschitz w.r.t. any of the Ys. and therefore, changing the value of any of the Ys can only affect the value of S(f)X1sns Yi.)) by at most 20 by triangular inequality.
Hence, ((f)X1mn V1..) is
22

---

On the Private Estimation of Smooth Transport Maps
E. Proofs of Section 4
E.1. Proof Lemma 4.1
Let fi, f2 E X. We observe that [l. - f2l I Ilfi - falloc, since for any y E Q
fi(1) fz =: sup (a. y) (xx) + inf { () + fa(x'))
x
=supinf inf (x (x- + f2(x') - f1(x)
S sup inf (x- + f2(x') - f1(x)
sup f2(²) - f1()).
Thus,
1 > (f( f2(X.)) + 1
- - S(ff 1:m Y2mn
71 i=1
(67)
1 S2llxc + +I.ʃi -12llo0
fi 521100
E.2. Proof of Lemma 4.2
By Lemma B.3, we have
Vy n (2M2 C (0,
(68)
for positive constant C, where ll- (0, r) refers to the closed ball of Vy with center 0 and radius r 2 0 for the norm ||- Iloo, (the infinite norm of the vector of coefficients the wavelet basis).
Since this is ball in dimensiimeniional space for distance in infinite norm, it is possible to build 8-covering of this ball with 5-grid on the coefficients of the wavelet decomposition, which is of cardinality
(
[2CM2 8
dim(Vs)
C₁
(69)
Furthermore, because of the bounded support of the father and mother wavelets, dim(Vy) S 2d (see page 30 in (Hütter Rigollet, 2021)). Thus,
Cd
C2 c, s ([2CMP)
(70)
8
where C' is constant that does not depend on J and 5.
Let us consider the following construction: for each element of this covering, if there exists point in V, n (2M) at distance not more than 8, we replace the original element by this new point (we choose any point that satisfies this condition in case of non uniqueness). Else, we remove this element if no point in V, n X2MM) satisfies this condition. By the triangular inequality, this construction yields 26 covering of V, n (2M) for || llo. of cardinality at most Cy-
Furthermore, by Lemma B.3, -coverirei of V, (2M) for || | 8-covering of V, (xx(2M) for the usual infinite norm Il
Scaling 8 appropriately concludes the proof.
E.3. Proof of Theorem 4.3
We will control
F Yim) $(fu Yim)
(71)
We work conditionally on X1.0; Yi.n- All the relations below hold almost surely.
23

---

On the Private Estimation of Smooth Transport Maps
Since CJ,M is d-covering of Vy n (2MM with respect S1-[X1mm X1m) by Lemma 4.1. Thus,
||
lloc. it is also 26-covering of V, (2(M with respect
S(Sprvl X1m, Kim) S(fs|X 1:ms YI:)
S(F(LD) 32M V 36d
-S(fs Xiss Mim)
min
Li
me
32M 36d
5 1E() (E(1...((CC.aa)
min
((T]|X 3(fs|X Yisn)
max
Li
n2
(72)
32M V 36d
min
Ilfe fulloo + max
L
(e(I...((CMMM)
32M V 36d
< 28 + max
Li
By integrating over the source of privacy and by Lemma B.2,
In(# (Ct.M))
E,, (CNM))))
(D)
(73)
2 In
C2/l//2
+
8 +
ne
C2 yields
where 2 is a constant independent of / and Fixing
(D) < 2 In(ne)
En (cn,e)))
(74)
By Lemma 2.5 and subsection 5.5 in (Hütter & Rigollet, 2021) in order to control the bias,
E (dlTprive (o)() S
2d (/dcn(nc)
+
22 In(n) + + 1R22220 2Jo
1
(75)
for J larger than suitable constant.
24

---

On the Private Estimation of Smooth Transport Maps
F. Proofs of Section 5
F.I Proof of Theorem 5.1
The proof of the lower bounding terms 1 and n -0+a uses standard packing arguments (Tsybakov, 2009) with a specific n packing for the problem at hand. It may be found in (Hütter Rigollet, 2021). We only provide the proof for the additional term (ne) 2044_ 22444
is based on packing arguments for differential privacy standardized via couplings in (Acharya et al., 2018; 2021; Lalanne et al., 2023a). We start by building a packing similar to the one from (Hütter & Rigollet, 2021), which later analyzed with TV distances instead of the traditional KL divergences order to highlight the effect of differential privacy.
2e
Packing construction. Let m be integer that will be specified later in the proof and let N m We consider k
the grid ((n
This grid has cardinality N, therefore we can enumerate its elements as (PI....,PN) E (IR.)._ By construction, we have that
ka (m+11.... m+1
Vi,j E (I,..,,NN, N), i = lpp: pill 1ox 2 m + 1
(76)
Now, we consider a C "bump" function B defined over IR and supported on [-1, I], taking positive values over (-1,
1).
For such a function, there exists vp (-1, 1) such that (xro * and B' (mo) #
For some sufficiently small constant 0 whose value will be fixed later, we define the function
d T2 2
((11 Fd) = II
B
(77)
==1
and for some h E (0, 1] and any 0 E {0, 13%, we define the potential Φo 52 -
R
as
(.)+) = _ 11111 + + Σ
1
N
0,00
Pi
(78)
To ensure that the functions v (1/ for E NV. have disjoint supports, we take h < 2mm+1] 2 1
m
First, we show that for any 10,1)%, Vén E Ta:
(Bounded transport map) 64 f0, 1 vz 52,
N
I x- Pi
Vol(z) = ha
V
(79)
h
i=1
and since the supports are disjoint, only one term in the sum is non-zero, which yields
v0 E (0, 1) Vo ② [[Voo()) x|| < ht Vb
(80)
Choosing a small enough ensures that v0 E {0, 1 Ve E Ô. [[(()) s M. (Strong convexity of the potential) V0 E 10,1), Vr Ω
V La + h Σ 2
x
(81)
h
and thus, since the supports are disjoint,
v0 E (0, 11 Ve Ω
[))))(()) - Tallop - h- sup || 2 1
(82)
where the right- hand side can be made arbitrarily close to 0 by taking a small enough (since h--1 S 1). which ensures that V0 E (0, N, Yo 2 1 = (2) < M.
25

---

On the Private Estimation of Smooth Transport Maps
(Stability of the support) Let {0, 13%. It follows from (80) that, when h m one can take small enough ensure that
h )) c Boo (p),
Vi, Voo Boo
pi: 2
(83)
Furthermore, since outside the balls of the form (Boo (pis ))). Vee is the identity, we have that (o) C Ω and that
Vi, Voo (Bx (pc, hi) C B (pi,
(84)
We now give additional details on the properties of Vég- We have proved above that dh strongly convex for any 0 {0, 13 It follows that Voo is injective and that, for any E f2, the Hessian (2) > 0 is invertible. Since Vdo is C over S2, the global inversion theorem states that Vóg is a C diffeomorphism from $2 to (d)
We may also see that the inclusion (2) C Q is in fact an equality using arguments borrowed from basic algebraic topology. First, Vøg the identity over An. Suppose for the sake of contradiction that Ω Vhg (S2) 0 and let E 22 Vol(S2) (æ & On since Vog is the identity over 08)). Then, letting Tz be retraction of Ω {x² an (which exists), we obtain that o Vio is retraction of f (which is homeomorphic to B(0, 1)) to an (which is homeomorphic to @B 1)), which is impossible by Brouwer's theorem (see Theorem 7.6.2 in 2024)).
As consequence,
A0 E 13,, Vor(?) = Ω
(85)
By injectivity of the functions de's ss this immediately yields
A0 E (0, 13,, (Vo))-1(()) Ω..
(86)
Finally, the same arguments applied to the supports of the functions vi ('>i)) ensure that, for small enough 0,
we have
vo E (0, Vi, Voe (Bx (pr, h1) = Boo (p:,h)
(87)
By injectivity of the functions do 's we similarly obtain
vO E (0,1)N,Vo Vi, (Voo)-* (Bxo (pr. h)) = Boo (pr, h)
(88)
(Smoothness) Let A E 1).. Using multi-index notation (see (Hütter & Rigollet, 2021)),
d V (a)) = Σ
|80 (Von); (x) - 86 (Véo); (1)
Σ
18b (Voo), 1la
Σ sup wyuwer
(89)
r y o-oaaa
Sa
=1A,b
B:
Furthermore,
N Ar, = @ Coord., + a Σ (Ve), 1=1
(
Pj
(90)
h
where Coord.; is the projection along the tth canonical vector. Thus, A., can be made as close as we want to ||ad Coord.; granted that the constant a is taken small enough.
26

---

On the Private Estimation of Smooth Transport Maps
Finally,
sup Bibb a4y,2,EE
8 (z)rd., + ha-
Σコ= 0 (Vb),
N
Z-Pi 8h Coord.: h 10 E3 0,00 ('7"
x y/ 1/0-Lo)
[a]
1a- 19 Σ
11
sup
1= (V+)),
2 P-
Dー (vv))
< hh-M
sup
x
y - [o]
(91)
(V(())
B-Ds
06 (Vb))
リーP;
Disjoint Supports & Coniiuuty
h aa-1bl max
h
sup
x
y 10-1000 [a]
@b (V
P1
(V
y-
< /t" [6]
max
sup ERR
[a
1 b) (x) 1
(Vv), (w)
aa- by max h (a- (a.)
sup
(0 b) (z) 0 (vb): (v)
sup SYRRER
x y a-|
Hence, B can be made as small as we want to 0 granted that the constant a is taken small enough.
All in all, if the constant is taken small enough, supa V Voollcu(h can be made as close as we want to Identity | (oy which guarantees that sup, |/Voellc S R if small enough.
Similarly as in (Hütter & Rigollet, 2021), we consider the family of statistics (So == p&n Q 10E(0.1) on the problem where
P = )
(92)
and
v0 (0,1)
Qo P4Voo
(93)
It is thus possible to simplify the lower-bounding problem as
E (f17O- TT)-
- - (
inf sup
2 inf sup Es,
(94)
T P.M.
1 8E(0.1)
where the supremum is now taken over a finite family only.
We verify that this family of statisties forms a packing for the pseudo metric defined below (with some overlap in the
notation)
= d(01,02)2 = |Vvoo Venn PP
(95)
Lemma F.I. For any 01, 02 10.13
d(Se, So )2 2 dram (01, 02) h 1,2d
(96)
27

---

On the Private Estimation of Smooth Transport Maps
Proof. Let 02,00 (0, 1) then
JA.IE |Vás, - -Vo0ll
Disjoint supports
Supportssppports
N Ehonr |00 - V2)
2 - Pi )|²
dr
h
Change variables
dham (0,, 02) 2ard
||
(97)
dram (01,02) (0,,0))22tt4 2aatd
From line 1 to line 2, we used that 101- The change of variable = -t in each of the remaining terms yields the term hd.
02 is equal to 1 only dham (01,0)) times, and is it equal to 0 in the other cases.
Upper bounding the TV distances. To proceed with the lower- argument, remains to lower-bound the testing difficulty between the hypotheses of this packing. Techniques for bounding the testing difficulties usually require bounding the KL.-divergences between the statistical models of the packing and reference measure. This the approach proposed in (Hütter & Rigollet, 2021), which leads to a lower bound of the order of V n 2 However, under differential privacy, the test difficulty is characterized by the TV distances between the untensorized marginals of the statistical models. This part of the proof is dedicated to controlling these terms.
Lemma F.2. For any 11, 02 {0, 13 it holds that
TV (Q2: Qo,) S dham (01, 02) h ---d
(98)
Proof. By the change of variables formula, for any (0, 11 the density Qo with respect to
dQa
dP (y) 1 [..
(99)
(eo
for P-almost all y. Let 01, 02 E {0,1]
dQo
dQ0a
TV Qo,) = 2 (-1,2) dP
(y)
(y) dP(y)
dP
(100)
1o.11 det(V2 ((VΦe,) (g))) ((Voo)((V
dy
((Vo,) (V
and by stability of [o, 1]dd and of its complement by either Voe, or V Voe,. this expression can be further simplified as
TV (Qo, Qo,) = /
dy
de ((Voo,)~'())
det(VZZoo, ((
(101)
10.
Then, since both Vée, and Veo, are the identity outside balls of the form Boc (p:, h), and since these balls and their complements are stable by Ven, and by Veh,, this can be rewritten as
1 Σ
1 det(VV ((Voo,)- det det(VVoes det(Ve"ee
1
TV (Qa, Qo.)
dy
(102)
2
(pt.h)
This expression finally further simplifies
TV (Qo. Qo.)
1 det(VVZo, ((VØ,,) -170,,)-((1)) (y)))
0 40
(Voe,)) - dy
(103)
B. (p).))
28

---

On the Private Estimation of Smooth Transport Maps
We treat the case 0 0, 0g
1, the other case being treated similarly. In this case,
A,
det det(V ((Vooz) (1))) dy
(104)
= BBoopp.d))
|dot (V2 Φo, (ar)))dx,
det (ett (z))
where the last line comes from change of variables and from the stability of Bo (pi, h) and of its complement.
For any x E (p,,
V2 (0) = 4 v
(- Pt
(105)
By Lemma B.I, that if is chosen small enough, then have det(VV (-)) S 2 uniformly over 3o ht. Finally, and again by Lemma B.1, if is chosen small enough, Va B (pi, h),
S 1ha-1 (1r V
(Ir(v'v))
(*
- Ps ))
I -
Ps
1)
+
(106)
det 22
which entails, by a change of variables,
ha- h2-1+d
/ (11+(>3))+ x h--1+
A
(107)
2
Plugging this result back into (103) yields
N
TV (Qu1: Q0,) S a Σ
11 40!0
(108)
i=1
dham (01,02) B2) h-
Private distributional tests and private Assouad method.
Lemma F.3 (Assouad's Lemma). Assume that there exists such that for any 0,, 0g E 10,
Z dnam (01,02)
(109)
Let T be any estimator and define 0 = arggingg d(T,, Volo). Then it holds that
(1IV0D-
N Poo. (0' #0) + Po.. (0' # +1)
sup Eso 10
-
2
(110)
mm1
where Po;; and Pe are the mixture distributions
Po
Σ
Sa. and Po.,
Σ S
(111)
2N
2N-1
0.0
0:g(8) m0
Note that in (110) there is second layer randomness that implicit, and that is w.r.t. the estimator itself (for privacy for instance).
Proof. The proof can be directly adapted from (Acharya et al., 2021) by substituting the notation with that used in the present paper.
29

---

On the Private Estimation of Smooth Transport Maps
Lemma F.4. I satisfies e-DP, then for any i,
Po_,(0' #0) + Poz,
+1
Σ
= (6t -1 1,0.itt..... L.,eit
(112)
2N-1 ,1.... e(0,11
where 0 is built from T' as in Lemma F.3.
Proof. This proof builds on coupling arguments from (Acharya al., 2018; 2021; Lalanne et al., 2023a). Let us consider the coupling C that selects 01, ... 011 1 ON {0, 1) uniformly random, and then samples accordingly
X b X P
(113)
and
Q
(114)
where Q is the optimal coupling between Q( "0.....00-110000 0,001.0000 and Q 1,,00- oN) Here, the optimality means that if (Y, Y") Q, then
,,, P(Y = Y') =1 11 TV (Q(o "0000....001,,,444.... Q(0),.., ...,,'-,,,,110 (...,...1111000.....)..
(115)
The existence of such coupling is well known (see, e.g. (Kallenberg, 1993)). Furthermore, we let XI...., X be copies of XI...., X Then ((X Xn, .i...., Y.), (X, X,, Yy.... X!)) (whose distribution is C) is a coupling between Pe,, and Po_.-
Thus, we may write
Po. (0' +0) + Po,, (0' +1)= =
(116)
Ee (P(0) +
Yı, NY,,,.,,yy + P(0' X v/, Vi,..,,,yy Y2)
where the inner randomness (i.e. inside the expectation) only w.r.t. 0¹ Since T is c-PP, then so 6³ by post-processing.
30

---

On the Private Estimation of Smooth Transport Maps
Thus, by group privacy and the characteristic property of differential privacy,
(o_, #0) Po,, (0' -
Ec (P( Xns Ii...., Yx)) 0) + 1(00 X ,.....,,,,) ,Y,) # 1)
-ithaam (A Xx x. ((X X Vi..... ..... yii) + 0)
2 Be
+P() Xx v. X..Y
xD) 1)
edham ............................... K.). K.
2 Be
X Vi V,)) # (....,...
P " * 11
(117)
Ee (e -cduum (Ki Nni Xnx Mnn Na.
=Egi 0i- (1:11 .N,
E [(x Xnn 2 (e ( Na Ka
Jensen
Egg 0i 1,0
CE -x Xn w. YaS00, X.. v....... (gg (dram ((XI..., Yo... X,, (.......
1
Σ
2
1,0++1
E(U.1}
where the last line comes from simple computation.
Conclusion of the proof.
As consequence of Lemma F.1, Lemma F.2, Lemma F.3 and Lemma F44
inf sup Ess, (fIV a((2pp) 2 2d -nnck-i+e T B
(118)
where C > 0 is a positive constant. Finally, since N taking h x (ne) Tna yields
(11V60-211 2 (ne) o-ite,
inf sup Ese @e(0.1)
(119)
and (94) then concludes the proof.
G. Practical algorithm
This section provides further details how obtain numerically tractable algorithm derived from the ideas presented in Section 3 and Section 4.
G.I. Choosing J
First, determine J achieve the best virianariance tradeoff. Using Equation (24),
= = min ([110g2(1))
log2(n)
logg(nc)
)
20 d + 2a
31

---

On the Private Estimation of Smooth Transport Maps
This choice asymptotically yields an error
2 J R (log2(n) + (nc)())) x Upper-Bourd Bound Equation (25),
where we explicitly track the scaling in R and retain logarithmic terms.
G.2. Constructing the Covering & Enforcing Conditions
With J fixed, we construct the covering. From Equation (39), controlling the infinite functional norm by the vector's
infinite norm requires computing V Vo)( In the paper, we assume Vol(s2) = 3 but since Ω only needs to be a hypercube containing Q in its interior, we can instead set
Vol($2) = (1 + 7)
for any fixed 0.
In Lemma 4.2 and Theorem 4.3, we first construct a 5 = (nen covering in vector infinite norm for the space of wavelet coefficients up to J", within a radius C.22, where
C= 2v Vol(
This covering is straightforward since it requires only axis- wise discretization in the space of wavelets coefficients.
The challenging part follows: the conditions Hessian eigenvalues and the potential's norm/gradient may not hold. We enforce them via the reasoning in the end of Appendix E.2. While this step is theoretically sound for obtaining the upper bound, we believe it is intractable in practice.
To address this, we can approximate using a grid, as in Section 6. This does not affect the privacy analysis but may introduce numerical errors that vanish as the discretization step decreases. Candidate potentials are now represented by their grid discretization and live in the span of wavelet discretizations up to level J
For each candidate in the initial covering, check whether a nearby potential (within distance 8) satisfies the conditions the Hessian, gradient, and potential itself, following Definition 2.3 and the end of Appendix E.2 in discretized manner. At this stage, existence testing reduces to a convex optimization constraints, since numerical differentiation schemes are linear operators. A numerical solver can efficiently handle this step. The set CJ.M is thus constructed using this quasi- proje-projection approach (see Appendix E.2) applied to each candidate potential from the initial covering.
Sooblemmmiimmizing the infinite norm of vector under linear
G.3. Conclusion
This concludes the practical implementation of our estimator. While computationally expensive, it was designed for theoretical purposes. However, we emphasize that the selection rule in Section remains valid for any set of convex potentials with bounded infinite norm corm-ensuring meaningfulness in optimal transport theory and privacy analysis.
The complexity mainly lies in generating candidate potentials (which is not due privacy but rather to the difficulty of the non-parametric nature of the potential estimation in (Hütter & Rigollet, 2021)), whereas the selection procedure itself is more practical. Thus, with realistic potential generator (e.g., leveraging prior knowledge), our private selector should yield strong utility in practice.
H. Potential alternative approaches
H.1. Plugin estimators
An alternative approach could be estimate privately both the input and output distributions, and to consider the optimal transport between those estimates. Such technique is usually referred to as a plugin estimator.
For our problem, it typically requires additional assumptions on the regularity of the source or the target distributions (Manole et al., 2024). We are confident that such a technique could lead to good results under this more restrictive setup, yet it would require extra work as it requires stability of the estimates in W2 distance, whereas most results on density estimation under differential privacy are stated either in terms of infinite or L2 norms (Wasserman & Zhou, 2010; Barber Duchi, 2014: Lalanne al., 2023b; Lalanne & Gadat, 2024).
32

---

On the Private Estimation of Smooth Transport Maps
H.2. Gradient-based approaches
The semi-dual problem is finite-dimensional convex optimization problem once discretized in the space of wavelet coefficients. Differentially private algorithms for convex optimization (such DP-SGD) could, in principle, be applied directly.
However, the problem is that f (the Fenchel conjugate which appears in the optimization problem) does not admit a closed-form expression in terms of the coefficients, akin to its gradient. In addition, it is not guaranteed that the problem benefits from gradient smoothness or strong convexity, also limiting approaches such as objective perturbation.
33


Reviews:
[{"review_id": "BZNQPIwkTJ", "reviewer": "Reviewer_tgzq", "summary": "The paper studies the private estimation of smooth optimal transport maps using a semi-dual formulation of optimal transport, where the transport map is obtained as the gradient of a Brenier potential. To make the problem tractable, they restrict the function space using standard nonparametric estimation techniques with wavelet bases, following the approach of Hütter & Rigollet, which provides minimax bounds for transport map estimation. The core contribution is the introduction of differential privacy (DP) by injecting Laplace noise into the empirical semi-dual objective function $\\hat S(f_i)$ ensuring that the estimation process remains private while preserving statistical guarantees. To implement this, they define a finite set of candidate functions $C_{J, M}$ which forms a discrete covering of the function space $V_J$ (merely a span of restricted wavelet basis) and the semi-dual objective is then computed for each function $f_i$​ in this set, and added classical Laplace mechanism to the values to enforce privacy.\nThe private transport map is then obtained as the gradient of the selected function. The paper rigorously analyzes the trade-off between privacy, statistical accuracy, and discuss some computational feasibility, proving upper and lower bounds on the estimation error and demonstrating that privacy constraints degrade the convergence rate but remain reasonable. Unfortunately, the lower and upper bound does not match.\nSome numerical experiments provide some illustration on toy examples.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.\n\n- **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?*\n\n  **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.\n\n- **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.*\n\n  **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.\n\n- **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.*\n\n  **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.\n\n- **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.*\n\n  **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.\n\nWe would be happy to discuss any remaining questions during the author-reviewer discussion phase.", "claims_and_evidence": "The claims of the paper are mostlty theoretical and supported by formal proof.", "methods_and_evaluation_criteria": "Only toy experiments are presented to illustrate how the proposed transport map are close to the optimal one. Unfortunately, these synthetic illustrations might not reflect practical performances, specially for nowadays highdimensional ML problems.", "theoretical_claims": "I briefly skim into the appendix but not read in details.", "experimental_designs_or_analyses": "As commented above, the numerical experiments section is rather weak and serve as toy illustrations for the theoretical claims.", "relation_to_broader_scientific_literature": "N.A", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The theoretical analysis and presentations are cleanly presented with transparent assumptions.\nThe minimax bounds is similar to (Hutter & Rigollet, 2021) $n^{-1} \\vee n^{\\frac{-2 \\alpha}{2 \\alpha - 2 + d}}$ with the additional differentially private term $(n \\epsilon)^{ \\frac{-2\\alpha}{2\\alpha + d} }$.\n\nThis additional term is unfortunately not tight; how the privacy mechanism interacts with function approximation is quite mysterious at some points.", "other_comments_or_suggestions": "Several use of same notation $M$ but with different meaning accross the text", "questions_for_authors": "- Assuming the function class $\\mathcal{F}$ is parameterized in a finite-dimensional space and Once the problem is formulated using the 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? Examples in mind (https://arxiv.org/abs/2207.08347 , https://jmlr.org/papers/volume12/chaudhuri11a/chaudhuri11a.pdf , https://proceedings.mlr.press/v23/kifer12.html).\n\n- Any plan to include experiments with real dataset or more realistic ML setting where DP OT map are needed?\n\n- The choice of the constant $J$ and the finite function set $C_{J, M}$ ​ remains unclear throughout the paper. It is difficult to keep track of how these quantities are selected, particularly since $J$ appears to depend on the dimension $d$ in an implicit manner, yet its exact scaling is not clearly derived or discussed. Additionally, the \"constant\" $R$ is not formally defined (coudln't find it), making it challenging to understand its role in the function space discretization. Theorem 4.3, which should provide precise details on these constants, remains evasive on their explicit dependence, even in the proof. This lack of clarity significantly affects the practical implementability of the proposed method\n\n\n \"## update after rebuttal\"\n\nI thanks the authors for the clarifications they provided during the discussions. The points on selecting the parameters are a bit more transparent. I maintain my score and not increase it because the numerical experiments are clearly weak and do not illustrate the initial motivation presented by the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jbi2Xww8GK", "reviewer": "Reviewer_3Ra6", "summary": "This paper considers the problem of learning the optimal transport map from $P$ to $Q$, given samples from each, under the requirement of (pure) differential privacy. They impose assumptions on smoothness of the optimal map which are standard in the map estimation literature. They obtain an upper bound using a noisy argmin mechanism and a covering argument. Their lower bound employs standard packing arguments.\n\n## Update after Rebuttal\n\nI am still borderline. The result is relatively interesting and the domain is new from the perspective of DP, but the privacy tools applied are pretty standard. Use of standard privacy tools is fine - the real question is whether their analysis is novel/significant enough for ICML. I am not sure - the covering and sensitivity analysis seem somewhat routine. If the accompanying lower bound was tight, then it wouldn't be fair to complain about this, but there is still a gap. On the other hand, I do not doubt correctness, and the paper was well-written and nice to read.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.\n\n- **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.*\n\n  **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.\n\n- **Comment 2:** *I think the novelty/significance [...]  conference like COLT.*\n\n  **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.\n\n- **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?*\n\n  **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.\n\n- **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.*\n\n  **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.\n\n- **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.*\n\n  **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.\n\n- **Comment 6:** *Can you resolve the complexity of this problem in 1D? Here, the connection to quantile functions should considerably simplify the problem.*\n\n  **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.\n\nWe would be happy to discuss any remaining questions during the author-reviewer discussion phase.\n\n[1] Transport-based counterfactual models, De Lara et al., JMLR 2024  \n[2] Fliptest: Fairness testing via optimal transport, Black et al., CFAT 2020  \n[3] Plugin estimation of smooth optimal transport maps, Manole et al., Annals of Stats., 2024  \n[4] Discrete Wasserstein barycenters: Optimal transport for discrete data, Anderes et al., Mathematical Methods of Operations Research 2016  \n[5] Privately Estimating Smooth Distributions on the Hypercube by Projections, Lalanne et al., ICML 2024", "claims_and_evidence": "Yes, this is primarily a theoretical paper, with results and proofs that appear sound.", "methods_and_evaluation_criteria": "They employ the standard evaluation metric for the map estimation task. The technical tools for designing the upper and lower bounds are standard in the literature (but have not yet been applied to this domain)", "theoretical_claims": "I skimmed through all of the appendix proofs, but did not check them line by line. However, these methods are super natural to apply here so I would be very surprised if there are any major issues.", "experimental_designs_or_analyses": "The experiments are naturally limited to 2d because of poor computational scaling with dimension. However, I think a statistical contribution is sufficient given that this problem has not been explored before. Plus, when smoothness is low, even the statistical rates without privacy scale poorly. (On the other hand, maybe that could enable \"efficient\" algorithms that scale polynomially in the sample size, since that is already exponential in dimension)", "relation_to_broader_scientific_literature": "They provide good background on the map estimation literature. There is a related problem of privately estimating a distribution/density under Wp. They mention some work in this direction but I note a couple missing references below.", "essential_references_not_discussed": "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.\n\nAlgorithmically Effective Differentially Private Synthetic Data\nYiyun He, Roman Vershynin, Yizhe Zhu\nCOLT 2023\n\nPrivate Measures, Random Walks, and Synthetic Data\nMarch Boedihardjo, Thomas Strohmer, and Roman Vershynin\nProbability theory and related fields, 2024", "other_strengths_and_weaknesses": "I think the novelty/significance of these contributions is a bit borderline. Since this problem has not been studied before, I am definitely open to acceptance. However, the techniques for the upper and lower bounds are all very standard in the literature, and I don't think this problem has not been studied due to its difficulty, but rather because it is a bit niche. To calibrate, I would probably accept this paper at a conference like AISTATS but reject for a conference like COLT.\n\nI think matching upper and lower bounds, or clear answers to my questions below, would convince me to accept.", "other_comments_or_suggestions": "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?\n\nIt 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.", "questions_for_authors": "Can you resolve the complexity of this problem in 1D? Here the connection to quantile functions should considerably simplify the problem.\n\nWhat about first doing private density estimation to obtain estimates $\\hat{P}$ and $\\hat{Q}$ which are accurate under $W_2$, then computing a smooth map for the $W_2(\\hat{P},\\hat{Q})$ problem (which is private by post-processing)? Analysis isn't obvious to me, but is there anything you can say here? To be fair, I don't think private density estimation has been well-studied under smoothness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PYexrhs01i", "reviewer": "Reviewer_KvNT", "summary": "This paper presents a differentiably private (DP) estimator for continuous $W_2$ transport maps, obtained from discrete samples from source and target distributions. It builds on top of the framework established by [Hutter & Rigollet 21] for estimating the Brenier potential ($\\nabla f$ returns the transport map), via wavelet approximation. Privacy is achieved with a noisy (Laplace) report argmin mechanism, applied to a covering of the admissible family of potentials. They are the first to provide upper and lower bounds for such a DP problem (in terms of $L^2$ error on the transport plan), but optimality of such bounds is not proven. The authors also present a simple practical implementation for a planar scenario that leverages a grid-based discretization.\n\n## Update after rebuttal\n\nI appreciate the clarifications from the authors, but remain at a weak accept, especially as some of my main concerns were shared by other reviewers.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.\n\n- **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.*\n\n  **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.\n\n- **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.*\n\n  **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.  \n  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.\n\n- **Comment 3:** *Also, for reproduction's sake, it would be quite nice to include an implementation of the practical algorithm for the research community.*\n\n  **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.\n\n- **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].*\n\n  **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.  \n\n  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.  \n\n  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).  \n\nWe would be happy to discuss any remaining questions during the author-reviewer discussion phase.", "claims_and_evidence": "The paper is primarily theoretical, so the need for empirical evidence is minimal. Detailed proofs are provided for the claims given, that mostly leverage prior analytical tools from [Hutter & Rigollet 21] and established mechanisms from the DP literature.", "methods_and_evaluation_criteria": "Yes, methods are fine. The experiment is small, but that is fine, as the focus is on the analysis and statistical bounds. \n\nI 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.", "theoretical_claims": "I did not have time to give a detailed check for the theoretical proofs in the appendices, but the arguments in the main text were correct.", "experimental_designs_or_analyses": "The experiment proposed is minimal, but sufficient.", "relation_to_broader_scientific_literature": "The paper is the first to provide some statistical guarantees on DP OT estimation in the continuous setting. The related work does a good job of establishing this and referencing relevant work (or at least, I did not notice any glaring omissions).", "essential_references_not_discussed": "None: see above.", "other_strengths_and_weaknesses": "A main strength of the paper is its clarity. I found the exposition to do a great job presenting and outlining their basic technique and results. \n\nIf 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. \n\nAlso, for reproduction's sake, it would be quite nice to include an implementation of the practical algorithm for the research community.", "other_comments_or_suggestions": "Explanation of rating: I found the paper to provide an interesting look at a heretofore unexpored 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].", "questions_for_authors": "See the one clarity weakness that I had a problem with above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xruo9HBxdY", "reviewer": "Reviewer_FYXP", "summary": "This paper leverages Differential Privacy (DP) to address concerns about privacy leakage when estimating the transport map between two distributions derived from user data. The authors propose a DP transport map estimator and establish its statistical guarantees in terms of an upper bound and a minimax lower bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe sincerely appreciate the time and effort you have taken to review our paper. Below, we provide detailed responses to each of your comments.\n\n- **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.*\n\n  **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.\n\n- **Comment 2:** *However, the method is not novel; it is a routine development that combines Differential Privacy (DP) with existing transport map estimators.*\n\n  **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.\n\n- **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 [...]*\n\n  **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.\n\n- **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.*\n\n  **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.\n\nWe would be happy to discuss any remaining questions during the author-reviewer discussion phase.", "claims_and_evidence": "The authors establish statistical guarantees for the proposed private transport map estimator. However, there is a lack of insight and clarification regarding these bounds, particularly in terms of how they compare to the non-DP version, and how changes in $\\epsilon$ affect the convergence rate and the estimation's optimality. The theoretical claim could be strengthened by deeper insights and more detailed explanations.", "methods_and_evaluation_criteria": "The problem addressed in this paper is important. However, the method is not novel; it is a routine development that combines Differential Privacy (DP) with existing transport map estimators.", "theoretical_claims": "There are no red flags in the theoretical part, but there is a possibility that I may have missed something.", "experimental_designs_or_analyses": "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.\n\nThe figures appear to show results from only a single run of the algorithm, but a single run provides little insight into the algorithm's general performance and variance. What is its average approximation error across multiple simulations? The fact that this is neither displayed nor mentioned is quite concerning.\n\nTo address privacy concerns, it could be interesting to evaluate the performance of the estimator in cases where the underlying distribution is heavily skewed.", "relation_to_broader_scientific_literature": "The main results of this paper could contribute to applications and methodologies involving optimal transport maps using real user data.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "My main concern is with the numerical experiments. Please see the comments under 'Experimental Design and Analysis'.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles the theoretically important and previously underexplored problem of estimating smooth optimal transport maps under differential privacy constraints. The authors propose a private estimator using a covering argument and establish upper and lower bounds on its statistical performance. The work is clearly written, with clean formalism and a sound analytical framework. Reviewers appreciated the clarity of the presentation, the relevance of the problem, and the fact that this is the first paper to provide nontrivial statistical guarantees in this setting. That said, several reviewers raised concerns about the limited practical applicability of the proposed estimator. The algorithm, while theoretically motivated, is computationally expensive and not easily implementable based on the current description. Additionally, the theoretical contributions, while solid, rely on fairly standard tools from the literature, and do not fully resolve important questions such as tightness of the bounds or efficient estimation. The experimental section is minimal, providing only toy illustrations, and does not convincingly demonstrate the utility of the approach in realistic settings. Still, considering the novelty of the problem, the soundness of the analysis, and the fact that all reviewers leaned toward acceptance despite their reservations, I believe this work makes a valuable theoretical contribution. I recommend acceptance.
Decision: Accept (poster)