# DC-MMD-GAN: A New Maximum Mean Discrepancy Generative Adversarial Network Using Divide and Conquer
## 3 Divide and Conquer MMD-GANs
\(\hat{R}_{re}\) is reconstructed data. m is batch size and \(R=\left\{r_{i}\right\}_{i=1}^{n}\), \(r\sim\mathbb{P}_{r}\) i.i.d. We freeze auto-encoder parameters and pass all training images to well-trained auto-encoder. Each image \(r_{i}\) is mapped to a vector of embedding \(e_{i}\). \(E_{all}\) is a set containing all embedding \(e_{i}\). Based on learned embedding representation, we conduct k-means on \(E_{all}\) and obtain \(c\) clusters: \(E_{i},\ i\in\left\{1,...,c\right\}\). Hereby training images are divided into \(c\) subsets \(R_{i},\ i\in\left\{1,...,c\right\}\) respectively according to clustered set of embedding. Each subset will be fed to a sub-model. Each sub-model is trained independently. For conquer task, we adopt a weighted-sum unbiased empirical estimate of \(\text{MMD}^{2}\) with tighter deviation bound: \(\text{MMD}_{\text{dc}}{}^{2}\), which can provide more precise gradients for training. All sub-problems of training independently, we integrate the empirical estimation \(\left\{\text{MMD}_{\text{em}}{}^{2}(R_{1},S_{1}),\text{MMD}_{\text{em}}{}^{2} (R_{2},S_{2}),...,\text{MMD}_{\text{em}}{}^{2}(R_{c},S_{c})\right\}\). \(R_{c}\) is a batch of training images and \(S_{c}\) is a batch of generated images generated by the c-th sub-model. We compute a weight-sum value of all estimate: \(\text{MMD}_{\text{dc}}{}^{2}\), with a tighter deviation bound. We set the weight parameter to \(\frac{1}{c}\). \[\text{MMD}_{\text{dc}}{}^{2}(R,S)=\sum_{i=1}^{c}w_{i}\text{MMD}_{\text{em}}{} ^{2}(R_{i},S_{i}). \tag{10}\]  
Each sub-model is updated synchronously by optimizing \(\text{MMD}_{\text{dc}}{}^{2}\)  
\[\min_{G_{sub}}\min_{D_{sub}}\text{MMD}_{\text{dc}}{}^{2}\left(R,S\right), \tag{11}\]  
where \(G_{sub}\) is generator and \(D_{sub}\) is discriminator of sub-model. As shown in the Theorem 1, the new loss function \(\text{MMD}_{\text{dc}}{}^{2}\) can be seen as an unbiased estimator of expected value \(\text{MMD}^{2}\). Therefore, optimizing \(\text{MMD}_{\text{dc}}{}^{2}\) can give correct direction of convergence when training DC-MMD-GANs. **Theorem 1**. : _Assuming that \(\sum_{i=1}^{c}w_{i}=1\), \(\text{MMD}_{\text{dc}}{}^{2}\) is an unbiased estimator of \(\text{MMD}^{2}\)._  
Proof of Theorem 1.: According to [16], for each \(\text{MMD}_{\text{em}}{}^{2}(R_{i},S_{i})\), \(\mathbb{E}(\text{MMD}_{\text{em}}{}^{2}(R_{i},S_{i}))=\text{MMD}^{2}\). \[\mathbb{E}(\text{MMD}_{\text{dc}}{}^{2}(R,S))=\sum_{i=1}^{c}w_{i}\mathbb{E}( \text{MMD}_{\text{em}}{}^{2}(R_{i},S_{i})=\sum_{i=1}^{c}w_{i}\text{MMD}^{2}= \text{MMD}^{2}.\]  
\(\square\)  
The calculation of \(\text{MMD}_{\text{dc}}{}^{2}\) can be seen as a type of unbiased estimator used in the B-test [31], which is an average over empirical estimate of \(\text{MMD}^{2}\) computed on subsets. According to Equation (5), \(\text{MMD}_{\text{em}}{}^{2}\) with batch size equaling to \(m\) can be obtained by computing \(m^{2}\) terms of \(k(\cdot,\cdot)\). \(\text{MMD}_{\text{em}}{}^{2}\) with batch size equaling to \(cm\) can be obtained by computing \(c^{2}m^{2}\) terms. By using the divide-and-conquer strategy, \(\text{MMD}_{\text{dc}}{}^{2}\) is computed using \(c\)\(\text{MMD}_{\text{em}}{}^{2}\) according to Equation (10). So \(\text{MMD}_{\text{dc}}{}^{2}\) can be obtained by computing \(cm^{2}\) terms. Compared to compute the \(\text{MMD}_{\text{em}}{}^{2}\) with batch size equaling to \(cm\), we avoid the calculation of cross terms when we calculated \(\text{MMD}_{\text{dc}}{}^{2}\)The cross terms are the information between different subsets and has been reduced by the division task. \(\text{MMD}_{\text{dc}}{}^{2}\) has same deviation bound as \(\text{MMD}_{\text{em}}{}^{2}\) with batch size equaling to \(cm\) according to [31].