1 Introduction↩︎

Multiple marginal matching (M\(^3\)) problem aims to map an input image (source domain) to multiple target domains (see Figure 1 (a)), and it has been applied in computer vision, e.g., multi-domain image translation [1]–[3]. In practice, the unsupervised image translation [4] gains particular interest because of its label-free property. However, due to the lack of corresponding images, this task is extremely hard to learn stable mappings to match a source distribution to multiple target distributions. Recently, some methods [1], [4] address M\(^3\) problem, which, however, face two main challenges.

First, existing methods often neglect to jointly optimize the multi-marginal distance among domains, which cannot guarantee the generalization performance of methods and may lead to distribution mismatching issue. Recently, CycleGAN [5] and UNIT [6] repeatedly optimize every pair of two different domains separately (see Figure 1 (b)). In this sense, they are computationally expensive and may have poor generalization performance. Moreover, UFDN [4] and StarGAN [1] essentially measure the distance between an input distribution and a mixture of all target distributions (see Figure 1 (b)). As a result, they may suffer from distribution mismatching issue. Therefore, it is necessary to explore a new method to measure and optimize the multi-marginal distance.

Second, it is very challenging to exploit the cross-domain correlations to match target domains. Existing methods [4], [5] only focus on the correlations between the source and target domains, since they measure the distance between two distributions (see Figure 1 (b)). However, these methods often ignore the correlations among target domains, and thus they are hard to fully capture information to improve the performance. Moreover, when the source and target domains are significantly different, or the number of target domains is large, the translation task turns to be difficult for existing methods to exploit the cross-domain correlations.

In this paper, we seek to use multi-marginal Wasserstein distance to solve M\(^3\) problem, but directly optimizing it is intractable. Therefore, we develop a new dual formulation to make it tractable and propose a novel multi-marginal Wasserstein GAN (MWGAN) by enforcing inner- and inter-domain constraints to exploit the correlations among domains.

The contributions of this paper are summarized as follows:

• We propose a novel GAN method (called MWGAN) to optimize a feasible multi-marginal distance among different domains. MWGAN overcomes the limitations of existing methods by alleviating the distribution mismatching issue and exploiting cross-domain correlations.

• We define and analyze the generalization of our proposed method for the multiple domain translation task, which is more important than existing generalization analyses [7], [8] studying only on two domains and non-trivial for multiple domains.

• We empirically show that MWGAN is able to solve the imbalanced image translation task well when the source and target domains are significantly different. Extensive experiments on toy and real-world datasets demonstrate the effectiveness of our proposed method.

2 Related Work↩︎

Generative adversarial networks (GANs). Deep neural networks have theoretical and experimental explorations [9]–[13]. In particular, GANs [14] have been successfully applied in computer vision tasks, such as image generation [15]–[18], image translation [1], [19], [20] and video prediction [21]. Specifically, a generator tries to produce realistic samples, while a discriminator tries to distinguish between generated data and real data. Recently, some studies try to improve the quality [22]–[24] and diversity [25] of generated images, and improve the mechanism of GANs [26]–[29] to deal with the unstable training and mode collapse problems. Multi-domain image translation. M\(^3\) problem can be applied in domain adaptation [30] and image translation [31], [32]. CycleGAN [5], DiscoGAN [33], DualGAN [34] and UNIT [6] are proposed to address two-domain image translation task. However, in Figure 1 (b), these methods measure the distance between every pair of distributions multiple times, which is computationally expensive when applied to the multi-domain image translation task. Recently, StarGAN [1] and AttGAN [2] use a single model to perform multi-domain image translation. UFDN [4] translates images by learning domain-invariant representation for cross-domains. Essentially, the above three methods are two-domain image translation methods because they measure the distance between an input distribution and a uniform mixture of other target distributions (see Figure 1 (b)). Therefore, these methods may suffer from distribution mismatching issue and obtain misleading feedback for updating models when the source and target domains are significantly different. In addition, we discuss the difference between some GAN methods in Section 16 in supplementary materials.

3 Problem Definition↩︎

3.0.0.1 Notation.

We use calligraphic letters (e.g., \({\mathcal{X}}\)) to denote space, capital letters (e.g., \(X\)) to denote random variables, and bold lower case letter (e.g., \({\boldsymbol{x}}\)) to denote the corresponding values. Let \({\mathcal{D}}{=} ({\mathcal{X}}, {\mathbb{P}})\) be the domain, \({\mathbb{P}}\) or \(\mu\) be the marginal distribution over \({\mathcal{X}}\) and \({\mathcal{P}}({\mathcal{X}})\) be the set of all the probability measures over \({\mathcal{X}}\). For convenience, let \({\mathcal{X}}{=} {\mathbb{R}}^d\), and let \({\mathcal{I}}{=} \{ 0, ..., N \}\) and \([N]{=}\{1, ..., N\}\). Multiple marginal matching (M\(^3\)) problem. In this paper, M\(^3\) problem aims to learn mappings to match a source domain to multiple target domains. For simplicity, we consider one source domain \({\mathcal{D}}_s{=}\{{\mathcal{X}}, {\mathbb{P}}_s\}\) and \(N\) target domains \({\mathcal{D}}_i{=}\{{\mathcal{X}}, {\mathbb{P}}_{t_i}\}, i {\in} [N]\), where \({\mathbb{P}}_s\) is the source distribution, and \({\mathbb{P}}_{t_i}\) is the \(i\)-th real target distribution. Let \(g_i, i {\in} [N]\) be the generative models parameterized by \(\theta_i\), and \({\mathbb{P}}_{\theta_i}\) be the generated distribution in the \(i\)-th target domain. In this problem, the goal is to learn multiple generative models such that each generated distribution \({\mathbb{P}}_{\theta_i}\) in the \(i\)-th target domain can be close to the corresponding real target distribution \({\mathbb{P}}_{t_i}\) (see Figure 1 (a)).

Optimal transport (OT) theory. Recently, OT [35] theory has attracted great attention in many applications [15], [36]. Directly solving the primal formulation of OT [37] might be intractable [38]. To address this, we consider the dual formulation of the multi-marginal OT problem as follows.

Unfortunately, it is challenging to optimize Problem 2 due to the intractable inequality constraints and multiple potential functions. To address this, we seek to propose a new optimization method.

4 Multi-marginal Wasserstein GAN↩︎

4.1 A New Dual Formulation↩︎

For two domains, WGAN [15] solves Problem 2 by setting potential functions as \(f_0 {=} f\) and \(f_1 {=} {-}f\). However, it is hard to extend WGAN to multiple domains. To address this, we propose a new dual formulation in order to optimize Problem 2. To this end, we use a shared potential in Problem 2, which is supported by empirical and theoretical evidence. In the multi-domain image translation task, the domains are often correlated, and thus share similar properties and differ only in details (see Figure 1 (a)). The cross-domain correlations can be exploited by the shared potential function (see Section 17 in supplementary materials). More importantly, the optimal objectives of Problem 2 and the following problem can be equal under some conditions (see Section 9 in supplementary materials).

To further build the relationship between Problem 2 and Problem 3, we have the following theorem so that Problem 3 can be optimized well by GAN-based methods (see Subsection 4.2).

4.2 Proposed Objective Function↩︎

To minimize Wasserstein distance among domains, we now present a novel multi-marginal Wasserstein GAN (MWGAN) based on the proposed dual formulation in (?? ). Specifically, let \({\mathcal{F}}{=} \{ f{:}\, {\mathbb{R}}^d {\to} {\mathbb{R}}\}\) be the class of discriminators parameterized by \(w\), and \({\mathcal{G}}{=} \{ g{:}\, {\mathbb{R}}^d {\to} {\mathbb{R}}^d \}\) be the class of generators and \(g_i {\in} {\mathcal{G}}\) is parameterized by \(\theta_i\). Motivated by the adversarial mechanism of WGAN, let \(\lambda_0 {=} 1\) and \(\lambda_i {:=} {-} \lambda_i^+\), \(\lambda_i^{+}{>}0, i {\in} [N]\), then Problem 3 can be rewritten as follows:

In Problem 4, we refer to \(\hat{{\mathbb{P}}}_{\theta_i} {\in} {\mathcal{D}}_i, i{\in}[N]\) as inner-domain constraints and \(f {\in} \Omega\) as inter-domain constraints (See Subsections 4.3 and 4.4). The influence of these constraints are investigated in Section 21 of supplementary materials. Note that \(\lambda_i^+\) reflects the importance of the \(i\)-th target domain. In practice, we set \(\lambda_i^+ {=} 1/N, i{\in}[N]\) when no prior knowledge is available on the target domains. To minimize Problem 4, we optimize the generators with the following update rule.

Theorem 2 provides a good update rule for optimizing MWGAN. Specifically, we first train an optimal discriminator \(f\) and then update each generator along the direction of \({\mathbb{E}}_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_s} \left[ \nabla_{\theta_i} f(g_{i}({\boldsymbol{x}})) \right]\). The detailed algorithm is shown in Algorithm 2. Specifically, the generators cooperatively exploit multi-domain correlations (see Section 17 in supplementary materials) and generate samples in the specific target domain to fool the discriminator; the discriminator enforces generated data in target domains to maintain the similar features from the source domain.

4.3 Inner-domain Constraints↩︎

In Problem 4, the distribution \({\mathbb{P}}_{\theta_i}\) generated by the generator \(g_i\) should belong to the \(i\)-th domain for any \(i\). To this end, we introduce an auxiliary domain classification loss and the mutual information.

Domain classification loss. Given an input \({\boldsymbol{x}}{:=}{\boldsymbol{x}}^{(0)}\) and generator \(g_i\), we aim to translate the input \({\boldsymbol{x}}\) to an output \(\hat{{\boldsymbol{x}}}^{(i)}\) which can be classified to the target domain \({\mathcal{D}}_i\) correctly. To achieve this goal, we introduce an auxiliary classifier \(\phi{:\;} {\mathcal{X}}{\to} {\mathcal{Y}}\) parameterized by \(v\) to optimize the generators. Specifically, we label real data \({{\boldsymbol{x}}} {\sim} \hat{{\mathbb{P}}}_{t_i}\) as \(1\), where \(\hat{{\mathbb{P}}}_{t_i}\) is an empirical distribution in the \(i\)-th target domain, and we label generated data \(\hat{{\boldsymbol{x}}}^{(i)} {\sim} \hat{{\mathbb{P}}}_{\theta_i}\) as \(0\). Then, the domain classification loss w.r.t. \(\phi\) can be defined as: \[\begin{align} \label{loss:classification} {\mathcal{C}}_{\alpha}(\phi) = \alpha \cdot {{\mathbb{E}}}_{{\boldsymbol{x}}' {\sim} \hat{{\mathbb{P}}}_{t_i} {\cup} \hat{{\mathbb{P}}}_{\theta_i}} \left[ \ell \left( \phi\left({{\boldsymbol{x}}'} \right), y^{} \right) \right], \end{align}\tag{1}\] where \(\alpha\) is a hyper-parameter, \(y\) is corresponding to \({\boldsymbol{x}}'\), and \(\ell(\cdot, \cdot)\) is a binary classification loss, such as hinge loss [39], mean square loss [40], cross-entropy loss [14] and Wasserstein loss [41].

4.3.0.1 Mutual information maximization.

After learning the classifier \(\phi\), we maximize the lower bound of the mutual information [2], [42] between the generated image and the corresponding domain, i.e., 

By maximizing the mutual information in (2 ), we correlate the generated image \(g_i({\boldsymbol{x}})\) with the \(i\)-th domain, and then we are able to translate the source image to the specified domain.

4.4 Inter-domain Constraints↩︎

Then, we enforce the inter-domain constraints in Problem 4, i.e., the discriminator \(f {\in} {\mathcal{F}}{\cap} \Omega\). One can let discriminator be \(1\)-Lipschitz continuous, but it may ignore the dependency among domains (see Section 15 in supplementary materials). Thus, we relax the constraints by the following lemma.

Note that \(L_f\) measures the dependency among domains (see Section 14 in supplementary materials). In practice, \(L_f\) can be calculated with the cost function, or treated as a tuning parameter for simplicity.

Inter-domain gradient penalty. In practice, directly enforcing the inequality constraints in Lemma 1 would have poor performance when generated samples are far from real data. We thus propose the following inter-domain gradient penalty. Specifically, given real data \({\boldsymbol{x}}\) in the source domain and generated samples \(\hat{{\boldsymbol{x}}}^{(i)}\), if \(\hat{{\boldsymbol{x}}}^{(i)}\) can be properly close to \({\boldsymbol{x}}\), as suggested in [43], we can calculate its gradient and introduce the following regularization term into the objective of MWGAN, i.e., 

where \((\cdot)_+ {=} \max\{0, \cdot\}\), \(\tau\) is a hyper-parameter, \(\tilde{{\boldsymbol{x}}}^{(i)}\) is sampled between \({\boldsymbol{x}}\) and \(\hat{{\boldsymbol{x}}}^{(i)}\), and \(\hat{{\mathbb{Q}}}_i, i {\in} [N]\) is a constructed distribution relying on some sampling strategy. In practice, one can construct a distribution where samples \(\tilde{{\boldsymbol{x}}}^{(i)}\) can be interpolated between real data \({\boldsymbol{x}}\) and generated data \(\hat{{\boldsymbol{x}}}^{(i)}\) for every domain [17]. Note that the gradient penalty captures the dependency of domains since the cost function in Problem 4 measures the distance among all domains jointly.

5 Theoretical Analysis↩︎

In this section, we provide the generalization analysis for the proposed method. Motivated by [44], we give a new definition of generalization for multiple distributions as follows.

In Definition 1, the generalization bound measures the difference between the expected distance and the empirical distance. In practice, our goal is to train MWGAN to obtain a small empirical distance, so that the expected distance would also be small.

With the help of Definition 1, we are able to analyze the generalization ability of the proposed method. Let \(\kappa\) be the capacity of the discriminator, and if the discriminator is \(L\)-Lipschitz continuous and bounded in \([-\Delta, \Delta]\), then we have the following generalization bound.

Theorem 3 shows that MWGAN has a good generalization ability with enough training data in each domain. In practice, if successfully minimizing the multi-domain Wasserstein distance i.e., \(W(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, \ldots, \hat{{\mathbb{P}}}_{\theta_N})\), the expected distance \(W({\mathbb{P}}_s, {\mathbb{P}}_{\theta_1}, \ldots, {\mathbb{P}}_{\theta_N})\) can also be small.

6 Experiments↩︎

Implementation details. All experiments are conducted based on PyTorch, with an NVIDIA TITAN X GPU.³ We use Adam [45] with \(\beta_1{=}0.5\) and \(\beta_2{=}0.999\) and set the learning rate as 0.0001. We train the model 100k iterations with batch size 16. We set \(\alpha{=}10\), \(\tau {=} 10\) and \(L_f\) to be the number of target domains in Loss (3 ). The details of the loss function and the network architectures of the discriminator, generators and classifier can be referred to Section 23 in supplementary materials.

Baselines. We adopt the following methods as baselines: (i) CycleGAN [5] is a two-domain image translation method which can be flexibly extended to perform the multi-domain image translation task. (ii) UFDN [4] and (iii) StarGAN [1] are multi-domain image translation methods.

Datasets. We conduct experiments on three datasets. Note that all images are resized as 128\(\times\)​128. (i) Toy dataset. We generate a Gaussian distribution in the source domain, and other six Gaussian or Uniform distributions in the target domains. More details can be found in the supplemental materials.
(ii) CelebA [46] contains 202,599 face images, where each image has 40 binary attributes. We use the following attributes: hair color (black, blond and brown), eyeglasses, mustache and pale skin. In the first experiment, we use black hair images as the source domain, and use the blond hair, eyeglasses, mustache and pale skin images as target domains. In the second experiment, we extract 50k Canny edges from CelebA. We take edge images as the source domain and hair images as target domains.
(iii) Style painting [5]. The size of Real scene, Monet, Van Gogh and Ukiyo-e is 6287, 1073, 400 and 563, respectively. We take real scene images as the source domain, and others as target domains.

Evaluation Metrics. We use the following evaluation metrics: (i) Frechet Inception Distance (FID) [47] evaluates the quality of the translated images. In general, a lower FID score means better performance. (ii) Classification accuracy widely used in [1], [2] evaluates the probability that the generated images belong to corresponding target domains. Specifically, we train a classifier on CelebA (90% for training and 10% for testing) using ResNet-18 [48], resulting in a near-perfect accuracy, then use the classifier to measure the classification accuracy of the generated images.

6.1 Results on Toy Dataset↩︎

We compare MWGAN with UFDN and StarGAN on toy dataset to verify the limitations mentioned in Section 2. Specifically, we measure the distribution matching ability and plot the value surface of the discriminator. Here, the value surface depicts the outputs of the discriminator [17], [49].

In Figure 3, MWGAN matches the target domain distributions very well as it is able to capture the geometric information of real distribution using a low-capacity network. Moreover, the value surface shows that the discriminator provides correct gradients to update the generators. However, the baseline methods are very sensitive to the type of source and target domain distributions. With the same capacity, the baseline methods on similar distributions (top row) are able to match the target domain distributions. However, they cannot match the target domain distribution well when the initial and the target domain distributions are different (see bottom row of Figure 3).

  

6.2 Results on CelebA↩︎

We compare MWGAN with several baselines on both balanced and imbalanced translation tasks.

(i) Balanced image translation task. In this experiment, we train the generators to produce single attribute images, and then synthesize multi-attribute images using the composite generators. We generate attributes in order of {Blond hair, Eyeglasses, Mustache, Pale skin}. Taking two attributes as an example, let \(g_1\) and \(g_2\) be the generators of Blond hair and Eyeglasses images, respectively, then images with Blond hair and Eyeglasses attributes are generated by the composite generators \(g_2 {\circ} g_1\).

Qualitative results. In Figure 4, MWGAN has a better or comparable performance than baselines on the single attribute translation task, but achieves the highest visual quality of multi-attributes translation results. In other words, MWGAN has good generalization performance. However, CycleGAN is hard to synthesize multi-attributes. UFDN cannot guarantee the identity of the translated images and produces images with blurring structures. Moreover, StarGAN highly depends on the number of transferred domains and the synthesized images sometimes lack the perceptual realism.

Quantitative results. We further compare FID and classification accuracy for the single-attribute results. For the multi-attribute results, we only report classification accuracy because FID is no longer a valid measure and may give misleading results when training data are not sufficient [47]. In Table 1, MWGAN achieves the lowest FID and comparable classification accuracy, indicating that it produces realistic single-attribute images of the highest quality. In Table ¿tbl:table:multi95att95fid95acc?, MWGAN achieves the highest classification accuracy and thus synthesizes the most realistic multi-attribute images.

(ii) Imbalanced image translation task. In this experiment, we compare MWGAN with baselines on the Edge\({\rightarrow}\)CelebA translation task. Note that this task is unbalanced because the information of edge images is much less than facial attribute images.

Qualitative results. In Figure 5, MWGAN is able to generate the most natural-looking facial images with the corresponding attributes from edge images. In contrast, UFDN fails to preserve the facial texture of an edge image, and generates images with very blurry and distorted structure. In addition, CycleGAN and StarGAN mostly preserve the domain information but cannot maintain the sharpness of images and the facial structure information. Moreover, this experiment also shows the superiority of our method on the imbalanced image translation task.

Quantitative results. In Table [tbl:table:edge2hair], MWGAN achieves the lowest FID, showing that it is able to produce the most realistic facial attributes from the edge images. In contrast, the FID values of baselines are large because these methods are hard to generate sharp and realistic images. We also perform a perceptual evaluation with AMT for this task(see Section 20 in supplementary materials).

6.3 Results on Painting Translation↩︎

In this experiment, we finally train our model on the painting dataset to conduct the style transfer task. As suggested in [5], [50], [51], we only show the qualitative results. Note that this translation task is also imbalanced because the input and target distributions are significantly different.

In Figure [fig:photo2art], MWGAN generates painting images with higher visual quality. In contrast, UFDN fails to generate clearly structural painting images because it is hard to learn domain-invariant representation when domains are highly imbalanced. CycleGAN cannot fully learn some useful information from painting images to scene images. When taking a painting image as an input, StarGAN may obtain misleading information to update the generator. In this sense, when all domains are significantly different, StarGAN may not learn a good single generator to synthesize images of multiple domains.

7 Conclusion↩︎

In this paper, we have proposed a novel multi-marginal Wasserstein GAN (MWGAN) for multiple marginal matching problem. Specifically, with the help of multi-marginal optimal transport theory, we develop a new dual formulation for better adversarial learning on the unsupervised multi-domain image translation task. Moreover, we theoretically define and further analyze the generalization ability of the proposed method. Extensive experiments on both toy and real-world datasets demonstrate the effectiveness of the proposed method.

Acknowledgements↩︎

This work is partially funded by Guangdong Provincial Scientific and Technological Funds under Grants 2018B010107001, National Natural Science Foundation of China (NSFC) 61602185, key project of NSFC (No. 61836003), Fundamental Research Funds for the Central Universities D2191240, Program for Guangdong Introducing Innovative and Enterpreneurial Teams 2017ZT07X183, and Tencent AI Lab Rhino-Bird Focused Research Program (No. JR201902). This work is also partially funded by Microsoft Research Asia (MSRA Collaborative Research Program 2019).

0.2cm

 

7.0.0.1 Organization.

In the supplementary materials, we provide detailed proofs for all theorems, lemmas and propositions of our paper ref_cao2019mwgan?, and more experiment settings and results. We organize our supplementary materials as follows.

Theory part. In Section 8, we provide preliminaries of multi-marginal optimal transport. In Section 9, we prove an equivalence theorem that solving Problem 2 is equivalent to solving Problem 3 under a mild assumption. In Section 10, we build the relationship between Problem 2 and Problem 3. In Section 11, we provide an error bound of the new dual formulation. In Section 12, we prove an update rule of optimizing the generators in Problem 4. In Section 13, we theoretically analyze the generalization performance of MWGAN. In Section 14, we provide a relaxation of inter-domain constraints. In Section 15, we discuss a case that the potential function is Lipschitz continuous.

Experiment part. In Section 16, we compare MWGAN with existing GAN methods. In Section 17, we study the effectiveness of one potential function of MWGAN. In Section 18, we introduce more details of toy dataset. In Section 19, we introduce details of the classification on CelebA. In Section 20, we apply more quantitative evaluations for MWGAN. In Section 21, we discuss the influences of inner-domain constraints and inter-domain constraints. In Section 22, we discuss the influence of the hyper-parameter in our proposed method. In Section 23, we introduce the details about the network architecture of the discriminator and generators as well as more training details of MWGAN. In Section 24, we present more qualitative results on CelebA and style painting dataset.

8 Preliminaries of Multi-marginal Optimal Transport↩︎

8.0.0.1 Notation.

We use calligraphic letters (e.g., \({\mathcal{X}}\)) to denote space, capital letters (e.g., \(X\)) to denote random variables, and bold lower case letter (e.g., \({\boldsymbol{x}}\)) to denote the corresponding values. Let \({\mathcal{D}}{=} ({\mathcal{X}}, {\mathbb{P}})\) be the domain, \({\mathbb{P}}\) or \(\mu\) be the marginal distribution over \({\mathcal{X}}\) and \({\mathcal{P}}({\mathcal{X}})\) be the set of all the probability measures over \({\mathcal{X}}\). For convenience, let \({\mathcal{X}}{=} {\mathbb{R}}^d\), and let \({\mathcal{I}}{=} \{ 0, ..., N \}\) and \([N]{=}\{1, ..., N\}\). Deep learning has achieved great success in computer vision. Despite its empirical success, however, the theoretical understanding of deep neural networks still remains an open problem. Existing analysis methods ref_cao2017flatness? are hard to understand the deep neural networks. Recently, optimal transport ref_villani2008optimal?, ref_cao2019learning?, ref_yan2019oversampling? has been applied in deep learning ref_zhang2019miccai?. With the help of optimal transport theory, one can define the following primal problem to measure the distance among all distributions jointly (see Figure 1). Specifically, the primal formulation of the multi-marginal Kantorovich problem is defined as follows.

Solving the primal problem is intractable on the generative task ref_genevay2018learning?, so we consider the dual formulation of the multi-marginal Kantorovich problem.

There is an interesting class of functions satisfying the constraint in Problem 1, it is helpful for deriving Theorem 4.

With Definition 2, the following theorem builds a relationship between the primal and dual problem.

This Primal-dual Optimality theorem helps to derive a new dual formulation in Theorem 1.

9 Equivalent Theorem↩︎

The Kantorovich duality theorem ref_santambrogio2015optimal? can transform Problem 2 into the following problem.

9.1 Proofs of Equivalent Theorem↩︎

Theorem 5 (Equivalent Theorem) Given the cost function defined in Definition 3, and \(\sum_i \lambda_i {=} 0, i{\in}{\mathcal{I}}\) then solving Problem 3 is equivalent to solving Problem 2, i.e., the optimal objective of Problems 2 and 3 are equal.

Proof First, we prove that any optimal solution to Problem 3 is a feasible solution to Problem 2. Suppose that \(f^*\) is the optimal solution to Problem 3, from Lemma 2, we know that \[\begin{align} f^*\left({\boldsymbol{x}}^{(0)}\right) = \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\limits_{j=1}^{N} \lambda_j f^* \left({\boldsymbol{x}}^{(j)} \right) \right\}, \quad \forall \; {\boldsymbol{x}}{\in} {\mathcal{X}}^0. \end{align}\] From the definition of \(c\)-conjugate function in Eqn. (?? ), we have \[\begin{align} (f^*)^c\left({\boldsymbol{x}}^{(0)}\right) = \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\limits_{j=1}^{N} \lambda_j f^* \left({\boldsymbol{x}}^{(j)} \right) \right\}, \quad \forall \; {\boldsymbol{x}}{\in} {\mathcal{X}}^0. \end{align}\] Hence, \(f^*\) is a feasible solution to Problem 2. Therefore, \[\begin{align} \hat{h}(F_c^*) \geq \hat{h}(F_{\lambda}^*). \end{align}\] Second, we prove that any optimal solution to Problem 2 is a feasible solution to Problem 3. Suppose \(f_i^*, i\in[N]\) are optimizers to Problem 2. From Lemma 2, \(\forall\; {\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\) with equal value, we have \((f^c)^*({\boldsymbol{x}}_{k_0}^{(0)}) = f_i^*({\boldsymbol{x}}_{k_i}^{(i)}), i \in [N]\), given that the cost function satisfies the condition in Definition 3. Therefore, we can find a function \(\phi\) and \(\lambda_i, i\in[N]\) such that \[\begin{align} \lambda_0 \phi\left({\boldsymbol{x}}_{k_0}^{(0)}\right) &= (f^c)^*\left({\boldsymbol{x}}_{k_0}^{(0)}\right), \\ \lambda_i \phi \left( {\boldsymbol{x}}_{k_i}^{(i)} \right) &= f_i^*\left({\boldsymbol{x}}_{k_i}^{(i)}\right). \end{align}\] Thus, \(\hat{h}(F_c^*)\) can be rewritten as \[\begin{align} \hat{h}(F_c^*) = \sum\limits_{i} \frac{\lambda_i}{n_i} \sum\limits_{j \in {\mathcal{J}}_i} \phi \left({\boldsymbol{x}}_{j}^{(i)} \right) \end{align}\] From the definition of \((f^c)^*\), we have \[\begin{align} \sum\nolimits_{i} \lambda_i \phi \left({\boldsymbol{x}}^{(i)} \right) \leq c \left({\boldsymbol{x}}^{(0)}, \ldots, {\boldsymbol{x}}^{(N)} \right), \end{align}\] Therefore, \(\phi\) is a feasible solution to Problem 3, and hence \[\begin{align} \hat{h}(F_c^*) \leq \hat{h}(F_{\lambda}^*). \end{align}\] From \(\hat{h}(F_c^*) \geq \hat{h}(F_{\lambda}^*)\) and \(\hat{h}(F_c^*) \leq \hat{h}(F_{\lambda}^*)\), we have \[\begin{align} \hat{h}(F_c^*) = \hat{h}(F_{\lambda}^*), \end{align}\] where \(\hat{h}(F^*_{\lambda}) = \{ \lambda_0 f^*, \ldots, \lambda_N f^* \}\). \(\square\)

9.2 Proofs of Lemmas 2 and 3↩︎

Lemma 2 If the cost function \(c(\cdot, \ldots, \cdot)\) satisfies Definition 3, then \(\forall\; {\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\), if they are equal and \(f_i^*, i \in [N]\) are the optimizers to Problem 2, then \((f^c)^*({\boldsymbol{x}}_{k_0}^{(0)}) = f_i^*({\boldsymbol{x}}_{k_i}^{(i)}), i \in [N]\), where \((f^c)^*\) is the \(c\)-conjugate function defined in Eqn. (?? ).

Proof We prove this by Contradiction. Without loss of generality, suppose \(\forall\; {\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\) are equal, and \((f^c)^*({\boldsymbol{x}}_{k_0}^{(0)}) \neq f_i^*({\boldsymbol{x}}_{k_i}^{(i)}), i \in [N]\). Let \({\mathcal{K}}= \{ k_1, \ldots, k_N \}\) and \(\Omega = \{ {\mathcal{X}}_1 \times \cdots \times {\mathcal{X}}_N \}\). According to the definition of the \(c\)-conjugate function, \[\begin{align} (f^c)^* \left( {\boldsymbol{x}}_{k_0}^{(0)} \right) {=} \inf \left\{ - \sum\limits_{j=1}^{N} f_j^* \left({\boldsymbol{x}}^{(j)}_{k_j} \right), \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\limits_{j=1}^{N} f_j^* \left({\boldsymbol{x}}^{(j)} \right) \right\} \right\}. \end{align}\] For simplicity, let \(\psi^*({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}) = \sum\nolimits_{j=1}^{N} f_j^* \left({\boldsymbol{x}}^{(j)} \right)\), we rewrite the above function as \[\begin{align} (f^c)^* \left( {\boldsymbol{x}}_{k_0}^{(0)} \right) = \inf \left\{- \psi^*\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right), \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\}\right\}. \end{align}\] Since \((f^c)^*({\boldsymbol{x}}_{k_0}^{(0)}) \neq f_i^*({\boldsymbol{x}}_{k_i}^{(i)}), i \in [N]\), for any \({\boldsymbol{x}}_i^{(0)}\), we have \[\begin{align} &\psi^*\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right) + c\left({\boldsymbol{x}}^{(0)}_i, {\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N} \right) \nonumber \\ > & \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \psi^*({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}) \right\} + c\left({\boldsymbol{x}}^{(0)}_i, {\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N} \right) \nonumber \\ =& \inf_{\Omega \setminus {\mathcal{K}}} \left\{ - \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) + c \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) + c\left({\boldsymbol{x}}^{(0)}_i, {\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N} \right) \right\} \nonumber \\ \geq& \inf_{\Omega \setminus {\mathcal{K}}} \left\{ - \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) + c\left({\boldsymbol{x}}^{(0)}_i, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) \right\}. \label{ineqn:lemma3} \end{align}\tag{4}\] Line 4 follows the fact that the definition of the cost function, \({\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\) are equal. Suppose the number of samples in each distribution is \(n\), \[\begin{align} & W^*(\mu_0, \ldots, \mu_N) = \sup_{F_c} \; \hat{h} (F_c) \\ =& \frac{1}{n} \sum\limits_{j \in {\mathcal{J}}_0} (f^c)^*\left({\boldsymbol{x}}_{j}^{(0)} \right) + \sum\limits_{i=1}^N \frac{1}{n} \sum\limits_{j \in {\mathcal{J}}_i} f_i^*\left({\boldsymbol{x}}_{j}^{(i)} \right) \\ =& \frac{1}{n} \sum\limits_{j \in {\mathcal{J}}_0} \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{j}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\} + \sum\limits_{i=1}^N \frac{1}{n} \sum\limits_{j \in {\mathcal{J}}_i} f_i^*\left({\boldsymbol{x}}_{j}^{(i)} \right) \\ =& \frac{1}{n} \sum\limits_{j \in {\mathcal{J}}_0} \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{j}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\} \\ &+ \frac{1}{n} \psi^* \left( {\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N} \right) + \frac{1}{n} \sum\limits_{j: {\boldsymbol{x}}_j^{(i)} \notin {\mathcal{K}}, i\in[N]} \psi^*\left({\boldsymbol{x}}^{(1)}_j, \ldots, {\boldsymbol{x}}^{(N)}_j \right). \end{align}\] We can always find another function \(\psi'\), such that \(\psi'\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) = \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right)\) for \(\forall {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \in \Omega \setminus {\mathcal{K}}\), and \[\begin{align} {-}\psi^*\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right) {>} {-} \psi'\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right) {>} \inf_{\Omega \setminus {\mathcal{K}}} \left\{ c \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) {-} \psi^*\left({\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\}. \end{align}\] In this case, \((f^c)'\left({\boldsymbol{x}}_{j}^{(0)}\right) = (f^c)^*\left({\boldsymbol{x}}_{j}^{(0)}\right), \forall j \in {\mathcal{J}}_0\), but \[\begin{align} \psi^*\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right) < \psi'\left({\boldsymbol{x}}^{(1)}_{k_1}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N}\right). \end{align}\] Therefore, \(\hat{F_{\psi}} > \hat{F_c}\), a contradiction. \(\square\)

Corollary 1 Given the cost function \(c(\cdot, \ldots, \cdot)\) defined in Definition 3, we assume \(f^*\) is \(1\)-Lipschitz continuous, the samples are bounded and the distance function satisfies \(d({\boldsymbol{x}}, {\boldsymbol{z}}) {\leq} d({\boldsymbol{x}}, {\boldsymbol{y}}) {+} d({\boldsymbol{y}}, {\boldsymbol{z}}) {\leq} C d({\boldsymbol{x}}, {\boldsymbol{z}})\), where \(C{\ge} 1\), when \(N{+}1\) samples \({\boldsymbol{x}}_{k_i}^{(i)} {\in} {\mathcal{X}}^{(i)}, i {\in} {\mathcal{I}}\) are close to each other, i.e., \(c({\boldsymbol{x}}_{k_0}^{(0)}, \ldots, {\boldsymbol{x}}_{k_N}^{(N)})\) is arbitrarily small, then \((f^c)^*({\boldsymbol{x}}_{k_0}^{(0)})\) would be arbitrarily close to \(f_i^*({\boldsymbol{x}}_{k_i}^{(i)}), i {\in} [N]\), where \(f_i^*, i {\in} [N]\) are the optimizers to Problem 2, and \((f^c)^*\) is the \(c\)-conjugate function defined in Eqn. (?? ).

Proof We prove the case of \(N{=}1\), it can be directly extended to the case of \(N{>}1\). Specifically, the potential function \(f_1 {:=} {-} f\). Based on the definition of the cost function, we have \(c({\boldsymbol{x}}, {\boldsymbol{y}}) {:=} d({\boldsymbol{x}}, {\boldsymbol{y}})\). If \({\boldsymbol{x}}_{k_1}^{(1)}\) is the optimal solution, i.e., \((f^c)^* \left({\boldsymbol{x}}_{k_0}^{(0)}\right) {=} f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right) {+} d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k_1}^{(1)} \right)\), then \[\begin{align} \left| (f^c)^*\left({\boldsymbol{x}}_{k_0}^{(0)}\right) - f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right) \right| = d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k_1}^{(1)} \right). \end{align}\] If \({\boldsymbol{x}}_{k'_1}^{(1)}\) is the optimal solution, i.e., \((f^c)^* \left({\boldsymbol{x}}_{k_0}^{(0)}\right) {=} f^*\left({\boldsymbol{x}}_{k'_1}^{(1)}\right) {+} d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k'_1}^{(1)} \right)\), then \[\begin{align} \left| (f^c)^*\left({\boldsymbol{x}}_{k_0}^{(0)}\right) - f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right) \right| =& \left| f^*\left({\boldsymbol{x}}_{k'_1}^{(1)}\right) + d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k'_1}^{(1)} \right) - f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right) \right| \\ \leq& \left| f^*\left({\boldsymbol{x}}_{k'_1}^{(1)}\right) - f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right) \right| + d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k'_1}^{(1)} \right) \\ \leq& d \left({\boldsymbol{x}}_{k'_1}^{(1)}, {\boldsymbol{x}}_{k_1}^{(1)}\right) + d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k'_1}^{(1)} \right) \\ \leq& C d \left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k_1}^{(1)} \right). \end{align}\] For the above two cases, when \({\boldsymbol{x}}_{k_1}^{(1)}\) is close to \({\boldsymbol{x}}_{k_0}^{(0)}\), then \(f^*\left({\boldsymbol{x}}_{k_1}^{(1)}\right)\) is also close to \((f^c)^*\left({\boldsymbol{x}}_{k_0}^{(0)}\right)\). \(\square\)

Lemma 3 Suppose \(f^*\) is an optimal solution to Problem 3 and \(\sum_{i\in{\mathcal{I}}} \lambda_i = 0\), then \(f^*\) satisfies \[\begin{align} f^*\left({\boldsymbol{x}}^{(0)}\right) = \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\nolimits_{j=1}^{N} \lambda_j f \left({\boldsymbol{x}}^{(j)} \right) \right\}, \quad \forall \; {\boldsymbol{x}}\in {\mathcal{X}}^0. \end{align}\] Proof Since \(f^*\) is the optimal solution to Problem 3, we have \[\begin{align} f^*\left({\boldsymbol{x}}^{(0)}\right) \leq \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\nolimits_{j=1}^{N} \lambda_j f \left({\boldsymbol{x}}^{(j)} \right) \right\}, \quad \forall \; {\boldsymbol{x}}\in {\mathcal{X}}^0. \end{align}\] We prove by contradiction. Without loss of generality, suppose there exists a \({\boldsymbol{x}}_{k_0}^{(0)}\), such that \[\begin{align} \label{ineqn:c95conjugate95contradiction} f^*\left({\boldsymbol{x}}^{(0)}\right) < \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\nolimits_{j=1}^{N} \lambda_j f \left({\boldsymbol{x}}^{(j)} \right) \right\}, \quad \forall \; {\boldsymbol{x}}\in {\mathcal{X}}^0. \end{align}\tag{5}\] Note that \({\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\) can not be equal, otherwise, \[\begin{align} f^* \left({\boldsymbol{x}}_{k_0}^{(0)}\right) =& -\sum\nolimits_{i\in[N]} \lambda_i f^* \left({\boldsymbol{x}}_{k_i}^{(i)}\right) \\ =& -\sum\nolimits_{i\in[N]} \lambda_i f^* \left({\boldsymbol{x}}_{k_i}^{(i)}\right) + c\left({\boldsymbol{x}}_{k_0}^{(0)}, {\boldsymbol{x}}_{k_1}^{(1)}, \ldots, {\boldsymbol{x}}_{k_N}^{(N)}\right) \\ \geq& \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{ -\sum\nolimits_{i\in[N]} \lambda_i f^* \left({\boldsymbol{x}}^{(i)}\right) + c\left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\}. \end{align}\] It is not consistent with Eqn. (5 ), thus \({\boldsymbol{x}}_{k_i}^{(i)} \in {\mathcal{X}}^{(i)}, i \in {\mathcal{I}}\) can not be equal.

Therefore, there exists another function \(f'\) such that \(f'\left( {\boldsymbol{x}}_{j}^{(i)} \right) = f^* \left( {\boldsymbol{x}}_{j}^{(i)} \right), \forall\; {\boldsymbol{x}}_{j}^{(i)} \in {\mathcal{X}}^i, i\in[N]\), and \(f'\left( {\boldsymbol{x}}_{j}^{(0)} \right) = f^* \left( {\boldsymbol{x}}_{j}^{(0)} \right), \forall\; {\boldsymbol{x}}_{j}^{(0)} \in {\mathcal{X}}^0 \setminus {\boldsymbol{x}}_{k_0}^{(0)}\) and \[f'\left( {\boldsymbol{x}}_{k_0}^{(0)} \right) = \inf_{{\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}} \left\{c \left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)} \right) - \sum\nolimits_{j=1}^{N} \lambda_j f \left({\boldsymbol{x}}^{(j)} \right) \right\}.\] It is easy to verify that \(f'\) satisfies the constraints in Problem 3 and \(\hat{h}(F'_{\lambda}) {>} \hat{h}(F^*_{\lambda})\), where \(\hat{h}(F'_{\lambda}) {=} \{ \lambda_0 f', \ldots, \lambda_N f' \}\) and \(\hat{h}(F^*_{\lambda}) {=} \{ \lambda_0 f^*, \ldots, \lambda_N f^* \}\). Therefore, it leads to a contradiction. \(\square\)

10 Proof of Theorem 1↩︎

Theorem 1 Suppose the domains are connected, \(c\) is continuously differentiable and that each \(\mu_i\) is absolutely continuous. If \((f_0, \ldots, f_N)\) and \((\lambda_0f, \ldots, \lambda_{N}f )\) are solutions to Problems 1, then there exist some constant \(\varepsilon_i\) for all \(i \in {\mathcal{I}}\) such that \(\sum_{i} \varepsilon_i = 0\), and \(f_i = \lambda_i f + \varepsilon_i\).

Proof First, using a convexification trick ref_gangbo1998optimal?, we are able to construct a \(c\)-conjugate solution \((f_0^c, f_1^c, \ldots, f_N^c)\) to the continuous case of Problem 1, where \(f_i^c\) can be defined as: \[\begin{align} \label{eqn:conjugate95ui} f_i^c \left( X^{(i)} \right) = \inf \left\{ c \left( X^{(0)}, \ldots, X^{(N)} \right) - \sum_{0 \leq j < i} f_j^c\left(X^{(j)}\right) - \sum_{i < j \leq N} f_j\left(X^{(j)}\right) \right\}, \quad \forall i \in {\mathcal{I}}. \end{align}\tag{6}\] Based on the definition of \(f_i^c\) and its optimality, we have \[\begin{align} \label{ieqn:conjugate95ui1} f_i^c \left( X^{(i)} \right) \leq \inf \left\{ c \left( X^{(0)}, \ldots, X^{(N)} \right) - \sum_{j \neq i} f_j^c \left( X^{(j)} \right) \right\}, \quad \forall i \in {\mathcal{I}}. \end{align}\tag{7}\] Then we iteratively obtain that \(f_i \left( X^{i} \right) \leq f_i^c \left( X^{i} \right)\), and using the definition of Equation (6 ), \[\begin{align} \label{ieqn:conjugate95ui2} f_i^c \left( X^{(i)} \right) =& \inf \left\{ c \left( X^{(0)}, \ldots, X^{(N)} \right) - \sum_{0 \leq j < i} f_j^c\left(X^{(j)}\right) - \sum_{i < j \leq N} f_j\left(X^{(j)}\right) \right\}, \quad \forall i \in {\mathcal{I}}\nonumber \\ \ge& \inf \left\{ c \left( X^{(0)}, \ldots, X^{(N)} \right) - \sum_{j \neq i} f_j^c\left(X^{(j)}\right) \right\}. \end{align}\tag{8}\] Combining Inequalities (7 ) and (8 ), we have a \(c\)-conjugate solution \(\left( f_0^c, f_1^c, \dots, f_N^c \right)\) which satisfies Definition 2. Let \(\varphi_i = \lambda_i f, -1 {\leq} \lambda {\leq} 1\), using the convexification trick, we are able to find \(c\)-conjugate solutions \((f_0^c, \ldots, f_N^c)\) and \((\varphi_0^c, \ldots, \varphi_N^c)\) to the continuous cases of Problems 2 and 3 such that \(f_i \leq f_i^c\) and \(\varphi_i \leq \varphi_i^c\). As \[\begin{align} \sum_{i \in {\mathcal{I}}} \int f_i \left(X^{(i)}\right) d \mu_i \left(X^{(i)}\right) = \sum_{i \in {\mathcal{I}}} \int f_i^c \left(X^{(i)}\right) d \mu_i \left(X^{(i)}\right), \end{align}\] we must have \(f_i = f_i^c\), \(\mu_i\) almost everywhere. Similarly, \(\varphi_i = \varphi_i^c\), \(\mu_i\) almost everywhere. We choose \(X^{(i)} \in {\mathcal{D}}_i\) where \(f_i^c\) and \(\varphi_i^c\) are differentiable. Then there exist \(X^{(j)}\) for all \(j \neq i\) such that \(( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} )\) in the support of \(\mu\). According to Theorem 4, we have \[\begin{align} f_i^c \left( X^{(i)} \right) - c \left( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} \right) = - \sum_{j \neq i} f_j^c \left(X^{(j)} \right). \end{align}\] Because \(f_i^c \left( Z^{(i)} \right) {-} c \left( X^{(0)}, \dots, X^{(i{-}1)}, Z^{(i)}, X^{(i)}, \ldots, X^{(N)} \right) \leq {-} \sum_{j \neq i} f_j^c \left(X^{(j)} \right)\) for all other \(Z^{(i)}\) we have the differential of \(f_i^c\) and \(c(\cdot)\) w.r.t. \(X^{(i)}\) as follows \[\begin{align} D_{X^{(i)}} f_i^c \left( X^{(i)} \right) = D_{X^{(i)}} c \left( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} \right). \end{align}\] Similarly, we have \[\begin{align} D_{X^{(i)}} \varphi_i^c \left( X^{(i)} \right) = D_{X^{(i)}} c \left( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} \right). \end{align}\] Therefore, we have \(D_{X^{(i)}} f_i^c \left( X^{(i)} \right) = D_{X^{(i)}} \varphi_i^c \left( X^{(i)} \right)\). As this equality holds for almost all \(X^{(i)}\), we have \(f_i^c \left( X^{(i)} \right) = \varphi_i^c \left( X^{(i)} \right) + \varepsilon_i\) and \(f_i \left( X^{(i)} \right) = \varphi_i \left( X^{(i)} \right) + \varepsilon_i\). Choosing any \(\left( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} \right)\) in the support of \(\gamma\), then \[\begin{align} \sum_{i \in {\mathcal{I}}} f_i^c \left( X^{(i)} \right) = c \left( X^{(0)}, \dots, X^{(i-1)}, X^{(i)}, X^{(i+1)}, \ldots, X^{(N)} \right) = \sum_{i \in {\mathcal{I}}} \varphi_i^c \left( X^{(i)} \right). \end{align}\] Therefore, \(\sum_i \varepsilon_i = 0\). \(\square\)

11 Error Bound of New Dual Formulation↩︎

Proof Based on the definitions of \(\hat{h}(F_{\lambda})\) and \({h}(F_{\lambda})\) and \(-1 {\leq} \lambda_i {\leq} 1, i {\in} {\mathcal{I}}\),

Suppose the function \(f\) is bounded in \([-\Delta, \Delta]\), then, according to Hoeffding’s inequality, we have

Using Inequality (10 ) and union bound over all \(i \in {\mathcal{I}}\), we further have the following inequality,

where \(\underline{n} = \min_{i \in {\mathcal{I}}} n_i\). Equivalently, we rewrite the above inequality as

Therefore, from Inequality (9 ), the following probability inequality satisfies:

Based on the definitions of \(\hat{\sigma}_{k_0, \ldots, k_N}\) and \(\sigma\), they are bounded in the interval \([0, 1]\). Using Hoeffding’s inequality, we have

where \(M = \prod\nolimits_{i} {n_i}\). Suppose the function \(f\) can be learned by a deep neural network with sufficient capacity, and it is able to solve Problem 3. Then, the inequality constraints \(\sum_{i} f\left({\boldsymbol{x}}^{(i)}_{k_i} \right) \leq c \left({\boldsymbol{x}}^{(0)}_{k_0}, \ldots, {\boldsymbol{x}}^{(N)}_{k_N} \right)\) are satisfied, and thus \(\hat{\sigma}_{k_0, \ldots, k_N} = 0\) for \(\forall\; {k_0, \ldots, k_N}\), we have \[P(|\sigma| > \epsilon) \leq 2e^{-2M\epsilon^2}.\] \(\square\)

12 Proof of Theorem 2↩︎

Theorem 2 If each generator \(g_{i} {\in} {\mathcal{G}}, i {\in} [N]\) is locally Lipschitz and satisfies Assumption 1 ref_arjovsky2017wasserstein? , then there exists a discriminator \(f\) to Problem 4, we have the gradient \(\nabla_{\theta_i} W(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, \ldots, \hat{{\mathbb{P}}}_{\theta_N}) = {-} \lambda_i^{+} {\mathbb{E}}_{{{\boldsymbol{x}}}\sim \hat{{\mathbb{P}}}_s} \left[ \nabla_{\theta_i} f(g_{i}({{\boldsymbol{x}}})) \right]\) for all \(\theta_i, i\in[N]\) when all terms are well-defined.

Proof Recall the optimization problem, we first define the value function as follows: \[\begin{align} V(\tilde{f}, \theta) &= {{\mathbb{E}}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ \tilde{f} ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i {{\mathbb{E}}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{\theta_i}} \left[ \tilde{f}({\boldsymbol{x}}) \right] \\ &= {{\mathbb{E}}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ \tilde{f} ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i {{\mathbb{E}}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ \tilde{f}({g_i} ({\boldsymbol{x}})) \right], \end{align}\] where \(\theta\) is the set of \(\theta_i, i\in[N]\), \(\tilde{f}\) lies in \(\tilde{{\mathcal{F}}}=\{ \tilde{f}: {\mathcal{X}}\to {\mathbb{R}}, \tilde{f} \in C_b({\mathcal{X}}), \tilde{f} \in \Omega \}\) and \(C_b({\mathcal{X}})\) is defined in (?? ). \[\begin{align} \Omega = \left\{ \tilde{f} : \tilde{f}({\boldsymbol{x}}) - \frac{1}{N}\sum\nolimits_{i \in [N]} \tilde{f} \left({\boldsymbol{x}}^{(i)}\right) \leq c\left({\boldsymbol{x}}^{(0)}, {\boldsymbol{x}}^{(1)}, \ldots, {\boldsymbol{x}}^{(N)}\right) \right\}, \end{align}\] where \({\boldsymbol{x}}^{(0)} {:=} {\boldsymbol{x}}\). Since \({\mathcal{X}}\) is compact, and based on Theorem 4, there is a solution \(f {\in} \tilde{{\mathcal{F}}}\) that satisfies \[\begin{align} W({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, {\ldots}, {{\mathbb{P}}}_{\theta_N}) = \sup_{\tilde{f} \in \tilde{{\mathcal{F}}}} V(\tilde{f}, \theta) = V(f, \theta). \end{align}\] Define the optimal set \({\mathcal{F}}^*(\theta) = \{ f \in \tilde{{\mathcal{F}}}: V(f, \theta) = W({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, {\ldots}, {{\mathbb{P}}}_{\theta_N}) \}\), and note that this set \({\mathcal{F}}^* (\theta)\) is non-empty. Based on envelope theorem ref_milgrom2002envelope?, we have \[\begin{align} \nabla_{\theta_i} W({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, {\ldots}, {{\mathbb{P}}}_{\theta_N}) = \nabla_{\theta_i} V(f, \theta) \end{align}\] for any \(f \in {\mathcal{F}}^*(\theta)\) when all terms are well-defined. Note that \(f\) exists since \({\mathcal{F}}^*(\theta)\) is non-empty for all \(\theta_i\). Then, we have \[\begin{align} \nabla_{\theta_i} W({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, {\ldots}, {{\mathbb{P}}}_{\theta_N}) =& \nabla_{\theta_i} V(f, \theta) \\ =& \nabla_{\theta_i} \left[ {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ {f} ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ {f}({g_i} ({\boldsymbol{x}})) \right] \right] \\ =& \nabla_{\theta_i} \left[ {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ {f} ({\boldsymbol{x}}) \right] - \frac{1}{N} {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ {f}({g_i}_{} ({\boldsymbol{x}})) \right] \right] \\ =& - \frac{1}{N} \nabla_{\theta_i} {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ {f}({g_i}_{} ({\boldsymbol{x}})) \right] \\ =& - \frac{1}{N} {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ \nabla_{\theta_i} {f}({g_i}_{} ({\boldsymbol{x}})) \right], \end{align}\] where the last equality holds by Lemma 4. \(\square\)

13 Proof of Theorem 3↩︎

Theorem 3 (Generalization bound)**** Let \({\mathbb{P}}_s\) and \({\mathbb{P}}_{\theta_i}\) be the continuous real and generated distributions, and \(\hat{{\mathbb{P}}}_s\) and \(\hat{{\mathbb{P}}}_{\theta_i}\) be the empirical real and generated distributions with at least \(n\) samples each. When \(n \ge \frac{C \kappa \Delta^2 \log(L\kappa/\epsilon) }{\epsilon^2}\), the following generalization bound is satisfied with probability at least \(1-e^{-\kappa}\), \[\begin{align} \left|W\left(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, {\ldots}, \hat{{\mathbb{P}}}_{\theta_N}\right) - W({\mathbb{P}}_s, {\mathbb{P}}_{\theta_1}, {\ldots}, {\mathbb{P}}_{\theta_N}) \right| \leq \epsilon. \end{align}\]

Proof Let \(\tilde{{\mathcal{W}}}\) be a finite set such that every point \(w \in {\mathcal{W}}\) is within distance \(\frac{\epsilon}{8L}\) of a point \(w' \in \tilde{{\mathcal{W}}}\), i.e., for every \(w \in {\mathcal{W}}\), there exist a \(w' \in {\mathcal{W}}\) such that \(\| w - w' \| \leq \frac{\epsilon}{8L}\). For any \({\boldsymbol{x}}\in {\mathbb{P}}_s\) or \({\boldsymbol{x}}\in \hat{{\mathbb{P}}}_s\), assume that \(f\) is \(L\)-Lipschitz continuous w.r.t. \(w\), then we have \[\begin{align} \label{ieqn:f95w95Lip} |f_{w'}({\boldsymbol{x}}) - f_{w}({\boldsymbol{x}})| \leq L \| w' - w \| \leq \frac{\epsilon}{8}. \end{align}\tag{11}\] Assume that \(f\) is bounded in \([-\Delta, \Delta]\). Using to Hoeffding’s inequality, for every \(w' \in \tilde{{\mathcal{W}}}\), we have \[\begin{align} P \left( \left| {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] - {\mathbb{E}}_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] \right| \ge \frac{\epsilon}{4} \right) \leq 2 \exp\left( -\frac{n\epsilon^2}{32 \Delta^2} \right). \end{align}\] Therefore, when \(n \ge \frac{C\kappa \Delta^2 \log(L\kappa/\epsilon) }{\epsilon^2}\) for a large enough constant \(C\), we have union bounds over all \(w' \in \tilde{{\mathcal{W}}}\). Then, we have \(|{\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} f_{w'}({\boldsymbol{x}}) - {\mathbb{E}}_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_{s} } f_{w'}({\boldsymbol{x}})| \leq \frac{\epsilon}{4}\) with the high probability at least \(1-\exp(-\kappa)\), where \(\kappa\) is the number of parameters in the discriminator \(f\). For every \(w \in {\mathcal{W}}\), we can find a \(w' \in \tilde{{\mathcal{W}}}\) such that the following satisfies \[\begin{align} \left| {\mathbb{E}}_{{\boldsymbol{x}}{\sim} {\mathbb{P}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] {-} {\mathbb{E}}_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] \right| \leq& \left| {\mathbb{E}}_{{\boldsymbol{x}}{\sim} {\mathbb{P}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] {-} {\mathbb{E}}_{{\boldsymbol{x}}{\sim} {{\mathbb{P}}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] \right| {+} \left| {\mathbb{E}}_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] {-} {\mathbb{E}}_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] \right| \\ &{+} \left| {\mathbb{E}}_{{\boldsymbol{x}}{\sim} {\mathbb{P}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] {-} {\mathbb{E}}_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{s}} \left[ f_{w'}({\boldsymbol{x}}) \right] \right| \\ \leq& \frac{\epsilon}{8} {+} \frac{\epsilon}{8} {+} \frac{\epsilon}{4} \leq \frac{\epsilon}{2}. \end{align}\] The third line holds by Inequality (11 ). Therefore, with high probability at least \(1-\exp(-\kappa)\), for every discriminator \(f_w\), \[\begin{align} \left| {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] - {\mathbb{E}}_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_{s}} \left[ f_w({\boldsymbol{x}}) \right] \right| \leq \frac{\epsilon}{2}. \end{align}\] Similarly, for \({\mathbb{P}}_{\theta_i}\) and \(\hat{{\mathbb{P}}}_{\theta_i}\), when \(n {\ge} \frac{C \kappa \Delta^2 \log(L\kappa/\epsilon) }{\epsilon^2}\), with the probability at least \(1{-}\exp({-}\kappa)\), \[\begin{align} \left| {\mathbb{E}}_{{\boldsymbol{x}}\sim {\mathbb{P}}_{\theta_i}} \left[ f_w({\boldsymbol{x}}) \right] - {\mathbb{E}}_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_{\theta_i}} \left[ f_w({\boldsymbol{x}}) \right] \right| \leq \frac{\epsilon}{2}, \quad \forall i=1, \ldots, N. \end{align}\] Let \(f_w\) be the optimal discriminator of \(W({\mathbb{P}}_s{,} {\mathbb{P}}_{\theta_1}{,} {\ldots}, {\mathbb{P}}_{\theta_N})\), we have \[\begin{align} W \left(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, \ldots, \hat{{\mathbb{P}}}_{\theta_N}\right) =& \sup_{f\in {\mathcal{F}}} \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_s} \left[ f ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i \left[ \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{\theta_i}} \left[ f \left({\boldsymbol{x}}\right) \right] \right] \\ \ge& \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_s} \left[ f_w ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i \left[ \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{\theta_i}} \left[ f_w \left({\boldsymbol{x}}\right) \right] \right] \\ =& \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim {{\mathbb{P}}}_s} \left[ f_w ({\boldsymbol{x}}) \right] - \frac{1}{N} \sum_i \left[ \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}{\sim} {{\mathbb{P}}}_{\theta_i}} \left[ f_w \left({\boldsymbol{x}}\right) \right] \right] - \left( \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim {{\mathbb{P}}}_s} \left[ f_w ({\boldsymbol{x}}) \right] - \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_s} \left[ f_w ({\boldsymbol{x}}) \right] \right)\\ &- \frac{1}{N} \sum_i \left[ \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}{\sim} \hat{{\mathbb{P}}}_{\theta_i}} \left[ f_w \left({\boldsymbol{x}}\right) \right] - \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}{\sim} {{\mathbb{P}}}_{\theta_i}} \left[ f_w \left({\boldsymbol{x}}\right) \right] \right]\\ \ge& W \left({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, \ldots, {{\mathbb{P}}}_{\theta_N}\right) - \epsilon. \end{align}\] Similarly, \(W \left({{\mathbb{P}}}_s, {{\mathbb{P}}}_{\theta_1}, \ldots, {{\mathbb{P}}}_{\theta_N}\right) \ge W \left(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, \ldots, \hat{{\mathbb{P}}}_{\theta_N}\right) - \epsilon\). Therefore, when the number of sample in each domain satisfying \(n \ge \frac{C \kappa \Delta^2 \log(L\kappa/\epsilon) }{\epsilon^2}\), then the following satisfies with the probability at least \(1-\exp(-\kappa)\), \[\begin{align} \left|W\left(\hat{{\mathbb{P}}}_s, \hat{{\mathbb{P}}}_{\theta_1}, {\ldots}, \hat{{\mathbb{P}}}_{\theta_N}\right) - W({\mathbb{P}}_s, {\mathbb{P}}_{\theta_1}, {\ldots}, {\mathbb{P}}_{\theta_N}) \right| \leq \epsilon. \end{align}\] We conclude the proof. \(\square\)

14 Proof of Lemma 1↩︎

Lemma 1 (Constraints relaxation)* If the cost function \(c(\cdot)\) is measured by \(\ell_2\) norm, then there exists a constant \(L_f {\ge} 1\) such that discriminator \(f\) satisfies the following constraint: \[\begin{align} \sum_i \frac{\left| f({\boldsymbol{x}}) - f \left(\hat{{\boldsymbol{x}}}^{(i)} \right) \right| }{ \left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\| } \leq L_f. \end{align}\]*

Proof When the inequality constraints in Problem 4 is satisfied, and without loss of generality, we assume that \(\frac{1}{N} \sum \left| f({\boldsymbol{x}}) - f\left({\boldsymbol{x}}^{(i)}\right) \right| \leq c( {\boldsymbol{x}}^{(0)}, \ldots, {\boldsymbol{x}}^{(N)} )\). Let \(c:= c( {\boldsymbol{x}}^{(0)}, \ldots, {\boldsymbol{x}}^{(N)} )\), we have \[\begin{align} \frac{1}{Nc} \min\limits_i \left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\| \sum_i \frac{ \left| f({\boldsymbol{x}}) - f\left(\hat{{\boldsymbol{x}}}^{(i)}\right) \right|}{\left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\|} \leq \frac{1}{Nc} \sum_i \frac{ \left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\| \left| f({\boldsymbol{x}}) - f\left(\hat{{\boldsymbol{x}}}^{(i)}\right) \right|}{\left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\|} \leq 1. \end{align}\] Let \(L_f = Nc / \min\limits_i \left\| {\boldsymbol{x}}- \hat{{\boldsymbol{x}}}^{(i)} \right\| \ge 1\), we conclude the proof. \(\square\)

In Lemma 1, the constant \(L_f\) is related to the cost function \(c\). In this sense, it captures the dependency among domains.

15 Discussions on Lipschitz Condition↩︎

From the following proposition, the assumption that the potential function is Lipschitz continuous is strong to enforce the inequality constraints. It would cause misleading results for our problem setting.

Proof If the potential function is 1-Lipschitz continuous, i.e.,  \[\begin{align} \left| f({\boldsymbol{x}}) - f\left({\boldsymbol{x}}^{i}\right) \right| \leq \left\| {\boldsymbol{x}}- {\boldsymbol{x}}^{i} \right\|, \quad i \in [N]. \end{align}\] Then, based on the definition of the potential and for all variables, we have \[\begin{align} \frac{1}{N} \sum_{i \in [N]} \left| f({\boldsymbol{x}}) - f\left({\boldsymbol{x}}^{(i)}\right) \right| \leq \sum_{i \in [N]} \left\| {\boldsymbol{x}}- {\boldsymbol{x}}^{i} \right\|. \end{align}\] \(\square\)

16 Comparisons with GAN Methods↩︎

16.1 Differences between MWGAN and WGAN↩︎

In this paper, the proposed MWGAN essentially differs from WGAN even when \(\lambda_i^+ = 1/N\): 1) MWGAN considers and incorporates multi-domain correlations into the inequality constraints to improve the image translation performance. WGAN focuses on image generation tasks and cannot directly deal with multi-domain correlations. 2) The objectives of two methods are different in the formulation. 3) In the algorithm, MWGAN uses gradient penalty to deal with inequality constraints; while WGAN relies on the weight clipping.

16.2 Comparisons with Image-to-image Translation Methods↩︎

CycleGAN ref_zhu2017unpaired? is a two-domain translation method, but it can be used in the multi-domain image translation task. It means that CycleGAN needs to learn multiple two-domain translation tasks. Moreover, CycleGAN performs well on the unbalanced translation task, because it independently optimizes multiple individual networks for the multi-domain image translation task. StarGAN ref_choi2018stargan? and UFDN ref_liu2018ufdn? are multi-domain image translation methods, however, they may not exploit multi-domain correlations to achieve good performance on the unbalanced translation task.

16.2.0.1 Difference between MWGAN and StarGAN.

The adversarial learning of MWGAN is different from StarGAN. Specifically, MWGAN cannot be interpreted as distribution matching between source and a mixture of target distributions. Let \(\bar{{\mathbb{P}}}_{\theta}\) be a mixture distribution over \(({\mathbb{P}}_{\theta_1}, \ldots, {\mathbb{P}}_{\theta_N})\). Note that \(\bar{{\mathbb{P}}}_{\theta}\) is related to the batch size. When the batch size is too small, then \(\bar{{\mathbb{P}}}_{\theta}\) cannot guarantee to contain all domains. StarGAN minimizes the following optimization problem: \[\begin{align} \label{obj:stargan} \max\nolimits_f {\mathbb{E}}_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_s} [f({\boldsymbol{x}})] - {\mathbb{E}}_{\hat{{\boldsymbol{x}}} {\sim} \bar{{\mathbb{P}}}_{\theta}} \left[ f \left(\hat{{\boldsymbol{x}}}\right) \right]. \end{align}\tag{12}\] In contrast, MWGAN minimizes the following optimization problem, \[\begin{align} \label{obj:mwgan} \max\nolimits_f \mathop{{{\mathbb{E}}}}\nolimits_{{\boldsymbol{x}}\sim \hat{{\mathbb{P}}}_s} \left[ f ({\boldsymbol{x}}) \right] - \sum\nolimits_i \lambda_i^+ \mathop{{{\mathbb{E}}}}\nolimits_{\hat{{\boldsymbol{x}}} {\sim} \hat{{\mathbb{P}}}_{\theta_i}} \left[ f \left(\hat{{\boldsymbol{x}}}\right) \right]. \end{align}\tag{13}\] When \(\lambda_i^+ {=} 1/N\) and \(\bar{{\mathbb{P}}}_{\theta}\) is uniformly drawn from every target generated distribution, the objective (12 ) is equivalent to the objective (13 ). However, when \(\lambda_i^+ {\neq} 1/N\) and the batch size is small, the objective (12 ) is not equivalent to the objective (13 ). Besides, the inequality constraints in MWGAN are related to the correlation among all domains, while StarGAN only considers the source domain and certain target domain. Therefore, the adversarial learning of MWGAN is different from StarGAN.

17 Effectiveness of One Potential Function↩︎

17.1 Comparisons between one and multiple potential functions↩︎

We focus on multiple marginal matching, where multiple target domains often contain cross-domain correlations. Thus, a shared potential function helps to exploit cross-domain correlations to improve performance (see results in Table 5 on the Edge\(\rightarrow\)CelebA task). Second, training a shared function using entire data of all domains is much easier than training \(N{+}1\) potentials (one per domain).

17.2 Weight Setting and Performance vs #domains (\(N\))↩︎

With \(\lambda_i^+ = 1/N\), each generator provides equal gradient feedbacks in each target domain and helps to exploit cross-domain correlations in adversarial learning. We apply MWGAN on the Edge\(\rightarrow\)CelebA translation task with different \(N\). From Table 6, more domains help to improve the performance in terms of FID by exploiting cross-domain correlations.

18 Toy Dataset↩︎

18.1 7 Gaussian Distributions↩︎

In the first row of Figure 3, we generate 7 Gaussian distributions as the real data distribution, where the center of initial distribution (green) is \((0, 0)\), and the centers of 6 target distributions (red) are \((3/2, 0)\), \((-3/2, 0)\), \((3/4, 3\sqrt{3}/4)\), \((-3/4, 3\sqrt{3}/4)\), \((3/4, -3\sqrt{3}/4)\) and \((-3/4, -3\sqrt{3}/4)\). For each Gaussian distribution, the variance is \(0.04\), and we generate 256 samples. The synthetic data distribution (orange) is generated from the Gaussian centered at \((0, 0)\).

18.2 1 Gaussian and 6 Uniform Distributions↩︎

In the second row of Figure 3, we generate 1 Gaussian distribution and 6 uniform distributions as the real data distributions, where the center of initial distribution (green) is also \((0, 0)\), and the centers of 6 uniform distributions (red) are \((3/2, 0)\), \((-3/2, 0)\), \((3/4, 3\sqrt{3}/4)\), \((-3/4, 3\sqrt{3}/4)\), \((3/4, -3\sqrt{3}/4)\) and \((-3/4, -3\sqrt{3}/4)\). For each uniform distribution, we generate 256 samples in a square around the center (length is 0.4). The synthetic data distribution (orange) is generated from the Gaussian centered at \((0, 0)\).

18.3 Toy Experiment Settings↩︎

We use fully connected neural network architecture for all methods. The generator contains 3 hidden layers with 512 units followed by ReLU. The discriminator contains 2 hidden layers with 512 units followed by ReLU. We use Adam as the optimizer with \(\beta_1\) = 0.5 and \(\beta_2\) = 0.999 and the learning rate of all methods is set to 0.0001. The hyper-parameters follow the default setting of these methods.

19 Details of Classification on CelebA↩︎

In the facial attribute translation experiment (In Section 6.5 of the main submission), we train a classifier on CelebA to obtain a near-perfect accuracy, and test on blond hair, eyeglasses, mustache and pale skin to obtain classifier accuracy of 99.62%, 99.94%, 99.76% and 97.96%, respectively. In the same way, we use this classifier to test on synthesized single and multiple attributes for the considered methods.

20 More evaluations with Amazon Mechanical Turk (AMT)↩︎

For more quantitative evaluations, we conduct a perceptual evaluation using AMT to assess the performance on the Edge\(\rightarrow\)CelebA translation task, following the settings of StarGAN ref_choi2018stargan?. From Table 7, MWGAN wins significant majority votes for the best perceptual realism, quality and transferred attributes for all facial attributes.

21 Influences of Inner- and Inter-domain Constraints↩︎

In this section, we evaluate the influences of inner-domain constraints and inter-domain constraints on the edge\(\rightarrow\)celebA task, respectively. Specifically, we compare the FID values with different \(\alpha\) (inner-domain constraint weights) and different \(\tau\) (inter-domain constraint weights). The value of \(\alpha\) and \(\tau\) is selected among [0, 0.1, 1, 10, 100]. Each experiment only evaluates one constraint and fix other parameters. To evaluate the influence of \(\alpha\), we empirically set \(\tau=10\). Otherwise, we set \(\alpha=10\) to evaluate the influence of \(\tau\). The results are shown in Tables ¿tbl:table:alation95edge2hair? and [tbl:table:alation95edge2hair2].

Specifically, when \(\alpha{=}0\) or \(\tau {=} 0\), MWGAN obtains the worst performance. In other words, when we abandon any one of the inner or inter-domain constraints, we cannot achieve a satisfactory result. This demonstrates the effectiveness of both constraints. Besides, MWGAN achieves the best performance when setting both weights to 10. This means that when setting some reasonable constraint weights, we can achieve a better trade-off between the optimization objective and constraints, and thus obtain better performance.

   

22 Influences of the parameter \(L_f\)↩︎

In this section, we evaluate the influences of the parameter \(L_f\) on the edge\(\rightarrow\)celebA task. Specifically, we compare the FID values with different \(L_f\) in the inter-domain constraints. The value of \(L_f\) is selected among [1, 3, 10, 50], where 3 is the number of domains. Each experiment only evaluates one constraint and fix other parameters. The results are shown in Table 8.

In Tables 8, MWGAN achieves the best performance when setting both weights to 3. This means that when setting some reasonable constants, we can achieve a better gradient penalty between the source and each target domain, and thus obtain better performance by exploiting the cross-domain correlations.

23 Network Architecture and More Implementation Details↩︎

23.0.0.1 Network architecture.

The classifier \(\phi\) shares the same structure except for the output layer with \(f\). The network architectures of the discriminator and generators of MWGAN are shown in Tables 9 and 10. We split each generator to an encoder and a decoder, where all generators share the same encoder but with different decoders. For the encoder and decoder network, instead of using batch normalization ref_guo2018aaai?, ref_Ioffe2015icml?, we use instance normalization in all layers except the last output layer of the decoder. For the discriminator network, we use PatchGAN network which is made up of fully convolutional networks, and we use Leaky ReLU with a negative slope of 0.01. We use the following abbreviations: \(h\): the width size of input image, \(w\): the height size of input image, \(n_d\): the number of transferred domains(exclude source domain), N: the number of output channels, K: kernel size, S: stride size, P: padding size, IN: instance normalization.

23.0.0.2 More implementation details.

For Loss (1 ), we use mean square loss and cross-entropy loss for the balanced and imbalanced translation task, respectively. In the experiments, we find that introducing an identity mapping loss ref_zhu2017unpaired? helps improve the quality of generated images on the facial attribute translation task. Specifically, the identity mapping loss is defined as: \(\mathcal{L}_{\text{idt}}(g_i)= \mathbb{E}_{{\boldsymbol{x}}\sim \mathbb{\hat{P}}_{t_i}} \left[ \left\| g_i({\boldsymbol{x}})-{\boldsymbol{x}}\right\|_1 \right]\), where \(\mathbb{\hat{P}}_{t_i}\) is an empirical distribution in the \(i\)-th target domain. We use the identity mapping loss for all target domains.

24 Additional Qualitative Results↩︎

24.1 Results on CelebA↩︎

24.2 Results on Edge\(\rightarrow\)CelebA↩︎

24.3 Results on Painting Translation↩︎

References↩︎

---

1. Authors contributed equally.↩︎

2. Corresponding author.↩︎

3. The source code of our method is available: https://github.com/caojiezhang/MWGAN.↩︎