Parameter tuning and model selection in Optimal Transport with semi-dual Brenier formulation
Authors: Adrien Vacher
François-Xavier Vialard
Venue: NeurIPS 2022 Accept (2022)
Keywords: Optimal Transport
model selection

Abstract: Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in a stochastic setting, where distributions are represented by samples and where the goal is to find the closest map to the ground truth OT map, unknown in practical settings. So far, no quantitative criterion has yet been put forward to tune the parameter of these models and select maps that best approximate the ground truth. To perform this task, we propose to leverage the Brenier formulation of OT. Theoretically, we show that this formulation guarantees that, up to sharp a distortion parameter depending on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimization, enables parameter tuning and model selection among entropic regularization of OT, input convex neural networks and smooth and strongly convex nearest-Brenier (SSNB) models.
We also use this criterion to question the use of OT in Domain-Adaptation (DA). In a standard DA experiment, it enables us to identify the potential that is closest to the true OT map between the source and the target. Yet, we observe that this selected potential is far from being the one that performs best for the downstream transfer classification task.

Parameter tuning and model selection in Optimal Transport with semi-dual Brenier formulation
Adrien Vacher LIGM, Univ. Gustave Eiffel, CNRS
François-Xavier Vialard
LIGM, Univ. Gustave Eiffel, CNRS
MOKAPLAN, INRIA
francois-xavier. vialard@uni--eiffll...... fra.oossswaaeeeevaaaaaaaaaarrrre
adrien. wer.iee.vaacerrmmii-eiiie
Abstract
Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in stochastic setting, where distributions are repre- sented by samples and where the goal is to find the closest map to the ground truth OT map, unknown in practical settings. So far, no quantitative criterion has yet been put forward to tune the parameters of these models and select maps that best approximate the ground truth. To perform this task, we propose leverage the Brenier formulation of OT. Theoretically, we show that this formulation guaran- tees that, up to sharp a distortion parameter depending on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimiza- tion, enables parameter tuning and model selection among entropic regularization OT, input convex neural networks and smooth and strongly convex nearest- Brenier (SSNB) models. We also use this criterion to question the use of OT in Domain- Iomaain-Adapaation (DA). the potential that is closest to the true OT map between the source and the target. Yet, we observe that this selected potential is far from being the one that performs best for the downstream transfer classification task.
standard DA experiment, enables us to identify
Introduction
Optimal transport (OT) is tool to compare probability distributions that has found numerous ap- plications ranging from economics Galcchon 2016. Chappon et al. 2010, unsupervised learning
NLP Chen all 20g Alyarez Melis and long et al. M020 In its dual form, OT is cost constraint. When the cost is chosen to be quadratic, the solutions of this problem are convex and their gradient provide optimal maps that transport one distribution onto the other. In a significant part of the OT applications, the transport map itself is the object of interest. For instance in Domminn-Adatation the source distribution is transported on the target [[ourty an, 2017, for color transfer one color histogram is transported profile is interpolated in time using OT maps [Schtebinger all 2010 Over the past few years,
ef [0Z]] shape matching reydy
201
laakkol
M01E and biology [Schrebinger et all 2010
linear maximization problem functions, which called potentials, subject
the other [Rabm et all
201 and in biology, the RNA cell expression
many models and computational methods [[ Cuturr 2013 Genevay et al. 2UG Seguy et al. 2018
implemented to estimate these optimal transport maps. Under regularity assumptions, some of these models were shown to accurately estimate the original transport map provided the models use optimal parameters Pooka Tran and Niles- Weed 1Ial,, Manole-iaal [иza] When such results exist, either the parameters to use are explicit but they are impractical as they rely on generic worst-case bounds, either they involve unavailable constants. To the best of our knowledge, quantitative criterion has yet been devised to tune the parameters of OT models and later discriminate between calibrated models. The setting
Bonneel and Coeurjolly, 201 Vacher-etal
2071| were proposed
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

we are interested in is standard in statistical and ML applications, in which probability measures are only accessible via samples in Euclidean spaces. The goal is to recover, for the quadratic cost, a potential chosen among different models/parameters that is the closest to the unknown ground truth. For achieving this task, we put forward the use of the semi-dual functional of OT that we now define.
The semi-dual (Brenier) objective. The quantitative criterion that we propose is the so-called semi- dual Brenier objective of OT. It is convex functional on the space of functions f : IR + R and is defined for μ,, / two probability measures on the Euclidean space by, denoting (-.-) the pairing between Radon measures and continuous functions, Jpp = (f
1/ with f the Fenchel- Legendre transform of f given by f") == su I y- f()) Note that for general cost c, this new objective can be obtained by replacing one potential by its c- c-transform in the Kantorovitch dual formulation. Now, whenever f is convex, its legendre transform can be computed pointwise with an arbitrary precision. Furthermore, if v is finite sum of Dirac masses, the resulting convex problems of J(f) are independent and can be solved in parallel.
Related works. The problem of evaluating OT models was recently studied by Korofin et all [202T]. They proposed to generate synthetic ground truth optimal maps using an input convex neural network. Then, they calibrate various OT models on these ground truth OT maps and compare the performance of each calibrated OT model by measuring the natural 1,a distance between the estimated map and the ground truth. Their paper gives an interesting perspective on comparing current OT models. However, their setup requires the knowledge of the ground truth calibrate the OT models. This limitation can be overcome for convex potentials as shown in our work.
The use of the Fenchel-Legendre transform can be found in the pioneering paper Brentei [1999]] It can be shown that this new formulation retains more convexity than the Kantorovitch formulation. On the theoretical side, this gain was leveraged for uses diverse as sharp bounds for the problem of statistical map estimation [Futter and Rigöllet, [[2 or quantitative stability results of the trans- port map with respect the measures [Delalande and Merigol 20211. On the numerical side, since the Senchel-Legendrr transform has linear cost on a grid (Fast Legendre Transform), the semi-dual used design efficient numerical algorithms in low dimension [aacobs and Lèger, 2020]. In the machine learning community, the semi-dual was proposed by Laghvaet and Jalaii [MOTC] to estimate convex transport maps parametrized by Input Convex Neural Networks [Amos et all M0 When is the sample size, they noticed that instead of the classical O(n²) complexity of OT, this new for- mulation leads an (n) complexity per iteration as it only requires n-independent computations of the Legendre transform.
The goal of our paper is to answer the following question: given (Ji,..., Sp). p convex potentials, how to select the one that minimizes the quadratic error, denoting V the gradient of Si, eg = Ss VI f((x)) To(=))]2dpp(a)
Our contributions.
where To is the true, unknown, OT map from to v?? A concrete example of this problem would be: we train a Sinkhorn model [Cntur] [ on samples (Perain: Dtrain) with different temperatures (#1,-.. Sp)) giving us empirical potentials (fe.,..., Je,)) Given test samples (frest: Plest) how to choose the Sinkhorn empirical potential that minimizes the unknown error (ex. We give an illustration of this problem in Fig. MI
The main contribution of the paper is to use the empiri- cal semi-dual to answer this question; to the best of our knowledge, it is the first time that the model selection problem in OT has been addressed. From theoretical point of view, in the strongly-convex and smooth setting, prove that the potential f. minimizing the empirical semi-dual is the one minimizing en up to a sharp mul- tiplicative factor that depends the smoothness of the potential and up to an additive statistical deviation term. From experimental point of view, we showcase three synthetic experiments, with an ICNN model [Tagh- Kaer and lalar, MHT Sinkhorn model [nnn MIKK and a SSNB model |Paty et all 20Z(), that the potential achieving the lowest quadratic error is nearly always se-
Greand truth
085
OZ (nolectdd)
01
5.-
02
0.9
3.5
Figure 1: Parameter tuning for stochas- tic entropic OT: how to pic E; that best fits the unknown blue curve?
lected by the semi-dual. This consistent behavior enables
us conclude on concrete ML application of our work: in Domain Adaptation, a widely accepted approach is to seek for an OT map between a source and a target using various models/parameters

---

in order to transfer the source's labels on the unknown target's labels. The question whether the OT model is truly relevant for this task has remained unanswered because of the impossibility to discriminate between candidates close to the "true" OT map and those "far" from it. In our last ex- periment, we bring a partial negative answer to this question: we observe that the map minimizing the semi-dual, hence the closest to the ground truth OT map, is often far from being the one that achieves the best label transfer.
Assumptions and notations. In this paper X, Y are compact subsets of IR 1 and v are probability measures over X and Y respectively with their n-samples empirical counterparts é. V. We shall denote by supp(n)). (upp(t))) the support of and y respectively. The cost we consider is the quadratic cost c(z, y) = || y/ 2 /2 and shall denote q the quadratic function g(x) ||==12/22 Finally, we shall call M-smooth any function with an M M-Lipschitz gradient.
2 Brenier formulation of OT
In its dual formulation, the OT problem optimizes over a pair of continuous functions, called Kan- torovitch potentials (c) t)) subject to a cost constraint as (T)
suP p) (1b, ( ve S c) where o @ &e is defined as (ø o (z) y) = o(x) + bly) and z is the convex indicator function. When is the Euclidean squared distance, we simply denote it by OT. In this case. if one of the two measures has density w.r.t. the Lebesgue measure, Brenier's theorem [Brentee [991 shows that unique optimal map sending jr to exists and is given by the gradient of convex function. If one further assumes regularity of the underlying densities and convexity of the support of the distributions, the optimal map gains in regularity.
Theorem Catarelli [PA]]]] Theorem 2b.). Assume that μ and v have C densities bounded from
below and above. If p. have compact and convex support, then, defining the Brenier potentials (f,9) = (g- - Φ. 9 - v) I and are C convex functions such that V f (p))= = v and V =
;1 where (T)) is the pushforward of the distribution n) by the map T defined Tx
((T=((A) for all Borel A.
(A))
Hence under the assumptions of Theorem W. the optimal Brenier potentials are both smooth. In particular, since they are mutual Legendre transform of one and other, they are both also strongly convex.
The semi-dual Brenier objective for convex potential selection. In the context of statistical OT, the transport Kantorovitch potentials o, & are usually estimated using the dual formulation of OT. To compare the obtained potentials, one may be tempted simply evaluate the Kantorovitch linear objective on test set Kj (p, v = (6. p)) + (v, D) +1(@@V S c) where ja, represent independent samplings of μ, v. However numerous OT models, the learned potentials (δ, v)) usually do not respect the cost constraint and the u( ( < c) term diverges. For instance, in the entropic regulariza- tion of OT the constraint is "loosely" satisfied on the train since it replaces the hard inequality con- straint by the soft penalization e dew-r r p & D). It is possible though to remove the cost constraint from the objective in order evaluate candidate potentials. Rewriting the Kantorovich dual with the Brenier potentials gives OT(H, v) = (q, 1 + v) - (nf() (f. + (q + (f(x)) + g0)) 2 x yy) where the optimization is done on f.g E C the space of continuous functions. The inequality costraint implies that g(y) 2 sup, x y f(x) for every æ which shows that we can replace g by f², the Fenchel-Legendre transform of f. Therefore, up to moment terms, we get the semi-dual Brenier formulation inf, (f)
(f. + +f*, vv. This new nonlinear objective gains in con- vexity with respect to the Kantorovitch formulation (see Sec. B and now, whenever f is strongly convex, (f) finite and can be efficiently computed on discrete measures using standard con- vex optimization algorithms. Hence, if we restrict ourselves to convex f, possibly regularized with the addition of a small quadratic term, we are provided with a tractable and well-behaved selection criterion: the potential that minimizes Jp.c. We show in the next section that, thanks to the extra con- vexity, the minimization of this objective coincides, up to a stochastic term, with the minimization of the quadratic error (f) Jx [|V [6 dd..
3

---

3 Potentials selection
We give in this section our main theoretical guarantee on model selection via the semi-dual. The setting we need to consider is the case of M-smooth and y-strongly convex potentials, assumption which is discussed below. Let us first recall a stability result which shows that the semi-dual formula- tion is upper-bounded and lower-bounded by the quadratic enror Ex.. When no confusion is possible, we shall from now on denote Ju, by
Lemma 1. Assuming that an optimal convex potential fo such that To fo pushes μ onto
exists, then if f is M-smooth, denoting Jo = J(fo), we have ZM e S (J(f) - Jo) where ( /IV5 Toll Toll Conversely, if is a continuous y-strongly convex functiin then J(s)-
Jo - 1 24 e
This result is derived from Muzellec cf al [202]] Proposition 1J. see Appendix for more details. A similar result can be found in Hütter and Rigollet [MIZT, Proposition 10] in a slightly less general form and in Makkuva el al [2020, Theorem 3.6]. Importantly, note that there is no smoothness assumption made on the optimal map To. In contrast, we prove that the smoothness and strong- convexity assumptions on the candidate f are necessary to lower and upper bound J(f) Ju with respect en.
Proposition 1. Take ~ 2(1-2, 2) and So of the form >g(æ)) + x with 2 O. The potential
f()) = x is indeed convex with Lipschitz gradient and is such that J(f) +00 yet e,, 4/4 +
Conversely, define the potential go(x) = |x| + +q(z) and for 0 S x 3. define gX = go A) which is indeed strongly convex (and even locally Lipschitz). The difference of semi-duals reads 4).
[(g)) (go) = 2X²
2X² and yet (x(9)) 4X + 5X2 A-
x-0
The detailed computations are left in Appendix. Equipped with this lemma, we can derive our result.
Proposition 2. Let (f1,... fv) be p potentials and (p. 8) be the n-samples empirical counter- parts of (J, Let in be the index of the map that minimizes the empirical semi-dual, in arg min; (fi) and similarly i = arg min; (ft). If fio is M-smooth and fú, is 7-strongly convex and if an OT map from μ to v exists, then for all 0 < ô 1-8 8
< 1 we have with probability at least
ea(fi)) I M
y (x(ftt) 8MC + In(4//)
(1)
2n
where C = max(Cin: Cú,) with C. max(Il 11 ll) and Il-1lz,o is defined as |1 supzez g(v)= - inl g(y).
=
The proof is left in Appendix and is direct application of the previous stability estimate and the Hoeffding lemma. The following proposition shows that in the non-stochastic regime n = +o0, our bound M. is tight.
Proposition 3. Take P ~ u(0 1]. fo = O, g(x) = Mq(x) + and for > 0, take he hx(x) =
(g(z) + (e + aM with aM,. =
4(M->) -1 and where we assumed M 2 7/ The -1
3n
potential g indeed M-smooth and h is indeed 7-strongly convex and we have (nig) M yet (he))
c- 7
J(h,) 2 (e+ 20m,)) <
The computations are left in Appendix. The bounds of Proposition being tight in the non-stochastic setting, it is natural to question the assumptions the class of potentials, namely M-smoothnesss and y-strong convexity. Let us first mention Theorem readily ensures that in the case where μ. have C densities with convex compact support then the optimal potentials satisfy the smooth- ness assumptions. Under such conditions on the measures, one should indeed benchmark poten- tials which are already smooth and strongly convex. However in practice, we may not have ac- cess to potentials satisfying these conditions. A simple idea to satisfy the smoothness assump- tion is to the Moreau- Coreau-Yosida transform Mf(f) inf, fly) + qq(z - y), which verifies L²r < (f) < f where L is the Lipschitz constant of f on v. The semi-dual shall read (f) Jo. however without further assumptions, cannot upper-bound
2
27 e

---

the original error (f) as le (Mx en( may not be in o(1). The case of strong-con convexxtyy has more favorable behavior. Denoting (f( f óq, we can apply Lemma and obtain I()x(1)) Jo I 28 (Qs())) The error can be upper bounded by ex( + 45 (q, n)- Under a local Lipschitz assumption on ʃ" f" J(Q(()) - Jn is ( hence we observe there is trade-off between the deterioration of the factor in O 3 and the bias in ( As consequence, we can de- rive a new stability result, proved in Appendix, when the optimal 6 is chosen. The strong-convexity assumption is relaxed with a local Lipschitz assumption of the conjugate at the cost of loosing on exponent on the error.
Proposition 4. If ist.s.t. f is L-Lipschitz on the support of then the semi- reads J(f) - Jo S 2/(0(f + (g,
Note that at optimality, fü is indeed Lipschitz on the support of v. yet this condition may be diffi- cult to enforce in practice. We believe though that sharper/less restrictive stability results could be obtained via a refined analysis and we postpone this interesting question for future works.
4 Sinkhorn potentials
The Sinkhorn model
nntrrr
VOKK
defined as Se(p, = supo.eeco (0.10) + (1)
,/ 2 2) is very popular in the OT community. We show in this section that the discrete potentials provided by the empirical Sinkhorn model can indeed be extended to continuous, convex and smooth potentials. However, their extension is not strongly convex and prove that the semi- dual diverges almost surely when evaluted on empirical Sinkhorn potentials; hence we propose to quadratically regularize the Sinkhorn potentials. From a numerical point of view, we show how to compute efficiently the semi-dual on this regularized model with a fast converging scheme.
e(e o0e-c "
A convex smooth model. Recall that the first-order optimality condition on the Sinkhorn potential [0
6e gives @ (I) = -E log(S, e
-(())-a(a.)) dv(u)). As done for instance in Berman
Booladan
and Niles- Weed [2024]], we use this conidtion to extend the empirical Sinkhorn potentials (de, ve) =
arg (o)) (e 8) on the whole domain Rd. Defining the associated Brenier potentials as Se =
q- de. we obtain fz(x=) e log(,,,
du(y)), where we defined &e (v) ((1/))(v
This shows that the potentials (fe. 9c) are Log-Suu--Exp (LSE) functions and in particular, they convex.
Proposition 5. fe is (mup(()) smooth where ((supp(i)) is the diameter of the support of D.
The proof is left in Appendix. While LSE functions are indeed smooth, they are not strongly convex. The following proposition shows that the semi-dual diverges almost surely on fc-
Proposition 6. Let (fe, (c) = (q - de Se). If v has continuous density with respect to the Lebesgue measure we have almost surely (iz v) +00
The proof is left in Appendix. This Proposition implies that evaluating the semi-dual on the empirical Sinkhorn potentials iol-posed and it justifies their strong-convexite regularization. To this end, we consider (f=) = f- óōq with >> small and shall now read (fe) - Jo S e (fa)+ (8)). We show in the experiments of Sec. E that despite this small bias, the selection of empirical Sinkhorn potentials via the semi-dual criterion still provides satisfactory results.
Self-concordant potentials. Now, even if the Legendre transform can be computed via a stan- dard convex first order minimization algorithm, will not be effective in practice as the prob- lem is conditioned by O One way to circumvent poor conditioning is to employ second order methods. In the standard cases, they require costly line-searches however if the function has a generalized self-concordant structure, we can use a second order algorithm of the form where ag is an explicit step size given in Sun Sun and Trans Theorem 2] and that provably yields super-linearly convergent algorithm.
an.( (v² f
Tk+1 Dinh
2019
Definition 1. Let O and s be O convex function. The function f is said to be (a, My) self-concordant if for all (2, u, v), f())((u)) Tul My||u[||||||] -|||||2 where ||ul|2
5

---

- Disigked anr tensorT (tyk)) T(o] Jerajer Ei v,T. with T; the matrix (sis))
(V2f(z)u) u, f(x) is the tensor ( 8'1
Informally, the self-concordance measures how fast the Hessian varies with respect the metric induces.
Proposition 7. The Sinkhorn Brenier potential fe is (2, D( self-concordant where the diameter D is defined D( supyee,zed lly 10--2p) z112.
The proof is left in Appendix. Fig. D shows that the second order scheme is much faster to compute the Fenchel conjugate on 1000 points, with learning rate ( for the first-order method.
Numerical experiments
We first introduce two other transport models on which we perform our numerical experiments.
Thee secoot 2he sraee
5.1 Other models
Input Convex Neural Network (ICNN). The con- vex Brenier potentials are modeled by (Jo, (o,) two ICNN. Then the model is trained using minimax ob-
355
jective ming, maxØ, (f)
- Vge, (3:)
(fe., (Vge,) (f)) The maximization aims at recovering 90, 2 fø and the minimization approximately solves the semi-dual. The implementation is based on the code of the a Softplus activation layers were used instead of ReLu to obtain less degencrated maps. Note that since the weights 01, 0g are not controlled, we expect this model to provide lowly regular maps.
Figure Fenchel Conjugate: 1st order vs 2nd order.
Smooth Strongly convex Nearest Brenier (SSNB). This model estimates the potential f by ap- proximately solving inf seF (2((V) f) (f)), ()), D), where F(.z) is the set of L-smooth, I-strongly convex functions. As opposed to the previous model, SSNB provides maps that are very regular (in bi-Lipschitz sense).
5.2 The experiments
Synthetic XP. We compare the ability of the models to recover the ground truth transport map using medium dimension setting df In all three cases, the distribution y is uniform on the cube [o, 1]d and v is given by f) (14 where f virtue of Brenier's theorem, T f the ground truth OT map between and v. The function f has 3 different forms.
the semi-dual criterion map for three different distributions
convex function
(i) Quadratic: (x: f Qx: xr where Q T DO + 0.25 Id where O is randomly chosen orthogonal matrix, is a random diagonal matrix whose entries are uniform in [0, 1] and b is a random d-dimensional gaussian. This is standard benchmark which simply aims at recovering translation. (ii) Tensorized: To(x) = x + (6 cos(6Tæz) 0.2) -1 and T(x) = >i To(x).. The map to learn is more complex but has a low dimensional structure as it pushes independently each directions. (iii) (Regularized) Log-Sum-Exxp f(xx) = ILSE & b) + 8q(xr) where the matrix C' is comprised of 10 centers uniformly chosen in [-1, 1]d, the shift b a random d-dimensional gaussian, the temperature function can be approximated by such a Log-Sum-Ext [Calatore 2020]. However, because of this parametric structure, we expect the Sinkhorn model to be favored.
fixed 0.3 and the regularizer 5 0.001. Note that any convex
The training of the models, the semi-dual estimation and the Monte-Carlo approximation of the done with 3 independent batches of size
error error" (f.) f f(()) To (x)()( n = 1024. For the computation the semi-dual, we regularized with +öq the ICNN and Sinkhorn models taking 5 1E 3. Note that the errors are computed on the original potentials, without the
hhtps://githuu.c http://ggthuh.coom/a// com com/AmiiTP/O/O0TCCNN
"Concentrates in O { toward the "true" error.

---

ICNN
Sinkhorn
SSNB
en (f(
eu (f(rrr))
eu(fo.,)
e en(
eu
ex (f
Quad
5.11
12.23 (16.13/48)
0.036
0.047 (1.93/5)
0.013
0.014 (1.33/11)
Tens
2.74
2.74 (1.22/48)
0,059
0.119 (2.72/5)
0,006
0.006 (1.0/11)
LSE 1.69
3.02 (17.11/48)
0.006
0.006 (1.68/5)
0.16
0.17 (1.26/11)
Table 1: Parameter tuning for OT models. Each model is trained with different parameters (0.) and a parameter 0% is selected with the semi-dual criterion 8g,- arg min; J J(fo.). We report the error (x, ) against ey (y,(),,,
min; (o.(o ); ideally e,, = en.So, ). The numerator between brackets corresponds to the rank of the tuned potential with respect to the error en: the closer to one, the better. The denominator corresponds to the number of parameters. In bold the model with the best performance after being tuned with the semi-dual criterion.
regularization term. Forty-eight combinations of parameters were tested for the ICNN model, five for the Sinkhorn model and eleven for the SSNB model. More details on the parameters and on the implementation are given in Appendix.
The results were averaged on fifteen independent runs and are reported on Table M. The parameters of each model are tuned with the semi-dual criterion. We denote 0ig the parameter that minimizes semi-dual and 0z, the parameter that minimizes the error ep- The numerator between brackets corresponds to the rank of the selected parameter with respect to the error egi the closer to one the better. In particular, if 0., = 6,, we obtain the rank 1. The denominator is number of parameters: for instance, we tested the Sinkhorn model with five different E, hence the denominator is 5.
In the case of SSNB where the smoothness and strong convexity parameters are explicitly controlled, the best parameter is almost always chosen. In the case of the Sinkhorn model, the regularity decreases for small val- ues of & yet the selected potential remains in the top 40% for the Quadratic and Log-Sum-Exp experiments. Con- versely, the regularity is not controlled in the ICNN model yet the selected parameters remains in the top-tier for the Quadratic and Log-Sum-Eas Expp experiments; as for the Ten- sorised experiment, the best potential is almost always se- lected.
ICNN/Sinkhom/SSNN
(f,)).))
(f.)
Quad 0.013
0.014 (1.33/64)
Tens
0.006
0.006 (1.0/64)
LSE
0.006
0.006 (1.68/64)
Table 2: Model selection for OT: once the three models tuned with the semi-dual, we select one among the three again with the semi-dual criterion. Note that the denominator is now equal to the sum of the number of parameters that we tested for each model.
Once the three models are calibrated with the semi-dual we select one among them with the same criterion (see Table D); note the denominator between brackets is now equal to the sum of the number of parameters considered for each model. We observe that the criterion selects the best or nearly-best transport map. This shows that the Brenier criterion can be both used for calibra- tion and selection. Fig. 3 plots the semi-dual values against the error in the Log-Sum-Esy experi- ment and empirically suggests an even better behavior than best model selection. For the Sinkhorn and SSNB models, the error strictly increases with the semi-dual value, hence the semi-dual can not only select but can also directly rank the potentials with respect to the error Cμ. For the ICNN model, we do not observe the same monotone behavior but we still get a positive correlation between the error and the semi-dual value. This less consistent behavior can be explained once again by the lack of control on the regularity of the potentials given by the model.
Overall, when we compare the models after being calibrated with the semi-dual we observe that ICNN always has the poor- est performance.
ICWNOY
SIC-OIN
SINB
344
52-
We may not have chosen the hyperpameters and the network structures in the best possible way and the ground truth may not favour this model. The SSNB model performs better by almost an order of magnitude than
35
232
0.5
0.80
0.0
EA2 235
5.5
Figure 3: Empirical Semi-Dual against Quadratic Error on the LSE experiment. Ideally, the error should strictly in- crease with the semi-
7

---

Sinkhorn on the Quadratic and Tensorized experiments. Conversely, as expected, the Sinkhorn model the best one on the Log-Sum-Exp experiment. In terms of computation time, the training of the SSNB model takes between one and three hours and between 30 minutes and one hour for the semi-dual computation on a 120 GB RAM CPU. ICNN and Sinkhorn take a few minutes and a few seconds respectively for the training and semi-dual computation on RTX6000 GPU.
Thanks the high scalabilty of Sinkhorn, we repeated those three experiments on larger batches with n = 10000 averaged on 10 runs. As shown on Table B. Sinkhorn recovers the same behavior as SSNB with respect to the semi-dual. Not only the best parameter is always chosen but also, we show in Appendix that in the Quadratic and LSE settings, the error increases with the semi-dual,
Quad
Tens
LSE
ep (Jes)
0.0104
0.0376
0.0005
en (Jeo) Rank
0.0104
0.0376
0.0005
1.0/5
1.0/5
1.0/5
Before ending this paragraph, we briefly discuss the ef- feet of the quadratic regularization for the ICNN and Sinkhorn models. We observed experimentally that with- out it, the Legendre transform indeed diverged over sev- eral points. On the other hand, the experiments did show that the semi-dual accurately selects the best po- tential even in the presence of the regularizer. We pro- pose the following informal explanation: we show in Appendix that [()s(J) - Jo J (T(()) - Qs(f)" + 8z) +x (T(x) + -zz +xT(((x)) To du((z). We can decompose the integration on areas where the origi- nal potential f* is 0(1) Lipschitz, where we can expect
Table 3: Parameter tuning for Sinkhorn model with n = 10000 points. The numerator of the Rank corresponds to the rank of the potential calibrated with the semi-dual criterion with respect to the error Cu: the closer to one, the bet- ter. The denominator corresponds to the number of parameters. We observe that the semi-dual accurately tunes the Sinkhorn model as the best parameter is always selected.
(T())) - (T()))((()) + 8π)1 = =(6) and on the remaining area, the integrand behaves like (1)). For instance in the case of the empirical Sinkhorn model whose conjugate is Lipschitz on the
interior of the convex hull of iz we conjecture that J(Qo(fe) - Jo S Csty e (fa) + O + ō where a > 0
Domain Adaptation. (DA) The goal of DA is to infer unknown labels of a target distribution X, using a shifted source distribution X, with known labels Y,. In the work of Courty al. [2011]] and many others [Redko all 2015. Xf all [021] a map T is sought between X, and X,. Then classifier e is learned on (T(X,), Y.) and is used to predict the unknown labels of the target as e(X.). Their core assumption is that T should be close to the OT map between X., Xx. Question: this assumption valid? Is the "true" OT map between X, and X₃ the one that will achieve the best knowledge transfer? Problem: among all proposed models, how to assess which map is the closest to the "true" unknown OT map? Using our criterion, we can now select the parameters and the model that will be closest to this ground truth.
We use the Caltech-office dataset which is set of images of objects from ten distinct categories coming from four different sources of various quality: objects found in the online Amazon catalog (A), objects whose pictures have been taken with a webcam (W), with a high resolution digital SLR camera (D) and the Caltech-256 dataset (C) which is comprised of Google images. We use all the nine distinct pairs as source/domain data. As in Courty et all [201]] in order for the quadratic distance to be meaningful, we do not use the raw images but feed them to a Decaf [Donahue al 20e] network and extract the features of the last layer and we use a 1-Nearest Neighbors as the classifier. The models and parameters we use are the same as in the Synthetic experiment. In our setting, the transport map T is learned on train sets Xtrein X and the semi-dual is evaluated on test sets Xtest, Xtest, with 70% of the data for the train and 30% for the test.
The results are reported on Table where only (A) and (W) are used as sources, the rest of the results are reported in Appendix and exhibit a similar pattern. We denote by in the index of the potential minimizing the empirical semi-dual criterion and by i the potential achieving the highest accuracy. The numerator between bracket corresponds to the rank of the selected potential with respect to the accuracy obtained when the classifier is learned on (X.) Y.): the closer to 1, the better and
'It is shown in Bruncl pMe Equation (2.3)) that if ş has a convex support, the volume of support (ū) is upper-bounded by O(n -9) Depending on the shape of the support, it varies between -1 log(n) dd and n -2((d+1)
8

---

ICNN
Sinkhorn
SSNB
acc(fi) (f,,)
aco(fr.)
acc(fi.)
acc(fio)
acc(fi,)
aco(fie)
A/C
0.41
0.34 (2/48)
0,84
0.82 (3/5)
0,85
0.79 (10/11)
A/D
0.44
0.15 (33/48)
0.87
0.78 (4/5)
0.82
0.8 (5/11)
A/W
0.36
0.07 (48/48)
0.78
0.72 (3/5)
0.79
0.71 (9/11)
C/A
0.47
0.09 (44/48)
0.91
0.82 (5/5)
0,91
0.88 (9/11)
C/D
0.65
0.27 (6/48)
0.9
0.8 (4/5)
0.88
0.82 (10/11)
C/W
0.36
0.34 (3/48)
0.82
0.79 (2/5)
0.83
0.83 (1/11)
Table 4: Potential Selection for Domain Admaainn-daaattionn. The column acc(ff,) corresponds to the best (highest) accuracy and af,(fa,) coressonds the accuracy of the potential selected with the Brenier criterion. On this Table, the potentials are ranked with respect to the accuracy; the closer to onc, the better the classification. In bold, the highest accuracy after being calibrated with the semi-dual.
in particular, rank(fi,) 1. We observe that the potential having the lowest accuracy is regularly selected by the semi-dual, even in the case of the SSNB model for which the semi-dual indicates very reliably the quality of the transport map. Hence we conclude that for DA, the best mapping for label transfer is not close to an optimal transport map. We remark that this conclusion is similar to the results of Korofin etal [202A]] and Stanezuk etal [2022]]] who observed that the transport models which performed best for various ML tasks were not the ones that recover the sharpest OT maps.
6 Conclusion
The semi-dual Brenier formulation of quadratic OT provides us with feasible criterion for convex potential selection. If the potentials are convex, this criterion can be computed numerically. Theoretically and experimentally, we showed that up to sharp distortion parameter, the potential that minimizes the semi-dual is the one whose gradient minimizes the squared error to the ground truth map. Hence this criterion gives a fair and accurate procedure to benchmark convex OT models and provides a first step towards parameter tuning for stochastic OT. Regarding ML applications, this criterion allowed us to bring a first partial negative answer to the question relevance of OT in DA: indeed, one may achieve good results in DA using models borrowed from OT literature, yet claim that their performance is not correlated with how well they approximate the ground truth OT map between the source and the target. Possible extensions of our work could include more general cost e and more general potentials. We believe M -ssmoothssss and y-strong convexity assumptions could be alleviated by careful analysis of the quadratic and Moreau- Moreau-Yosida regularizations. If not possible, the question smoothness parameters selection in stochastic OT is widely open.
References
David Alvarez-Melis and Tommi Jaakkola. Cromov-wasserstenn alignment of word embedding spaces. Conference on Empirical Methods in Natural Language Processing, 2018
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. ICML, 2017.
Robert Berman. The Sinkhorn algorithm, parabolic optimal transport and geometric monge- amp'/ere (re equations. Num. Math., 2018.
Nicolas Bonneel and David Coeurjolly. Spot: Sliced partial optimal transport. SIGGRAPH, 2019.
Yann Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math., 1991.
Victor-Emmanuel Brunel. Non-parametric estimation of convex bodies and convex polytopes. Theses, Université Pierre et Marie Curie Paris VI University of Haifa, July 2014. URL
https://tell www.ives-ooveeteeeeeeee wwweeerttsffrtteeeeeee ff/tel-01066977
Luis Caffarelli. Monotonicity properties of optimal transportation. Communications Mathe- matical Physics, 2000.

---

Giuseppe Carlo Calafiore, Stéphane Gaubert, and Corrado Possieri. Log-sum-ext neural networks and posynomial models for convex and log-log-convex data. IEEE Transactions on Neural Ner- works and Learning Systems, 2020.
Liqun Chen, Yizhe Zhang, Ruiyi Zhang, Chenyang Tao. Zhe Gan, Haichao Zhang, Bai Li, Ding- han Shen, Changyou Chen, and Lawrence Carin. Improving sequence-to-sequence learning via optimal transport. In ICLR, 2019.
Pierre-André Chiappori, Robert J. McCann, and Lars P. Nesheim. Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness. Economic Theory, 2010.
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. Optimal transport for do- main adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation optimal transport. In NeurIPS, 2013.
Alex Delalande and Quentin Merigot. Quantitative stability of optimal transport maps under varia- tions of the target measure. arXiv, 2021.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf:: A deep convolutional activation feature for generic visual recognition. In ICML, 2014.
Jean Feydy, Benjamin Charlier, Trançois-Xavies Vialard, and Gabriel Peyré. Optimal transport for diffeomorphic registration. In International Conference on Medical Image Computing and Computer-Asiisted Intervention, 2017.
Alfred Galichon. Optimal transport methods in economics. Princeton University Press, 2016.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic Optimization for Large- scale Optimal Transport. In NeurlPS, 2016.
Jan-Christian Hütter and Philippe Rigollet. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 2021.
M. Jacobs and F. Léger. A fast approach to optimal transport: the back-and-forth method. Nu- merische Mathematik, 2020.
Alexander Korotin, Lingxiao Li, Aude Genevay, Justin Solomon, Alexander Filippov, and Evgeny Burnaev. Do neural optimal transport solvers work? a continuous wasserstein-2 benchmark. arXiv, 2021.
Ashok Makkuva, Amirhossein Taghvaei, Sewoong Oh, and Jason Lee. Optimal transport mapping via imput convex neural networks. In ICML, 2020.
Tudor Manole, Sivaraman Balakrishnan, Jonathan Niles- Weed, and Larry Wasserman. Plugin esti- mation of smooth optimal transport maps, 2021.
Boris Muzellec, Adrien Vacher, Francis Bach, François-Xavies Vialard, and Alessandro Rudi. Near- optimal estimation of smooth transport maps with kernel sums-of-squares, 2021.
François-Pierre Paty, Alexandre d' d'Aspremont, and Marco Cuturi. Regularity regularization: Smooth and strongly convex brenier potentials in optimal transport. In AISTATS, 2020.
Giovanni Pistone and Henry P Wynn. Finitely generated cumulants. Statistica Sinica, 1999.
Aram-Alexandre Pooladian and Jonathan Niles-Weed. Entropic estimation of optimal transport maps, 2021.
Julien Rabin, Sira Ferradans, and Nicolas Papadakis. Adaptive color transfer with relaxed optimal transport. In 2014 IEEE International Conference Image Processing (ICIP), 2014.
levgen Redko, Nicolas Courty, Rémi Flamary, and Devis Tuia. Optimal transport for multi-source domain adaptation under target shift. In Proceedings of the Twenty-Second International Confer- ence on Artificial Intelligence and Statistics, 2019.
10

---

Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, al. aptimal-transpor analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 2019.
Vivien. Seguy, Bharath B. Damodaran, Remi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. In ICLR, 2018.
Byeongsu Sim, Gyutaek Oh, Jeongsol Kim, Chanyong Jung, and Jong Chul Ye. Optimal trans- port driven cyclegan for unsupervised learning in inverse problems. SIAM Journal on Imaging Sciences, 2020.
Jan Stanczuk, Christian Etmann, Lisa Maria Kreusser, and Carola- Schönlieb. Wasserstein gans work because they fail (to approximate the wasserstein distance). arXiv, 2021.
Tianxiao Sun and Quoe Tran-Dinh. Generalized self-concordant functions: a recipe for newton-type methods. Mathematical Programming. 2019.
Amirhossein Taghvaci and Amin Jalali. 2-wasserstein approximation via restricted convex potentials with application to improved training for gans. arXiv, 2019.
Alexander Tong, Jessie Huang, Guy Wolf, David Van Dijk, and Smita Krishnaswamy. Trajectorynet:
A dynamic optimal transport network for modeling cellular dynamics. In ICML, 2020.
Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, and Trancois-Xavies Vialard. A dimension-free computational upper-bound for smooth optimal transport estimation. In COLT, 2021.
Renjun Xu, Pelen Liu, Liyan Wang, Chao Chen, and Jindong Wang. Reliable weighted optimal transport for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.


Reviews:
[{"review_id": "XIx58E8IeYB", "reviewer": "Reviewer_vPxL", "summary": "The paper proposes a sample-based criterion to select the best convex Brenier potential among the list of available ones for the Wasserstein-2 optimal transport. The criterion is based on the theoretical result (lemma 1) which connects the semi-dual Brenier formulation of OT and the L2 error between the gradient of the approximate potential and the OT map. The main idea of the criterion is to simply take the potential for which the empirical semi-dual is the smallest: for this potential, one may guarantee that its gradient will not be far from the best available OT map (Proposition 2). The authors provide some quantitative evaluation in small dimensional spaces to illustrate that the potential selected by their criterion is good (they use SSNB, ICNN-based and Sinkhorn algorithms to get the candidate potentials). Also, they conduct a domain adaptation experiment to show that that the improved accuracy of computing the OT may does not necessarily yield increase in DA accuracy metric.\n", "questions": "Incorporated to the previous part.\n\n**Note:** My assessment is mostly based on the main text. I have looked through the main text + briefly looked through appendices. I did not run the code of the supplementary and did not check the proofs of appendices.", "limitations": "There is no separate section of paragraph with limitations, but some of them are discussed in the text, e.g., the necessity to consider smooth/strongly convex potentials.\n\nAnother important limitation, which seems not to be discussed in the paper, it the fact that the proposed criterion significantly relies on the brenier OT formulation, convexity of the dual potentials, Fenchel transform, etc. Thus,\n(1) the same analysis/ideas would presumably not generalize to other OT transport cost functions beyond W2 (quadratic cost);\n(2) the application of the criterion requires convex potentials which are in practice are either ICNNs or LSE functions (in the Sinkhorn case), which are both very restrictive. It is unclear whether these architectures will perform perform well in practical tasks.\n\nIt would be great if the authors could carefully discuss these important limitations in the answers and speculate on possible ways to overcome them.\n\n**Post-rebuttal:** I increase my score from 4 to 5.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength.** To my knowledge, there is no closely research related to model selection for optimal transport. The current paper seems to be the first who studies this question and proposes an approach to model selection in W2 optimal transport. It derives an upper bound on the empirical semi-dual error and provides an example showing that it is tight (in the non-stochastic regime).\n\nThe domain adaptation experiment also raises an interesting and important question: is it reasonable to apply OT in DA problems? Emphasizing and discussing this question might be interesting to the ML/OT community. The current paper shows that better DA performance not necessarily correlates with the OT performance, which points to a gap between computational OT and downstream applications.\n\n**Weaknesses.** I think the paper has several important flaws.\n\n*(1) Clarity.* The overall exposition, writing and presentation could be improved. First, most of the equations are in-line formulas which makes it hard to read the paper. Next, there is simply no introduction to the optimal transport problem: an unprepared reader without significant experience in OT (especially in W2 OT related to the Brenier formulation) will struggle to understand the message of this paper. In the paper, the OT problem has never been formally defined, only its dual is considered. Due to this, it might be hard to understand how all these derivations are related to the domain adaptation problem studied later (why the gradient of the OT potential is a meaningful mapper for DA problem?). In general, it is not trivial to follow the stream of thoughts of the authors: there is limited discussion of the meaning of propositions/theoretical results and transition between them. For example, in my view, the main criterion is not clearly stated: how to apply it in practice? (Note: this could be understood from the experimental section, but I think the authors should devote a separate paragraph for this to make it clear).\n\n*(2) Main contribution.* While the idea is novel, but one might argue that it is rather straightforward from the theoretical point of view. Indeed, the key proposition 2 follows from lemma 1 (which is a already known result in W2 optimal transport) and Hoeffding lemma (the authors themself note this in line 168).\n\n*(3) Related work.* Most of the related work seems to be resonably covered. However, in some cases whether the provided results are new or they already exist. For example, as a reader, I do not understand whether results in section 4 are novel or it is just a discussion of some related OT background with illustrations. In the discussion of the related methods 246-252, it is not straightforward to come up with the optimization objective of line 248. The authors could have repeated a reference to the original method’s paper. Same applies to SSNB method (253-256). How to optimize this objective? Additional details and clarifications could be useful (in the main text (!), not appendix). Besides, there is a work [1] which is not cited in the current paper although it seems to be closely related as its authors also discuss the necessity to use strongly convex/smooth potentials (which is heavily relied on the current paper). Also, lemma 1 (which the authors use) is also present in [1]. \n\n[1] Korotin, A., Egiazarian, V., Asadulaev, A., Safin, A., & Burnaev, E. (2021). Wasserstein-2 Generative Networks. In International Conference on Learning Representations.\n\n*(4) Experiments.* The synthetic experiments seem to be a little bit limited. I think the authors should consider more examples and in different dimensions (not only d=8) to study the practical usefulness of their criterion. In the current form, the evaluation (Tables 2, 1, 3) is not sufficiently convincing.\n\nRelevance of DA experiments. As I noted earlier, the OT DA part of the paper raises and discusses an interesting question: is the OT map a valid adaptation map in DA? While the question is important, I would argue that the answer to the question is just obvious: for some dataset pairs OT map may be a meaningful, for some - not. In particular, I have checked three papers that the authors cite [Courty et al., 2017], [Redko et al., 2019], [Xu et al., 2020]. If I understand correctly, the methods are mostly discrete (they are not interested in the dual potentials as functions contrary to the current work) and their authors typically propose costs/regularization to make the mapping obtain desired properties instead of  using the “raw” W2 cost (which is studied here) [between features]. Thus, the DA experiment in the current paper is a nice illustration of their criterion but is note very significant.\n\nTo conclude, I think the most serious weaknesses are (1) [clarity] and (4) [experimental evaluation].\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CbVeAcVV4wO", "reviewer": "Reviewer_Qbsh", "summary": "Given two measures $\\mu$ and $\\nu$, and a set of estimated potentials (from the dual formula in Optimal Transport theory) between them, the paper provides a criterion to select the potential having a corresponding pushforward map (derivative) being closest to the Monge map. Thanks to the assumptions of strong convexity and smoothness of the potentials, and Bernstein-typed of inequalities, we can provide the theoretical bounds for error of this method non-asymptotically (Lemma 1 and Proposition 2). Some experiments and applications are provided to support the method and theory. It also gives a good negative finding to Optimal Transport Domain Adaptation models that the best Domain Adaptation map is not close to the Monge map in several applications.", "questions": "1. The calculation in Proposition 1 seems to be not correct. Because in the OT dual formula, the constraint $\\phi(x) + \\psi(x) \\leq (x-y)^2/2$ only needs to satisfy in the $Support(\\mu)\\times Support(\\nu)$. Similar to constraint of the potentials $f(x) + g(y) \\geq xy$. Therefore, in this case, because both the support of $\\mu$ and $\\nu$ are compact, we can not use the definition of Fenchel-Legendre on the whole domain $\\mathbb{R}$ (but with respect to $[-1/2, 1/2]$ only). This potentially relates to other results and proofs in this paper. \n\n2. Similar to the synthetic experiment, the Domain Adaptation experiment also needs to run with a few replications. The result should be then more reliable. When we learn the transport map $T$ from training data and evaluate potentials on the test data, how can we make sure that the distribution of the training and test data are the same? The experiment description should be more clear in this aspect.", "limitations": "While the research question is interesting, the approach is good and natural, it appears to have several points that can be improved in this paper, both in terms of theory and experiments (see above). I suggest the authors examine those points carefully and make the paper better. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: \n\n1. The idea of this paper is natural and good. From a naive perspective, it is natural to select the potential as the one optimizing the dual formulation. The theory from this paper supports this viewpoint, and the experiments empirically show it is effective. The take-away lesson in the paper is valuable to Optimal Transport and Domain Adaptation researchers.\n\n2. The presentation of the paper is clear, the story is well-motivated, and the experiments part is carefully carried out.\n\n**Weakness**: \n\n1. There are still many typos in the manuscript. For example, in the caption of Figure 1: \"pic\", in line 208: \"conidtion\", and in line 209: \"argmin\" (instead of argmax).\n\n2. Some of the arguments and theoretical results appear to be not correct (see Questions).\n\n3. To make the presentation of the paper more fluent, I think the authors should merge Section 4 and Section 5.1 because they both talk about finding potentials. The paragraph \"Self-concordant potentials\" is not clearly written about how we can obtain the conjugate via the second-order method. It is better to just present the method to find the conjugate and a theoretical result about its sample complexity (combination of Definition 1 and Proposition 7) instead of introducing a new notion (generalized self-concordant). A detailed explanation can be put in the appendix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4ZVlCT87ShU", "reviewer": "Reviewer_Visd", "summary": "This paper proposes a novel criterion to evaluate how close an estimated (L2 Wasserstein) optimal transport plan between two given measures is close to the true (unknown) optimal transport plan. To do so, the authors rely on the semi-dual formulation of the Kantorovich problem, and prove that the objective function for this formulation (using discrete measures with n points) is highly correlated with the L2 distance between the estimated transport plan and the true one (and give bounds). The authors require that the potential to be estimated has a Lipschitz gradient, and the true potential is strongly convex. When those criteria are met, the semi-dual objective is finite and can be used as a proxy for the distance to the optimal map. The authors show that the map minimizing this criterion are related to the distance between the true map and the closest one, through an inequality involving a factor depending on the regularity of the estimated map. When the regularity criteria are not met, the authors argue that the potentials can be regularized using an additive quadratic term for the semi-dual objective to be computable. The criterion can be used for hyperparameter tuning in various OT algorithms (including Sinkhorn iterations, that do not natively satisfy the requirements), or to evaluate whether performance for a downstream task (here domain adaptation) correlates or not with OT performance. Somewhat surprisingly, performance on a DA task does not correlate with the quality of the OT map.", "questions": "- It would be quite informative to check the bound validity on practical cases where everything is known (e.g OT between gaussians, where gamma and M, and T0 can be explicitly computed, or even the synthetic experiments with a quadratic potential). Examples in 1D such as the one illustrated in Fig. 1 (which is never really discussed beyond the introduction, though it brings the point across nicely) could also have been explored in more detail.\n\n- On a related note, the bound provided in equation one is particularly interesting, since even if the function minimizing the semi-dual criterion has a small smoothness coefficient (M), the ratio M/gamma cannot become smaller than one (in the non-stochastic case). This would contradict the optimality of the model in the RHS. Are there results on this or do the authors have some insight on the interplay between the smoothness of f0 and the strong convexity of f1 ? Would it be for example possible to have an idea of the optimal model if only those constants are known, without computing the semi-dual criterion ?\n\n- Why does the number of candidate models vary so much from one model to the next ? There are only 5 hyperparameter values for the Sinkhorn potentials, while the method is quite fast to train and the number of candidate models could have been higher.\n\n- I checked [Caffarelli 2000] but could not find exactly what result was being referenced in theorem 1, but I could have missed something. Can the authors provide the exact reference to the theorem and its proof? Besides, the conclusion that under the hypotheses of this theorem, the Brenier potentials are smooth and strongly convex are not obvious to me and could deserve some explanation (the theorem only states they are convex and C2). Also, what happens for continuous measures with non compact support (e.g. Gaussians) ?\n\n- The counter examples (propositions 1 and 3) are a bit abrupt and would benefit a bit more contextualization. For example, proposition 3 aims at showing in a practical case that the bound is tight in the infinite samples regime. But isn’t this a general result, valid for any case as long as n goes to infinity ? I am not sure what the example brings exactly. ", "limitations": "The authors point out that the conditions required for the semi dual to be both finite and reliable in terms of correlating with the OT performance may be restrictive in some cases.\nFor Sinkhorn models, they resolve this in practice via quadratic regularizations and suggest useful bounds could be obtained under less strong regularity conditions. \nThey also show experimentally that the critetion may not correlated with OT performance when the regularity of the obtained potentials cannot be controlled (as in ICNNs).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths :\n\n- The authors propose a conceptually simple way to rank candidate estimated OT maps in terms of how well they approximate the true map, without using the latter. This could be potentially very useful to compare algorithms in the future, or to check on pratical cases whether or not optimal transport is a good constraint to add to improve performance on a given downstream task.\n\n- The theoretical developments are well presented and the empirical results are well illustrated by the experimental results. Namely the regularity in practice of the potentials is well shown (on simple computable examples and when comparing the different algorithms) to be crucial for the proposed semi-dual criterion to be computable and more importantly reliable.\n\n- The approach can be applied in practical case where the semi-dual would normally not be useful (infinite) thanks to small regularizations providing the necessary smoothness and strong convexity. This in particular makes the approach applicable (and tractable thanks to efficent ways to compute the Legendre transform) to Sinkhorn models which are among the most common.\n\n- The Domain Adaptation experiment provides interesting nsight on this problem and answers at least partially to the question of how useful OT is in this situation.\n\nWeaknesses :\n\n- The presentation and motivation foir presenting some of the propositions and theorems could be improved (See below for details on this point)\n\n- The results on domain adaptation, given their potential consequences on the applicability of OT to this problem, would probably have to be confirmed on another case study, either on another real dataset, or maybe a low dimensional toy dataset (where maybe the optimal transformationis knwon) for this result to be strengthened.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1kUAyszI3ML", "reviewer": "Reviewer_8oqQ", "summary": "This paper uses Lebesgue transform to give the semi-dual Brenier objective as the quantitative criterion for convex potential selection .\nThis criterion enables parameter tuning and model selection among entropic regularization of OT, input convex neural networks(ICNN) and smooth and strongly convex nearest-Brenier (SSNB) models.\nThe authors also use this criterion to question the use of OT in Domain-Adaptation.", "questions": "How to ensure that the final model selection is accurate if the performance of ICNN is not optimal? ", "limitations": "They proposed the limitation of their algorithm, but doesn't address the potential negative societal impact .", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: this paper uses Lebesgue transform to give the semi-dual objective as the quantitative criterion . The theoretical derivation and experiments show the effectiveness of the method. \nThis paper has been proved by experiment that the map minimizing the semi-dual, hence the closest to the ground truth OT map, is often far from being the one that achieves the best label transfer.\nWeakness: (Page 8,paragraph 2)The authors claimed the choice of network structure may lead to poor ICNN performance,which needs more experimental verification. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept