Title: MMD GAN WITH RANDOM-FOREST KERNELS CONFERENCE SUBMISSIONS

Abstract: In this paper, we propose a novel kind of kernel, random forest kernel, to enhance the empirical performance of MMD GAN. Different from common forests with deterministic routings, a probabilistic routing variant is used in our innovated random-forest kernel, which is possible to merge with the CNN frameworks. Our proposed random-forest kernel has the following advantages: From the perspective of random forest, the output of GAN discriminator can be viewed as feature inputs to the forest, where each tree gets access to merely a fraction of the features, and thus the entire forest benefits from ensemble learning. In the aspect of kernel method, random-forest kernel is proved to be characteristic, and therefore suitable for the MMD structure. Besides, being an asymmetric kernel, our random-forest kernel is much more flexible, in terms of capturing the differences between distributions. Sharing the advantages of CNN, kernel method, and ensemble learning, our random-forest kernel based MMD GAN obtains desirable empirical performances on CIFAR-10, CelebA and LSUN bedroom data sets. Furthermore, for the sake of completeness, we also put forward comprehensive theoretical analysis to support our experimental results.

1. INTRODUCTION:

Generative adversarial nets (GANs; Goodfellow et al., 2014) are well-known generative models, which largely attribute to the sophisticated design of a generator and a discriminator which are trained jointly in an adversarial fashion. Nowadays GANs are intensely used in a variety of practical tasks, such as image-to-image translation (Tang et al., 2019; Mo et al., 2019) ; 3D reconstruction (Gecer et al., 2019) ; video prediction (Kwon & Park, 2019) ; text-to-image generation (Zhu et al., 2019) ; just to name a few. However, it's well-known that the training of GANs is a little tricky, see e.g. (Salimans et al., 2016) . One reason of instability of GAN training lies in the distance used in discriminator to measure the divergence between the generated distribution and the target distribution. For instance, concerning with the Jensen-Shannon divergence based GANs proposed in Goodfellow et al. (2014) , Arjovsky & Bottou (2017) points out that if the generated distribution and the target distribution are supported on manifolds where the measure of intersection is zero, Jensen-Shannon divergence will be constant and the KL divergences be infinite. Consequently, the generator fails to obtain enough useful gradient to update, which undermines GAN training. Moreover, two non-overlapping distributions may be judged to be quite different by the Jensen-Shannon divergence, even if they are nearby with high probability.

As a result, to better measure the difference between two distributions, Integral Probability Metrics (IPM) based GANs have been proposed. For instance, Arjovsky et al. (2017) utilizes Wasserstein distance in GAN discriminator, while Li et al. (2017) adopts maximum mean discrepancy (MMD), managing to project and discriminate data in reproducing kernel Hilbert space (RKHS). To mention, the RKHS with characteristic kernels including Gaussian RBF kernel (Li et al., 2017) and rational quadratic kernel (Bińkowski et al., 2018) has strong power in the discrimination of two distributions, see e.g. (Sriperumbudur et al., 2010) .

In this paper, inspired by non-linear discriminating power of decision forests, we propose a new type of kernel named random-forest kernel to improve the performance of MMD GAN discriminator. In order to fit with back-propagation training procedure, we borrow the decision forest model with stochastic and differentiable decision trees from Kontschieder et al. (2015) in our random-forest kernel. To be specific, each dimension of the GAN discriminator outputs is randomly connected to one internal node of a soft decision forest, serving as the candidate to-be-split dimension. Then, the tree is split with a soft decision function through a probabilistic routing. Other than the typical decision forest used in classification tasks where the value of each leaf node is a label, the leaf value of our random forest is the probability of a sample x i falling into a certain leaf node of the forest. If the output of the discriminator is denoted as h θ N (x i ) and the probability output of the t-th tree is denoted as µ t (h θ N (x i ); θ F ), the random forest kernel k RF can be formulated as

k RF (x i , x j ; θ F ) = 1 T T t=1 µ t (h θ N (x i ); θ F ), µ t (h θ N (x j ); θ F ) ,

where T is the total number of trees in the forest, θ N and θ F denote the parameters of the GAN discriminator and the random forest respectively.

Recall that random forest and deep neural networks are first combined in Kontschieder et al. (2015) , where differentiable decision tree model and deep convolutional networks are trained together in an end-to-end manner to solve classification tasks. Then, Shen et al. (2017) extends the idea to label distribution learning, and Shen et al. (2018) makes further extensions in regression regime. Moreover, Zuo & Drummond (2017) , Zuo et al. (2018) and Avraham et al. (2019) also introduce deep decision forests. Apart from the typical ensemble method that averages the results across trees, they aggregate the results by multiplication. As for the combination of random forest and GAN, Zuo et al. (2018) introduce forests structure in GAN discriminator, combining CNN network and forest as a composited classifier, while Avraham et al. (2019) uses forest structure as one of non-linear mapping functions in regularization part.

On the other hand, in the aspect of relationship between random forest and kernel method, Breiman (2000) initiates the literature concerning the link. He shows the fact that a purely random tree partition is equivalent to a kernel acting on the true margin, of which form can be viewed as the probability of two samples falling into the same terminal node. Shen & Vogelstein (2018) proves that random forest kernel is characteristic. Some more theoretical analysis can be found in Davies & Ghahramani (2014) , Arlot & Genuer (2014) , Scornet (2016) . However, despite their theoretical breakthroughs, forest decision functions used in these forest kernels are non-differentiable hard margins rather than differentiable soft ones, and thus cannot be directly used in back propagation regime.

To the best of our knowledge, MMD GAN with our proposed random-forest kernel is the first to combine random forest with deep neural network in the form of kernel MMD GAN. Through theoretical analysis and numerical experiments, we evaluate the effectiveness of MMD GAN with our random-forest kernel. From the theoretical point of view, our random-forest kernel enjoys the property of being characteristic, and the gradient estimators used in the training process of random-forest kernel GAN are unbiased. In numerical experiments, we evaluate our random-forest kernel under the setting of both the original MMD GAN (Li et al., 2017) and the one with repulsive loss (Wang et al., 2019) . Besides, we also compare our random-forest kernel with Gaussian RBF kernel (Li et al., 2017) , rational quadratic kernel (Bińkowski et al., 2018) , and bounded RBF kernel (Wang et al., 2019) . As a result, MMD GAN with our random-forest kernel outperforms its counterparts with respect to both accuracy and training stability.

This paper is organized as follows. First of all, we introduce some preliminaries of MMD GAN in Section 2. Then we review the concept of deep random forest and show how it is embedded within a CNN in 3.1. After that, random-forest kernels and MMD GAN with random-forest kernels are proposed in 3.2 and 3.3 respectively. Besides, the training techniques of MMD GAN with random-forest kernel are demonstrated in Section 3.4 and the theoretical results are shown in Section 3.5. Eventually, Section 4 presents the experimental setups and results, including the comparison between our proposed random-forest kernel and other kernels. In addition, all detailed theoretical proofs are included in the Appendices.

2. MMD GAN:

GANs are recently introduced as a novel way of training a generative model. To learn a distribution P X , we build an adversarial model composed of two parts, the generator G and the discriminator D.

The generative model captures the data distribution P X , by building a mapping function G : Z → X from a prior noise distribution P Z to data space. While the discriminative model D : X → R is used to distinguish generated distribution P Y from real data distribution P X .

Taking X, X ∼ P X and Y, Y ∼ P Y := P G (Z) where Y := G(Z) and Y := G(Z ), the squared MMD is expressed as

EQUATION

The loss of generator and discriminator in MMD GAN proposed in Li et al. (2017) is:

min G L G = MMD 2 [P X , P Y ], min D L D = -MMD 2 [P X , P Y ].

Wang et al. ( 2019) proposed MMD GAN with repulsive loss, where the objective functions for G and D are:

min G L G = MMD 2 [P X , P Y ], min D L D = E X,X k(X, X ) -E Y,Y k(Y, Y ).

Given i.i.d. samples D X = {x 1 , . . . , x n } ∼ P X and D Y = {G(z 1 ), . . . , G(z m )} ∼ P Y , we can write an unbiased estimator of the squared MMD in terms of k as

MMD 2 u [D X , D Y ] = 1 n(n -1) n i=1 n j =i k(x i , x j ) + 1 m(m -1) m i=1 m j =i k(y i , y j ) - 2 nm n i=1 m j=1 k(x i , y j ).

(

EQUATION

When k is a characteristic kernel, we have MMD 2 [P X , P Y ] ≥ 0 with equality applies if and only if P X = P Y . The best-known characteristic kernels are gaussian RBF kernel and rational quadratic kernel (Bińkowski et al., 2018) .

3. RANDOM-FOREST KERNEL:

In this section, we review a stochastic and differentiable variant of random forest and how it is embedded within a deep convolutional neural network proposed in Kontschieder et al. (2015) . Then we propose random-forest kernel and we apply it in MMD GAN. We illustrate the advantages of our random-forest kernel, show the training technique of MMD GAN with random-forest kernel, and study its theoretical properties.

3.1. DEEP RANDOM FOREST:

Suppose that a random forest consists of T ∈ N random trees. For the t-th tree in the forest, t ∈ {1, . . . , T }, we denote N t := {d t j } |Nt| j=1 as the set of its internal nodes and if T trees have the same structure, then we have |N t | = |N |, see Figure 1 . Furthermore, we denote L t as the set of its leaf nodes and θ t F as the parameters of the t-th tree. Here we introduce the routing function µ t (x; θ t F ) which indicates the probability of the sample x falling into the -th leaf node of the t-th tree. In order to provide an explicit form for the routing function µ t (x; θ t F ), e.g. the thick black line in Figure 1 , we introduce the following binary relations that depend on the tree structure: d t j is true, if belongs to the left subtree of node d t j , and d t j is true, if belongs to the right subtree of node d t j . Moreover, let p t j (x; θ t F ) be the decision function of the j-th internal node in the t-th tree, that is the probability of the sample x falling into the left child of node d t j in the t-th tree. Then, µ t can be expressed by these relations as Now, let us derive the explicit form of the decision function p t j (x; θ t F ). Here, to utilize the power of deep learning, we consider using the convolutional neural network to construct decision functions of random forest.

µ t (x; θ t F ) = d t j ∈R t p t j (x; θ t F )

To be specific, given the parameter θ N trained from a CNN network, we denote h(•; θ N ) as the d -dimension output of a convolutional neural network, which is the unit of the last fullyconnected layer in the CNN, and h i (•; θ N ) is the i-th element of the CNN output. We denote C : {1, . . . , T |N |} → {1, . . . , d } as the connection function, which represents the connection between the internal node d t j and the former CNN output h i . Note that during the whole training process, the form of the connection function C is not changed and every internal node d t j is randomly assigned to an element h C(T (t-1)+j) (•; θ). If we choose the sigmoid function σ(x) = (1+e -x ) -1 as the decision function, and let the parameters of the t-th tree be θ t F := (w t , b t ) with w t = (w t 1 , . . . , w t |N | ) and b t = (b t 1 , . . . , b t |N | ), then the decision functions p t j delivering a stochastic routing can be defined as

p t j (x; θ N , θ t F ) = σ w t j • h C(T (t-1)+j) (x; θ N ) + b t j .

For example, we have the probability

p 1 1 (x; θ N , θ 1 F ) = σ(w 1 1 h C(1) (x; θ N ) + b 1 1 )

for the node in the first layer, see Figure 2 for an explicit example of the random forest. 

is µ 1 4 (x; θN , θ 1 F ) = 1 -σ(w 1 1 h d (x; θN ) + b 1 1 ) 1 -σ(w 1 3 h1(x; θN ) + b 1 3 ) .

Every leaf node in each tree has a unique road R t from node 1 to node with length |R t | = log 2 (|L t |). Then, for the every leaf node of the t-th tree, we have

EQUATION

where Lf denotes the set of all left son nodes of its father node.

Here, we propose the random-forest kernel as follows:

Definition 1 (Random-Forest Kernel) Let x, y be a pair of kernel input, let θ t F = (w t , b t ) denotes the weights and bias of the t-th tree of the random forest, and θ F := (θ t F ) T t=1 . The random-forest kernel can be defined as

k RF x, y; θ F = 1 T T t=1 ∈Lt µ t (x; θ t F )µ t (y; θ t F ) = 1 T T t=1 µ t x; θ t F ), µ t (y; θ t F ) = 1 T µ (T ) (x; θ F ), µ (T ) (y; θ F ) ,

where L t denotes the set of leaf nodes in the t-th tree, µ t = (µ t ) ∈Lt and µ (T ) = (µ t ) T t=1 .

3.3. MMD GAN WITH RANDOM-FOREST KERNELS:

We write

k(x, x ) := k RF h θ N (x), h θ N (x ); θ F

and introduce the objective functions of MMD GAN with random-forest kernel by

min ψ L G = MMD 2 [P X , P Y ] = E X,X k(X, X ) -2E X,Y k(X, Y ) + E Y,Y k(Y, Y ), min θ N ,θ F L D = -MMD 2 [P X , P Y ] + R = -E X,X k(X, X ) + 2E X,Y [k(X, Y )] -E Y,Y k(Y, Y ) + R,

where y = G ψ (z), z is noise vector, and R is the regularizer of random-forest kernel (the detail is shown in Section 3.4). In addition, the objective functions of MMD GAN with repulsive loss are

min ψ L G = MMD 2 [P X , P Y ] = E X,X k(X, X ) -2E X,Y k(X, Y ) + E Y,Y k(Y, Y ), min θ N ,θ F L D = -MMD 2 [P X , P Y ] + R = E X,X k(X, X ) -E Y,Y k(Y, Y ) + R.

Random-forest kernel MMD GAN enjoys the following advantages:

• Our proposed random-forest kernel used in MMD GAN benefits from ensemble learning.

From the perspective of random forest, the output of MMD GAN discriminator h(•; θ N ) can be viewed as feature inputs to the forest. To mention, each tree only gets access to merely a fraction of the features by random connection functions, and thus the entire forest benefits from ensemble learning.

• Our random-forest kernel MMD GAN enjoys the advantages of three powerful discriminative methods, which are CNN, kernel method, and ensemble learning. To be specific, CNN is good at extracting useful features from images; Kernel method utilize RKHS for discrimination; Ensemble learning utilizes the power of randomness and ensemble. • Our proposed random-forest kernel has some good theoretical properties. In one aspect, random-forest kernel is proved to be characteristic in Shen & Vogelstein (2018) . In another, in Section 3.5, the unbiasedness of the gradients of MMD GAN with random-forest kernel is proved.

3.4. RANDOM-FOREST KERNEL TRAINING TECHNIQUE:

In Frosst & Hinton (2017) , the authors mention that the tree may get stuck on plateaus if internal nodes always assign the most of probability to one of its subtree. The gradients will vanish because the gradients of the logistic-type decision function will be very closed to zero. In order to stabilize the training of random-forest kernel and avoid the stuck on bad solutions, we add penalty that encourage each internal node to split in a balanced style as Frosst & Hinton (2017) does, that is, we penalize the cross entropy between the desired 0.5, 0.5 average probabilities of falling into two subtrees and the actual average probability α, 1 -α.

The actual average probability of the i-th internal node α i is

α i = x∈Ω P i (x)p i (x) x∈Ω P i (x)

, where P i (x) is the routing probability of x from root node to internal node i, p i (x) is the probability of x falling into the left subtree of the i-th internal node, and Ω is the collection of mini-batch samples.

Then, the formulation of the regularizer is:

R(Ω) = -λ i∈Internal Nodes 0.5 log (α i ) + 0.5 log (1 -α i ) ,

where λ is exponentially decayed with the depth of d of the internal node by multiplying the coefficient 2 -d , for the intuition that less balanced split in deeper internal node may increase the non-linear discrimination power.

When training random-forest kernel, a mini-batch of real samples X and generated pictures Y are both fed into the discriminator, and then k(X, X), k(X, Y ) and k(Y, Y ) are calculated, where

k := k RF • h(•; θ N ).

Here, to notify, we find that the Ω in the regularizer formulation does matter in forest-kernel setting. It's better to calculate α i and R(Ω) in the case of Ω = X, Ω = Y , Ω = X ∪ Y respectively, and then sum up three parts of regularizer as final regularizer R.

Therefore, the formulation of regularizer R added in the training of random-forest kernel is

EQUATION

3.5. THEORETICAL RESULTS:

In this subsection, we present our main theoretical results.

Theorem 2 (Unbiasedness) Let X be the true data on X with the distribution P X and Z be the noise on Z with the distribution P Z satisfying E P X X α < ∞ and E P Z Z α < ∞ for some α ≥ 1. Moreover, let G ψ : Z → X be a generator network, h θ N : X → R d be a discriminator network, k RF be the random-forest kernel, and θ D := (θ N , θ F ) be the parameters of the GAN discriminator. Then, for µ-almost all θ D ∈ R |θ D | and ψ ∈ R |ψ| , there holds

E D X ∼P m X ,D Z ∼P n Z ∂ θ D ,ψ MMD 2 u (h θ N (D X ), h θ N (G ψ (D Z ))) = ∂ θ D ,ψ MMD 2 (h θ N (P X ), h θ N (G ψ (P Z ))).

In other words, during the training process of Random-Forest Kernel MMD GAN, the estimated gradients of MMD with respect to the parameters ψ and θ D are unbiased, that is, the expectation and the differential are exchangeable.

In this section, we evaluate our proposed random-forest kernel in the setting of MMD GAN in (Li et al., 2017) and the MMD GAN with repulsive loss (Wang et al., 2019) . To illustrate the efficacy of our random-forest kernel, we compare our random-forest kernel with Gaussian kernel (Li et al., 2017) , rational quadratic kernel (Bińkowski et al., 2018) in the setting of the original MMD GAN loss, and compare our random-forest kernel with bounded Gaussian kernel (Wang et al., 2019) in the setting of MMD GAN with repulsive loss.

4.1. EXPERIMENTAL SETUP:



4.1.1. DATASETS:

The experiments are evaluated on three benchmark datasets:

(1) the Cifar10 dataset of 32 × 32 pictures (Krizhevsky et al., 2009) ;

(2) the LSUN dataset of bedroom pictures resized to 64 × 64 (Yu et al., 2015) ;

(3) the CelebA dataset of celebrity faces pictures randomly cropped and resized to 160 × 160 (Liu et al., 2015) . The images are scaled to range [0, 1].

4.1.2. KERNELS AND LOSSES:

Under the setting of MMD GAN loss proposed in Li et al. (2017) , we compare our proposed randomforest kernel with the Gaussian RBF kernel (Li et al., 2017) with mixture of kernel scales σ and the Rational quadratic kernel (Bińkowski et al., 2018) with mixture of kernel scales α. Moreover, under another setting of MMD GAN with repulsive loss proposed in Wang et al. (2019) , we compare our random-forest kernel with the bounded RBF kernel (Wang et al., 2019) . As is shown in Figure 3 , the shapes of the Gaussian RBF kernel and the rational quadratic kernel are both symmetric. However, the local structure of random-forest kernel (w.r.t reference points except 70-dimensional zero vector) is asymmetric and very complex. The asymmetry and complexity of random-forest kernel may be helpful to discriminate two distributions in MMD GAN training.

4.1.3. NETWORK ARCHITECTURE:

For dataset Cifar10 and dataset LSUN bedroom, DCGAN (Radford et al., 2016) architecture with hyper parameters from Miyato et al. ( 2018) is used for both generator and discriminator; and for dataset CelebA, we use a 5-layer DCGAN discriminator and a 10-layer ResNet generator. Further details of the network architecture are given in Appendix A.3. We mention that in all experiments, batch normalization (Ioffe & Szegedy, 2015) is used in the generator and spectral normalization (Miyato et al., 2018) is used in the discriminator. The hyper-parameter details of kernels used in The following three metrics are used for quantitative evaluation: Inception score (IS) (Salimans et al., 2016) , Fréchet inception distance (FID) (Heusel et al., 2017) , and Kernel inception distance (KID) (Bińkowski et al., 2018) . In general, higher IS and Lower FID, KID means better quality. However, outside the dataset Imagenet, the metric IS has some problem, especially for datasets celebA and LSUN bedroom. Therefore, for inception score, we only report the inception score of CIFAR-10. Quantitative scores are calculated based on 50000 generator samples and 50000 real samples.

4.2. EXPERIMENTAL RESULTS:

We compare our proposed random-forest kernel with mix-rbf kernel and mix-rq kernel in the setting of the MMD GAN loss, and compare our proposed random-forest kernel with rbf-b kernel in the setting with MMD GAN repulsive loss. The Inception Score, the Fréchet Inception Distance and the Kernel Inception Distance of applying different kernels and different loss functions on three benchmark datasets are shown in table 1 .

We find that, in the perspective of the original MMD GAN loss, our newly proposed random-forest kernel shows better performance than the mix-rbf kernel and the mix-rq kernel in CIFAR-10 dataset and LSUN bedroom dataset; and in the perspective of the repulsive loss, the performance of our newly proposed random-forest kernel is comparable or better than the rbf-b kernel. The efficacy of our newly proposed random-forest kernel is shown under the setting of both MMD GAN loss and MMD GAN repulsive loss.

Some randomly generated pictures of model learned with various kernels and two different loss functions are visualized in Appendix D.

A SUPPLEMENTARY METHODOLOGY:

A.1 KERNELS AND LOSSES

The formulation of our proposed random-forest kernel is

k RF (x, y; θ F ) = 1 T µ (T ) (x; θ F ), µ (T ) (y; θ F ) .

In experiments, we take the number of trees in the forest T = 10 and the depth of trees dep = 3. Thus, the total number of internal nodes is 70. To notify, in general, the parameters θ F = (θ t F ) T t=1 are trainable, where

θ t F = (w t , b t ), w t = (w t 1 , . . . , w t |N | ), b t = (b t 1 , . . . , b t |N |

) and N is the set of every internal nodes of a tree. However, for the sake of experimental simplification, we fix each w t j = 1, b t j = 0 untrainable. In the setting of MMD GAN loss proposed in Li et al. (2017) , we compare our random-forest kernel with the two following kernels: Gaussian kernel (Li et al., 2017) with mixture of kernel scales σ, that is,

k m rbf (x, y) = σ∈Σ exp - x -y 2 2σ 2 ,

where Σ = {2, 5, 10, 20, 40, 80}, and rational quadratic kernel (Bińkowski et al., 2018) with mixture of kernel scale α, that is,

k m rq (x, y) = α∈A 1 + x -y 2 2α -α

, where A = {0.2, 0.5, 1, 2, 5}.

In the setting of the MMD GAN with repulsive loss proposed in Wang et al. (2019) , we compare our forest kernel with bounded RBF kernel (Wang et al., 2019) , that is,

k b rbf (x, y) =        exp - max{ x -y 2 , b l } 2σ 2 if x, y ∈ {P Y } exp - min{ x -y 2 , b u } 2σ 2 if x, y ∈ {P X },

with σ = 1, b l = 0.25 and b u = 4.

A.2 VISUALIZATION DETAILS OF KERNELS:

In figure 3 , we compare the contours of three different kernels (the detail of kernels is shown in A.1). We directly plot the filled contours of 2-dimensional Gaussian kernel and rational quadratic kernel with reference to (0, 0); As for random-forest kernel with T = 10 and dep = 3, where the input dimension is 70, the steps of a 2-dimensional visualization are as follows:

1) We randomly generate 25000 points from the uniform distribution U[-1, 1] 70 and set (0.5, . . . , 0.5) ∈ R 70 as the reference point. To notify, if the reference point is 70dimensional zero vector, the values of random-forest kernel will be constant; 2) We calculate the 25000 output values of random-forest kernel; 3) We transform 70-dimensional 25000 randomly generated points and reference point together by t-SNE to 2-dimensional points; 4) We show the filled contour of the neighborhood of transformed reference point. We try to visualize the local structure of random-forest kernel.

A.3 NETWORK ARCHITECTURE:

In the experiments of the CIFAR-10 and LSUN bedroom datasets, we use the DCGAN architecture following Miyato et al. (2018) , and for the experiments of the CelebA dataset, we use a 5-layer DCGAN discriminator and a 10-layer ResNet generator as in Bińkowski et al. (2018) . The first few layers of the ResNet generator consist of a linear layer and 4 residual blocks as in Gulrajani et al. (2017) . The network architecture details are shown in Table 2 and 3 . 

B THEORETICAL ANALYSIS:

In Section B, we will show the main propositions used to prove the Theorem 2. To be specific, in Section B.1, we represent neural networks as computation graphs. In Section B.2, we consider a general class of piecewise analytic functions as the non-linear part of neural networks. In Section B.3, we prove the Lipschitz property of the whole discriminators. In Section B.4, we discover that for P X almost surely, the network is not differential for its parameters θ N and ψ. Fortunately, we prove that the measure of bad parameters set is zero.

In Section C, we will show the explicit proof of main propositions in Section B and Theorem 2.

B 

the output of a fully connected layer, where d represents the number of neurons in the output.

The general feed-forward networks including CNN and FC can be formulated as a directed acyclic computation graph G consisting of L + 1 layers, with a root node i = 0 and a leaf node i = L. For a fixed node i, we use the following notations:

π(i): the set of parent nodes of i; j < i: j is a parent node of i.

Each node i > 0 corresponds to a function f i that receives a R d π(i) -valued input vector, which is the concatenation of the outputs of each layer in π(i), and outputs a R di -valued vector, where d π(i) = j∈π(i) d j and d 0 = d > 0. According to the construction of the graph G, the feed-forward network that factorizes with functions f i recursively can therefore be defined by h 0 = X, and for all 0 < i ≤ L,

h i := f i (h π(i) ),

where h π(i) is the concatenation of the vectors h j , j ∈ π(i). Here, the functions f i can be of the following different types:

(i) Linear/Affine: If the weights W i are m i -dimensional vectors, and the function

g i : R mi → R di×(d π(i) +1

) is a linear operator on the weights W i , e.g. convolutions, then the functions f i are of the linear form

f i (Y ) = g i (W i ) (Y 1) T =: g i (W i ) Y .

(ii) Non-linear: Such functions f i including ReLU, max-pooling and ELU, have no learnable weights, can potentially be non-differentiable, and only satisfy some weak regularization conditions, see Definition 3 and the related Examples 2, 3, and 4.

In the following, we denote by I the set of nodes i such that f i is non-linear, and its complement by I c := {1, . . . , L} \ I, that is, the set of all of all linear modules. We write θ N as the concatenation of parameters

θ N := (W i ) i∈I c ∈ R |θ N | ,

where |θ N | denotes the total number of parameters of θ N . Moreover, the feature vector of the network corresponds to the output neurons G L of the last layer L and will be denoted by

h θ := h L θ N ∈ R |h θ N |

, where the subscript θ stands for the parameters of the network. If X is random, we will use h θ N (X) to denote explicit dependence on X, and otherwise when X is fixed, it will be omitted.

B.2 PIECEWISE ANALYTIC NONLINEAR LAYERS:

Throughout this paper, in the construction of neural networks, we only consider activation functions that are piecewise analytic which can be defined as follows:

Definition 3 (Piecewise Analytic Functions) Let {f i } i∈I be non-linear layers in neural networks, then f i is said to be an piecewise analytic function if there exists a partition of R d π(i) with J i pieces, that is, i) and D j i D j i = ∅ for j = j , such that there exist (i) S j i real analytic functions g j i,s : R d π(i) → R such that

Ji j=1 Dj i = R d π(

EQUATION

Y ) > 0 for all s ∈ {1, . . . , S j i } ;

(ii) J i real analytic functions (f j i ) j∈{1,...,Ji} such that

f i (Y ) = f j i (Y ) for all Y ∈ Dj i .

The sets D j i are called analytic domains and the functions f j i are called analytic value.

The following examples show that in practice, the vast majority of deep networks satisfy the conditions in the above definition, and therefore are piecewise analytic.

Example 1 (Sigmoid) Let f i outputs the sigmoid activation function on the inputs. Then we need no partition, and hence there exist (i) S j i = 1 real analytic functions g 1 i,1 (Y ) = 1 such that

D j i = R d π(i) corresponding to the whole space; (ii) J i = 1 real analytic function f 1 i := f i .

Here, we mention that the case in Example 1 corresponds to most of the differentiable activation functions used in deep learning, more examples include the softmax, hyperbolic tangent, and batch normalization functions. On the other hand, in the case that the functions are not differentiable, as is shown in the following examples, many commonly used activation functions including the ReLU activation function are at least piecewise analytic.

Example 2 (ReLU) Let f i outputs the ReLU activation function on two inputs. Then we have a partition of J i = 4 pieces, with each D j i , j ∈ {1, 2, 3, 4}, corresponding to a quadrant of the real plane, such that there exist (i) S j i = 2 real analytic functions g j i,1 (Y ) := ±Y 1 and g j i,2 (Y ) := ±Y 2 such that

D j i = {Y | g j i,1 (Y ) > 0 and g j i,2 (Y ) > 0};

(ii) J i = 4 real analytic functions

EQUATION

f 4 i := (0, Y 2 ) such that f i (Y ) = f j i (Y ) for all Y ∈ D j i .

Besides the ReLU activation function, other activation functions, such as the Max-Pooling and the ELU (Clevert et al., 2016 ) also satisfy the form of Definition 3 are therefore piecewise analytic.

Example 3 (Max-Pooling) Let f i outputs max-pooling on two inputs. Then we have a partition of J i = 2 pieces with each domain D j i , j = 1, 2, corresponding to a half plane, such that there exist (i)

S 1 i = S 2 i = 1 real analytic function g 1 i,1 (Y ) := Y 1 -Y 2 and g 2 i,1 (Y ) = Y 2 -Y 1 such that D 1 i = {Y | g 1 i,1 (Y ) > 0} and D 2 i = {Y | g 2 i,1 (Y ) > 0};

(ii) J i = 2 real analytic functions

f 1 i := Y 1 and f 2 i := Y 2 such that f i (Y ) = f j i (Y ) for all Y ∈ D j i .

Example 4 (ELU) Let f i outputs the ELU activation function on two inputs. Then we have a partition of J i = 4 pieces, with each D j i , j ∈ {1, 2, 3, 4}, corresponding to a quadrant of the real plane, such that there exist (i) S j i = 2 real analytic functions g j i,1 (Y ) := ±Y 1 and g j i,2 (Y ) := ±Y 2 such that

D j i = {Y | g j i,1 (Y ) > 0 and g j i,2 (Y ) > 0};

(ii) J i = 4 real analytic functions

EQUATION

f 4 i := (0, Y 2 ) such that f i (Y ) = f j i (Y )

for all Y ∈ D j i .

B.3 BOUNDING THE NETWORK GROWTH:

In this section, we investigate the Lipschitz property of the proposed discriminative networks, which is formulated as follows:

Denote u := (x, y), then the linear kernel k L (x, y) can be written as a univariate function K L (u), that is,

EQUATION

)

Proposition 4 Let θ D be the parameters of discriminators and B r (θ D ) ⊂ R |θ D | be the ball with center θ D and radius r ∈ (0, ∞). Then, for all θ D ∈ B r (θ D ) and all x ∈ R d , there exists a regular function c(x) with

E P X [c(x)] < ∞ such that K µ (T ) θ D (x) -K µ (T ) θ D (x) ≤ c(x) θ D -θ D .

B.4 EFFECTLESS OF CRITICAL PARAMETERS:

In the analysis of section B.3, we intentionally ignore the situation when samples fall into the "bad sets", where the network is not differentiable for data sets x with nonzero measure. And in proposition 5, we show that the measure of the so called "bad sets" is zero.

To better illustrate this proposition, we first denote some notations as follows:

For a fixed θ N,0 ∈ R |θ N | , we denote

N (θ N,0 ) = {x ∈ R d | θ N → h θ N (x) is not differentiable at θ N,0 } (7)

as the set of input vectors x ∈ R d such that h θ N (x) is not differentiable with respect to θ N at the point θ N,0 . Then we call

EQUATION

8) the set of critical parameters, where the network is not differentiable for data sets x with nonzero measure.

Proposition 5 Let the set Θ P X be as in equation 8. Then, for any distribution P X , we have µ(Θ P X ) = 0.

C PROOFS C.1 PROOFS OF SECTION B.3:

To prove Proposition 4, we first introduce Lemma 6 and Lemma 7.

Lemma 6 describes the growth and Lipschitz properties of general networks including convolutional neural networks and fully connected neural networks introduced in Section B.1.

Lemma 6 Let h θ N be the neural networks defined as in Section B.1. Then there exist continuous functions a, b : R |θ N | → R and α, β : R 2|θ N | → R such that for all x ∈ R d and all θ N , θ N ∈ R |θ N | , there hold

EQUATION

EQUATION

)

Proof [of Lemma 6] We proceed the proof by induction on the nodes of the network.

Obviously, for i = 0, the inequalities hold with b 0 = 0, a 0 = 1, β 0 = 0 and α 0 = 0. Then, for the induction step, let us fix an index i. Assume that for all x ∈ R d and all θ N , θ N ∈ R |θ N | , there hold

h π(i) θ N (x) ≤ b π(i) (θ N ) + a π(i) (θ N ) x , h π(i) θ N (x) -h π(i) θ N (x) ≤ θ N -θ N β π(i) (θ N , θ N ) + α π(i) (θ N , θ N ) x , where a π(i) (θ N ), b π(i) (θ N ), α π(i) (θ N , θ N ) and β π(i) (θ N , θ N ) are some continuous functions. (i) If i ∈ I, that is, if i is a linear layer, then the following growth condition h i θ N ≤ g i (W i ) hπ(i) θ N ≤ g i W i h π(i) θ N + 1 ≤ b i (θ N ) + a i (θ N ) x holds with a i (θ N ) = g i W i a π(i) (θ N ) and b i (θ N ) = g i W i b π(i) (θ N ).

Moreover, concerning with the Lipschitz property, we have

h i θ N (x) -h i θ N (x) = g i (W i ) hπ(i) θ N (x) -g i (W i ) hπ(i) θ N (x) ≤ g i (W i )( hπ(i) θ N (x) - hπ(i) θ N (x)) + (g i (W i -W i )) hπ(i) θ N (x) ≤ g i W i h π(i) θ N (x) -h π(i) θ N (x) + W i -W i h π(i) θ N (x) + 1 ≤ θ N -θ N β i (θ N , θ N ) + α i (θ N , θ N ) x ,

where we used the notations

α i (θ N , θ N ) := g i ( W i + W i )α π(i) (θ N , θ N ) + (a π(i) (θ N ) + a π(i) (θ N )) β i (θ N , θ N ) := g i ( W i + W i )β π(i) (θ N , θ N ) + (b π(i) (θ N ) + b π(i) (θ N )) + 1 . (ii) If i ∈ I c

, that is, i is not a linear layer, here we only consider the sigmoid and ReLU functions. We first show that both of them are Lipschitz continuous. Concerning the sigmoid function,

σ(x) = 1 1 + e -x we obviously have σ (x) = 1 2 + e -x + e x = 1 (e -x/2 + e x/2 ) 2 ≤ 1 4

, for all x ∈ R. Consequently, the sigmoid function is Lipschitz continuous with Lipschitz constant |σ| 1 := 1/4. Next, for the ReLU function,

σ(x) = max{0, x},

we have for all x ∈ R,

σ (x) = max{0, 1} ≤ 1.

Therefore, the ReLU function is Lipschitz continuous with Lipschitz constant |σ| 1 := 1. Thus, non-linear layer f i is Lipschitz continuous with Lipschitz constant

M := |f i | 1 .

Consequently, by recursion, we obtain continuous functions

α i = M α π(i) , β i = M β π(i) , a i = M a π(i) , and b i = M b π(i) .

Next, we investigate the growth conditions and Lipschitz property of the random forest. For the ease of notations, we write the function µ (T ) as

µ (T ) (x; θ N , θ F ) =: µ (T ) (h(x; θ N ); θ F ) =: µ (T ) (h).

Moreover, it is easily seen that T • |N | equals the number of internal nodes in the random forest.

Lemma 7 Let h(x; θ N ) be the input vector of random trees and θ F := (w, b) where w and b denote the weights and bias of the random forests, respectively. Then, for all h ∈ R d and θ F , θ F ∈ R 2T |N | , there exist continuous functions c 1 , c 2 , and constants c 3 , c 4 , c 5 such that

EQUATION

EQUATION

EQUATION

Proof [of Lemma 7] For t = 1, . . . , T , denote µ t as the -th leaf node of the t-th tree. By convenient abuse of notation, we write the function µ t as

µ t (x; θ N , w t , b t ) =: µ t (h(x; θ N ); w t , b t ) =: µ (h).

First of all, let us verify the growth condition equation 11. From the definition of the function T we immediately know that for any node i in the random forest, there exists an element j = T (i) such that

p i (h) = 1 1 + exp -(wihj +bi) .

Obviously, we have

max i {p i , 1 -p i } ≤ 1 1 + exp -|wihj +bi| .

For any leaf node ∈ L t , that is, for any node in the t-th tree, in the following, for the ease of notation, we always set µ = µ t , w i = w t i , h j = h t j , b i = b t i , if not otherwise mentioned. Then µ in equation 3 can be upper bounded by

µ ≤ 1 i∈R t 1 + e -|wihj +bi| ≤ 1 2 + i∈R t |w i h j + b i | ≤ 1 2 + |N | i=1 |w i h j + b i | ≤ 1 2 + |N | i=1 (|w i h j | + |b i |).

Taking the summation on both sides of the above inequality with respect to all of the nodes in the random forest, that is, w.r.t. ∈ L, we obtain

µ (T ) ≤ |L| 2 + |N | i,t |b t i | + |N | i,t |w t i ||h T (i) | ≤ |L| 2 + |N ||L| b + |N | i,t |w t i | 2 1/2 i,t |h T (i) | 2 1/2 ≤ |L| 2 + |N ||L| b + |N | w |L| d h =: c 1 (b) + c 2 (w) h ,

where the second inequality follows from the Cauchy-Schwartz inequality and the third inequality is due to the fact that the number that the nodes p i in the random forest assigned to the corresponding node h j equals T |N |/d or T |N |/d + 1, which are less than |L|/d . Now, we show the Lipschitz properties equation 12 and equation 13 of the random forest. From the equivalent form equation 3 concerning the value of the leaf node, we easily see that µ can be written as a product of probability functions p i or 1 -p i . Therefore, without loss of generality, we can assume µ are of the product form

EQUATION

For a fixed t = 1, . . . , T , recall that T t denotes the connection function of the t-th random tree.

Then, the Lipschitz property of the sigmoid function and the continuously differentiability of the linear transform yield

|p i -p i | ≤ |p i (h; θ F ) -p i (h; θ F )| ≤ |w i h i + b i -w i h i -b i | ≤ |w i -w i ||h i | + |b i -b i |. (15)

Then, equation 14 together with equation 15 implies

|µ t (h; θ F ) -µ t (h; θ F )| = |p R (1) × • • • × p R (H) -p R (1) × • • • × p R (H) | ≤ |p R (1) -p R (1) | × p R (2) × • • • × p R (H) + • • • + p R (1) × • • • × p R (H-1) × |p R (H) -p R (H) | ≤ H i=1 |p R (i) -p R (i) | ≤ |N | k=1 |p k -p k | ≤ |N | k=1 |w t k -w k ||h i | + |b t k -b k | ≤ w t -w t |N | k=1 h 2 Tt(k) 1/2 + |N | b t -b t ,

where the last inequality follows from the Cauchy-Schwartz inequality. Consequently, concerning the random forest, we obtain

µ (T ) (h; θ F ) -µ (T ) (h; θ F ) ≤ |N | t w t -w t |N | k=1 h 2 Tt(k) 1/2 + |N | 2 t b t -b t ≤ |N | w -w k,t h 2 Tt(k) 1/2 + |N | 2 √ T b -b ≤ |N | w -w L d h + |N ||L| b -b =: c 3 w -w h + c 4 b -b ,

where the second inequality is again due to then Cauchy-Schwartz inequality.

Analogously, for a fixed t = 1, . . . , T and any i, we have

|p i (h; θ F ) -p i (h ; θ F )| ≤ |w i h j + b i -w i h j -b i | ≤ |w i ||h j -h j |,

and consequently we obtain

µ t (h; θ F ) -µ t (h ; θ F ) = |p R (1) × • • • × p R (H) -p R (1) × • • • × p R (H) | ≤ |p R (1) -p R (1) | × p R (2) × • • • × p R (H) + • • • + p R (1) × • • • × p R (H-1) × |p R (H) -p R (H) | ≤ H j=1 |p R (j) -p R (j) | ≤ |N | i=1 |p t i -p t i | ≤ |N | i=1 |w t i ||h Tt(i) -h Tt(i) | ≤ w t |N | i=1 |h Tt(i) -h Tt(i) | 2 1/2

and for the random forest, there holds

µ (T ) (h; θ F ) -µ (T ) (h ; θ F ) ≤ |N | t w t |N | i=1 |h Tt(i) -h Tt(i) | 2 1/2 ≤ |N | w i,t |h Tt(i) -h Tt(i) | 2 1/2 ≤ |N | w L d h -h =: c 5 w h -h ,

which completes the proof.

The next proposition presents the growth condition and the Lipschitz property of the composition of the neural network and the random forest.

Lemma 8 Let B r (θ D ) ⊂ R |θ D | be the ball with center θ D and radius r ∈ (0, ∞). Then, for all θ D ∈ B r (θ D ), all x ∈ R d , there exist continuous functions c 6 , c 7 , c 8 , and c 9 such that

µ (T ) (x; θ D ) ≤ c 7 (θ D ) + c 6 (θ D ) x ; µ (T ) (x; θ D ) -µ (T ) (x; θ D ) ≤ θ D -θ D c 8 (θ D , θ D ) + c 9 (θ D , θ D ) x .

Proof [of Lemma 8] Combining equation 9 in Lemma 6 with equation 11 in Lemma 7, we obtain the growth condition of the form

µ (T ) (x; θ N , θ F ) ≤ c 1 (b) + c 2 (w) h(x; θ N ) ≤ c 1 (b) + c 2 (w)(b(θ N ) + a(θ N ) x ) = c 1 (b) + c 2 (w)b(θ N ) + c 2 (w)a(θ N ) x =: c 7 (b, w, θ N ) + c 6 (w, θ N ) x = c 7 (θ D ) + c 6 (θ D ) x .

Concerning the Lipschitz property, using equation 12 and equation 13, we get

µ (T ) (x; θ N , θ F ) -µ (T ) (x; θ N , θ F ) ≤ µ (T ) (x; θ N , θ F ) -µ (T ) (x; θ N , θ F ) + µ (T ) (x; θ N , θ F ) -µ (T ) (x; θ N , w , b ) ≤ c 5 w h(x; θ N ) -h(x; θ N ) + c 3 w -w h(x; θ N ) + c 4 b -b ≤ c 5 w θ N -θ N (β(θ N , θ N ) + α(θ N , θ N ) x ) + c 3 w -w (b(θ N ) + a(θ N ) x ) + c 4 b -b ,

where the last inequality follows from equation 9 and equation 10 established in Proposition 6. With the concatenation θ D := (θ N , θ F ) := (θ N , w, b) we obtain

µ (T ) (x; θ D ) -µ (T ) (x; θ D ) ≤ θ D -θ D (c 8 (θ D , θ D ) + c 9 (θ D , θ D ) x )

and thus the assertion is proved.

Proof [of Proposition 4] First we give the growth conditions for the linear kernel. Let k be the linear kernel k L (x, y) := x, y , then we have

|k L (x, y)| ≤ x 2 + y 2 + 1, ∇ x,y k L (x, y) ≤ x 2 + y 2 1/2 + 1.

If we denote u := (x, y), then the above linear kernel k L (x, y) can be written a as a univariate function K L (u), that is,

EQUATION

)

Therefore we have K is continuously differentiable satisfying the following growth conditions:

EQUATION

)

Let us define the function f :

[0, 1] → R by f (t) = K(tu + (1 -t)v), t ∈ [0, 1].

Then we have f (0) = K(v) and f (1) = K(u). Moreover, f is differentiable with derivative

f (t) = ∇K((tu + (1 -t)v))(u -v).

The growth condition equation 18 implies

|f (t)| = ∇K((tu + (1 -t)v)(u -v) ≤ ∇K(tu + (1 -t)v) (u -v) ≤ t(u -v) + v + 1 u -v ≤ ( u -v + v ) + 1 u -v .

Using the mean value theorem, we obtain that for all u, v ∈ R L , there holds C.2 PROOFS OF SECTION B.4 To reach the proof of Proposition 5, we first introduce Lemma 9 and Lemma 11.

Let i be a fixed node. To describe paths through the network's computational graph, we need to introduce the following notations:

P := (i, j, s) ∈ N 3 | i ∈ {0, 1, . . . , L}, j ∈ {1, . . . , J i }, s ∈ {1, . . . , S i,j } ; A(i) := {i | i is an ancestor of i}; ¬i := {(i , j, s) ∈ P | i ∈ A(i) or i = i}; ¬π(i) := i ∈π(i) ¬i := {(i , j, s) ∈ P | i ∈ A(i)}; ∂i := {(i, j, s) ∈ P}.

Obviously, we always have ∂i ⊆ ¬i and ¬i = ∂i ∪ ¬π(i).

We define a backward trajectory starting from node i by

q := (i , j i ) i ∈A(i)∪{i} , j i ∈ {1, . . . , J i }.

The set of all backward trajectories for node i will be denoted by Q(i).

Lemma 9 Let i be a fixed node in the network graph. If θ N ∈ R |θ N | \ ∂S ¬i , then there exist a constant η > 0 and a trajectory q ∈ Q(i) such that for all θ N ∈ B η (θ N ), there holds

h i θ N = f q (θ N ),

where f q is the real analytic function on R |θ N | with the same structure as h θ N , only replacing each nonlinear f i with the analytic function f

j i i for (i , j i ) ∈ q.

Proof [of Lemma 9] We proceed by induction on the nodes of the network. If i = 0, we obviously have h 0 θ N = x, which is real analytic on R |θ N | . For the induction step we assume that the assertion holds for ¬π(i) and let θ N ∈ R |θ N | \ ∂S ¬i . Then there exist a constant η > 0 and a trajectory q ∈ Q(π(i)) such that for all θ N ∈ B η (θ N ), there holds

EQUATION

with f q : R |θ N | → R being a real analytic function.

(i) If θ N ∈ S ∂i , then there exists a sufficiently small constant η > 0 such that B η (θ N ) ∩ S ∂i = ∅. Therefore, there exists a j ∈ {1, . . . , J i } such that for all θ N ∈ B η (θ N ), there holds

h i θ N = f j i (h π(i) θ N )

where f j i is one of the real analytic functions in the definition of f i . Then, equation 19 implies that for all θ N ∈ B min{η,η } (θ N ), there holds

EQUATION

(ii) Consider the case θ N ∈ S ∂i . By assumption, we have θ N ∈ ∂S ∂i . Then there exists a small enough constant η > 0 such that B η (θ N ) ⊂ S ∂i . If we denote

A := {p = (i, j, s) ∈ ∂i | θ N ∈ S P }, then A = ∅ since θ N ∈ S ∂i . Therefore, we have θ N ∈ p∈A S p and θ N ∈ p∈A c S p .

Now we show by contradiction that for η small enough, there holds

B η (θ N ) ⊆ p∈A S p .

To this end, we assume that there exists a sequence of parameter and index pairs (θ N,n , p n ) such that p n ∈ A c , θ N,n ∈ S pn , and θ N,n → θ N as n → ∞. Since A c is finite, there exists a constant subsequence {p ni } ⊂ {p n } and some constant p 0 ∈ A c with p ni = p 0 for all i. Then the continuity of the network and g p0 imply that S p0 is a closed set and consequently we obtain θ N ∈ S p0 by taking the limit, which contradicts the fact that θ N ∈ p∈A c S p . Therefore, for η small enough, there holds B η (θ N ) ⊆ p∈A S p , which contradicts the assumption θ N ∈ ∂S ∂i . Consequently, there exists a j ∈ {1, . . . , J i } satisfying equation 20. By setting f q0 = f j i (f q ) with q 0 = ((i, j) ⊕ q) ∈ Q(i), where ⊕ denotes concatenation, then for for all θ N ∈ B min{η,η } (θ N ), there holds

h i θ N = f q0 (θ N )

and the assertion is proved. Now, for a fixed p = (i, j, s) ∈ P, we denote the set of network parameters θ N that lie on the boundary of p by

S p = {θ N ∈ R |θ N | | g j i,s (h π(i) θ N ) = 0},

where the functions g j i,s are as in Definition 3. As usual, the boundary of the set S p is denoted by ∂S p and the set of the boundaries is denoted by

EQUATION

Finally, for the ease of notations, if P ⊂ P, we write

EQUATION

Obviously, we have θ N ∈ R m \ ∂S ¬π(i) . To prove Lemma 11, we need the following lemma which follows directly from Mityagin (2015) and hence we omit the proof.

Lemma 10 Let θ N → F (θ N ) : R |θ N | → R be a real analytic function and define

M := θ N ∈ R |θ N | F (θ N ) = 0 .

Then we have either µ(M) = 0 or F = 0.

Lemma 11 Let the set of boundaries ∂S P be as in equation 21. Then we have µ(∂S P ) = 0.

Proof [of Lemma 11] We proceed the proof by induction. For i = 0, we obviously have ∂S ¬0 = ∅ and therefore µ(∂S ¬0 ) = 0. For the induction step let us assume that µ(∂S ¬π(i) ) = 0.

For s = (p, q), the pair of an index p ∈ ∂i and a trajectory q ∈ Q(i), we define

M s := {θ N ∈ R |θ N | | g p (f q (θ N )) = 0},

where the analytic function f q is defined as in Proposition 9. Then we prove by contradiction that for any θ N ∈ ∂S ∂i \ ∂S ¬π(i) , there exists an s ∈ ∂i × Q(i) such that θ N ∈ M s and µ(M s ) = 0.

To this end, let θ N ∈ ∂S ∂i \ ∂S ¬π(i) , then for small enough η > 0, there holds ∂S ¬π(i) . By Proposition 9, there exists a trajectory q ∈ Q(π(i)) such that for all θ N ∈ B η (θ N ), there holds

B η (θ N ) ⊂ R |θ N | \

EQUATION

Moreover, since θ N ∈ ∂S ∂i , there exists an index p ∈ ∂i such that g p (h π(i)

θ N ) = 0. This means that for s = (p, q), we have θ N ∈ M s . Therefore, we have

EQUATION

where A ⊆ P × L j=0 Q(j) is finite. Suppose that µ(M s ) > 0, then by Lemma 10, we have M s = R |θ N | and hence B η (θ N ) ⊂ M s . By equation 23, we then have B η (θ N ) ⊂ S ∂i , which contradicts the fact that θ N ∈ ∂S ∂i and hence we have µ(M s ) = 0.

(25)

Combing equation 24 and equation 25, we obtain µ ∂S ∂i \ ∂S ¬π(i) ≤ s∈A µ(M s ) = 0.

By the assumption µ(∂S ¬π(i) ) = 0, we conclude that µ(∂S ¬i ) = 0. Since for the last node L, we have ¬L = P and therefore µ(∂S P ) = 0.

Note that the random forest µ (T ) (•) can be considered as the composition of affine transformations and sigmoid functions and hence are always continuously differentiable with respect to θ F , we only need to investigate whether the neural network h θ N (x) is differentiable with respect to θ N . For a fixed x ∈ R d , we write

EQUATION

as the set of parameters for which the network is not differentiable.

Lemma 12 Let the set Θ x be as in equation 26. Then, for any x ∈ R d , we have µ(Θ x ) = 0.

Proof [of Lemma 12] Let the boundary set ∂S P be defined as in equation 22 and θ N,0 ∈ Θ x . Obviously, we have θ 0 ∈ S P . We proceed the proof of the inclusion Θ x ⊆ ∂S P by contradiction.

To this end, we assume that θ D,0 ∈ ∂S P . When Lemma 9 applied to the output layer, there exist some η > 0 and a real analytic function f (θ N ) such that for all θ N ∈ B η (θ N,0 ), there holds

h θ N = f (θ N ).

Consequently, the network is differentiable at θ N,0 , contradicting the fact that θ N,0 ∈ Θ x . Therefore, we have Θ x ⊆ ∂S P and hence µ(Θ x ) = 0 since µ(∂S P ) = 0 according to Lemma 11.

Proof [of Proposition 5] Let the sets N (θ N ), Θ P X , and Θ x be as in equation 7, equation 8, and equation 26, respectively. Consider the sets

S 1 = {(θ N , x) ∈ R |θ N | × R d | θ N ∈ Θ P X and x ∈ N (θ N )}, S 2 = {(θ N , x) ∈ R |θ N | × R d | θ N ∈ Θ x }.

Since the network is continuous and not differentiable, Theorem I in Piranian (1966) implies that the sets S 1 and S 2 are measurable. Obviously, we have S 1 ⊂ S 2 and therefore we obtain ν(S 1 ) ≤ ν(S 2 ), where ν := P X ⊗ µ. On the one hand, Fubini's theorem implies

ν(S 2 ) = R d Θx dµ(θ N ) dP X (x) = R d µ(Θ x ) dP X (x).

there exists a δ > 0 such that λ n -λ 0 < δ for all n ∈ N. For a fixed u = (x, z) ∈ R d × R |z| , Proposition 4 states that there exists a regular function c(u) with E P X c(X) < ∞ such that |K(h λn (u)) -K(h λ0 (u))| ≤ c(u) λ n -λ 0 and consequently we have

|∂ λ K(h λ0 (u))| ≤ c(u)

for P X ⊗ P Z -almost all u ∈ R |u| .

For n ∈ N, we define the sequence g n (x) by

g n (u) = |K(h λn (u)) -K(h λ0 (u)) -∂ λ K(h λ0 (u))(λ n -λ 0 )| λ n -λ 0 .

Obviously, the sequence g n (x) converges pointwise to 0 and is bounded by the integrable function 2c(u). By the dominated convergence theorem, see e.g., Theorem 2.24 in Folland (1999), we have

E P X ⊗P Z g n (u) → 0.

Moreover, for n ∈ N, we define the sequence gn (x) by gn = |E P X K(h λn (u)) -E P X K(h λ0 (u)) -E P X ∂ λ K(h λ0 (u))(λ n -λ 0 )| λ n -λ 0 .

Clearly, the sequence gn (x) is upper bounded by E P X ⊗P Z g n (u) and therefore converges to 0. By Lemma 13, E P X ⊗P Z [K(h λ (u))] is differentiable at λ 0 with differential

E P X ⊗P Z ∂ λ K(h λ (u)).

Since similar results as above hold also for the networks h (2) and h (3) , and Lemma 6 in Gretton et al. (2012) states that MMD 2 u is unbiased, our assertion follows then from the linearity of the form of MMD 2 u in equation 1.

D SAMPLES OF GENERATED PICTURES:

Generated samples on the datasets CIFAR-10, CelebA, and LSUN bedroom are shown in Figure 4 , 5, and 6, respectively. 

:

d t j (1 -p t j (x; θ t F ))1 d t j ,where R t denotes the unique path from node 1 to node of the t-th tree.

Figures and Tables:

Figure 1: Example of a random forest with T trees: blue nodes denote the internal nodes N := {d1, ..., d7} while purple nodes are the leaf nodes L := { 1, • • • , 8}. The black thick path illustrates the route of a sample x falling into the 6 leaf node of the t-th tree.

Figure 2: Example of a connection between CNN network d -dimensional output h(•; θN ) and random forest with T trees and depth 2. The internal node d 1 3 in the left tree has the probability p 1 3 (x; θN , θ 1 F ) = σ(w 1 3 h1(x; θN ) + b 1 3 ) and therefore the routing function of leaf node 1 4 is µ 1 4 (x; θN , θ 1 F ) = 1 -σ(w 1 1 h d (x; θN ) + b 1 1 ) 1 -σ(w 1 3 h1(x; θN ) + b 1 3 ) .

Figure 3: Visualization of three kernels by drawing filled contours: (a) & (b) -A direct visualization of 2-dimensional kernels with reference to (0, 0); (c) -A 2-dimensional visualization of the multidimensional random-forest kernel with the help of t-SNE (Maaten & Hinton, 2008). The details of visualization are shown in Appendix A.2.

stride 2 deconv, 3, Sigmoid (b) Discriminator RGB picture x ∈ [-1, 1] H×W ×3 5 × 5, stride 2 conv, 64, LReLU 5 × 5, stride 2 conv, 128, LReLU 5 × 5, stride 2 conv, 256, LReLU 5 × 5, stride 2 conv, 512, LReLU 5 × 5, stride 2 conv, 1024, LReLU dense → s

Figure 4: Generated Pictures with different kernels and two different loss functions on 32x32 CIFAR-10 dataset.

Score evaluation results for three datasets: Inception Score (IS), Fréchet Inception Distance (FID) and Kernel Inception Distance (KID). The best score within two setups are marked in bold For the sake of comparison with forest kernel, the dimension of discriminator output layer s is set to be 70 for random-forest kernel and to be 16 for other kernels following the previous setting ofBińkowski et al. (2018);Wang et al. (2019).

Table content: <table><tr><td>Kernel</td><td>Loss</td><td>Dimension of Output Layer</td><td>IS</td><td colspan="2">CIFAR-10 FID KID ×10 3</td><td>FID</td><td>CelebA KID ×10 3</td><td>FID</td><td>LSUN KID ×10 3</td></tr><tr><td>Real data</td><td/><td/><td>11.28</td><td>0.217</td><td>0.00</td><td>0.589</td><td>0.00</td><td>0.670</td><td>0.00</td></tr><tr><td>mix-rbf</td><td>mmd</td><td>16</td><td>6.91</td><td>28.99</td><td>20.92</td><td>22.08</td><td>14.07</td><td>68.36</td><td>41.67</td></tr><tr><td>mix-rq</td><td>mmd</td><td>16</td><td>7.12</td><td>28.23</td><td>20.13</td><td>34.02</td><td>16.96</td><td>82.08</td><td>56.41</td></tr><tr><td>mix-rbf</td><td>mmd</td><td>70</td><td>6.96</td><td>27.56</td><td>19.51</td><td>21.64</td><td>14.39</td><td>65.48</td><td>40.34</td></tr><tr><td>mix-rq</td><td>mmd</td><td>70</td><td>7.19</td><td>27.68</td><td>18.88</td><td>29.78</td><td>11.91</td><td>78.89</td><td>48.82</td></tr><tr><td>forest</td><td>mmd</td><td>70</td><td>7.16</td><td>24.74</td><td>17.29</td><td>25.07</td><td>17.63</td><td>24.99</td><td>24.35</td></tr><tr><td>rbf-b</td><td>mmd-rep</td><td>16</td><td>7.37</td><td>23.54</td><td>17.27</td><td>27.81</td><td>15.53</td><td>17.99</td><td>16.04</td></tr><tr><td>rbf-b</td><td>mmd-rep</td><td>70</td><td>7.60</td><td>24.80</td><td>16.38</td><td>30.82</td><td>18.36</td><td>18.28</td><td>16.57</td></tr><tr><td>forest</td><td>mmd-rep</td><td>70</td><td>7.42</td><td>22.32</td><td>15.46</td><td>21.11</td><td>14.29</td><td>17.60</td><td>16.94</td></tr><tr><td colspan="5">the discriminator are shown in Appendix A.1.</td><td/><td/><td/><td/><td/></tr></table>

Network architecture used in the image generation on CIFAR-10 dataset and LSUN bedroom dataset. In terms of the shape parameter h and w in the table, we take h = w = 4 for CIFAR-10 and h = w = 8 for LSUN bedroom. As for the output dimension of discriminator s, we take s = 70 for random-forest kernel and s = 16, 70 for other kernels. To notify, 16 is the setting inBińkowski et al. (2018);Wang et al. (2019) and 70 is set for the comparison of random-forest kernel.

Table content: <table><tr><td>(a) Generator</td><td>(b) Discriminator</td></tr><tr><td>noise input z ∈ R 128 ∼ U[-1, 1]</td><td>RGB picture x ∈ [0, 1] H×W ×3</td></tr><tr><td>128 → h × w × 512, dense, BN, ReLU</td><td>3 × 3, stride 1 conv, 64, LReLU</td></tr><tr><td>4 × 4, stride 2 deconv, 256, BN, ReLU</td><td>4 × 4, stride 2 conv, 128, LReLU</td></tr></table>

Network architecture used in the image generation on CelebA dataset. For the output dimension of discriminator s, we take s = 70 for random-forest kernel and s = 16, 70 for other kernels.

Table content: <table/>

Historical attempts to scale up GANs using CNNs to model images have been unsuccessful. The original CNN architecture is made up of convolution, non-linear and pooling. Now for our model, we adopt the deconvolution(Zeiler & Fergus, 2014) net to generate the new data with spatial upsampling. Moreover, batch normalization(Ioffe & Szegedy, 2015) is a regular method which stabilizes learning by normalizing the input to each unit to have zero mean and unit variance. Furthermore, relu functions are used both in generator and discriminator networks as non-linear part. Here we avoid spatial pooling such as max-pooling and global average pooling.

Table content: <table><tr><td>.1 NEURAL NETWORKS (NN)</td></tr><tr><td>B.1.1 CONVOLUTIONAL NEURAL NETWORKS (CNN)</td></tr></table>

Peer review (iclr2020):
Theorem 2 and its proof are plagiarised: they are rephrased and reorganized formulation and proof of Theorem 1 of [1], while being presented as authors* own work. Although the assumptions are slightly different (random forest kernels vs general kernels), core of the proof is the same, including notation and its split into Lemmas and helper Theorems. In particular: - formulation is the same (even use of MMD_u is copied, while not being defined before), - main proof of Theorem 2 (p.25-26) is the proof of Corollary 3 of [1] followed by the proof of Theorem 5 of [1], - Lemma 13 is Lemma 3 of [1], - Definition 3 in Appendix B.2 is the same as Assumption D of [1] (Appendix C.2), - Proposition 4 and it*s proof (p. 21) are the same as Lemma 2 of [1]. [1] Miko?aj Bi?kowski, Dougal J. Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD GANs. International Conference on Learning Representations, 2018.