2019

2-Wasserstein Approximation via Restricted Convex Potentials with Application to Improved Training for GANs

Taghvaei, Amirhossein, Jalali, Amin

Understand

We provide a framework to approximate the 2-Wasserstein distance and the optimal transport map, amenable to efficient training as well as statistical and geometric analysis.

With the quadratic cost and considering the Kantorovich dual form of the optimal transportation problem, the Brenier theorem states that the optimal potential function is convex and the optimal transport map is the gradient of the optimal potential function.
Using this geometric structure, we restrict the optimization problem to different parametrized classes of convex functions and pay special attention to the class of input-convex neural networks.
We analyze the statistical generalization and the discriminative power of the resulting approximate metric, and we prove a restricted moment-matching property for the approximate optimal map.

Built on

The speed of mean Glivenko–Cantelli convergence
R. Dudley · 1969
Earlier work this paper cites.
Minkowski-type theorems and least-squares clustering
F. Aurenhammer, F. Hoffmann, and B. Aronov · 1998
Earlier work this paper cites.
Mass Transportation Problems: Volume I: Theory , volume 1
S. T. Rachev and L. Rüschendorf · 1998
Earlier work this paper cites.
A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem
J.-D. Benamou and Y. Brenier · 2000
Earlier work this paper cites.
Fast image retrieval via embeddings
P. Indyk and N. Thaper · 2003
Earlier work this paper cites.
Topics in optimal transportation
C. Villani · 2003
Earlier work this paper cites.
Convex optimization
S. Boyd and L. Vandenberghe · 2004
Earlier work this paper cites.
Least angle regression
B. Efron, T. Hastie, I. Johnstone, R. Tibshirani, et al · 2004
Earlier work this paper cites.
Gradient flows: in metric spaces and in the space of probability measures
L. Ambrosio, N. Gigli, and G. Savaré · 2008
Earlier work this paper cites.
CVX: Matlab software for disciplined convex programming, 2008
M. Grant, S. Boyd, and Y. Ye · 2008
Earlier work this paper cites.
Fixed-point continuation for ℓ 1 \ell_{1} -minimization: Methodology and convergence
E. T. Hale, W. Yin, and Y. Zhang · 2008
Earlier work this paper cites.
Approximate earth mover’s distance in linear time
S. Shirdhonkar and D. W. Jacobs · 2008
Earlier work this paper cites.
A general duality theorem for the Monge–Kantorovich transport problem
Original
M. Beiglböck, C. Léonard, and W. Schachermayer · 2009
Earlier work this paper cites.
A gradient descent solution to the Monge–Kantorovich problem
R. Chartrand, B. Wohlberg, K. Vixie, and E. Bollt · 2009
Earlier work this paper cites.
Texture mapping via optimal mass transport
A. Dominitz and A. Tannenbaum · 2010
Earlier work this paper cites.
Semidefinite representation of convex sets
J. W. Helton and J. Nie · 2010
Earlier work this paper cites.
Bayesian inference with optimal maps
T. A. El Moselhy and Y. M. Marzouk · 2012
Earlier work this paper cites.
Sparse/robust estimation and Kalman smoothing with nonsmooth log-concave densities: Modeling, computation, and theory
A. Y. Aravkin, J. V. Burke, and G. Pillonetto · 2013
Earlier work this paper cites.
Sinkhorn distances: Lightspeed computation of optimal transport
M. Cuturi · 2013
Earlier work this paper cites.
A nonparametric ensemble transform method for Bayesian inference
S. Reich · 2013
Earlier work this paper cites.
A proximal-gradient homotopy method for the sparse least-squares problem
L. Xiao and T. Zhang · 2013
Earlier work this paper cites.

Similar

DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization
A. A. Ahmadi and A. Majumdar · 2014
Cited alongside, same era.
Regularized discrete optimal transport
S. Ferradans, N. Papadakis, G. Peyré, and J.-F. Aujol · 2014
Cited alongside, same era.
Sliced and Radon Wasserstein barycenters of measures
N. Bonneel, J. Rabin, G. Peyré, and H. Pfister · 2015
Cited alongside, same era.
Gibbs flow for approximate transport with applications to Bayesian computation
Original
J. Heng, A. Doucet, and Y. Pokern · 2015
Cited alongside, same era.
Optimal transportation with capacity constraints
J. Korman and R. McCann · 2015
Cited alongside, same era.
Optimal mass transport for shape matching and comparison
Z. Su, Y. Wang, R. Shi, W. Zeng, J. Sun, F. Luo, and X. Gu · 2015
Cited alongside, same era.
On the Monge–Kantorovich problem with additional linear constraints
D. A. Zaev · 2015
Cited alongside, same era.
Stochastic optimization for large-scale optimal transport
A. Genevay, M. Cuturi, G. Peyré, and F. Bach · 2016
Cited alongside, same era.
Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge–Ampère equations
X. Gu, F. Luo, J. Sun, and S.-T. Yau · 2016
Cited alongside, same era.
f-GAN: Training generative neural samplers using variational divergence minimization
S. Nowozin, B. Cseke, and R. Tomioka · 2016
Cited alongside, same era.
Wasserstein continuity of entropy and outer bounds for interference channels
Y. Polyanskiy and Y. Wu · 2016
Cited alongside, same era.
Stabilized sparse scaling algorithms for entropy regularized transport problems
Original
B. Schmitzer · 2016
Cited alongside, same era.

Then

Smooth and sparse optimal transport
M. Blondel, V. Seguy, and A. Rolet · 2018
Later among the works it cites.
Learning Wasserstein embeddings
N. Courty, R. Flamary, and M. Ducoffe · 2018
Later among the works it cites.
Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm
P. Dvurechensky, A. Gasnikov, and A. Kroshnin · 2018
Later among the works it cites.
Quadratically regularized optimal transport on graphs
M. Essid and J. Solomon · 2018
Later among the works it cites.
A convex duality framework for GANs
F. Farnia and D. Tse · 2018
Later among the works it cites.
Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under wasserstein distance
Y. Han, J. Jiao, and T. Weissman · 2018
Later among the works it cites.
A geometric view of optimal transportation and generative model
N. Lei, K. Su, L. Cui, S.-T. Yau, and X. D. Gu · 2018
Later among the works it cites.
Notions of optimal transport theory and how to implement them on a computer
B. Lévy and E. L. Schwindt · 2018
Later among the works it cites.
Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
Original
J. Liu, W. Yin, W. Li, and Y. T. Chow · 2018
Later among the works it cites.
A distributed framework for the construction of transport maps
Original
D. A. Mesa, J. Tantiongloc, M. Mendoza, and T. P. Coleman · 2018
Later among the works it cites.
Computational optimal transport
Original
G. Peyré and M. Cuturi · 2018
Later among the works it cites.
Uncoupled isotonic regression via minimum Wasserstein deconvolution
Original
P. Rigollet and J. Weed · 2018
Later among the works it cites.
Improving GANs using optimal transport
Original
T. Salimans, H. Zhang, A. Radford, and D. Metaxas · 2018
Later among the works it cites.
Large-scale optimal transport and mapping estimation
V. Seguy, B. B. Damodaran, R. Flamary, N. Courty, A. Rolet, and M. Blondel · 2018
Later among the works it cites.
Wasserstein auto-encoders
I. Tolstikhin, O. Bousquet, S. Gelly, and B. Schoelkopf · 2018
Later among the works it cites.
Improving the improved training of Wasserstein GANs: A consistency term and its dual effect
Original
X. Wei, B. Gong, Z. Liu, W. Lu, and L. Wang · 2018
Later among the works it cites.
On the discrimination-generalization tradeoff in GANs
P. Zhang, Q. Liu, D. Zhou, T. Xu, and X. He · 2018
Later among the works it cites.
Mode collapse and regularity of optimal transportation maps
Original
Y. Guo, D. An, X. Qi, Z. Luo, S.-T. Yau, X. Gu, et al · 2019
Closest in time.
W2GAN: Recovering an optimal transport map with a GAN, 2019
L. Jacob*, J. She*, A. Almahairi, S. Rajeswar, and A. Courville · 2019
Closest in time.
Wasserstein proximal of GANs, 2019
A. T. Lin, W. Li, S. Osher, and G. Montufar · 2019
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…