Extremal Domain Translation with Neural Optimal Transport

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

Paper

References (78)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer 3fqr7/10 · confidence 3/52023-07-04

Summary

This paper presents a novel OT problem, extremal transport (ET), in the context of domain translation. The authors propose an incomplete transport (IT) problem as a surrogate optimization problem to obtain an approximate solution to the ET problem. The theoretical convergence between IT and ET costs (plans) is proven conditionally. The effectiveness of ET and IT is showcased through experiments on toy examples and public datasets, while also demonstrating the relationship between ET and IT.

Strengths

- The optimal transport formulations in this work, i.e., ET and IT, are something that I have not seen. These formulations, for me, are inspiring and interesting. - The paper provides a thorough discussion on the technical differences and relationship with other existing methods. - The overall presentation of the main paper is generally clear. Furthermore, the full paper, including the appendices, appears to be comprehensive and well-prepared. The theoretical results are presented in a comprehensive and self-contained manner.

Weaknesses

- The scope of and motivation for the work are a little unclear from the abstract and introduction. In particular, the motivation to incorporate ET in the context of domain translation is not clear, which could make readers confused. It should be highlighted at least in the abstract and introduction sections. - Certain statements lack sufficient explanations or supporting intuitions, which should be explained and provided in the main text. To list a few: - In the lines 85-91, a variant of OT problem is established. The authors mentioned "we say that the target domain is the part of Y where the probability mass of Q lives". However, the intuition behind this statement is not well-presented and should be elaborated upon. - In the lines 76-78, the intuition to establish the ET framework in the context of domain translation should be demonstrated. It should also be highlighted in the abstract and introduction sections. Specifically, readers may hope to see why it is essential to construct ET for domain translation task, given thorough related works on weak OT, partial OT, etc... Although you have formulated the technical difference with them, I hope to see analysis on "why ET outperforms them in your application". - In the lines 91-92, the authors relaxes the mass preservation condition for the target domain. Why not relax the condition for both the target and source domain, likewise UOT? A concise and simple comparison with current weak / partial OT should be clarified here, to **explain the advantages of ET in domain translation compared with peer methods, (rather than purely formulating the technical differences)**, which is critical for identifying and evaluating ET's role in domain translation.** ### ************ Minors *************** - Figure 3-4 are kind of redundant and largely inherit from current literatures. As such, it is not appropriate to take too much blank space for them. A more proper way would be consendate them in one line or move them to the appendix. - In the line 104, the NN could lead to unexpected confusion since it usually represents neural networks. - In the lines 80-109, the authors establish an optimization problem to seek for the nearest neighbors of $x\in\mathcal{X}$ in Supp(Q). The narrative in this section is kind of redundant. - It is essential for readers to acknowledge the technical differences with other OT methods. As such, I suggest authors moving the section of "Related works" after the section of "background on optimal transport", and highlight your technical difference with each genre of OT methods concisely. My current score is a reflection of the weaknesses above as they stand. Since these seem like rather correctable issues, I expect to increase my score pending a positive response from the authors.

Questions

- The authors noted "the task is ill-posed as there might exist multiple suitable T." It is confusing for me due to two reasons: (1) you just mention that there could be multiple maps between source and target; however, the optimization problem has not been formulated here, and it is not proper to say it is ill-posed problem since the word ill-posed seems to be suitable for optimization problems; (2) the optimization problem, such as the Kantorovich problem, could be not ill-posed in some cases given certain metrics, is it right? Please consider to improve the narrative to make it more rigorous and self-contained. - The authors noted "challenge here is that the correspondence between vailable data samples a from the source and y from target domains is not given." What if the correspondence is given? Can we get a new optimization problem with intriguing properties?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitations have been well discussed.

Reviewer Cqh57/10 · confidence 3/52023-07-05

Summary

The paper proposes extremal transport (ET), a mathematical framework for achieving the best possible unpaired translation between two domains based on a given similarity function, and proving that ET maps can be learned as a limit of specific partial optimal transport (OT) problem. The contributions of the paper include a formalization of ET as a rigorous mathematical task, the characterization of ET maps and plans through a connection to nearest neighbors, and the derivation of an efficient computational algorithm based on partial optimal transport. The proposed algorithm is evaluated using 2D examples and the unpaired image-to-image translation task.

Strengths

1.The logic of this paper is well organized, and also the mathematical formulas are well defined. 2.The work demonstrates that it is possible to relax equality constraints to inequality constraints especially for some situations where enforcing rigorous equal constraints are difficult, and proposes incomplete transport (IT) to approximate ET maps using partial optimal transport (OT) problems, which is very novel. 3.The experimental part is quite sufficient complete and proves the effectiveness of the proposed method.

Weaknesses

It is not clarified the motivations of defining ET problem and the relationship between specific task such as unpaired image translation and the mathematical ET problem.The process from abstraction of practical problems to theoretical derivation is too steep.

Questions

Why the ET problem is defined in the compact polish spaces?Could it transfer to other spaces?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The ℓ2 and FID metrics have some limitations in characterizing the effectiveness of the method.

Reviewer URfJ9/10 · confidence 3/52023-07-05

Summary

This paper introduces a mathematical formalization called "extremal transport" that aims to achieve optimal translation between unpaired domains based on a given similarity function. Additionally, the paper proposes a scalable algorithm that utilizes neural optimal transport to approximate extremal transport mappings. The algorithm is tested on toy examples and the image-to-image translation task, yielding promising results.

Strengths

The paper introduces a novel mathematical formalization called extremal transport for achieving optimal translation between unpaired domains. Additionally, the concept of neural optimal transport is introduced and applied in the algorithm. These theoretical foundations provide a solid basis for the algorithm design. The algorithm is tested on toy examples and the image-to-image translation task, demonstrating good results. These experiments validate the effectiveness and scalability of the algorithm. Image-to-image translation is an important problem in computer vision, and the proposed algorithm can be applied to address this problem. Furthermore, the paper mentions other potential application areas, such as single-cell data analysis in biology. The algorithm proposed in this paper can be widely applied to solve translation problems between unpaired domains, making it highly generalizable. Additionally, a new method called partial optimal transport is introduced, which can be used to address alignment problems between imbalanced measures, further expanding its potential for generalization.

Weaknesses

Based on the information provided, the paper primarily focuses on the common main features of existing approaches rather than encompassing all of them. It's possible that due to space constraints, some concepts or details may not be extensively elaborated in the main paper. However, substantial explanations are provided in the Appendix.

Questions

In lines 121-124, how the lower bound is defined during the process of analyzing and constructing upper and lower bounds to simplify the objective is not mentioned. The reason why value(8) admits more minimizers is also not explained. In lines 133-136, an explanation is needed for the replacement mentioned here and why using a finite parameter w can achieve the desired replacement of Supp(T#P) belonging to Supp(Q). In lines 218-220, it is asked whether the method presented in the paper scales to high dimensions. If images are defined as high-dimensional, this should be clarified from the beginning of the paper.

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The paper has conducted extensive discussions.

Reviewer Mz3K4/10 · confidence 4/52023-07-18

Summary

This paper introduces the concept of extremal Optimal Transport (OT) and proposes the use of incomplete OT as a solution to the extremal OT problem. The authors present a duality method to address the incomplete OT problem and validate this approach using a toy 2D dataset and image translation tasks.

Strengths

The authors offer the analysis of the proposed problems and algorithms, including the existence of Extremal Transport (ET), the presence of Incomplete Transport (IT), and the convergence of IT plans to the ET plans. They test their algorithms on several image translation datasets, demonstrating the ability to manipulate the similarity between the source image and the generated image by adjusting the weight parameter $w$. Their algorithm exhibits the capability to map the data towards a portion of the target distribution's support.

Weaknesses

## Motivation Firstly, the paper's logic doesn't fully convince me. The authors initially propose to solve the Extremal Transport (ET) problem, but then shift to solving the Incomplete Transport (IT) problem, presumably because the ET problem is too challenging. However, based on their experimental results, it seems more logical to propose solving the IT problem directly, as most of their visualizations demonstrate that adjusting the weight parameter $w$ controls the similarity between the source image and the generated image. If the authors are indeed intent on solving the ET problem, could they provide experimental evidence to support this? For instance, they could design some distributions that have a closed-form solution for ET, and then compare the ground truth minimum value of problem (5) with their simulation results. Regarding the motivation for problem (11): the authors state that "In practice, solving the extremal problem (5) is challenging because it is hard to enforce Supp($T \sharp P$) $\subset$ Supp($Q$)", but isn't this relatively straightforward for image tasks? Since images are typically scaled to a certain range like [-1,1], we can simply scale the images to meet this support requirement. I believe that the application of incomplete OT or extremal OT could be limited in image tasks, especially extremal OT, as multiple data points could be mapped to the same data point, resulting in generated images with limited diversity. ## Method Regarding the relaxation from problem 5 to 11, it seems to me that the constraint in 11 is not a softened version, but rather a stronger one. To satisfy the constraint in (11), one must also satisfy the constraint in (5). This is because in the constraint of (11), if Q=0, then regardless of the value of $w$, $T\sharp P$ must also be zero, which aligns with the constraint in (5). Why is it not feasible to design a dual formula for ET directly? The authors mention the issue of fake solutions. Could they consider borrowing ideas from the Kernel Neural OT paper? It seems that using a similar cost from Kernel Neural OT could enhance this paper, and it seems not that difficult? ## Results Given that the motivation of this paper is to solve the extremal OT problem, could the authors clarify under what conditions their method can recover the solution to extremal OT? Specifically, how large does the value of $w$ need to be? It's possible that this information is already included, and I may have overlooked it. The authors acknowledge that the FID is not particularly meaningful when $w>1$, yet it appears to be the primary metric used in this paper. If the authors believe that FID is not representative, why do they present so many FID results? They also claim that the image quality of the translated image does not decrease with increasing $w$. Is there a way to verify this quantitatively, perhaps with a metric based on the image itself rather than the image distribution? Some of the results presented in this paper seem less than satisfactory. For instance, in Figure 24, even when $w$ is large, some images fail to preserve hair colors. In Figure 22, as $w$ increases, some images exhibit unrealistic artifacts (e.g., the first grey shoe and the black saddle have strange bands on them), likely because the generated image is forced to share more similarity with the source image. Could this be a limitation of the proposed method?

Questions

Figure 5b may not be as illustrative as intended. In this case, it seems that pi would still uniquely correspond to a certain deterministic transport map. Perhaps it would be more instructive to provide an example where (8) admits multiple minimizers, such as a scenario where the support is not convex?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

.

Reviewer iXGC6/10 · confidence 3/52023-07-26

Summary

This paper proposes a novel notion of extremal transport, which relaxes the optimal transport problem by only requiring the support of the pushed-forward distribution to be a subset of the support of the target distribution. To solve this problem, the authors propose a novel approximation approach to find the solution from a subsequence of a series of incomplete OT problems (where T#P = Q is relaxed to T#P < wQ, w >= 1, when w=1 this is the traditional OT problem). Then the author derives novel dual formulations of the incomplete OT problems, which the author proposes to solve by using neural networks to approximate the potential and c-transform solutions. The authors apply the method to toy sets and image translation examples to demonstrate the scalability of the method. FID results on the image translation example prove the concept of the method. The authors carefully compare their results with related works and establish their theoretic novelty. The presentation of the results are clear and potential impacts are well discussed.

Strengths

The paper proves several strong theoretical results on the relaxed versions of OT problems (i.e. ET and IT). The theoretic study of the solutions to these problems is fruitful. This opens up a new domain of study area in the optimal transport area.

Weaknesses

Overall the theoretic results are rigorous and novel. To solve the solution of the dual formulation of IT, the authors propose to use neural networks to approximate the transport map (necessary for solving large-scale problems). One concern I have is that in the traditional OT problem, the OT map is in general discontinuous. This proposes difficulties in using DNN to approximate the OT map. It would be very welcomed if results on the regularity of the IT maps are presented, and/or how well the neural network can approximate such maps.

Questions

One question: in theorem 3, it only guarantees the existence of a subsequence. In practice, if we found a sequence of solutions by Alg. 1, how can we make sure whether it is the desired ET solution?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitation of the paper is adequately addressed by the authors.

Area Chair YdJW2023-08-14

Dear reviewer Mz3K, does the author's rebuttal address your concerns? In particular, can you comment on whether your concerns on formulation and method are addressed? Do you have further comments/questions for the authors?

Reviewer Mz3K2023-08-14

Thank you for your reply! I have some follow-up questions. (6) "We do not specify the rate of convergence and leave this aspect for future studies (see lines 168-170)." Can you discuss this even empirically? For example, for those face image style transfer and handbag <-> shoes datasets, what range is enough? (7) FID and metrics based on images itself. Could you try to add the following baseline? For each image in the source dataset, determine its closest match in the target dataset using a 1-nearest-neighbor approach. This method will allow you to create a new dataset. Then, calculate the FID concerning this newly established dataset instead of the initial target dataset. I foresee a reduction in the FID value as $w$ increases.

Authorsrebuttal2023-08-16

Additional response

Dear Reviewer Mz3K, please find the answers to your follow-up questions below. **(1) Convergence rate: empirically, which values of $w$ are enough to make IT maps close to ET?** We may use the $\ell^2$ transport cost of learned IT maps to determine $w$ for which IT maps become close enough to ET. Indeed, after a certain value of $w$ it is expected that $\mbox{Cost}_{w}$ will stop rapidly changing. Hence, intuitively, one may expect that IT map is close enough to ET as well. For *celeba*$\rightarrow$*anime* case, the $\ell^{2}$ cost decreases rapidly for weights $w\in\\{1,2,4,8\\}$, see Table 1(a) in our paper. However, as we discussed in Appendix G.2, further increase of the weight (there we tested additional weights $w\in\\{16,32\\}$) does not lead to any significant cost decrease. Therefore, for this pair of datasets, $w=8$ can be considered as a sufficient value to get the IT map which is close enough to ET. In *handbag*$\rightarrow$*shoes* experiment, the difference in $\ell^2$ cost between $w=4$ and $w=8$ in Table 1(a) seems insignificant. Thus, in this case, for $w=4$ the IT map may be treated as close enough to some ET map. **(2) FID for the 1-nearest-neighbors.** To address the reviewer's question, we calculate FID values between our IT maps and 1-nearest-neighbors of input samples in target dataset (test parts) for *celeba*$\rightarrow$*anime* and *handbag*$\rightarrow$*shoes* experiments, see the Table below. | | $w=1$ | $w=2$ | $w=4$ | $w=8$ | |---------------------------------------------|-------|-------|-------|-------| | *celeba*$\rightarrow$*anime* | 53.21 | 44.81 | 39.77 | 43.03 | | *handbag*$\rightarrow$*shoes* | 73.35 | 68.31 | 73.44 | 80.61 | We see that there is no obvious dependence between the weight $w$ and calculated FID values. This is quite expected since the comparison with discrete nearest neighbors is irrelevant in our case. Indeed, in our paper we show that minimizer $T^*$ of ET problem (which we seek for when $w\rightarrow\infty$) maps each point $x\sim\mathbb{P}$ to its nearest neighbors *in the support* (Supp$(\mathbb{Q})$) of the target distribution, see lines 104-113. However, nearest neighbors in the **empirical** dataset are significantly **biased** over the desired nearest neighbors in the support. The fact that the **empirical nearest neighbors are a poor replacement of the true nearest neighbors** (in the support) was already indirectly illustrated in the Appendix D of our paper. There we regressed (distilled) a neural network $T_{\theta}$ to predict discrete (empirical) nearest neighbors in the train dataset. From Figure 18 we can make two valuable conclusions: - While the learned network generates high-quality images on the training dataset (Figure 18(b), $w=\infty$), it struggles to generalize well to the unseen test samples (Figure 18(a), $w=\infty$). - The empirical nearest neighbors may not have sufficient similarity with the input images. This can be seen from Figure 18(b) (the 1st and last lines). Despite the fact that the target empirical nearest neighbors are not shown there, our trained network ($w=\infty$) almost perfectly reproduces them (the train loss was almost zero in that experiment). Hence, the images in the last line can be viewed as the empirical nearest neighbors to the images on the first line. To conclude, FID values estimated by using the empirical replacement of nearest neighbors can not be considered as the representative metric.

Reviewer Mz3K2023-08-17

Thank you for your prompt response. I am willing to increase my score. However, upon reviewing the supplementary material, I've observed a few areas that might benefit from further refinement. Specifically, in Figure 23, columns five and six, it appears that as $w$ increases, the generated chair seems to deviate from the input pattern. Additionally, in certain columns, such as the penultimate and final ones, the generated chair doesn't seem to closely match the input pattern. Moving on to Figure 24, in the first column, the generated face at $w=8$ seems to lack the teeth detail, and in the fifth column, the representation at $w=1$ appears to be more in line with the input because it does not show the teeth. I believe there's potential for further enhancement, perhaps by integrating methods like the kernel neural OT.

Authorsrebuttal2023-08-18

Response to your official comment

Dear Reviewer, we appreciate your thorough attention to the details of our paper. Please find below the clarifications for the concerns which you raised. **(1a) Figure 23. In columns 5 and 6, as $w$ increases, the generated chair seems to deviate from the input pattern. In penultimate (11th) and final (12th) columns, the generated chair doesn't seem to closely match the input pattern.** **(1b) Figure 24. In the 1st column, the generated face at $w=8$ seems to lack the teeth detail. In the 5th column, the representation at $w=1$ appears to be more in line with the input because it does not show the teeth.** In order to address your concerns about the patterns and details, we additionally explain several points about our results. - Particular samples are not good representatives of the properties of the entire learned transport map $\hat{T}$. According to the average $\ell^2$ cost between the generated and respective input images, the **average input-output dissimilarity** $\frac{1}{N_{test}}\sum_{n=1}^{N_{test}}\ell^{2}(x_n,\hat{T}(x_n))$ indeed decreases for all the dataset pairs with the increase of the weight $w$, see Table 1 in our paper. - Moreover, we additionally calculate $\ell^2(x,\hat{T}(x))$ for the **particular face/texture samples** $x$ to which you pointed to. We see that their input-output dissimilarity also decreases with the increase of $w$ in majority of the cases, see the Table below. | | $w=1$ | $w=2$ | $w=4$ | $w=8$ | |------------------|-------|-------|-------|-------| | Fig. 23, col. 5 | 0.635 | 0.526 | 0.522 | 0.482 | | Fig. 23, col. 6 | 0.524 | 0.378 | 0.323 | 0.277 | | Fig. 23, col. 11 | 0.798 | 0.724 | 0.610 | 0.591 | | Fig. 23, col. 12 | 0.410 | 0.420 | 0.291 | 0.226 | | Fig.24, col. 1 | 0.258 | 0.239 | 0.213 | 0.198 | | Fig.24, col. 5 | 0.154 | 0.131 | 0.105 | 0.103 | - It is a generic knowledge that $\ell^2$ cost is mostly sensitive to low-frequency image components (big image parts) rather than high-frequency components (tiny details). For example, as your noted, in the 1st column of Figure 24, IT map for $w=8$ lacks the fine teeth detail. However, here we observe the presence of the long hair (like in the input image). Note that the hair was not generated for smaller weights. In the *textures*$\rightarrow$*chairs* experiment, the situation is also expainable. Here with the increase of $w$, the IT method with $\ell^{2}$ focuses more on the reducing the white background area. At the same time, preservation of the fine details of the texture may become less important. We have partially mentioned this aspect in lines 508-509 of Appendix A (limitations). To conclude, when using $\ell^{2}$ cost, it is not correct to assess similarity of the images focusing only on fine/tiny image details. In order to focus on such details, one may consider using more advanced cost functions, e.g., perceptual ones from computer vision. While this is a promising research avenue, it is beyond the scope of our paper which focuses on developing the theoretical formulation and the computational algorithm. Still to ensure that our IT algorithm may work with costs beside $\ell^{2}$, we have already tested it with a VGG-based perceptual cost, see Appendix G.1. **(2) Further enhancement, e.g., using kernel neural OT.** We agree that many potential modifications to our methodology can be considered. For example, apart from the advanced cost functions mentioned above, one indeed may employ kernel regularization [1]. We note that the goal of the current work is to establish the **basic fundament** to which such modifications can be applied. Studying of all possible modifications is a separate interesting topic which is out of the scope of our paper. At the same time, we have already provided evidence that such modifications are applicable and sometimes useful. In Appendix G.1, there are our experiments with a perceptual cost and in the attached PDF $-$ your requested experiment with kernel regularization. **Concluding remarks.** We hope that our clarifications have resolved your concerns regarding our method performance and potential enhancement. If the responses above are sufficient, we kindly ask that you consider raising your score. **References** [1] Korotin, A. et al. (2023). Kernel neural optimal transport.

Reviewer URfJ2023-08-16

The authors answered questions and will also add details. Their work is greatly appreciated.

Area Chair YdJW2023-08-18

Rebuttal Acknowledgment

Dear authors, Thank you for your efforts in writing a rebuttal. Unfortunately not all reviewers have acknowledged or responded to it, but rest assured that I have read it and will bring it up in further discussion with the reviewers, and will take it into account for the final recommendation. Best, AC

Reviewer 3fqr2023-08-20

Acknowledgement

Thank you very much for your detailed response. The author response has mitigated my concerns, especially (1-4). I believe the authors could consider my suggestions in preparing their final version. After reading the comments from other reviewers and author responses, I am pleased to adjust my initial rating to support acceptance of this work more definitely.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC