A Mean-Field Theory for Kernel Alignment with Random Features in Generative Adverserial Networks
Authors: Masoud Badiei Khuzani
Liyue Shen
Shahin Shahrampour
Lei Xing
Venue:  (2020)
Keywords: Kernel Learning
Generative Adversarial Networks
Mean Field Theory

Abstract: We propose a novel supervised learning method to optimize the kernel in maximum mean discrepancy generative adversarial networks (MMD GANs). Specifically, we characterize a distributionally robust optimization problem to compute a good distribution for the random feature model of Rahimi and Recht to approximate a good kernel function. Due to the fact that the distributional optimization is infinite dimensional, we consider a Monte-Carlo sample average approximation (SAA) to obtain a more tractable finite dimensional optimization problem. We subsequently leverage a particle stochastic gradient descent (SGD) method to solve finite dimensional optimization problems. Based on a mean-field analysis, we then prove that the empirical distribution of the interactive particles system at each iteration of the SGD follows the path of the gradient descent flow on the Wasserstein manifold. We also establish the non-asymptotic consistency of the finite sample estimator. Our empirical evaluation on synthetic data-set as well as MNIST and CIFAR-10 benchmark data-sets indicates that our proposed MMD GAN model with kernel learning indeed attains higher inception scores  well as Fr\`{e}chet inception distances and generates better images compared to the generative moment matching network (GMMN) and MMD GAN with untrained kernels.

Under review as conference paper ICLR 2020
A MEAN-FIELD THEORY FOR KERNEL ALIGNMENT WITH RANDOM FEATURES IN GENERATIVE ADVERSE- RIAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a novel supervised learning method to optimize the kernel in maxi- mum mean discrepancy generative adversarial networks (MMD GANs), Specif- ically, characterize distributionally robust optimization problem compute a good distribution for the random feature model of Rahimi and Recht to approx- immat a good kernel function. Due to the fact that the distributional optimization consider a Monte-Carlo sample average approxima-
is infinite dimensional, tion (SAA) to obtain a more tractable finite dimensional optimization problem. We subsequently leverage a particle stochastic gradient descent (SGD) method to solve the derived finite dimensional optimization problem. Based on mean--iell analysis, we then prove that the empirical distribution of the interactive particles system at each iteration of the SGD follows the path of the gradient descent flow on the Wasserstein manifold. We also establish the non-asymptotic consistency of the finite sample estimator. Our empirical evaluation on synthetic data-set set as well as MNIST and CIFAR-10 benchmark data-sets indicates that our proposed MMD GAN model with kernel learning indeed attains higher inception scores well as Frèchet inception distances and generates better images compared to the generative moment matching network (GMMN) and MMD GAN with untrained kernels.
INTRODUCTION
A fundamental and long-standing problem in unsupervised learning systems is to capture the under- lying distribution of data. While deep generative models such Boltzmann machines Salakhutdi- nov Hinton (2009) and auto-encoding variational Bayes Kingma & Welling (2013) accomplish this task to some extent, they are inadequate for many intractable probabilistic computations that arise maximum likelihood estimation. Moreover, many machine learning tasks such as caption generation Xu et al. (2015), the main objective is to obtain new samples rather than to accurately estimate the underlying data distribution. Generative adverserial network (GAN) Goodfellow et al. (2014) provides framework directly draw new samples without estimating data distribution. consists of deep feedforward network to generate new samples from a base distribution (e.g. Gaus- sian distribution), and discriminator network to accept reject the generated samples. However, training GAN requires finding a Nash equilibrium of a non-convex minimax game with continuous, high-dimensional parameters. Consequently, it is highly unstable and prone to miss modes Salimans al. (016); Che et al. (016)) To obtain more stable models, the generative moment matching net- works (GMMNs) et al. (2015) are proposed, wherein instcad of training a discriminator network, non- con-maraettric statistical hypothesis test is performed to accept or reject the generated samples via the computation of the kernel maximum mean discrepancy Gretton et al.) (2007). While leveraging statistical test simplifies the loss function for training GMMN, in practice, the diversity of generated samples by GMMN is highly sensitive to the choice of the kernel. Thus, to improve the sampling performance, the kernel function also needs to be jointly optimized with the generator. Rather than

---

Under review as conference paper ICLR 2020
optimizing the kernel directly, the MMD GAN model Li et al. (2017) proposed which an em- bedding function is optimized in conjunction with fixed user- user-defined kernel (e.g. RBF Gaussian kernel). However, there theoretical guarantees that the user-defined kernel is the 'right' kernel for embedded features.
Contributions, To address the kernel model selection problem in MMD GAN al. (2017) in this paper put forth novel framework to learn good kernel function from training data. Our kernel learning approach based on distributional optimization problem to learn a good distribution for the random feature model of Rahimi and Recht Rahimi & Recht (2008) 2009) to approximate the kernel. Since optimization with respect the distribution of random features infinite dimensional, we consider a Monte Carlo approximation to obtain a more tractable finite dimensional optimization problem with respect to the samples of the distribution. We then use particle stochastic gradient descent (SGD) to solve the approximated finite dimensional optimization problem. We provide theoretical guarantee for the consistency of the finite sample-average approximations. Based on mean-field analysís, show that when the number of particles tends to infimity, the empirical distribution the particles in SGD follows the path of the gradient descent flow of the distributional optimization problem on the Wasserstein manifold.
also show the consistency of the proposed particle SGD. In particular,
2 PRELIMINARIES OF MMD GANS
Assume we are given data (v, i= that are sampled from an unknown distribution Py with the support V. In many unsupervised tasks, we wish to attain new samples from the distribution Pv
without directly estimating it. Generative Adversarial Network (GAN) Goodfellow et al. (2014) provides such a framework. In vanilla GAN, a deep network G(: W) parameterized by W E W is trained as generator to transform the samples Z ~ Pzz Z E Z from a user-defined distribution Pz (e.g. Gaussian) into new sample OZZ; W) Pw, such that the distributions Pw and Py are close. addition, a discriminator network O),;)) parameterized by E A is also trained to reject accept the generated samples realization of the data distribution. The training of the generator and discriminator networks then accomplished via solving minimax optimization problem as below
min max Ep, [D(X; 8)] PE [log(1 - ([9(Z:W);;)) WEW BEA
In the high dimensional settings, the generator trained via the min-max program of equation I can potentially collapse to single mode of distribution where it always emits the same point (Ch et al. (2016). To overcome this shortcoming, other adversarial generative models are proposed in the literature, which propose modify or replace the discriminator network by a statistical two-sample test based on the notion of the maximum mean discrepancy which is defined below:
Definition 2.1. (MAXIMUM MRAN DISCREPANCY GRETTON ET AL.. (2007) Let (X, d) be metric space, F be class of functions f : X + IR, and P.Q E B(X) two probability measures
from the set of all Borel probability measures ((x)) on X' The maximum mean discrepancy (MMD) between the distributions P and with respect to the function class F is defined below
Dr[P.Q] sup / (P (dx)). JEF
(2)
Different choices of the function class FF in equation Wasserstein GANs (WGAN) Arjovsky et al. (2017). GANs Nowozin et al. (2016), and GMMN
2 vield different adversarial models such as
and MMD GAN Li et al. 2017 2015). In the latter two cases, the function class F def {f + IR |f < J. where Hx is a reproducing kernel Hilbert space (RKHS) of functions with IR, denoted by (Hxx K). Then, the squared MMD loss in equation
kernel K X X

---

Under review conference paper ICLR 2020
measure of distance between the distributions Pv and Pw has the following expression
DR Pw]
def
sup
I [w) Pw)((d))
(3)
-Vv (VV V Pw (WW w 2 WwPW [V; W)],
(4)
where X VUW W. Instead of training the generator via solving the minimax optimization in equation D the MMD GAN model of Li et al. (2015) proposes to optimize the discrepancy between two distributions via optimization of an embedding function : IR. + RR, . D,i,e.
min max MMD (Pv Pw], WEW AE
(5)
where k IR x IRP IR is user-defined fixed kernel. In Li et al. 2015). the proposal for the kernel le IR" R IR a mixture of the Gaussians,
[1(2)
d
1o y) k(((()))) (()) = Σ
07
where the bandwidth parameters di.-.. Fn there is no guarantee that the user-defined kernel ((())),(())) can capture the structure of the embedded features ((x).
are manually selected. Nevertheless, in practice
PROPOSED APPROACH: KERNEL LEARNING WITH RANDOM FEATURES FOR MMD GANS
In this section, we first expound our kernel learning approach. Then, we describe novel MMD GAN model based on the proposed kernel learning approach.
3.1 ROBUST DISTRIBUTIONAL OPTIMIZATION FOR KERNEL LEARNING
To address the kernel model selection issue in MMD GAN Li al. 2017), consider kernel optimization scheme with random features Rahimi & Recht 2008 2009). Let IR IR" +
[-1, 1] denotes the explicit feature maps and μ E "IR") denotes probability measure from the space of probability measures M(RP) IR The kernel function is characterized via the explicit feature maps using the following integral equation
(a, y) = (B,,p((x:)))((
((a;()) ()
Let (PV, def (Pv, Then, the kernel optimization problem in can be formulated as distribution optimization for random features, i.e,
min sup MMD,,, Pw]] WEW PEP
Here, P is the set of probability distributions corresponding kernel class K. In the sequel, consider P to be the distribution ball of radius R as below
def BB (HO) def {u E M(RP) W,,,,, po) S R).
(9)
where A4 user-defined base distribution, and To establish the proof, consider the Wp(ss) is the p- W-Wssersstein distance defined as below
1/2
W Wp(mi, P2) def inf (FElI(()P))) (2) RP P
||E: E2(Bdm(E1,
(10)

---

Under review as conference paper ICLR 2020
where the infimum is taken with respect to all couplings я of the measures 14 140 E M(ID), and [p, Mo) is the set of all such couplings with the marginals μ and puu-
The kernel MMD loss function in equation 8 is defined with respect the unknown distributions of the data-set Py and the model Pw: Therefore, we construct an unbiased estimator for the MMD loss function in equation 8 based on the training samples. To describe the estimator, sample the labels from uniform distribution y1,".. Un Liid. Uniform ( (-1, +1), where assume that the number positive and negative labels are balanced. In particular. consider the set of positive labels
I {i E [1, ......... _n. Vi +1}, and negative labels I (1,2. 2... ,n)/T, where their cardinality is | = J =
nt We consider the following assignment of labels:
Positive class labels: y: +1, sample the corresponding feature map from Iata-distribution = Pv.
Negative class labels: If 1, sample from the corresponding feature map from the generated distribution x; = (Z W) ~ Pw, Zi ~ Pz.
By this construction, the joint distribution features and labels Py.x has the marginals P P Pv. and Px Pw. Moreover, the following statistic, known as the kernel alignment in the literature (see, e.g., Sinha & Duchi (2016); Cortes al. (2012)) is unbiased estimator of the
MMD loss in equation 8
min sup MMD, 4 Pvv Pw] def 8
(11)
WeW WEP WEP
n(n
iiicisn
See Appendix C.I for the related proof. through the lens of the risk minimization
The kernel alignment in equation can also be viewed
min inf MMD,, " WEW PEP
/ Pv. PPvPvw Pw]
def
8
Σ
(ay,y (x,,,,,,)))
(12a)
n(n
1)a
1sissEn
(ayay) - Ep ((a)) (12b)
n(n 1)ax Igi<jšn
Here, a > 0 is a scaling factor that determines the separation between feature vectors, and K. def azyy is the ideal kernel that provides the maximal separation between the feature vec- tors over the training data-set, i.e., (x, (. 22)) aa otherwise. Upon expansion of the risk function in equation 12 it can be easily shown that reduces the kernel alignment equation [T when a + +00. Intuitively, the risk minimization in equation 12 gives feature space in which pairwise distances are similar to those in the output space )
a when features have identical labels ys = My, and
3.2 SAA FOR DISTRIBUTIONAL OPTIMIZATION
The distributional optimization problem in equation infinite dimensional, and thus cannot be solved directly. To obtain a tractable optimization problem, instead optimizing with respect to the distribution y of random features, optimize the i.i.d. samples (particles) , N widd μ generated from the distribution. The empirical distribution these particles is accordingly defined as follows
N
P.N (E)(E)
def
8(E Σ
(13)
N
where 5(-) is the Dirac's s delta function concentrated at zero. In practice, the optimization problem in equation 12 is solved via the Monte-Carlo sample average approximation of the objective function,
min
min
MM (vv [Pv, Pw] n(n 1)a
Σ
(ow.s
Σ spa. )=()); (14)
WeW A EPN
N
150355n
k
iv

---

Under review as conference paper ICLR 2020
(T {ar e M(RR): Wp(T*, .T0) S R.). and P is the empirical
where Px
measure associated with the initial samples Eo... E0 Midd Mo. The empirical objective function in equation 14 can be optimized with respect to the samples 5 .... & using the particle stochastic gradient descent. For the optimization problem in equation 14 the (projected) stochastic gradient descent (SGD) takes the following recursive form
N
sm+1 5m " N
ym aN Σ plami Sm
(m)pimm) )ip sih) Ve (1p(2mm ( (pm)
(15a)
for k = 1,,, ... .N. where (Ym: Tm), (Um, Fm) Win Pæ. and RR denotes the learning rate of the algorithm, and the initial particles are Eo.... ED Lid Ho. At each iteration of the SGD
dynamic in equation 15] feasible solution for the inner optimization of the empirical risk function in equation 14]is generated via the empirical measure
P N
5IE - k=1
(16)
Indeed, prove in Section that for appropriate choice of the learning rate 1) O, the empirical measure in equation 16 remains inside the distribution ball C E PN for all m E N7] n IN, and is thus a feasible solution for the empirical risk minimization equation 14 (see Corollary 4.2.1
in Section
3.3 PROPOSED MMD GAN WITH KERNEL LEARNING
In Algorithm L describe the proposed method MMD GAN model with the kernel learning ap- proach described earlier. Algorithm has an inner loop for the kernel training and an outer loop for training the generator, where we employ RMSprop Tieleman & Hinton (012)) Our proposed MMD GAN model is distinguished from MMD GAN Li al. (2017) in that we learn good kernel function in equation If the inner loop instead of optimizing the embedding function that is implemented by an encoder. However, we mention that our kernel learning approach is com- patible with the auto-encoder implementation Li et al. (2017) for the dimensionality reduction of features (and particles). In the case of including an auto-encoder, the inner loop in Algorithm must be modified to add additional step for training the auto-encoder. However, to convey the main ideas more clearly, the training step of the auto-encoder is omitted from Algorithm
3.4 COMPUTATIONAL COMPLEXITY ANALYSIS
Sampling the labels y. wiid Uniform(-1,+1) require O(1) complexity, while sampling xly +1, +1 Pv and ž +1,
-1 Pw has complexity of O (d). The computation of the stochastic gradient step in equation 17 requires computing the sum
y +1.
N Em p( (<<;:"))<<;; (ā;; This can be done as separate preprocessing step prior to executing
the SGD in equation 17 and requires preparing the vectors &p def (i(zz:')),
<p(x; [N) and
6 def
sp ; {N)]. Using the random feature model of Rahimi and Recht Rahimi & Recht 2008 2009), where (0x;; {) v c2cos + b). Here b ~ Uniform[-T, +.). the complex- ity of computing the vectors &p and & of the order ((Nd) on a single processor. However, this construction is trivially parallelizable. Furthermore, computation can be sped up even further for cer- tain distributions Po. For example, the Fastfood technique can approximate &p and in O(N log(d))
[o(
of the gradient is omitted by To avoid clutter in our subsequent analysis, the normalization factor -( modifying the step-size 17.
16

---

Under review as conference paper ICLR 2020
Algorithm MMD GAN with supervised kernel learning Method (Monte-Cart Approach)
Inputs:
The learning rates 9; > 0,, the mumber of iterations of discriminator per genemator update 7 g N, the hatch-size n, the number of rundom features E N. Regularization parameter 0.
while W not converged do for f = 1, ..... T do
Sample the y, 5 mud Uniform( (-1, 1). Sample the features 2/y +1 Pv. and æ update parricles,
Pw. Similarly, øly +1 Pv. and BlV - =11- Pw
1,
e* E
2 plm; 5* (o((;: Ve V=(vetr=""
(17)
end for
Sample balanced minibatch of labels (vc mui Uniform -1, +11- Sample the minibatch (ar y such that 28 = +1 m Pv. and 2. li, = Pw for all 1, ,. Update the generator
1 N
gw + VWN [Pv.Pw] x a== N
Σ
DiE E*)
(18a)
W +- W RRMSSprppssw W).
(18b)
end while
time for the Gaussian kernel Le al. (2013). Updating each particle in equation 17 involves the computation of the gradient (g( 5 ( {))) which (d). Thus, the complexity one iteration of SGD for all the particles is (Nd).
Overall, one step of the kernel learning has a complexity of O(Nd). On the other hand, to attain e-suboptimal solution max .N _| I S E, the SGD requires has the sample complexity
O (log( )). Consequently, the computational complexity of the kernel learning is of the order of O dl log( ))). To compare this complexity with that of MMD GAN is of the order O (B3 log( {)). where the batch size for approximation of the population MMD, and é the number of kernel mixtures.
4 CONSISTENCY AND MEAN-FIELD ANALYSIS
In this section, we provide theoretical guarantees for the consistency of various approximations we made to optimize the population MMD loss function in equation 88] We defer the proofs of the fol- lowing theoretical results to AppendixC] The main assumptions (A.2),,A..2, and (A.3)) underlying our theoretical results are also stated the same section.
Consistency of finite-sample estimate: In this part, we prove that the solution to finite sample optimization problem in equation aappoacce its population optimum in equation aas the number of data points as well as the number of random feature samples tends to infinity.
Theorem 4.1. (NON-ASYMPTOTIC CONSISTENCY
FINITE-SAMPIN ESTIMATOR) Suppose conditions (A.1)-(A.3) of Appendix C are satisfied. Consider the distribution balls P and Pi that are defined with respect to the 2- Wasserstein distance (p = 2). Furthermore, consider the optimal MMD values of the population optimization and finite sample estimate
del arg min arg sup MMD,,(P, Pw]. WeW NEP
(19a)
WWN. p.
arg inf def
arg
min WeW EPN
MMD pN [Pv, Pw], (19b)

---

Under review as conference paper ICLR 2020
Then, with the probubility of (at least) 30 over the training data samples {(r1, )i) and the random feature samples { the following non-asymptotic bound holds
respectively.
MMD,. [Pv. [Pv.Pw.) Pw.]
MMD (Pv. PWx]
(20)
[. 2)
In
2 Neliiam
+ 2 max
Ci 1? Int
(4)
C2 n²
In
de
1
+
81.2
N
a
where 6j 3 24, and 02 9 2
The proof Theorem 4.1 is presented in Appendix C.1
Notice that there are three key parameters involved in the upper bound of Theorem 4.1 Namely, the number of training samples n,, the number of random feature samples NN, and the regularization
parameter a. The upper bound in equation 20 thus shows that when n. N, a -> +000 the solution
obtained from solving the empirical risk minimization in equation [2 yields MMD population value tending to the optimal value of the distributional optimization equation X
Consistency particle SGD for solving distributional optimization. The consistency result of Theorem 4.1 concerned with the MMD value of the optimal empirical measure 77," (E) * E 8(5 <** of the empirical risk minimization equation 14 In practice, the particle SGD executed for a few iterations and its values are used as an estimate for (E..... ...).. Conse- quently, it is desirable to establish similar consistency type result for the particle SGD estimates (E) ...
at the m-th iteration. To reach this objective, we define the scaled empirical measure as follows
<%) ,
1 = M NNN
Σ - EiNC), OSEST.
(21)
At any time the scaled empirical measure 14, is random element, and thus (H JosesT is measured-value stochastic process. Therefore, we characterize the evolution of its Lebesgue den- sity Pi (E) u (dE)/dÉ in the following theorem:
Theorem 4.2. (McKFAN-VLACN
MEAN-FIELM PDE) Suppose conditions (A.1)-(A.3) Ap-
pendix G are satisfied. Further, suppose that the Radon-Nikodyme derivative go(E) po(d))/d exists. Then, there exists a unique solution (pī (E))sTTTT to the following non-linear partial differ- ential equation
- [fxx (Jav pla, E)p(a ())i agy) (E) (E).
@pp(E)
(22)
Moreover, the measure-valued process {(1 (iSIsT)NeN defined in equation 21 converges (weakly) to the unique solution (E) = pt (E) as the number of particles tend to infinit N + co.
Due to the mean-field analysis of Theorem 4.2 we can prove that the empirical measure AN of the particles in SGD dynamic equation 15 remains inside the feasible distribution ball Px:
Corollary 4.2.1. Consider the learning rate 1 = O T log(2/5) for the SGD in equation
15
Then, the empirical measure p.v. of the particles remains inside the distributional ball po E Px (T. M(RP) WT( . & R} for all m E [0, [T) n IN, with the probability of (at least) 1-
"The notion weak convergence sequence empirical measures is formally defined Supple- mentary.
vii

---

Under review as conference paper ICLR 2020
Let us make two remarks about the PDE equation 22 First, the seminal works of Otto Outo (200T) and Jordan, et al. Jordan et al. (998)) establishes deep connection between the McKean- Vlasov type PDEs specified in equation 22 and the gradient flow on the Wasserstein manifolds. More specifically, the PDE equation in equation 22 can be thought of as the minimization of the energy functional
inf Ea(P((E)) def / (a((Ep((E))))(E)d (EM(RD)
(23a)
RD
Pc def a(Exx, lappa: E))) + Bg ((pp)l((x:))p( ():
(23b)
using the following gradient flow dynamics
dpr(E) r- grad,, Ea (pe(E))) po(E) = qo) (E),
(24)
dt
where grad,, p. (E): = Vg (E Rs (pr (E)) is the Riemannian gradient of R. (ue (5) with respect the metric of the Wasserstein manifold... This shows that when the number of particles in particle SGD equation [5] tends to infinity (N + +oo), their empirical distribution follows a gradient descent path for minimization of the population version (with respect to data samples) of the distributional risk optimization in equation 12 In this sense, the particle SGD is the "consistent" approximation algorithm for solving the distributional optimization.
4.1 RELATED WORKS
The mean-field description of SGD dynamics has been studied in several prior works for different information processing tasks. Wang et al. [Wang al. (2017) consider the problem of online learning for the principal component analysis (PCA), and ana yze the scaling limits of different online learn- ing algorithms based on the notion of finite exchangeabiliry. In their seminal papers, Montanari and co-authors Mei al. 2018): Javanmard
al. (2019); Mei al. (2019) consider the scaling limits of SGD for traiing a two-layer neural network, and characterize the related Mckean- Vlasov PDE for the limiting distribution of the empirical measure associated with the weights of the input layer. Similar mean-field type results for two-layer neural networks are also studied recently in Rotskoff & Vanden-Eijnden (2018); Sirignano & Spiliopoulos (2018). Our work is also related to the unpub- lished work of Wang, et al. [Wang et al.] which proposes a solvable model of GAN and analyzes the scaling limits. However, our GAN model different from Wang al., and is based on the notion of the kemel MMD. Our work is also closely related to the recent work of Li, el al Li et al. (2019) which proposes an implicit kernel learning method based the following kernel definition
K₁ (1(x), (z)) = Ba- [ (((h())((()))(()))
(25)
where Ag is a user defined base distribution, and h E a function that transforms the base distri- bution Mu into a distribution μ that provides a better kernel. Therefore, the work of Li, et a et al. (2019) implicitly optimizes the distribution of random features via transforming random variable with a function. In contrast, the proposed distributional optimization framework this paper opti- mizes the distribution of random feature explicitly, via optimizing their empirical measures. Perhaps more importantly from practical perspective the fact that our kernel learning approach does not require the user-defined function class H. Moreover, our particle SGD method in equation [55 ob- viates tuning syper-parametert related to the implicit kernel learning method such the gradient penalty factor and the variance constraint factor (denoted by AGP and X,. respectively, in Algorithm I of Li et al. (2019)).
EMPIRICAL EVALUATION
5.1 SYNTHETIC DATA-SET
Due to the space limitation, the experiments on the synthetic data are deferred to Appendix A
viii

---

Under review as a conference paper ICLR 2020
5.2 PERFORMANCE ON BENCHMARK DATASETS
We evaluate our kernel learning approach on large-scale benchmark data-sets. We train our MMD GAN model on two distinct types of datasets, namely on MeIST et al. (1998) and CIFAR-10
LeCun et al. (1998), where the size of training instances are 60 x 10 and 50 x IOs respectively. the generated samples are from a fixed noise random vectors and are not singled out.
Implementation and pyper--arameters. We implement Algorithm I as well as MMD GAN Li et al.] (2017) in Pytorch using NVIDIA Titan V100 32GB graphics processing units (GPUs). The source code of Algorithm ji built upon the code of Li et al. 2017). and retains the auto-encoder im- plementation. In particular, we use sequential training of the auto-encoder and kernel as explained in the Synthetic data Section A Supplementary. For a fair comparison, our hyper-parameters are adjusted as in Li et al. (2017). i.e. the learning rate of 0,00005 is considered for RMSProp Tieleman & Hinton (2012). Moreover, the batch-size for training the generator and auto-encoder is
n1 64. The learning rate of particle SGD is tuned to 1) = 10.
Random Feature Maps. To approximate the kernel, we use the the random feature model of Rahimi and Recht Rahimi & Recht 20088 2009), where y0æ:; {) = v2cos(x* & + b). Here b Uniform n,, + f a random bias term.
Practical considerations. When data-samples {V)} E R² are high dimensional (as in CIFAR- 10), the particles 5,,... ,NN E IR_, D = d in SGD equation 15 are also high-dimensional. To reduce the dimensionality of the particles, we apply auto-encoder architecture similar to Li et al. (2017), and train our kernel on top of learned embedded features. More specifically, in our simula- tions, we train an auto-encoder where the dimensionality of the latent space is h = 10 for MNIST, and h = 128 (thus D = d = 128) for CIFAR-10. Therefore, the particles et. .... , in subsequent kernel training phase have the dimension of D = 10, and D = 128, respectively.
Choice of the scaling parameter a. There is trade-off in the choice of a. While for large values of a, the kernel is better able to separate data-samples from generated samples, in practice, it slows down the convergence of particle SGD. This is due to the fact that the coupling between the particle dynamics in equation| [5] decrease as a increase. The scaling factor is set to be a = 1 in all the following experiments.
Qualitative comparison. We now show that without the bandwidth tuning for Gaussian kernels and using the particle SGD to learn the kernel, we can attain better visual results on benchmark data-sets. In Figure [T] show the generated samples CIFAR- 10 and MNIST data-sets, using our Algorithm MMD GAN at (2017) with mixed and homogeneous Gaussian RBF kernels, and GMMN Li et al. (2015).
Figure 1 a) shows the samples from Algorithm I Figure [bb) shows the samples from MMD GAN Li et al. (0117) with a mixture RBF Gaussian kernel k(æ,, y) Σi= Kor, (ar, y). where o 21,2,4,
4,8, 8, 16) are the bandwidths of the Gaussian kernels that are fine tuned and optimized. We observe that our MMD GAN with automatic kernel learning visually attains similar results MMD G al. (017) which requires manual tuning of the pyper-parameters. In Figure we show the MMD GAN result with single kernel RBF Gaussian kernel whose bandwidth is manually tuned at 16. Lastly, in Figure dd), we show the samples from GMMN et al. (2015) which does not exploit an auto-encoder or kernel training. Clearly, GMMN yield a poor results compared to other methods due to high dimensionality of features, well the lack of efficient method to train the kernel.
On MNIST data-set in Figure (c)-(b), the difference between our method and MMD GAN Li et al. (217)) is visually more pronounced. We observe that without manual tuning of the kernel bandwidth and by using the particle SGD equation [5 optimize the kernel, we attain better gener- ated images in Figure ee), compared to MMD GAN with mixed RBF Gaussian kernel and manual bandwidth tuning in Figure Tif). Moreover, using single RBF Gaussian kernel yields a poor result regardless of the choice its bandwidth. The generated images from GMMN is also shown in Figure
ix

---

Under review conference paper ICLR 2020
(a)
(c)
(d)
/
3
3
0
8
8
3
0 4 0
8
5
4
/ 7
7
2 /
2
3
3
2
3 3
3
2
0
7
5
3
5
7
8
3
9 4
9
9 3
3
2
7
2 2 2
7
2
6
1
/
4
3
5
4
6
0
0
9
3
4 1
9
4 6
3
1
3
3
2 1
0 O
7
8
2
4
2
5
3
3
9
5
6
4 4 9
9
2
2
1
2
4 8
1
9
2
9
/ 9 3
9
44
7
1
O
3
0
0
0
9
3
4. 2
66
1.
2 1
1 J
2
/
t 8
8
1
0
8
5
4
7
9
9
5
2
4 Q
(
3
2
2
5
4
Q
8
4
2
9
30
9
6
1
/
2
5
6
/
7
6
(c)
(f)
(g)
Figure 1: Sample generated images using CIFAR-10 (top row), and MNIST (bottom row) data-sets. Pancls (a)-(c): Proposed MMD GAN with an automatic kernel selection the partiele SGD (Algorithm [ Pancls
(b)-(f:: MMD GAN Li al. (2017) with an auto-encoder for dimensionality reduction conjunction with mixed RBF Gaussian kernel whose bandwidths are manually tuned, Panels (c)-(g): MMD GAN in [i al. (2017) with a single RBF Gaussian kernel with an auto-encoder for dimensionality reduction conjunction
with single RBF Gaussian kernel whose bandwidth is manually tuned, Panel (d)-(g): GMMN without an auto-encoder Li et al. 20015).
Quantitivative comparison. To quantitatively measure the quality and diversity of generated sam- ples, compute the inception score (IS) Salimans al. (2016) well as Frèchet Inception Dis- tance (FID) Heusel al. (2017) on CIFAR-TO images. Inturtively, the inception score used for GANs to measure samples quality and diversity. Accordingly, for generative models that are col- lapsed into single mode of distribution, the inception IS by actually comparing the statistics of generated samples to real samples, instead of evaluating generated samples independently.
is relatively low. The FID improves
In T report the quantitative measures for different MMD GAN model using different scor- ing metric. Note that in Table]looer FID scores and higher scores indicate a better performance. We observe from Table that our approach attain lower FID score, and higher IS score compared MMD GAN with single Gaussian kernel (bandwidth 16), and mixture Gaussian kernel (bandwidths {1, 4, 8, 16))
Method
FID (1)
IS (f)
MMD GAN (Gaussian) Li et al. (201))
67.244 + 0.134
5.608
MMD GAN (Mixture Gaussian) et (2017)
67.129 + 0.148
5.850:10.055
SGD Alg.
65.059 + 0.153 0
5.97 + 0.046 11.237+0.116
Real Data
Table 1: Comparison of the quantitative performance measures of MMD GANs with different kernel learning approaches.

---

Under review as conference paper ICLR 2020
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein GAN.
arXiv preprint
arXiv: (ttv:/700.07888 2017.
Patrick Billingsley. Convergence of probability measures. John Wiley Sons, 2013.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Tong Che, Yanran Li, Athul Paul Jacob, Yoshua Bengio, and Wenjie Li. Mode regularized generative adversarial networks. arXiv preprint arXiv: 2016.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based centered alignment. Journal of Machine Learning Research, 13(Mar):795-82) 2012.
Joseph Leo Doob. Stochastic processes, volume 101. New York Wiley, 1953.
Rui Gao and Anton J Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. arXiv preprint arXiv: 2016.
Kay Giesecke, Konstantinos Spiliopoulos. Richard В Sowers, al. Default clustering in large portfolios: Typical events. The Annals of Applied Probability, 23(1):348-385, 2013.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. kernel method for the two-sample-problem. In Advances in neural information processing systems, pp- 513-520, 2007.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-666 0666-66672200 2017.
Adam Jakubowski. On the skorokhod topology. In Annales de l'IHP Probabilités et statistiques, volume 22, pp. 263-285 1986.
Adel Javanmard, Marco Mondelli, and Andrea Montanari. Analysis of a two-layer neural network via displacement convexity. arXiv preprini arXiv: 1901.01355. 2019.
Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the Fokker- Planck equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
Masoud Badiei Khuzani and Na Li. Stochastic primal-dual method on riemannian manifolds with bounded sectional curvature. arXiv preprint arXiv:1703.0888 2017.
Diederik P Kingma and Max Welling. arXiv:1312.6114 2013.
Auto-encoding variational Bayes,
arXiv preprint
Quoe Le. Tamás Sarlós, and Alexander Smola. Fustfood-computting hilbert space expansions in loglinear time. In International Conference on Machine Learning, pp. 244 2013.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(1 11:2278-22322 1998.
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnaáás Póezos. Mmd GAN: Towards deeper understanding of moment matching network. In Advances in Neural Information Processing Systems, pp. 2203-2213, 2017.

---

Under review as conference paper ICLR 2020
Chun-Liang Li, Wei-Cheng Chang, Youssef Mroueh, Yiming Yang, and Barnabás Póczos. Implicit kernel learning. arXiv preprint arXiv: 2019.
Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In International Conference on Machine Learning, pp. 1718-1727, 2015.
Ziwei Liu, Ping Luo. Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of the IEEE international conference on computer vision, pp. 3730-3738, 2015.
Shishi Luo and Jonathan C Mattingly. Scaling limits of a model for selection at two scales. Nonlin- earity, 30(4):1682 2017.
Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148- 188, 1989.
Song Mei, Andrea Montanari, and Phan-Minn Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):576655-77777 2018.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. arXiv preprint 1rXiv:1902.06015 2019.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural sam- plers using variational divergence minimization. In Advances in neural information processing systems, pp. 271-279, 2016.
Felix Otto. The geometry of dissipative evolution equations: the porous medium equation. 2001.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, (3):127-239, 2014.
David Pollard. Empirical processes: theory and applications. In NSF-CBMS regional conference series in probability and statistics, pp. i-86. JSTOR, 1990.
Yu V Prokhorov. Convergence of random processes and limit theorems in probability theory. Theory of Probability & Its Applications, 1(2):157-214, 1956.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization learning. In Advances in neural information processing systems, pp. 1313- 1320, 2009.
Philippe Robert. Stochastic networks and queues, volume 52. Springer Science & Business Media, 2013.
Grant M Rotskoff and Eric Vanden-Eijnden Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. arXiv preprint arXiv: 10Xxx:88000009155 2018.
W Rudin. Real and complex analysis megraw-hill book co. New York 3rd ed., xiv, 1987.
Ruslan Salakhutdinov and Geoffrey Hinton. Deep boltzmann machines. In Artificial intelligence and statistics, pp. 148-455, 2009.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In Advances in neural information processing systems, pp. 2234-2242, 2016.
xii

---

Under review as conference paper ICLR 2020
Shashank Singh and Barnabás Póczos. Minimax distribution estimation wasserstein distance. arXiv preprint arXiv:/802.08885, 2018.
Aman Sinha and John C Duchi. Learning kernels with random features. In Advances in Neural Information Processing Systems, pp. 1298-1306, 2016.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks. arXiv preprint T.t.:1800500005. 2018
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26- 31, 2012.
VS Varadarajan. On the theorem of Riesz concerning the form of linear functional. 1958.
Chuang Wang, Hong Hu, and Yue Lu. solvable high-dimensional model GAN.
Chuang Wang, Jonathan Mattingly, and Yue Lu. Scaling limit: Exact and tractable analysis of
online learning algorithms with applications regularized regression and PCA. arXiv preprint arXiv: 2017.
Jeff Webb. Extensions of Gronwall's inequality with quadratic growth terms and applications. Elec- tronic Journal of Qualitative Theory of Differential Equations, (018(61)11-12, 2018.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In International conference on machine learning, pp. 2048-2057, 2015.
Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsun: Construction of large-scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv: 500.: 550.::33506003355, 2015.
APPENDIX
We provide additional material to support the content presented in the paper. This Appendix is organized as follows:
Appendix(A| We provide the results of our experiments on the synthetic data-set described in Section of the main text.
Appendix
B
We provide the results of our experiments the LSUN and CelebA data-sets.
Appendix
We present the proofs of the main theoretical results of Section 4 in the main text.
Appendix
D
We present the proofs of auxiliary lemmas used to support the proof of main results.
Appendix E
We prove additional theoretical results regarding the so-called chaolicity of the particle
SGD in equation
A
EXPERIMENTAL RESULTS ON THE SYNTHETIC DATA-SET
The synthetic data-set we consider is as follows:
The distribution of training data is Py N(O, (1 + A)
The distribution of generated data Pw = N(O, (1 Aa)a))).
Xiii

---

Under review as conference paper ICLR 2020
(a)
(b)
(c)
Figure 2: Visualization data-points from the synthetic data-set Pv = N(O, (1 laxa) and Pw
N(O, (1 daxx) for d Panel (a): 0.1, Panel (b): 0.5, and Panel (c): 0.9.
To reduce the dimensionality of data, we consider the embedding IR + IR", x + ((x) Ea, where Σ E IR and < d. In this case, the distribution of the embedded features are Px|Y=+1 = N(O, (1 + A)ΣE") and Px|y=-1 N(O, (1 )
Note that À E [0, 1] is parameter that determines the separation of distributions. In particular, the Kullhack-Leeble divergece of the two multi-variate Gaussian distributions controlled by À [0, 1].
1 ( - p p - -x]]
log
(26)
2
In Figure 2 we show the distributions of i.i.d. samples from the distributions Pv and Pw for
different choices of variance parameter of = 0.1, 0.5, and X = 0.9. Notice that for larger the divergence is reduced and thus performing the two-sample test is more difficult. From Figure 2 we clearly observe that for large values of X. the data aata-points from the two distributions Py and Pw have a large overlap and conducting a statistical test to distinguish between these two distributions more challenging.
A.0.1 KERNEL LEARNING APPROACH
Figure Fatreeddepict our two- pho-phase kernel learning procedure which we also employed our implemen- tations of Algorithm [ on benchmark data-sets of Section 5.2 in the main text. The kernel learning approach consists training the auto-encoder and the kernel optimization sequentially, i.e.,
sup sup MMD K RAN oz [Pv. A EN e
(27)
where the function class is defined Q def {1(2) Σz, IR" Dxd), and (KaN ()(1) K Kn (1(x1), (()))) Now, we consider two-phase optimization procedure:
Phase (I): we the kernel function, and optimize the auto-encoder to compute co- variance matrix Σ for dimensionality reduction
Phase (II): we optimize the kernel based on the learned embedded features.
This two-phase procedure significantly improves the computational complexity of SGD as it reduces the dimensionality of random feature samples & IR.", D & d. When the kemel function K is fixed, optimizing the auto-encoder equivalent to the kernel learning step of et (017).
xiv

---

Under review as conference paper ICLR 2020
180
(a)
(b)
(c)
(d)
Figure 3: evolution of the empirical measure (E) = Σ 8(E <th)) of the SGD particles ....... <o IR² different iterations m. The empirical measure of random feature maps scemingly con- verges to Gaussian stationary measure corresponding a Gaussian RBF kernel. Panel (a): m Panel (b): m 300, Panel (c): m 1000, and Panel (d): 2500.
A.0.2 STATISTICAL HYPOTHESIS TESTING WITH THE KERNEL MMD
Let Vi, Vn LLid. Pv N(O, (1 A)daxa), and Wi. W. Rid Pw N(O, (1 A) laxd). Given these i.i.d. samples, the statistical test T( 1m la pm Wm - {0.
((V (RE (W,)a
used distinguish between these hypotheses:
Null hypothesis Ho Pv Pw (thus X = 0),
Alternative hypothesis H; Pv + Pw (thus X > 0).
To perform hypothesis testing via the kernel MMD, we require that H.x is a universal RKHS, defined on compact metric space X. Universality requires that the kernel (---)) -) be continuous and, H.x be dense in C(X). Under these conditions, the following theorem establishes that the kernel MMD is indeed metric:
Theorem A.1. (METRIZABLITY OF THE RKHS) Let F denotes a unit ball in a universal RKHS Hx defined compact metric space X with the associated continuous kernel K(-,-). Then, the kernel MMD metric the sense that MMD x [Pv, Pw] = 0 and only if Pv Pw.
To design test, let T. 1 ΣN k= 8(E
4% denotes the solution of SGD in equation 15 for solving the optimization problem. Consider the following MMD estimator consisting of two

---

Under review as conference paper ICLR 2020
U-statistics and an empirical function
N
MMD K N [(V))
(Wi)==))
c(((V), (((())))) E
m(m m 1)
k=1 i
(n 1)
2
((((W)) (V))
(28)
nm
Given the samples (V) and (W,)== we design a test statistic as below
T(VV (WT) def HD if HMMD & PM ou [V]] (W.)=] ST
(29)
H if MMD K J (V)) (W.)L >T,
where E IR is threshold. Notice that the unbiased MMD estimator of equation 28 can be negative despite the fact that the population MMD is non-negative. Consequently, negative values for the statistical threshold r equation 29 are admissible. In the following simulations, we only consider non-negative values for the threshold т.
Type I error is made when Ho is rejected based on the observed samples, despite the null hy- pothesis having generated the data. Conversely, Type error occurs when Ho is accepted despite the alternative hypothesis H₃ being true. The significance level of test is upper bound on the probability of Type error: this a design parameter of the test which must be set in advance, and is used to determine the threshold to which we compare the test statistic. The power of test is the probability of rejecting the null hypothesis Ho when it is indeed incorrect. In particular,
Power [rejeett Ho/H; is true).
(30)
In this sense, the statistical power controls the probability of making Type errors.
A.0.3 EMPIRICAL RESULTS
In Figure 3 we show the evolution of the empirical measure ( (E) of SGD particles by plotting the 2D histogram of the particles ... A. E IR" at different iterations of SGD (D = d). Clearly, starting with uniform distribution in Ja). the empirical measure seemingly evolves into a Gaussian measure in Figure d). The evolution to a Gaussian distribution demonstrates that the RBF Gaussian kernel corresponding to a Gaussian distribution for the random features indeed provides a good kernel function for the underlying hypothesis test with Gaussian distributions.
In Figure we evaluate the power of the test for 100 trials of hypothesis test using the test statistics of equation 29 To obtain the result, we used an autoencoder to reduce the dimension from 100 p 50. Clearly, for the trained kernel in Panel (a) of Figure the threshold for which Power increases after learning the kernel via the two phase procedure described earlier. In comparison, in Panel (b), we observe that training auto-encoder only with fixed standard Gaussian kernel K(x,, 3) - attains lower thresholds compared to two-phase procedure. In Panel (c), we demonstrate the case of a fixed Gaussian kernel without an auto-encoder. In this case, the threshold is significantly lower due to the large dimensionality of the data.
From Figure 4 we also observe that interestingly, the phase transition in the statistical threshold not sensitive to the parameter X. This phenomenon can be justified by the fact that the kernel learning indeed improves the MMD value more significantly for smaller values of À (i.e., more difficult hypothesis testing problems) than larger values of X. See Figure 5
xvi

---

Under review conference paper ICLR 2020
000
0=
1-0,9
Power of the test
0.8
0.5.5
1m0.5
Power of the tost
0.8
1.0.55
000.
1-0.1
1=0.11
0.6
0.4
Power
0.4
0.4
0.2
0.2
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
threshold т
threshold (b)
threshold 7 (c)
(a)
The statistical power versus the threshold r for the binary hypothesis testing via the unbiased estimator of the kernel MMD. The parameters for this simulations are À {0.1, 0.5, 0.9). 100, p 50. Panel (a): Trained kernel using the two-phase procedure with the particle SGD in equation 13 and auto-encoder. Panel (b): Trained kernel with auto-encoder and fixed Gaussian kernel with the bandwidth 1, Panel (c): Untrained kernel without auto-encoo eoooeer
Figure 4:
d = 100. n + m
PINO TAAAA
2.
1.5
3.0
25
Earations
(a)
(b)
(c)
Figure 5: The MMD value during the two phase procedure for the kernel training. In the first phase, an auto-encoder is trained (blue curve). In the second phase, the kernel is trained using the embedded features (red curve). Panel (a): = 0.9, Panel (b): = 0.5, Panel (c):A = 0.1
B EXPERIMENTAL RESULTS LSUN BEDROOM AND CELEBA DATA-SETS
In this section, we present additional simulations using Celeb Liu et al. (015). and LSUN bedroom et. 2015) data-sets. The LSUN dataset of bedroom pictures resized to 64 x 64, and the CelebA dataset of celebrity face images resized and cropped to 160 x 160. The sample generated images
are shown Figure 6
The inception score for LSUN bedroom data set is 3.860 + 0.0423 using single Gaussian kernel with the bandwidth of 16, and 4.064 + 0.061 using proposed method in Algorithm I
C PROOFS OF MAIN THEORETICAL RESULTS
Before we delve into proofs, we state the main assumptions underlying our theoretical results: Assumptions:
(A.1) The feature space X' -UW c Id compact with a finite diameter diamm(') < oc, where V support(Pvv and W support(Pw) are the supports of the distributions Py and Pw respectively.
xvi

---

Under review as conference paper ICLR 2020
(b)
(c)
Figure 6: The sample generated images from CelebA (top row), and LSUN bedroom data sets (bottom row).
Panels (a): Proposed MMD GAN with automatic kernel selection the particle SGD (Algorithm IT. Panels (b): MMD GAN Li al. 2017) with an auto-encoder dimensionality reduction conjunction with a mixed RBF Gaussian kernel whose bandwidths are manually tuned, Panels (c): MMD GAN Li et al. (2017) with a single RBF Gaussian kernel with an auto-encoder dimensionality reduction in conjunction with a single RBF Gaussian kernel whose bandwidth is manually tuned.
(A.2) The feature maps are bounded and Lipchitz almost everywhere (a.e.) E IRP, In particu- $) L1, and supGER? (=; <
lar, sup=Ex (:p(;; E) < Lo. sup=ex I [[Ve<(<;; del
L2. Let L max Lo. L1, L2} < +00.
(A.3) Let M (E) del E 8(E < denotes the empirical measure for the initial particles ....... EN We assume that A (E) converges (weakly) to deterministic measure μuu E M). Furthermore, we assume the limiting measure is absolutely continuous w.r.f. Lebesgue measure and has a compact support support(uo) = C P...
N
Notation: We denote vectors by lower case bold letters, e.g. (II, , .n)) E IR", and matrices by the upper case bold letters, e.g., M [My] " The Frobenius norm of matrix is denoted by || E My 2 Let (x) {y IR
y1 æ||2 r} denote the Euclidean ball of radius r centered at æ. For given metric space X, Let C₂ CR(I)) denote the space of bounded and continuous functions A' equipped with the usual supremum norm
Il loo
def
sup [f()). x
(31)
Further, Ch (Xt) the space of all functions in Cx(X) whose partial derivatives up to order l are bounded and continuous, and C. (X) the space of functions whose partial derivatives up to order are continuous with compact support.
xvii

---

Under review as conference paper ICLR 2020
We denote the class of the integrable functions/ / with J(t) 2 a.e. on 0 S S b by [_ Similarly, _ [o, I] will denote the essentially bounded functions with f(t) 2 0 almost everywhere. For given metric space X' we denote the Borel o-algebra by B(X). For Borel set B E B())), the measure value of the set B with respect to the measure is given by (B)). The space of finite non-negative measures defined on X' is denoted by M(X). The Dirac measure with the unit mass at X' is denoted by ((x). For any measure ja E MM()) and any bounded function Cb(2), we define
() del J (()))((a))
(32)
The space M(X) is equipped with the weak topology, i.e., a (random) sequence {u NEN con- verges weakly to a deterministic measure μ E MM if and only if (4² .f) - (n. f) for all
E (x)).. We denote the weak convergence by ju, weakly μ. Notice that when X is Polish, then M(X) equipped with the weak topology is also Polish PJ For a Polish space X, let Dx T)) denotes the Skorokhod space of the cádlág functions that take values in X' defined on [0, We assume that Dx([0 T)) is equipped with the Skorokhod's J, Jitooollggy (Billingsley (013)) which in that case Dx (x( TT) is also Polish space.
We use asymptotic notations throughout the paper. We use the standard asymptotic notation for sequences. If a and by are positive sequences, then on = O(b,) means that lim supn_+oo an/Un < oo, whereas an (bba)) means that lim inf an /n/b,,
O. Furthermore, On (bb)) implies a, = -bb,,,poly log(bb))), Moreover an = o(b,)) means that lim,-+oo an/b,, = 0 and a, = (b,))
means that litn- On Un/bn = 30. Lastly, we have a, (bb.. if = O(b,) ) and a, ((b.).. Finally, for positive a, > 0, denote a S if a/b b is most some universal constant.
Definition C.1. (ORLICZ NORM) The Young-Orlicz modulus is convex non-decreasing function di : RR+ + .. such that (0) 0 and (xx) + co when x + co. Accordingly, the Orlicz norm of an integrable random variable X with respect to the modulus &b is defined as
|| ll def inf > 0 [XI(IIXI - X [1/3)] 13.
(33)
- 1. Accordingly, the cases of || and || l| norms are called the sub-Gaussian and the sub-exponential norms and have the following alternative definitions:
In the sequel, we consider the Orlicz modulus v (x) del (x²)
Definition C.2. "SUB-GAUSSIA NORM) The sub-Gaussian norm of a random variable Z, denoted by || p2z. is defined
| ll = sup 1/2 -/ (|)
(34)
q21
For random vector Z E IR", its sub-Gaussian norm is defined as follows
Z
|/2 = sup
|| [z, Z)
(35)
Definition C.3, SUUNEXPPNENTIAL NORM) The sub-exponential norm of a random variable Z,
denoted by || p is defined as follows
| v - (IE (
(36)
921
For a random vector Z E IR", its sub-exponential norm is defined below
Z |/
sup --
(Z,z))l
(37)
'A topological space Polish if is homeomorphic to complete, separable metric space.
xix

---

Under review as conference paper ICLR 2020
C.I PROOF OF THEOREM
By the triangle inequality, we have that
MMD,.. [Pv, Pw.] MMD2N Pv. PWN] where the terms A,, i = 1, 2,2,3, 4 are defined as follows
S + A2 + As A4;
(38)
A def
MMD,.. Pv, Pw.] WEW NEP
min sup MMD MIV,,(Pv.al Pwl
A2
def
min sup MMD, (IM,,(PV, Pw] WEW HEP
min WEW a EPN
sup MMD Nx
Pv. Pw
Ag def
min WEW
sup ENEPP EPx
MMD
IN Pv, Pw
MMDRN uN Pv.
A4
der
MMD ON
Pv, W
MMMD
AN
Pv ]w
In the sequel, we compute an upper bound for each term on the right hand side of equation 38
Upper bound on A₁:
First, notice that the squared kernel MMD loss in equation 4 can be characterized in terms of class labels and features defined in Section 3.1 as follows
MMD, p. (v, Pw] p2: [ +)]
(39)
To see this equivalence, we first rewrite the right hand side of equation
39 follows
L p82
=
( = +1 +1 IE
pas2
[K (x. 3)]
=lu=+1
+ (P = 1P
00, ã- p82 p 1)IF
[K (ar, ]}]
[P = - 13P1 = +1 Paly=~a +==+1 [K R)]
(p - +1
EmPP [K k)]. (40)
Now, recall from Section 3.1 that Paly=+1= Pv, and Palg=-1 Pw by construction of the labels
and random features. Moreover, y, y wi.d U and thus IP -1 = Pp
+1} 2. Therefore, from equation 40 we derive
LE psz K (x, IF pe (2; x) + EE pes K (x; PPy. (x,
MMD,,.PV Pw].
For any given W E W, we have that sup MMD, y [Pv, Pw] sup pEP
MMD,,,.PP Pw|l
S sup PEP
MMD (Pv, Pw] MMD,,(P. Pw]]
4 sup MEP
1
Σ
Uilly K, (20 (20 xt,) - BE pgg lN0 n (x. R)
n(n 1)
4 sup PEP
EE [En
S 4 sup IF,, (F) μEP

---

Under review as conference paper ICLR 2020
where the error term defined using the random features
(E)
3600 (n ()s((); P2 (0p {)s E)].
(41)
n(n2
Now, we invoke the following strong duality theorem Gao & Kleywegt (016):
Theorem C.4. (STRONG DUALITY FOR ROBUST OPTIMIZATION, (GAO & KLEYWEGT 2016
THEOREM 1)) Consider the general metric space (E, d), and any normal distribution E M(),,
where M(E) is the set of Borel probability measures on E. Then,
[[)() Wp v) S R)
min AR
inl Add (E, W(3))u(as}. (42)
sup (EM(E)
X
JS
provided that is upper semi-continuous in E.
Under the strong duality of Theorem C.4 we obtain that
sup [Pv, Pw] - sup MMD Pw] μEP
μEP
[AIEE C1I Ex(()))o(dE) }11 (43)
min A20
AR
inf CETRD
In the sequel, let p = The Moreau's envelope Parikh Boyd (0114) of a function f: + IR defined as follows
(y)
def inf
23 1
v1ž + [(x)
E X,
(44)
TEX
where 0 is the regularization parameter. When the function f is differentiable, the following lemma can be established:
Lemma C.5. (MOREAU'S ENVELOPE OF DITTERENTIALEE FUNCTIONS) Suppose the function
f f: is differentiable. Then, the Moreau's 's envelope defined in equation 44 has the following upper bound and lower bounds
3
{' Lo
f(y)
sup IV + s(x yd) & Mf(e) = fly).
(45)
2
wEX
In particular, when f Lipsschit we have
313
(
< Mf s f(v)-
(46)
The proof is presented in Appendix D.I
Now, we return to Equation equation
43
leverage the lower bound on Moreau's envelope in
equation 45 of Lemma C,5
as follows
sup MMD,, [Pv, Pw] sup MMD, [Pv, Pwi PEP
PEP
<4 min A20
XR
M E. (s)vo(dE)
IRD
< min
XR² + E EE (E)]
+ 4X
IF
sup CEIRD
|VF ((1 8) + sc)l
A20
/ sup CERP
< E E,, (E)] + 44IE
VE, ((1 3) + sc)l
(47)
xxi

---

Under review as conference paper ICLR 2020
Let C. = (- 8) arg suP<Em=
En 1 - 5) + aCI12.
Then, applying the union bound in
conjunction with Inequality equation 47 yields
IP
sup MMD Pw] PEP
sup (Pv, Pw]l Pw/l220 26) MEP
(
$ IP
(x(E))((
+ IP
[[VE,((1- s) (d.))3ds 2
8
8R
(48)
Now, we state the following lemma:
Lemma C.6. (TAIL. BOUNDS FOR THE FINITE SAMPLE ESTIMATION ERROR) Consider the esti- mation error En defined in equation 41 Then, the following statements hold:
= F. (E) is sub-exponential random variable with the Orlicz norm of [| S 9x2xx1 for every IR. Moreover,
IP (1 / [ -) +c.) (G.)spds) 26) S 2e
2a
axx2x
(49)
(E)(E) is zero-mean sub- Gaussian random variable with the Orlicz norm of [E), I 16v3L' for every & E DR. Moreover,
IP (1/e E (E) RRD
2g2
2 2 2e
1673ET
(50)
The proof of Lemma C.6lis presented in Appendix C.2
Now, we leverage the probability bounds equation 49 and equation 50 of Lemma C.6 to upper bound the terms on the right hand side of equation 48 below
2,2 S Vax2 +
IP
sup MMD,,. Pwl PCP
sup MMD,,(P, Pw] μEP
Pw] 20
Dx KRLT +
2 VEx2IXXL
26
S 4mmxx
5X2IXXREE
(51)
where the last inequality comes from the basic inequality + b maxfaa b}. Therefore, with the probability of at least 1 have that
sup MMD,,Pv, Pw] sup MMD,,, (Pv, [w] Pw] NEP
HEP
31 x 2 x 2
9 x 22 x
RL
4e 4/
}
max
n
n2a
In
(52)
for all W E W.
Lemma C.7. (DISTANCE BETWEEN MINIMA OF ADIACENT FUNCTIONS) Let v ((W) W - IR and (W): W IR. Further, suppose (W) ((W) 8 for some > 0. Then,
min wew
((W) min ((W) S.. wew
(53)
xxii

---

Under review as conference paper ICLR 2020
See Appendix DD4 for the proof.
Let (W) del
MMD,, (v. Pwl, and (W) def
Then, from
Inequality equation 53
we have the following upper bound on A
A
MMDD,. J. Pw.]
min sup MMD, ,M (Pv, Pwl WEW NEP
min sup MMD Pw] WEW PEP
min sup WEW PEP
(PV: Pwi]
44
34
x
2 x
L
4
9 x
2
RL
4e
S max
ln
In
(54)
0
n1a
0
with the probability of (at least) 1 - 0.
Upper bound on A2:
To establish the upper bound on A2, recall that
MMD AN (Pv,Pwl n(n 1)
yay (ay ((()ii)
(55a)
inf
MMD,IIV,PPr Pw] a(n 1)
Σ izj
ya,, (o0
(55b)
Therefore,
sup MMD,I.h Pw]] EEP
sup MMD pm (Pv, Pw|
T CPN
S sup E (a,; {)x((r;;
sup (p(] (56) NNEPN
μEP
Here, the last inequality is due to Theorem C.4 and the following duality results hold
-f
PEP (=)
sup () E)] = inf
AR²
IRP
inf {AllE
<11 - (m(:: ()s(m ())o((
X20
CERD
(p E)] MM
sup
inf A20
An?
Σ
inf
(AIEE
<11 pla () c)
N
SERD
Now, in the sequel, we establish a uniform concentration result for the following function
Tha : IR NXD + IR
<b .
in (
Σ
N
2x
)et (E)) f M 2x (o(m.)
(E)ooo))) (E)))
N
Then, from equation 56 we have
sup LV. Pw] REP
sup
MMD n (Pv, Pw. < sup sup x aE
T Th (E) (E).... , ,5,5). (57)
T PN
We now closely follow the argument Rahimi & Recht (2008) establish uniform concentration result with respect the data points x, ã X. In particular, consider an c-net cover of X' C IR".
xxiii

---

Under review as conference paper ICLR 2020
Then, we require N.
4diamm(a))
balls of the radius > 0, e.g,, see PPollard 1990 Lemma
4.1, Section 4). Let Z { [ C X' denotes the center of the covering net. Now, let (Eh.... EB. .6....))))) E IR NxD and (6..... -.....
E IR NxD be two sequences that differs
in the k-th coordinate for
N. Then,
(E). ... Eb. .56 T(z,,,)) (E): E.. ... 66'1
N M (())))()))) (Eh) - M 2x
p(.. 5
(58)
Without loss of generality suppose 28
(E6) 2 M
(())))(Z)))) (EI). Then,
(=))) (=())))
M 24
((a (Eb) M (( (E))
= inf {Nls <bl12 - (z: (z) {)}
inf SEIR
AlIc Eb - p(z:; ()s((z;;)) {)
Seal
(2)
-p(z 46 (z); +
inf
Alls 11122 plzz: ()s((z))))
CERP
(b)
((z et) (z); (t) + sup
{p(z) <)p((z;))) C))
EERR
(
$ 2L2.
(59)
where (a) follows by letting Ç E in the first optimization problem, (b) follows by using the fact that < $b is non-positive for any Ç E IR and can be dropped, and (c) follows from Assumption ().
Now, plugging the upper bound in equation 59 into equation 58 yields
2L
IT (T (E), 46.... ..... <6") T (x, z, (5)
S
N
From McDiarnid's Martingale inequality McDiarmid (1989) and the union bound, we obtain that
IP (UZnzJez|T (T),, ( . 2 8) (Adiam(2)) (
No L
(60)
for all A 2 O. Now, consider arbitrary points (x, a) E X x M. Let the center of the balls containing
those points be 2,, z, Z, i.e., E (2;))) and To [B, for some 2;, 2j E Z. Then, by the triangle inequality, we have that
46")
Ti (Eo.
(E),
$ Th (E).
=60) T T/2,,0) 88 (E) ,6"M
Th (,. (Ed,
665) T( (5) -66"11
< V (Sb
-b )lll|a 21112 + | Ti ... ... Mla - x, ll
$ 2LTc,
(61)
where LT= = Lr(E), ... EN def of the mapping T. Note that the Lipschitz constant Lr random variable with respect to the random feature samples .......6. ,N. Let (x., a.) argsup | TA
supa,axx V (m.a) (E). . 112 ll is the Lipschitz constant
def
(E ..666 1|2-
xxiv

---

Under review conference paper ICLR 2020
We compute an upper bound on the second moment the random variable Lr as follows
Eo
[[+]
Ep
Vo..n....... (E). .... )1
N
Epp
V p(an))))(( (50)
VaM
-p(=x (5) (dE)
RRD
k=1
N
Em |1
Ep
v M (( (0( (Et)
V Va p(w. -p(m. (E)
R.D.
k=1
N
27
Puo
Σ
V M (e( (E6)
N2
We further proceed using the triangle inequality as well as the basic inequality (a1 + a2 + + aN)² s Naa + a² +... a²x)
27
E 140
L3
BnO
V M 24 (
) (E0)
N2
2
S
Eno
V M s ( (56)
(665)11)
N
N
|1
Eno
V M p(a me)
(E6)
(62)
km
To proceed from equation 62
we leverage the following lemma:
Lemma C.8. (MOREAU's 's ENVELOP OF PARAMETRIC FUNCTIONS) Consider the parametric function f X' x θ + IR and the associated Moreau's envelope for given O E θ C IR
M
(a) = inf ((:00)
1 + f(y:0)
(63)
yEX 23
Furthermore, define the proximal operator follows
1
Prox f(-0) (2)
arg inf yEX 2,3
|
2112 + f(y:
(64)
Then, Moreau's 's envelope has the following upper bound
VeM f( (z)
< Vee (
(65)
The proof is presented in Appendix
D.2
Equipped with Inequality equation hand side of equation 62 as follows
65 of Lemma C.8
we compute upper bound on the right
N
IF
E
Va ( L
(66)
N
Ar
where the last inequality is due (A.2).

---

Under review as conference paper ICLR 2020
Invoking Markov's inequality now yields
8
IP (E) ..0' -66) 2,),, (Eb....
-60' 20) "
PP
LT
2c
IF
[T
8
T,1
(67)
Now, using the union bound, for every arbitrary pair of data points (a, σ) E X X the following inequality holds
IP (TTr, ... .60 6) < IP (IT ( ,., 2 8/2)
+ IP
(T) . ..6)) -T T(x (E): 56 2 8/2)
(68)
26 (20 La +
(Adiam(2))
d (- No2
L2
Following the proposal of Rahimi & Recht 2008), we select e = (K1/ atz, where 1n def 28262 24=x+24 and (2/5)²LA4 Then,
(
( )²
N82
IP
ITA (m. (E), xx
sup
< 28
( (
8
Thus, with the probability of least - e. the following inequality holds
2 N"diiam 2 (x) (2Ndiam())))
L2 + 2) W , )1
sup sup (T X O
(E)
(69)
N
where W(.) is the Lambert W-function ! Since W(x) S In(x) for x > e, we can rewrite the upper bound in terms of elementary functions
(d N
2 Ndiam (X)
sup sup m
(5 ... 1
In
(70)
0
provided that N is sufficiently large and/or i sufficiently small so that 2 Ndiam' (x) Inequality equation 70 equation 57 now results in the following inequality 9
Plugging
Ld + 2) In Ndiiimn(
sup MMD Pv, Pw] P
sup MMD as (Pv, Pw]] S ePx
(71)
2
for W E W. Employingequation 53 from Lemma C.7 now yields the following upper bound
A
min sup MMD, [Pv, Pw] WeW PEP
min sup WeW ENEP
MMD [Pv.Pw) Pw
1 (d + 2) N
28 Ndiiam?
Int
(72)
0
RReall that the lambert W-function the inverse the function f(W) = W.W
xxvi

---

Under review conference paper ICLR 2020
Upper bound on Ag:
Recall that the solution of the empirical risk function of equation 14 is denoted by
(W..
del'
arg min WEW
arg
inf
MMD
(Pv, Pw!
j. ENE
arg min arg sup
8
Σ Isicjsn
y:ls ep ee (pp));
n(n WeW PPN
8
(I (12 ()(()))))))
(73)
n 1)a: isicjEn
We also define the solution of the empirical kernel alignment as follows
(W
Po
N arg min WEW
def
arg
sup INEPN
MMD (Pv. Pw]
V:,, (x(a;; ())
(74)
n(n
SSicjnn
Due to the optimality of empirical measure following inequality holds
T for the inner optimization in equation 73
MM [Pv, Pwwl MMD
py
(Pv, Pwyl
8 n(n
yeg (p(ax;;))(() ()p(( E)].
(75)
IgkjSnn
Upon expansion of MMD
[Pv: pw.: and after rearranging the terms in equation 75 we arrive
at
MMD ng [Pv, P
Pwyl
MMD
AN Pv, Pwyl
8
Σ
(e ppla, (p(a;; (,y E)] - 1u [sp( (xy E)))
nnn
ISikjEn
8
Σ
(Bay (p(a))
n(n 1)a
Igi<sSn
8L"
(76)
where the last inequality is due the fact that for the outer optimization problem in equation
||
by (A.1). Now, due optimality of W
we have
MMD aa
[Pv,
w
MMD AN [Pv. Pw
(77)
Putting together Inequalities equation 76 and equation 77 yields
1L*
MMD
[Pv.
P
[yy]
MMD pa [Pv. Pw
(78)
py
Similarly, due to the optimality of the empirical measure P. for the optimization in equation 74 we have that
MMD aN Pv, PWN.]
< MMD By Pv. Pww
MMD ng Pv. PW
(79)
xxvii

---

Under review conference paper ICLR 2020
Combining equation 78 and equation 79 then yields
81.
Aa
MMD pM Pw.
MMD 2g [Pv, Pwwyl
(80)
Upper bound A4:
The upper bound on A₁ can be obtained exactly the same way as A1. Specifically, from equation 52 it follows directly that
A4
MMDRy RM
Pv. PWN]
MMDD NN
Pv. PWN]
sup n EPN
MMD
Pv, W.W.
MMD NN
Pv. Pw..)
(81)
3 x 2 L
9 x 2
RL
4e 4
max
In
In
(82)
n
n²
!
Now, plugging the derived upper bounds in A1-A1 in equation completes the proof.
38 and employing the union bound
C.2 PROOF OF THEOREM 4.2
The proof has three main ingredients and follows the standard procedure in the literature, see, e.g., Wang et al. (2017); Luo & Mattingly (2017). In the first step, we identify the mean-field limit of the particle SGD in equation 15 In the second step,
prove the convergence of the seasured-valuee process ( Jogigr) } to the mean-field solution by establishing the pre-compactness of Sokhorhod space. Lastly, we prove the uniqueness of the mean-field solution of the particle SGD.
Step I-Identification the scaling limit: First, we identify the weak limit of converging sub-
sequences via the action of the empirical measure T (E) N E 5(g - -xh) on test function
f (IR ?). In particular, use the standard techniques of computing the scaling limits from Luo Mattingly (0177).
Recall that the action of an empirical measure on a bounded function is defined as follows
N
(f.Po)
del
f(et))
(83)
k=1
We analyze the evolution the empirical measure T via its action on a test function f E C C(((RR)) (I..).
Using Taylor's expansion, obtain
(f, Pf - (f, (f.Pm) = ( (f, DN
Vf(Eh)
<th)²² R.N
where R. is remainder term defined as follows
R.
def
c
-Ehh)
(84)
N
xxvii

---

Under review as conference paper ICLR 2020
where ş* del
and (1) E Ishh (1), - (1), for 1.2....,. -p-
Plugging the difference term (Sth (m) from the SGD equation in equation 15
results in
(f.Pm+1) (5,Pm)
(85)
N
(1N (NE (m (p@mm S aym.mm
" VV(th)
Ve Ve ((pplami Em)sp(mms stilo(mnsstt)) R.Y.
Naa
Now, we define the drift and Martingale terms as follows
D det "
Na I[ (1((,)))(( 6), MM) ayv)
(86a)
x (VI(E) ( Ves((m))) ( E)). (M). pdd ((.,, v), (7, v))
Mm del 1
Na ((((mm (m f) p - azmm Di
(86b)
x (p(()) V { + y <) Veip(eeerrn (mmm E)), pem)
D
respectively. Using the definitions of D and M in equation 86a equation 86b equation 85 as follows
we recast Equation
(f,P (f. P = D + M
+ R
(87)
Summation over é = 0, 1, 2.... m and using the telescopic sum yields
m-1
m-1
m
(f. p (f.
DD
D
M
Σ
R
(88)
We also define the following continuous embedding of the drift, martingale, and the remainder terms as follows
[NC]]
D.N
def
D
(89a)
8=
[N
M
der
M
(89b)
[Nt]
RN
RN,
1 (0,
(89c)
8=
The scaled empirical measure N.t def [ then can be written as follows
(f. (f. (f D. + M R.N. Since the drift process (D JosisT is piecewise cádlág process, we have
(90)
Ripalds,
(91)
where the functional R(p.]] is defined as follows
Riue] def // xxy ((p(0, ()p()) ayyū)
(92)
(VI()) +
+ Vep(EE))) .Pa) Pa) P dz), (dy, d7)).
xxix

---

Under review as conference paper ICLR 2020
Therefore, the expression in equation 90 can be rewritten as follows
! Rlua]ds M₁ R.²
U ( (6,
(93)
In the following lemma, we prove that the remainder term suPosigT [ vanishes in probabilistic sense as the number particles tends to infinity + oc:
Lemma C.9. (LARGE N-LIMIT OF THE REMAINDER PROCESS) Consider the remainder process
(R. Jusier defined via scaling in equation 84 equation 89c Then, there exists a constant Co 0 such that
CoT
n12 + 2nL a
sup 0STST
R -
(94)
and thus limm - suPosesT
| =0
Proof. The proof is relegated to Appendix D.5
We can also prove similar result for the process defined by the remainder term:
Lemma C.10. (LARGE N-LIMIT OF THE MARTINGALE PROCESS) Consider the Martingale
process (M, JoseST defined via scaling equation 86b eqbeeiiooon 89b Then, for some constant C > 0, the following inequality holds
IP
N M
4Vē1² VINTInC a
(95)
OSEET
Nas
In particular, with the probability of at least we have
sup
|M 4V2L² (N a²).
(96)
0StST
Nap
and thus lim suPoseST M = 0 almost surely.
Proof. The proof is deferred Appendix D.6
Now, using the results of Lemmata C.10 and C.9 mean-field equation as N - 00,
conjunction with equation 93 yields the following
L. ( (1pla, ())( - azÿÿ
? a (Hi (4o,
(97)
x (V/(E)(((2;) p(x; {)), Ma) P3 (ddx, dã), (dy, dÿ))
ds.
Notice that he mean-field equation in equation 97 is in the weak form. When the Lebesgue density Pe(E) du,/dg exists, the McKean-Vlasov PDE in equation 22 can be readily obtained from equation 97
Step 2: Pre-compactness of the Skorkhod space: To establish results in this part of the proof, we need definition and theorem:

---

Under review conference paper ICLR 2020
Definition C.11. (TIGHTNESS) set A of probability measures on metric space S is tight there exists a compact subset Sp C S such that
v(So) 2 21-5, for all A,
(98)
for all E 0. A sequence {X* JNNN of random elements of the metric space S is tight if there exists a compact subset Sp C S such that
v(X Eo) e,
(99)
for & O, and all N IN.
Now, show the tightness of the measured valued process JoSIST, we must verify Jakubowski's criterion (Jakubowski, 1986 Thm. 1):
Theorem C.12. (JAKUBOWSKI'S CRITERION (JAKBBOSKKI 1986 THM. 1)) sequence of
measured-valued process {(G two conditions satisfied:
((C)) Josest NNee NeN is tight in D PMRR)) (0, T) ifand only if the following
(J.1) For each T > 0 Dandd >> O, there exists compact set Ur, such that
lim inf IP (si" E UT Vt (0,T)) 117%
(100)
This condition is referred to as the compact-conttaimmet condition.
(J.2) There exists a family H of real-valued functions : M(RP) + IR that separates points in M(RP) and is closed under addition such that for every E H. the sequence (EH(EE ( New is tight in DıR (10, T]).
To establish (J1), we closely follow the proof of (Giesecke et al. 2013 Lemma 6.1.). .) In particular, for each L > 0, we define S₁ = B.P. Then, SB IR. compact, and for each 2 0, and N IN, we have
N
Eln (TR" (S))
(1Ef 2 B)
(101)
N
k=1
N
EF
ck
[1a]
No
(102)
N
B
Co maL LT
2
(103)
B
where (a) follows from Markov's inequality, and (b) follows from the upper bound on the norm of the particles in equation 177 of Appendix D We now define the following set
for all j E 1N]
Up { p M(IP)) ((IP//8
(104)
JB+J
xxxi

---

Under review conference paper ICLR 2020
We let UTT = Us where Un is the completion of set Un. By definition, UT, is a compact subset of M(RR)) ). Now, we have
2
P (up & UI
-
pi (R"
(S(+))))+)))))
/B +
j=1
IB El (IR" (S(+))))
1//B+: Jj
00 + 111 + +(1
(B+j)\/BB}
+ +
(105)
(B+j)
Now, since
Co + n + 2(naa)
lim
(106)
000
(B
this implies that for any y > O, there exists a B 0, such that
lim inf IP (ny E Lu E (0, (T) > 1 7 N
(107)
This completes the proof of (J.1). To verify (J.2), we consider the following class of functions
H def {H 3f E Cg (IR.) such that H (p) = (n. f) E M(RP)).
(108)
By definition, every function H E H. is continuous with respect to the weak topology of M P) and further the class of functions H separate points in M(RP) and is closed under addition. Now, we state the following sufficient conditions establish (J.2). The statement of the theorem due to (Robert, 2013, Thm. C.9):
Theorem C.13. (TIGHTNESS IN Dne ([o T)), ((Z )osesr NeN (T.1) There exists > O, such that
(ROBERT 2013
THM. C.9)) A sequence
NEN is fight in Dm ((0, TJ) iff for any > O, we have
IP
56
(109)
for all N I.
(T.2) For any p O, there exists
0 such that
IP
sup StaSpp
NNN N
2
(110)
61
This completes the tightness proof of the the laws of the measured-valued process JoifoossT]eee NEN. Now, we verify the condition (J.2) by showing that the sufficient conditions (T.1) and (T.2) hold for function values ((H ] where Hl E H and H defined in Eq. equation 108 Now, condition (T.1) is readily verified since
H( (n6'f1 Sn f(E))r (dg)
(111)
$ 11 {
uū (dE)
(112)
<b b.
(113)
xxxii

---

Under review as conference paper ICLR 2020
where in the last step, we used the fact that (IRIP) and hence, 11/1l < b. Thus, (H (1)) Z
b) O for all N E IN, and the condition (T.1) is satisfied. Now, consider the condition (T.2). From
Equation equation 93 and with
l2 S T have
H H( H( = 1f. M4) - (f. M
J,
l2
[ M Ma I R
(114)
To bound the first term, recall the definition of R(us] from equation inequalities holds,
The following chain of
[R[u.]] - IE rea [1x () E) 3
$ E paa (1p(a, ())((, (), +
,,)']] (115)
Let 1: IR_ + R. (E) denotes the identity function. Notice that (1, p.) Smp Ms (ds) 1.
From equation
113 proceed follows
|R[u.]]
IB pe [11p11 |01, M.)l a) ()
pla [1
1100
K.
s EE aa (111120 aa) [
2n (L2 ,)
(116)
where the last inequality is due (A.1). Therefore,
l [Rlpeldds S soltt2 - t2l.
(117)
(T.2 21 (T.2 + ao)
where
Consider the middle term of equation 114 tion 89h we obtain that
Using the definition of the martingale term in equa-
NNDJ
[Nta]
M
- M
Σ
M
M
t=
t=
[Nta]
Σ
M
(118)
Fm [N]
In Equation of Section
D we have proved the following concentration bound
22a2s2
P 2 c) 2
Vm E NT, N..
(119)
Now, recall the alternative definition of the sub-Gaussian random variables:
Definition C.14. (SUB-GAUSSIAN RANDOM VARIABLES BOUCHERON ET AL. (013) A ran-
dom variable X is SasuusGaussin if
X202 (-2
[E(((X - E[XI) <
(120)
xxxiii

---

Under review as conference paper ICLR 2020
We enumerate a few standard consequences of Sab--aussianity Boucheron et al. (201)). X; are independent and Fe--sub-Gausiine then Di=1 X; is Ei=1 o'-sub-Gaussian if and only if
of Sau-Gausii Moreover, X is
2²
P[[ E[
2
(121)
20
Now, it is clear from equation
119 andthat M N sub- Gaussian random variable with a zero mean,
and with the parameter o 4mL 4 C7 + +a)² Therefore, _e=[No, M is sub-Gaussian
N²
def 2L
C9
+ +a)
with the parameter (² (2) sequently, from Inequality equation TT8 and the concentration inequality in equation
(LAVt)) [Ntz]] + [ + [Ntt]]. Con-
22
121
we have
[ Σ
IP
sup
MM - M 28
IP
sup
M
2 E
(122)
N=
= PP
M
2E
(123)
p= [
E²
2
(124)
o2 (2
a²
22
(125)
AL*1 app 1)7
where tg) def arg st -tl
[e=(Nt,] M
We first compute bound for the last term of equation 114 using the definition of the scaled term R. from equation 89c We have
NNG
[Ntal
IR
R.N
Σ
R
Σ
R
[Ntal
Re
N
Σ
|Rel
1= [Nti]
Co (nL2 + (L)
||
[Ntill N2
lt2
tıl.
(126)
where (a) follows from the upper bound in equation 178 of Section Cu
and in (b) we define s def
N (nL² + +(**/a)
xxxiv

---

Under review as conference paper ICLR 2020
Putting together equation 117 tion 114 that
equation 122
and equation 126 we conclude from Inequality equa-
( H( σ) IP
M - (5o + 51)p 2 o)
M
sup C1ita STi
sup
histTT -t2lsp
a² (5o + s1)p)²
AL + 1)T
Therefore, condition (T.2) also satisfied. Since the sufficient conditions (T.1) and (T.2) are sat- isfied, the condition (J.2) is satisfied. This completes the tightness proof of the measured-value sequence {ur NEN.
Now, we prove its convergence to mean- -ieldfiildddd solution (et )osISTTT
Theorem C.15. (PROKHOROV's THEOREM PROKHOROV (1956)) subset of probability mea- sures on complete separable metric space is tight if and only if it is pre-compact.
According Theorem C.15 the tightness of the Skorkhod Space DM(RD) ((0, ((,,T) implies its pre- compactness which turn implies the existence of a converging sub-sequence {ur JosegT]N, of {uy NNN Notice that {(u)" N is a stochastic process defined on the Skorkhod space. Therefore, let N denotes the law of the converging sub-sequence ((44 (ISEST),, By definition, No is an element of the measure space M(D (M((R)))) In the sequel, we closely follow the argument of (Wang et al. 2017 Proposition 4) to show that the limiting measure x is Dirac's delta function concentrated at mean-field solution μi E (Po.((((RP)) We define the following functional
Fe (M((R)))) + IR,
14 Fi[mo] (ue, (po, Rluadds
(127)
We compute the expectation of the functional F; with respect Ne. We then have
E,, [F(()) [E[F[
LE | ( L( MiNNs
(128)
Now, from Equation equation 93 we have that
[
f
(0 No. f)
Rlu No Ids -M.- - R.N.
(129)
Plugging equation 129 equation
128 gives
Ex,, (F((
IE Fr [
Ni
IE M + R.
EE sup |M 0SEST
sup
RR
OSEST
CoT
Nap 4V212 2 (I +a) + (naL'T LT)),
(130)
N
where the last equality is due to the bounds in equation 94 and equation
95 of Lemmata C.9 and
C.10 respectively. Taking the limit of N from equation 130 yields
lim E [[[]]]]] = 0.
(131)
N 000
XXXV

---

Under review as conference paper ICLR 2020
can be shown that the functional Fr[:] is continuous and bounded. Therefore, due the weak con- vergence of the sequence Nx NNEN to Th, equation 131 implies that
F [r()]] = 0.
(132)
Since the identity equation 132 holds for all bounded test functions f E (IR and for all (0, it follows that xh is Dirac's delta function concentrated at a solution (pī)o of the mean-field equation.
Step Uniqueness of a mean-field solution: Before we establish the uniqueness result we make two remarks:
First, we make it clear that from the compact-containment condition (J.1) of Jakubowski's criterion in Theorem C.12) the support of the measured-valued process (14 Jogrgr (7[ Josigr is com- pact for all 2 t s T. Moreover, in Step 2 of the proof, we established that the measure valued process (14² J0SEST converges weakly to mean-field solution as the number of particles tends to infinity (i.e., N + oc). Thus, all the possible solutions of the mean-field equation also have com- pact supports. Let E IR. denotes compact set containing the supports of all such solutions 0 S S T. In the sequel, it suffices to establish the uniqueness the mean-field solution for the test functions with a compact domain, i.e., let f C
Second, for all bounded continuous test functions f ()) the operator f - (Me: f) is linear operator with [4r (IR-)
Hence, from Riesz-Markov-Kauuke representation theorem Rudin 1987;; Varadarajan (958)) by assuming 14 M(RR). existence of unique operator implies + (f. (4) implies the existence of the unique probability measure 14. Now, we equip the measure space M(RP) with the following norm
Kf. lf
|a def
sup
(133)
SEC
[f o/ 200
Given initial measure μo. we next prove that there exists most one mean-field model solution by showing that there exists at most one real valued process (j4, I' corresponding to the mean-field model. Suppose (H," Jogegr, (u, JogesT are two solutions satisfying the mean-field equations equation 997 with the initial distributions ub. 1 <M(RRD), respectively. For any test function C have that
" L. (JJrr (G 22 (nd 1o.
E).1a p. ayÿ)
(134)
(V (Vr(t ((ax
uga 2) p02 p dī) ds.
We bound the first term on the right side of Equation equation 134 as follows
(n)
2 f) < 1l - Hill |l
(135)
< blllb pall.
(136)
where used the definition of the norm
|| on the measure space M(R from equation 133
xxxvi

---

Under review as conference paper ICLR 2020
Furthermore, let
J| ayo( cyglVVile/Veelolaa))aaaaa .4 - pag y). d( 7))
$ $1 aly . VVV
,10 n4 2 (d(æ, y). d(
$ sallps - 11:2 V](
p (da, dā
I salpat- - - Vf < {) 1) (dz dz)
S CaL"Cil -
(137)
where the last inequality, we used the fact that [ < C₁ since the test function is three- times continuously differentiable f (3) on compact support. Similarly, have
f (p(2), 3),(",)),13 p. 2 (V 8)), u4 1..2) 2 (dx: dā))
S $lla - m1:213 / 11 ( VV x SLACillu - u3 21?
11 peoppet(el dā)
(138)
Putting together the inequalities equation 136 equation 137 and equation 138 yield
(4, - -2 -11b الق + 120in [. l 11 1 + n
[/ | 1., ds..
(139)
The above inequality holds for all bounded functions / E C3((E Thus, by taking the supremum with respect to ff we obtain
|| ur 11 sup SEC
(140)
$ bllb - 1 + 1.2cn ( 1100" 11, 2d2 + LACin S Ilua - 14, 21
(141)
Now, we employ the following result which generalizes Gronewall's inequality when higher order terms involved:
Lemma C.16. (EXTENDED GRONEWALL'S INEQUALITY, (WEBB 2018 THM 2.1.)) Let p E IN and suppose that for a.e. t E [0, u u [0, satisfies
u4 S colt) / (c)(s)u, + c2(s)u + Cpt1 (s)uct))
(142)
where E [0 T| is non-decreasing, and ej [0, for (1,... . 1}. Then, if
L" ()1(s) s My jE (1,2......p)
(143)
It follows that for a.e. t E [0.T]
S col)) ( ((s)ds)) (M1 +.. Mp).
(144)
xxxvii

---

Under review as conference paper ICLR 2020
We now apply the extended Gronewall's Inequality equation 142 with p 1, co(l) 160
m 0 sts (t) n, 0 S sts TT (2) n ,0 1005 S T. and U, l 1 In
this case, it is easy to see that M1 2brTD Consequently, from equation an0 equation 144 obtain that
| 14 2 S 6lpb - Mلll (nL2 26TTL
0 s
(145)
Thus, starting from initial measure d m n4. there exists most solution for the mean-field model equations equation 97
C.3 PROOF OF COROLLARY 4.2.
To establish the proof, we recall from equation
88 that
( (.P (S.P))
D
D
M
Σ
R
(146)
t-0
E=0
ビ=
for all E Ca Recall the definition of the total variation distance TV,; on metric space (X
1 TV v) sup Im(A)) v(A))-
(147)
2 ACX
The total variation distance admits the following variational form
TV(,,v)
sup
(f.p) (f.z).
(148)
Now, using the variation form and by taking the supremum of equation 146 with respect to the functions from the function class Fe def the TV distance
{f C122(IR we obtain the following upper bound on
m-1
TV
me
D
Σ
M
Σ
R
(149)
2 8=
2
8=0
Based on the upper bound equation 178 on the remainder term, we have
S
N2 (nL (2
Co
E 10,m m 1],
(150)
for some constant Co > Moreover, from the concentration incquality equation 189 we also have that with the probability of at least - 8, the following inequality holds
8. + aa) log
(
IM
(151)
Na
Lastly, recall the definition of the drift term in equation 86a method leading equation T16 it can be shown that
By carrying out similar bounding
2n
DD
<
(L2 +a)
(152)
Na
By plugging equation
150
equation
151 and equation 152 i52 into equation
149
we derive that
TV
mnnCo
1
Smm/mnL (L + a)
log 2
my (I.2 + a.
2N
No
8
Na
(153)
with the probability of 5. We now leverage the following lemma:
xxxviii

---

Under review as conference paper ICLR 2020
Lemma C.17. (BOUNDED EQUIVALENCE OF THE WASSERSTEIN AND TOTAL VARIATION DIS- TANCES, SINGH & Póczos (2018)) Suppose (X, d) is metric space, and suppose and v are Borel probability measures on X with countable support; i.e, there exists countable set X' C X such that p(x") = v((*)= ( Then, for any p z 1, we have
S (,, & Diam(X")(2TV(u.)))
(154)
where (iam( def
SuPawEx' d(r, v). and Sep(X*) def infz d(x. v).
Consider the metric space (IR |l 112). Note that the empirical measures Pm Pi have countable support X' { 1N
[E C IR.. Therefore, using the upper bounds in equation 154 of we conclude that when the step-size is of the order
Lemma C.17 and 153,
R
n= O TVNT (2g(2/6)
(155)
then W, (P p S R for all m E NT) N..
D PROOFS OF AUXILIARY RESULTS
D.1 PROOF OF LEMMA
The upper bound follows trivially by letting = y in the optimization problem equation 44
Now, consider the lower bound. Define the function g [0. + IR, t g(t) = fly t(x - y)) Then, when f is differentiable, we have g() (xr y. V/y + 1(x -y)))- In addition, ,(0)
fyy, and g(1) (x)) Based on the basic identity g(1) = g(0) + + g()dds we derive
f(x) f(y) S (or y. V.V + s(x y)))ds
2 f(v) x Ulla / VVf + s(x b) 12ds,
(156)
where the last step is due the Cauchy-Schware inequality. Using Inequality equation 156 yields the following lower bound on Moreau's 's envelope
1
L. |/ [y + s(x - 12)
Mg(r)) 2 f(y) + inf øEA
||
U|12
2,3
2
V2 2
[' IVV + s(x 122s
= -(y) + inf
x
xEX
2,3
3
(f/ || - s(x - 12)ls
2
8
| [V + 12)
2 f(v)
sup
2
xE
B
f(y)
sup
|Vf(y + +s(x 1)ds
2
xex
B
2 f())
sup æe
VVf + s(x 3)sss
(157)
2
where (a) is due Jensen's inequality.
xxxix

---

Under review as conference paper ICLR 2020
D.2 PROOF OF LEMMA
Let E IR" denotes arbitrary unit vector ||u/|2 1. From the definition of the gradient of function, we have that
(VoM 11:10) (z)), u) = Du(M
(158)
where Du. ((-o))) is the directional derivative
M M
M (()
Du(M
del lim 8-0
(159)
We now have
1
M((:066)(
inf
x
212 + s,y; +u)
#EX
2,3
1
inf
x
21ا + f1: 0) + ([Vo](y; + 0
#EX
2/3
(a)
x Prox
((:0) (z) ((
23
+ (Prox 0), u) ()²),
(160)
where the inequality (a) follows by letting y = (iox)( (z) in the optimization problem. Now, recall that
1
- - + + fly: flv:0) )
(x) = inf yEX
2,
(() = arg min
1
| - u1l + f(v:0)
yeX
23
Therefore,
1
M (x)
23 x Prox (1)00
+ ( (z)
(161)
Substitution of equation
161 in equation 160 yields
M ((=0+ōu) (x) MM (z) + ( (
(162)
Hence, Du ((.o) (z)] (Prx
((=0) (xx;; 0), u). From equation 158 and by using Cauchy- (xx;
Schwarz inequality, we compute the following bound on the inner product of the gradient with the unit vectors Idd ||u||2 1,
( (z))) u |oo ()))))
|ull2 I [ [x)
(163)
VoMe (a)
Since the preceding upper bound holds for all the unit vectors u E IRd, we let u
Ioa 1| oo (z)]la
to get Inequality equation 65
D.3 PROOF OF LEMMA C.6
Let Sd-1 denotes arbitrary vector the sphere. Define the random variable
Q₂ (11, ... (yn, (zn; def (z, (.)
Σ wons (p(an))) (2. Vep(ay;)) + p(ay (z, Vep((e;;))
(0nn 1)
1B pas (V(()())))(( Veplax; ((a,; Ves(er))))) E)
(164)
xl

---

Under review as conference paper ICLR 2020
Clearly, P.., [Q=] O. Now, let (Tm: Tm) [ triangle inequality, we obtain that
EV x S m n. By repeated application of
Q2((v1 x1). ... (ym, Tm). .. .. (Uhr xn,)) Qz ((11, (1). .. (Tm, Tm). . ... (yn xn))
Mapp 4) V/m Verp(mmi Um c E))
n(n
1)
if
1
Σ
ye(z,
Tin (3 E))
na(12
1)
fyfm
( 4) |||||2 Ilum Vel((amiE)) Im Ve E)Il
n(n - 1)
igtm
1
| (ev
Wmpp(amm E) - Im (anssp(amn (Zmi
n(n
4L2
(165)
n
where the last inequality due to assumption (A.2) and the fact that || = for 2 E S In particular, derive Inequality equation [65] employed the following upper bounds
1 E) S L,
(impp(mmmi: E) ( {) I Ip(am E)I + (pp(@m E) S 2I,
[ l) I L,
1l (m { i. (mmi l) 3 [ El + Vg E) S 2L.
Using McDiarmid Martingale's inequality McDiarmid 1989) then gives us
nu²
IP (fex((v.. ... (Uro ..,))
2 u
S 2
(166)
167,4
for x 2 Now, for every p E IN, the 2p-th moment of the random variable Q= given by
E .., (Yn, mnn)]]
2pm2 2p Spm2r-1I((22((00 (P(22((1)))))))) (1),, (yn, xxa) 2 u dl
(a)
42
2p-2
du
16n
IR+
2(161.'
2
(167)
where (a) is due to the concentration bound in equation 166
Now Therefore,
IE [[( ((31, x1), (Un, (w)n22))//?))
IE 62 ((V1 x1)..
(Nas (Yny 2n))
2l720 p=u
166,4 nry
2p
1 Σ PEIN
1 (161.4/15 1.
For = 16v3L4/n, obtain ((( (Wn, L xz)) / < 2. Therefore, ||221 (1(2, (E)(())) S 16/3L /n for all E Sn-1 and & IR" D Consequently, by the definition
xli

---

Under review as conference paper ICLR 2020
of sub-Gaussian random vector in equation 35 of Definition C.2 we have |/ E, (5) S
16v3I.4 /n for every & E TRD We invoke the following lemma proved by the first author in KKuuzani & Li 2017 Lemma 16):
Lemma D.1. (THE ORLICZ NORM OF THE SQUARED VECTOR NORMS, KHUZANI LI 2017 LEMMA 16)) Consider the zero-mean random vector Z satisfying Z
S B for every v Z O.
Then, ||I| Z Billv 2--3.. 3 8
Using Lemma D.1 now have that (5)ll,,,, I 4608L /n² for every & E IR.. Applying the exponential Chebyshev's inequality with 3 4608L /n² yields
l RDD
VIVE, S)E+ sc.) Ez,, VI ((1 s) sc.) mo(dE) 2
8 460964
n2 el 400SET
Inn Sa [IV -
$
Exg
(a)
e
Evr e 20081
- VV.. (spo((EE)
m
2e
4608
where (a) follows by Jensen's inequality, and (b) follows from the fact that
E Exyy 4608 ((--))
2
(1 [2D1 2,
(168)
due to Definition C.I
Therefore,
IP (1
VE -s)E - (c.))s(ddds)(( 26)
RD
n218 1 SRO E IVE, (1-s11----)))
s) + sc.) (dd)ssssss
2
(169)
4608L4
now remains compute an upper bound on the expectation 1Eg,. || V E,, ((1 s) + sc But this readily follows from equation 167 by letting and
VE. ((1-)((1)))))))) (
as follows
V En 8) &c.)
IF F V Fr, ((1 s){ + =(.) FFryy
VF, -)) + 8(.)
E,, ((1 5) + sc.)]l2
Exy,
Q² (EN(((-n)==7C))
< 29 1
(170)
n²
Plugging the expectation upper bound equation 170 into equation 169 first part of Lemma C.6
completes the proof of the
The second part of Lemma C.6 follows by similar approach and thus omit its proof.
xlii

---

Under review conference paper ICLR 2020
D.4 PROOF OF LEMMA
Let W, def
arg Ww (W) and Wo
def
arg minnew ((W). Then, since (W(W)
$ (W) 5 for all W W, we have that
(WW.) (W
min (WW) - ((W.) so. Wew
(171)
Therefore,
min @(W) ((W.) v WeW
min (WW) + WEW
(172)
Similarly, it can be shown that
min (W) < V (W.)
min Φ(W) 8.
(173)
WEW
WEW
Combining equation 172 and equation 173 yields the desired inequality.
D.5 PROOF LEMMA C.10
We recall the expression of the remainder term { JoSmENT from equation 84 For each 0 S NT, N IN, we can bound the absolute value of the remainder term follows
R
5m+1
- *th /2 [( (5 - - )²
k=1
N
(ch ) 2 f(5 (E -tth T
N
k=
st.
V (
(174)
N
Next, we characterize bound on the difference term c iterations of the particle SGD Equation equation 15
c ll2.
To attain this goal, we the
We have that
l|
Σ (a ethh ) Eth.) (
ve pmt l
$
N
Na
(1s0(amm; sth I/ e 2 lll + lop@@ms 5l V| 5 111l)
N
plamm 5th (mmm sthss (Ie(arms e mm ( ll1 + lyp I1l Vep((e (th)l2))
N
Na
(6)
nL
2
(175)
N
Na
where in (a), used the fact that || < L and / g E) L due (A.1), and ymu Um
(-1,1}. Plugging the last inequality in equation 175 yields
1 N3
2 +
RM
S
nn
2 f(E
(176)
xliii

---

Under review conference paper ICLR 2020
We next compute an upper bound on the Frobenious norm of Hessian matrix V² To this end, we first show that there exists a compact set IR' such that &m E C for all k = 1,2, , and all m E [0, .T) IN. For each At = 1, ... N, from Inequality equation 175 we obtain that
| lla 2 || 112 + gL
2nL
N +
No
= || + mnL + No
2mmL
N
I || 2| + nTT,²T 2(1//x)
(177)
Now, |1&/12 l < for some constant co > 0 since the initial samples Eo EN are drawn from the
measure /Ap whose support supportsupport (No) =\t is assumed to be compact by (A.3). From upper bound
in equation 177. it thus follows that c l2 C' for some constant C' > 0, for all m [0, NN (p)), where (i) 1ch (i). (t)],
Now, recall that E (1), for i = 1,2, P. Therefore, ş C. Since all the test function f C (IR)) are three-times continuously differentiable, it follows that there exists constant Co def Co(T) 0 such that
1,2, m + 1,
suptec [|v Co- From Inequality equation 176 it follows that
Co N2
1 + 2nL* m E [0,
(178)
Now, recall the definition of the scaled term R2 from equation 89c tion 178 as well as the definition of R.N we obtain
Using the Inequality equa-
CoT N
27L²
sup 0SEST
R
nn +
(179)
a
D.6 PROOF OF LEMMA C.10
Let Fm-1 = Tn-1=o((27) a((ck, yk o 1, (Øk, Te 3h)oskkm-1) denotes the o-algebra generated by the sam- def
ples up to time 1. We define F-1 (). Further, define the following random variable
A def ((5(2mm ()pp( E), (-m) orymim x (VI(E)
( ( (m {)), AM)
(180)
Notice that 1/2
D.N. We now rewrite the martingale term in equation 86b in term of
A
m
M def 1
Na Σ IAN
(181)
with M 0.
By construction of M in equation that MN has also bounded difference. To do we define the shorthand notations
181 it is Martingale I F = MN We now prove
NN def am (p(xm ()p E), P.N) a.ymnmm
(182)
b def
(V((E(VV ( (a (T) p.M).
(183)
xliv

---

Under review as conference paper ICLR 2020
Then, we compute
M Mm11
7/
A N
[F N
F
No
7
N
DI [
No
Na
"
|
E |aaM 16 F
(184)
No
Na
For the difference terms, derive that
am
(p(2mmm
(2 E), Pm)) czymmm
1 (a Sth (T 5m) + Ollymmm
< 1 a,
(185)
where the last step follows from the fact that 1001 I L due (A.1). Similarly, obtain that b ((V () E))) Pm)
me( Eth V (Vep( Et.)) =
+
pp(#mi 2*0
(V
eVess +
V f (Vpp )
V ( (Vp et))))))))) )²
N
Ve
+
V V l
2L N
[Vf(
(186)
where (a) and (c) follows from (A.1), and (b) follows from the Cauchy-Schward inequality. From Inequality equation 177 and the ensuing disucssion in Appendix D.5 we recall that ||&h l22 < C for some constant and for all
[0, NT) n IN, and k 1,2, N. For the two times continuously
test function C3 D) it then follows that [V S Ci for some constant C₁ 0. The
following bound can now computed from equation 186
20, L
(187)
N
Plugging the upper bounds on ا and 1--i from equation obtain that
185 equation
187 into equation 184 we
4nC1
M MN
(T? +a).
(188)
Na
Thus, (M m NTJON is Martingale process with bounded difference. From the Azuma- Hoeffding inequality it follows that
No
PP N 2 =) = P(M MA
52
Vm E [O, N.
SmL
(189)
xlv

---

Under review as conference paper ICLR 2020
Therefore, since M M we have
N²a2
PI 2 I
52
(190)
Then,
IE [
I E)de
N
2
SL aa)3
JO
1 4V
(TT +a)2
(191)
No
where the inequality follows from equation 190
By Doob's Martingale inequality Doob (1953) the following inequality holds
EE 1
IP
sup 0
M 2
(192)
Nos 4V222 (L a))
(193)
In particular, with the probability of at least 1 - P. we have
sup
I 4V222 /NT a)². a0)
(194)
0S1ST
Nap
E CHAOTICITY AND PROPAGATION OF CHAOS IN PARTICLE SGD
In this appendix, we establish the so called 'propagation chaos' property of particle SGD. We now establish the so called ppropagation of chaos' property of particle SGD. At high level, the propagation of chaos means that when the number of samples { N tends to infinity (N + +00), their dynamics are decoupled.
Definition E.1. (EXCIANGABLITY) Let be probability measure on Polish space S and. For N E IN, we say that O is an exchangeable probability measure the product space S if it is invariant under the permutation π def (T(1,, ... ,(N)) indices. In particular,
sNN (π B) = OBB)
(195)
for all Borel subsets B E B(S*).
An interpretation of the exchangablity condition equation 195 can be provided via De Finetti's rep- resentation theorem which states that the joint distribution of an infinitely exchangeable sequence of random variables is as a random parameter were drawn from some distribution and then the random variables in question were independent and identically distributed, conditioned on that pa- rameter.
Next, we review the mathematical definition of chaoticity, as well as the propagation of chaos in the product measure spaces:
Definition E.2. (CHAOTICITY) Suppose S exchangeable. Then, the sequence (v&N) NEN is v-chaotic if, for any natural number E IN and any test function fi.f2.".. fn Cf have
II fu(s*), & (ds!,... ... doy)) A
lim
(196)
N-+00
Rm
xlvi

---

Under review as conference paper ICLR 2020
According to equation 196 Definition E.2 a sequence probability measures on the product spaces S is y-chaotic if, for fixed & the joint probability measures for the first & coordinates tend to the product measure v(ds; ...ds))...va v(dss) = yok on S* the measures VaN are thought of as giving the joint distribution of N particles residing in the space S, then (vSN) v-chaotic k particles out of N become more and more independent as N tends to infinity, and each particles distribution tends v. A sequence symmetric probability measures on S chaotic if it y-chaotic for some probability measure v on S.
a Markov process on SN begins in random state with the distribution / the distribution of the state after /. seconds of Markovian random motion can be expressed in terms of the transition function IC for the Markov process. The distribution at time 0 is the probability measure D defined by the kernel
[
UN (B)
KC B,t, (ds).
(197)
SN
Definition E.3. (PROPOGATION OF CIAAOS) A sequence functions
{rM (s. NEN
(198)
whose N-th term Markov transition function on S. that satisfies the permutation condition
KN (s, B,t K (T B,t),
(199)
propagates chaos if whenever {D&N) INEN is chaotic, so is {UN} for any t 2 0, where U,N is defined in equation 197
We note that for finite systems size ,th states of the particles are not independent of each other. However, as we prove in the following result, in the limiting system N - +00, the particles are mutually independent. This phenomena is known the propagation of chaos (a.ka. asymptotic independence):
Theorem E.4. (CHAOTICITY PARTICLE SGD) Consider Assumptions (A.1)- (A.3). Further- more, suppose that { Widd Ho is exchangable in the sense that the joint law is invariant under the permutation of indices. Then, at each time instant E (0, (),T). the scaled empirical measure ui E EM(RD)) defined via scaling
4 (dE),... .d ".E. def (.0e",....,d))) "....(de......dd"" -P E de',
E E d
(200)
is μt, -chootic, where st is mean-field solution of equation 97
Proof. To establish the proof, suffices to show that for every integer IN, and for all the test functions fI,... ffk E (IR we have
lim sup IE N00
II (A(E)))))
1I k=1
(uG. fu) = 0.
(201)
Using the triangle inequality, we now have that
E
fo
II (pi. k=1
(A)
E
fu)
I KeG
fxx
IE
fi)
IE
II
fat (N1)
(202)
R=1
kk=1
1=1
xlvii

---

Under review as conference paper ICLR 2020
For the first term on the right side of equation 202 we have
lim sup N-to k=1
IE
fk)
II k=1
fe)
lim sup
fkk
( fk)
N-000
R=1
IE
lim sup
( fie)
II (4t fi)
N
k=1
LE
lim sup N-000
(T) Sa)
0,
(203)
where (a) is by Jensen's inequality. (b) is by Fatou's lemma, (c) follows from the basic inequality
I I bi
S Eim la: b. for lasl. [b,1 - 1, 1,2, N, well as the fact that
(44, fa) s b and (i
fu) S for all A 1, .N due the boundedness of the test functions
ft fi. E Cg IR" ). and (d) follows from the weak convergence ft. + Mi to the mean-field
solution equation 97
Now, consider the second term on the right hand side of equation 202
Due to the exchangeability
of the initial states (4%) ISNE,, the law of the random variables 1g)gg is also exchangeable. Therefore, we obtain that
E II (ffeN))))
A! N I
Σ (EII(E,N)
II fA (
(K) (NN)
(204)
where IT,,, N) the of all permutations of l numbers selected from 21, N). Notice that the right hand side of equation 204 is the symmetrized version of the left hand side equation 205
Further, by the definition of the empirical measure çi2"" we obtain that
N
II C
Sk)
EE
Σ
(205)
N
m=1
8
IE
Σ
II [
(206)
N
LxEi(eNN)
Therefore, subtracting equation 204
and equation 205
yields
55 (1
N EIVE
IE
fk)
IE
fe
(207)
-==1
Hence,
lim sup
IE
II (7 fk)
IE
II Sa (
=0
(208)
N No0
1==1
Combining equation 203 equation
208 yields the desired result.
xlviii


Reviews:
[{"review_id": "Syx3pUyf5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to improve the kernel selection issue of the MMD-based generative models. The author formulates the kernels via inverse Fourier transform and the goal is to learn the optimal N finite random Fourier features (RFF). The RFF samples are optimized by the proposed kernel alignment loss where the positive and negative labels are defined as samples coming from real and negative data distributions, respectively. Some theoretical analysis regarding the consistency of the learned kernel is provided. Experiment results on the IS score and FID on CIFAR-10 show improvement of the proposed methods over MMD-GAN baselines, while the results are not comparable to the original MMD-GAN due to unknown results.\n\nWhile motivated from the mean-field theory, the algorithm 1 is essentially doing stochastic gradient on the RFF samples with fixed learning rate. Learning spectral distribution of kernel via optimising RFF samples is also not entirely new, as [0] presented in the Appendix C4 of [1]. they show the difference between two different realization of kernel learning.\n\nI would love to increase my score if the author could address the following comments:\n(1) Can you explain why the IS and FID results of MMD-GAN presented in Table 1 is inconsistent (i.e. considerably worse) with other papers [1,2,3]?\n(2) In experiment setting, the learning rate eta of learning RFF samples is fixed to 10. Does this guarantee the learned spectral distribution lying in the constraint set P as specify in Eq (8)?\n\n[1] Implicit kernel learning, AISTATS 2019\n[2] DEMYSTIFYING MMD GANS, ICLR 2018\n[3] MMD GAN: Towards Deeper Understanding of Moment Matching Network, NIPS 2017\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJx5gjF2FB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to learn a kernel for training MMD-GAN by optimizing over the probability distribution that defines the kernel by means of random features. This is unlike the usual setting of MMD-GAN where the kernel is parametrized by composing a fixed top-kernel with a discriminator network that is optimized during training. The main motivation for this approach is to avoid having to 'manually' fix some parameters of the top-level kernel like the bandwidth of the RBF kernel. They provide an algorithm to achieve such optimization in probability space along with some consistency results and perform experiments on MNIST and Cifar10 to demonstrate empirically the advantage of such an approach over those that fix the top-level kernel.\n\nTheory:\n\tTheorem 4.1 provides a convergence result of an oracle finite-sample estimator: that is the one obtained by exactly solving the optimization problem in 19b. In that case, they show the consistency of the proposed estimator. The result is somehow expected but the proof relies on nice duality results for measures and is very technical.\t\nThe clarity of the proof could be improved:\n- Currently, the structure of the main proof mixes direct lemma (lemma B.7) with less obvious ones (lemma B.6). Also, some concepts are introduced in the main proof but not necessary for its understanding: The notion of Orlicz norm is in introduced in Definition B.3 on the fly to state lemma B.6, but only equations 50 and 51 are used in this lemma which does not make use of the notion of Orlicz norm at all.\n\n\tTheorem 4.1 doesn't say anything about the consistency of the algorithm itself. To partly address this, the authors show in theorem 4.2 that as the number of particles grows the empirical process converges to a McKean Vlasov PDE (equation 22). This means that the proposed algorithm is approximating some gradient flow in metric space (25). \n- However, this gradient flow is a non-convex optimization problem and there is no guarantee that a global solution is reached.  Recent work provides cases when global convergence occurs [Chizat2018] but it is not the case in general. Some further clarification about the connection between Thm 4.1 and Thm 4.2 would be therefore useful.\n\t\nThm 4.2 is also curious in the sense that the process defined by equation 16, which is noisy since it relies on one sample from the data, would converge towards (22) which is a Mc-valsov equation with a drift only (no diffusion or other noise).  What happened to the noise coming from sampling from P_v  and P_w in equation 16? Wouldn't there be some sort of diffusion term as in [Hu2018]?\n\t\nMore generally it would be nice to have a discussion of the assumptions and results in the paper as they seem to rely on methods that people in the machine learning community are not totally familiar with.\n\t\nExperiments:  The experiments are not convincing for several reasons:\n - The comparison with the other methods is somehow unfair since the bandwidth is manually tuned for the competing methods. It is easy to adaptively learn the bandwidth as well:  in this case, it will be just an additional parameter of a discriminator network. This was done in [Arbel2018] where a single gaussian kernel is used and a regularization of the critic allows to learn the bandwidth without manual tuning. Does the proposed method offer an additional advantage compared to those?\n- In practice and for a scaling parameter alpha=1, isn't the algorithm strictly equivalent to considering an MMD-GAN with a dot product kernel and a discriminator given by the feature \\phi(x,\\zeta)?\n- Mnist and Cifar10 are somehow very simple, what would happen on more complicated datasets (CelebA or imagenet)?\n\n- I also think there is an ablation that is missing: If the auto-encoder also needs to be optimized then does it also help to optimize over the particles as well or is optimizing the auto-encoder discriminator enough to achieve a similar performance? In other words, does optimizing the auto-encoder compensate for the need to learn the distribution mu? Of course, this would depend on how the auto-encoder is parametrized but I don't see why it wouldn't in many cases.\n\n\nOverall, I'm not convinced that the proposed approach would lead to any substantial improvement for MMD-GAN in practice, and the experiments are not really convincing as they are now. However, I find the theoretical results interesting and might be used to better analyse the dynamics of GAN's. But as the paper is currently framed, it is hard to put these theoretical results in perspective.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lbCgh6KB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper addresses the problem of kernel learning in MMD GAN using particle stochastic gradient descent to solve an approximation of the intractable distributional optimization problem for random features. The paper provides theoretical guarantees for the consistency of approximations, although proofs are deferred to Appendix.\nIt seems to be a good result theoretically thanks to the consistency guarantees for the particle SGD approximation of the optimization problem. However, its practical efficacy is not completely clear.\n1. There is no discussion on how the method fares in terms of time/space complexity and if it is scalable to higher-dimensional datasets or larger batch sizes. How many steps T for good results are needed? How much time does it take to learn the model compared to the Implicit Kernel Learning or original MMD GAN?\n2. For a more detailed analysis of performance, it would be helpful to see the benefits of the kernel learned with the proposed method on synthetic data and its performance on supervised learning tasks compared with other kernel learning methods on supervised tasks.\n\nSome minor remarks:\n1. Scaling parameter alpha has become parameter beta on page ix.\n2. Some citations and equation references should be fixed.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was assessed by three reviewers who scored it as 6/1/6. The main criticism included somewhat weak experiments due to the manual tuning of bandwidth, the use of old (and perhaps mostly solved/not challenging) datasets such as Mnist and Cifar10, lack of ablation studies. The other issue voiced in the review is that the proposed method is very close to a MMD-GAN with a kernel plus random features. Taking into account all positives and negatives, we regret to conclude that this submission falls short of the quality required by ICLR2020, thus it cannot be accepted at this time.


Decision: Reject