Efficient estimates of optimal transport via low-dimensional embeddings
Authors: Patric Fulop
Vincent Danos
Venue:  (2021)
Keywords: optimal transport
sinkhorn divergences
robustness
neural networks
lipschitz
spectral norm

Abstract: Optimal transport distances (OT) have been widely used in recent work in Machine Learning as ways to compare probability distributions. These are costly to compute when the data lives in high dimension.
Recent work aims specifically at reducing this cost by computing OT using low-rank projections of the data (seen as discrete measures)~\citep{paty2019subspace}. We extend this approach and show that one can approximate OT distances by using more general families of maps provided they are 1-Lipschitz. The best estimate is obtained by maximising OT over the given family. As OT calculations are done after mapping data to a lower dimensional space, our method scales well with the original data dimension.
We demonstrate the idea with neural networks. 

Under review conference paper at ICLR 2021
EFFICIENT ESTIMATES OF OPTIMAL TRANSPORT VIA EMBEDDINGS CONFERENCE SUBMISSIONS
Anonymous authors Paper under doublc-blind review
ABSTRACT
Optimal transport distances (OT) have been widely used in recent work in Machine Learning as ways to compare probability distributions. These are costly to compute when the data lives in high dimension. Recent work aims specifically this cost by computing OT using low-rank projections of the data (seen as discrete measures) (Paty & Cuturi, 2019). We extend this approach and show that one can approximate OT distances by using more general families of maps provided they are 1-Lipschitz. The best estimate is obtained by maximising OT over the given family. As OT calculations are done after mapping data to lower dimensional space, our method scales well with the original data dimension. We demonst rate the idea with neural networks. We Sinkhorn Divergences (SD) to approximate OT distances as they are differentiable and allow for gradient-based optimisation. We illustrate on synthetic data how our technique preserves accuracy and displays a low sensitivity of computational costs to the data dimension.
reducing
1 INTRODUCTION
Optimal Transport metrics (Kantorovich, 1960) or Wasserstein distances, have emerged successfully in the field of machine learning, as outlined in the review by Peyré et al. (2017). They provide machinery to lift distances X' to distances over probability distributions in machine learning: domain adaptation Courty
P(X). They have found multiple applications et al. (2017), density estimation (Bassetti et al., 2006) and generative networks (Genevay al,, 2017; Patrini et al., 2018). However, it is prohibitively expensive to compute OT between distributions with support in a high-dinensional space and might not even be practically possible as the sample complexity can grow exponentially as shown by Dudley (1969). Similarly, work by Weed et al. (2019) showed a theoretical improvement when the support of distributions is found in a low-dimensional space. Furthermore, picking the ground metric that one should use is not obvious when using high-dimensional data. One of the carlier idcas from Santambrogio (2015) showed that OT projections in a 1-D space may be sufficient enough to extract geometric information from high dimensional data. This further prompted Kolouri ct al. (2018) to use this method to build generative models, namely the Sliced Wasserstein Autoencoder. Following a similar approach Paty & Cuturi (2019) and Muzellec & Cuturi (2019) project the measures into a linear subspace E of low-dimension & that maximizes the transport cost and show how this can be used in applications of color transfer and domain adaptation. This can be seen as an extension to carlier work by Cuturi & Doucet (2014) whereby the cost function is parameterized.
One of the fundamental innovations that made OT appealing to the machine learning com-

---

Under review conference paper at ICLR 2021
munity was the seminal paper by Cuturi (2013) that introduced the idea of entropic regularization of OT distances and the Sinkhorn algorithm. Since then, regularized OT has been successfully used as a loss function to construct generative models such as GANs (Genevay et al., 2017) or RBMs (Montavon et al., 2015) and computing Baryeenters (Cuturi & Doucet, 2014; Claici et al., 2018). More recently, the new class of Sinkhorn Divergences was shown by Feydy al. (2018) to have good geometric properties, and interpolate between Maximum Mean Discrepancies (MMD) and OT.
Building on this previous work, we introduce a general framework for approximating high- dimensional OT using low-dimensional projections f by finding the subspace with the worst OT cost, i.e. the one maximizing the ground cost on the low-dimensional space. By taking a general family of parameterizable fas that are 1-Lipschitz, we show that our method generates a pseudo-metric and is computationally efficient and robust. We start the paper in $2 with background on optimal transport and pseudo-metrics In $3 we define the theoretical framework for approximating OT distances and show how both linear (Paty & Cuturi, 2019) and non-ling -ineiea projections can be seen as a special instance of our framework. In $4 we present an efficient. algorithm for computing OT distances using Sinkhorn Divergences and fas that are 1-Lipschitz under the Le norm. We conclude in $5 with experiments illustrating the efficiency and robustness of our method.
2 PRELIMINARIES
We start with brief reminder of the basic notions needed for the rest of the paper. Let X be set equipped with a map dx : X x X' + Rz0 with non-negative real values. The pair (X, dx) is said to be metric space and dx is said to be metric on X' if it satisfies the usual properties:
dx(x. v) 0 if and only if i =
dx(z,v) dx(
dx(x,)) S dx(x, v) + (v
dx verifies the above except for the only if condition, it is called a pseudo-metric, and (X,, dx) said to be a pseudo-metric space. For a pseudo-metric, it may be that (x y) 0 while x # y-
We write dx I d'x if for all x, dx(x,,) I d'x((,))) y). It is easy to see that: 1) "<" a partial order on pseudo-metries over X, 2) "<" induces complete lattice structure on the set of pseudo-metrics over X, where 3) suprema are computed pointwise (but not infima).
Consider X, V, two metric spaces equipped with respective metrics dx, dy- A map ʃ from X to Y is said to be a-Lipschitz continuous if (x(()) S odx(x,x)). 1-Lipschitz map is also called non- expaessssiiee
Given a map f from X' to y one defines the pullback of dy along f as:
f(dy)(x, = dy([(z),
(1)
It is easily seen that: 1) f(dy) is a pseudo-metric on X, 2) f(yy) is a metric iff f is injective, 3) f(dy) s dx iff f is non-expansive, 4) f(dy) is the least pseudo-metric on the set X such that f is non-expansive from (x, fdy)) to dy).
Thereafter, we assume that all metric spaces considered are complete and soparable, i.c. have a dense countable subset.
2

---

Under review conference paper at ICLR 2021
Let (X, dx) be a (complete separable) metric space. Let Ex be the o-algebra generated by the open sets of X (aka the Borelian subsets). We write (()) for the set of probability distributions on (X' Ex).
Given measurable map f X. + V and E (X) one defines the push-forward of μ along f as: f= pff (B)
(2)
for E Σy. It is easily seen that f is probability measure on (V,Er)
Given μ in (X), in PP)), a coupling of & and is a probability measure 7 over X y such that for all A in Ex, B in By, 7(A x X) = =((), and >(X' x B) = (B). Equivalently, Too (T), and == x (T) for To, #1 the respective projections.
We write v) for the set of couplings of μ and v.
There are several ways lift given metric structure on dx to one on 9()). We will be specifically interested in metries on (X) derived from optimal transport problems.
The p- Wasserstein metric with p E (1) defined by:
/
W U))
inf yET(u,)) xxx dzx dy
Villani (2008) establishes that if dx is (pseudo-) metric so is (dddx). The natural 'Dirac' embedding of X' into P (XX) is isometric (there is only one coupling).
The idea behind the definition that dl is used as a measure of the cost of transporting units of mass in X' while coupling y specifies how to transport the μ distribution to the one. One can therefore compute the mean transportation cost under 7, and pick the optimal 7y Hence the name optimal transport.
In most of the paper, we are concerned with the case X' Rd for some large with a metric structure dx given by the Euclidean norm, and we wish to compute the W2 metric between distributions with finite support. Since OT metrics are costly to compute in high dimension, to estimate these will
efficiently, and mitigate the impact. of dimension,
well-chosen family of fs to push the data along a map with a low dimensional co-domaín y also equipped with the Fuclidean metric. The reduction maps may be linear or not. They have to be non-expansive guarantee that the associated pull-back metrics are always below the Euclidean one, and therefore we provide lower estimate (222).
3 APPROXIMATE OT WITH GENERAL PROJECTIONS GPW
With the ingredients from the above section in place, we can now construct a general framework for approximating Wasserstein-like metrics by low-dimensional mappings of X. We write simply W instead of Wp as the value of p plays no role in the development.
Pick two metric spaces (X, dx), (V, dy), and a family S (fs X' - V: o S) of mappings from X to y. Define map from (X) x (X) to non-negative reals as follows:
ds(u, v) sup ((d)) (A), So (v)
(4)
Equivalently and more concisely ds can be defined as: ds(u,v) v) sup W ((fo(dd))))
(5)
It is casily seen that:
3

---

Under review conference paper at ICLR 2021
1. the two definitions are equivalent
2. ds is pseudo-metric on (X))
3. ds is metric (not just pseudo one) if the family fo jointly separates points in X' and
4. if the fas are non-expansive from (X, dx) to (V, dy), then ds S <W(dx)
The second point follows readily from the second definition. Each foldy) is a pscudo-metric on X' obtained by pulling back dy (see preceding section), hence, so is W ([fo(dy) on (()), and therefore ds being the supremum of this family (in the lattice of pseudo-metrics over X) is itself pseudo-metric.
The first definition important because it allows one to perform the OT computation in the target space where it will be cheaper.
Thus we have derived from 8 pseudo-metric ds on the space of probability measures ( We assume from now on that mappings in & are non-expansive. By point 4. above, we know that ds is bounded above by W(dx). We call ds the generalized projected Wasserstein metric (GPW) associated to S. In good cases, it is both cheaper to compute and a good estimate.
3.1 SRW AS AN INSTANCE OF GPW
In Paly Cuturi (2019), the authors propose to estimate W2 metrics by projecting the ambient Euclidean X' into k-dimensional linear Euclidean subspaces. Specifically, their derived metric on (X), written Sk, can be defined as (Paty Cuturi, 2019, Th. 1, Eq. 4):
(u = sup W (1) (w). (w)
where: 1) dy is the Euclidean metric on V, 2) Ω contains all positive semi-definite matrices of trace & (and therefore admitting a well-defined square root) with associated meni-metric smaller than dx.
We recognise a particular case of our framework where the family of mappings is given by the linear mappings vΩ: Rd X' y = R* under the constraints above. In particular, all mappings used are linear. The authors can complement. the general properties of the approach with a specific explicit bound on the error and show that St S. (dxx))= S (d/k)S? In the general case, there is no upper bound available, and one has only the lower one.
3.2 NON-LINEAR EMBEDDINGS FOR APPRONIMATING WASSERSTEIN DISTANCES
Using the same Euclidean metric spaces, X' X R²= R* we observe that our framework does not restrict us to use linear functions as mappings. One could use family of mapping given by a neural network (Sg : X + y; & S) where & ranges over network weights. However, not any o is correct. Indeed, by point 4) in the list of properties of ds, we need fas to be non-expansive. Ideally, we could pick to be the set of all weights such that fo is non-expansive.
There are two problems one needs to solve in order to reduce the idea to actual tractable computa- tions. First, one needs an efficient gradient-based search to look for the weights ó which maximise sups ((dy) (H), (v)) (see 4). Second, as the gradient update may take the current fo out of the non-expansive maps, one needs to project back efficiently in the space of non-expansive.
Both problems already have solutions which are going to re-use. For the first point, we will Sinkhorn Divergence (SD) (Genevay et al., 2017). Recent work Foydy et al. (2018) shows that SD, which one can think regularised version of W, is sound choice loss function in machinc
4

---

Under review conference paper at ICLR 2021
learning. It can approximate W closely and without bias (Genevay al., 2017), has better sample complexity (Genevay ct al., 2019), as well as quadratic computation time. Most importantly, it is fully diffcrentiable.
For the second problem, one can 'Lipshify' the linear layers of the network by dividing their (op- erator) norm after each update. We will use linear layers with Euclidean metrics, and this will need to estimate the spectral radius of each layer. The same could be done with linear layers using a mixture of Tr, Ln and Lox metrics. In fact computing the I - L1 operator norm for linear layers is an exact operation, opposed to using the spectral norm for L2 + L2 case where we approximate using the power method.
Note that the power method can only approximate the Ly norm and gradient ascent methods used in the maximization phase are stochastic making our approximation susceptible to more variables. However, it is extremely efficient since it requires computation of optimal transport distances only in the low-dimensional space. We can see this as a trade-off between exactness and efficiency.
4 COMPUTATIONAL DETAILS
In this section we propose Algorithm for stochastically estimating ds between two measures with finite support where the class of mappings S is as defined above. Note that this algorithm can further be used during the training of a discriminator as part of a generative network with an optimal transport objective, similar to Genevay et al. (2017). The Sinkhorn Divergence alternative for ds now uses Sinkhorn divergences as a proxy for OT (compare with equation 4):
SD = W. (dy) (w), (v)) 1 W. (ddd)))oo Son (1))
1
W. (dd) Sox (7)
2
where W. is the well-known Sinkhorn regularized OT problem (Cuturi, 2013). The non- parameterized version of the divergence has been shown by Feydy et al. (2018) to be an unbiased estimator of (p,,v) and converges to the true OT distance when constructs an effective numerical scheme for computing the gradients of the Sinkhorn divergence on GPU, without having to back-propagate through the Sinkhorn iterations, by using autodiffer- entiation and the detach methods available in PyTorch (Paszke et al., 2019). Moreover, work by Schmitzer (2019) devised an e-scaling scheme to trade-off between guaranteed convergence and speed. This gives us further control over how fast the algorithm is. It is important to note that the minimization computation happens in the low-dimensional space, differently from the approach in Paty & Cuturi (2019), which makes our algorithm scale better with dimension, seen in $5.
O. Their paper also
Feydy et al. (2018) established that the gradient of 7 w.r.t to the input measures μt, is given by the dual optimal potentials. Since we are pushing the measures through a differentiable function fo. we can do the maximization step via a stochastic gradient ascent method such as SGD or ADAM (Kingma & Ba, 2014). Finally, after each iteration, we project back into the space of 1-Lipschitz functions fg- For domain-codomain L2 + + L2 the Lipschitz constant of a fully connected layer is given by the spectral norm of the weights, which can be approximated in a few iterations of the power method. Since non-lincar activation functions such as ReLU are 1-Lipschitz, in order to project back into the space of constraints we suggest to normalize each layer's weights with the spectral norm, i.e. for layer i we have Φ := dz ///l//i]|- Previous work done by Neyshabur et al. (2017) well as Yoshida & Miyato (2017) and Miyato et al. (2018) showed that with smaller magnitude weights, the model can better generalize and improve the quality of generated samples discriminator in GAN. We note that if we let fø to be a 1-Layer fully connected network with no activation, the optimization we perform is very similar with the optimization done by Paty & Cuturi (2019). The space of 1-Lipschitz functions we are optimizing over is larger and
when used
5

---

Under review conference paper at ICLR 2021
our method stochastic, but we are able recover very similar results at convergence. Moreover, our method applies to situations where the data lives in a non-lincar manifold that an fo such as neural network able model. Comparing different numerical propertics of the Subspace Robust Wasserstein distances in 6 with our Generalized Projected Wasserstein Distances is the focus of the next section.
Algorithm 1 Ground metric parameterization through ø
Input: Mcasures μ E, 02 and v = En 6y by, fo IR - R 2-Layer network with dimen- sions (d, 20, k) and 1-T.ipschitz, optimizer ADAM, power method iterations X, SDo.c unbiased Sinkhorn Divergence.
Output: Sex SD..
Initialize:
Ir,c,,, fo NO0 10), Objective SD.lblur 2pp= 2, debias Truc) for l...., mariter do
-DD (f (f f0
(pushforward through fa and evaluate SD in lower space) (maximization step with autodiff)
grad + Autodiff(L)
(grM()r
(gradient step with SGD and scheduler) (projection into 1-Lipschitz space of functions)
+ P-ojjji-
end for
EXPERIMENTS
We consider similar experiments presented in Forrow et al. (2019) and Paty & Cuturi (2019) and show the mean estimation of SD,, v) for different values of k as well as robustness to noise. We also show how close the distance generated by the linear projector from Paly & Cuturi (2019) is to our distance and highlight the trade-off in lerms of computation time with increasing number of dimensions.
In order illustrate our method, we construct two empirical distributions A. & by taking samples from two independent measures space. Similarly to Paty & Cuturi (2019) we construct the covariance matrices E,, Mg such that they are of rank 5, i.c. the support of the distributions is given by 5 dimensional lincar subspace. Throughout our experiments we fix fo to be a 2-layer neural network with hidden layer of 16 units, activation function ReLU and output of dimension k. We initialize the weights from No, 10) and use standard ADAM optimizer with decaying cyclie learning rate (Smith, 2017) bounded by (0.1,100) Decreasing and increasing the learning rate via scheduler allows to not fall into local optima. The batch size for the algorithm is set to n 500, which is the same number of samples that make up the two measures. Bosides the neural network variables, strength small enough, to c = 0.001, and the scaling to e-scaling = 0.95 such that we can accurately estimate the true optimal transport distance, but not spend too much computational time during the Sinkhorn iterates.
(0, and v (O Σn) that live in a 10 dimensional
set the regularization
5.1 10-D GAUSSIAN DATA OT ESTIMATION USING SD
This leaves with three variables of interest during the computation of SD namely k. d, X (latent dimension, input dimension, power method iterations). The power method iterations plays an important role during the projection step, as for small number of iterations, there is chance
6

---

Under review conference paper at ICLR 2021
60
1.0-
Mean Normalized distances
40
2/4. 0)
10
50
k=3
Noisy SDgln v/
SDain, v//2
k=
k=10
Noisy 53 wMW
WA M
SiM. vur v
100
203
300
520
Iterations
Figure 1: Mean estimation of (1, for different values the latent dimension Horizontal line is constant and shows the true (n,, v). The shaded area shows the stan- dard deviation
Figure 2: Mean normalizod distances with and without noise for (u, and (H, v) function of latent dimension k. The shaded area shows the standard deviation over 20 runs.
20 runs.
of breaking the constraint. At the same time, running the algorithm for too long is computationally expensive. In Figure 1 used X = 5 power iterations and show the values of SD after rumning 1 for 500 iterations. We compare them to the truc OT distance for various levels of k and observe that even with a small number of power iterations, the estimation approaches the true value as & increases. Furthermore, see that for k = 5 and k the algorithm converges after 200 steps.
Using 20 power iterations, show how the approximation behaves in the presence of noise as a function of the latent space k. We add Gaussian noise in the form of (00, to ù,, and show in Figure 2 the comparison between noise and noise for both SRW distances defined in and GPW 4. We observe that SD2 0. behaves similarly to 5% in the presence of noise.
5.2 COMPUTATION TIME
In Figure. 8 Paty & Cuturi (2019) they note that their mothod when using Sinkhorn itcrates quadratic in dimension because of the eigen-decompositioon of the displacement matrix. Fundamen- tally different, we are always optimizing in the embedded space, making the computation of the Sinkhorn iterates linear with dimension. Note that there is the extra computation involved with pushing the measures through the neural network and backpropagating as well as the projection step that depends and generate A, & by changing dimension but leaving the rank of Σ,, Σ2 equal to 5. The latent space is fixed to l 5. In Figure 3 we plot the normalized distances using the two approaches function of dimension and see that the gap gets bigger with increasing dimensions, but it is stable. In Figure we plot the log of the relative computation time, taking the d 10 as benchmark in both cases. We see that the time to compute SD3, is linear in dimension and is significantly lower increase the number of dimensions. This be traced back to Algo-
the power iteration method. In order to run this experiment we set À 5
than its counterpart S2 rithm. 1 and Algorithm. 2 of Paty & Cuturi (2019) where at each itcration stop, the computation of OT distances in the data space is prohibitively expensive.
7

---

Under review conference paper at ICLR 2021
66
sogta wow' uu v fa v//W(u..
Relative computation (lop scale)
50 v) 5214
Mean Normal bred distances
6.8-
6.74
6.-
0.4
202
1000
1250
1500
1750
2002
252
762
1000
125a
1750
2000
Dimension
Dimension
Comparison between normalized S v) and normalized (1,,, v) func- tion of dimension. The shaded area shows the standard deviation over 20 runs.
Figure 3:
Figure 4: Mean relative computation time (log scale) comparison between the two dis- tances. The shaded area shows shows the standard deviation over 20 runs.
6 CONCLUSION
In this paper we presented a new framework for approximating optimal transport distances using a wide family of embedding functions that are 1-Lipschitz. We showed how linear projectors can be considered a special case of such functions and proceeded to define neural networks another class of embeddings. We showed how we can use existing tools to build an efficient algorithm that robust and constant in the dimension of the data. Future work includes showing the approximation valid for datasets where the support of distributions lies low-dimensionall non-linesd non-linear manifold, where hypothesize that linear projects would fail. Other work includes experimenting with different operator norms such as L1 or Lint for the linear layers and the approximation of W1- An extension of the projection step in to convolutional layers would allow to experiment with real datasets such as CIFAR-10 and learn a discriminator in an ad adversarial way with SDR, as loss function. This be used to show that the data naturally clusters in the embedding space.
REFERENCES
Federico Bassetti, Antonella. Bodini, and Eugenio Regazzini. On minimum kantorovich distance estimators. Statistics probability letters, 76(12):1296 1302, 2006.
Sebastian Claici, Edward Chien, and Justin Solomon. Stochastic wasserstein barycenters. arXiv preprint arv: 05757, 2018.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730 3739, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pp. 2292 2300, 2013.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. International Conference on Machine Learning, pp. 685-693, 2014.
8

---

Under review conference paper at ICLR 2021
Richard Mansfield Dudley, The speed of mean glivenko-cantelli convergence. The Annals of Math- ematical Statistics, 40(1):40-50, 1969.
Jean Feydy, Thibault Séjourné, François-Xavel Xavier Vialard, Shun-Tchi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. arXiv preprint arXiv:1810.088 082288, 2018.
Aden Forrow, Jan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2454-2465. PMLR, 2019.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Sinkhorn-autodiff: Tractable wasserstein learning of generative models. arXiv preprint arxi (000000000 2017.
Aude Genevay, Lénaic Chizat, Francis Bach, Mareo Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1574 1583, 2019.
Leonid Vital?evich Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6(4):366 422, 1960.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprinl
arXim: 141.:141..00 22800, 2014.
Soheil Kolouri, Phillip E Pope, Charles E Martin, and Gustavo K Rohde. toencoder: An embarrassingly simple generative model. arXiv preprint arXiv:1804.01947, 2018.
au-
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprinl 1rx:::1802.000 05957, 2018.
Grégoire Montavon, Klaus-Robert Müller, and Marco Cuturi. Wasserstein training of Boltzmann machines. arXiv preprinl 1xXi::107701177 2015.
Boris Muzellec and Marco Cuturi. Subspace detours: Building transport plans that are optimal on subspacc projections. In Advances in Neural Information Processing Systems, pp. 6917-6928, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in neurol information processing systems, pp. 5947 5956,
2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zoming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in newral information processing systems, pp. 8026 8037, 2019.
Giorgio Patrini, Rianne van den Berg, Patrick Forre, Marcello Carioni, Samarth Bhargav, Max Welling, Tim Genewein, and Frank Nielsen. Sinkhorn autoencoders. arXiv preprint arXix:1810.00 01110011011, 2018.
François-Pierre Paty and Marco Cuturi. Subspace robust wasscrstein distances. arXiv preprint arXiv:1901.08949, 2019.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport. Technical report, 2017.
9

---

Under review conference paper at ICLR 2021
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 2015.
Bernhard Schnitzer. Stabilized sparse scaling algorithms for entropy regularized transport prob- lems. SIAM Journal on Scientific Compuling, A3333A11443AA 2019.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Con- ference on Applications of Computer Vision (WACV), pp. 464-472. IEEE, 2017.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Jonathan Weed, Francis Bach, et Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):2620-644) 2019.
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint orXiv: 10941, 2017.
10


Reviews:
[{"review_id": "tQgm2nhJUv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "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": "", "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": "This paper addresses estimation of a certain type of OT distance, substance robust wasserstein distances, by Patty and Cuturi, 2019\n\nI don't think this paper is suited for publication since it lacks enough substance. \n\n1)There is gross error in the abstract: the curse of dimensionality doesn't refer any cubic scaling, but on an exponential dependence in dimension.\n2)the first 4 pages are spent on elementary definitions. This appears as an unnecessary padding. I suggest authors put that kind of definitions in the appendix and/or cite relevant literature, e.g. the paper by Patty and Cuturi.\n3)The overall idea, although sensible, appears unjustified. Why would the community be interested in this problem? In the current papers, authors claim they are generalizing the results of Patty et al. Nonetheless it is unclear whether there is reasons for wanting to create such generalized framework. It would be helpful if the authors had a concrete application to showcase their results.\n4)Experimental results are weak, and comparisons with other methods are lacking, so it is hard to judge what are the actual gains.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hnlK5BJR8Lz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "", "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": "The paper lists a general approach to compare probability distributions. In particular it generalizes the approach by  \\cite{Paty and Cuturi, 2019} to include arbitrary projections. In my mind, the idea of the paper is nice although I am not sure of its novelty. However, currently this seems a preliminary attempt to me  (although a good one) rather than a complete paper. An extensive theoretical treatment needs to be carried out to truly establish the utility of this metric under high-dimensional circumstances. There needs to be more experimental setups that need to also be checked. In particular how does this method behave for heavy tailed distributions. When does this lose its speed? How does it perform for estimation of distances for mixture distributions? All of these questions would help strengthen the claim of superiority of the metric mentioned. I would encourage the authors to resubmit a more complete draft at a future submission.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UejE_cpyaca", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "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": "The paper introduces the notion of the generalized projected Wasserstein metric (GPW) as a pseudo-metric, associated with a set of mappings, between two probability measures. \nWhen applied to the parametric set of mappings defined by a neural network with an output layer much narrower than the input layer, GPW can be used for performing nonlinear dimension reduction. The authors propose to replace the Wasserstein distance used in the definition of GPW by the Sinkhorn divergence and to solve the resulting optimization problem by combining the Sinkhorn algorithm and the projected gradient descent.  \n\nThe paper is written as a sequence of historical remarks, literature review, definitions of some notions, and statements of their properties, without clearly defining what is the problem under consideration and what is the most important novelty leading to the main contribution. More precisely, the authors write (the last paragraph of the introduction) \"[...] we introduce a general framework for approximating high-dimensional OT using low-dimensional projections by finding the subspace with the worst\nOT cost [...]. By taking a general family of parameterizable fφs that are 1-Lipschitz, we show that our method generates\na pseudo-metric and is computationally efficient and robust.\" \n\n a) As far as I understand, what the authors call \"general framework introduced in this work\" is the definition (4). \nI would not qualify this definition as a new general framework.\n \n b) Contrarily to what is claimed, it is not clear that problem (4) approximates the high-dimensional OT. In particular, the\n metric d_X, playing a central role in the high dimensional OT between mu and nu, is not used at all in the definition of d_S.\n This metric appears implicitly when the function class is specified and chosen to be 1-Lipschitz wrt d_X. But still, it is not clear to me why the GPW can be thought of as an approximation of high-dimensional OT. \n\n c) There is no sufficient justification in this paper for claiming that the pseudo-metric defined by d_S is computationally efficient and robust. Furthermore, I would very much appreciate if the authors could elaborate on how the computational efficiency and the robustness should be understood within this work. \n\n***   More specific remarks\n\n- page 4, line 2: I guess \\mathscr P X should be replaced by \\mathscr P(\\mathscr X)\n\n- line -2 of section 3.1: should d/kS_k^2 be understood as (d/k)S_k^2? Please add parentheses to avoid any possible misunderstanding. \n\n- Eq 6 is not clear at all. The sentence that follows this equation does not really clarify it. There is not d_X in (6), why the sentence after (6) contains d_X ? Omega is supposed to be a mapping (in order that the push-forward of mu by Omega be well defined) but it is defined as a set of matrices? What is the power 1/2 of Omega?\n\n- Page 5, paragraph starting with \"For the second problem...\": Is there any guarantee that the procedure of renormalization of the linear layers described in this paragraph somehow approximates the projection of the mapping onto the set of 1-Lipschitz maps ? Furthermore, I guess that it is necessary to stress that the activation function should be 1-Lipschitz as well. \n\n- Page 6: \"It has been previously shown that [...] the Lipschitz constant of a fully connected layer is given by the spectral norm of the weights\". I suggest removing the words \"It has been previously shown that [...] \" since if I am not mistaken, this is just the definition of the spectral norm. \n\n- Page 6: \"in order to project back into the space of constraints we need to\nnormalize each layer’s weights with the spectral norm\"   I am not sure that \"we need to\" is appropriate here. It might very well happen that some of the linear layers have a spectral norm larger than 1 but the resulting NN is 1-Lipschitz.\nI recommend replacing \"we need to\" by \"we sggest to\".\n\n- Should we understand that the first paragraph of section 5.1 relates to section 5.2 as well? If yes, please move it before section 5.1. If not, please provide more details on the experimental setting of section 5.2.\n\n- Section 5.2: The number of weights depends on the dimension d. Therefore, the computation of the gradient wrt phi requires a running time that is an increasing function of d. Furthermore, the projection onto the space of 1-Lipschitz functions is done by computing the spectral norm of a matrix of dimension qxd, where q is the number of units in the hidden layer. If k<d and power method is used for computing this norm, it involves at least k^2*d computations. It is therefore not clear why the authors insist on the fact that the \"the time to compute SD_phi is constant in dimension\", while what really counts is the overall computational cost of the method. On a related note, in Fig 4, it would be more relevant to show the running time of the algorithm and not just the time of computing SD_phi for a given phi.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Oi5lrxPp8V", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "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": "\nThis paper uses the fact that the Wasserstein distance is decreasing under 1-Lipschitz mappings from the ambient space to a feature space in order to propose more robust (to dimensionality ?) estimation of the Wasserstein distance between two probability distributions. A neural network with some sort of weight renormalization is used to produce 1-Lipschitz embeddings. The authors then maximise over the parametrized maps.\n\nThe paper is not well-written and is sometimes simply wrong in my understanding. For instance, the second sentence of the abstract mention that « they scale cubically », « they » is not defined and the curse of dimensionality in optimal transport is not related to cubic scaling. My opinion is that the authors misunderstood the curse of dimensionality in optimal transport which is related to the statistical estimation of the Wasserstein distance (that is the convergence when increasing the number of samples is quite slow).\n\nThe model and its instantiation are quite obvious; a generalization of linearly projected optimal transport (Paty, Cuturi).\nOn the optimization side, the problem once parametrized is non-convex and was probably already non convex on the space of Lipschitz mappings. Comments on these points are of interest. In other words, how hard is the optimization problem introduced by the authors?\n\nExperiments lack a clear motivation and the synthetic experiments are not particularly illuminating. In fact, it is difficult to clearly state the problem addressed in this paper.\n\nIn the algorithm, proj^\\lampda_{1 - Lip} is not defined.\n\nMinor remarks: \n— f_\\phi instead of f_phi on page 6.\n— page 8: « projects » projections\n— page 5: « Both problems already have solutions which are going to re-use » we are going?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for their submission. The paper feels more like an early draft, with several fundamental factual mistakes (mistake on computational and statistical complexities) as highlighted by the reviewers. There's plenty of material in the reviews to help authors improve their submission, we encourage them to use these recommendations to improve motivation / experiments.
Decision: Reject