PaperlayerView exact revision on arXiv

Source-linked AI summary

Extremal Domain Translation with Neural Optimal Transport

Milena Gazdieva, Alexander Korotin, Daniil Selikhanovych, Evgeny Burnaev

arXiv:2301.12874v3cs.LG

TL;DR

Unpaired translation has no specified source–target correspondences, while often seeking outputs similar to their inputs. This paper defines extremal transport and approximates its maps through incomplete transport; its theoretical results connect ET maps to nearest neighbors and IT costs converge to ET costs as w increases.

  • Problem

    Unpaired translation lacks known correspondences between source and target samples, leaving multiple suitable maps and motivating similarity-preserving outputs.

    Source: §1 · p. 2

  • Method

    The paper defines extremal transport as a constrained similarity-optimal translation and approximates its maps through incomplete transport as w increases.

    Source: §3.1 · p. 3, §3.2 · p. 5

  • Results

    ET maps send almost every source point to a nearest neighbor in the target support, and IT costs converge to ET costs as w tends to infinity.

    Source: §3.1 · p. 4, §3.3 · p. 6

  • Takeaways & Limitations

    ET plans can be interpreted as stochastic nearest-neighbor assignments from source probability mass to the target support.

    Source: §3.1 · p. 5

    A stronger convergence result for approximating ET plans with finite-w IT plans remains an open theoretical question.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

In many unpaired image domain translation problems, e.g., style transfer or super-resolution, it is important to keep the translated image similar to its respective input image. We propose the extremal transport (ET) which is a mathematical formalization of the theoretically best possible unpaired translation between a pair of domains w.r.t. the given similarity function. Inspired by the recent advances in neural optimal transport (OT), we propose a scalable algorithm to approximate ET maps as a limit of partial OT maps. We test our algorithm on toy examples and on the unpaired image-to-image translation task. The code is publicly available at https://github.com/milenagazdieva/ExtremalNeuralOptimalTransport

1 Introduction

Unpaired translation lacks known source–target correspondences, so multiple translations may be suitable. The paper formulates extremal transport to seek the most similar output that still lies in the target domain.

1 Introduction

  • Unpaired translation is ambiguous because available source and target samples have no given correspondence, allowing multiple suitable maps.The task maps source samples into the target domain, typically with a neural network.Source: §1 · pp. 1–2
  • Extremal transport (ET) formalizes the theoretically best unpaired translation with respect to a specified similarity function.The paper also characterizes ET maps and plans through nearest neighbors.Source: §1 · p. 2
  • The proposed scalable algorithm approximates ET maps as a limit of incomplete transport maps, using a duality formula for efficient computation.The authors test it on toy examples and unpaired image translation.Source: §1 · p. 2

2 Background on Optimal Transport

Optimal transport minimizes a cost while matching source and target distributions. The background distinguishes deterministic transport maps, possibly nonexistent minimizers, mass-splitting transport plans, and partial transport with inequality constraints.

2 Background on Optimal Transport

  • Monge OT minimizes transport cost over maps that push the source distribution P to the target Q.A minimizer, when it exists, is called an OT map.Source: §2 · p. 2
  • Because a minimizing map may not exist, Kantorovich relaxation optimizes over transport plans with source and target marginals P and Q.Plans allow splitting the mass of an input point; under mild assumptions, the plan and map costs coincide.Source: §2 · pp. 2–3
  • Partial OT uses inequality constraints on transported source and target mass, so the matched fractions are part of the optimization.When the transported mass equals both input masses, the constraints reduce to the standard OT equalities.Source: §2 · p. 3

3 Main Results

The paper defines extremal transport (ET) as minimum-cost translation into the target distribution’s support, then links it to incomplete transport (IT), whose plans converge toward ET plans as its weight grows. It also derives a neural saddle-point approach for computing IT maps.

3.1 Extremal Transport Problem

  • ET requires translated mass to lie in the target distribution’s support, rather than requiring the translated distribution to equal the target distribution.The infimum is unchanged if the target measure is replaced by another measure with the same support.Source: §3.1 · pp. 3–4
  • An ET map exists and sends almost every source point to one of its nearest neighbors in the target support.ET plans may also split each source point’s mass among its nearest neighbors, and their cost equals the ET-map cost.Source: §3.1 · pp. 4–5

3.2 Incomplete Transport Problem

  • IT replaces ET’s support constraint with the finite-weight constraint T♯P ≤ wQ, and increasing w gives maps more ways to redistribute source mass across the target support.At w = 1, Kantorovich IT coincides with standard OT; as w tends to infinity, IT approaches ET.Source: §3.2 · p. 5
  • In compact Euclidean settings with atomless P, Monge and Kantorovich IT costs coincide, and a Kantorovich IT minimizer exists.The corresponding Monge infimum is not guaranteed to be attained, even in the Euclidean case.Source: §3.2 · p. 5

3.3 Link between Incomplete and Extremal Transport

  • As the IT weight w grows, its costs converge to the ET cost, and weak-* convergent subsequences of IT plans converge to ET plans.For sufficiently large w, every IT plan is within any prescribed ε of an ET plan in W1, although different subsequences may converge to different ET plans.Source: §3.3 · p. 6

3.4 Computational Algorithm for Incomplete Transport

  • The computational method solves an IT saddle-point problem, where the non-positive potential f acts as a multiplier for the constraint T♯P − wQ ≤ 0.The map and potential are approximated with neural networks trained on random batches using stochastic gradient ascent-descent.Source: §3.4 · pp. 6–7

4 Related work

Neural OT work learns maps or plans through saddle-point objectives, while other approaches compute only OT costs or address specific formulations. Unlike prior map-learning methods that enforce equality constraints, this approach permits partial alignment; related image-translation methods use similarity losses, but IT achieves better input-output similarity in the reported experiments.

Neural optimal transport

  • Unlike related neural OT map-learning methods that enforce T♯P = Q, this approach uses T♯P ≤wQ to allow partial alignment.Other neural OT approaches mentioned either compute OT costs rather than maps or solve specific formulations such as entropic OT.Source: §4 · p. 7

Image translation

  • IT achieves better input-output similarity than CycleGAN and StarGAN-v2, including modified variants designed to better preserve image content.The paper frames these image-translation methods as related work because they use additional similarity losses.Source: §4 · p. 8

5 Evaluation

Toy experiments illustrate how the weight w controls the target mass captured by incomplete transport maps. In image translation, IT better preserves input-output similarity than popular comparison methods, while increasing w makes outputs more input-like and raises FID as maps cover less of the target distribution.

5 Evaluation

  • The evaluation covers toy 2D examples and unpaired image-to-image translation, with squared ℓ2 cost and perceptual-cost experiments provided in the appendix.The code is publicly available and technical training details are provided in Appendix E.Source: §5 · p. 8, §5.1 · p. 8

5.1 Toy 2D experiments

  • In the Wi-Fi toy experiment, w = 1 captures all three target arcs, w = 3/2 captures two (about 2/3 of Q), and w = 3 captures one (about 1/3).The Accept example with w = 2 captures the one text line closest to P in ℓ2.Source: §5.1 · p. 8

5.2 Unpaired Image-to-image Translation

  • The evaluation tests image pairs from publicly available datasets containing 5K–500K samples, using 64 × 64 and 128 × 128 images and a 90%/10% train-test split.The experiments include faces, anime, comics, handbags, shoes, textures, and chairs.Source: §5.2 · p. 9
  • Increasing w changes image attributes toward the input: colors in face and handbag translations, facial characteristics, and chair size under pixel-wise ℓ2 cost.Handbag-to-shoes PCA projections move closer to P as w increases; at w = 1 they are close to Q.Source: §5.2 · p. 9
  • As w increases, translated images become more similar to their inputs by ℓ2, while FID increases as IT maps cover a smaller part of Q.The authors state that visual quality does not decrease, and caution that FID is not representative when w > 1.Source: §5.2 · p. 9
  • IT better preserves input-output similarity than CycleGAN and StarGAN-v2, including modified variants, in the reported image-translation experiments.The evaluation uses squared ℓ2 cost and reports test ℓ2 cost and FID for learned IT maps.Source: §5 · p. 8, Table 1 · p. 9, §5.2 · p. 10

6 Potential Impact

The paper identifies inequality constraints as a possible direction for generative models and discusses potential applications of incomplete transport in partial OT, generative nearest neighbors, and robustness. These are prospective uses, including a possible target-data outlier score.

Inequality constraints for generative models

  • The work demonstrates applying inequality constraints such as T♯P ≤wQ to a large-scale problem, where generative-model objectives commonly enforce equality constraints such as T♯P = Q.The paper primarily studies image-to-image translation and describes further applications as prospects for improvement.Source: §6 · p. 10

Partial OT

  • Incomplete transport may help control mass distribution in partial OT problems, including applications to biological single-cell data that currently use unbalanced OT.The authors note that soft mass control in unbalanced OT may make the mass distribution hard to control.Source: §6 · p. 10

Generative nearest neighbors

  • For w → ∞, IT is presented as a theoretically justified way to learn approximate nearest-neighbor maps from samples, including possible use with latent vectors from generative models.The paper suggests this as a potential application, alongside existing OT methods for latent spaces.Source: §6 · p. 10

Robustness and outlier detection

  • IT may support robustness by aligning P with only part of Q, with the cost c(x, y) and weight w tuning which target outliers are excluded.The potential f*(y) vanishes on target-support samples that are not transported, making it a possible outlier score.Source: §6 · p. 10

A Limitations

The limitations concern the choice of similarity cost, possible degeneracy or immobility of extremal maps, and practical constraints in training and evaluation. The method also approximates potentially non-deterministic plans with deterministic maps, and its optimization may exhibit fake solutions and instabilities.

Transport costs

  • The experiments use ℓ2 costs, while semantically meaningful image costs such as perceptual distance remain a future research direction.The theoretical results hold for any continuous cost function.Source: A Limitations · p. 15

Intersecting supports

  • When source and target supports intersect and the cost is minimized at x = y, an ET plan can leave the intersecting mass unmoved.For c = ℓ2, the ET plan may be the identity on Supp(P) ∩ Supp(Q).Source: A Limitations · p. 15

Limited diversity

  • ET and IT maps can be degenerate: in the texture-to-chair example, increasing w yields fewer small chairs and only armchairs at w = 8.The paper attributes this shift to armchairs being closer to textures in ℓ2 because they have less white background.Source: A Limitations · p. 15

Unused samples

  • As w increases, training slows; samples in Q outside the mapped region can become non-informative, potentially requiring larger training datasets.The authors connect the non-informative samples to Proposition 4.Source: A Limitations · p. 15, Figure 11 · p. 15

Limited quantitative metrics

  • The experiments use limited quantitative metrics because FID and similar unpaired metrics test T♯P = Q, which partial maps violate by construction.The paper offers transport cost and explanatory metrics, while identifying quality metrics for partial generative models as future work.Source: A Limitations · p. 16

Inexistent IT maps

  • Actual IT plans may be non-deterministic, but the approach learns deterministic maps; the paper says such maps can approach IT cost arbitrarily well.Adding noise to the generator is suggested as a way to learn stochastic plans, though it may ignore the noise [43, M5.1].Source: A Limitations · p. 16

Fake solutions and instabilities

  • Lagrangian objectives may have fake optimal saddle points whose T is not an OT map, potentially contributing to training instabilities.The paper notes that strictly convex weak cost functions can remove fake solutions.Source: A Limitations · p. 16

Potential societal impact

  • Generative models may support applications such as style translation, but can also be used to create fake faces.The authors mention outlier detection as a possible new direction for neural OT use.Source: A Limitations · p. 16

B Toy 2D Illustrations of Other Methods

The toy experiments compare GAN and unbalanced OT methods with partial OT on Wi-Fi, then test whether other methods can isolate the text Accept. The alternatives can direct mass to unintended target regions or fail to produce the desired translation.

Wi-Fi

Accept

C Comparison with Other Image-to-Image Translation Methods

The comparison examines how similarity-weighted GAN objectives trade target-domain fit against input-output similarity, and contrasts them with IT's constrained transport objective. Across the reported image-translation comparisons, increasing GAN similarity weights can lower transport cost while degrading visual quality or causing translation failures, whereas IT provides better similarity without the same quality decrease.

Experimental setup

Results and discussion (CycleGAN)

  • For CycleGAN, larger λ lowers transport cost but can make outputs practically useless; at acceptable visual quality, its cost exceeds standard OT, and IT's w = 8 result is unachievable.With very large λ, CycleGAN learns the identity map; in most cases, IT also has smaller FID than CycleGAN.Source: C Comparison with Other Image-to-Image… · p. 18, Figure 14 · p. 19

Results and discussion (StarGAN-v2)

  • For StarGAN-v2 on handbags-to-shoes, λ ≥ 10 can leave handbags nearly unchanged, while λ = 10 still yields a low FID despite frequent translation failures.The authors note that FID can give misleading estimates in this case, while IT does not show this issue on the same image set.Source: C Comparison with Other Image-to-Image… · p. 18, Figure 14 · p. 19

Concluding remarks

  • IT with increasing w improves input-output similarity without the image-quality decrease seen as GAN similarity weight λ grows.The paper frames IT as enforcing a transport constraint rather than balancing multiple loss terms.Source: C Comparison with Other Image-to-Image… · p. 19
  • GAN objectives combine realism and similarity losses whose different minima create a trade-off between target-domain fit and input-output similarity.The paper says this issue applies generally to GAN-based methods, with differences mainly in architectures or added losses.Source: C Comparison with Other Image-to-Image… · pp. 17, 19
  • IT enforces T♯P ≤wQ through a learned potential and minimizes transport cost among admissible maps, rather than summing realism and similarity losses.When w → ∞, the reported FID decrease reflects covering less of Q, not lower image quality.Source: C Comparison with Other Image-to-Image… · p. 19

D Relation and Comparison with Discrete Partial OT Methods

Discrete partial OT plans are learned on finite training samples, and barycentric projections provide a possible route to neural maps for unseen inputs. In the evaluated CelebA→anime comparison, this route performs poorly relative to the paper’s method.

D Relation and Comparison with Discrete Partial OT Methods

  • Discrete OT matches empirical distributions, so barycentric projection is used to learn a network that can map previously unseen inputs.The paper notes that discrete OT itself does not provide out-of-sample maps.Source: D Relation and Comparison with… · p. 19
  • As w increases, DOT+BP’s train-set averaging effect disappears, but its w = ∞ network generalizes poorly and produces insufficient-quality test images.The nearest-neighbor limit explains the train behavior, while test images remain poor for all weights.Source: D Relation and Comparison with… · pp. 21–22
  • DOT+BP produces poor-quality test images, with FID scores and ℓ2 costs much bigger than the paper’s method in all cases.The comparison covers the DOT+BP results in Table 7 and the paper’s method.Source: Table 7 · p. 21, D Relation and Comparison with… · p. 22
  • Using perceptual rather than MSE regression does not meaningfully improve DOT+BP, locating its poor performance in the barycentric-projection methodology rather than regression loss.Source: D Relation and Comparison with… · p. 22

E Experimental Details

The experiments use resized and augmented images, neural architectures selected by experiment type, and Adam optimization with a weight-dependent learning-rate schedule. Training duration and compute depend on image size and weight.

E Experimental Details

  • Image preprocessing rescales RGB channels to [-1, 1], resizes datasets to 64×64 or 128×128, and applies dataset-specific cropping and augmentation.Anime faces are first resized to 512×512 and center-cropped; textures receive random resized crops and horizontal and vertical flips.Source: E Experimental Details · p. 22
  • The transport map uses fully connected networks in M5.1 and a UNet in M5.2, while the potential uses a WGAN-QC ResNet with a non-positive output layer.Source: E Experimental Details · p. 22
  • Adam uses learning rate 10^-4, with MultiStepLR reductions scheduled according to weight w; image experiments gradually increase w during the first 20K potential iterations.The batch size for image translation is 64, with 10 inner transport-map iterations.Source: E Experimental Details · p. 22
  • Image experiments run about 40K iterations for 64×64 datasets and 70K for 128×128 datasets, while convergence time increases with w.Training takes 2 days at w = 1 up to 6 days at w = 8 on a single Tesla V100 GPU.Source: E Experimental Details · pp. 22–23
  • The authors provide experiment code and state that trained models will be provided in README.md.Source: E Experimental Details · p. 23

F Proofs

This section establishes the transport formulations’ existence, limiting behavior, and relationships among optimal transport plans, Kantorovich and Monge formulations, and the dual formulation. It also distinguishes the constrained saddle-point approach from related neural OT methods and reports a Swiss2Ball experiment examining how learned IT maps vary with the target-marginal bound.

F Proofs

  • Continuity of the cost gives a measurable pointwise minimizing selection, which makes the bound in Theorem 1 tight.The proof also derives continuity of the minimum cost function from uniform continuity of the cost.Source: F Proofs · p. 23
  • Weak-* compactness of the admissible plans and continuity of the cost ensure that the IT problem has a minimizing plan.The proof establishes compactness by showing that weak-* limits preserve the marginal and inequality constraints, then applies the extreme value theorem.Source: F Proofs · p. 24
  • The Kantorovich IT minimum equals the infimum in the Monge IT problem.The proof first identifies the IT plan as a minimizer for an OT problem, then uses approximate Monge maps to approach its cost.Source: F Proofs · p. 24
  • The IT cost is non-increasing and convex in the target-marginal bound, and converges to the perfect cost as that bound tends to infinity.The proof constructs an admissible plan whose cost is within any prescribed ε of the perfect cost for a sufficiently large bound.Source: F Proofs · pp. 24–25
  • As the target-marginal bound tends to infinity, a weak-* convergent subsequence of IT plans yields a perfect plan with cost equal to the perfect cost.The proof also checks that the limiting plan’s target support is contained in Supp(Q).Source: F Proofs · p. 26
  • On compact spaces, every sequence of IT plans with bounds tending to infinity has a subsequence converging in W1 to an ET plan.The proof uses weak-* subsequential convergence and the equivalence of weak-* and W1 convergence on compact spaces.Source: F Proofs · p. 26
  • The duality proof uses minimax and measure disintegration, and establishes that a non-positive continuous potential attains the dual supremum.It uses uniform equicontinuity and boundedness to obtain a uniformly convergent subsequence, then shows its limit attains the supremum.Source: F Proofs · pp. 27–28
  • Unlike related saddle-point methods for recovering optimal transport maps [61, Lemma 4.2], [24, Lemma 3], [43, Lemma 4], and [20, Theorem 2], the proposed formulation constrains f ≤ 0, and not every saddle point yields the IT map.The algorithm overlaps with standard maximin neural OT solvers but adds the constraint f ≤ 0 and multiplier w ≥ 1; Proposition 4 is described as a consequence of KKT complementary slackness.Source: F Proofs · p. 29

G.1 Comparison with the Closed-form Solution for ET

  • As w increases across {1, 3/2, 2, 32}, learned IT maps approach the closed-form ET map in the Swiss2Ball experiment.The source is a uniform Swiss roll and the target is a uniform ball of radius 0.5; their supports partially overlap. Table 8 reports MSE against the ground-truth ET map.Source: Figure 20f · p. 29, §G.1 · p. 29, Figure 20 · p. 29

G.2 Solving Fake Solutions Issue with Weak Kernel Cost

The appendix examines weak-kernel regularization for unstable IT training, tests perceptual transport cost, and reports larger-weight and additional ℓ2-cost results. The findings include a stability benefit with regularization and continued translation at larger weights.

G.2 Solving Fake Solutions Issue with Weak Kernel Cost

  • Kernel regularization improves IT stability in Ball2Circle, though at w = 32 its learned map has greater MSE from the ground-truth ET map than the unregularized map.Without regularization, training is highly unstable for w ∈ {1, 2}; regularization can introduce solution bias, and further study of fake solutions is out of scope.Source: Table 9 · p. 30, §G.2 · p. 31

G.3 Perceptual Cost

  • With perceptual transport cost, increasing w raises input-output similarity and lowers both perceptual and ℓ2 mean transport costs; FID is smaller than for IT trained with ℓ2 cost.Source: §G.3 · p. 31

G.4 Bigger Weight Parameters

  • At w = 16 and 32, IT continues translating faces to anime, unlike CycleGAN at large λ; mean transport costs decrease as w rises while FID increases slightly.The section reports quantitative results in Table 11 and additional qualitative results in Figure 24.Source: §G.4 · p. 31, Table 11 · p. 32

G.5 Additional Results for ℓ2 Cost

Loading 2301.12874v3…