PaperlayerView exact revision on arXiv

Source-linked AI summary

A Geometric View of Optimal Transportation and Generative Model

Na Lei, Kehua Su, Li Cui, Shing-Tung Yau, David Xianfeng Gu

arXiv:1710.05488v2cs.LGstat.ML

TL;DR

The paper examines how convex-geometric problems connect to optimal transportation maps, especially for L2 cost. It relates Wasserstein potentials to those maps and reports that its geometric method outperforms WGAN in a Gaussian-mixture experiment.

  • Problem

    The paper examines how Minkowski and Alexandrov problems in convex geometry connect to optimal transportation maps, especially for L2 cost.

    Source: §4 · p. 7

  • Method

    It relates the Wasserstein potential to the optimal transportation map, with a closed-form relation for costs such as Lp distance when p > 1.

    Source: §8 · p. 20

  • Results

    In the reported two-cluster Gaussian-mixture experiment, the geometric method outperforms WGAN, whose generated samples tend to lie between the Gaussians.

    Source: §7.1 · p. 18

  • Takeaways & Limitations

    Because g0 and g1 generate the same distribution, using g0 avoids the added complexity of s and is more efficient than double training.

    Source: §8 · p. 21

    In high-dimensional settings, rigorous computational geometry for computing the optimal transportation map is intractable because it requires maintaining complex geometric data structures.

    Source: §8 · p. 21

Abstract

from arXiv · show

In this work, we show the intrinsic relations between optimal transportation and convex geometry, especially the variational approach to solve Alexandrov problem: constructing a convex polytope with prescribed face normals and volumes. This leads to a geometric interpretation to generative models, and leads to a novel framework for generative models. By using the optimal transportation view of GAN model, we show that the discriminator computes the Kantorovich potential, the generator calculates the transportation map. For a large class of transportation costs, the Kantorovich potential can give the optimal transportation map by a close-form formula. Therefore, it is sufficient to solely optimize the discriminator. This shows the adversarial competition can be avoided, and the computational architecture can be simplified. Preliminary experimental results show the geometric method outperforms WGAN for approximating probability measures with multiple clusters in low dimensional space.

1 Introduction

The introduction recasts GANs through optimal mass transportation, linking the generator to a transportation map and the discriminator to a Kantorovich potential. It connects these roles to convex geometry and proposes deriving the generator directly from the discriminator for suitable costs.

1 Introduction

  • In WGAN, the generator maps latent samples toward the data distribution while the discriminator estimates Wasserstein distance through a Kantorovich potential, and they train alternately.The generator pushes the latent distribution forward into image space.Source: §1 · p. 2
  • For L2 transportation cost, the optimal transportation map is equivalent to constructing a convex polytope with prescribed normals and face volumes.The resulting generating map can be found by convex optimization, including Newton’s method with explicit geometric meaning.Source: §1 · p. 3
  • For costs c(x, y) = h(x−y) with strictly convex h, the optimal generator can be written explicitly once the optimal discriminator is obtained, making adversarial competition unnecessary.The proposed relation makes one of the two deep networks and its training process redundant.Source: §1 · p. 3
  • The paper proposes a generative framework that constructs the optimal transportation map geometrically and reports preliminary proof-of-concept experiments.The experiments are described as preliminary rather than a full benchmark evaluation.Source: §1 · p. 3

2 Optimal Transportation View of GAN

This section frames WGAN as estimating a Wasserstein distance between a generated and an empirical data distribution. The generator defines a latent-to-image map, while the discriminator approximates the Kantorovich potential used in the dual formulation.

2 Optimal Transportation View of GAN

  • The data distribution is represented empirically, and the generator maps a fixed latent distribution into image space to define the generated distribution.The latent space is specified as much lower dimensional than the ambient image space.Source: §2 · p. 4
  • The section formulates the gradient of the dual energy with respect to generator parameters and notes that the discrete optimization over {ψi} can use stochastic gradient descent.The passage attributes the stochastic-gradient approach to.Source: §2 · p. 4
  • WGAN’s discriminator approximates the Kantorovich potential in the dual formulation of the transportation problem.For discrete data, the continuous potential can be replaced by a discrete vector.Source: §2 · p. 4
  • The WGAN generator produces the decoding map and the discriminator estimates the potential through alternating training.For the stated distance cost, the c-transform is −ϕξ when ϕξ is 1-Lipschitz.Source: §2 · p. 4

3 Optimal Mass Transport Theory

Optimal mass transport formulates measure-preserving movement as a cost-minimization problem and admits a Kantorovich dual formulation. Brenier’s theory connects the optimal map to convex potentials, while Theorem 3.7 relates the map to the Kantorovich potential for strictly convex difference costs.

3 Optimal Mass Transport Theory

  • The Monge problem seeks a measure-preserving map minimizing transport cost, while the Kantorovich relaxation represents transport by a joint plan with prescribed marginals.The plan minimizes total cost among suitable plans; its projections recover µ and ν.Source: §3 · p. 5, §3.1 · p. 5

3.2 Kontarovich Dual Formulation

  • The Kantorovich problem is the dual formulation of the transport linear program, with ϕ named the Kantorovich potential and cost-dependent transforms.For L1 cost, a 1-Lipschitz potential satisfies ϕc = −ϕ; for L2 cost, the c-transform relates to the Legendre transform.Source: §3.2 · p. 6

3.3 Brenier’s Approach

  • For quadratic Euclidean cost, Brenier’s theorem identifies the optimal map as the gradient of a convex function and states that the map is unique.The theorem assumes an absolutely continuous source measure and finite second moments for both measures.Source: §3.3 · p. 6
  • For costs c(x, y) = h(x − y) with strictly convex h, Theorem 3.7 represents the optimal map using the Kantorovich potential, under stated regularity conditions.The optimal plan is unique and of the form (id, T#)µ when µ is absolutely continuous and ∂Ω is negligible.Source: §3.3 · p. 7

4 Convex Geometry

The section connects optimal transport with convex geometry through Alexandrov’s polytope problem and its power-diagram representation. It also presents a variational route to solving that problem with Newton’s method.

4 Convex Geometry

  • For L2 transportation cost, the optimal map has a geometric interpretation through constructing a convex polytope with prescribed normals and face volumes.The section connects this construction to the Monge-Ampère equation.Source: §4 · p. 7

4.1 Alexandrov’ Theorem

  • Minkowski and Alexandrov problems prescribe polytope face normals and volumes, and the variational approach to Alexandrov’s problem represents the polytope through a convex function.The graph of the piecewise linear convex function is a convex polytope whose projection induces a cell decomposition.Source: §4.1 · p. 8

4.2 Power Diagram

  • Alexandrov’s problem can be solved using a power diagram, whose cells are convex polytopes and whose dual structure is a weighted Delaunay triangulation.The section describes the optimal transport map as mapping each power cell to its corresponding site.Source: §4.1 · p. 9, §4.2 · p. 10

4.3 Convex Optimization

  • Solving Alexandrov’s problem amounts to solving a discrete Monge-Ampère equation, and the energy can be optimized directly with classical Newton’s method.The section relates the energy gradient and Hessian to power-diagram geometry.Source: §4.3 · p. 11

5 Semi-discrete Optimal Mass Transport

The semi-discrete setting turns transport to a discrete target into a partition of the source domain. For quadratic cost, the Kantorovich dual and Brenier approaches are equivalent at the optimum.

5 Semi-discrete Optimal Mass Transport

  • A compact convex source domain and discrete target measure define the semi-discrete transport setting, with source cells assigned to target points.The cells are defined by comparing cost-to-target values adjusted by discrete Kantorovich potentials.Source: §5 · p. 11, §5.1 · pp. 11–12

5.1 Kantorovich Dual Approach

  • With discrete Kantorovich weights, the dual approach partitions the source into cells and optimizes an energy over those weights.Each cell contains points for which its adjusted transport cost is no greater than the corresponding costs for other target points.Source: §5.1 · pp. 11–12

5.2 Brenier’s Approach

  • For quadratic cost, Brenier heights yield a convex polyhedral potential whose gradient maps each cell to its target point while matching prescribed cell masses.The height vector is unique up to an additive constant under the stated mass condition.Source: §5.2 · pp. 12–13

5.3 Equivalence

  • Infinitesimal changes to cell weights are associated with mass changes in the cells sharing their boundary.For a shared boundary between cells i and j, the passage relates the corresponding mass changes with opposite signs.Source: §5.3 · p. 14
  • At the optimum, the Kantorovich and Brenier approaches are equivalent, and the dual energy equals the transportation cost.The paper also relates the two potentials at the optimum.Source: §5.3 · p. 15

6 Geometric Generative Model

The proposed geometric generative framework separates encoding and decoding from probability-measure transformation. It uses an optimal transport map in latent space before decoding samples back to the data space.

6 Geometric Generative Model

  • The framework separates encoding and decoding from probability-measure transformation, combining the generator and discriminator processes in a geometric model.Encoding maps data to latent space; decoding maps latent samples back to the image space.Source: §6 · p. 15
  • The method focuses on transforming a fixed latent distribution ζ into the encoded data distribution µ using a map T.The paper notes that encoding and decoding can use existing methods such as VAE.Source: §6 · pp. 15–16
  • The optimal latent transport map is the gradient of a Brenier potential and can be constructed with a power diagram before decoding.Composing the transport map with the decoding map transforms ζ into the empirical distribution in image space.Source: §6 · p. 16

7 Experiments

In the two-Gaussian experiment, the geometric method outperforms WGAN, whose generated samples tend to fall between the modes. A second experiment applies the geometric approach to sampling on a surface with complicated geometry.

7.1 Comparison with WGAN

  • After 1,000 iterations, WGAN-generated points tend to lie between the two Gaussians rather than capture the mixture.The experiment uses 128 real samples from two Gaussian distributions and 128 generated samples.Source: Figure 8 · p. 17, §7.1 · p. 18
  • The geometric method outperforms WGAN on the two-cluster Gaussian mixture, and its equal-area cells push the uniform input to the exact empirical distribution.The paper describes this as a preliminary experiment; the cell-to-sample correspondence is shown in the geometric-method visual.Source: Figure 9 · p. 17, §7.1 · p. 18

7.2 Geometric Method

  • The surface experiment maps a complicated 3D data manifold to a planar latent disk, then uses optimal transport to generate samples on the surface.The encoding uses discrete surface Ricci flow, and the authors describe direct sampling from the encoded surface as highly non-uniform.Source: §7.2 · pp. 18–19
  • Applying the transport-adjusted sampling procedure yields the paper’s illustrated generated distribution on the surface.Figures 10 and 11 illustrate the geometric model and generated distributions.Source: §7.2 · p. 19, Figure 10 · p. 19, Figure 11 · p. 20

8 Discussion and Conclusion

The discussion connects the discriminator’s Kantorovich potential and generator’s transportation map, arguing that optimal transportation can remove the need to train both. It also identifies high-dimensional computation and large-scale implementation as boundaries for the geometric method.

8 Discussion and Conclusion

  • For Lp costs with p > 1, the Kantorovich potential and transportation map have a closed-form relation, so training one of them is sufficient.The discussion frames the discriminator as computing the potential and the generator as calculating the transportation map.Source: §8 · p. 20
  • Even when a general cost lacks an explicit potential–map relation, Brenier factorization gives g1 = g0 ◦s with s preserving ζ, so g0 yields the same distribution without double training.The authors say the added complexity of s makes finding g1 harder, with no difference in whole-system performance.Source: §8 · pp. 20–21
  • In high dimensions, rigorous computational geometry for the optimal map is intractable because it requires maintaining complex geometric data structures.The authors list socialistic, sliced, and hierarchical optimal transportation methods as alternatives for high-dimensional settings.Source: §8 · p. 21
  • Large-scale implementation of the proposed model remains future work.The authors say they will explore this direction and implement the model at large scale.Source: §8 · p. 21

Appendix

The appendix points readers to a diagram of relations among geometric and functional objects and includes a symbol list.

8.1 Commutative Diagram

  • The commutative diagram summarizes relations among geometric and functional objects, with adjacent layers described as commutable.The text also directs readers to Figure 4 to observe these relations.Source: §8.1 · p. 21

8.2 Symbol list

Loading 1710.05488v2…