--- abstract: 'We develop and analyze a projected particle Langevin optimization method to learn the distribution in the Schönberg integral representation of the radial basis functions from training samples. More specifically, we characterize a distributionally robust optimization method with respect to the Wasserstein distance to optimize the distribution in the Schönberg integral representation. To provide theoretical performance guarantees, we analyze the scaling limits of a *projected* particle online (stochastic) optimization method in the mean-field regime. In particular, we prove that in the scaling limits, the empirical measure of the Langevin particles converges to the law of a *reflected* Itô diffusion-drift process. The distinguishing feature of the derived process is that its drift component is also a function of the law of the underlying process. Using Itô lemma for semi-martingales and Grisanov's change of measure for the Wiener processes, we then derive a Mckean-Vlasov type partial differential equation (PDE) with Robin boundary conditions that describes the evolution of the empirical measure of the projected Langevin particles in the mean-field regime. In addition, we establish the existence and uniqueness of the steady-state solutions of the derived PDE in the weak sense. We apply our learning approach to train radial kernels in the kernel locally sensitive hash (LSH) functions, where the training data-set is generated via a $k$-mean clustering method on a small subset of data-base. We subsequently apply our kernel LSH with a trained kernel for image retrieval task on MNIST data-set, and demonstrate the efficacy of our kernel learning approach. We also apply our kernel learning approach in conjunction with the kernel support vector machines (SVMs) for classification of benchmark data-sets.' address: | Stanford University, 450 Serra Mall, Stanford, CA 94305\ \ author: - 'Masoud Badiei Khuzani$^{\dagger,\ddagger}$, Yinyu Ye$^{\dagger}$, Sandy Napel$^{\ddagger,\ast}$, Lei Xing$^{\ddagger,\ast}$' bibliography: - 'NIPS.bib' title: 'A Mean-Field Theory for Learning the Schönberg Measure of Radial Basis Functions' --- Introduction ============ basis functions (RBFs) are key tools in statistical machine learning to approximate multivariate functions by linear combinations of terms based on a single univariate function. Such non-parametric regression schemes are typically used to approximate multivariate functions or high-dimensional data @powell2001radial,@cheney1966introduction which are only known at a finite number of points or too difficult to evaluate otherwise, so that then evaluations of the approximating function can take place often and efficiently. The accuracy and performance of such techniques, however, relies to a large extent on a good choice of RBF kernel that captures the structure of data. Standard regression methods based on RBF kernels requires the input of a user-defined kernel—a drawback if a good representation of underlying data is unknown a priori. While statistical model selection techniques such as cross-validation or jackknife @efron1981jackknife can conceptually resolve those statistical model selection issues, they typically slow down the training process on complex data-sets as they repeatedly refit the model. It is thus imperative to devise efficient learning algorithms to facilitate such model selection problems. In this paper we put forth a novel optimization framework to learn a good radial kernel from training data. Our kernel learning approach is based on a distributionally robust optimization problem @delage2010distributionally [@gao2016distributionally] to learn a good distribution for the Schönberg integral representation of the radial basis functions from training samples @schoenberg1938metric [Thm. 1]. Since optimization with respect to the distribution of RBF kernels is intractable, we consider a Monte Carlo sample average approximation to obtain a solvable finite dimensional optimization problem with respect to the samples of the distribution. We then use a projected particle Langevin optimization method to solve the approximated finite dimensional optimization problem. We provide a theoretical guarantee for the consistency of the finite sample-average approximations. Based on a mean-field analysis, we also show the consistency of the proposed projected particle Langevin optimization method in the sense that when the number of particles tends to infinity, the empirical distribution of the Langevin particles follows the path of the gradient descent flow of the distributionally robust optimization problem on the Wasserstein manifold. Related works ------------- The proposed kernel learning approach in this paper is closely related to the previous work of the authors in @khuzani2019mean. Therein, we proposed a particle stochastic gradient descent method in conjunction with the random feature model of Rahimi and Recht @rahimi2008random [@rahimi2009weighted] to optimize the distribution of the random features in generative and discriminative machine learning models using training samples. We also showed numerically that compared to the importance sampling techniques for kernel learning (*e.g.*, @sinha2016learning), the particle SGD in conjunction with the kernel SVMs yields a lower training and test errors on benchmark data-sets. Nevertheless, we observed that the particle SGD scales rather poorly with data dimension and the number of random feature samples, rendering it inapplicable for discriminative analysis of high dimensional data-sets. In this work, we address the scalability issue by optimizating the kernel over the sub-class of the radial kernels which includes important special cases such as the Gaussian, inverse multiquadrics, and Matérn kernels. While we characterize a distributionally robust optimization framework similar to @khuzani2019mean, in this work we optimize distributions defined on the real line instead of high dimensional distributions in @khuzani2019mean. This work is also closely related to the copious literature on the kernel model selection problem, see, *e.g.*, @lanckriet2004learning [@cortes2010two; @bach2004multiple; @gonen2011multiple]. For classification problems using kernel SVMs, Cortes, *et al*. studied a kernel learning procedure from the class of mixture of base kernels. They have also studied the generalization bounds of the proposed methods. The same authors have also studied a two-stage kernel learning in @cortes2010two based on a notion of the kernel alignment. The first stage of this technique consists of learning a kernel that is a convex combination of a set of base kernels. The second stage consists of using the learned kernel with a standard kernel-based learning algorithm such as SVMs to select a prediction hypothesis. In @lanckriet2004learning, the authors have proposed a semi-definite programming for the kernel-target alignment problem. However, semi-definite programs based on the interior point method scale rather poorly to a large number of base kernels. Our proposed kernel learning framework is related to the work Sinha and Duchi @sinha2016learning for learning shift invariant kernels with random features. Therein, the authors have proposed a distributionally robust optimization for the importance sampling of random features using $f$-divergences. In @khuzani2019mean, we proposed a particle stochastic gradient descent to directly optimize the samples of the random features in the distributionally robust optimization framework, instead of optimizing the weight (importance) of the samples. However, for the high dimensional data-sets the particles are high dimensional, and the particle SGD scales poorly. In this paper, we address the scalibility issue by restricting the kernel class to the radial kernels. The mean-field description of SGD dynamics has been studied in several prior works for different information processing tasks. Wang *et al.* @wang2017scaling consider the problem of online learning for the principal component analysis (PCA), and analyze the scaling limits of different online learning algorithms based on the notion of *finite exchangeability*. In their seminal papers, Montanari and co-authors @mei2018mean [@javanmard2019analysis; @mei2019mean] consider the scaling limits of SGD for training 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. They also establish the uniqueness and existence of the solution for the PDE using the connection between Mckean-Vlasov type PDEs and the gradient flows on the Wasserstein manifolds established by Otto @otto2001geometry, and Jordan, Kinderlehrer, and Otto @jordan1998variational. Similar mean-field type results for two-layer neural networks are also studied recently in @rotskoff2018neural [@sirignano2018mean] Paper Outline ------------- The rest of this paper is organized as follows: - *Empirical Risk Minimization in Reproducing Kernel Hilbert Spaces*: In Section \[Section:Preliminaries of Kernel Methods in Classification and Regression\], we review some preliminaries regarding the empirical risk minimization in reproducing kernel Hilbert spaces. We also provide the notion of the kernel-target alignment for optimizing the kernel in support vector machines (SVMs). We then characterize a distributionally robust optimization problem for multiple kernel learning. - *Theoretical Results*: In Section \[Section:Main\_Results\], we provide the theoretical guarantees for the performance of our kernel learning algorithm. In particular, we establish the non-asymptotic consistency of the finite sample approximations. We also analyze the scaling limits of the kernel learning algorithm. - *Empirical Evaluation on Synthetic and Benchmark Data-Sets*: In Section \[Section:Performance Evaluation on Synthetic and Benchmark Data-Sets\], we evaluate the performance of our proposed kernel learning model on synthetic and benchmark data-sets. In particular, we analyze the performance of our kernel learning approach for the hypothesis testing problem. We also apply our proposed kernel learning approach to develop hash codes for image query task from large data-bases. Preliminaries and the Optimization Problem for Kernel Learning {#Section:Preliminaries of Kernel Methods in Classification and Regression} =============================================================== In this section, we review preliminaries of kernel methods in classification and regression problems. Reproducing Kernel Hilbert Spaces and Kernel Alignment Optimization ------------------------------------------------------------------- Let $\mathcal{X}$ be a metric space. A *Mercer kernel* on $\mathcal{X}$ is a continuous and symmetric function $K:\mathcal{X}\times \mathcal{X}\rightarrow {{\rm I\!R}}$ such that for any finite set of points $\{\bm{x}_{1},\cdots,\bm{x}_{N}\}\subset \mathcal{X}$, the kernel matrix $(K(\bm{x}_{i},\bm{x}_{j}))_{1\leq i,j\leq N}$ is positive semi-definite. The *reproducing kernel Hilbert space* (RKHS) $\mathcal{H}_{K}$ associated with the kernel $K$ is the completion of the linear span of the set of functions $\{K_{\bm{x}}{\stackrel{\text{def}}{=}}K(\bm{x},\cdot), \bm{x}\in \mathcal{X}\}$ with the inner product structure $\langle\cdot,\cdot \rangle_{\mathcal{H}_{K}}$ defined by $\langle K_{\bm{x}_{0}},K_{\bm{x}_{1}} \rangle_{\mathcal{H}_{K}}=K(\bm{x}_{0},\bm{x}_{1})$. That is $$\begin{aligned} \left\langle \sum_{i}\alpha_{i}K_{\bm{x}_{i}},\sum_{j}\beta_{j}K_{\bm{x}_{j}} \right\rangle_{\mathcal{H}_{K}}=\sum_{i,j}\alpha_{i}\beta_{j}K(\bm{x}_{i},\bm{x}_{j}).\end{aligned}$$ The *reproducing property* takes the following form $$\begin{aligned} \langle K_{\bm{x}},f\rangle_{\mathcal{H}_{K}}=f(\bm{x}), \quad \forall \bm{x}\in \mathcal{X}, f\in \mathcal{H}_{K}.\end{aligned}$$ In the classical supervised learning models, we are given $n$ feature vectors and their corresponding uni-variate class labels $(\bm{x}_{1},y_{1}),\cdots,(\bm{x}_{n},y_{n})\sim_{\text{i.i.d.}} P_{\bm{X},Y}$, $(\bm{x}_{i},y_{i})\in \mathcal{X}\times \mathcal{Y}\subset {{\rm I\!R}}^{d}\times {{\rm I\!R}}$. For the binary classification and regression tasks, the target spaces is given by $\mathcal{Y}=\{-1,1\}$ and $\mathcal{Y}={{\rm I\!R}}$, respectively. Given a loss function $\ell:\mathcal{Y}\times {{\rm I\!R}}\rightarrow {{\rm I\!R}}$, a classifier $f$ is learned from the function class $\mathcal{F}$ via the minimization of the regularized empirical risk $$\begin{aligned} \label{Eq:Empirical_Loss_Minimization} \inf_{f\in \mathcal{F}}\widehat{R}[f]{\stackrel{\text{def}}{=}}\dfrac{1}{n}\sum_{i=1}^{n} \ell(y_{i},f(\bm{x}_{i}))+\dfrac{\lambda}{2}\|f\|_{\mathcal{F}}^{2},\end{aligned}$$ where $\|\cdot\|_{\mathcal{F}}$ is a function norm, and $\lambda>0$ is the parameter of the regularization. Consider a Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_{K}$ with the kernel function $K:\mathcal{X}\times \mathcal{X}\rightarrow {{\rm I\!R}}$, and suppose $\mathcal{F}=\mathcal{H}_{K}\oplus 1$. Then, using the expansion $f(\bm{x})=\omega_{0}+\sum_{i=1}^{n-1}\omega_{i}K(\bm{x},\bm{x}_{i})$, and optimization over the kernel class $\mathcal{K}$ yields the following primal and dual optimization problems $$\begin{aligned} &\text{Primal:}\min_{\bm{\omega}\in {{\rm I\!R}}^{n}}\max_{K\in \mathcal{K}} \dfrac{1}{n}\sum_{i=1}^{n} \ell\left(y_{i},\omega_{0}+\sum_{i=1}^{n-1}\omega_{i}K(\bm{x},\bm{x}_{i}) \right)+\dfrac{\lambda}{2}\|\bm{\omega}\|_{2}^{2},\\ &\text{Dual:}\max_{\bm{\alpha}\in {{\rm I\!R}}^{n}}\min_{K\in \mathcal{K}}-\sum_{i=1}^{n}\ell^{\ast}(\gamma_{i},y_{i})-\dfrac{1}{2\lambda}\bm{\alpha}^{T}\bm{K}\bm{\alpha}, \end{aligned}$$ respectively, where $\ell^{\ast}(\beta,y)=\sup_{z\in {{\rm I\!R}}}\{\beta z-\ell(\beta,y)\}$ is the Fenchel's conjugate, and $\bm{K}{\stackrel{\text{def}}{=}}(K(\bm{x}_{i},\bm{x}_{j}))_{1\leq i,j\leq n}$ is the kernel Gram matrix. In the particular case of the soft margin SVMs classifier $\ell(y,z)=[1-yz]_{+}{\stackrel{\text{def}}{=}}\max\{0,1-yz\}$, the primal and dual optimizations take the following forms \[Eq:Suggest\] $$\begin{aligned} &\text{Primal:}\min_{\bm{\omega}\in {{\rm I\!R}}^{n}}\max_{K\in \mathcal{K}}\dfrac{1}{n}\sum_{i=1}^{n}\left[1-\omega_{0}y_{i}-\sum_{i=1}^{n-1}\omega_{i}y_{i}K(\bm{x},\bm{x}_{i})\right]_{+}\hspace{-3mm}+\dfrac{\lambda}{2}\|\bm{\omega}\|_{2}^{2}, \\ &\text{Dual:}\max_{\bm{\beta}\in {{\rm I\!R}}^{n}:\langle \bm{\beta},\bm{y} \rangle=0,\bm{0}\preceq \bm{\beta} \preceq C\bm{1}}\min_{K\in \mathcal{K}} \langle \bm{\beta},\bm{1}\rangle-\dfrac{1}{2}\mathrm{Tr}(\bm{K}(\bm{\beta}\odot \bm{y})(\bm{\beta}\odot \bm{y})^{T}), \end{aligned}$$ where $\odot$ is the Hadamard (element-wise) product of vectors. The form of the dual optimization in Eq. suggests that for a fixed dual vector $\bm{\beta}\in {{\rm I\!R}}^{n}$, the optimal kernel can be computed by optimizing the following $U$-statistics known as the *kernel-target alignment*, *i.e.* $$\begin{aligned} \label{Eq:kernel_target} &\max_{K\in \mathcal{K}} \dfrac{2}{n(n-1)} \sum_{1\leq i<j\leq n}y_{i}y_{j}K(\bm{x}_{i},\bm{x}_{j}).\end{aligned}$$ In this paper, we focus on the class of radial kernels [^1] $$\begin{aligned} \label{Eq:Focus} \mathcal{K}{\stackrel{\text{def}}{=}}\{K:\mathcal{X}\times \mathcal{X}\rightarrow {{\rm I\!R}}: K(\bm{x}_{i},\bm{x}_{j})=\psi(\|\bm{x}_{i}-\bm{x}_{j}\|_{2}), \psi \in C^{1}({{\rm I\!R}}) \},\end{aligned}$$ which includes the following important special cases: - *Gaussian*:$K(\bm{x},\tilde{\bm{x}})=\operatorname{exp}\left(-\dfrac{\|\bm{x}-\tilde{\bm{x}}\|_{2}^{2}}{2\sigma}\right)$, for $\sigma>0$, - *Inverse multiquadrics*: $K(\bm{x},\tilde{\bm{x}})=\left(c^{2}+\|\bm{x}-\tilde{\bm{x}} \|_{2}^{2}\right)^{-\gamma}$ for $c,\gamma>0$, - *Matèrn*: $K(\bm{x},\tilde{\bm{x}})= {c^{2\tau -d}\over \Gamma\big(\tau-{d\over 2}\big)2^{\tau-1-{d\over 2}}}\left({\|\bm{x}-\tilde{\bm{x}}\|_{2}^{2}\over c} \right)^{\tau-{d\over 2}}\mathcal{K}_{{d\over 2}-\tau}(c\|\bm{x}-\tilde{\bm{x}}\|_{2})$, where $\mathcal{K}_{\alpha}$ is the modified Bessel function of the third kind, and $\Gamma$ is the Euler Gamma function. The radial kernel $K(\bm{x}_{i},\bm{x}_{j})=\psi(\|\bm{x}_{i}-\bm{x}_{j}\|_{2})$ is a positive semi-definite kernel (a.k.a. Mercer kernel) if the uni-variate function $\psi:{{\rm I\!R}}_{+}\rightarrow {{\rm I\!R}}$ is positive semi-definite. A uni-variate function which is positive semi-definite or positive definite on every ${{\rm I\!R}}^{d}$ admits an integral representation due to Schöenberg @schoenberg1938metric [Thm. 1]: <span style="font-variant:small-caps;">(I. J. Schöenberg @schoenberg1938metric [Thm. 1])</span> A continuous function $\psi:{{\rm I\!R}}_{+}\rightarrow {{\rm I\!R}}$ is positive semi-definite if and only if it admits the following integral representation $$\begin{aligned} \psi(r)=\int_{0}^{\infty} e^{-tr^{2}}\mathrm{d}\mu(t),\end{aligned}$$ for a finite positive Borel measure $\mu$ on ${{\rm I\!R}}_{+}$. Moreover, if $\mathrm{supp}(\mu)\not= \{0\}$ then $\psi$ is positive definite, where $\mathrm{supp}(\mu)$ denotes the support of the measure $\mu\in \mathcal{M}_{+}({{\rm I\!R}}_{+})$. From the Schönberg's representation theorem @schoenberg1938metric, the following integral representation for the radial kernels follows $$\begin{aligned} \label{Eq:Sch} K(\bm{x},\widehat{\bm{x}})=\int_{0}^{\infty}e^{-\xi\|\bm{x}-\widehat{\bm{x}}\|_{2}^{2}}\mu(\mathrm{d}\xi), \quad \forall\bm{x},\widehat{\bm{x}}\in {{\rm I\!R}}^{d}, \mu\in \mathcal{M}_{+}({{\rm I\!R}}_{+}),\end{aligned}$$ where $\mathcal{M}_{+}({{\rm I\!R}}_{+})$ is the set of all finite non-negative Borel measures on ${{\rm I\!R}}_{+}$. Due to the integral representation of Equation , a kernel function $K$ is completely characterized in terms of the probability measure $\mu$. Therefore, we can reformulate the kernel-target alignment as an optimization with respect to the distribution of the kernel $$\begin{aligned} \label{Eq:Kernel_Target_Alignment} \sup_{\mu\in \mathcal{P}} \widehat{E}_{0}(\mu){\stackrel{\text{def}}{=}}\dfrac{2}{n(n-1)}\sum_{1\leq i<j\leq n}y_{i}y_{j}\int_{0}^{\infty} e^{-\xi \|\bm{x}_{i}-\bm{x}_{j}\|_{2}^{2}}\mu(\mathrm{d}\xi),\end{aligned}$$ where $\mathcal{P}\subset \mathcal{M}_{+}({{\rm I\!R}}_{+})$ is a distribution sub-set. In the sequel, we consider a distribution ball $\mathcal{P}{\stackrel{\text{def}}{=}}\{\mu\in \mathcal{M}(\Xi): W_{2}(\mu,\nu) \leq R\}$ with the radius $R>0$ and the (user-defined) center $\mu_{0}\in \mathcal{M}_{+}(\Xi)$, where $\Xi\subseteq {{\rm I\!R}}_{+}$ is the support of the distributions. Moreover, given the metric space $(\mathcal{X},d)$, for the measures $\mu,\nu\in \mathcal{M}_{+}(\mathcal{X})$, $W_{p}(\mu,\nu)$ is the $p$-Wasserstein metric defined below $$\begin{aligned} \label{Eq:Wasserstein} W_{p}(\mu,\nu){\stackrel{\text{def}}{=}}\left(\inf_{\pi \in \mathcal{C}(\mu,\nu)} \int_{\mathcal{X}\times \mathcal{X}}d^{p}(\bm{\xi}_{1},\bm{\xi}_{2}) \mathrm{d}\pi(\bm{\xi}_{1},\bm{\xi}_{2})\right)^{1\over p},\end{aligned}$$ where the infimum is taken with respect to all couplings $\pi$ of the measures $\mu,\nu\in \mathcal{M}_{+}({{\rm I\!R}}^{d})$, and $\Pi(\mu,\nu)$ is the set of all measures for which $\mu$ and $\nu$ are marginals, *i.e.*, $$\begin{aligned} \mathcal{C}(\mu,\nu){\stackrel{\text{def}}{=}}\Big\{\pi\in \mathcal{M}_{+}({{\rm I\!R}}^{d}\times {{\rm I\!R}}^{d}):T^{1}_{\#}\pi=\mu, T^{2}_{\#}\pi=\nu\Big\},\end{aligned}$$ for all the maps $T^{1}(\bm{\xi}_{1},\bm{\xi}_{2})=\bm{\xi}_{2}$ and $T^{2}(\bm{\xi}_{1},\bm{\xi}_{2})=\bm{\xi}_{1}$, and $T^{1}_{\#}\pi$ and $T^{2}_{\#}\pi$ are the push-forwards of $\pi$. Alternatively, we can recast the distributional optimization problem as a risk minimization aiming to match the output of the target kernel with the ideal kernel $\bm{K}_{\ast}=\bm{y}\bm{y}^{T}$ on the training data-set $$\begin{aligned} \label{Eq:Tends_to} \inf_{\mu\in \mathcal{P}} \widehat{E}_{\gamma}(\mu){\stackrel{\text{def}}{=}}\dfrac{2}{n(n-1)\gamma}\sum_{1\leq i<j\leq n}\left( \gamma y_{i}y_{j}-\int_{0}^{\infty} e^{-\xi \|\bm{x}_{i}-\bm{x}_{j}\|_{2}^{2}}\mu(\mathrm{d}\xi)\right)^{2}.\end{aligned}$$ As $\gamma\rightarrow +\infty$, the optimization problem in Eq. tends to that of Eq. . The distributional optimization in Eq. is infinite dimensional. To characterize a finite dimensional optimization problem, we instead optimize the samples (particles) of the target distribution. In particular, we consider the independent identically distributed samples $ \xi^{1},\cdots,\xi^{N}\sim_{\text{i.i.d.}} \mu$, and let $\bm{\xi}{\stackrel{\text{def}}{=}}(\xi^{1},\cdots,\xi^{N})$. Let $\xi_{0}^{1},\cdots,\xi_{0}^{N}\sim_{\text{i.i.d.}} \mu_{0}$. Then, we consider the following empirical risk function $$\begin{aligned} \label{Eq:Tends_to} \inf_{\widehat{\mu}^{N}\in \mathcal{P}^{N}} \widehat{E}_{\gamma}\big(\widehat{\mu}^{N}\big)&{\stackrel{\text{def}}{=}}\dfrac{2}{n(n-1)\gamma}\sum_{1\leq i<j\leq n}\left( \gamma y_{i}y_{j}-{1\over N}\sum_{k=1}^{N}e^{-\xi^{k} \|\bm{x}_{i}-\bm{x}_{j}\|_{2}^{2}}\right)^{2}.\end{aligned}$$ where $\widehat{\mu}^{N}(\xi){\stackrel{\text{def}}{=}}{1\over N}\sum_{k=1}^{N}\delta_{\xi^{k}}(\xi)$ and $\widehat{\mu}_{0}^{N}(\zeta){\stackrel{\text{def}}{=}}{1\over N}\sum_{k=1}^{N}\delta_{\xi_{0}^{k}}(\zeta)$, and $$\begin{aligned} \mathcal{P}^{N}{\stackrel{\text{def}}{=}}\Big\{\widehat{\mu}^{N}\in \mathcal{M}_{+}(\Xi):W_{2}(\widehat{\mu}^{N},\widehat{\mu}_{0}^{N})\leq R \Big\}.\end{aligned}$$ Surrogate Loss Function ----------------------- Using $h\geq 0$ for the constraint $W_{2}(\widehat{\mu}^{N},\widehat{\nu}^{N})\leq R $, a partial Lagrangian is $$\begin{aligned} \inf_{\mu\in \mathcal{M}_{+}({{\rm I\!R}}_{+})}\sup_{h\in {{\rm I\!R}}_{+}} \widehat{J}_{h}(\mu){\stackrel{\text{def}}{=}}\widehat{E}_{\gamma}(\widehat{\mu}^{N})+{h\over 2}\big(W^{2}_{2}(\widehat{\mu}^{N},\widehat{\mu}_{0}^{N})-R^{2}\big),\end{aligned}$$ where $h>0$ is the Lagrange multiplier. The Wasserstein distance in Eq. , the minimization in Eq. is computationally prohibitive. Therefore, we instead minimize a surrogate loss function. To obtain the surrogate loss function, we define the empirical measure of the samples (particles) $\xi_{m}^{1},\cdots,\xi_{m}^{N}$ at each iteration $m=0,1,2,\cdots,T$ as follows $$\begin{aligned} \widehat{\mu}^{N}_{m}(\xi){\stackrel{\text{def}}{=}}\dfrac{1}{N}\sum_{k=1}^{N}\delta(\xi-\xi_{m}^{k}).\end{aligned}$$ Then, the surrogate loss for the Wasserstein distance in Eq. can be obtained as follows. We denote the joint distribution of the particle-pair $(\xi_{m}^{i},\zeta^{j})$ by $\pi_{ij}$. Then, we obtain that $$\begin{aligned} \label{Eq:Lagrangina} W_{2}^{2}\big(\widehat{\mu}_{m}^{N},\widehat{\mu}_{0}^{N}\big)&=\arg\min_{\bm{\pi}\in \mathcal{C}_{+}} \sum_{i,j=1}^{N}\pi_{ij}|\xi_{m}^{i}-\xi_{0}^{j}|^{2}, \end{aligned}$$ where the set of couplings are given by $$\begin{aligned} \label{Eq:Couplings} \mathcal{C}_{+}{\stackrel{\text{def}}{=}}\Bigg\{\bm{\pi}\in {{\rm I\!R}}_{+}^{N\times N}: &\sum_{i=1}^{N}\pi_{ij}=\dfrac{1}{N},\sum_{j=1}^{N}\pi_{ij}=\dfrac{1}{N}, \quad i,j=1,2,\cdots,N\Bigg\}.\end{aligned}$$ is a linear program that is challenging to solve in practice for a large number of particles $N$. To improve the computational efficiency, Cuturi @cuturi2013sinkhorn have proposed to add an entropic regularization to the Wasserstein distance. The resulting *Sinkhorn divergence* solves a regularized version of Equation : $$\begin{aligned} \bm{\pi}^{\ast}&{\stackrel{\text{def}}{=}}\arg\min_{\bm{\pi}\in \mathcal{C}} \sum_{i,j=1}^{N}\pi_{ij}|\xi_{m}^{i}-\xi_{0}^{j}|^{2}-\varepsilon H(\bm{\pi}),\end{aligned}$$ where $H(\bm{\pi}){\stackrel{\text{def}}{=}}-\sum_{i,j=1}^{N}\pi_{ij}\log(\pi_{ij})$ is the entropic barrier function enforcing the non-negativity constraint on the entries $\pi_{ij}$'s, with the regularization parameter $\varepsilon>0$. Moreover, $\mathcal{C}$ has a similar definition as in Eq. , except that $(\pi_{ij})_{i,j}\in {{\rm I\!R}}^{N\times N}$, and thus $\mathcal{C}_{+}\subseteq \mathcal{C}$.The Sikhorn divergence is now computed as follows $$\begin{aligned} \label{Eq:Without_Entropic_Regularization} W_{\varepsilon,2}^{2}\big(\widehat{\mu}_{m}^{N},\widehat{\mu}_{0}^{N}\big)&=\sum_{i,j=1}^{N}\pi_{ij}^{\ast}|\xi_{m}^{i}-\xi_{0}^{j}|^{2},\end{aligned}$$ Notice that the entropic regularization term $H(\bm{\pi})$ is absent from Eq. .[^2] We thus consider the following surrogate loss function $$\begin{aligned} \label{Eq:Surrogate_Loss} \inf_{\bm{\xi}\in {{\rm I\!R}}_{+}^{N}}\widehat{J}^{N}_{h,\varepsilon}(\bm{\xi}){\stackrel{\text{def}}{=}}\widehat{E}_{\gamma}(\bm{\xi})+{h\over 2}W_{\varepsilon,2}^{2}(\widehat{\mu}_{m}^{N},\widehat{\mu}_{0}^{N}).\end{aligned}$$ The loss function $\widehat{J}_{h,\varepsilon}^{N}(\bm{\xi})$ acts as a proxy for the empirical loss $\widehat{J}_{h}^{N}(\bm{\xi})$ that we wish to optimize. After introducing the Lagrange multipliers $\bm{\lambda}{\stackrel{\text{def}}{=}}(\lambda_{i})_{1\leq i\leq N}$ and $\tilde{\bm{\lambda}}{\stackrel{\text{def}}{=}}(\tilde{\lambda}_{i})_{1\leq i\leq N}$ for the constraints on the marginals of $\pi_{ij}$, we obtain that $$\begin{aligned} \nonumber \mathcal{L}(\bm{\pi};\bm{\lambda},\bm{\gamma}){\stackrel{\text{def}}{=}}& \sum_{i,j=1}^{N}\varepsilon\pi_{ij}\log(\pi_{ij})+\sum_{i,j=1}^{N}\pi_{ij}|\xi_{m}^{i}-\xi_{0}^{j}|^{2}\\ &+\sum_{j=1}^{N}\lambda_{j}\left(\sum_{i=1}^{N}\pi_{ij}-{1\over N}\right)+\sum_{i=1}^{N}\tilde{\lambda}_{i}\left(\sum_{j=1}^{N}\pi_{ij}-{1\over N}\right),\end{aligned}$$ The optimal values of $\pi^{\ast}_{ij}$ can be derived explicitly using the KKT condition $$\begin{aligned} \pi_{ij}^{\ast}=v_{i}\operatorname{exp}\left(-\dfrac{|\xi_{m}^{i}-\xi_{0}^{j}|^{2}}{\varepsilon}\right)u_{j},\end{aligned}$$ where $v_{i}{\stackrel{\text{def}}{=}}\operatorname{exp}(-{\tilde{\lambda}_{i}\over \varepsilon}-{1\over 2})$, and $u_{j}{\stackrel{\text{def}}{=}}\operatorname{exp}(-{\lambda_{j}\over \varepsilon}-{1\over 2})$. Alternatively, the transportation matrix is given by $$\begin{aligned} \label{Eq:Wasserstein_distance_1} \bm{\pi}_{m}^{\ast}{\stackrel{\text{def}}{=}}\mathrm{diag}(\bm{v}^{\ast})e^{-{\bm{D}_{m}\over \varepsilon}}\mathrm{diag}(\bm{u}^{\ast}),\end{aligned}$$ where $\bm{v}^{\ast}{\stackrel{\text{def}}{=}}(v^{\ast}_{i})_{1\leq i\leq N}$, $\bm{u}^{\ast}{\stackrel{\text{def}}{=}}(u^{\ast}_{i})_{1\leq i\leq N}$, $\bm{D}_{m}=(d^{m}_{ij})_{ij}, d^{m}_{ij}{\stackrel{\text{def}}{=}}|\xi_{m}^{i}-\xi_{0}^{j}|^{2}$, and $\mathrm{diag}(\cdot)$ denotes the diagonal element of the matrix. The vectors $\bm{v}^{\ast}$ and $\bm{u}^{\ast}$ can be computed efficiently via the Sinkhorn-Knopp matrix scaling algorithm @sinkhorn1967concerning $$\begin{aligned} (\bm{u}_{k+1},\bm{v}_{k+1})=\mathscr{F}(\bm{u}_{k},\bm{v}_{k}), \quad k\in {{\rm I\!N}},\end{aligned}$$ where $\mathscr{F}:{{\rm I\!R}}^{N}\times {{\rm I\!R}}^{N}\rightarrow {{\rm I\!R}}^{N}\times {{\rm I\!R}}^{N}$ is the following contraction mapping $$\begin{aligned} \mathscr{F}(\bm{u},\bm{v})={1\over N}\left(\mathrm{diag}^{-1}\left(e^{-{\bm{D}\over \varepsilon}}\bm{v}_{m'-1}\right)\bm{1}_{N},\mathrm{diag}^{-1}\left(e^{-{\bm{D}\over \varepsilon}}\bm{u}_{m'-1}\right)\bm{1}_{N} \right),\end{aligned}$$ where $\bm{1}_{N}{\stackrel{\text{def}}{=}}(1,1,\cdots,1)\in {{\rm I\!R}}^{N}$. Moreover, $$\begin{aligned} \label{Eq:Wasserstein_distance_3} W_{\varepsilon,2}^{2}(\widehat{\mu}^{N}_{m},\widehat{\nu}^{N})=\mathrm{Tr}\left(\bm{D}\bm{\pi}_{m}^{\ast}\right).\end{aligned}$$ To optimize Eq. , we consider the projected noisy stochastic gradient descent optimization method (a.k.a. Langevin dynamics). In particular, at each iteration $m=0,1,\cdots,T$, two samples $\bm{z}_{m}=(y_{m},\bm{x}_{m})$ and $\tilde{\bm{z}}_{m}=(\tilde{y}_{m},\tilde{\bm{x}}_{m})$ uniformly and randomly are drawn from the training data-set. Then, we analyze the following iterative optimization method $$\begin{aligned} \label{Eq:following_iterations} \bm{\xi}_{m+1}=\mathscr{P}_{\Xi^{N}}\left(\bm{\xi}_{m}-\eta_{m} \nabla \widehat{J}^{N}_{\varepsilon,h}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m})+\sqrt{\dfrac{2\eta}{\beta}} \bm{\zeta}_{m}\right),\end{aligned}$$ where $(\xi_{0}^{k})_{1\leq k\leq N}\sim_{\mathrm{i.i.d}} \mu_{0}$ Above, $\beta>0$ is the temperature parameter, $\eta_{m}>0$ is the step-size, and $(\bm{\zeta}_{m})_{m\in {{\rm I\!N}}}\sim_{\text{i.i.d.}} \mathsf{N}(0,\bm{I}_{N\times N})$ is the isotropic Gaussian noise. Note that when $\gamma\rightarrow \infty$, the iterations in Eq. correspond to the projected stochastic gradient descent method. Moreover, $\mathscr{P}_{\Xi^{N}}(\cdot)$ is the projection onto the sub-set $\Xi^{N}\subseteq {{\rm I\!R}}_{+}^{N}$. Furthermore, $\nabla \widehat{J}^{N}_{\varepsilon,h}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m}){\stackrel{\text{def}}{=}}\left(\nabla_{k} \widehat{J}^{N}_{\varepsilon,h}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m}) \right)_{1\leq k\leq m}$ is the stochastic gradient that has the following elements $$\begin{aligned} \label{Eq:Nabla_RN} \nabla_{k} \widehat{J}^{N}_{\varepsilon,h}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m})&{\stackrel{\text{def}}{=}}{\partial E_{\gamma}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m}) \over \partial \xi_{m}^{k}}+{h\over 2}\dfrac{\partial W^{2}_{\varepsilon,2}(\widehat{\mu}^{N}_{m},\widehat{\nu}^{N})}{\partial \xi_{m}^{k}}.\end{aligned}$$ where for all $k=1,2,\cdots,N$. To update the Lagrange multiplier $h$, we note that Eq. is concave in $h>0$, and $h$ is a scaler. Therefore, a bisection method can be applied to optimize the Lagrange multiplier $h$. In Algorithm \[Algoirthm:1\], we summarize the main steps of the proposed kernel learning approach. To analyze the complexity of Algorithm \[Algoirthm:1\], we note that the Sinkhorn's divergence can be computed in $O(N^{2})$ time @cuturi2013sinkhorn. Since the Euclidean projection in Eq. is onto the hyper-cube $\Xi^{N}$, it can be computed efficiently in $O(N)$ time by computing $\min\{\xi^{k},\xi_{u}\}$ and $\min\{\xi^{k},\xi_{l}\}$ for each particle $k=1,2,\cdots,N$. Overall, the $\epsilon$-optimal solution to problem can be reached in $O(N^{2}\log(1/\epsilon))$. \[t!\] $$\begin{aligned} \bm{\xi}\leftarrow\mathscr{P}_{\Xi^{N}}\left(\bm{\xi}-\eta\nabla \widehat{J}^{N}_{\varepsilon,h_{s}}(\bm{\xi};\bm{z},\tilde{\bm{z}})+\sqrt{2\eta\over \beta}\bm{\zeta} \right). \end{aligned}$$ $$\begin{aligned} \bm{\xi}\leftarrow\mathscr{P}_{\Xi^{N}}\left(\bm{\xi}-\eta\nabla \widehat{J}^{N}_{\varepsilon,h_{s}}(\bm{\xi};\bm{z},\tilde{\bm{z}})+\sqrt{2\eta\over \beta}\bm{\zeta} \right). \end{aligned}$$ Main Results {#Section:Main_Results} ============ In this section, we state our main theoretical results regarding the performance of the proposed kernel learning procedure. The proof of theoretical results is presented in Appendix. Assumptions ----------- To state our theoretical results, we first state the technical assumptions underlying our theoretical results: - The feature space $\mathcal{X}\subset {{\rm I\!R}}^{d}$ has a finite diameter, *i.e.*, $$\begin{aligned} \nonumber K{\stackrel{\text{def}}{=}}\sup_{\bm{x},\bm{y}\in \mathcal{X}} \|\bm{x}-\bm{y}\|_{2}<\infty. \end{aligned}$$ - The slater condition holds for the empirical loss functions. In particular, we suppose there exists $\bm{\xi}_{s}\in {{\rm I\!R}}_{+}^{N}$ and $\bar{\bm{\xi}}_{s}\in {{\rm I\!R}}_{+}^{N}$ such that $\bm{\xi}_{s}\in \mathrm{relint}(\mathcal{P}^{N})$, and ${\bar{\bm{\xi}}}_{s}\in \mathrm{relint}(\mathcal{P}_{\varepsilon}^{N})$.[^3] - The Langevin particles are confined to a compact sub-set of ${{\rm I\!R}}_{+}$, *i.e.*, $\Xi=[\xi_{l},\xi_{u}]$, for some $0\leq \xi_{l}<\xi_{u}<+\infty$. - The Langevin particles are initialized by sampling from a distribution $\mu_{0}\in \mathcal{M}_{+}(\Xi)$ whose Lebesgue density exists. Let $q_{0}(\xi){\stackrel{\text{def}}{=}}\mathrm{d}\mu_{0}/\mathrm{d}\xi$ denotes the associated Lebesgue density. We remark that while **(A.3)** is essential to establish theoretical performance guarantees for Algorithm \[Algoirthm:1\] in this paper, in practice, the same algorithm can be employed to optimize distributions with unbounded support. Non-asymptotic consistency -------------------------- In this part, we prove that the value of the population optimum evaluated at the solution of the finite sample optimization problem in Eq. approaches its population value as the number of training data $(n)$, the number of Langevin particles $(N)$, the regularization parameter $(\gamma)$, and the inverse of the parameter of the Sinkhorn transport $(\varepsilon)$ tend to infinity. <span style="font-variant:small-caps;"><span>(Non-asymptotic Consistency of Finite-Sample Estimator)</span></span> \[Thm:Consistency of Monte Carlo Estimation\] Further, consider the distribution balls $\mathcal{P}$ and $\mathcal{P}_{\varepsilon}^{N}$ of the radius $R$ that are defined with respect to the $2$-Wasserstein and Sinkhorn's divegences, respectively. Define the optimal values of the population optimization and its finite sample estimate $$\begin{aligned} \nonumber \mu_{\ast}(\xi){\stackrel{\text{def}}{=}}\inf_{\mu\in \mathcal{P}} E_{0}(\mu(\xi)){\stackrel{\text{def}}{=}}{{\rm I\!E}}_{P^{\otimes 2}_{\bm{x},y}}[\widehat{E}_{0}(\mu(\xi))], \quad \widehat{\mu}^{N}_{\ast}(\xi;\gamma,\varepsilon){\stackrel{\text{def}}{=}}\inf_{\widehat{\mu}^{N}\in \mathcal{P}_{\varepsilon}^{N}} \widehat{E}_{\gamma}(\widehat{\mu}^{N}).\end{aligned}$$ respectively. Then, with the probability of (at least) $1-3\varrho$ over the training data samples $\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$ and the Langevin particles $\{\xi_{0}^{k}\}_{k=1}^{N}$, the following non-asymptotic bound holds $$\begin{aligned} \nonumber \Big|E_{0}(\mu_{\ast}(\xi))-E_{0}(\widehat{\mu}_{\ast}^{N}(\xi;\varepsilon,\gamma)) \Big|&\leq \dfrac{2\sqrt{2}(\xi_{u}-\xi_{l})}{R^{2}\sqrt{N}}\left(1+{\log^{1\over 2}\left(\dfrac{4\sqrt{2N}(\xi_{u}-\xi_{l})}{\varrho } \right)}\right)\\ \nonumber &+2\max\left\{\dfrac{c_{1}L^{2}}{n} \ln^{1\over 2}\left(\dfrac{4}{\varrho}\right),\dfrac{c_{2}RL^{4} }{n^{2}}\ln\left(\dfrac{4e^{L^{4}\over 9}}{\varrho}\right) \right\}+\dfrac{3}{\gamma}+c_{3}e^{-{1\over \varepsilon}},\end{aligned}$$ where $c_{1}=3^{1\over 4}\times 2^{4}$, and $c_{2}=9\times 2^{11}$, and $c_{3}$ is a constant independent of $\varepsilon$. The proof of Theorem \[Thm:Consistency of Monte Carlo Estimation\] is presented in Appendix \[Proof:Consistency\_of\_Monte\_Carlo\]. Scaling limits for the unconstrained optimization ------------------------------------------------- In this part, we provide a mean-field analysis of the projected particle optimization in Eq. for the special case of the unconstrained optimization. In particular, throughout this part, we assume $R=\infty$ in the distributional ball (thus $h=0$). We then analyze the following Langevin optimization method for unconstrained distributional optimization: $$\begin{aligned} \label{Eq:Dump} \bm{\xi}_{m+1}=\mathscr{P}_{\Xi^{N}}\left(\bm{\xi}_{m}-\eta_{m} \nabla \widehat{J}^{N}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m})+\sqrt{\dfrac{2\eta}{\beta}} \bm{\zeta}_{m}\right),\end{aligned}$$ where $\widehat{J}^{N}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m}){\stackrel{\text{def}}{=}}\widehat{J}_{\varepsilon,h}^{N}(\bm{\xi}_{m};\bm{z}_{m},\tilde{\bm{z}}_{m})\Big\vert_{h=0}$. The first result of this paper is concerned with the scaling limits of the Langevin optimization method in Eq. in the mean-field regime: <span style="font-variant:small-caps;">(Mean-Field Partial Differential Equation)</span> \[Theorem:Mean-Field Partial Differential Equation\] Suppose Assumptions $\mathbf{(A.1)}$-$\mathbf{(A.4)}$ are satisfied. Let $\mu^{N}_{t}$ denotes the continuous-time embedding of the empirical measure $(\widehat{\mu}^{N}_{k})_{k\in {{\rm I\!N}}}$ associated with the projected Langevin particles in Eq. , *i.e.*, $$\begin{aligned} \mu^{N}_{t}(\xi){\stackrel{\text{def}}{=}}\widehat{\mu}^{N}_{\lfloor {t\over \eta} \rfloor}= \dfrac{1}{N}\sum_{k=1}^{N}\delta(\xi-\xi^{k}_{\lfloor {t\over \eta}\rfloor}), \quad 0\leq t\leq T,\end{aligned}$$ associated with the projected particle Langevin optimization in Eq. .[^4] Suppose the step size $\eta=\eta_{N}$ satisfies $\eta_{N}\rightarrow 0$, $N/\log(\eta_{N}/N)\rightarrow \infty$, and $\eta_{N}/\log(\eta_{N}/N)\rightarrow 0$ as $N\rightarrow \infty$. Furthermore, suppose the Lebesgue density $q_{0}(\xi)=\mathrm{d}\mu_{0}/\mathrm{d}\xi$ exists. Then, for any fixed $t\in [0,T]$, $\mu^{N}_{t}\stackrel{\text{weakly}}{\rightarrow}\mu_{t}$ as $N\rightarrow\infty$, where the Lebesgue density of the limiting measure $p^{\ast}_{t}(\xi)=\mathrm{d}\mu^{\ast}_{t}/\mathrm{d}\xi$ is a solution to the following distributional dynamics with Robin boundary conditions as well as an initial datum[^5] \[Eq:distributional\_dynamics\] $$\begin{aligned} \dfrac{\partial p_{t}(\xi)}{\partial t}&=\dfrac{\partial}{\partial \xi}\left(p_{t}(\xi)\dfrac{\partial}{\partial \xi}J(\xi,p_{t}(\xi))\right)+\dfrac{1}{\beta} \dfrac{\partial^{2}}{\partial\xi^{2}}\left(p_{t}(\xi)\right),\quad \forall(t,\xi)\in [0,T]\times (\xi_{l},\xi_{u}), \\ \label{Eq:Robin_Boundary} {\partial p_{t}(\xi)\over \partial \xi}&+\beta p_{t}(\xi)\dfrac{\partial}{\partial \xi}J(\xi,p_{t}(\xi))\Big\vert_{\xi=\xi_{l}}=0, \quad\forall t\in [0,T],\\ {\partial p_{t}(\xi)\over \partial \xi}&+\beta p_{t}(\xi)\dfrac{\partial}{\partial \xi}J(\xi,p_{t}(\xi))\Big\vert_{\xi=\xi_{u}}=0,\quad\forall t\in [0,T], \\ p_{0}(\xi)&=q_{0}(\xi), \quad \forall \xi\in [\xi_{l},\xi_{u}] \\ p_{t}(\xi)&\geq 0,\quad \forall \xi\in [\xi_{l},\xi_{u}],\quad \int_{\Xi}p_{t}(\xi)\mathrm{d}\xi=1, \quad \forall t\in [0,T], \end{aligned}$$ where the functional $J(\xi,p_{t}(\xi))$ is defined $$\begin{aligned} \nonumber J(\xi,p_{t}(\xi))={{\rm I\!E}}\Big[y\hat{y}\operatorname{exp}(-\xi \|\bm{x}-\hat{\bm{x}}\|_{2}^{2}) \Big]+\dfrac{1}{\gamma}\int_{0}^{\infty}{{\rm I\!E}}\Big[\operatorname{exp}(-(\xi+\xi') \|\bm{x}-\hat{\bm{x}}\|_{2}^{2})\Big] p_{t}(\xi')\mathrm{d}\xi'.\end{aligned}$$ Above, the expectations are taken with respect to the tensor product of the joint distribution $P^{\otimes 2}_{\bm{x},y}$ of the features and class labels, and its marginal $P^{\otimes 2}_{\bm{x}}$, respectively. The proof of Theorem \[Theorem:Mean-Field Partial Differential Equation\] is presented in Appendix \[Appendix:Proof\_of\_Theorem\_Mean\_Field\]. Let us make several remarks regarding the distributional dynamics in Theorem \[Theorem:Mean-Field Partial Differential Equation\]. First, we notice that despite some resemblance between Eq. and the Fokker-Plank (a.k.a. forward Kolmogorov) equations for the diffusion-drift processes, they differ in that the drift $J(\xi,p_{t}(\xi))$ of Eq. is a functional of the Lebesgue density of the law of the underlying process. In the context of kinetic gas theory of statistical physics, such distributional dynamics are known as the Mckean-Vlasov partial differential equations; see, *e.g.*, @chan1994dynamics. Second, the proof of Theorem \[Theorem:Mean-Field Partial Differential Equation\] is based on the notion of *propogation of chaos* or *asymptotic freedom* @sznitman1991topics [@khuzani2019mean], meaning that the dynamics of particles are decoupled in the asymptotic of infinitely many particles $N\rightarrow \infty$. To formalize this notion, we require the following definitions: <span style="font-variant:small-caps;">(Exchangablity)</span> Let $\nu$ be a probability measure on a Polish space $\mathcal{S}$ and. For $N\in {{\rm I\!N}}$, we say that $\nu^{\otimes N}$ is an exchangeable probability measure on the product space $\mathcal{S}^{n}$ if it is invariant under the permutation $\bm{\pi}{\stackrel{\text{def}}{=}}(\pi(1),\cdots,\pi(N))$ of indices. In particular, $$\begin{aligned} \label{Eq:Exchangable} \nu^{\otimes N}(\bm{\pi}\cdot B)=\nu^{\otimes N}(B), \end{aligned}$$ for all Borel subsets $B\in \mathcal{B}(\mathcal{S}^{n})$. An interpretation of the exchangablity condition can be provided via De Finetti's representation theorem which states that the joint distribution of an infinitely exchangeable sequence of random variables is as if a random parameter were drawn from some distribution and then the random variables in question were independent and identically distributed, conditioned on that parameter. Next, we review the mathematical definition of chaoticity, as well as the propagation of chaos in the product measure spaces: <span style="font-variant:small-caps;">(Chaoticity)</span> \[Def:Chaoticity\] Suppose $\nu^{\otimes N}$ is exchangeable. Then, the sequence $\{\nu^{\otimes N}\}_{N\in {{\rm I\!N}}}$ is $\nu$-chaotic if, for any natural number $\ell \in {{\rm I\!N}}$ and any test function $f_{1},f_{2},\cdots,f_{k}\in C_{b}^{2}(\mathcal{S})$, we have $$\begin{aligned} \label{Eq:Chaoticity} \lim_{N\rightarrow \infty}\left\langle\prod_{k=1}^{\ell} f_{k}(s^{k}),\nu^{\otimes N}(\mathrm{d}s^{1},\cdots,\mathrm{d}s^{N})\right\rangle= \prod_{k=1}^{\ell}\langle f_{k},\nu\rangle \end{aligned}$$ According to Eq. of Definition \[Def:Chaoticity\], a sequence of probability measures on the product spaces $\mathcal{S}$ is $\nu$-chaotic if, for fixed $k$ the joint probability measures for the first $k$ coordinates tend to the product measure $\nu(\mathrm{d}s_{1})\nu(\mathrm{d}s_{2})\cdots \nu(\mathrm{d}s_{k})=\nu^{\otimes k}$ on $\mathcal{S}^{k}$. If the measures $\nu^{\otimes N}$ are thought of as giving the joint distribution of $N$ particles residing in the space $\mathcal{S}$, then $\{\nu^{\otimes N}\}$ is $\nu$-chaotic if $k$ particles out of $N$ become more and more independent as $N$ tends to infinity, and each particle's distribution tends to $\nu$. A sequence of symmetric probability measures on $\mathcal{S}^{N}$ is chaotic if it is $\nu$-chaotic for some probability measure $\nu$ on $\mathcal{S}$. If a Markov process on $\mathcal{S}^{N}$ begins in a random state with the distribution $\nu^{\otimes N}$, the distribution of the state after $t$ seconds of Markovian random motion can be expressed in terms of the transition function $\mathcal{K}^{N}$ for the Markov process. The distribution at time $t>0$ is the probability measure $U_{t}^{N}\nu^{\otimes N}$ is defined by the kernel $$\begin{aligned} \label{Eq:Definition_of_Ut} U_{t}^{N}\nu^{\otimes N}(B){\stackrel{\text{def}}{=}}\int_{\mathcal{S}^{N}}\mathcal{K}^{N}(s,B,t)\nu^{\otimes N}(\mathrm{d}s).\end{aligned}$$ <span style="font-variant:small-caps;">(Propogation of Chaos)</span> A sequence functions $$\begin{aligned} \Big\{\mathcal{K}^{N}(s,B,t)\Big\}_{N\in {{\rm I\!N}}} \end{aligned}$$ whose $N$-th term is a Markov transition function on $\mathcal{S}^{N}$ that satisfies the permutation condition $$\begin{aligned} \mathcal{K}^{N}(s,B,t)=\mathcal{K}^{N}(\bm{\pi}\cdot s,\bm{\pi}\cdot B,t), \end{aligned}$$ propagates chaos if whenever $\{\nu^{\otimes N} \}_{N\in {{\rm I\!N}}}$ is chaotic, so is $\{U_{t}^{N} \}$ for any $t\geq 0$, where $U_{t}^{N}$ is defined in Eq. . In the context of this paper, the propagation of chaos simply means that the time-scaled empirical measures $\widehat{\mu}^{N}_{t}$ (say, on the path space) converge weakly in probability to the deterministic measure $\mu_{t}$, or equivalently that the law of $(\xi_{\lfloor {t\over \eta}\rfloor}^{1},\cdots, \xi_{\lfloor{t\over \eta}\rfloor}^{N})$ converges weakly to the product measure $\mu_{t}^{\otimes N}$ for any fixed $N$, where $\mu_{t}$ is the law of the following *reflected* diffusion-drift Itô process $$\begin{aligned} \label{Eq:Lulu} \theta_{t}=\theta_{0}-\int_{0}^{t}{\partial\over \partial \xi}J(\xi_{s},\mu_{s}(\xi))\mathrm{d}s +\dfrac{1}{\beta}W_{t}+Z_{t}^{-}-Z_{t}^{+}, \quad \mu_{t}\stackrel{\mathrm{law}}{=} \theta_{t}.\end{aligned}$$ In Eqs. , $Z_{t}^{-}$ and $Z_{t}^{+}$ are the non-negative reflection processes from the boundaries $\xi_{l}$ and $\xi_{u}$, respectively. In particular, $Z_{t}^{-}$ and $Z_{t}^{+}$ are non-decreasing, cádlág, with the initial values $Z_{0}^{+}=Z_{0}^{-}=0$, and $$\begin{aligned} \int_{0}^{\infty}(X_{t}-\xi_{\mathrm{l}})\mathrm{d}Z^{-}_{t}=0, \quad \int_{0}^{\infty}(\xi_{\mathrm{u}}-X_{t})\mathrm{d}Z^{+}_{t}=0,\end{aligned}$$ where the integrals are in the Stieltjes sense. In fact, we show that the law of the Langevin particles $(\xi_{\lfloor {t\over \eta}\rfloor}^{1},\cdots, \xi_{\lfloor {t\over \eta}\rfloor}^{N})$ converges in the $2$-Wasserstein distance to $\mu_{t}^{\otimes N}$. Alternatively, due to the bounded equivalence of the Wasserstein distance and the total variation distance on compact metric spaces (cf. **(A.3)**), the sense in which $\widehat{\mu}^{N}_{t}$ converges in probability to $\mu_{t}$ can be strengthened; rather than working with the usual weak-$^\ast$ topology induced by duality with bounded continuous test functions (see, *e.g.*, @khuzani2019mean), we work with the stronger topology induced by duality with bounded measurable test functions. Third, the Robin boundary conditions in Eq. captures the effect of an *elastic reflection* of the particles in the projected particle Langevin optimization method. Alternatively, the Robin boundary conditions asserts that the flux of particles in and out of the boundaries is zero. In particular, the particles are constrained to stay in $(\xi_{l},\xi_{u})$ by barriers at $\xi=\xi_{u}$ and $\xi=\xi_{l}$, in such a way that when the particle hits the barrier with incoming velocity $v<0$, it will instantly bounce back with velocity $−\rho v\geq 0$, where $\rho \geq 0$ is a parameter called the *velocity restitution coefficient*. When $\rho=1$ we say that the reflection is perfectly elastic; when $\rho=0$ it is said to be a *rigid reflection* resulting in the Neumann boundary conditions instead of the Robin boundary conditions. By definition of the Euclidean projection $\mathscr{P}_{\Xi^{N}}(\cdot)$ in the projected Langevin particle of Eq. , the particles are bounced off of the boundary of the projection space with the elastic parameter $\rho=\beta$. Fourth, we note that the solution of the distributional dynamics in Eq. is absolutely continuous with respect to $\xi$, and lacks atoms at the boundaries $\xi=\xi_{l}$ and $\xi=\xi_{u}$. This is due to the fact that the boundaries are non-absorbing. In the next proposition, we establish the existence and uniqueness of the steady-state solutions of the mean-field PDE : <span style="font-variant:small-caps;">(Existence and Uniqueness of the Steady-State Solution)</span> \[Proposition:Uniqueness and Fixed Points\] Suppose Assumptions $\mathbf{(A.1)}$-$\mathbf{(A.4)}$ are satisfied. Then, the following assertions hold: - There exists a unique non-negative steady-state solution for the mean-field PDE in Eq. in the weak sense. - The fixed point of the restricted Gibbs-Boltzmann measure $$\begin{aligned} p_{\ast}(\xi)= \dfrac{\operatorname{exp}(-\beta J(\xi,p_{\ast}(\xi)) )}{Z_{\beta}}\bm{1}_{\xi\in \Xi}, \quad Z_{\beta}{\stackrel{\text{def}}{=}}\int_{\Xi} \operatorname{exp}(-\beta J(\xi,p_{\ast}(\xi)))\mathrm{d}\xi.\end{aligned}$$ is a steady-state solution to the mean-field PDE in Eq. . The proof of Proposition \[Proposition:Uniqueness and Fixed Points\] is deferred to Appendix \[Appendix:Proof\_of\_Uniqueness\]. Performance Evaluation on Synthetic and Benchmark Data-Sets {#Section:Performance Evaluation on Synthetic and Benchmark Data-Sets} =========================================================== For simulations of this section, we consider kernel SVMs in conjunction with the random feature model of Rahimi and Recht @rahimi2008random [@rahimi2009weighted]. Specifically, we consider the following model random feature model: $$\begin{aligned} \label{Eq:Random_Feature_Model} K(\bm{x},\tilde{\bm{x}})=\int_{\Omega}\varphi(\bm{x};\bm{\omega})\varphi(\tilde{\bm{x}};\bm{\omega})\nu(\mathrm{d}\bm{\omega}),\end{aligned}$$ where $\varphi: \mathcal{X}\times \Omega\rightarrow {{\rm I\!R}}$ is the random feature. For translation invariant kernels, we have $\varphi(\bm{x};\bm{\omega})=\sqrt{2}\cos(\langle \bm{x},\bm{\omega} \rangle+b)$, where $b\sim \mathrm{Uniform}[-\pi,\pi]$ is a random bias term. Given the i.i.d. samples $\bm{\zeta}^{1},\cdots,\bm{\zeta}^{D}\sim_{\text{i.i.d.}} \nu$, then we minimize the following risk function $$\begin{aligned} \min_{\bm{\alpha}\in {{\rm I\!R}}^{D}} \dfrac{1}{n}\sum_{i=1}^{n}\max\left\{0,1-\sum_{k=1}^{D}y_{i}\alpha_{i}\varphi(\bm{x}_{i};\bm{\omega}_{k}) \right\}+\dfrac{\lambda}{2}\|\bm{\alpha}\|_{2}^{2}.\end{aligned}$$ To compute the random features associated with the radial kernels, we note that the probability measure of the random feature has the following Lebesgue's density $$\begin{aligned} \nonumber \dfrac{\mathrm{d}\nu}{\mathrm{d}\bm{\omega}}&=\int_{\Xi} \left(\dfrac{1 }{2\xi}\right)^{{d\over 2}} \operatorname{exp}\left(-{ \|\bm{\omega}\|_{2}^{2}\over 4\xi}\right)\mu(\mathrm{d}\xi).\end{aligned}$$ More specifically, due to the fact that $$\begin{aligned} \int_{0}^{\infty}\left(\int_{{{\rm I\!R}}^{d}}\left|e^{-i\langle \bm{\omega},\bm{x}-\tilde{\bm{x}} \rangle}\left(\dfrac{1 }{2\xi}\right)^{{d\over 2}} \operatorname{exp}\left(-{ \|\bm{\omega}\|_{2}^{2}\over 4\xi}\right) \right|\mathrm{d}\bm{\omega}\right)\mu(\mathrm{d}\xi) < \infty,\end{aligned}$$ the Tonelli-Fubini theorem is admissible. Therefore, we may change the order of integral to derive where we recognize the last term as the integral representation of the radial kernel in Eq. . Let $\bm{\xi}=(\xi^{k})_{1\leq k\leq N}\sim_{\text{i.i.d.}} \mu$ denotes the vector outputs of Algorithm \[Algoirthm:1\]. We draw the random features, $$\begin{aligned} \bm{\varphi}(\bm{x}){\stackrel{\text{def}}{=}}(\varphi(\bm{x};\bm{\omega}_{1}),\cdots,\varphi(\bm{x};\bm{\omega}_{D})),\end{aligned}$$ where $\bm{\omega}_{1},\cdots,\bm{\omega}_{D}\sim_{\mathrm{i.i.d.}} \widehat{\nu}^{N}$. We compare our method with three alternative kernel learning techniques, namely, the importance sampling of Sinha and Duchi @sinha2016learning, the Gaussian bandwidth optimization via $k$ nearest neighbor ($k$-NN) @chen2017simple, and our proposed particle SGD in @khuzani2019mean. In the sequel, we provide a brief description of each method: - *Importance Sampling*: the importance sampling of Sinha and Duchi @sinha2016learning which proposes to assign a weight $w^{m}$ to each sample $\bm{\omega}^{m}\in {{\rm I\!R}}^{d_{0}}$ for $m=1,2,\cdots,N$. The weights are then optimized via the following standard optimization procedure $$\begin{aligned} \label{Eq:Importance} \max_{w^{1},\cdots,w^{N_{\bm{\omega}}}\in \mathcal{Q}_{N}}\dfrac{1}{2n(n-1)} \sum_{1\leq i<j\leq n}y_{i}y_{j}\sum_{k=1}^{N_{\bm{\omega}}}w^{m}\varphi(\bm{x}_{i};\bm{\omega}^{k})\varphi(\bm{x}_{j};\bm{\omega}^{k}), \end{aligned}$$ where $\mathcal{Q}_{N_{\bm{\omega}}}{\stackrel{\text{def}}{=}}\{\bm{w}\in {{\rm I\!R}}_{+}^{N_{\bm{\omega}}}: \langle \bm{w},\bm{1}\rangle=1, \chi(\bm{w}|| \bm{1}/N_{\bm{\omega}})\leq R\}$ is the distributional ball, and $\chi(\cdot||\cdot)$ is the $\chi^{2}-$divergence. Notice that the complexity of solving the optimization problem in Eq. is insensitive to the dimension of random features $\bm{x}_{i}\in {{\rm I\!R}}^{d}$. - *Gaussian Kernel with $k$-NN Bandwidth Selection Rule*: In this method, we fix the Gaussian kernel $K(\bm{x},\bm{y})=\operatorname{exp}\left(-{\|\bm{x}-\bm{y}\|_{2}^{2}\over \sigma^{2}}\right)$. To select a good bandwidth for the kernel, we use the deterministic $k$ nearest neighbor ($k$NN) approach of @chen2017simple. In particular, we choose the bandwidth according to the following rule $$\begin{aligned} \sigma^{2}= \dfrac{1}{n}\sum_{i=1}^{n}\|\bm{x}_{i}-\bm{x}_{i}^{k\mathrm{NN}}\|_{2}^{2}, \end{aligned}$$ where $\bm{x}_{i}^{k\mathrm{NN}}$ is defined as $k$ nearest neighbor of $\bm{x}_{i}$. In our experiments, we let $k=3$. We then generate random Fourier features $\varphi(\bm{x};\bm{\omega}^{k})=\sqrt{{2\over N_{\bm{\omega}}}}\cos(\langle \bm{w},\bm{\omega}^{k} \rangle+b^{k})$, with $(\bm{\omega}^{k})_{1\leq k\leq N}\sim_{\mathrm{i.i.d.}} {1\over \sqrt{2\pi\sigma^{2}}}\operatorname{exp}(-\sigma^{2}\|\bm{\omega}\|_{2}^{2})$ and $(b^k)_{1\leq k\leq N}\sim_{\mathrm{i.i.d.}} \mathrm{Uniform}[-\pi,\pi]$. - *Particle Stochastic Gradient Descend Method*: This is the method that we proposed in the earlier work @khuzani2019mean, where we optimized the samples in the random feature model of Eq. . In particular, for $k=1,2,\cdots,N$. Notice that in the random feature model of @rahimi2008random [@rahimi2009weighted], the explicit feature map is given by $\varphi(\bm{x};\bm{\omega})=\sqrt{2}\cos(\langle \bm{x},\bm{\omega}\rangle+b)$, where the dimension of the particles in Eq. is the same as the dimension of the feature vectors $\bm{x}\in {{\rm I\!R}}^{d}$. As a result, for high dimensional data-sets $(d\gg 1)$, the computational complexity per iterations of Eq. is potentially prohibitive. Empirical Results on the Synthetic Data-Set ------------------------------------------- For experiments with the synthetic data, we use the setup of @khuzani2019mean. The synthetic data-set we consider is as follows: - The distribution of training data is $P_{\bm{V}}=\mathsf{N}(\bm{0},(1+\lambda)\bm{I}_{d\times d})$, - The distribution of generated data is $P_{\bm{W}}=\mathsf{N}(\bm{0},(1-\lambda)\bm{I}_{d\times d})$. To reduce the dimensionality of data, we consider the embedding $\iota:{{\rm I\!R}}^{d}\mapsto {{\rm I\!R}}^{d_{0}}, \bm{x}\mapsto \iota(\bm{x})=\bm{\Sigma}\bm{x}$, where $\bm{\Sigma}\in {{\rm I\!R}}^{d_{0}\times d}$ and $d_{0}<d$. In this case, the distribution of the embedded features are $P_{\bm{X}|Y=+1}=\mathsf{N}(\bm{0},(1+\lambda)\bm{\Sigma}\bm{\Sigma}^{T})$, and $P_{\bm{X}|Y=-1}=\mathsf{N}(\bm{0},(1-\lambda)\bm{\Sigma}\bm{\Sigma}^{T})$. Note that $\lambda\in [0,1]$ is a parameter that determines the separation of distributions. In particular, the Kullback-Leibler divergece of the two multi-variate Gaussian distributions is controlled by $\lambda\in [0,1]$, $$\begin{aligned} D_{\mathrm{KL}}(P_{\bm{X}|Y=-1},P_{\bm{X}|Y=+1})=\dfrac{1}{2}\left[ \log \left(\dfrac{1-\lambda}{1+\lambda}\right)-d_{0}+d_{0}(1-\lambda^{2})\right].\end{aligned}$$ In Figure \[Fig:4\], we show the *i.i.d.* samples from the distributions $P_{\bm{V}}$ and $P_{\bm{W}}$ for different choices of variance parameter of $\lambda=0.1$, $\lambda=0.5$, and $\lambda=0.9$. Notice that for larger $\lambda$ the divergence is reduced and thus performing the two-sample test is more difficult. From Figure \[Fig:4\], we clearly observe that for large values of $\lambda$, the data-points from the two distributions $P_{\bm{V}}$ and $P_{\bm{W}}$ have a large overlap and conducting a statistical test to distinguish between these two distributions is more challenging. ### Kernel Learning Approach {#subsubsection:Kernel Learning Approach} Figure \[Fig:5\] depicts our two-phase kernel learning procedure. The kernel learning approach consists of training the auto-encoder for the dimensionality reduction and the kernel optimization sequentially, *i.e.*, $$\begin{aligned} \label{Eq:solution_of_the_optimization} \sup_{\widehat{\mu}^{N}\in\mathcal{P}^{N}}\sup_{\iota \in \mathcal{Q}}\widehat{\mathrm{MMD}}_{K_{\widehat{\mu}^{N}}\circ \iota}^{\alpha}[P_{\bm{V}},P_{\bm{W}}].\end{aligned}$$ where the function class is defined $\mathcal{Q}{\stackrel{\text{def}}{=}}\{\iota(\bm{z})=\sigma(\bm{\Sigma}\bm{z}+\bm{b}),\bm{\Sigma}\in {{\rm I\!R}}^{d_{0}\times d},\bm{b}\in {{\rm I\!R}}^{d_{0}}\}$, and $(K_{\widehat{\mu}^{N}}\circ \iota)(\bm{x}_{1},\bm{x}_{2})=K_{\widehat{\mu}^{N}}(\iota(\bm{x}_{1}),\iota(\bm{x}_{2}))$. Here, $\bm{\sigma}(\cdot)$ is the sigmoid non-linearity. Now, we consider a two-phase optimization procedure: - <span style="font-variant:small-caps;">Phase (I)</span>: we fix the kernel function, and optimize the auto-encoder to compute a co-variance matrix $\bm{\Sigma}$ and the bias term $\bm{b}$ for the dimensionality reduction. - <span style="font-variant:small-caps;">Phase (II)</span>: we optimize the kernel based from the learned embedded features $\iota(\bm{x})$. This two-phase procedure significantly improves the computational complexity of SGD as it reduces the dimensionality of random feature samples $\bm{\xi}\in {{\rm I\!R}}^{D}$, $D=d_{0}\ll d$. \ ### Statistical Hypothesis Testing with the Kernel MMD Let $\bm{V}_{1},\cdots,\bm{V}_{m}\sim_{\text{i.i.d.}} P_{\bm{V}}=\mathsf{N}(\bm{0},(1+\lambda)\bm{I}_{d\times d})$, and $\bm{W}_{1},\cdots,\bm{W}_{n}\sim_{\text{i.i.d.}} P_{\bm{W}}=\mathsf{N}(\bm{0},(1-\lambda)\bm{I}_{d\times d})$. Given these i.i.d. samples, the statistical test $\mathcal{T}(\{\bm{V}_{i}\}_{i=1}^{m},\{\bm{W}_{i}\}_{j=1}^{n}):\mathcal{V}^{m}\times \mathcal{W}^{n}\rightarrow \{0,1\}$ is used to distinguish between these hypotheses: - <span style="font-variant:small-caps;">Null hypothesis</span> $\mathsf{H}_{0}:P_{\bm{V}}=P_{\bm{W}}$ (thus $\lambda=0$), - <span style="font-variant:small-caps;">Alternative hypothesis</span> $\mathsf{H}_{1}:P_{\bm{V}}\not= P_{\bm{W}}$ (thus $\lambda>0$). To perform hypothesis testing via the kernel MMD, we require that $\mathcal{H}_{\mathcal{X}}$ is a universal RKHS, defined on a compact metric space $\mathcal{X}$. Universality requires that the kernel $K(\cdot,\cdot)$ be continuous and, $\mathcal{H}_{\mathcal{X}}$ be dense in $C(\mathcal{X})$. Under these conditions, the following theorem establishes that the kernel MMD is indeed a metric: <span style="font-variant:small-caps;">(Metrizablity of the RKHS)</span> Let $\mathcal{F}$ denotes a unit ball in a universal RKHS $\mathcal{H}_{\mathcal{X}}$ defined on a compact metric space $\mathcal{X}$ with the associated continuous kernel $K(\cdot,\cdot)$. Then, the kernel MMD is a metric in the sense that $\mathrm{MMD}_{K}[P_{\bm{V}},P_{\bm{W}}]=0$ if and only if $P_{\bm{V}}=P_{\bm{W}}$. A radial kernel is universal if the support of the measure in the integral representation in Eq. excludes the origin, i.e., $\mathrm{supp}(\mu)\not=\{0\}$, see @sriperumbudur2011universality. To design a test, let $\widehat{\mu}^{N}_{m}(\bm{\xi})={1\over N}\sum_{k=1}^{N}\delta(\bm{\xi}-\bm{\xi}_{m}^{k})$ denotes the solution of SGD in for solving the optimization problem. Consider the following MMD estimator consisting of two $U$-statistics and an empirical function $$\begin{aligned} \nonumber \widehat{\mathrm{MMD}}_{K_{\widehat{\mu}_{m}^{N}}\circ \iota}\big[\{\bm{V}_{i}\}_{i=1}^{m},\{\bm{W}_{i}\}_{i=1}^{n}\big]&=\dfrac{1}{m(m-1)}\sum_{k=1}^{N}\sum_{i\not =j}\varphi(\iota(\bm{V}_{i}),\bm{\omega}_{m}^{k})\varphi(\iota(\bm{V}_{j}),\bm{\omega}_{m}^{k})\\ \nonumber &\hspace{4mm}+\dfrac{1}{n(n-1)}\sum_{k=1}^{N}\sum_{i\not =j}\varphi(\iota(\bm{W}_{i}),\bm{\omega}_{m}^{k})\varphi(\iota(\bm{W}_{j}),\bm{\omega}_{m}^{k})\\ \label{Eq:Negative_Estimator} &\hspace{4mm}-\dfrac{2}{nm}\sum_{k=1}^{N}\sum_{i=1}^{m}\sum_{j=1}^{n}\varphi(\iota(\bm{W}_{i}),\bm{\omega}_{m}^{k})\varphi(\iota(\bm{V}_{j}),\bm{\omega}^{k}_{m}).\end{aligned}$$ Given the samples $\{\bm{V}_{i}\}_{i=1}^{m}$ and $\{\bm{W}_{i}\}_{i=1}^{n}$, we design a test statistic as below $$\begin{aligned} \label{Eq:Test_statistics} \mathcal{T}(\{\bm{V}_{i}\}_{i=1}^{m},\{\bm{W}_{i}\}_{i=1}^{n}){\stackrel{\text{def}}{=}}\begin{cases} \mathsf{H}_{0} & \text{if } \widehat{\mathrm{MMD}}_{K_{\widehat{\mu}_{m}^{N}}\circ \iota}\big[\{\bm{V}_{i}\}_{i=1}^{m},\{\bm{W}_{i}\}_{i=1}^{n}\big]\leq \tau \\ \mathsf{H}_{1} & \text{if } \widehat{\mathrm{MMD}}_{K_{\widehat{\mu}_{m}^{N}}\circ \iota}\big[\{\bm{V}_{i}\}_{i=1}^{m},\{\bm{W}_{i}\}_{i=1}^{n}\big]> \tau, \end{cases}.\end{aligned}$$ where $\tau\in {{\rm I\!R}}$ is a threshold. Notice that the unbiased MMD estimator of can be negative despite the fact that the population MMD is non-negative. Consequently, negative values for the statistical threshold $\tau$ are admissible. Nevertheless, int our simulations, we only consider non-negative values for the threshold $\tau$. A Type I error is made when $\mathsf{H}_{0}$ is rejected based on the observed samples, despite the null hypothesis having generated the data. Conversely, a Type II error occurs when $\mathsf{H}_{0}$ is accepted despite the alternative hypothesis $\mathsf{H}_{1}$ being true. The *significance level* $\alpha$ of a test is an upper bound on the probability of a Type I error: this is 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 a test* is the probability of rejecting the null hypothesis $\mathsf{H}_{0}$ when it is indeed incorrect. In particular, $$\begin{aligned} \mathrm{Power}{\stackrel{\text{def}}{=}}{{\rm I\!P}}(\text{reject}\ \mathsf{H}_{0}| \mathsf{H}_{1} \ \text{is true}).\end{aligned}$$ In this sense, the statistical power controls the probability of making Type II errors. Empirical results on benchmark data-sets ---------------------------------------- In Figure \[Fig:5\], we evaluate the power of the test for $100$ trials of hypothesis test using the test statistics of . To obtain the result, we used an autoencoder to reduce the dimension from $d=100$ to $p=50$. Clearly, for the trained kernel in Panel (a) of Figure \[Fig:5\], the threshold $\tau$ for which $\mathrm{Power}=1$ increases after learning the kernel via the two phase procedure described earlier. In comparison, in Panel (b), we observe that training an auto-encoder only with a fixed standard Gaussian kernel $K(\bm{x},\bm{y})=\operatorname{exp}(-\|\bm{x}-\bm{y}\|_{2}^{2})$ attains lower thresholds compared to our 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. We also observer that the particle SGD for optimization we proposed in @khuzani2019mean to optimize the translation invariant kernels provides the highest statistical power for a given threshold value. Nevertheless, as we observe in Figure \[Fig:5\], the run-time of the particle SGD for a given number of particles is significantly higher than Algorithm \[Algoirthm:1\]. This is due to the fact that the dimension of the particles in the particle SGD is dependent on the number of hidden layers of auto-encoder. In contrast, the particles in Algorithm \[Algoirthm:1\] are one dimensional. \ \ \ \ Application to Locally Sensitive Hashing ======================================== \ \ \ \ \ \ \ \ \ \ \ The research on computer systems and web search in the mid-nineties was focused on designing "hash" functions that were sensitive to the topology on the input domain, and preserved distances approximately during hashing. Constructions of such hash functions led to efficient methods to detect similarity of files in distributed file systems and proximity of documents on the web. We describe the problem and results below. Recall that a metric space $(\mathcal{C},d)$ is given by a set $\mathcal{C}$ (here the set of cells) and a distance measure $d:\mathcal{X}\times \mathcal{X}\rightarrow {{\rm I\!R}}_{+}$ which satisfies the axioms of being a metric. <span style="font-variant:small-caps;">(Locally Sensitive Hash Function)</span> Given a metric space $(\mathcal{C},\rho)$ and the set $\mathcal{L}$, a family of function $H\subseteq \{h :\mathcal{C}\rightarrow \mathcal{L}\}$ is said to be a basic locality sensitive hash (LSH) family if there exists an increasing invertible function $\alpha:{{\rm I\!R}}_{+}\rightarrow [0,1] $ such that for all $\bm{x},\tilde{\bm{x}}\in \mathcal{X}$, we have $$\begin{aligned} {{\rm I\!P}}_{h\in \mathcal{H}}[h(\bm{x})=h(\tilde{\bm{x}})]\leq \alpha(d(\bm{x},\tilde{\bm{x}})). \end{aligned}$$ To contrast the locally sensitive hash functions with the standard hash function families note that in the latter, the goal is to map a domain $\mathcal{C}$ to a range $\mathcal{L}$ such that the probability of a collision among any pair of elements $\bm{x}\not=\tilde{\bm{x}}\in \mathcal{C}$ is small. In contrast, with LSH families, we wish for the probability of a collision to be small only when the pairwise distance $d(\bm{x},\tilde{\bm{x}})$ is large, and we do want a high probability of collision when $d(\bm{x},\tilde{\bm{x}})$ is small. Indyk and Motwani @indyk1998approximate showed that such a hashing scheme facilitates the construction of efficient data structures for answering approximate nearest-neighbor queries on the collection of objects. In the sequel, we describe a family of locally sensitive hash functions due to Raginsky, et al. @raginsky2009locality, where the measure $d(\bm{x},\tilde{\bm{x}})$ is determined by a kernel function. We draw a random threshold $t\sim \mathrm{Uniform}[-1,1]$ and define the quantizer $Q_{t}(u)=\mathrm{sgn}(t+u)$. The following theorem is due to Raginsky, *et al.* @raginsky2009locality: <span style="font-variant:small-caps;">(Kernel Hash Function, Raginsky, et al. @raginsky2009locality)</span> \[Lemma:KHF\] Consider a translation invariant kernel $K:\mathcal{X}\times \mathcal{X}\rightarrow {{\rm I\!R}}, K(\bm{x},\tilde{\bm{x}})=\phi(\bm{x}-\tilde{\bm{x}})$. Define the following hamming $\mathbb{Z}_{2}^{n}$-code $$\begin{aligned} F^{n}(\bm{x}){\stackrel{\text{def}}{=}}(F_{t_{1},b_{1},\bm{\omega}_{1}}(\bm{x}),\cdots,F_{\tau_{n},b_{n},\bm{\omega}_{n}}(\bm{x})),\end{aligned}$$ where $(b_{i})_{1\leq i\leq n}\sim_{\text{i.i.d}} \mathrm{Uniform}[-\pi,\pi]$, $(t_{i})_{1\leq i\leq n}\sim_{\text{i.i.d.}} \mathrm{Uniform}[-1,1]$, and $(\bm{\omega}_{i})_{1\leq i\leq n}\sim_{\text{i.i.d.}} \nu$, where $\nu$ is the distribution in the Rahimi and Recht random feature model $$\begin{aligned} \phi(\bm{x}-\tilde{\bm{x}})=\int_{{{\rm I\!R}}^{d}}\varphi(\bm{x};\bm{\omega})\varphi(\tilde{\bm{x}};\bm{\omega})\mathrm{d}\nu(\bm{\omega}).\end{aligned}$$ Furthermore, $F_{t,b,\bm{\omega}}:{{\rm I\!R}}^{d}\rightarrow \mathbb{Z}_{2}$ is a mapping defined as follows $$\begin{aligned} \label{Eq:Ftb} F_{t,b,\bm{\omega}}(\bm{x}){\stackrel{\text{def}}{=}}\dfrac{1}{2}\Big[1+Q_{t}(\cos(\langle \bm{\omega},\bm{x}\rangle+b)) \Big].\end{aligned}$$ Fix $\epsilon,\delta\in (0,1)$. For any finite data set $D = \{\bm{x}_{1},\cdots,\bm{x}_{N}\}\subset {{\rm I\!R}}^{d}$, $F^{n}$ is such that $$\begin{aligned} h_{K}(\bm{x}_{i}-\bm{x}_{j})-\delta\leq {1\over n}d_{\mathrm{H}}(F^{n}(\bm{x}_{i}),F^{n}(\bm{x}_{j}))\leq h_{K}(\bm{x}_{i}-\bm{x}_{j})+\delta,\end{aligned}$$ where $d_{H}(\cdot,\cdot):\mathbb{Z}^{n}_{2}\times \mathbb{Z}^{n}_{2}\rightarrow \{0,1\}$ is the Hamming distance. Furthermore, $$\begin{aligned} h_{K}(\bm{x}_{i}-\bm{x}_{j}){\stackrel{\text{def}}{=}}\dfrac{8}{\pi^{2}} \sum_{m=0}^{\infty}\dfrac{1-K(m\bm{x}_{i}-m\tilde{\bm{x}}_{i})}{4m^{2}-1} .\end{aligned}$$ The construction of LSH in Eq. of Lemma is based on the random feature model of Rahimi and Recht @rahimi2008random [@rahimi2009weighted], and is restricted to the Hamming codes defined on a hyper-cube. In the sequel, we present an alternative kernel LSH using the embedding of functions in $L^{p}(\Omega,\nu)$ space into $\ell^{p}$-spaces, generalizing the result of Lemma \[Lemma:KHF\] to any finite integer alphabet $\mathbb{Z}_{q}{\stackrel{\text{def}}{=}}\{0,1,\cdots,q-1\}$. To describe the result, we define the Lee distance between two code-words $\bm{x}=(x_{1},\cdots,x_{n}),\bm{y}=(y_{1},\cdots,y_{n})\in \mathbb{Z}_{q}^{n}$ of length $n$ as follows $$\begin{aligned} d_{\mathrm{Lee}}(\bm{x},\bm{y})&{\stackrel{\text{def}}{=}}\sum_{i=1}^{n}\min\{(x_{i}-y_{i})\ \mathrm{mod}\ q, (y_{i}-x_{i})\ \mathrm{mod}\ q\}\\ &=\sum_{i=1}^{n}\min\{|y_{i}-x_{i}|, q-|y_{i}-x_{i}|\}.\end{aligned}$$ In the special cases of $q=2$ and $q=3$, the Lee distance corresponds to the Hamming distance as distances are $0$ for two single equal symbols and 1 for two single non-equal symbols. For $q>3$ this is not the case anymore, and the Lee distance can become larger than one. <span style="font-variant:small-caps;">(Generalized Kernel LSH)</span> \[Lemma:Kernel\_LSH\_via\_Embedding\] Consider a translation invariant kernel $K:{{\rm I\!R}}^{d}\times {{\rm I\!R}}^{d}\rightarrow {{\rm I\!R}}, K(\bm{x},\tilde{\bm{x}})=\psi(\|\bm{x}-\tilde{\bm{x}}\|_{2}^{2})$. Define a random map $G_{t,\bm{\omega}}:{{\rm I\!R}}^{d}\rightarrow \mathbb{Z}_{q}$ through the following function $$\begin{aligned} G_{t,\bm{w}}(\bm{x}){\stackrel{\text{def}}{=}}\left\lceil q^{-1}({\langle \bm{w},\bm{\varphi}_{N}(\bm{x}) \rangle+t}) \right\rceil \mathrm{mod}\ q, \end{aligned}$$ where $\bm{w}\sim \mathsf{N}(0,\bm{I}_{N\times N})$, $t\sim \mathrm{Uniform}[0,q]$. Moreover, $\bm{\varphi}_{N}(\bm{x}){\stackrel{\text{def}}{=}}(\cos(\langle\bm{\omega}_{k},\bm{x} \rangle+b_{k}))_{1\leq k\leq N}$, where $b_{1},\cdots,b_{N}\sim_{\text{i.i.d.}}\nu_{0}{\stackrel{\text{def}}{=}}\mathrm{Uniform}[-\pi,\pi]$, and $\bm{\omega}_{1},\cdots,\bm{\omega}_{N}\sim_{\text{i.i.d.}}\nu$. Then, the probability of collision is bounded as follows $$\begin{aligned} \nonumber &\left|{{\rm I\!P}}\Big[G_{t,\bm{w}}(\bm{x})=G_{t,\bm{\omega}}(\tilde{\bm{x}})\Big]-\Psi_{q}(K(\bm{x},\tilde{\bm{x}}))\right|=\mathcal{O}\left(\dfrac{\ln(N)}{N}\right). \end{aligned}$$ where $\Psi_{q}:{{\rm I\!R}}_{+}\mapsto {{\rm I\!R}}_{+}$ is defined $$\begin{aligned} \Psi_{q}(u){\stackrel{\text{def}}{=}}\int_{0}^{q}{1\over \sqrt{\pi (1-u)}}e^{-{s^{2}\over 4(1-u)}} \left( 1-\dfrac{s}{q}\right)\mathrm{d}s. \end{aligned}$$ The proof of Lemma \[Lemma:Kernel\_LSH\_via\_Embedding\] is presented in Appendix \[Appendix:Proof\_of\_General\_Kernel\_LSH\], and uses the property of the stable distributions. Description of the experiment ----------------------------- We present image retrieval results for 10000 images from MNIST databases \[10\]. The images are 28 by 28 pixels and are compressed via an auto-encoder with 500 hidden layers, which have proven to be effective at learning useful features. For this experiment, we randomly select 1,000 images to serve as queries, and the remaining 9,000 images make up the "database". To distinguish true positives from false positives for the performance evaluation retrieval performance, we select a "nominal" neighborhood. Results ------- In Figure \[Fig:5\], we illustrate the scatter plots of the hash codes $F^{n}(\bm{x})$ of length $n\in \{128,512,4096\}$ bits. In Figure \[Fig:5\] (a)-(c), we show the scatter plots for Hamming codes constructed by Lemma \[Lemma:KHF\] using an untrained Gaussian kernel $K(\bm{x},\widehat{\bm{x}})=\operatorname{exp}(-\|\bm{x}-\widehat{\bm{x}}\|_{2}^{2})$. From Figure \[Fig:5\] (a)-(c) we observe that as the number of bits of the Hamming code increase, the scatter plots concentrate around a curve that has a flat region. Evidently, this curve deviates from the ideal curve which is a straight line passing through the origin. In particular, in \[Fig:5\] (a)-(c), as the Euclidean distance changes on the interval $[2,8]$ of $x$-axis, the normalized Hamming distance of the constructed codes remains constant. To attain proportionality between the Hamming distance and the Euclidean distance, we train the kernel using Algorithm \[Algoirthm:1\]. To generate the labels for kernel training, we first perform a $k$-NN on 1000 images from 9,000 images of the data-base, where here $k=10$. Then, we generate the binary class labels by assigning $y=+1$ to the points in a randomly chosen cluster, and $y=-1$ to the remaining data-points in other clusters (*i.e.*, the one-versus-all rule). After training the kernel, the kernel is used to generate the Hash codes using the construction of Lemma \[Lemma:KHF\]. The resulting scattering plots are depicted in Figure \[Fig:5\] (d)-(f), and the Hamming distances are more proportional to the Euclidean distance. Central to our study is the precision-recall curve, which captures the trade-off between precision and recall for different threshold. A high area under the curve represents both high recall and high precision, where high precision relates to a low false positive rate, and high recall relates to a low false negative rate. High scores for both show that the classifier is returning accurate results (high precision), as well as returning a majority of all positive results (high recall). Specifically, $$\begin{aligned} {\displaystyle {\text{Precision}}{\stackrel{\text{def}}{=}}{\frac {|\{{\text{relevant images}}\}\cap \{{\text{retrieved images}}\}|}{|\{{\text{retrieved images}}\}|}}},\\ {\displaystyle {\text{Recall}}{\stackrel{\text{def}}{=}}{\frac {|\{{\text{relevant images}}\}\cap \{{\text{retrieved images}}\}|}{|\{{\text{relevant images}}\}|}}}.\end{aligned}$$ In Figure \[Fig:6\] we illustrate the precision-recall curves for Hamming codes of different lengths $n\in \{64,512,2048,4096\}$. We also depict the precision-recall curve for the Euclidean distance. We recall the notions of the recall and precision as follows From Figure \[Fig:6\](a), we depict the precision-recall curves for Hamming codes constructed from the Gaussian kernel. We observe that even Hamming codes of length $4096$ bits attain the precision-recall curve that is significantly lower than the Euclidean curve. In Figure \[Fig:6\](b), we illustrate the precision-recall curves after training kernels using Algorithm \[Algoirthm:1\]. The curves from Hamming codes are markedly closer to the curve associated with the Euclidean distance. In Figure \[Fig:6\](c), we depict the precision-recall curves using the $q$-ary codes in Lemma \[Lemma:Kernel\_LSH\_via\_Embedding\] for different quantization levels $q\in \{2,3,5,10\}$. Clearly, increasing $q$ leads to a better performance initially while larger values of $q$ has a diminishing return. This can be justified using Figure \[Fig:7\], where we plot the normalized histogram of the distance of a sample query point from each point of the MNIST data-base consisting of 9,000 of data-points. The blue color histogram depict the histogram using a Euclidean distance, and the orange color histogram with spikes depicts the histogram of the Lee distance. Figure \[Fig:7\](a)-(c) are plotted with the quantization levels $q=2$, $q=20$, and $q=50$, respectively. As the quantization level increases, the histogram of the Lee distance provides a better approximation for the Euclidean distance histogram. However, even for large $q$, there is a disparity between the two histograms, as the length of the $q$-ary codes are fixed at $n=512$ and is finite. In Figure \[Fig:8\], we depict the retrieval results for three query digits $\{1,0,4\}$ on MNIST data-set. In Fig. \[Fig:8\](a)-(c), we show the performance of retrieval system using a Euclidean distance for searching nearest neighbor. In particular, for each query digit, the retrieval system returns 99 similar images among 9,000 images in the data-base using nearest neighborhood search. The retrieved images for less challenging digits such as 1 and 0 are all correct, while for more challenging query points such as 4, some erroneous images are retrieved. In Fig. \[Fig:8\](d)-(f), we depict the retrieved images using a Hamming distance for the nearest neighborhood search, where the Hamming codes for each feature vector are generated via the kernel LSH in Lemma \[Lemma:KHF\], where a Gaussian kernel $K(\bm{x},\widehat{\bm{x}})=\operatorname{exp}(-\|\bm{x}-\widehat{\bm{x}}\|_{2}^{2})$ is employed. We observe that compared to the Euclidean distance in Fig. \[Fig:8\](a)-(c), the performance of Hamming based nearest neighbor search is significantly less accurate. However, we point out that from a computation complexity perspective, computing the Hamming distance is significantly more efficient than the Euclidean distance which is the main motivation in using LSH for nearest neighborhood search. In Fig. \[Fig:8\] (g)-(i), we show the retrieval results after training the kernel using Algorithm \[Algoirthm:1\]. Clearly, the retrievals are more accurate on the digits $0$ and $4$. However, the length of the Hamming code required to achieve such performance is quite large $n=4096$. In Fig. \[Fig:8\] (j)-(l), we show the retrieval performance using the $q$-ary code of length $n=1024$ and the quanitization level of $q=10$. Although the length of the $q$-ary code is significantly smaller than that of the Hamming code, the retrieval error is slightly less. However, the computational cost is slightly higher than that of the Hamming code. In the future, we will test our method on data-sets consisting of millions of data points. At present, our promising initial results on MNIST data-set, combined with our comprehensive theoretical analysis, convincingly demonstrate the potential usefulness of our kernel learning scheme for large-scale indexing and search applications. Classification on Benchmark Data-Sets ===================================== We now apply our kernel learning method for classification and regression tasks on real-world data-sets. Data-Sets Description --------------------- We apply our kernel learning approach to classification and regression tasks of real-world data-sets. In Table \[Table:Benchmark\_Data\_Descrpition\], we provide the characteristics of each data-set. All of these datasets are publicly available at UCI repository.[^6] ### Online news popularity This data-set summarizes a heterogeneous set of features about articles published by Mashable in a period of two years. The goal is to predict the number of shares in social networks (popularity). ### Buzz in social media dataset This data-set contains examples of buzz events from two different social networks: Twitter, and Tom's Hardware, a forum network focusing on new technology with more conservative dynamics ### Adult Adult data-set contains the census information of individuals including education, gender, and capital gain. The assigned classification task is to predict whether a person earns over 50K annually. The train and test sets are two separated files consisting of roughly 32000 and 16000 samples respectively. ### Epileptic Seizure Detection The epileptic seizure detection data-set consists of a recording of brain activity for 23.6 seconds. The corresponding time-series is sampled into 4097 data points. Each data point is the value of the EEG recording at a different point in time. So we have total 500 individuals with each has 4097 data points for 23.5 seconds. The 4097 data points are then divided and shuffled every into 23 segments, each segment contains 178 data points for 1 second, and each data point is the value of the EEG recording at a different point in time. Quantitative Comparison ----------------------- In Figure
{'source': 'arXiv_out/2006'}