Implicit Kernel Learning
Chun-Liang Li Wei-Cheng Chang Youssef Mroueh Yiming Yang Barnabás Póczos

[

Implicit Kernel Learning

 Chun-Liang Li Wei-Cheng Chang Youssef Mroueh Yiming Yang Barnabás Póczos 

  
 Carnegie Mellon University and IBM Research]



Kernels are powerful and versatile tools in machine learning and statistics. Although the notion of universal
kernels and characteristic kernels has been studied, kernel selection still greatly influences the empirical
performance.
While learning the kernel in a data driven way has been investigated,
in this paper we explore learning the spectral distribution of kernel via
implicit generative models parametrized by deep neural networks.
We called our method Implicit Kernel Learning (IKL).
The proposed framework is simple to train and inference is performed via sampling random Fourier features.
We investigate two applications of the proposed IKL as examples, including generative adversarial networks with
MMD (MMD GAN) and standard supervised learning.
Empirically, MMD GAN with IKL outperforms vanilla predefined kernels on both image and text generation
benchmarks; using IKL with Random Kitchen Sinks also leads to substantial improvement over existing state-of-the-art
kernel learning algorithms on popular supervised learning benchmarks. 
Theory and conditions for using IKL in both applications are also studied
as well as connections to previous state-of-the-art methods.




§ INTRODUCTION


Kernel methods are among the essential foundations in machine learning and have been extensively studied in the past decades.
In supervised learning, kernel methods allow us to learn non-linear hypothesis. 
They also play a crucial role in statistics. 
Kernel maximum mean discrepancy (MMD) <cit.> is a powerful two-sample test, which is based 
on a statistics computed via kernel functions.
Even though there is a surge of deep learning in the past years, several successes have been shown by
kernel methods and deep feature extraction.
<cit.> demonstrate state-of-the-art performance by incorporating deep
learning, kernel and Gaussian process. <cit.> use MMD to train deep
generative models for complex datasets. 

In practice, however, kernel selection is always an important step. Instead of choosing by a heuristic, 
several works have studied kernel learning. 
Multiple kernel learning (MKL) <cit.> is one of the pioneering frameworks
to combine predefined kernels. 
One recent kernel learning development is to learn kernels via learning spectral distributions
(Fourier transform of the kernel). <cit.> model spectral distributions via a mixture of Gaussians,
which can also be treated as an extension of linear combination of kernels <cit.>.  
<cit.> extend it to Bayesian non-parametric models. 
In addition to model spectral distribution with explicit density models aforementioned, many works
optimize the sampled random features or its weights (<cit.>).
The other orthogonal approach to modeling spectral distributions is learning feature maps for standard kernels (Gaussian).  
Feature maps learned by deep learning lead to state-of-the-art
performance on different tasks <cit.>. 

In addition to learning effective features, implicit generative models via deep learning also lead to 
promising performance in learning distributions of complex data <cit.>. 
Inspired by its recent success,
we propose to model kernel spectral distributions with implicit generative models in a
data-driven fashion, which we call Implicit Kernel Learning (IKL). 
IKL provides a new route to modeling spectral distributions by learning sampling processes of the spectral densities, which is
under explored by previous works aforementioned. 


In this paper, we start from studying the generic problem formulation of IKL, and propose an easily implemented, trained and evaluated
neural network parameterization which satisfies Bochner's theorem (Section <ref>). 
We then demonstrate two example applications of the proposed IKL. 
Firstly, 
we explore MMD GAN <cit.> with IKL on learning to generate images and text (Section <ref>).
Secondly, we consider a standard two-staged supervised learning task with Random Kitchen Sinks <cit.>
(Section <ref>).
The conditions required for training IKL and its theoretical guarantees in both tasks are also studied.
In both tasks, we show that IKL leads to competitive or better performance than heuristic kernel
selections and existing approaches
modeling kernel spectral densities. It demonstrates the potentials of learning more powerful kernels via deep
generative models. 
Finally, we discuss the connection with existing works in Section <ref>.



§ KERNEL LEARNING



Kernels have been used in several applications with success,
including supervised learning, unsupervised learning, and hypothesis testing. They have also been combined with deep
learning in different applications <cit.>. 
Given data x ∈^d, kernel methods compute the inner product of the feature
transformation ϕ(x) in a high-dimensional Hilbert space H 
via a kernel function k : ×→, which is defined as
k(x,x') = ⟨ϕ(x), ϕ(x') ⟩_H,
where ϕ(x) is usually high or even infinitely dimensional. If k is shift invariant (k(x,y)=k(x-y)), we can represent k as an expectation with respect to a spectral distribution _k(ω).


  
Bochner's theorem <cit.>
	A continuous, real valued, symmetric and shift-invariant function
	k on ^d is a positive definite kernel if and only if 
	there is a positive finite measure _k(ω) such that
	
    k(x-x') = ∫_^d e^iω^⊤ (x-x')d_k(ω) = _ω∼_k[ e^iω^⊤
    		(x-x')].




 §.§ Implicit Kernel Learning

We restrict ourselves to learning shift invariant kernels. According to that, learning kernels is equivalent to learning a
spectral distribution by optimizing

    [              max_k∈∑_i=1_x∼_i,x'∼_i[ F_i(x, x')k(x,x') ]  =; max_k∈∑_i=1_x∼_i,x'∼_i[ F_i( x, x')_ω∼_k[ e^iω^⊤ (x-x')] ], ]

where F is a task-specific objective function and  is a set of kernels. (<ref>) covers many popular objectives, such as kernel
alignment <cit.> and
MMD distance <cit.>. 
Existing works <cit.> learn the spectral density _k(ω) 
with explicit forms via parametric or non-parametric models. 
When we learn kernels via (<ref>), it may not be necessary to model the density of _k(ω), 
as long as we are able to estimate kernel evaluations k(x-x') = _ω[e^iω^⊤(x-x')] via 
sampling from _k(ω) <cit.>.
Alternatively, implicit probabilistic (generative) models define a stochastic procedure that can generate (sample) data from
_k(ω) without modeling _k(ω). Recently, the neural implicit generative models <cit.>
regained attentions with promising results <cit.> and 
simple sampling procedures.  We first sample ν from a base distribution (ν) which is known (Gaussian distribution), then use a
deterministic function h_ψ parametrized by ψ, to transform ν into ω=h_ψ(ν), 
where ω follows the complex target distribution _k(ω). 
Inspired by the success of deep implicit generative models <cit.>, 
we propose an Implicit Kernel Learning (IKL) method by modeling
_k(ω) via an implicit generative model h_ψ(ν), where ν∼(ν), which results in

    k_ψ(x, x') =_ν[e^ih_ψ(ν)^⊤ (x-x')]


and reducing (<ref>) to solve

    [ max_ψ∑_i=1_x∼_i,x'∼_i[F_i(x,x') _ν( e^ih_ψ(ν)^⊤(x-x'))].;                                                          ]

The gradient of  (<ref>) can be represented as 

    ∑_i=1_x∼_i,x'∼_i_ν[ ∇_ψ F_i(x,x') e^ih_ψ(ν)^⊤ (x-x')].

Thus,  (<ref>) can be optimized via sampling x, x' from data and ν from the base distribution to estimate gradient as shown above (SGD) in every iteration. 
Next, we discuss the parametrization of h_ψ to satisfy Bochner's Theorem,
and describe how to evaluate IKL kernel in practice.



  
Symmetric _k(ω)
To result in real valued kernels, the spectral density has to be symmetric, where _k(ω)=_k(-ω). Thus,
we parametrize h_ψ(ν) = (ν)∘h̃_ψ((ν)), where ∘ is
the Hadamard product and h̃_ψ can be any unconstrained function if the base distribution (ν) is symmetric ((ν)=(-ν)), such as standard normal distributions.



  
Kernel Evaluation Although there is usually no closed form for the kernel evaluation k_ψ(x, x') 
in (<ref>)
with fairly complicated h_ψ, we can evaluate (approximate) k_ψ(x,x') via sampling 
finite number of random Fourier features k̂_ψ(x, x')=ϕ̂_h_ψ(x)^⊤ϕ̂_h_ψ(x'), where
ϕ̂_h_ψ(x)^⊤ = [ϕ(x; h_ψ(ν_1)), …, ϕ(x; h_ψ(ν_m))], and ϕ(x; ω) is
the evaluation on ω of the Fourier transformation ϕ(x) <cit.>.

Next, we demonstrate two example applications covered by (<ref>), where we can apply IKL, including kernel alignment and maximum mean
discrepancy (MMD). 





§ MMD GAN WITH IKL


Given {x_i}_i=1^n ∼_,
instead of estimating the density _, Generative
Adversarial Network (GAN) <cit.> is an implicit generative model, which learns a generative
network g_θ (generator). The generator g_θ transforms a base distribution _ over  into _θ
to approximate _, where _θ is the distribution of g_θ(z) and z∼_.
During the training, GAN alternatively estimates a distance D(__θ) between _ and _θ, and
updates g_θ to minimize D(__θ). 
Different probability metrics have been studied <cit.> for
training GANs.

Kernel maximum mean discrepancy (MMD) is a probability metric, which is commonly used in two-sample-test to
distinguish two distributions with finite samples <cit.>. Given a kernel k,  
the MMD between  and  is defined as

    M_k(, ) = _,[ k(x,x') ] -2_,[k(x,y)] + _, [ k(y,y') ].

For characteristic kernels, M_k(, )=0 iff =.
<cit.> train the generator g_θ by optimizing min_θM_k(_,
_θ) with a Gaussian kernel k. <cit.> propose MMD GAN,
which trains g_θ via min_θmax_k∈M_k(_,_θ), where  is a pre-defined
set of kernels. The intuition is to learn a kernel _k∈M_k(_,_θ), which has a
stronger signal (larger distance when _≠_θ) to train g_θ. 
Specifically, <cit.> consider a 
composition kernel k_φ 
which combines Gaussian kernel k and a neural network f_φ as k_φ = k∘ f_φ, where

    k_φ(x, x') = exp(-f_φ(x)-f_φ(x)'^2).

The MMD GAN objective then becomes 
	min_θmax_φ M_φ(_, _θ).



 §.§ Training MMD GAN with IKL

Although the composition kernel with a learned
feature embedding f_φ is powerful, choosing a good base kernel k is still crucial in
practice <cit.>. 
Different base kernels for MMD GAN, such as rational quadratic kernel <cit.> and
distance kernel <cit.>, have been studied.
Instead of choosing it by hands, we propose to learn the base kernel by IKL, which 
extend (<ref>) to be  k_ψ,φ=k_ψ∘ f_φ with the form

    k_ψ,φ(x, x') = _ν[ e^ih_ψ(ν)^⊤(f_φ(x)-f_φ(x'))  ].

We then extend the MMD GAN objective to be 

    min_θmax_ψ,φ M_ψ,φ(_, _θ),

where M_ψ,φ is the MMD distance (<ref>) with the IKL kernel (<ref>).
Clearly, for a given φ, the maximization over ψ in (<ref>) can
be represented as (<ref>) by letting F_1(x,x')=1, F_2(x,y)=-2 and
F_3(y,y')=1.
In what follows, we will use  for convenience k_ψ,φ, k_ψ and k_φ to denote kernels defined in (<ref>),
(<ref>) and  (<ref>) respectively.




 §.§ Property of MMD GAN with IKL


As proven by <cit.>, some probability distances adopted by existing works (<cit.>) 
are not weak (_n then D(_n) → 0), which cannot provide better
signal to train g_θ. Also, they usually 
suffer from discontinuity, hence it cannot be trained via gradient descent at certain points. 
We prove that max_ψ,φ M_ψ,φ(_, _θ)  is a continuous and
differentiable objective in θ and weak under mild assumptions as used in <cit.>.
 
	 
	g_θ(z) is  locally Lipschitz and differentiable in θ; f_φ(x) is Lipschitz in x and
	φ∈Φ is compact. 
	f_φ∘ g_θ(z) is differentiable in θ and 
    there are local Lipschitz constants, which is independent of φ, such that _z ∼_z[L(θ, z)]
	<+∞. The above assumptions are adopted by <cit.>.
	Lastly, assume given any ψ∈Ψ, where Ψ is compact, k_ψ(x,x')=_ν[ e^ih_ψ(ν)^⊤(x-x')] and |k_ψ(x,x')|<∞ is differentiable and Lipschitz in (x,x') which has an 
	 upper bound L_k for Lipschitz constant of (x,x') given different ψ.


 
Assume function g_θ and kernel k_ψ,φ satisfy Assumption <ref>, 
max_ψ,φ M_ψ,φ is weak, that is, max_ψ,φ M_ψ,φ(_,
_n) → 0 ⟺_n _.
Also, max_ψ,φ M_ψ,φ(_, _θ) is continuous everywhere 
and differentiable almost everywhere in θ.



Assume  is bounded. Let x,x' ∈,
k_ψ(x,x')=_ν[ e^ih_ψ(ν)^⊤(x-x')] is Lipschitz in (x,x') if
_ν[h_ψ(ν)^2] < ∞, which is variance since _ν[h_ψ(ν)]=0.



We penalize λ_h(_ν[h_ψ(ν)^2] -u )^2 as an approximation of Lemma <ref> in practice to ensure that assumptions in
Theorem <ref> are satisfied. 
The algorithm with IKL and gradient penalty <cit.> is shown in Algorithm <ref>.










 §.§ Empirical Study


We consider image and text generation tasks for quantitative evaluation.
For image generation, we evaluate the inception score <cit.> and FID score <cit.> on
CIFAR-10 <cit.>. 
We use DCGAN <cit.> and expands the output of f_φ to be 16-dimensional
as <cit.>.
For text generation, we consider a length-32 character-level generation task on Google Billion Words dataset. 
The evaluation is based on Jensen-Shannon divergence on empirical
4-gram probabilities (JS-4) of the generated sequence and the validation data as used by <cit.>.
The model architecture follows <cit.> in using ResNet with 1D convolutions.
We train every algorithm 10,000 iterations for comparison. 

For MMD GAN with fixed base kernels, we consider the mixture of Gaussian kernels 
k(x,x')=∑_qexp(-x-x'^2/2σ_q^2) <cit.> and the mixture of RQ kernels
k(x,x')=∑_q(1+x-x'^2/2α_q)^-α_q. 
We tuned hyperparameters σ_q and α_q for each kernel as reported in Appendix <ref>.

Lastly, for learning base kernels, we compare IKL with SM kernel <cit.> 
f_φ, which learns mixture of Gaussians to model kernel spectral density.
It can also be treated as the explicit generative model counter part of the proposed IKL.

In both tasks, (ν), the base distribution of IKL, is a standard normal distribution and h_ψ is a 3-layer MLP with 32 hidden units for
each layer. Similar to the aforementioned mixture kernels, we consider the mixture of IKL kernel with the variance
constraints [h_ψ(ν)^2] = 1/σ_q, where σ_q is the bandwidths for the mixture of Gaussian kernels. 
Note that if h_ψ is an identity map, we recover the mixture of Gaussian kernels.
We fix λ_h to be 10 and resample m=1024 random features for IKL in every iteration.
For other settings, we follow <cit.> and the hyperparameters can be found in Appendix <ref>.



  §.§.§ Results and Discussion


We compare MMD GAN with the proposed IKL and different fixed kernels.
We repeat the experiments 10 times and report the average result
with standard error in Table <ref>. 
Note that for inception score the larger the better; while JS-4 the smaller the better. 
We also report WGAN-GP results as a reference. 
Since FID score results <cit.> is consistent with inception score and does not change our discussion,
we put it in Appendix <ref> due to space limit. 
Sampled images on larger datasets are shown in Figure <ref>. 







  
Pre-defined Kernels
<cit.> show RQ kernels outperform Gaussian and energy distance kernels on image generation. 
Our empirical results agree with such finding: RQ kernels achieve 6.785 inception score while for Gaussian kernel it is
6.726, as shown in the left column of Table <ref>. In text generation, nonetheless, RQ kernels only
achieve 0.463 JS-4 score[For RQ kernels, we searched 10 possible hyperparameter settings and reported the
best one in Appendix, to ensure the unsatisfactory performance is not caused by the improper parameters.]
and are not on par with 0.381 acquired by Gaussian kernels, even though it is still slightly worse than WGAN-GP.
These results imply kernel selection is task-specific. On the other hand, the proposed IKL learns  
kernels in a data-driven way, which results in the best
performance in both tasks. In CIFAR-10, although Gaussian kernel is worse than RQ, IKL is still able to transforms
(ν), which is Gaussian, into a powerful kernel, and outperforms RQ on inception scores (6.876 v.s. 6.785).
For text generation, from Table <ref> and
Figure <ref>, we observe that IKL can further boost Gaussian into better kernels with substantial
improvement.
Also, we note that the difference between IKL and pre-defined kernels in Table <ref> is significant
based on the t-test at 95% confidence level.





  
Learned Kernels
The SM kernel <cit.>, which learns the spectral density via mixture of Gaussians, does not
significantly outperforms Gaussian kernel as shown in Table <ref>, since  <cit.>
already uses equal-weighted mixture of Gaussian formulation. It suggests that proposed IKL can learn more complicated
and effective spectral distributions than simple mixture models. 



  
Study of Variance Constraints
In Lemma <ref>, we prove bounding variance [h_ψ(ν)^2] guarantees k_ψ to be Lipschitz as required in
Theorem <ref>. We investigate the importance of this constraint.
In Figure <ref>, we show the training objective (MMD), [h_ψ(ν)^2] and the JS-4 divergence for
training MMD GAN (IKL) without variance constraint, λ_h=0.
We could observe the variance keeps going up without constraints, which leads exploded MMD values. 
Also, when the exploration is getting severe, the JS-4 divergence starts increasing, which implies MMD cannot provide
meaningful signal to g_θ. The study justifies the validity of Theorem <ref> and Lemma <ref>.





  
Other Studies
One concern of the proposed IKL is the computational overhead introduced by sampling random features as well as using
more parameters to model h_ψ. 
Since we only use small network to model h_ψ, the increased computation overhead is almost negligible under GPU
parallel computation. The detailed comparison can be found in Appendix <ref>.
We also compare IKL with <cit.>, which can
be seen as a variant of IKL without h_ψ, and studt the variance constraint. Those additional discussions can be found in
Appendix <ref>.



§ RANDOM KITCHEN SINKS WITH IKL


<cit.> propose Random Kitchen Sinks (RKS) as follows.
We sample ω_i∼_k(ω) and transform x∈^d
into ϕ̂(x)=[ϕ(x; ω_1),…,ϕ(x; ω_M)], where sup_x,ω |ϕ(x; ω)| < 1. 
We then
learn a classifier on the transformed features ϕ̂(x;ω). 
Kernel methods with random features <cit.> is an example of RKS,
where _k(ω) is the spectral distribution of the kernel and
ϕ(x;ω) = [ cos(ω^⊤ x), sin(ω^⊤ x) ].
We  usually learn a model  by solving 

    min_λ/2^2 + 1/n∑_i=1^n ℓ( ^⊤ϕ̂(x_i) ).

If ℓ is a convex loss function, the objective (<ref>) can be solved efficiently to global optimum.

Spectral distributions _k are usually set as a parameterized form, such as Gaussian distributions, but the 
selection of _k is important in practice. 
If we consider RKS as kernel methods with random features, then selecting  is equivalent to
the well-known kernel selection (learning) problem for supervised learning <cit.>. 



  
Two-Stage Approach
We follows <cit.> to consider kernel learning for RKS with a two-stage approach. 
In stage 1, we consider kernel
alignment <cit.> of the form,
_k∈_(x,y), (x',y')∑_i≠ j yy' k(x, x').
By parameterizing k via the implicit generative model h_ψ as in Section <ref>,
we have the following problem:

    _ψ_(x,y), (x',y') yy'_ν[ 
    	e^ih_ψ(ν)^⊤(x-x') ,
    	].

which can be treated as (<ref>) with F_1(x, x')=yy'.
After solving (<ref>), we learn a sampler h_ψ where we can easily sample.
Thus, in stage 2, we thus have the advantage of solving a convex problem (<ref>) in RKS with IKL.
The algorithm is shown in Algorithm <ref>.



Note that in stage 1, we resample {ν_j}_j=1^m in every iteration to train an implicit generative model h_ψ. 
The advantage of Algorithm <ref> is the random features used in kernel learning and RKS 
can be different, which allows us to use less random features in kernel learning (stage 1), and
sample more features for RKS (stage 2). 

One can also jointly train both feature mapping ω and the
model parameters , such as neural networks.
We remark that our intent is not to show state-of-the-art results on supervised learning, 
on which deep neural networks dominate <cit.>.
We use RKS as a protocol to study kernel learning and the proposed IKL, which still has competitive performance with
neural networks on some tasks <cit.>. 
Also, the simple procedure of RKL with IKL allows us to provide some theoretical guarantees of the performance, which is
sill challenging of deep learning models. 



  
Comparison with Existing Works
<cit.> learn non-uniform weights
for M random features via kernel alignment in stage 1 then using these optimized features in RKS in the stage 2. 
Note that the random features used in stage 1 has to be the same as the ones in stage 2.
A jointly training of feature mapping and classifier can be treated as a
2-layer neural networks <cit.>. 
Learning kernels with aforementioned works will be more costly if we want to use a
large number of random features for training classifiers. 
In contrast to implicit generative models,  <cit.> learn an explicit Bayesian nonparametric generative
model for spectral distributions, which requires specifically designed inference algorithms.
Learning kernels for (<ref>) in dual form without random features has also been proposed. 
It usually require  costly steps, such as eigendecomposition of the Gram matrix <cit.>.




 §.§ Empirical Study

We evaluate the proposed IKL on both synthetic and benchmark binary classification tasks.
For IKL, (ν) is standard Normal and h_ψ is a 3-layer MLP for all experiments.
The number of random features m to train h_ψ in Algorithm <ref> is fixed to be 64. 
Other experiment details are described in Appendix <ref>.








  
Kernel learning with a poor choice of _k(ω)
We generate {x_i}_i=1^n ∼(0, I_d) with y_i = sign(x_2 - √(d)), where d is the data
dimension. A two dimensional example is shown in Figure <ref>.
Competitive baselines include random features (RFF) <cit.> as well as OPT-KL <cit.>.
In the experiments, we fix M=256 in RKS for all algorithms. 
Since Gaussian kernels with the bandwidth σ=1 is known to be ill-suited for this task <cit.>,
we  directly use random features from it for RFF and OPT-KL. Similarly, we set (ν) to be standard normal
distribution as well.

The test error for different data dimension d={2,4,…,18,20} is shown in Figure <ref>.
Note that RFF is competitive with OPT-KL and IKL when d is small (d ≤ 6),
while its performance degrades rapidly as d increases, which is consistent with the observation
in <cit.>.
More discussion of the reason of failure can be referred to <cit.>.
On the other hand, although using standard normal as the spectral distribution is ill-suited for this task,  
both OPT-KL and IKL can adapt with data and learn to transform it into effective kernels and result in slower degradation with d. 

Note that OPT-KL learns the sparse weights on the sampled random features (M=256).
However, the sampled random features can fail to contain informative ones, especially in high dimension <cit.>.
Thus, when using limited amount of random features, OPT-IKL may result in worse performance than IKL in the high
dimensional regime in Figure <ref>.  





  
Performance on benchmark datasets
Next, we evaluate our IKL framework on standard benchmark binary classification tasks.
Challenging label pairs are chosen from MNIST <cit.>
and CIFAR-10 <cit.> datasets;
each task consists of 10000 training and 2000 test examples.
For all datasets, raw pixels are used as the feature representation.
We set the bandwidth of RBF kernel by the median heuristic.
We also compare with <cit.>, the spectral mixture (SM) kernel, which uses Gaussian mixture
to learn spectral density and can be seen as the explicit generative model counterpart of IKL.
Also, SM kernel is a MKL variant with linear combination <cit.>.
In addition, we consider 
the joint training of random features and model parameters, which can be treated as two-layer neural network (NN) and
serve as the lower bound of error for comparing different kernel learning algorithms.  

The test error versus different M={2^6, 2^7, …, 2^13} in the second stage are shown in Figure <ref>.
First, in light of computation efficiency, SM and the proposed IKL only sample
m=64 random features in each iteration in the first stage, and draws different
number of basis M from the learned h_ψ(ν) for the second stage.
OPT-KL, on the contrary, the random features used in training and testing should be the same. 
Therefore, OPT-IKL needs to deal with M random features in the training. It brings computation concern when M is
large. 
In addition, IKL demonstrates improvement over 
the representative kernel learning method OPT-KL, 
especially significant on the challenging datasets such as CIFAR-10.
In some cases, IKL almost reaches the performance of NN, such as MNIST,
while OPT-KL degrades to RFF except for small number of basis (M=2^6).
This illustrates the effectiveness of learning kernel spectral distribution
via the implicit generative model h_ψ. 
Also, IKL outperforms SM, which is consistent with the finding in Section <ref> that IKL
can learn more complicated spectral distributions than simple mixture models (SM).








 §.§ Consistency and Generalization

The simple two-stages approach, IKL with RKS, allows us to provide the consistency and generalization
guarantees. For consistency, it guarantees the solution of finite sample approximations of  (<ref>)
approach to the optimum of  (<ref>) (population optimum), 
when we increase number of training data and number of random features. We firstly define necessary symbols and state the theorem. 

Let s(x_i, x_j)=y_iy_j be a label similarity function, where |y_i|≤ 1. We use s_ij to denote s(x_i, x_j)
interchangeably. Given a kernel k, we define the true and empirical alignment functions as,

    [                           T(k)                              =           [ s(x, x')k(x, x') ];                          T̂(k)                              = 1/n(n-1)∑_i≠ js_ijk(x_i, x_j).;                                ]


In the following, we abuse the notation k_ψ to be k_h for ease of illustration.
Recall the definitions of k_h(x,x')=⟨ϕ_h(x), ϕ_h(x')  ⟩ and
k̂_h(x, x')=ϕ̂_h(x)^⊤ϕ̂_h(x').
We define two hypothesis sets

    [ _  = { f(x) = ⟨ w, ϕ_h(x) ⟩_H | h∈, ⟨ w, w⟩≤ 1 }; _^m  =  { f(x) = w^⊤ϕ̂_h(x)  | h∈, w≤ 1, w∈^m }. ]

(Rademacher's Complexity)
Given a hypothesis set , where f: ×→ if f∈, and a fixed sample X = {x_1, …, x_n}, 
the empirical Rademacher's complexity of  is defined as 

    ℜ_X^n() = 1/n_σ[ sup_f∈∑_i=1^n σ_i f(x_i) ],

where σ are n i.i.d. Rademacher random variables.


We then have the following theorems showing that the consistency guarantee 
depends on the complexity of the function class induced by IKL as well as the number of random features.
The proof can be found in Appendix <ref>.
 (Consistency)
Let ĥ = max_h∈T̂(k̂_h), with i.i.d, samples {ν_i}_i=1^m drawn from
(ν). With probability at least 1-3δ, we have  |T(k̂_ĥ) - sup_h∈ T(k_h) | ≤

    [ 2_X[ ℜ_X^n-1(_) + ℜ_X^n-1(_^m) ]+
    √(8log1/δ/n) + √(2log4/δ/m). ]




Applying <cit.>,  
We also have a generalization bound, which depends number of training data n,
number of random features m and the Rademacher complexity of IKL kernel, as shown in Appendix <ref>.
The Rademacher complexity ℜ_X^n(_), for example, can be 1/√(n) or even
1/n for kernels with different bounding conditions <cit.>. 
We would expect worse rates for more powerful kernels.
It suggests the trade-off between consistency/generalization and using powerful kernels parametrized by neural networks.




§ DISCUSSION



We propose a generic kernel learning algorithm, IKL, which
learns sampling processes of kernel spectral distributions by transforming samples from a base distribution (ν)
into ones for the other kernel (spectral density). 
We compare IKL with other algorithms for learning MMD GAN and supervised learning with Random Kitchen Sinks (RKS). 
For these two tasks, the conditions and guarantees of IKL for are studied.
Empirical studies show IKL is better than or competitive with the state-of-the-art kernel learning algorithms.
It proves IKL can learn to transform (ν) into effective kernels even if (ν) is less 
less favorable to the task.

We note that the preliminary idea of IKL is mentioned in <cit.>, but they ended up with a
algorithm that directly optimizes sampled random features (RF), which has many follow-up works ( <cit.>). The major difference is, by learning the transformation function h_ψ, the RF used in
training and evaluation can be different. This flexibility allows a simple training algorithm (SGD) and does not require
to keep learned features. In our studies on GAN and RKS, we show using a simple MLP can already achieve better
or competitive
performance with those works, which suggest IKL can be a new direction for kernel learning and worth more studies.

We highlight that IKL is not conflict with existing works but can be combined with them. 
In Section <ref>, we show combining IKL with kernel learning via embedding <cit.> and mixture
of spectral distributions <cit.>. 
Therefore, 
in addition to the examples shown in Section <ref> and Section <ref>,
IKL is directly applicable to many existing works with kernel learning via embedding ( <cit.>). 
A possible extension is combining with 
Bayesian inference <cit.> under the framework similar to <cit.>.
The learned sampler from IKL can possibly provide an easier way to
do Bayesian inference via sampling. 





apalike






§ PROOF OF THEOREM <REF>


We first show _n then max_ψ, φM_ψ, φ(, _n) → 0.
The results are based on <cit.>, which leverages Corollary 11.3.4 of <cit.>. 
Follows the sketch of <cit.>, the only thing we remain to show is proving k_ψ(f_φ(x), ·)-k_ψ(f_φ(y),
·)__K is Lipschitz. By definition, we know that
k_ψ(f_φ(x), ·)-k_ψ(f_φ(y),·)__K = 2(1- k_ψ(f_φ(x), f_φ(y)) ).
Also, since k_ψ(0)=1 and k_ψ(0) - k_ψ(x,x') ≤ L_k 0-(x-x') (Lipschtiz assumption of k_ψ),
we have 

    k_ψ(f_φ(x), ·)-k_ψ(f_φ(y),·)__K≤ 2L_kf_φ(x)- f_φ(y)≤ 
    	2L_k L x-y,

where the last inequality is since f_φ is also a Lipschitz function with Lipschitz constant L.

The other direction, max_ψ, φM_ψ, φ(, _n) → 0 then _n, 
is relatively simple. Without loss of generality, we assume there exists ψ' and ϕ' such  that h_ψ and f_ϕ are identity
functions (up to scaling), which recover the Gaussian kernel k. Therefore, 
max_ψ, φM_ψ, φ(, _n) → 0 implies M_ψ', φ'(,_n) →
0, which completes the proof because MMD with any Gaussian kernel is weak <cit.>.




 §.§ Continuity

(<cit.>)
Define τ(x) = max{f(x, u) | u∈ U}. If f is locally Lipschitz in x, U is compact and ▽ f(x, u^*(x))
exists, where u^*(x) =  max_u f(x, u), then τ(x) is differentiable almost everywhere. 



We are going to show 

    max_ψ,φ M_ψ,φ(_, _θ) = _x,x'[k_ψ,φ(x, x')] -2_x,z[k_ψ,φ(x,g_θ(z))]  + _z,z'[ k_ψ,φ(g_θ(z'), g_θ(z))  ]

is differentiable with respect to φ almost everywhere by using the auxiliary Lemma <ref>. 
We fist show _z,z'[ k_ψ,φ(g_θ(z'), g_θ(z))  ] in (<ref>) is locally Lipschitz in
θ. By definition, k_ψ,φ(x, x') = k_ψ(f_φ(x )-f_φ( x' ) ), therefore,

    _x,x'[ k_ψ,φ( g_θ(z), g_θ(z') ) - k_ψ,φ( g_θ'(z), g_θ'(z')  ) ] 
    
    	=    _z,z'[ k_ψ( f_φ( g_θ(z) ) - f_φ( g_θ(z') )) ] - 
    	  _z,z'[ k_ψ( f_φ( g_θ'(z) ) - f_φ( g_θ'(z') )) ] 
    ≤   _z,z'[ L_k ‖ f_φ( g_θ(z) ) - f_φ( g_θ(z') ) - f_φ( g_θ'(z) ) + f_φ( g_θ'(z') ) ‖] 
    ≤   _z,z'[ L_k L(θ, z) θ-θ'   + L_k L(θ, z') θ-θ'  ] 
    
       =     2L_k_z[  L(θ, z) ]θ-θ'  .

The first inequality is followed by the assumption that k is locally Lipschitz in (x,x'), with a upper bound
L_k for Lipschitz constants.
By Assumption <ref>, _z[  L(θ, z) ]<∞,
we prove _z,z'[ k_ψ( f_φ( g_θ(z) ) - f_φ( g_θ(z') ) ) ] is locally Lipschitz. 
The similar argument is applicable to other terms in (<ref>); therefore, (<ref>) is locally
Lipschitz in θ.  

Last, with the compactness assumption on Φ and Ψ, and differentiable assumption on
M_ψ,φ(_, _θ), applying Lemma <ref> proves Theorem <ref>.




§ PROOF OF LEMMA <REF>

Without loss of the generality, we can rewrite the kernel function as
k_ψ(t) = _ν[ cos( h_ψ(ν)^⊤ t ) ],
where t is bounded. We then have

    [                        ∇_t k_ψ(t)                                 = ‖_ν[ sin( h_ψ(ν)^⊤ t ) h_ψ(ν) ] ‖;                                                                   ≤    _ν[ |sin(h_ψ(ν)^⊤ t) |×h_ψ(ν)];                                                                   ≤                   _ν[ th_ψ(ν)^2 ] ]

The last inequality follows by |sin(x)| < |x|. Since t is bounded, if _ν[h_ψ(ν)^2]<∞, there exist a
constant L such that ∇_t k_ψ(t) < L, ∀ t. 

By mean value theorem, for any t and t', there exists s=α t + (1-α)t', where α∈ [0,1], such that

    k_ψ(t) - k_ψ(t') = ∇_s k_ψ( s )^⊤ (t-t').

Combining with ∇_t k_ψ(t) < L, ∀ t, we prove 

    k_ψ(t) - k_ψ(t')  ≤ Lt-t'.





§ ADDITIONAL STUDIES OF MMD GAN WITH IKL




 §.§ Additional Quantitative Results

We show the full quantitative results on MMD GANs with different kernels with mean and standard error 
in Table <ref>.
In every tasks, IKL is the best among the predefined base kernels (Gaussian, RQ) and the competitive kernel learning
algorithm (SM).
The difference in FID is less significant than inception score and JS-4, but we note that FID score is a biased evaluation metric as discussed in <cit.>.





 §.§ Computational Issues of GAN trainings with IKL




  
Model Capacity
For f_φ, the number of parameters for DCGAN is around 0.8 million for size 32× 32 images and 3 millions
for size 64× 64 images. The ResNet architecture used in <cit.> has around 10 millions
parameters.
In contrast, in all experiments, we use simple three layer MLP as h_ψ for IKL, where the input and output dimensions are 16, and hidden
layer size is 32. The total parameters are just around 2,000. Compared with f_ϕ, the additional number of
parameters used for h_ψ is almost negligible.

r.5
      
    < g r a p h i c s >




  
Computational Time
The potential concern of IKL is sampling random features for each examples. In our experiments, we use
m=1024 random features for each iteration. 
We measure the time per iteration of updating critic iterations (f for WGAN-GP and MMD GAN with Gaussian kernel; f
and h for IKL) with different batch sizes under Titan X.
The difference between WGAN-GP, MMD GAN and IKL
are not significant.  The reason is computing MMD and random feature is highly parallelizable, and other computation, such as
evaluating f_ϕ and its gradient penalty, dominates the cost because f_ϕ has much more parameters as
aforementioned. Therefore, we believe the proposed IKL is still cost effective in practice.



 §.§ Detailed Discussion of Variance Constraints

In Section <ref>, we propose to constrain variance via  λ_h(_ν[h_ψ(ν)^2] -u
)^2. There are other alternatives, such as constraining L^2 penalty or using Langrange. In practice, we do not
observe significant difference. 

Although we show the necessity of the variance constraint in language generation in Figure <ref>,
we remark that the proposed constraint is a sufficient condition. 
For CIFAR-10, without the constraint, we observe that the variance is still bouncing between 1 and 2
without explosion as Figure <ref>.
Therefore, the training leads to a satisfactory result with 6.731 ± 0.034 inception score, but it is slightly 
worse than IKL in Table <ref>.
The necessary or weaker sufficient conditions are worth further studying as a future work.



 §.§ IKL with and without Neural Networks on GAN training


Instead of learning a transform function h_ψ for the spectral distribution
as we proposed in Section <ref> (IKL-NN), 
the other realization of IKL is to keep a pool of finite number learned random features  Ω = {ω̂_̂î}_i=1^m, and
approximate the kernel evaluation by k̂_Ω(x, x')= ϕ̂_Ω(x)^⊤ϕ̂_Ω(x'),
where ϕ̂_Ω(x)^⊤ = [ϕ(x; ω̂_1), …, ϕ(x; ω̂_m)].
During the learning, it directly optimize ω̂_̂î.
Many existing works study this idea for supervised learning, such as <cit.>.
We call the latter realization as IKL-RFF. Next, we discuss
and compare the difference between IKL-NN and IKL-RFF.

The crucial difference between IKL-NN and IKL-RFF is, IKL-NN can sample arbitrary number of random features
by first sampling ν∼(ν) and transforming it via h_ψ(ν), while IKL-RFF is restricted by the pool size
m. If the application needs more random features, IKL-RFF will be memory inefficient. 
Specifically, we compare IKL-NN and IKL-RFF with different number of random features in Figure <ref>.
With the same number of parameters (i.e., |h_ψ| = m × dim(ν))[|h_ψ| denotes
number of parameters in h_ψ, m is number of random features and dim(ν) is the dimension of the ν.]
, IKL-NN outperforms IKL-RFF of m=128 on Inception scores (6.876 versus 6.801).
For IKL-RFF to achieve the same or better Inception scores of IKL-NN, the number of random features
m needs increasing to 4096, which is less memory efficient than the IKL-NN realization.
In particular, h_ψ of IKL-NN is a three-layers MLP with 2048 number of parameters
(16×32 + 32×32 + 32×16),
while IKL-RFF has 2048, 65536 number of parameters, for m=128,4096, respectively.




On the other hand, using large m for IKL-RFF not only increases the number of parameters, but might also enhance the
optimization difficulty. <cit.> discuss the difficulty of optimizing RFF directly on different tasks. 
Here we compare IKL-NN and IKL-RFF on challenging Google Billion Word dataset. We train IKL-RFF
with the same setting as Section <ref> and Appendix <ref>, where we set the pool size m
to be 1024 and the updating schedule between critic and generator to be 10:1, but we tune the Adam optimization
parameter for IKL-RFF for fair comparison. As discussed above, please note that the number of parameters for h_ψ is
2048 while IKL-RFF uses 16384 when m=1024. The results are shown in Table <ref>. Even IKL-RFF is using more
parameters, the performance 0.383 is not competitive as IKL-NN, which achieves 0.372.

In Algorithm <ref>, we update f_φ and h in each iteration with n_c times, where we use n_c=10
here. We keep the number of updating f_φ to be 10, but increase the number of update for
{ω̂_̂î}_i=1^1024 to be 12, 14, 18 in each iteration. The result is shown in Table <ref> with
symbols +2, +4 and +8 respectively. Clearly, we see IKL-RFF need more number of updates to achieve competitive
performance with IKL-NN. The results might implies IKL-RFF is a more difficult optimization problem with more parameters
than IKL-NN. It also confirms the effectiveness of learning implicit generative models with deep neural
networks <cit.>, but the underlying theory is still an open research question. 
A better optimization algorithm <cit.> may improve the performance gap between IKL-NN and IKL-RFF, which worth
more study as future work.





§ PROOF OF THEOREM <REF>


We first prove two Lemmas. 

 (Consistency with respect to data)

With probability at least 1-δ, we have

    sup_h∈|T̂(k_h)-T(k_h)| ≤ 2_X[ℜ_X^n-1(_)] + √(2/nlog1/δ)



Define 

    ρ(x_1, …, x_n) = sup_h∈|T̂(k_h)-T(k_h)|,
 
since |k_h(x, x')|≤ 1, it is clearly 

    [   sup_x_1,…,x_i,x_i',…, x_n      |ρ(x_1, …,x_i,… x_n) -;                             ρ(x_1, …,x_i',… x_n)| ≤2/n. ]


Applying McDiarmids Inequality, we get 

    ( ρ(x_1, …, x_n)- [ρ(x_1, …, x_n)] ≥ϵ) ≤exp( -nϵ^2/2).


By Lemma <ref>, we can bound 

    [ρ(x_1, …, x_n)] ≤ 2_X[ℜ_X^n-1(_)]

and finish the proof.




Given X={x_1,…,x_n}, define  

    ρ(x_1, …, x_n) = sup_h∈|T̂(k_h)-T(k_h)|,
 
we have 

    [ ρ(x_1, …, x_n) ] ≤ 2_X[ ℜ_X^n-1(_) ],



The proof is closely followed by <cit.>.
Given h, we first define t_h(x,x') = s(x, x')k_h(x, x') as a new kernel function to simplify the notations. We are
then able to write 

    [                                                                                                                  [ ρ(x_1, …, x_n) ];                                                                 =     _X[ sup_h_∈| [ t_h(z,z') ] - 1/n(n-1)∑_i≠ j t_h(x_i, x_j) | ];                                                                 ≤ _X, Z[ sup_h_∈| 1/n(n-1)∑_i≠ j(t_h(z_i, z_j) - t_h(x_i, x_j)) | ] ]

by using Jensen's inequality. Utilizing the conditional expectation and introducing the Rademacher random variables
{σ_i}_i=1^n-1, we can write the above bound to be 

    1/n∑_i _X_-i, Z_-i_x_i, z_i[ sup_h_∈| ∑_i≠
    	j t_h(z_i, z_j) - t_h(x_i, x_j)/n-1| ] 
    
    	= _X,Z_X',Z',σ[ sup_h∈| 1/n-1∑_i=1^n-1σ_i(t_h(z',z_n)-t_h(x',x_n) ) | ]

The equality follows by X-X' and -(X-X') has the same distributions if X and X' are independent samples
from the same distribution.
Last, we can bound it by 

    [                                                  ≤ _X_σ, X'[ sup_h∈| 2/n-1∑_i=1^n-1σ_it_h(x',x_i) | ];                                                  ≤      _X_σ[ sup_f∈_k_|  2/n-1∑_i=1^n-1σ_if(x_i) | ];                                                  =                                   2_X[ ℜ_X^n-1(_)] ]

The second inequality follows by s(x,x')ϕ(x') ∈ since |s(x,x')| ≤ 1.



 (Consistency with respect to sampling random features)

With probability 1-δ, we have

    |sup_h∈T̂(k_h) - sup_h∈T̂(k̂_h) | ≤√(2log4/δ/m)




Let the optimal solutions be

    [             h^*               =   max_h∈T̂(k_h);               ĥ               = max_h∈T̂(k̂_h), ]

By definition, 

    [                                                                                                        T̂(k̂_h);                                                       = 1/n(n-1)∑_i≠ j s_ij(1/m∑_k=1^m
    	cos(h(ν_k)^⊤(x_i-x_j)));                                                       =       1/m∑_k=1^m( 1/n(n-1) s_ijcos(h(ν_k)^⊤(x_i-x_j)) ) ]

It is true that |1/n(n-1) s_ijcos(h(ν_k)^⊤(x_i-x_j)|≤ 1 since |s_ij|<1 and |cos(x)|<1. 
we then have

    [                                                                               (|sup_h∈T̂(k_h) - sup_h∈T̂(k̂_h) |>ϵ);                                                         ≤ (|T̂(k_h^*) - T̂(k̂_h^*) |>ϵ) +  (|T̂(k_ĥ) - T̂(k̂_ĥ)|>ϵ);                                                         ≤                                           4exp( -mϵ^2/2), ]

where the last inequality follows from the Hoeffding's inequality.


With Lemma <ref> and Lemma <ref>, we are ready to prove Theorem <ref>.
We can decompose 

    [                                                                                                                                                        |T(k̂_ĥ) - sup_h∈ T(k_h) |;                                                                                        ≤   |sup_h∈ T(k_h) - sup_h∈T̂(k_h)| +  
    	|sup_h∈T̂(k_h) - T̂(k̂_ĥ)| + |T̂(k̂_ĥ) - T(k̂_ĥ)|;                                                                                        ≤ sup_h∈ |T(k_h) - T̂(k_h)| +  
    	|sup_h∈T̂(k_h) - T̂(k̂_ĥ)|  + sup_h∈ |T̂(k̂_h) - T(k̂_h)| ]

We then bound the first and third terms by Lemma <ref> and the second term by Lemma <ref>.
Last, using a union bound completes the proof. 



§ GENERALIZATION OF RANDOM KITCHEN SINKS WITH IKL



 (Generalization <cit.>)
Define the true and empirical misclassification for a classifier f as
R(f)  =   (Yf(X)<0) and R̂_γ(h)  =  1/n∑_i=1^nmin{ 1,
[1-yf(x_i)/γ]_+ }.
Then 

    sup_f∈_{R(f) - R̂_γ(f) }≤2/γℜ_X^n( _ ) +
    3√(log2/δ/2n)

with probability at least 1-δ.





§ HYPERPARAMETERS

We report the hyperparameters used in the experiments.


 §.§ GAN


For Gaussian kernels, we use σ_q={1,2,4,8,16} for images and σ_q={0.5, 1, 2, 4, 8} for text;
for RQ kernels, we use α_q={0.2,0.5,1,2,5} for images and α_q = {0.04, 0.1, 0.2, 0.4, 1} for text.
We used Adam as optimizer. 
The learning rate for training both f_ϕ and g_θ is 0.0005 and 0.0001 for image and text 
experiments, respectively. The batch size B is 64. 
We set hyperparameter n_c for updating critic to be n_c=5 and n_c=10 for CIFAR10 and Google Billion Word datasets.
The learning rate of of h_ψ for Adam is 10^-6.



 §.§ Random Kitchen Sinks with IKL


For OPT-KL, we use the code provided by <cit.>[<https://github.com/amansinha/learning-kernels>].
We tune the hyperparameter ρ = {1.25, 1.5, 2, 4, 16, 64} on the validation set.
For RFF, OPT-KL, and IKL, the linear classifier is Logistic Regression
<cit.>[<https://github.com/cjlin1/liblinear>],
as to make reasonable comparison with MLP.
We use 3-fold cross validation to select the best C
on training set and present the error rate on test set. 
For CIFAR-10 and MNIST, 
we normalize data to be
zero mean and one standard deviation in each feature dimension. 
The learning rate for Adam is 10^-6.
We follow <cit.> to use early stopping when performance on validation set does not
gain. 


