Learning with Hierarchical Kernels, Supplement
Ingo Steinwart
%% \thanks{
% % % % % % % % % % % Philipp Thomann
% % % % % % % % % % % Institut für Stochastik und Anwendungen
% % % % % % % % % % % Universität Stuttgart
% % % % % % % % % % % Pfaffenwaldring 57
70569 Stuttgart
% % % % % % % % % % % philipp.thomann@mathematik.uni-stuttgart.de
% % % % % % % % % % % % David S.~Hippocampus\thanks{Use footnote for providing further % % % % % % % % % % % % information about author (webpage
alternative % % % % % % % % % % % % address)---not
David S.~Hippocampus\thanks{Use footnote for providing further information about author (webpage
alternative address)---not
% % % % % % % % % % % We investigate iterated compositions of weighted sums of Gaussian kernels and provide an % % % % % % % % % % % interpretation of the construction that shows some similarities with deep architectures. % % % % % % % % % % % On the theoretical side, we show that these kernels are universal and that SVMs using these % % % % % % % % % % % kernels are universally consistent. We also describe a parameter optimization method and % % % % % % % % % % % validate it empirically by comparing some architectures of the resulting kernels. % % % % % % % % % % %
analysis.tex
\section{Mathematical Analysis}\label{sec:analysis}



In this section we analyze hierarchical Gaussian kernels theoretically.
Our main result shows that these kernels are universal under a simple
and natural assumption. Based on this, we then show that SVMs using such 
kernels are universally consistent.











\begin{theorem}\label{main-universal-result}
 Let $X\subset \Rd$ be compact. Then 
 every hierarchical Gaussian kernel $k_{\g,X_I,H}$ of some  depth is universal if  $I=\{1,\dots,d\}$.
\end{theorem}


\begin{proofof}{Theorem \ref{main-universal-result}}
Let us first consider the case $I=\{1,\dots,d\}$.
If $k_{\g,X_I,H}$ has depth 1, then the assertion follows by Theorem \ref{hier-kernel-universal} and the 
fact that linear kernels are injective. Moreover, for higher  depths the universality  follows
from Theorem \ref{hier-kernel-universal} and the injectivity of universal kernels. 
% Finally, it is obvious that the
% hierarchical Gaussian kernel $k_{\g,X_I,H}$ cannot be universal if $I\neq \{1,\dots,d\}$.
\end{proofof}

% 
% 
% Note that for sets $X=[a,b]^d$, the condition 
% $I=\{1,\dots,d\}$ in Theorem \ref{main-universal-result} is also necessary.

Let us fix some $Y\subset \R$.
In the following, a measurable function $L:Y\times \R\to [0,\infty)$ is called a loss.
We further say that the loss $L$ is convex or continuous, if it is convex or continuous with respect to its second argument.
Moreover, $L$ is called Lipschitz continuous, if 
\begin{displaymath}
 |L|_1 := \sup_{y,t\neq t'}\frac{\bigl|L(y,t) -L(y,t')\bigr|}{|t-t'|} < \infty\, ,
\end{displaymath}
where the supremum is taken over all possible values of $y,t$, and $t'$.
Finally, we say that $L$ can be  clipped at some $M>0$ if  
$L(y,\clippt ) \Leq L(y,t)$,
where $\clippt$ denotes the {clipped} value of $t$ at $\pm M$, that is $\clippt := \max\{-M, \min\{M, t\}\}$.
Recall that \cite[Lemma 2.23]{StCh08} gives a simple characterization of convex, clippable losses. In particular, 
the hinge loss is clippable, and so are the 
least squares loss and the pinball loss, if $Y$ is bounded. Furthermore, all these losses are convex and continuous, and 
the hinge loss and the pinball loss are also Lipschitz continuous.
Given a distribution $P$ on $X\times Y$ and a 
(measurable) function $f:X\to \R$, the $L$-risk of $f$ is 
\begin{displaymath}
 \RP L f := \int_{X\times Y}L(y,f(x))\, dP(x,y)\,.
\end{displaymath}
Moreover, the Bayes risk $\RPB L:= \inf\{\RP L f| f:X\to \R\}$ is the smallest possible risk. Finally,  the empirical risk
with respect to some data set $D=((x_1,y_1), \dots,(x_n,y_n))$ is, as usual, 
\begin{displaymath}
 \RD L f := \frac 1 n \sum_{i=1}^nL\bigl(y_i, f(x_i)\bigr)\, .
\end{displaymath}
Now let $L$ be a convex loss, $H$ be an RKHS over $X$ and $\lb>0$ be some regularization parameter. Then the SVM decision function for the data set $D$ is the 
unique solution of the optimization problem 
\begin{equation}\label{svm-opt-problem}
 \fDl = \arg\min_{f\in H} \lb \snorm f_H^2 + \RD L f\, .
\end{equation}
The statistical properties of these learning methods have been extensively studied in the last 15 years, so that a rich theory
is now available, see e.g.~\cite{CuZh07,StCh08}. One key concept of this theory is the so-called  approximation error 
function 
\begin{displaymath}
 A(\lb) := \inf_{f\in H} \lb\snorm f_H^2 + \RP L f -\RPB L\, , \qquad   \lb >0\, ,
\end{displaymath}
which roughly speaking describes the regularization error in an infinite-sample regime. In particular, we have 
$\lim_{\lb\to 0} A(\lb) = 0$ if $X$ is compact, $Y$ is bounded, $H$ is universal, and $L$ is one of the 
losses mentioned above. We refer to \cite[Lemma 5.15 and Corollary 5.29]{StCh08} for the derivation of these results and to 
\cite[Chapter 5.5]{StCh08} for further results in the case of unbounded $Y$.


With the help of these definitions we can now present the following oracle inequality, which is a direct
derivation from  \cite[Theorem 7.22]{StCh08} and the fact that universal kernels have a separable RKHS.

\begin{theorem}\label{consistency-result}
  Let $X\subset \Rd$ be compact, $I=\{1,\dots,d\}$, and   $k_{\g,X_I,H}$ be a 
  hierarchical Gaussian kernel of some depth. Moreover, let $L$ be a Lipschitz continuous loss that can be clipped at some 
  $M>0$ and that satisfies 
  \begin{displaymath}
   L(y,t) \leq B\, , 
  \end{displaymath}
  for some $B>0$ and all $y\in Y$, $t\in [-M,M]$.
  Then there exists a  constant $K>0$
such that for all fixed 
$\t\geq 1$, $n\geq 2$, and $\lb>0$
the SVM associated with $L$ and $k_{\g,X_I,H}$  satisfies 
\begin{align*}
% \lb\snorm\fDl^2 + 
&\RP L \fTc - \RPB L \\
&\quad \leq   9 A(\lb)
+ K   \frac {\ln n}{\lb  n}
+ \frac {15 \t} n \sqrt{\frac{A(\lb)}\lb}
+ \frac{300 B \t} {\sqrt n}
\end{align*}
with probability $P^n$ not less than $1-3e^{-\t}$. In particular, 
the SVM is universally consistent if we pick a regularization sequence $(\lb_n)$
with $\lb_n\to 0$ and $\frac {\ln n}{\lb_n  n}\to 0$, that is
\begin{displaymath}
 \RP L \fTcn \to  \RPB L
\end{displaymath}
in probability for all distributions $P$ on $X\times Y$.
\end{theorem}

Note that the oracle inequality above can also be used to derive learning rates, if, 
as usual, an assumption on the behavior of 
$A(\mycdot)$ is imposed. However, translating such a behavior into 
an assumption on $P$ is even for standard Gaussian kernels
a highly non-trivial task, see e.g.~\cite[Chapter 8.2]{StCh08} and \cite{EbSt13a},
since by \cite{SmZh03a}
all reasonable results in this direction require the kernel parameter $\g$ to change with $n$, too.
While for inhomogeneous kernels there is still some hope to adapt the analysis of \cite{EbSt13a}, 
the situation becomes extraordinarily more difficult for deeper Gaussian kernels. In addition, even 
considering inhomogeneous kernels only,  would most likely be more complicated and lengthy 
than the already involved  analysis of \cite{EbSt13a}, and hence this task is clearly 
out of the scope of this paper. Similarly, our statistical analysis can be sharpened if we add an assumption on the 
entropy number or eigenvalue behavior, see e.g.~\cite[Theorem 7.23 and Chapter 7.5]{StCh08} 
but a refined analysis in this direction is, for essentially the same reasons as above, 
again out of the scope of this paper. Finally, note that some assumptions made in Theorem \ref{consistency-result}
are \emph{not} necessary for deriving consistency. For example, the Lipschitz continuity, the bound in terms of $B$, and the clipping 
assumption can be removed for the price of a looser oracle inequality. For examples in this direction we refer to 
\cite[Chapters 6.4, 7.4, and 9.2]{StCh08}.







appendix.tex

% \newpage

\setcounter{section}{0}
\renewcommand{\thesection}{\Alph{section}}

% \input{changes}


% \newpage
\section{Appendix}\label{sec:appendix}


\begin{lemma}\label{injective-kernel-char}
   For a kernel $k$  on $X$ the following statements are equivalent:
\begin{enumerate}
   \item $k$ is injective.
	\item $k$ has one injective feature map.
\item All feature maps of $k$ are injective.
\end{enumerate}
\end{lemma}

\begin{proofof}{Lemma \ref{injective-kernel-char}}
   The implications $iii) \Rightarrow i) \Rightarrow ii)$ are trivial. To show the remaining implication,
let $\P_0:X\to H_0$ be an arbitrary 
feature map of $k$ and $\P_1:X\to H_1$ be an injective feature map of $k$. For $x,x'$ we then have
\begin{displaymath}
   \snorm{\P_0(x)-\P_0(x')}_{H_0}^2 =   k(x,x)-2k(x,x')+k(x',x')  = \snorm{\P_1(x)-\P_1(x')}_{H_1}^2\, ,
\end{displaymath}
that is $\P_0(x)=\P_0(x')$ if and only if $\P_1(x)=\P_1(x')$, and by assumption the latter is equivalent to 
$x=x'$. 
\end{proofof}







\begin{theorem}\label{hier-proto-kernel-universal}
Let $X$ be a compact metric space and $k$ be a continuous and injective kernel with  feature map $\P:X\to H$ 
and feature space $H$,
then  $k_{\g,X,H}$ defined by \eqref{hier-prot-kernel} is a universal kernel.
\end{theorem}


\begin{proofof}{Theorem \ref{hier-proto-kernel-universal}}
Since $\snorm{\P(x)-\P(x')}_H^2 = k(x,x)-2k(x,x')+k(x',x')$ we may assume without loss of generality that 
$H$ is the RKHS of  $k$ and $\P$ is the canonical feature map of $k$.
Now every compact metric space is separable and since we assumed that $k$ is continuous,
we see by \cite[Lemma 4.33]{StCh08} that $H$ is separable. 
Moreover, the continuity of $k$ implies the continuity of $\P$, see  \cite[Lemma 4.29]{StCh08}, and 
consequently, the assertion follows from 
\cite[Theorem 2.2]{ChSt10a}.
\end{proofof}


%%%%%%%%%%%%%%%%%%%%

%Our first result, whose proof can be found in the appendix, gives a simple product formula for the resulting hierarchical Gaussian kernel.

\begin{lemma}\label{hier-kernel-product}
 Let $k$ be a kernel of the form \eqref{weighted-kernel} and $H$ be its RKHS. 
 Then the resulting hierarchical Gaussian kernel $k_{\g,X_I,H}$ can be computed by 
 \begin{displaymath}
  k_{\g, X_I,H}(x,x')  = \prod_{i=1}^l k_{\g/w_i, X,H_i}\bigl(x_{I_i},x'_{I_i}\bigr)\, , \qquad\qquad x,x'\in X_I.
 \end{displaymath}
\end{lemma}



%%%%%%%%%%%%%%%%%%%%



\begin{proofof}{Lemma \ref{hier-kernel-product}}
Let $\P:X_I\to H$ be the canonical feature map of $k$, and 
$\P_i:X_{I_i}\to H_i$ be the canonical feature map of $k_i$. Then a    
simple calculation shows that, for all $x,x'\in X_I$, we have 
\begin{align*}
&    
k_{\g, X_I,H}(x,x') \\
 &= \exp\bigl( -\g^{-2}\snorm{\P(x)-\P(x')}_H^2  \bigr) \\
& = \exp\bigl(  -\g^{-2}   k(x,x)+2\g^{-2}k(x,x')-\g^{-2}k(x',x')   \bigr) \\
& = \exp\biggl( -\g^{-2} \sum_{i=1}^l w_i^2 k_i\bigl( x_{I_i}, x_{I_i} \bigr)  
   + 2\g^{-2} \sum_{i=1}^l w_i^2 k_i\bigl( x_{I_i}, x'_{I_i} \bigr) 
   - \g^{-2}\sum_{i=1}^l w_i^2 k_i\bigl( x'_{I_i}, x'_{I_i} \bigr) \biggr) \\
&    = \exp\biggl( -\g^{-2} \sum_{i=1}^l w_i^2\Bigl( k_i\bigl( x_{I_i}, x_{I_i} \bigr) 
- 2  k_i\bigl( x_{I_i}, x'_{I_i} \bigr)  +  k_i\bigl( x'_{I_i}, x'_{I_i} \bigr) \Bigr)\biggr) \\
& =  \exp\biggl( -\g^{-2} \sum_{i=1}^l w_i^2 \mnorm{\P_i(x_{I_i})-\P_i(x'_{I_i})}_{H_i}^2 \biggr) \\
& =  \prod_{i=1}^l \exp\biggl( -\g^{-2}  w_i^2 \mnorm{\P_i(x_{I_i})-\P_i(x'_{I_i})}_{H_i}^2 \biggr) \\
& = \prod_{i=1}^l k_{\g/w_i, X,H_i}\bigl(x_{I_i},x'_{I_i}\bigr)\, .
\end{align*}
In other words, we have shown the assertion.
\end{proofof}


%Our next result provides a simple sufficient condition for the universality of   the 
%hierarchical Gaussian kernels   resulting from  \eqref{weighted-kernel}.




\begin{theorem}\label{hier-kernel-universal}
 Let $k$ be a kernel of the form \eqref{weighted-kernel} and $H$ be its RKHS. 
If all kernels $k_1,\dots,k_l$ are injective, and $X_I$ is compact, then 
the resulting hierarchical Gaussian kernel $k_{\g,X_I,H}$  is universal.
\end{theorem}


% For the proof of this theorem we need the following lemma, which, despite the fact that 
% its assertion is somewhat expected, we could not find in the literature. 



\begin{proofof}{Theorem \ref{hier-kernel-universal}}
By Theorem \ref{hier-proto-kernel-universal} and the assumed injectivity of $k_i$
we know  that  $k_{\g/w_i, X_i,H_i}$ is universal on $X_{I_i}$. 
Moreover, Lemma \ref{hier-kernel-product} shows that 
 \begin{displaymath}
  k_{\g, X,H}(x,x')  = \prod_{i=1}^l k_{\g/w_i, X,H_i}\bigl(x_{I_i},x'_{I_i}\bigr)\, , \qquad\qquad x,x'\in X.
 \end{displaymath}
Therefore, Lemma \ref{tensor-universal}
together with a simple induction over $l$  gives the desired result.
% 
% 
% 
% 
% Let us now fix a compact $X\subset \pi_I(\R^m)$. Since restrictions of universal kernels onto compact subsets are
% again universal, see \cite[Lemma 4.55]{StCh08}, we may assume without loss of generality that 
% $X$ is of the form $X=[a,b]^{|I|}$
% for some  $a,b\in \R$. By Theorem \ref{hier-proto-kernel-universal} and the assumed injectivity of $k_i$
% we then know that $k_{\g/w_i, X_i,H_i}$ is universal on $X_i :=[a,b]^{|I_i|}$, that is,
% the corresponding RKHS $H_{\g/w_i, X_i,H_i}$ is dense in $C(X_i)$. From this it is easy to conclude that 
% the RKHS of $ k_{\g/w_i, X,H_i}\bigl(\pi_{I_i}(\cdot),\pi_{I_i}(\cdot)\bigr)$ is dense in the space
% $C_{I_i}(X):= \{f\circ \pi_{I_i}: f\in C(X_i)     \}$, and consequently, \dots
\end{proofof}




\begin{lemma}\label{tensor-universal}
Let $X\subset \R^m$ be a compact and non-empty subset, $I,J\subset \{1,\dots,m\}$ be non-empty,
and $k_I$ and $k_J$ be universal kernels on $X_I$ and $X_J$, respectively. Then 
$k_I\otimes k_J$ defined by 
\begin{displaymath}
k_I\otimes k_J(x , x' ) := k_I(x_I, x'_I) \cdot k_J(x_J, x'_J)   
\end{displaymath}
for all  $x , x' \in X_{I\cup J}$
  is a universal kernel on $X_{I\cup J}$.
\end{lemma}


\begin{proofof}{Lemma \ref{tensor-universal}}
Let us denote the RKHSs of $k_I$ and $k_J$ by $H_I$ and $H_J$, respectively. 
Similarly, we write $\P_I$ and $\P_J$ for the canonical feature maps of these kernels.
Moreover, let $H_I \otimes H_J$ be the formal tensor product of $H_I$ and $H_J$. 
Recall that this tensor product is a vector space spanned by the elementary tensors
$h_I\otimes h_J$, where $h_I\in H_I$ and $h_J\in H_J$. Moreover, there is a unique 
inner product $\langle \mycdot,\mycdot\rangle_{H_I \otimes H_J}$ on $H_I \otimes H_J$ that satisfies 
\begin{displaymath}
   \langle h_I\otimes h_J, h'_I\otimes h'_J \rangle_{H_I \otimes H_J} = \langle h_I, h'_I\rangle_{H_I} \cdot \langle h_J, h'_J\rangle_{H_J} 
\end{displaymath}
for all elementary tensors. We write $H_I\hat\otimes H_J$ for the completion of $H_I \otimes H_J$
with respect to the norm resulting from $\langle \mycdot,\mycdot\rangle_{H_I \otimes H_J}$.
Then the map 
\begin{align*}
 \P_I\otimes \P_J:X_{I\cup J}& \to H_I\hat\otimes H_J \\  
x&\mapsto \P_I(x_I) \otimes \P_J(x_J)
\end{align*}
 is a feature map of $k_I\otimes k_J$
since for $x,x'\in  X_{I\cup J}$ we have  
\begin{align*}
   \bigl\langle \P_I\otimes \P_J(x) , \P_I\otimes \P_J(x')\bigr\rangle_{H_I\hat\otimes H_J}
& =  \bigl\langle \P_I(x_I)\otimes \P_J(x_J) , \P_I(x'_I)\otimes \P_J(x'_J)\bigr\rangle_{H_I\otimes H_J}\\
& =  \bigl\langle \P_I(x_I), \P_I(x'_I)\bigr\rangle_{H_I} 
			\cdot  \bigl\langle \P_J(x_J) , \P_J(x'_J)\bigr\rangle_{H_J} \\
& = k_I(x_I, x'_I) \cdot k_J(x_J, x'_J)  \\
& = k_I\otimes k_J(x , x' ) \, .
\end{align*}
By \cite[Theorem 4.21]{StCh08} we then know that the RKHS $H$ of $k_I\otimes k_J$ is given by 
\begin{displaymath}\label{almost-universal}
   H = \Bigl\{ h:X_{I\cup J}\to \R  \,\bigl|\,  \exists v\in   H_I\hat\otimes H_J \mbox{ with } h(x) = \bigl\langle v, \P_I\otimes \P_J(x)\bigr\rangle_{H_I\hat\otimes H_J} \mbox{ for all $x\in X_{I\cup J}$}   \Bigr\}\, .
\end{displaymath}
Now observe that $k_I$ and $k_J$ are continouos because of  their assumed universality  
and therefore, $k_I\otimes k_J$ is continuous, too. In particular, $H$ consists of continuous functions.

Let us now consider the space
\begin{displaymath}
   C(X_I) \otimes C(X_J) := \spann \bigl\{ f\otimes g\, \bigl| \, f\in C(X_I),\, g\in C(X_J)  \bigr\}\, ,
\end{displaymath}
where again we define the functions $f\otimes g:X_{I\cup J}\to \R$ 
by $f\otimes g(x) := f(x_I)\cdot g(x_J)$ for all $x\in X_{I\cup J}$. 
Our next goal is to show that $H$ approximates the space  $C(X_I) \otimes C(X_J)$ arbitrarily well
with respect to the $\inorm\cdot$, that is
\begin{equation}
  C(X_I) \otimes C(X_J) \subset \overline{H}^{\inorm\cdot}\, ,
\end{equation}
where $\overline{H}^{\inorm\cdot}$ denotes the $\inorm\cdot$-closure of $H$ in $C(X_{I\cup J})$.
To this end, it clearly suffices to show that each $f\otimes g\in  C(X_I) \otimes C(X_J)$ 
can be arbitrarily well approximated. To show the latter, we fix an $\e>0$. Since $k_I$ and $k_J$ are universal,
there then exist $h_I\in H_I$ and $h_J\in H_J$ with $\inorm {h_I-f}\leq \e$ and $\inorm {h_J-g}\leq \e$.
For the function $h\in H$ defined by
$h(x):= \bigl\langle h_I\otimes h_J, \P_I\otimes \P_J(x)\bigr\rangle_{H_I\hat\otimes H_J}$ we then have 
\begin{align*}
   h(x) = \bigl\langle h_I\otimes h_J, \P_I\otimes \P_J(x)\bigr\rangle_{H_I\hat\otimes H_J} 
= \bigl\langle h_I, \P_I(x_I)\bigr\rangle_{H_I}
\cdot \bigl\langle h_J, \P_J(x_J)\bigr\rangle_{H_J}
= h_I(x_I) \cdot h_J(x_J)
\end{align*}
for all $x\in X_{I\cup J}$. This equation together with $\inorm{h_J} - \inorm{g} \leq\inorm{h_J-g}\leq \e $ now gives
\begin{align*}
   \inorm {h-f\otimes g} = \inorm{h_Ih_J - fg}
&\leq \inorm{h_Ih_J - fh_J}   + \inorm{fh_J - fg} \\
&\leq \inorm{h_I-f}\cdot \inorm{h_J } + \inorm{f}\cdot\inorm{h_J-g} \\
& \leq \e \cdot (\inorm g+\e) + \inorm f \cdot\e \, .
\end{align*}
From the latter we easily conclude that \eqref{almost-universal} holds.

In view of \eqref{almost-universal} we now show in the last step of the 
proof that $\ca A:=C(X_I) \otimes C(X_J)$ is dense in $C(X_{I\cup J})$.
To this end, we first observe that $\ca A$ is a sub-algebra of $C(X_{I\cup J})$ by construction. 
Moreover, $\ca A$ does not vanish, since for $x\in X_{I\cup J}$ there exist $f\in C(X_I)$ and $g\in C(X_J)$
with $f(x_I) \neq 0$ and $g(x_J) \neq 0$. This gives $f\otimes g(x) = f(x_I)\cdot g(x_J)\neq 0$.
Finally, $\ca A$ also separates points.  To check this, we first observe that 
for $x,x'\in X_{I\cup J}$ with $x\neq x'$ 
we have $x_I\neq x_I'$ or $x_J\neq x'_J$. Let us assume without loss of generality that $x_I\neq x_I'$.
Then there exists an $f\in C(X_I)$ with $f(x_I)\neq f(x'_J)$. For $g:=\eins_{X_J}\in C(X_J)$ 
being the constant one function, we then 
obtain $f\otimes g(x) = f(x_I) \neq f(x'_I) = f\otimes g(x')$,
and therefore $\ca A$ does separate points. By the theorem of Stone-Weierstra\ss\ we then see that $\ca A$ is dense 
in $C(X_{I\cup J})$.
\end{proofof}




\begin{lemma}\label{kernel-derivative}
  Let $k$ be a kernel of the form \eqref{weighted-kernel} and $H$ be its RKHS. 
 Then the resulting hierarchical Gaussian kernel $k_{\g,X_I,H}$ satisfies
 \begin{displaymath}
   \frac{\partial }{\partial w_j}k_{\g, X_I,H}(x,x')  = -2w_j \g^{-2} \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2 k_{\g, X_I,H}(x,x') \, , \qquad\qquad x,x'\in X.
 \end{displaymath}
\end{lemma}



\begin{proofof}{Lemma \ref{kernel-derivative}}
Using Lemma \ref{hier-kernel-product} we find
 \begin{align*}
   \frac{\partial }{\partial w_j} k_{\g, X_I,H}(x,x') 
   & =  \frac{\partial }{\partial w_j} \prod_{i=1}^l k_{\g/w_i, X,H_i}\bigl(x_{I_i},x'_{I_i}\bigr) \\
  & =    \prod_{i\neq j} k_{\g/w_i, X,H_i}\bigl(x_{I_i},x'_{I_i}\bigr)  
      \cdot   \frac{\partial }{\partial w_j} k_{\g/w_j, X,H_j}\bigl(x_{I_j},x'_{I_j}\bigr)  \, .
%   = 
%    \prod_{i=1}^l \exp\biggl( -\g^{-2}  w_i^2 \mnorm{\P_i(x_{I_i})-\P_i(x'_{I_i})}_{H_i}^2 \biggr)
 \end{align*}
 Moreover, we have 
 \begin{align*}
  & \frac{\partial }{\partial w_j} k_{\g/w_j, X,H_j}\bigl(x_{I_j},x'_{I_j}\bigr)  \\
   &= \frac{\partial }{\partial w_j} \exp\biggl( -\g^{-2}  w_j^2 \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2 \biggr) \\
   & = - 2\g^{-2}  w_j \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2 \exp\biggl( -\g^{-2}  w_j^2 \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2 \biggr) \\
   & = - 2\g^{-2}  w_j \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2  k_{\g/w_j, X,H_j}\bigl(x_{I_j},x'_{I_j}\bigr) \, ,
 \end{align*}
and by combining both expressions we obtain the assertion.
\end{proofof}





\begin{proofof}{Lemma \ref{depth-m-kernel-derivative}}
Let $H_j$ be a RKHS of $k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}$
and $\P_j$ be the corresponding canonical feature map.
 Then the  formula for the highest layer follows from Lemma \ref{kernel-derivative} and 
 \begin{displaymath}
  \mnorm{\P_j(x_{I_j})-\P_j(x'_{I_j})}_{H_j}^2 
  = 2 - 2 k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}(x_{I_j},x_{I_j}')\, .
 \end{displaymath}
Moreover, if $w$ is a weight that occurs in a lower layer of the $j$-th node, that is, it occurs at 
the component $\mathbf W^{(n)}_j$ of $\mathbf W^{(n)}$ for some $n\leq m-1$, then 
\eqref{depth-m-kernel} gives
\begin{align*}
  \frac{\partial }{\partial w} k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g}(x,x') 
  & = \frac{\partial }{\partial w} \exp\biggl(\!\! -2\g^{-2} \sum_{i=1}^l w_i^2 
 \bigl(1\!-\!  k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)}}( x_{I_i}, x'_{I_i})\bigr) \!\! \biggr) \\
 &=  \exp\biggl( -2\g^{-2} \sum_{i\neq j} w_i^2 
 \bigl(1-  k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)}}( x_{I_i}, x'_{I_i})\bigr)  \biggr) \\
& \quad \cdot \frac{\partial }{\partial w} \exp\biggl(\! -2\g^{-2} w_j^2 
 \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\bigr) \! \biggr)\, .  
\end{align*}
In addition, the chain rule yields
\begin{align*}
 &\frac{\partial }{\partial w} \exp\biggl(\! -2\g^{-2} w_j^2 
 \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\bigr) \! \biggr)\\
 & = \exp\biggl(\! -2\g^{-2} w_j^2 
 \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\bigr) \! \biggr) \\
&\quad \cdot
 \frac{\partial }{\partial w}  
 \Bigl(-2\g^{-2} w_j^2 \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\bigr) \Bigr)\\
 & = \exp\biggl(\! -2\g^{-2} w_j^2 
 \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\bigr) \! \biggr) \\
&\quad \cdot 2 \g^{-2} w_j^2
 \frac{\partial }{\partial w}   k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}( x_{I_j}, x'_{I_j})\, .
\end{align*}
Combining both expressions, we then obtain the second formula.
\end{proofof}




To illustrate the lemma~\ref{depth-m-kernel-derivative} we note that the parameter 
derivatives of hierarchical Gaussians $k_{\mathbf v}$ of depth 1, that is, of kernels of 
the form \eqref{depth-1-kernel}, are given by 
\begin{displaymath}
 \frac{\partial }{\partial v_j} k_{\mathbf v} (x,x') 
 =  -2v_j (x_j-x_j')^2  k_{\mathbf v} (x,x') \, , \qquad \qquad x,x'\in X\, .
\end{displaymath}
To derive an explicit formula for depth-2-kernels we fix 
some
first layer weight vectors
$\mathbf v_1=(v_{i, 1})_{i\in I_1} , \dots,  \mathbf v_l=(v_{i, l})_{i\in I_l} $ and a second layer weight vector 
$\mathbf w=(w_1,\dots w_l)$. Let us write  $\mathbf V:=\mathbf W^{(1)} := (\mathbf v_1,\dots\mathbf v_l)$.
The first formula of Lemma \ref{depth-m-kernel-derivative} then shows that 
the depth-2 kernel 
$k_{\mathbf V,  \mathbf w, \g}$ defined in \eqref{depth-2-kernel} has the $\mathbf w$-parameter derivatives
\begin{align*}
 \frac{\partial }{\partial w_j} k_{\mathbf V,  \mathbf w, \g}(x,x')  
 = -4w_j \g^{-2} \bigl( 1 - k_{\mathbf v_j} (x,x')\bigr) k_{\mathbf V,  \mathbf w, \g}(x,x')  \, .
\end{align*}
Moreover, the second formula of Lemma \ref{depth-m-kernel-derivative} gives
\begin{align*}
 \frac{\partial}{\partial v_{i,j}} k_{\mathbf V,  \mathbf w, \g}(x,x')  
 = 2 \g^{-2} w_j^2
 \frac{\partial }{\partial v_{i,j}}   k_{\mathbf v_j}(x,x') 
 = - 4 v_{i,j}\g^{-2} w_j^2  (x_j-x_j')^2  k_{\mathbf v_j} (x,x')\, .
\end{align*}





% \begin{algorithm}[t]
% \caption{Initialization of weights}
% \label{init-algo}
% \begin{algorithmic}[1]
% {\footnotesize
% \REQUIRE A dataset  $D$, a hierarchical Gaussian kernel $k_{\mathbf W}$ of some depth, $M, N\geq 1$.
%   \hspace*{2.7em} %An algorithm that produces, for all data sets $D\in X^n$,
% \ENSURE  Some initial values for the weights contained in $\mathbf W$. 
% \STATE Split the data set $D$ into three random parts $D_1$, $D_2$, and $D_3$.
% \FORALL{$i=1,\dots,M$}
% 	\STATE Assign random values to the weights in $\mathbf W$.
% 	\STATE Train an SVM $f_{D_1,\lb,\mathbf W}$ of the form \eqref{svm-solution}  
% 	with $k_{\mathbf W,\g}$ on $D_1$ including  grid search for $\lb$ and $\g$.
% 	\STATE Optimize ${\ca R}_{L,D_2}(\lb, \g, \a, \mathbf W)$  with respect to $\mathbf W$
% 		 by simulated annealing with $N$ steps.
% 	\STATE Compute the test error $\Rx L {D_3}{\lb, \g, \a, \mathbf W}$ on $D_3$.
% \ENDFOR
% \STATE \textbf{return} weights $\mathbf W$ that achieved the smallest test error.
% }
% \end{algorithmic}
% \end{algorithm}


% \section{Appendix}


\input{data-table-new.tex}





% % % 
% % % In some additional experiments we investigated 
% % % whether the obtained hierarchical  kernels represent the data 
% % % in a way that is also useful for other learning tasks.
% % % To this end, we first used the optimized hierarchical kernels obtained 
% % % in the previous experiment reported in Table \ref{first-run-table}
% % % to train an SVM on the extra data set part, whenever this part existed, see Table \ref{data-table}.
% % % The resulting SVM, as well as a standard SVM trained on the extra part,
% % % was then tested on the test set. It turned out that these results nicely matches 
% % % those reported in  Table \ref{first-run-table}. For details we refer to Table \ref{val-run-table} in the appendix.
% % % In our last experiment we again took the previously optimised hierarchical kernels,
% % % but this time we used them to train an SVM for a different loss function. 
% % % To be more precise, we used the hinge loss for the binary classification data sets, perfomed 
% % % one-versus-all multiclass classification for the data sets of this type, and 
% % % considered median estimation for the regression data sets. Again, we trained the 
% % % corresponding SVMs on the training set and reported the results on the test
% % % sets, see Table \ref{scene-run-table}.
% % % This time, the results are a bit more mixed in the sense that 
% % % the difference between the different kernels is less pronounced.
% % % In particular, the standard Gaussian kernel was able to match the results 
% % % of the best hierarchical kernel in three cases, see {\sc Bank-marketing, Magic}, and {\sc Pendigits},
% % % and even outperformed them significantly  in one case, namely on {\sc Satimage}. However, 
% % % the hierarchical kernels were still significantly better on 
% % % {\sc Covtype, Higgs, Letter-recognition} and 
% % % {\sc Updrs-motor}. Finally, the adaptive architecture selection ranked first in seven 
% % % out of the nine cases in which it was applicable, and scored only marginally above
% % % the best single architecture in the remaining tow cases.


% % % 
% % % \begin{table}
% % % \begin{center}
% % % {
% % % {\footnotesize
% % % \input{valtrain_experiments.tex}
% % % }
% % % }
% % % \end{center}
% % % \caption{{\small Test errors with respect to the 
% % % classification or $0.5$-pinball loss averaged over the 10 runs together with standard deviations.
% % % The choice of the loss depends on the data 
% % % set type listed in Table \ref{data-table}, see the text for details.
% % % }}
% % % \label{val-run-table}
% % % \end{table}
% % % 
% % % 
% % % 
% % % \begin{table}
% % % \begin{center}
% % % {
% % % {\footnotesize
% % % \input{scenario_experiments.tex}
% % % }
% % % }
% % % \end{center}
% % % \caption{{\small Least squares errors averaged over the 10 runs together with standard deviations
% % % for the SVMs trained on the extra data set part. Again, bold face results correpsond to 
% % % the best performing 
% % % kernels.
% % % }}
% % % \label{scene-run-table}
% % % \end{table}
% % % 
% % % 
% % % 
% % % 
% % % 
% % % 
% % % 
% % % \begin{table}
% % % \begin{center}
% % % {
% % % {\footnotesize
% % % \input{initial_experiments-rerun.tex}
% % % }
% % % }
% % % \end{center}
% % % \caption{{\small This table shows the results for the experiments in Table \ref{first-run-table} with debugged code.
% % % }}
% % % \label{scene-run-table}
% % % \end{table}
% % % 
% % % 
% % % \newpage
% % % 
% % % \begin{table}
% % % \begin{center}
% % % {
% % % {\footnotesize\hspace*{-10ex}
% % % \input{new_experiments.tex}
% % % }
% % % }
% % % \end{center}
% % % \caption{{\small This table shows the results for the experiments in Table \ref{first-run-table} with debugged code.
% % % }}
% % % \label{scene-run-table}
% % % \end{table}
% % % 
% % % 
% % % 
% % % \newpage
% % % 
% % % \begin{table}
% % % \begin{center}
% % % {
% % % % {\footnotesize\hspace*{-10ex}
% % % \input{raw_errors.tex}
% % % % }
% % % }
% % % \end{center}
% % % \caption{{\small Raw errors and rankings
% % % }}
% % % \label{scene-run-table}
% % % \end{table}



data-table-new.tex
\begin{table}
\begin{center}
{
{\footnotesize
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
Data Set &  Size & Dimension. & Type & Training & Testing  &Source\\
\hline
{\sc Bank-Marketing}  &  45211  &  16   &  BC & 7000 & 24212 & UCI \\
\hline
{\sc Cadata}  & 20640   &   8  & REG &  7000 & 6640 & LIBSVM \\
\hline
{\sc Cod-rna}  & 331152   &  8   &  BC & 7000 & 310154 & LIBSVM \\
\hline
{\sc Covtype}  & 581012   & 55    &  BC & 7000& 560014 & UCI \\
\hline
{\sc Cpusmall}  &  8192  &  12   & REG &  6000& 2192 & LIBSVM \\
\hline
{\sc Cycle-Power-Plant}  &  9568  &  4   & REG & 6000 & 3568  & UCI \\
\hline
{\sc Higgs}  &  500000  &  28   &   BC &7000 & 479002 & UCI \\
\hline
{\sc Letter-Recognition}  &  20000  &  16   & MC-26 & 7000& 6000&  UCI   \\
\hline
{\sc Magic}  & 19020   &   10  & BC & 7000 & 5022 & UCI   \\
\hline
{\sc Pendigits}  & 10992   &  16   & MC-10 & 7000 & 3992 & UCI  \\
\hline
{\sc Satimage}  & 6435   &   36  &  MC-6  & 5000 & 1435 & UCI\\
\hline
{\sc Seismic}  &  98528  & 50  & MC-3  & 7000 & 77530 & LIBSVM   \\
\hline
{\sc Shuttle}  &  43500  & 8    & MC-6 & 7000 & 22500 & LIBSVM    \\
\hline
{\sc Thyroid-ann}  & 7200   &  21   &  BC & 5000 & 2001 & UCI \\
\hline
{\sc Updrs-motor}  & 5875   &  19   &  REG & 5000 & 875 & UCI \\
\hline
\end{tabular}
}
}
\end{center}
\caption{{\small Details of the considered datasets and their preparation. All data sets were scaled 
to  $[-1,1]^{d+1}$ or $[0,1]$. For {\sc Shuttle} we additionally removed the first 
data column that contains a time stamp whose influence has been debated in the literature.
The types are binary classification (BC), regression (REG), and multiclass classification with $k$ labels
(MC-$k$). We subsampled training and test sets of the specified size. For the larger datasets we initially
planned some additional experiments, for which a separate data set would have been needed.
This explains the difference between the total size and the sum of the training and test set sizes.
These splits  were 30 times repeated.
}}
\label{data-table}
\end{table}
data-table.tex
\begin{table}
\begin{center}
{
{\footnotesize
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
Data Set &  Size & Dim. & Type & Train. & Extra &Source\\
\hline
{\sc Bank-Marketing}  &  45211  &  16   &  BC & 7000 & 14000 & UCI \\
\hline
{\sc Cadata*}  & 20640   &   8  & REG &  7000 & 7000 & LIBSVM \\
\hline
{\sc Cod-rna}  & 331152   &  8   &  BC & 7000 & 14000& LIBSVM \\
\hline
{\sc Covtype}  & 581012   & 55    &  BC & 7000& 14000& UCI \\
\hline
{\sc Cpusmall}  &  8192  &  12   & REG &  6000& 0 & LIBSVM \\
\hline
{\sc Cycle-Power-Plant}  &  9568  &  4   & REG & 6000 & 0  & UCI \\
\hline
{\sc Higgs*}  &  50000  &  28   &   BC &7000 & 14000 & UCI \\
\hline
{\sc Letter-Recognition}  &  20000  &  16   & MC-26 & 7000& 7000&  UCI   \\
\hline
{\sc Magic}  & 19020   &   10  & BC & 7000 & 7000 & UCI   \\
\hline
{\sc Pendigits}  & 10992   &  16   & MC-10 & 7000 & 0 & UCI  \\
\hline
{\sc Satimage}  & 6435   &   36  &  MC-6  & 5000 & 0 & UCI\\
\hline
{\sc Seismic}  &  98528  & 50  & MC-3  & 7000 & 14000 & LIBSVM   \\
\hline
{\sc Shuttle*}  &  43500  & 8    & MC-6 & 7000 & 14000 & LIBSVM    \\
\hline
{\sc Thyroid-ann}  & 7200   &  21   &  BC & 5000 & 0 & UCI \\
\hline
{\sc Updrs-motor}  & 5875   &  19   &  REG & 5000 & 0 & UCI \\
\hline
\end{tabular}
}
}
\end{center}
\caption{{\small Details of the considered datasets and their preparation. All data sets were scaled 
to either $[-1,1]$ or $[0,1]$. In addition, the ones marked by a $*$ were further modified as follows:
For {\sc Cadata} we scaled the labels by $0.0001$ to report comparable test errors, for {\sc Higgs}
we only considered a subsample of the specified size, and for {\sc Shuttle} we removed the first 
data column that contains a time stamp whose influence has been debated in the literature.
The types are binary classification (BC), regression (REG), and multiclass classification with $x$ labels
(MC-$x$). We subsampled a training set of the specified size, and for the larger data sets an 
additional subset (Extra column). All remaining samples were used for testing. These splits into two 
or three subsets were ten times repeated.
}}
\label{data-table}
\end{table}
experiments.tex


\section{Experiments}\label{sec:experiments}

\begin{table*}[hbtp]
{\small
  \label{raw_error_table}
  \centering  %\footnotesize
\input{raw_errors.tex}}
\caption{Average least squares error and standard deviations 
for the considered algorithms on the 15 data sets. For each dataset,   the smallest 
average error is printed in bold face, and the second best error is printed in italics.
In a few cases, the differences were not statistically significant, so that more than two errors are highlighted.}
\end{table*}

While the greater flexibility of hierarchical Gaussian kernels may reduce the 
approximation error, it may also increase the statistical error, that is, the 
danger of overfitting. In addition, 
it is by no means guaranteed, that the optimization strategy described in Section
\ref{sec:param-optimization} is able to find sufficiently good weights.
For this reason we empirically compare our developed method with some other state-of-the-art
learning algorithms.




\textbf{Algorithms.}
As baseline algorithms we picked random forests (RFs) and SVMs since both algorithms 
are well established and 
scored 
best in the recent comparison \cite{FeCeBaAm14a}. In addition, a comparison of our hierarchical
Gaussian kernels to SVMs seems to be somewhat natural.
For the random forests, we simply used the $R$-package \verb randomForest \
and for the  SVMs we found the recent and fast implementation \cite{Steinwart14b}.
Besides these two algorithms, we also   included the
\verb\hierarchical kernel learning (HKL)\
approach of \cite{Bach08a}
and deep neural networks (DNNs) in form of \verb\Caffe\, see \cite{jia2014caffe}.
Since   we scaled the labels of all our data sets to $[-1, 1]$, we 
clipped the final decision functions obtained by the different algorithms to  $[-1, 1]$, too.
Finally, the weight optimization approaches of our algorithm, namely simulated annealing and gradient descent, were
implemented in C++, where the most time-critical inner parts were  ported to GPU code.
Following a conservative approach, all these parts were using double precision although this 
is likely to slow down the GPU code considerably. For the SVM step of our algorithm, we re-used the 
core solver of \cite{Steinwart14b}.

\textbf{Hyper-Parameter-Selection.}
Except RFs the different algorithms come with different hyper-parameters, which need to be 
carefully determined.
For the baseline SVMs we used the default 5-fold cross validation (CV) procedure of \cite{Steinwart14b},
which determines $\lb$ and $\g$ from a 10 by 10 grid. Similarly, we determined the parameter $\lb$
of HKL by 5-fold CV. For the DNNs we choose the architecture from 
15 different candidate architectures with up to 1000 relu-neurons per layer 
by 5-fold CV combined with early stopping, 
and these candidates were 
 determined by some preliminary 
experiments. For our algorithm we considered  inhomogeneous Gaussian 
kernels as well as six hierarchical Gaussian kernels of depth 2 with 4 to 16  nodes in the first layer,
and the final kernel was again chosen by 5-fold CV.
For the weight optimization in Algorithm   \ref{opt-algo}
we split the training sets  
into three parts $D_1$, $D_2$, and $D_3$ 
of size $44.44\%$, $22.22\%$, and    $33.33\%$, respectively. In 
Algorithm \ref{opt-algo} we set  $L=10$, $M=15$, $N_1=1000$, $N_2=500$, and 
$N_3 = 10$. 

All CVs were solely performed by splitting the training data and whenever this was applicable
 the final decision function was obtained by averaging over the resulting five decision functions.
Finally, we ran some preliminary experiments verifying that the setup for the different
algorithms led to satisfying results. In particular for the HKL package we compared 
the results for the data sets {\sc bank-32nh, bank-32nh, pumadyn-32nh, pumadyn-32nh}
reported in \cite{Bach08a} with our setup for the algorithm and obtained 
in all 4 cases slightly better results.






\begin{figure*}[hbtp]
  \label{error_figures}
  \centering  %\footnotesize
    \includegraphics[height=0.30\textwidth,width=0.30\textwidth]{./images/relaterrors.jpg}
    \hspace*{0.03\textwidth}
    \includegraphics[height=0.30\textwidth,width=0.30\textwidth]{./images/improvements.jpg}
    \hspace*{0.03\textwidth}
    \includegraphics[height=0.30\textwidth,width=0.30\textwidth]{./images/badruns.jpg}
\caption{Left. Relative errors of the different algorithms on the 15 data sets. 
As a baseline, we picked 
SVMs, that is, the relative error of,  say RFs, on a data set is the ratio
error(RF)/error(SVM). The figure shows that SVMs and DNNs performed equally well,
and that our algorithm consistently outperformed SVMs. The latter is not surprising, since
this was the initial intention of our construction. The figure also shows that 
RFs and DNNs have a quite complementary performance: on most data sets on which 
RFs performed better than the SVM, the DNNs did not, and vice versa.
Middle. This graphic compares our algorithm to RFs and DNNs from a different angle.
It shows, for example, that our algorithm achieved a 5\% better average risk
than the other two algorithms on 5 data sets, while RFs and DNNs did so on
3 and 1 data sets, respectively. This graphic therefore illustrates 
the potential gain of using one of the algorithms.
Right. This graphic illustrates the potential risk of solely using 
one of the three algorithms. For example, it shows that 
our algorithm achieved an error that was 10\% worse than the best error 
on 4 data sets, while RFs and DNNs did so on 5 and 9 data sets, respectively.
}
\end{figure*}

\textbf{Data.}
We downloaded 15 data sets from the UCI Machine Learning Repository and
from LIBSVM's web page, where we note that some  data sets can actually be found on both sites.
In all cases, we scaled the input variables $x$ to $[-1,1]^d$ and the label $y$ to $[-1,1]$.
We randomly generated 30 training and test sets from these data sets, where 
the training set size ranged from 5.000 to 7.000 samples.
The details of the considered data sets as well as their preparation are summarized in Table \ref{data-table}
in the appendix.







\textbf{Execution.}
All experiments were repeated 30 times, so that every algorithm was run 450 times.
These runs were distributed among several computers
with different hardware:
The RF- and SVM-experiments were conducted on an ordinary desktop computer,
where each RF run took between 5 and 60 seconds, and an average SVM run took about 60 seconds.
The DNN runs
were conducted on a PC with an i7-3930K  processor, 64GB of RAM and a Titan GPU. Here, the average experiment
ran for about 45 minutes.
The runs for our algorithm were distributed among 4 identical PCs with 
an i7-5820K processor, 64GB of RAM and a GTX980 GPU. On average, a single run took about 81 minutes, 
but some control experiments on the PC with the Titan GPU showed that on that machine 
an average run would have taken around 45 minutes, too. In addition note, that the DNNs were
using single precision while our algorithm was using double precision, which is between 2 to 3 times 
slower on the Titan. 
Finally, the HKL experiments were run on 10 PCs with i7-3770 processor and 16GB of RAM, and 
an average run took about 60 minutes.
Altogether, we used  more than 1.400 hours, or 58.4 days, of processing time, which indicates that 
the experiments would have been infeasible without distributing the tasks among heterogeneous hardware.





\textbf{Results.}
The average least squares error for each algorithm and data set can be found, 
together with some preliminary ranking of the algorithms, 
in Table 1.
A quick look shows that both our method and RFs 
consistently performed well, scoring on 14, respectively  11, 
data sets among the top two, which are typeset in bold face.
Moreover, our algorithm scored first on 6 data sets, while 
RFs scored best on 7.
The algorithm with the next best scoring is DNN, although this impression
is a bit biased since the SVMs were outperformed by our algorithm, as intended,
on every 
single data set, so that the SVMs had never a chance to score first.
A somewhat better comparison between DNNs and SVMs can thus
be found in the left graphic of Figure 2, which shows that 
both algorithms perform quite comparable. Finally, we were quite
surprised by the performance of HKL, which never scored first or second.
Despite this small issue let us finally have a look at a 
slightly finer comparison between RFs, DNNs and our algorithm, which  can be found in Figure 
2, middle and right. 
Here it turns out that the majority of wins for RFs were
only achieved by a small improvement compared to the second best among these three algorithm,
while our algorithm achieves many of its victories with a larger margin.
For example, RFs won  on 3 data sets by more than 5\% improvement, 
DNNs on 1, and our algorithm even  on 5.
In this respect we finally note, that RFs dramatically 
outperformed all other methods on two data sets, namely {\sc shuttle, thyroid},
while our algorithm did so on {\sc updrs}.
Last but not least, the   graphic on the right hand side of Figure 
2 shows on how many data sets each of the three considered algorithms 
lack behind the best algorithm by which percentage. For example, 
RFs are   5\% worse than the best algorithm on 5   data sets, DNNs on 9,
and our algorithm on 4.







fnew_experiments.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}1, S\hspace*{0.2ex}=\hspace*{0.2ex}1\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}1, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}1, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}1, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}1\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}1\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}1\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!0.292 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! & --- & --- & --- & ---&\!\!0.275 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.273 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & --- & ---&\!\!0.280 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.269 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!\textbf{0.266} {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.281 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.277 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.268 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!0.298 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!.0538 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & --- & --- & ---&\!\!.0540 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0538 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & ---&\!\!.0534 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0536 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0533 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0523 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0522} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0525 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! & ---&\!\!.0545 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.144 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! & --- & --- & --- & ---&\!\!0.131 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.135 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! & --- & ---&\!\!0.132 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.133 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.134 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! & ---&\!\!\textbf{0.131} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.134 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.137 {\tiny $\pm$\hspace*{0.2ex}.006}\!\! & ---&\!\!0.158 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.407 {\tiny $\pm$\hspace*{0.2ex}.013}\!\! & --- & --- & --- & ---&\!\!0.416 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!\textbf{0.405} {\tiny $\pm$\hspace*{0.2ex}.015}\!\! & --- & ---&\!\!0.426 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.413 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.411 {\tiny $\pm$\hspace*{0.2ex}.016}\!\! & ---&\!\!0.450 {\tiny $\pm$\hspace*{0.2ex}.021}\!\!&\!\!0.414 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.425 {\tiny $\pm$\hspace*{0.2ex}.021}\!\! & ---&\!\!0.520 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!.0035 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & --- & --- & ---&\!\!\textbf{.0033} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & ---&\!\!.0033 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0033 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0033 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0033 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0036 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!.0103 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & --- & --- & ---&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0102 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & ---&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & ---&\!\!.0102 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{.0100} {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0106 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!0.808 {\tiny $\pm$\hspace*{0.2ex}0.24}\!\! & --- & --- & --- & ---&\!\!0.767 {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!0.749 {\tiny $\pm$\hspace*{0.2ex}0.22}\!\! & --- & ---&\!\!0.786 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\!&\!\!\textbf{0.744} {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!0.750 {\tiny $\pm$\hspace*{0.2ex}0.22}\!\! & ---&\!\!0.795 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\!&\!\!0.769 {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!0.766 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\! & ---&\!\!0.833 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!.0361 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! & --- & --- & --- & ---&\!\!.0354 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0344 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & ---&\!\!.0355 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0343} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0346 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0354 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0343 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0347 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0452 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.396 {\tiny $\pm$\hspace*{0.2ex}.007}\!\! & --- & --- & --- & ---&\!\!0.389 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.395 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & --- & ---&\!\!0.388 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!\textbf{0.386} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.393 {\tiny $\pm$\hspace*{0.2ex}.006}\!\! & ---&\!\!0.387 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.390 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.390 {\tiny $\pm$\hspace*{0.2ex}.007}\!\! & ---&\!\!0.398 {\tiny $\pm$\hspace*{0.2ex}.007}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!.0075 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & --- & --- & ---&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0075 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & --- & ---&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!\textbf{.0071} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0081 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!.0482 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & --- & --- & --- & ---&\!\!.0458 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0455 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & --- & ---&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0456 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{.0449} {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0462 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0458 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!.0482 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.307 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & --- & --- & --- & ---&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! & --- & ---&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{0.298} {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!0.311 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!\textbf{.0041} {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & --- & --- & ---&\!\!.0047 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0044 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & --- & ---&\!\!.0054 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0047 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0045 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0066 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0055 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0051 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0046 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!\textbf{0.153} {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & --- & --- & --- & ---&\!\!0.155 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.160 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & --- & ---&\!\!0.153 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.161 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.163 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.153 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.156 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.173 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0118 {\tiny $\pm$\hspace*{0.2ex}.012}\!\! & --- & --- & --- & ---&\!\!\textbf{.0099} {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0129 {\tiny $\pm$\hspace*{0.2ex}.010}\!\! & --- & ---&\!\!.0319 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!.0184 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!.0176 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!.0361 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0146 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0107 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! & ---&\!\!.0530 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline 
\end{tabular}


hierarchical-illustration.tex
\begin{figure}[th]
\centering
\def\layersep{3.5cm}
\begin{tikzpicture}[shorten >=1pt,->,draw=black!50, node distance=\layersep,
scale=0.7, every node/.style={transform shape}]
\tikzstyle{every pin edge}=[<-,shorten <=1pt]

\tikzstyle{node}=[rectangle,draw=black!25,minimum size=17pt,inner sep=3pt]
\tikzstyle{input dim}=[node, circle]%, fill=green!50]
\tikzstyle{final layer}=[node]%, fill=red!50]
\tikzstyle{first layer}=[node]%, fill=blue!50]
\tikzstyle{second layer}=[node]%, fill=blue!50]
\tikzstyle{col1}=[red]
\tikzstyle{col2}=[blue]
\tikzstyle{col3}=[green]

\newcommand{\myedgeIF}[3]{\draw[col#2] (I-#1.east) -- (F-#2-#3.west) ;}
\newcommand{\myedgeIFt}[3]{\draw[col#2] (I-#1.east) -- (F-#2-#3.west) node[near start,black,anchor=south]{$\big(\mathbf W^{(1)}_{#2}\big)_{#1,#3}$} ;}
\newcommand{\myedgeIFb}[3]{\draw[col#2] (I-#1) -- (F-#2-#3) node[midway,black,anchor=north]{$\big(\mathbf W^{(1)}_{#2}\big)_{#1,#3}$} ;}
\newcommand{\myedgeFEt}[1]{\draw (F-2-#1) -- (E-1) node[near start]{$w_{#1}$} ;}
\newcommand{\myedgeFSt}[2]{\draw (F-#1-#2) -- (S-#1) node[near start]{$w^{(2)}_{#1,#2}$} ;}
\newcommand{\myedgeSEt}[1]{\draw (S-#1) -- (E-1) node[near start]{$w_{#1}$} ;}


\begin{scope}[xshift=3*\layersep]
\foreach \name in {1,...,6} \node[input dim] (I-\name) at (0,5-\name) {$x_{\name}$} ;

\foreach \name in {1,...,4} \node[first layer,col1] (F-1-\name) at (\layersep,5.25-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_1\big)_{\name}}$} ;
\foreach \name in {1,...,4} \node[first layer,col2] (F-2-\name) at (\layersep,2-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_2\big)_{\name}}$} ;
%\foreach \name in {1,...,4} \node[first layer,col3] (F-3-\name) at (\layersep,-1.5-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_3\big)_{\name}}$} ;

\foreach \name in {1,...,2} \node[second layer] (S-\name) at (2*\layersep,6-3*\name) {$k_{\mathbf W^{(1)}_\name,\mathbf w^{(2)}_\name}$} ;
\node[final layer] (E-1) at (3*\layersep,1.5) {$k_{\mathbf W^{(1)},\mathbf W^{(2)},\mathbf w}$} ;


\myedgeIF123
\myedgeIFt113

\myedgeIF214
\myedgeIF221
\myedgeIF224

\myedgeIF311
\myedgeIF313
\myedgeIF314

\myedgeIF411
\myedgeIF412
\myedgeIF422

\myedgeIF521
\myedgeIF523
\myedgeIF524

\myedgeIF612
\myedgeIFb623

% \myedgeIF722
% \myedgeIF723
% \myedgeIF724
%
% \myedgeIF814
% \myedgeIF821
% \myedgeIF834
%
% \myedgeIF912
% \myedgeIF932
% \myedgeIFb934



\foreach \i in {1,...,2} \foreach \j in {1,...,4} \myedgeFSt{\i}{\j} ;

\foreach \i in {1,...,2} \myedgeSEt{\i} ;

\begin{scope}[yshift=5cm]
\draw[-,decorate,decoration={brace,amplitude=3pt},thick] (0.5,0) -- (2.5,0) node[black,midway,anchor=south]{$\mathbf W^{(1)}=(\mathbf W^{(1)}_1,\mathbf W^{(1)}_2)$} ;
\draw[-,decorate,decoration={brace,amplitude=3pt},thick] (4.5,0) -- (6,0) node[black,midway,anchor=south]{$\mathbf W^{(2)}=(\mathbf w^{(2)}_1,\mathbf w^{(2)}_2)$} ;
\draw[-,decorate,decoration={brace,amplitude=3pt},thick] (8,0) -- (9.5,0) node[black,midway,anchor=south]{$\mathbf w$} ;
\end{scope}
\end{scope}

\end{tikzpicture}
\caption{Illustration of a possible hierarchical Gaussian kernel of depth 3.}
\end{figure}




% % % % % % % % % \begin{figure}[ht]
% % % % % % % % % \centering
% % % % % % % % % \def\layersep{5cm}
% % % % % % % % % \begin{tikzpicture}[shorten >=1pt,->,draw=black!50, node distance=\layersep,
% % % % % % % % % scale=0.4]
% % % % % % % % % \tikzstyle{every pin edge}=[<-,shorten <=1pt]
% % % % % % % % % \tikzstyle{node}=[rectangle,fill=black!25,minimum size=17pt,inner sep=0pt]
% % % % % % % % % \tikzstyle{input dim}=[node, circle, fill=green!50]
% % % % % % % % % \tikzstyle{final layer}=[node, fill=red!50]
% % % % % % % % % \tikzstyle{first layer}=[node, fill=blue!50]
% % % % % % % % % \tikzstyle{second layer}=[node, fill=blue!50]
% % % % % % % % % 
% % % % % % % % % \newcommand{\myedgeIF}[2]{\draw (I-#1) -- (F-#2) ;}
% % % % % % % % % \newcommand{\myedgeIFt}[2]{\draw (I-#1) -- (F-#2) node[midway]{$v_{#1,#2}$} ;}
% % % % % % % % % \newcommand{\myedgeFEt}[1]{\draw (F-#1) -- (E-1) node[near start]{$w_{#1}$} ;}
% % % % % % % % % \newcommand{\myedgeFSt}[1]{\draw (F-#1) -- (S-1) node[near start]{$w_{#1}$} ;}
% % % % % % % % % \newcommand{\myedgeSEt}[1]{\draw (S-#1) -- (E-1) node[near start]{$w_{#1}$} ;}
% % % % % % % % % 
% % % % % % % % % \foreach \name in {1,...,9} \node[input dim] (I-\name) at (0,-\name) {$x_{\name}$} ;
% % % % % % % % % \foreach \name in {1,...,5} \node[first layer] (F-\name) at (\layersep,1-2*\name) {$k_{\mathbf v_{\name}}$} ;
% % % % % % % % % \node[final layer] (E-1) at (2*\layersep,-5) {$k_{\mathbf W^{(1)},  \mathbf w}$} ; 
% % % % % % % % % 
% % % % % % % % % \draw[-,decorate,decoration={brace,amplitude=3pt},thick] (1,0) -- (4,0) node[black,midway,anchor=south]{$\mathbf W^{(1)}$} ;
% % % % % % % % % \myedgeIFt12
% % % % % % % % % \myedgeIF45
% % % % % % % % % \myedgeIF23
% % % % % % % % % \myedgeIFt32
% % % % % % % % % \myedgeIFt43
% % % % % % % % % \myedgeIF54
% % % % % % % % % \myedgeIF61
% % % % % % % % % \myedgeIF74
% % % % % % % % % \myedgeIF71
% % % % % % % % % \myedgeIFt84
% % % % % % % % % \myedgeIFt95
% % % % % % % % % 
% % % % % % % % % \draw[-,decorate,decoration={brace,amplitude=3pt},thick] (6,0) -- (9,0) node[black,midway,anchor=south]{$\mathbf w$} ;
% % % % % % % % % \foreach \i in {1,...,5} \myedgeFEt{\i} ;
% % % % % % % % % 
% % % % % % % % % \end{tikzpicture}
% % % % % % % % % \caption{Illustration of a hierarchical kernel of depth 2.}
% % % % % % % % % \end{figure}
% % % % % % 
% % % % % % 
% % % % % % \begin{figure}[hb]
% % % % % % \centering
% % % % % % \def\layersep{4cm}
% % % % % % \begin{tikzpicture}[shorten >=1pt,->,draw=black!50, node distance=\layersep,
% % % % % % scale=0.7, every node/.style={transform shape}]
% % % % % % \tikzstyle{every pin edge}=[<-,shorten <=1pt]
% % % % % % 
% % % % % % \tikzstyle{node}=[rectangle,draw=black!25,minimum size=17pt,inner sep=3pt]
% % % % % % \tikzstyle{input dim}=[node, circle]%, fill=green!50]
% % % % % % \tikzstyle{final layer}=[node]%, fill=red!50]
% % % % % % \tikzstyle{first layer}=[node]%, fill=blue!50]
% % % % % % \tikzstyle{second layer}=[node]%, fill=blue!50]
% % % % % % \tikzstyle{col1}=[red]
% % % % % % \tikzstyle{col2}=[blue]
% % % % % % \tikzstyle{col3}=[green]
% % % % % % 
% % % % % % \newcommand{\myedgeIF}[3]{\draw[col#2] (I-#1.east) -- (F-#2-#3.west) ;}
% % % % % % \newcommand{\myedgeIFt}[3]{\draw[col#2] (I-#1.east) -- (F-#2-#3.west) node[near start,black,anchor=south]{$\big(\mathbf W^{(1)}_{#2}\big)_{#1,#3}$} ;}
% % % % % % \newcommand{\myedgeIFb}[3]{\draw[col#2] (I-#1) -- (F-#2-#3) node[midway,black,anchor=north]{$\big(\mathbf W^{(1)}_{#2}\big)_{#1,#3}$} ;}
% % % % % % \newcommand{\myedgeFEt}[1]{\draw (F-2-#1) -- (E-1) node[near start]{$w_{#1}$} ;}
% % % % % % \newcommand{\myedgeFSt}[2]{\draw (F-#1-#2) -- (S-#1) node[near start]{$w^{(2)}_{#1,#2}$} ;}
% % % % % % \newcommand{\myedgeSEt}[1]{\draw (S-#1) -- (E-1) node[near start]{$w_{#1}$} ;}
% % % % % % 
% % % % % % 
% % % % % % \begin{scope}[xshift=3*\layersep]
% % % % % % \foreach \name in {1,...,6} \node[input dim] (I-\name) at (0,5-\name) {$x_{\name}$} ;
% % % % % % 
% % % % % % \foreach \name in {1,...,4} \node[first layer,col1] (F-1-\name) at (\layersep,5.25-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_1\big)_{\name}}$} ;
% % % % % % \foreach \name in {1,...,4} \node[first layer,col2] (F-2-\name) at (\layersep,2-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_2\big)_{\name}}$} ;
% % % % % % %\foreach \name in {1,...,4} \node[first layer,col3] (F-3-\name) at (\layersep,-1.5-\name / 1.25) {$k_{\big(\mathbf W^{(1)}_3\big)_{\name}}$} ;
% % % % % % 
% % % % % % \foreach \name in {1,...,2} \node[second layer] (S-\name) at (2*\layersep,6-3*\name) {$k_{\mathbf W^{(1)}_\name,\mathbf w^{(2)}_\name}$} ; 
% % % % % % \node[final layer] (E-1) at (3*\layersep,1.5) {$k_{\mathbf W^{(1)},\mathbf W^{(2)},\mathbf w}$} ; 
% % % % % % 
% % % % % % 
% % % % % % \myedgeIF123
% % % % % % \myedgeIFt113
% % % % % % 
% % % % % % \myedgeIF214
% % % % % % \myedgeIF221
% % % % % % \myedgeIF224
% % % % % % 
% % % % % % \myedgeIF311
% % % % % % \myedgeIF313
% % % % % % \myedgeIF314
% % % % % % 
% % % % % % \myedgeIF411
% % % % % % \myedgeIF412
% % % % % % \myedgeIF422
% % % % % % 
% % % % % % \myedgeIF521
% % % % % % \myedgeIF523
% % % % % % \myedgeIF524
% % % % % % 
% % % % % % \myedgeIF612
% % % % % % \myedgeIFb623
% % % % % % 
% % % % % % % \myedgeIF722
% % % % % % % \myedgeIF723
% % % % % % % \myedgeIF724
% % % % % % % 
% % % % % % % \myedgeIF814
% % % % % % % \myedgeIF821
% % % % % % % \myedgeIF834
% % % % % % % 
% % % % % % % \myedgeIF912
% % % % % % % \myedgeIF932
% % % % % % % \myedgeIFb934
% % % % % % 
% % % % % % 
% % % % % % 
% % % % % % \foreach \i in {1,...,2} \foreach \j in {1,...,4} \myedgeFSt{\i}{\j} ;
% % % % % % 
% % % % % % \foreach \i in {1,...,2} \myedgeSEt{\i} ;
% % % % % % 
% % % % % % \begin{scope}[yshift=4.5cm]
% % % % % % \draw[-,decorate,decoration={brace,amplitude=3pt},thick] (0.5,0) -- (3,0) node[black,midway,anchor=south]{$\mathbf W^{(1)}=(\mathbf W^{(1)}_1,\mathbf W^{(1)}_2)$} ;
% % % % % % \draw[-,decorate,decoration={brace,amplitude=3pt},thick] (5,0) -- (8,0) node[black,midway,anchor=south]{$\mathbf W^{(2)}=(\mathbf w^{(2)}_1,\mathbf w^{(2)}_2)$} ;
% % % % % % \draw[-,decorate,decoration={brace,amplitude=3pt},thick] (9,0) -- (11,0) node[black,midway,anchor=south]{$\mathbf w$} ;
% % % % % % \end{scope}
% % % % % % \end{scope}
% % % % % % 
% % % % % % \end{tikzpicture}
% % % % % % \caption{Illustration of a possible hierarchical Gaussian kernel of depth 3.}
% % % % % % \end{figure}
% % % % % % 
% % % % % % 

hierarchical-kernels.tex
\section{Hierarchical Gaussian Kernels}\label{sec-hier-kernels}


% 
% \todo{\item move proofs out of text \item sort results and presentation \item tell story}



In this section we introduce the central object of this paper, namely hierarchical Gaussian kernels.
Let us begin by recalling some basic facts on kernels from \cite[Chapter 4]{StCh08}.
To this end, let $k:X\times X\to \R$ 
be a function. Then $k$ is a kernel, if there exists a Hilbert space $H$ and a map 
$\P_0:X\to H_0$ such that 
\begin{displaymath}
   k(x,x') = \langle \P_0(x), \P_0(x')\rangle\, , \qquad \qquad x,x'\in X.
\end{displaymath}
In this case, $\P_0$ and $H_0$ are said to be  a feature map and a feature space of $k$, respectively.
It is well known, that every such kernel possesses a unique reproducing kernel Hilbert space (RKHS)  $H$ 
and this RKHS is a feature space of $k$ with respect to the canonical 
feature map $\P:X\to H$ given by $\P(x) := k(x,\cdot)$, $x\in X$. Moreover, by definition $H$ consists
of functions $h:X\to \R$, and if $k$ is continuous, so are the functions in $H$.
Let us now assume that $X$ is a compact metric space and that $k$ is a continuous kernel. 
Then
 $k$ is said to be universal, if its RKHS $H$ is dense in the space $C(X)$ of continuous functions 
$f:X\to \R$ with respect to the supremums norm $\inorm\cdot$.
Furthermore, we say that $k$  is injective, if its canonical feature map is injective.
Recall that universal kernels are injective, see e.g.~\cite[Lemma 4.55]{StCh08}. 
Moreover, the injectivity is actually shared by all feature maps of $k$, see 
Lemma \ref{injective-kernel-char} for details.
In particular, it is easy to see that 
besides universal kernels many other kernels are injective, too. For example, 
the linear kernel $k(x,x') := \langle x,x'\rangle$ on $\R^d$ is injective since one of its 
feature maps is the identity on $\R^d$, which, of course, is injective. Finally, note that 
if $k$ is injective on $X$ then its restriction $k_{|X'\times X'}$ onto some subset $X'\subset X$
is still injective. 


% Moreover, $k$ is said to be characteristic, see \cite{...}, if the embedding 
% \begin{align*}
%    \ca M(X)& \to H \\
% 	P&\mapsto \E_P \P\, ,
% \end{align*}
% where $\ca M(X)$ denotes the set of all Borel probability measures on $X$
% and $\E_P \P$ is the $H$-valued Bocher integral of $\Phi$ with respect to $P$,
% is injective.\fix{Include two references: one for the definition and one for the implication}
% Recall that  it has been shown in \cite{...} that universal kernels are characteristic.


Probably one of the best known universal kernel
 on $X\subset \Rd$ is the standard Gaussian RBF kernel $k_\g$ with width $\g>0$, which is given by
\begin{displaymath}
   k_{\g, X}(x,x') := \exp\bigl( -\g^{-2}\snorm{x-x'}_2^2  \bigr)\, , \qquad \quad x,x'\in X\, ,
\end{displaymath}
where $\snorm\cdot_2$ denotes the standard Euclidean norm on $\Rd$. 
In the following we denote its RKHS by $H_{\g, X}$.
Now, it is well-known 
that this construction
can actually be extended to subsets $Z$ of more general Hilbert spaces $H$, that is, 
\begin{equation}\label{gauss-on-H}
   k_{\g, Z}(z,z') := \exp\bigl( -\g^{-2}\snorm{z-z'}_H^2  \bigr)\, ,  \quad z,z'\in Z  .
\end{equation}
is again a   kernel, whose RKHS will be denoted by $H_{\g, Z}$.
In particular, if we have a map $\P:X\to H$, then 
\begin{equation}\label{hier-prot-kernel}
   k_{\g, X,H}(x,x')  := \exp\bigl( -\g^{-2}\snorm{\P(x)-\P(x')}_H^2  \bigr) %\, , \qquad \qquad x,x'\in X\, ,
\end{equation}
defines a new kernel on $X$, see e.g.~\cite[Lemma 4.3]{StCh08}, and 
 if $\P_{\g,Z}:Z\to H_{\g,Z}$ denotes the
canonical feature map
of $k_{\g,Z}$, then $\P_{\g,Z}\circ \P:X\to H_{\g,Z}$ is a feature map of $k_{\g,X, H}$.
Now, note that these assumptions on $\P$ and $H$ are equivalent to saying that 
$H$ is a feature space of the kernel given by $k(x,x') = \langle \P(x), \P(x')\rangle$, and 
since we have $\snorm{\P(x)-\P(x')}_H^2 = k(x,x)-2k(x,x')+k(x',x')$, we can also express 
\eqref{hier-prot-kernel} by the kernel $k$. In the following, we call kernels  $k_{\g,X,H}$ of the form above 
\emph{hierarchical Gaussian kernels}. For later use we note that 
these kernels are universal if $X$ is a compact metric space and $\P$ is continuous and injective,
see Theorem \ref{hier-proto-kernel-universal} for details.
%  Namely, the following result has essentially  been shown in 
% \cite{ChSt10a}.








Our next goal is to investigate hierarchical Gaussian kernels \eqref{hier-prot-kernel} for which 
$H$ and its kernel $k$ is 
of rather complicated form. To this end, we write, for 
 $x=(x_1,\dots,x_m)\in \R^m$ and $I\subset \{1,\dots,m\}$,
\begin{displaymath}
  x_I:= (x_i)_{i\in I} 
\end{displaymath}
for the vector projected onto the coordinates listed in $I$.
% 
% we consider, for some non-empty 
% $I\subset \{1,\dots,m\}$ and $X\subset \R^m$, the
% coordinate projection $\pi_I: X \to \R^{|I|}$ given by
% \begin{align*}
% 	\pi_I(x_1,\dots,x_m) := (x_i)_{i\in I} \, , \qquad \qquad x\in X.
% \end{align*}
% In the following we often use the more intuitive notation $x_I := \pi_I(x_1,\dots,x_m) = (x_i)_{i\in I}$
% and $X_I := \{x_I: x\in X\}$ for the  image of $\pi_I$. 
Note that if $X$ is compact then the image 
$X_I$ of this projection is also compact since continuous images of compact sets are compact.
Let us now assume that we have non-empty sets $I_1,\dots,I_l\subset  \{1,\dots,m\}$ 
and $X\subset \R^m$, some weights $w_1,\dots,w_l>0$, 
as well kernels $k_i$ on $X_{I_i}$ for all $i=1,\dots,l$.
For  $I:= I_1\cup \cdots\cup I_l$, we then define a new kernel on $X_I$  by
\begin{equation}\label{weighted-kernel}
   k(x,x') := \sum_{i=1}^l w_i^2 k_i\bigl( x_{I_i}, x'_{I_i} \bigr)\, , \qquad   x,x'\in X_I.
\end{equation}
One can show, that  hierarchical Gaussian kernels of the form \eqref{weighted-kernel} can be computed by a simple product formula, 
see Lemma \ref{hier-kernel-product}. The following definition considers iterations of \eqref{weighted-kernel}.
% Our first result, whose proof can be found in the appendix, gives a simple product formula for the resulting hierarchical Gaussian kernel.
% 



% For the proof of this theorem we need the following lemma, which, despite the fact that 
% its assertion is somewhat expected, we could not find in the literature. 






\begin{definition}
 Let $k$ be a kernel of the form \eqref{weighted-kernel} and $H$ be its RKHS. 
 Then the resulting hierarchical Gaussian kernel $k_{\g,X_I,H}$ is said to be of depth
 \begin{enumerate}
  \item  $m= 1$, if all  kernels  $k_1,\dots, k_l$ in  \eqref{weighted-kernel}
  are  linear.
  \item   $m>1$, if all  $k_1,\dots, k_l$ in  \eqref{weighted-kernel}
  are hierarchical Gaussian kernels of depth $m-1$.
%   \item of mixed depth, if every  kernel  $k_1,\dots, k_l$ in  \eqref{weighted-kernel}
%   is a linear kernel, a hierarchical Gaussian kernel of some depth $m_1,\dots, m_l$, or a hierarchical Gaussian kernel of mixed depth.
 \end{enumerate}
\end{definition}






To illustrate the definition above, we note 
that hierarchical kernels of depth 1 are of the form
\begin{equation}\label{depth-1-kernel}
 k_{\mathbf v}(x,x') :=  \exp\bigl(- \sum_{i\in I} v_i^2 (x_i-x_i')^2\bigr) , \quad   x,x'\in X  ,
\end{equation}
for some suitable $\mathbf v:= (v_i)_{i\in I}$ with 
$v_i> 0$ for all $i\in I$. In other words, they only differ from standard Gaussian kernels on $X_I$ by 
their inhomogeneous width parameter $\mathbf v$. For this reason we sometimes also call 
kernels of the form \eqref{depth-1-kernel} \emph{inhomogeneous Gaussian kernels}.


To derive an explicit formula for depth-2-kernels, we fix some $I_1,\dots,I_l\subset \{1,\dots,d\}$, some
first layer weight vectors
$\mathbf v_1=(v_{i, 1})_{i\in I_1} , \dots,  \mathbf v_l=(v_{i, l})_{i\in I_l} $ and a second layer weight vector 
$\mathbf w=(w_1,\dots w_l)$. Writing $\mathbf W^{(1)}:= (\mathbf v_1,\dots\mathbf v_l)$, 
the  hierarchical Gaussian kernel $k_{\mathbf W^{(1)},  \mathbf w, \g}$  of depth 2 that is build 
upon the kernels $k_{\mathbf v_1}, \dots k_{\mathbf v_l}$ and weights $\mathbf w=(w_1,\dots w_l)$ is given by 
\begin{align}\label{depth-2-kernel}
& k_{\mathbf W^{(1)},  \mathbf w, \g}(x,x') \\\nonumber
 &=  \exp\biggl( -2\g^{-2} \sum_{i=1}^l w_i^2 \bigl(1-  k_{\mathbf v_i}( x_{I_i}, x'_{I_i})\bigr)  \biggr) \\ \nonumber
 &= \exp\Biggl( -2\g^{-2} \sum_{i=1}^l w_i^2 \biggl(1-  \exp\Bigl(- \sum_{j\in I_i} v_{j,i}^2 (x_j-x_j')^2\Bigr) \biggr)  \Biggr)\, .
\end{align}
Here we note that  we used the fact that all first layer kernels  $k_{\mathbf v_1},\dots, k_{\mathbf v_l}$
are normalized, that is $k_{\mathbf v_i}(x,x)=1$ for all $x\in X_{I_i}$. Also note that the parameter $\g$ in 
\eqref{depth-2-kernel} can be consumed by the weights $\mathbf w$. In the following, we therefore use the shorthand 
$k_{\mathbf W^{(1)},  \mathbf w} := k_{\mathbf W^{(1)},  \mathbf w, 1}$.
Finally, if 
$k_{\mathbf W^{(1)}_1,  \mathbf w_1^{(2)}}, \dots, k_{\mathbf W^{(1)}_l,  \mathbf w_l^{(2)}}$ are some hierarchical kernels of depth 2,
and 
$\mathbf w=(w_1,\dots w_l)$ is a third layer weight vector, then the corresponding kernel $k$ of depth 3 is given by 
\begin{align}\label{depth-3-kernel}
 &k_{\mathbf W^{(1)}, \mathbf W^{(2)},\mathbf w, \g}(x,x') \\ \nonumber
 &=  \exp\biggl( -2\g^{-2} \sum_{i=1}^l w_i^2 \bigl(1-  k_{\mathbf W^{(1)}_i,  \mathbf w_i^{(2)}}( x_{I_i}, x'_{I_i})\bigr)  \biggr) \, ,
\end{align}
where we used the notation $\mathbf W^{(1)}:= (\mathbf W^{(1)}_1,\dots\mathbf W^{(1)}_l)$ and $\mathbf W^{(2)}:= (\mathbf w_1^{(2)},\dots\mathbf w_l^{(2)})$.
Repeating these calculations, we see that hierarchical kernels of depth $m$ are given by
\begin{align}\label{depth-m-kernel}
\hspace*{-1.5ex}
 &k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g}(x,x') \\\nonumber
 &=  \exp\biggl( -2\g^{-2} \sum_{i=1}^l w_i^2 
 \bigl(1-  k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)}}( x_{I_i}, x'_{I_i})\bigr)  \biggr) \, ,
\end{align}
where  $k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)}}$ denote 
% := k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)},1}$ are 
hierarchical
kernels of depth $m-1$ with $\g=1$. 
Note that because of the recursive definition of hierarchical kernels, 
the number of children kernels $l$ may differ in each parent kernel. 
To be more precise, the kernels $k_{\mathbf W^{(1)}_i,\dots, \mathbf W^{(m-2)}_i,\mathbf w_i^{(m-1)}}$
in \eqref{depth-m-kernel} are  build by $l_i$ many kernels of depth $m-2$, and in general we have both
 $l_i\neq l_j$ and $l_i \neq l$.

\input{hierarchical-illustration}

initial_experiments-rerun.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{.0675} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0721 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0698 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0689 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0699 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0681 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0754 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!31.28 {\tiny $\pm$\hspace*{0.2ex}0.41}\!\!&\!\!29.41 {\tiny $\pm$\hspace*{0.2ex}0.56}\!\!&\!\!\textbf{27.07} {\tiny $\pm$\hspace*{0.2ex}0.46}\!\!&\!\!31.25 {\tiny $\pm$\hspace*{0.2ex}0.89}\!\! & ---&\!\!31.45 {\tiny $\pm$\hspace*{0.2ex}0.93}\!\! & ---&\!\!32.38 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.169 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!\textbf{0.139} {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.152 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!0.178 {\tiny $\pm$\hspace*{0.2ex}.007}\!\! & ---&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.188 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.423 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.416 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!\textbf{0.404} {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!0.424 {\tiny $\pm$\hspace*{0.2ex}.027}\!\!&\!\!0.480 {\tiny $\pm$\hspace*{0.2ex}.020}\!\!&\!\!0.410 {\tiny $\pm$\hspace*{0.2ex}.019}\!\! & ---&\!\!0.527 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!8.745 {\tiny $\pm$\hspace*{0.2ex}0.26}\!\!&\!\!\textbf{8.553} {\tiny $\pm$\hspace*{0.2ex}0.36}\!\!&\!\!8.877 {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!8.701 {\tiny $\pm$\hspace*{0.2ex}0.20}\!\! & ---&\!\!8.600 {\tiny $\pm$\hspace*{0.2ex}0.38}\!\! & ---&\!\!9.263 {\tiny $\pm$\hspace*{0.2ex}0.29}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!\textbf{11.97} {\tiny $\pm$\hspace*{0.2ex}3.33}\!\!&\!\!14.05 {\tiny $\pm$\hspace*{0.2ex}0.78}\!\! & ---&\!\!12.52 {\tiny $\pm$\hspace*{0.2ex}1.61}\!\! & --- & --- & ---&\!\!14.74 {\tiny $\pm$\hspace*{0.2ex}0.50}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!0.819 {\tiny $\pm$\hspace*{0.2ex}.028}\!\!&\!\!\textbf{0.811} {\tiny $\pm$\hspace*{0.2ex}.020}\!\!&\!\!0.845 {\tiny $\pm$\hspace*{0.2ex}.029}\!\!&\!\!0.849 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.848 {\tiny $\pm$\hspace*{0.2ex}.026}\!\!&\!\!0.822 {\tiny $\pm$\hspace*{0.2ex}.033}\!\! & ---&\!\!0.905 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!5.645 {\tiny $\pm$\hspace*{0.2ex}0.32}\!\!&\!\!5.644 {\tiny $\pm$\hspace*{0.2ex}0.40}\!\!&\!\!5.748 {\tiny $\pm$\hspace*{0.2ex}0.27}\!\!&\!\!5.599 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\!&\!\!5.848 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\!&\!\!\textbf{5.583} {\tiny $\pm$\hspace*{0.2ex}0.33}\!\! & ---&\!\!7.158 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!.0993 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0999 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0990 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{.0977} {\tiny $\pm$\hspace*{0.2ex}.002}\!\! & ---&\!\!.0990 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.103 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!0.177 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.214 {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!0.160 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.177 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!\textbf{0.160} {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.160 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!1.840 {\tiny $\pm$\hspace*{0.2ex}1.61}\!\!&\!\!0.827 {\tiny $\pm$\hspace*{0.2ex}.057}\!\!&\!\!\textbf{0.565} {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!2.467 {\tiny $\pm$\hspace*{0.2ex}1.76}\!\!&\!\!0.639 {\tiny $\pm$\hspace*{0.2ex}.056}\!\!&\!\!0.802 {\tiny $\pm$\hspace*{0.2ex}0.11}\!\! & ---&\!\!4.898 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.302 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{0.298} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.303 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! & ---&\!\!0.318 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.0482 {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!\textbf{.0465} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0684 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!.0513 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! & ---&\!\!.0521 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! & ---&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!0.154 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!\textbf{0.153} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.156 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.157 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.155 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! & ---&\!\!0.195 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0193 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!.0339 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0249 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!\textbf{.0070} {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0387 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0112 {\tiny $\pm$\hspace*{0.2ex}.007}\!\! & ---&\!\!.0530 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline 
\end{tabular}


initial_experiments.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{.0694} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0719 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0722 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0699 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0704 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{\textit{.0680}} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0754 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!31.56 {\tiny $\pm$\hspace*{0.2ex}0.40}\!\!&\!\!29.69 {\tiny $\pm$\hspace*{0.2ex}0.46}\!\!&\!\!\textbf{27.33} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!31.41 {\tiny $\pm$\hspace*{0.2ex}0.56}\!\! & ---&\!\!31.58 {\tiny $\pm$\hspace*{0.2ex}0.78}\!\!&\!\!\textbf{\textit{27.33}} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!32.38 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{0.142} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.154 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.142 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.188 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.415 {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!\textbf{0.414} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.426 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.421 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.448 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.432 {\tiny $\pm$\hspace*{0.2ex}.032}\!\!&\!\!\textbf{\textit{0.409}} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!0.527 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!9.015 {\tiny $\pm$\hspace*{0.2ex}0.38}\!\!&\!\!\textbf{8.699} {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!8.750 {\tiny $\pm$\hspace*{0.2ex}0.28}\!\!&\!\!8.814 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!8.889 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!9.263 {\tiny $\pm$\hspace*{0.2ex}0.29}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!14.45 {\tiny $\pm$\hspace*{0.2ex}0.74}\!\!&\!\!14.24 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! & ---&\!\!\textbf{13.92} {\tiny $\pm$\hspace*{0.2ex}0.68}\!\! & --- & --- & ---&\!\!14.74 {\tiny $\pm$\hspace*{0.2ex}0.50}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!\textbf{0.819} {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.833 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.867 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.832 {\tiny $\pm$\hspace*{0.2ex}.035}\!\!&\!\!0.869 {\tiny $\pm$\hspace*{0.2ex}.025}\!\!&\!\!0.859 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!\textbf{\textit{0.810}} {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.905 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!5.880 {\tiny $\pm$\hspace*{0.2ex}0.44}\!\!&\!\!5.864 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!5.879 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!\textbf{5.727} {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.998 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\!&\!\!5.757 {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.755 {\tiny $\pm$\hspace*{0.2ex}0.33}\!\!&\!\!7.158 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.100 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.100 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.100 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.100 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.103 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.203 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!\textbf{0.157} {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!0.164 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.012}\!\! & ---&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!0.914 {\tiny $\pm$\hspace*{0.2ex}0.63}\!\!&\!\!0.910 {\tiny $\pm$\hspace*{0.2ex}0.18}\!\!&\!\!\textbf{0.610} {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.681 {\tiny $\pm$\hspace*{0.2ex}.070}\!\!&\!\!0.639 {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.714 {\tiny $\pm$\hspace*{0.2ex}.042}\!\! & ---&\!\!4.898 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.298} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.303 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.305 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.318 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.0500 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!\textbf{.0460} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0519 {\tiny $\pm$\hspace*{0.2ex}.006}\!\! & ---&\!\!.0521 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0479 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!0.161 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!\textbf{0.158} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.166 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.158 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.165 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.163 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.195 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0301 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0409 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!.0267 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!\textbf{.0217} {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!.0397 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0235 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!.0530 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline 
\end{tabular}


initial_experiments_safe.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{.0694} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0719 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0722 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0699} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0704 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{\textit{.0680}} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0754 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!31.56 {\tiny $\pm$\hspace*{0.2ex}0.40}\!\!&\!\!29.69 {\tiny $\pm$\hspace*{0.2ex}0.46}\!\!&\!\!\textbf{27.33} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!31.41 {\tiny $\pm$\hspace*{0.2ex}0.56}\!\! & ---&\!\!31.58 {\tiny $\pm$\hspace*{0.2ex}0.78}\!\!&\!\!\textbf{\textit{27.33}} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!32.38 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{0.142} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.154 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.142 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.188 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.415 {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!\textbf{0.414} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.426 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.421 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.448 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.432 {\tiny $\pm$\hspace*{0.2ex}.032}\!\!&\!\!\textbf{\textit{0.409}} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!0.527 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!9.015 {\tiny $\pm$\hspace*{0.2ex}0.38}\!\!&\!\!\textbf{8.699} {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!8.750 {\tiny $\pm$\hspace*{0.2ex}0.28}\!\!&\!\!8.814 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!8.889 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!9.263 {\tiny $\pm$\hspace*{0.2ex}0.29}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!14.45 {\tiny $\pm$\hspace*{0.2ex}0.74}\!\!&\!\!14.24 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! & ---&\!\!\textbf{13.92} {\tiny $\pm$\hspace*{0.2ex}0.68}\!\! & --- & --- & ---&\!\!14.74 {\tiny $\pm$\hspace*{0.2ex}0.50}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!\textbf{0.819} {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.833 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.867 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.832 {\tiny $\pm$\hspace*{0.2ex}.035}\!\!&\!\!0.869 {\tiny $\pm$\hspace*{0.2ex}.025}\!\!&\!\!0.859 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!\textbf{\textit{0.810}} {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.905 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!5.880 {\tiny $\pm$\hspace*{0.2ex}0.44}\!\!&\!\!5.864 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!5.879 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!\textbf{5.727} {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.998 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\!&\!\!5.757 {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.755 {\tiny $\pm$\hspace*{0.2ex}0.33}\!\!&\!\!7.158 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{\textit{0.100}} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.103 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.203 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!\textbf{0.157} {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!0.164 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.012}\!\! & ---&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!0.914 {\tiny $\pm$\hspace*{0.2ex}0.63}\!\!&\!\!0.910 {\tiny $\pm$\hspace*{0.2ex}0.18}\!\!&\!\!\textbf{0.610} {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.681 {\tiny $\pm$\hspace*{0.2ex}.070}\!\!&\!\!0.639 {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.714 {\tiny $\pm$\hspace*{0.2ex}.042}\!\! & ---&\!\!4.898 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.298} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.303 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.305 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.318 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.0500 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!\textbf{.0460} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0519 {\tiny $\pm$\hspace*{0.2ex}.006}\!\! & ---&\!\!.0521 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0479 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!0.161 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!\textbf{0.158} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.166 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!\textbf{0.158} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.165 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.163 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.195 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0301 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0409 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!.0267 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!\textbf{.0217} {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!.0397 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0235 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!.0530 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline 
\end{tabular}


intro.tex
\section{Introduction}\label{sec:intro}




Although kernel methods such as support vector machines 
are one of the state-of-the-art methods when it comes to fully 
automated learning, see e.g.~the recent independent comparison
\cite{FeCeBaAm14a}, the recent years have shown that on complex datasets
such as image, speech and video data,
they clearly fall short 
compared to deep neural networks. 

One possible explanation for 
this superior behavior is certainly their deep architecture 
that makes it possible to represent highly complex functions 
with relatively few parameters. In particular, it is possible to 
amplify or suppress certain dimensions or features of the 
input data, or to combine features to new, more abstract features.
Compared to this, standard kernels such as the popular Gaussian 
kernels simply treat every feature equally. In addition, most users of 
kernel machines probably stick to the very few standard kernels, often 
simply because there is in most cases no principled way for 
finding problem specific kernels. In contrast to this, deep neural networks
offer yet another order of freedom to the user by making it easy to 
choose among many different architectures and other design decisions.
This discussion shows that the class of deep neural networks offers
potentially much more functions that may fit well to the problem at hand
than classical kernel methods do. 
Therefore, if the training algorithms are able to find these good hypotheses
while  simultaneously controlling the inherent danger of overfitting (and the user 
picked a good design), 
then the recent success of deep networks does not seem to be so surprising after all.
In particular, this may be an explanation for the types of data mentioned above, for
which an equal and un-preprocessed use of all features may really not be the best idea,
but for which there is also some biological insight suggesting certain building blocks of  neural architectures.
Moreover, the recent success of deep networks indicates that these `ifs' can nowadays much better
be controlled than 20 to 30 years ago.
This naturally raises the question, whether and how certain aspects of deep neural 
networks can be translated into the kernel world without sacrificing the benefits 
of kernel-based learning, namely less `knobs' an unexperienced user
can play with, the danger of getting stuck in poor local minima, a more principled 
statistical understanding, and last but not least, their success in situations in which 
no human expert is in the loop.

Of course, the limitations of using simple single kernels have already been recognized before.
Probably the first attempts in this direction are multiple kernel learning algorithms, see e.g.~\cite{SoRaScSc06a}, which,
in a nutshell,  replace a single kernel by a weighted sum of kernels. The advantage 
of this approach is that finding these weights can again be formulated as a convex objective, while
the disadvantage is the limited gain in expressive power unless the used dictionary 
of kernels is really huge. 
A more recent approach for increasing the expressive power is to construct complex kernels 
from simple ones by composing their feature maps in some form.
Probably the first result in this direction can be found in \cite{ChSa09a}, in which 
the authors described the general setup and considered some particular constructions.
Moreover, this idea was adopted in \cite{StVi13a}, where the authors considered sums of 
kernels in each composition step and established bounds on the Rademacher chaos complexities.
Similarly, \cite{ZhTsHo11a-art} considered such sums in the decomposition step, but they 
mostly restricted their considerations to a single decomposition step, for which they established
a generalization bound based on the pseudo-dimension.
Furthermore, \cite{WiHuSaXi16a-art} 
investigated compositions, in which the initial map is not a kernel feature map, but 
the map induced by a deep network. All these articles also present some experimental
results indicating the benefits of the more expressive kernels. Similarly, \cite{Tang13a}
reports some experiments with a linear SVM as the top layer of a deep network.
Another approach  can be found in 
\cite{mairal:hal-01005489}, where the authors construct 
hierarchical convolutional kernels for image data, and finally 
 \cite{Bach08a} proposed a multiple kernel learning approach, which is also called 
hierarchical kernels. However, besides the name, that paper has  little similarity to our approach.
 

In this paper we  adopt the   idea of iteratively composing weighted sums of kernels 
in each layer. Unlike the papers mentioned above, however, we focus on sums of Gaussian 
kernels composed with Gaussian kernels. Besides an illustrative interpretation of the construction,
which highlights the similarities to deep architectures, we show that the resulting kernels
are universal and that the corresponding SVMs become universally consistent. 
To the best of our knowledge our paper is thus the first that does not only investigate
some statistical properties of   iterated   kernels, but also considers their approximation properties. 
We further describe
a possible kernel parameter optimization algorithm in detail, and last but not least we report
results from extensive experiments comparing our algorithm
against SVMs, random forests, the hierarchical kernel learning (HKL) of \cite{Bach08a}
and deep neural networks. Here it turns out that 
even for rather small compositions our approach consistently outperforms SVMs and HKL.
Moreover, our experiments indicate an advantage over deep neural networks
for which the architecture is automatically determined by cross validation
and they further show that our approach  performs better than random forests.

% 
% even with very moderately sized networks 
% such as one kernel composition of four or eight kernels the standard SVM can consistently be outperformed,
% sometimes with very significant improvements. In addition, we investigate empirically, whether the 
% learned kernel can also be used for other purposes.


The rest of this paper is organized as follows: In Section \ref{sec-hier-kernels}
we introduce our class of kernels and in  Section \ref{sec:analysis} we
present their theoretical analysis. Section \ref{sec:param-optimization}
contains the description of the parameter optimization, and the experiments are reported in 
Section \ref{sec:experiments}. The proofs and some auxiliary theorems can be found in the appendix.

local-macros.tex


\newcommand{\Tkx}[1]{T_{k,#1}}

\newcommand{\Tkp}{\Tkx P}
\newcommand{\Tkq}{\Tkx Q}
\newcommand{\Tkm}{\Tkx \mu}
\newcommand{\Tkn}{\Tkx \nu}

\newcommand{\Ltnk}{L_2^k(\nu)}







\newcommand{\clippt} {{{}^{\textstyle \smallfrown}} \hspace*{-1.5ex} t\hspace*{0.5ex}}
\newcommand{\clipps} {{{}^{\textstyle \smallfrown}} \hspace*{-1.67ex} s\hspace*{0.5ex}}
\newcommand{\clippf} {{{}^{^{\textstyle \smallfrown}}} \hspace*{-2.1ex} f\hspace*{0.5ex}}
\newcommand{\clippfo} {{{}^{^{\textstyle \smallfrown}}} \hspace*{-2.1ex} f}
\newcommand{\clippdot} {{{}^{{\textstyle \smallfrown}}} \,\hspace*{-2.5ex} \,\mycdot\,}
\newcommand{\clippL} {{{}^{^{\textstyle \smallfrown}}} \hspace*{-2ex} L}
\newcommand{\clippF} {{{}^{^{\textstyle \smallfrown}}} \hspace*{-2.4ex} {\cal F}}
\newcommand{\RxcL}[2]{{{\cal R}_{{{{}^{^{\scriptstyle \smallfrown}}} \hspace*{-1.6ex} L,#1}}}(#2)}

\newcommand{\hfc}[1]{{{h}_{{{{}^{^{\scriptstyle \smallfrown}}} \hspace*{-1.8ex} f_#1}}}}
\newcommand{\hfco}{{{h}_{{{{}^{^{\scriptstyle \smallfrown}}} \hspace*{-1.8ex} f}}}}
\newcommand{\hfcoq}{{{h}^2_{{{{}^{^{\scriptstyle \smallfrown}}} \hspace*{-1.8ex} f}}}}

\newcommand{\fOc}{{\clippfo_0}}
\newcommand{\fDc}{{\clippfo_{D}}}
\newcommand{\fTc}{\clippfo_{D,\lb}}
\newcommand{\fTcn}{\clippfo_{D,\lb_n}}
\newcommand{\fTqc}{\clippfo_{D,\lb}^{\,\,(q)}}
\newcommand{\fTcg}{\clippfo_{D,\lb,\g}}
\newcommand{\fTonecg}{\clippfo_{D_1,\lb,\g}}





\newcommand{\fbP}{f_{\bar \P,\lb}}
%\newcommand{\fLPH}{f_{L,\P,\lb,H}}
\newcommand{\fPHl}{f_{\P,\lb,H}}
\newcommand{\fPo}{f_{\P,0}}
\newcommand{\fPx}[1]{f_{\P,#1}}
\newcommand{\fPp}{f_{\P,\lb}^{(p)}}
\newcommand{\fPi}{f_{\P,\lb}^{(\infty)}}
\newcommand{\fDq}{f_{D,\lb}^{(q)}}
\newcommand{\fPii}{f_{\P,\lb}^{_{(\infty)}}}
\newcommand{\fPiig}{f_{\P,\g}^{_{(\infty)}}}
\newcommand{\fPpk}{f_{\P,\kappa}^{(p)}}
\newcommand{\fPik}{f_{\P,\kappa}^{(\infty)}}
\newcommand{\fPix}[1]{f_{\P,#1}^{(\infty)}}
\newcommand{\fPpx}[1]{f_{\P,#1}^{(p)}}
\newcommand{\fPH}{f_{L,\P,H}^{*}}
\newcommand{\fTx}[1]{f_{D,\lb,#1}}
\newcommand{\fTgl}{f_{D,\lb,\g}}
\newcommand{\fDlg}{f_{D,\lb,\g}}
\newcommand{\fTln}{f_{D,\lb_n}}
\newcommand{\fPln}{f_{\P,\lb_n}}
\newcommand{\fDl}{f_{D,\lb}}
\newcommand{\fDln}{f_{D,\lb_n}}
\newcommand{\fbT}{f_{\bar D,\lb}}
\newcommand{\fQ}{f_{\Q,\lb}}
\newcommand{\fD}{{f_{D}}}
\newcommand{\fpb}{{f_{L,\P}^*}}
\newcommand{\fs}{{f^*}}
\newcommand{\fO}{{f_0}}





macros.tex
%----------------Used packages -------------------------


\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{color}
\DeclareSymbolFontAlphabet{\Bbb}{AMSb}


% \usepackage{url}
% \usepackage{graphicx}





%---------------Theorem and friends-------------------------------------------------%



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
% 
% 
% % \theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{assumptionsk}{Assumption K}
\newtheorem*{assumptionsc}{Assumption CK}
\newtheorem*{assumptionsx}{Assumption X}
\newtheorem*{assumptionsks}{Assumption KS}
% 
% \theoremstyle{remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

% \newtheorem*{assumptions}{Standardassumptions}

\newcommand{\atob}[2]{\emph{#1)} $\Rightarrow$ \emph{#2)}.} 
\newcommand{\aeqb}[2]{\emph{#1)} $\Leftrightarrow$ \emph{#2)}.} 
\newcommand{\ada}[1]{\emph{#1).}} 


% \newcommand{\qed}{\hfill\rule{7pt}{7pt}}
% \newenvironment{proof}{\noindent{\bf Proof:}}{\qed\medskip}
\newenvironment{proofof}[1]{\noindent{\bf Proof of #1:}}{\qed\medskip}

%-------------tools----------------------------------

\newlength{\fixboxwidth}
\setlength{\fixboxwidth}{\marginparwidth}
\addtolength{\fixboxwidth}{\myleftmargin}
\newcommand{\fix}[1]{\marginpar{%
    \fbox{\parbox{\fixboxwidth}{\tiny #1}}}}


\definecolor{darkgreen}{rgb}{0,0.6,0}
\newcommand{\done}[1]{\newline\textcolor{darkgreen}{#1}}
\newcommand{\idea}[1]{\newline\textcolor{red}{#1}}
\newcommand{\todo}[1]{\textcolor{red}{\textbf{2'Dos}\begin{itemize} #1 \end{itemize}}}
                                         



%-------------paths-------------------------------


\newcommand{\bibtexpath}{}


%---------------Font switches -------------------------

\newcommand{\ca}[1]{{\cal #1}}


%----------------Formatting-----------------------------


\newcommand{\qspace}{\, , \qquad\qquad}
\newcommand{\qqquad}{\qquad\quad}
\newcommand{\qqqquad}{\qquad\qquad}
\renewcommand{\labelenumi}{\it\roman{enumi})}
\newcommand{\mycdot}{\,\cdot\,}
\newcommand{\Leq}{\,\leq \,}
\newcommand{\Geq}{\,\geq \,}


%------------Fields and friends-------------------------------------------


\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rd}{\mathbb{R}^d}
\newcommand{\Rn}{\mathbb{R}^n}




%------------Expectations and friends-------------------------------------------


\newcommand{\E}{\mathbb{E}}
\DeclareMathOperator{\var}{Var}
\newcommand{\dx}[1]{\hspace*{0.25ex}d\hspace*{-0.15ex}#1}
\newcommand{\dxy}[2]{\dx{#1}(#2)}
\newcommand{\dP}[1]{\dxy P{#1}}
\newcommand{\dQ}[1]{\dxy Q{#1}}
\newcommand{\dm}[1]{\dxy \mu{#1}}
\newcommand{\dn}[1]{\dxy \nu{#1}}


%------------Greeks---------------------------------------------


\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma}
\newcommand{\G}{\Gamma}
\renewcommand{\d}{\delta}
\newcommand{\D}{\Delta}
\newcommand{\e}{\varepsilon}
\newcommand{\eps}{\epsilon}
\newcommand{\z}{\zeta}
\newcommand{\n}{\eta}
\newcommand{\vt}{\vartheta}
\newcommand{\vr}{\varrho}
\renewcommand{\k}{\kappa}
\newcommand{\lb}{\lambda}
\newcommand{\x}{\xi}
\renewcommand{\r}{\rho}
\newcommand{\s}{\sigma}
\newcommand{\vs}{\varsigma}
\renewcommand{\t}{\tau}
\newcommand{\p}{\varphi}
\renewcommand{\P}{\Phi}
\newcommand{\om}{\omega}
\newcommand{\Om}{\Omega}



%---------------Operators--------------------------------------

\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\spann}{span}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\ran}{ran}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\interior}{int}

%-----------------Operations and Relations --------------------------

\newcommand{\symdif}{\vartriangle}




%--------------Functions-----------------------------------

\DeclareMathOperator{\arcoth}{arcoth}
\DeclareMathOperator{\arctanh}{arctanh}
\DeclareMathOperator{\sign}{sign}



%---------------Special Symbols------------------------------

\DeclareMathOperator{\id}{id}
\newcommand{\eins}{\boldsymbol{1}}
\newcommand{\BlackBox}{\rule{1.5ex}{1.5ex}} 



%---------------norms---------------------------------------

\newcommand{\snorm}[1]{\Vert #1 \Vert}
\newcommand{\mnorm}[1]{\bigl\Vert \, #1 \, \bigr\Vert}
\newcommand{\bnorm}[1]{\Bigl\Vert \, #1 \, \Bigr\Vert}
\newcommand{\lnorm}[1]{\biggl\Vert #1 \biggr\Vert}
\newcommand{\hnorm}[1]{\Vert #1 \Vert_{H}}
\newcommand{\inorm}[1]{\Vert #1 \Vert_\infty}


%---------------spaces---------------------------------------

\newcommand{\sLx}[2]{{\ca L_{#1}(#2)}}
\newcommand{\sLo}[1]{\sLx 1 {#1}}
\newcommand{\sLt}[1]{\sLx 2 {#1}}
\newcommand{\sLtn}{\sLx 2 \nu}


\newcommand{\Lx}[2]{{L_{#1}(#2)}}
\newcommand{\Lt}[1]{\Lx 2 {#1}}
\newcommand{\Ltp}{\Lx 2 P}
\newcommand{\Ltq}{\Lx 2 Q}
\newcommand{\Ltm}{\Lx 2 \mu}
\newcommand{\Ltn}{\Lx 2 \nu}



%---------------Risks and friends---------------------------------------

\newcommand{\RP}[2]{{{\cal R}_{#1,P}(#2)}}
\newcommand{\RPB}[1]{{{\cal R}_{#1,P}^{*}}}
\newcommand{\RD}[2]{{{\cal R}_{#1,D}(#2)}}
\newcommand{\RDn}[1]{{{\cal R}_{L,D_n}(#1)}}
\newcommand{\RPxB}[2]{{{\cal R}_{#1,P,#2}^*}}
\newcommand{\Rx}[3]{{{\cal R}_{#1,#2}(#3)}}
\newcommand{\RxB}[2]{{{\cal R}^*_{#1,#2}}}

%---------------Losses---------------------------------------

\newcommand{\lclass}{{{L}_{\mathrm{class}}}}
\newcommand{\lhinge}{{{L}_{\mathrm{hinge}}}}
\newcommand{\ldld}{{{L}_{\mathrm{DLD}}}}
\newcommand{\ldldb}{{{\bar L}_{\mathrm{DLD}}}}
\newcommand{\ldldbq}{{{\bar L}_{\mathrm{DLD},Q}}}





%---------------diagrams---------------------------------------


\newcommand{\seqdia}[7]{
\setlength{\unitlength}{1ex}
\begin{picture}(70,10)
\put(-4,4){\makebox(9,2)[rt]{$#1$}}
\put(17,4){\makebox(9,2)[rt]{$#2$}}
\put(40,4){\makebox(9,2)[lt]{$#3$}}
\put(61,4){\makebox(9,2)[lt]{$#4$}}
\put(6,5){\vector(1,0){12}}
\put(27,5){\vector(1,0){12}}
\put(60,5){\vector(-1,0){12}}
\put(9,6){\makebox(6,2){$#5$}}
\put(30,6){\makebox(6,2){$#6$}}
\put(52,6){\makebox(6,2){$#7$}}
\end{picture}}



\newcommand{\tridia}[6]{
\setlength{\unitlength}{1ex}
\begin{picture}(60,20)
\put(20,14){\makebox(9,2)[rt]{$#1$}}
\put(51,14){\makebox(9,2)[lt]{$#2$}}
\put(35.5,2){\makebox(9,2){$#3$}}
\put(30,15){\vector(1,0){20}}
\put(30,14){\vector(1,-1){9}}
\put(41,5){\vector(1,1){9}}
\put(37,16){\makebox(6,2){$#4$}}
\put(27.5,8){\makebox(6,2)[rt]{$#5$}}
\put(47.5,8){\makebox(6,2)[lt]{$#6$}}
\end{picture}}


\newcommand{\quadiasn}[8]{
\setlength{\unitlength}{1ex}
\begin{picture}(60,20)
\put(20,15){\makebox(9,2)[rt]{$#1$}}
\put(45,15){\makebox(9,2)[lt]{$#2$}}
\put(20,2){\makebox(9,2)[rt]{$#3$}}
\put(45,2){\makebox(9,2)[lt]{$#4$}}
\put(30,16){\vector(1,0){14}}
\put(28,14){\vector(0,-1){9}}
\put(46,5){\vector(0,1){9}}
\put(30,3){\vector(1,0){14}}
\put(34,17){\makebox(6,2){$#5$}}
\put(21,8.5){\makebox(6,2)[rt]{$#6$}}
\put(47,8.5){\makebox(6,2)[lt]{$#7$}}
\put(34,0){\makebox(6,2){$#8$}}
\end{picture}}



\newcommand{\quadiass}[8]{
\setlength{\unitlength}{1ex}
\begin{picture}(60,20)
\put(20,15){\makebox(9,2)[rt]{$#1$}}
\put(45,15){\makebox(9,2)[lt]{$#2$}}
\put(20,2){\makebox(9,2)[rt]{$#3$}}
\put(45,2){\makebox(9,2)[lt]{$#4$}}
\put(30,16){\vector(1,0){14}}
\put(25,14){\vector(0,-1){9}}
\put(49,14){\vector(0,-1){9}}
\put(30,3){\vector(1,0){14}}
\put(34,17){\makebox(6,2){$#5$}}
\put(18,8.5){\makebox(6,2)[rt]{$#6$}}
\put(50,8.5){\makebox(6,2)[lt]{$#7$}}
\put(34,0){\makebox(6,2){$#8$}}
\end{picture}}


\newcommand{\quadiann}[8]{
\setlength{\unitlength}{1ex}
\begin{picture}(60,20)
\put(20,15){\makebox(9,2)[rt]{$#1$}}
\put(45,15){\makebox(9,2)[lt]{$#2$}}
\put(20,2){\makebox(9,2)[rt]{$#3$}}
\put(45,2){\makebox(9,2)[lt]{$#4$}}
\put(30,16){\vector(1,0){14}}
\put(25,5){\vector(0,1){9}}
\put(49,5){\vector(0,1){9}}
\put(30,3){\vector(1,0){14}}
\put(34,17){\makebox(6,2){$#5$}}
\put(18,8.5){\makebox(6,2)[rt]{$#6$}}
\put(50,8.5){\makebox(6,2)[lt]{$#7$}}
\put(34,0){\makebox(6,2){$#8$}}
\end{picture}}

master.tex
\documentclass[]{article} 
% \usepackage[]{aistats2017}

% If your paper is accepted, change the options for the package
% aistats2017 as follows:
%
%\usepackage[accepted]{aistats2017}
%
% This option will print headings for the title of your paper and
% headings for the authors names, plus a copyright note at the end of
% the first column of the first page.

%%%%%%%%%%%%%%%%%%%%%%%%%   From nips paper   %%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing} 
% \usepackage{natbib}
\usepackage[numbers]{natbib} 
\usepackage{algorithmic}
\usepackage{algorithm}
%\usepackage{xr}
%\externaldocument{supplement}

\renewcommand{\labelenumi}{\it\roman{enumi})}

\newlength{\myleftmargin}
\setlength{\myleftmargin}{-5ex}
\input{macros}
\input{local-macros}

\evensidemargin .2in
\oddsidemargin  .2in
\setlength\topmargin{-0.75in}
\setlength\textheight{9.25in}
\setlength\textwidth{6.15in}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




% If your paper is accepted and the title of your paper is very long,
% the style will print as headings an error message. Use the following
% command to supply a shorter title of your paper so that it can be
% used as headings.
%
%\runningtitle{I use this title instead because the last one was very long}

% If your paper is accepted and the number of authors is large, the
% style will print as headings an error message. Use the following
% command to supply a shorter version of the authors names so that
% they can be used as headings (for example, use only the surnames)
%
%\runningauthor{Surname 1, Surname 2, Surname 3, ...., Surname n}



\title{Learning with Hierarchical Gaussian Kernels}

% \ifnum\statePaper=0
% \aistatsauthor{ Anonymous Author 1 \And Anonymous Author 2 \And Anonymous Author 3 }
% 
% \aistatsaddress{ Unknown Institution 1 \And Unknown Institution 2 \And Unknown Institution 3 }
% \else
% 
% \aistatsauthor{ Ingo Steinwart \And Nico Schmid \And Philipp Thomann}
% 
% \aistatsaddress{ University of Stuttgart \And University of Stuttgart \And Robert Bosch GmbH  \And University of Stuttgart }
% \fi ]



\author{
  Ingo Steinwart \\ %% \thanks{}
  Institut für Stochastik und Anwendungen\\
  Universität Stuttgart \\
  Pfaffenwaldring 57, 70569 Stuttgart \\
  \texttt{ingo.steinwart@mathematik.uni-stuttgart.de}\\
  \and
  Philipp Thomann \\
  Institut für Stochastik und Anwendungen\\
  Universität Stuttgart \\
  Pfaffenwaldring 57, 70569 Stuttgart \\
  \texttt{philipp.thomann@mathematik.uni-stuttgart.de}\\
  \and
  Nico Schmid \\
  Bosch Healthcare Solutions \\
   \texttt{Nico.Schmid2@de.bosch.com}
}


\begin{document}

\maketitle



\begin{abstract}
We investigate iterated compositions of weighted sums of Gaussian kernels and provide an
interpretation of the construction that shows some similarities with the architectures of  deep neural networks.
On the theoretical side, we show that these kernels are universal and that SVMs using these 
kernels are universally consistent. We further describe a parameter optimization method 
for the kernel parameters and empirically compare this method to SVMs, random forests, a multiple kernel learning
approach, and to some deep neural networks.
\end{abstract}

\input{intro}

\input{hierarchical-kernels}

\input{analysis}

\input{param-opt}

\input{experiments}



\bibliographystyle{plain}
\bibliography{steinwart-books,steinwart-proc,steinwart-article,steinwart-mine,additional}


\clearpage

% \onecolumn
\input{appendix}
% 
% 
% \input{introduction}
% 
% \section{The local SVM approach}
% \input{locSVM}
% 
% \section{Oracle inequality and learning rates for local SVMs with hinge loss}
% \label{sec.theory}
% \input{theory}
% 
% \input{toy}
% 
% \input{experiments}


%\section{Conclusion}


% \ifnum\statePaper=1
% \subsubsection*{Acknowledgments}
% 
% We thank the Institute of Mathematics at the University of Zurich
% for the computational resources.
% \fi

% \clearpage

%It is permissible to reduce the font
%size to \verb+small+ (9 point) when listing the references. {\bf
%  Remember that you can use a ninth page as long as it contains
%  \emph{only} cited references.}
%\medskip

% \small
% 
% %\bibliographystyle{IEEEtran}
% \bibliographystyle{plain}
% 
% \small
% 
% \bibliography{bib/additional,bib/steinwart-books,bib/steinwart-proc,bib/steinwart-article,bib/steinwart-mine,bib/christmann}
% 
% 
% \iftrue %false
% \clearpage
% \onecolumn
% \appendix
% 
% \section{Proofs}
% \input{theory_proof}
% \section{Appendix}
% \input{theory_appendix}
% 
% 
% \section{More detailed results}
% 
% \section{More References on SVMs}
% \input{more_references}
% 
% \fi
\end{document}














% % % % % % % % % % % \documentclass[twoside]{article} \usepackage[]{aistats2017}
% % % % % % % % % % % 
% % % % % % % % % % % % If your paper is accepted, change the options for the package
% % % % % % % % % % % % aistats2017 as follows:
% % % % % % % % % % % %
% % % % % % % % % % % %\usepackage[accepted]{aistats2017}
% % % % % % % % % % % %
% % % % % % % % % % % % This option will print headings for the title of your paper and
% % % % % % % % % % % % headings for the authors names, plus a copyright note at the end of
% % % % % % % % % % % % the first column of the first page.
% % % % % % % % % % % 
% % % % % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%   From nips paper   %%%%%%%%%%%%%%%%%%%%%%%%%
% % % % % % % % % % % \usepackage[utf8]{inputenc} % allow utf-8 input
% % % % % % % % % % % \usepackage[T1]{fontenc}    % use 8-bit T1 fonts
% % % % % % % % % % % \usepackage{hyperref}       % hyperlinks
% % % % % % % % % % % \usepackage{url}            % simple URL typesetting
% % % % % % % % % % % \usepackage{booktabs}       % professional-quality tables
% % % % % % % % % % % \usepackage{amsfonts}       % blackboard math symbols
% % % % % % % % % % % \usepackage{nicefrac}       % compact symbols for 1/2, etc.
% % % % % % % % % % % \usepackage{microtype}      % microtypography
% % % % % % % % % % % \usepackage{tikz}
% % % % % % % % % % % \usetikzlibrary{decorations.pathreplacing} 
% % % % % % % % % % % \usepackage{algorithmic}
% % % % % % % % % % % \usepackage{algorithm}
% % % % % % % % % % % 
% % % % % % % % % % % \usepackage{natbib}
% % % % % % % % % % % %\usepackage{xr}
% % % % % % % % % % % %\externaldocument{supplement}
% % % % % % % % % % % 
% % % % % % % % % % % \renewcommand{\labelenumi}{\it\roman{enumi})}
% % % % % % % % % % % 
% % % % % % % % % % % \newlength{\myleftmargin}
% % % % % % % % % % % \setlength{\myleftmargin}{-5ex}
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % %\input{ingrid/macros}
% % % % % % % % % % % \input{macros}
% % % % % % % % % % % \input{local-macros}
% % % % % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % \begin{document}
% % % % % % % % % % % 
% % % % % % % % % % % % If your paper is accepted and the title of your paper is very long,
% % % % % % % % % % % % the style will print as headings an error message. Use the following
% % % % % % % % % % % % command to supply a shorter title of your paper so that it can be
% % % % % % % % % % % % used as headings.
% % % % % % % % % % % %
% % % % % % % % % % % %\runningtitle{I use this title instead because the last one was very long}
% % % % % % % % % % % 
% % % % % % % % % % % % If your paper is accepted and the number of authors is large, the
% % % % % % % % % % % % style will print as headings an error message. Use the following
% % % % % % % % % % % % command to supply a shorter version of the authors names so that
% % % % % % % % % % % % they can be used as headings (for example, use only the surnames)
% % % % % % % % % % % %
% % % % % % % % % % % %\runningauthor{Surname 1, Surname 2, Surname 3, ...., Surname n}
% % % % % % % % % % % 
% % % % % % % % % % % \twocolumn[
% % % % % % % % % % % 
% % % % % % % % % % % \aistatstitle{Learning with Hierarchical Kernels}
% % % % % % % % % % % 
% % % % % % % % % % % \ifnum\statePaper=0
% % % % % % % % % % % \aistatsauthor{ Anonymous Author 1 \And Anonymous Author 2 \And Anonymous Author 3 }
% % % % % % % % % % % 
% % % % % % % % % % % \aistatsaddress{ Unknown Institution 1 \And Unknown Institution 2 \And Unknown Institution 3 }
% % % % % % % % % % % \else
% % % % % % % % % % % 
% % % % % % % % % % % \aistatsauthor{ Philipp Thomann \And Ingo Steinwart \And Ingrid Blaschzyk \And Mona Meister }
% % % % % % % % % % % 
% % % % % % % % % % % \aistatsaddress{ Univeristy of Stuttgart \And University of Stuttgart \And University of Stuttgart \And Robert Bosch GmbH }
% % % % % % % % % % % \fi ]
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % % % % % % % % % % \iffalse
% % % % % % % % % % % \author{
% % % % % % % % % % %   Philipp Thomann \\
% % % % % % % % % % %   Institut für Stochastik und Anwendungen\\
% % % % % % % % % % %   Universität Stuttgart \\
% % % % % % % % % % %   Pfaffenwaldring 57, 70569 Stuttgart \\
% % % % % % % % % % %   \texttt{philipp.thomann@mathematik.uni-stuttgart.de}\\
% % % % % % % % % % %   \And
% % % % % % % % % % %   Ingo Steinwart \\ %% \thanks{}
% % % % % % % % % % %   Institut für Stochastik und Anwendungen\\
% % % % % % % % % % %   Universität Stuttgart \\
% % % % % % % % % % %   Pfaffenwaldring 57, 70569 Stuttgart \\
% % % % % % % % % % %   \texttt{ingo.steinwart@mathematik.uni-stuttgart.de}
% % % % % % % % % % %   %% examples of more authors
% % % % % % % % % % %   \And
% % % % % % % % % % %   Ingrid Blaschzyk \\
% % % % % % % % % % %   Institut für Stochastik und Anwendungen\\
% % % % % % % % % % %   Universität Stuttgart \\
% % % % % % % % % % %   Pfaffenwaldring 57, 70569 Stuttgart \\
% % % % % % % % % % %   \texttt{ingrid.blaschzyk@mathematik.uni-stuttgart.de}\\
% % % % % % % % % % %   \And
% % % % % % % % % % %   Mona Meister \\
% % % % % % % % % % %   Robert Bosch GmbH \\
% % % % % % % % % % %   70442 Stuttgart \\
% % % % % % % % % % %   \texttt{mona.meister@de.bosch.com}\\
% % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % %   %% Address \\
% % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % %   %% \AND
% % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % %   %% Address \\
% % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % %   %% \And
% % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % %   %% Address \\
% % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % %   %% \And
% % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % %   %% Address \\
% % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % % }
% % % % % % % % % % % 
% % % % % % % % % % % \fi
% % % % % % % % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % % \title{Learning with Hierarchical Kernels}
% % % % % % % % % % % 
% % % % % % % % % % % % The \author macro works with any number of authors. There are two
% % % % % % % % % % % % commands used to separate the names and addresses of multiple
% % % % % % % % % % % % authors: \And and \AND.
% % % % % % % % % % % %
% % % % % % % % % % % % Using \And between authors leaves it to LaTeX to determine where to
% % % % % % % % % % % % break the lines. Using \AND forces a line break at that point. So,
% % % % % % % % % % % % if LaTeX puts 3 of 4 authors names on the first line, and the last
% % % % % % % % % % % % on the second line, try using \AND instead of \And before the third
% % % % % % % % % % % % author name.
% % % % % % % % % % % 
% % % % % % % % % % % % \author{
% % % % % % % % % % % %   David S.~Hippocampus\thanks{Use footnote for providing further
% % % % % % % % % % % %     information about author (webpage, alternative
% % % % % % % % % % % %     address)---\emph{not} for acknowledging funding agencies.} \\
% % % % % % % % % % % %   Department of Computer Science\\
% % % % % % % % % % % %   Cranberry-Lemon University\\
% % % % % % % % % % % %   Pittsburgh, PA 15213 \\
% % % % % % % % % % % %   \texttt{hippo@cs.cranberry-lemon.edu} \\
% % % % % % % % % % % %   %% examples of more authors
% % % % % % % % % % % %   %% \And
% % % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % % %   %% Address \\
% % % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % % %   %% \AND
% % % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % % %   %% Address \\
% % % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % % %   %% \And
% % % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % % %   %% Address \\
% % % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % % %   %% \And
% % % % % % % % % % % %   %% Coauthor \\
% % % % % % % % % % % %   %% Affiliation \\
% % % % % % % % % % % %   %% Address \\
% % % % % % % % % % % %   %% \texttt{email} \\
% % % % % % % % % % % % }
% % % % % % % % % % % 
% % % % % % % % % % % \begin{document}
% % % % % % % % % % % % \nipsfinalcopy is no longer used
% % % % % % % % % % % 
% % % % % % % % % % % \maketitle
% % % % % % % % % % % 
% % % % % % % % % % % \begin{abstract}
% % % % % % % % % % % We investigate iterated compositions of weighted sums of Gaussian kernels and provide an
% % % % % % % % % % % interpretation of the construction that shows some similarities with deep architectures. 
% % % % % % % % % % % On the theoretical side, we show that these kernels are universal and that SVMs using these 
% % % % % % % % % % % kernels are universally consistent. We also describe a parameter optimization method and 
% % % % % % % % % % % validate it empirically by comparing some  architectures of the resulting kernels.
% % % % % % % % % % % \end{abstract}
% % % % % % % % % % % 
% % % % % % % % % % % \input{intro}
% % % % % % % % % % % 
% % % % % % % % % % % \input{hierarchical-kernels}
% % % % % % % % % % % 
% % % % % % % % % % % \input{analysis}
% % % % % % % % % % % 
% % % % % % % % % % % \input{param-opt}
% % % % % % % % % % % 
% % % % % % % % % % % \input{experiments}
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % \bibliographystyle{plain}
% % % % % % % % % % % \bibliography{steinwart-books,steinwart-proc,steinwart-article,steinwart-mine,./additional}
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % \newpage
% % % % % % % % % % % 
% % % % % % % % % % % 
% % % % % % % % % % % \input{appendix}
% % % % % % % % % % % 
% % % % % % % % % % % \end{document}

new_experiments.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}1, S\hspace*{0.2ex}=\hspace*{0.2ex}1\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}6\!\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!0.290 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.274 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!0.272 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.276 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.269 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!\textbf{0.266} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.280 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.277 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.267 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.298 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!.0531 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0533 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0531 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0528 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0529 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0526 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0518 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0516} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0518 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0538 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.144 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.132 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.134 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.131 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.132 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.133 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!\textbf{0.130} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.134 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.135 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!0.157 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.417 {\tiny $\pm$\hspace*{0.2ex}.017}\!\!&\!\!0.421 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!\textbf{0.406} {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.424 {\tiny $\pm$\hspace*{0.2ex}.021}\!\!&\!\!0.419 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!0.416 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.445 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.418 {\tiny $\pm$\hspace*{0.2ex}.026}\!\!&\!\!0.426 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!0.521 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!.0036 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{.0033} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0036 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!.0102 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0100 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0099 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0100 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0100 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0101 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{.0099} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0105 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!0.883 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.822 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!0.808 {\tiny $\pm$\hspace*{0.2ex}.021}\!\!&\!\!0.845 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!\textbf{0.804} {\tiny $\pm$\hspace*{0.2ex}.020}\!\!&\!\!0.812 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!0.856 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.824 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.830 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.902 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!.0359 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0348 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0340 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0354 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0339} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0342 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0352 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0343 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0344 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0451 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.399 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.391 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.396 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.390 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!\textbf{0.389} {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.395 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.389 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.393 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.393 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.401 {\tiny $\pm$\hspace*{0.2ex}.008}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!.0075 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0072 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0073 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0071 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0071 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0071 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0070} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0071 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0071 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0079 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!.0490 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0465 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0463 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0476 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0464 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{.0458} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0478 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0470 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0465 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0488 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.308 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.299} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.311 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!\textbf{.0041} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0046 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0042 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0054 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0046 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0044 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0066 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0055 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0049 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0046 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!\textbf{0.155} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.158 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.162 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.156 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.162 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.164 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.156 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.162 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.175 {\tiny $\pm$\hspace*{0.2ex}.008}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0126 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!\textbf{.0099} {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!.0136 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!.0333 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!.0172 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!.0174 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!.0346 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0153 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!.0112 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0537 {\tiny $\pm$\hspace*{0.2ex}.005}\!\! \\
\hline 
\end{tabular}


param-opt.tex
\section{Parameter Optimization}\label{sec:param-optimization}


For the standard Gaussian kernels it is well-known both empirically and theoretically
that
the learning performance of the resulting SVM heavily depends on the chosen width parameter $\g$.
Clearly, we can expect a similar dependence on the weight parameters 
${\mathbf W}$ for hierarchical Gaussian kernels, but for these parameters, finding good values 
is a potentially more difficult problem. In this section we address this 
issue by presenting an optimization strategy, which in the next section is empirically validated.



In the following let $D=((x_1,y_1),\dots,(x_n,y_n))$ and $D'=((x'_1,y'_1),\dots,(x'_{n'},y'_{n'}))$ be two data sets. 
Let us assume that $D$ is used for training, that is, $D$ is used to find an SVM decision function
\begin{equation}\label{svm-solution}
 f_{D,\lb,\mathbf W, \g} = \sum_{i=1}^n \a_i k_{\mathbf W, \g}(x_i, \mycdot)\, ,
\end{equation}
where $\mathbf W$ denotes the collection of weights of a hierarchical Gaussian kernel of fixed architecture.
Let us further assume that $D'$ is used to validate the quality of the weights $\mathbf W$, that is,
the empirical risk
\begin{equation}\label{validation-risk}
\Rx L {D'}{f_{D,\lb,\mathbf W, \g}} = \frac 1 {n'} \sum_{j=1}^{n'} L\bigl(y_j',  f_{D,\lb,\mathbf W,\g}(x_j')\bigr)  
\end{equation}
is computed. Clearly, by minimizing this validation risk, we may hope to find a suitable collection of weights $\mathbf W$.
 Note however, that 
 if we change the weights $\mathbf W$ of the kernel $k_{\mathbf W,\g}$ 
 to decrease the validation risk \eqref{validation-risk}, then
 the right-hand side of \eqref{svm-solution} is no longer the SVM solution with respect to the new kernel 
 $k_{\mathbf W,\g}$. Therefore, a recomputation of  $\a:=(\a_1,\dots\a_n)$ becomes necessary, and the same may be true for the 
  hyper-parameters $\lb$ and $\g$. The overall objective is therefore threefold: \emph{a)}
  for fixed $\lb,\g,\a$ we wish to minimize 
 \begin{align}\label{opt-problem}
  &{\ca R}_{L,D'}(\lb, \g, \a, \mathbf W) \\\nonumber
  &\qquad :=   \frac 1 {n'} \sum_{j=1}^{n'} L\biggl(y_j',  \sum_{i=1}^n \a_i  k_{\mathbf W,\g}(x_i, x_j')\biggr) 
 \end{align}
 with respect to $\mathbf W$; \emph{b)} we need to determine $\a$ 
 for fixed $\lb$, $\g$, and $\mathbf W$ by solving the SVM optimization problem \eqref{svm-opt-problem};
 and \emph{c)} we need to update the hyper-parameters $\lb$ and $\g$. 
 Clearly, \emph{b)} is nowadays standard, and for \emph{c)} the most widely adopted approach is grid search based on 
 cross validation. 
%  Finding goods weights $\mathbf W$ for \eqref{opt-problem}, 
%  however, has not been considered, yet, so that 
%  new techniques need to be developed. 
 Unfortunately, however, there is no hope that the objective function \eqref{opt-problem} is 
convex in $\mathbf W$, so that minimizing it is   a challenge. In addition, brute-force methods such as  
 grid search over all combinations of weights are far too expensive.  However, finding the `right' weights for learning
 may be a smaller problem compared to, e.g., neural networks, since even for non-optimal weights the corresponding SVM is consistent
 if we split the learning process into two independent phases in which we first look for weights on one (small) chunk of the 
 data and then retrain an SVM with these weights on another (larger) chunk of the data, see 
  Theorem \ref{consistency-result}. In this sense, our task therefore reduces to finding 'good' weights that promise to
  expedite 
 the learning process. 
 
 
To find such good weights,  we will now present a combination of a local minimizer, namely gradient descent,
 and a global minimization heuristic, namely simulated annealing, but certainly, other approaches such as 
 stochastic gradient descent and its modifications, which are popular for training deep neural networks, may
 be serious alternatives that should be investigated in the future.
 In addition, one could, at least in principle, combine the three objectives \emph{a)}-\emph{c)} into one by a simple summation.
 However, this would change the SVM objective function so that we loose both the well-founded statistical
 theory for SVMs and the ability to use off-the-shelf solvers for \eqref{svm-opt-problem}. For this reason,
 we decided to ignore this possibility. 
 The goal of the remainder of this section is to 
 describe the two optimization  
 strategies for $\mathbf W$ and how they were combined with the steps \emph{b)} and \emph{c)}.
 
 
 Let us begin by describing some details of  gradient descent for \eqref{opt-problem}. To this end, let $w$ be a weight 
 contained in $\mathbf W$. If the loss $L$ is differentiable in its second argument, then a simple application of 
 the chain rule shows that 
  the partial derivative of \eqref{opt-problem} with respect to $w$ is given by
 \begin{align*}
 & \frac{\partial}{\partial w}  {\ca R}_{L,D'}(\lb, \g, \a, \mathbf W)\\
%   \frac{\partial}{\partial w}  \Rx L {D'}{f_{D,\lb,\mathbf W}} 
%   &= \frac 1 {n'} \sum_{j=1}^{n'} L'\bigl(y_j',  f_{D,\lb,\mathbf W}(x_i')\bigr) \frac{\partial}{\partial w} f_{D,\lb,\mathbf W}(x_j')  \\
  &= \frac 1 {n'} \sum_{j=1}^{n'}  L'\biggl(y_j', \sum_{i=1}^n \a_i  k_{\mathbf W,\g}(x_i, x_j')\biggr)  \sum_{i=1}^n \a_i   \frac{\partial}{\partial w} k_{\mathbf W, \g}(x_i, x_j')  \, ,
 \end{align*}
where $L'$ denotes the derivative of $L$ in its second argument. To implement gradient descent we consequently need to know the 
partial derivatives $ \frac{\partial}{\partial w} k_{\mathbf W,\g}$, which are recursively computed in the following lemma for which the proof and an example can be found in the 
appendix.




\begin{lemma}\label{depth-m-kernel-derivative}
  Let $k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g}$ be a 
  hierarchical Gaussian kernel of depth $m$ 
  of the form \eqref{depth-m-kernel} and $H$ be its RKHS. 
 Then the parameter derivatives of the highest layer can be computed by
 \begin{align*}
 &  \frac{\partial }{\partial w_j}k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g} \\   %(x,x') 
 & \qquad  = -4\g^{-2}  w_j  \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}\bigr) \\  %  ( x_{I_j}, x'_{I_j})\bigr)
 &\qquad \quad\cdot   k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g}\, . %(x,x') \, , \qquad\qquad x,x'\in X.
 \end{align*}
 Moreover, the parameter derivative of a weight $w$ occurring in a lower layer of the $j$-th node 
%  of lower layers $n<m$ 
 can be computed  by recursively  using the formula 
 \begin{align*}
  & \frac{\partial }{\partial w}k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g} \\  %(x,x') 
%    = -4w_j \g^{-2} \bigl(1-  k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}\bigr)
  &\qquad = 2\g^{-2} w_j^2
 \frac{\partial }{\partial w}   k_{\mathbf W^{(1)}_j,\dots, \mathbf W^{(m-2)}_j,\mathbf w_j^{(m-1)}}\, . %( x_{I_j}, x'_{I_j})
   %  ( x_{I_j}, x'_{I_j})\bigr)
%    k_{\mathbf W^{(1)},\dots, \mathbf W^{(m-1)},\mathbf w, \g}\, . %(x,x') \, , \qquad\qquad x,x'\in X.
 \end{align*}
\end{lemma}


%
%
%To illustrate the previous lemma we note that the parameter 
%derivatives of hierarchical Gaussians $k_{\mathbf v}$ of depth 1, that is, of kernels of 
%the form \eqref{depth-1-kernel}, are given by 
%\begin{displaymath}
% \frac{\partial }{\partial v_j} k_{\mathbf v} (x,x') 
% =  -2v_j (x_j-x_j')^2  k_{\mathbf v} (x,x') \, , \qquad \qquad x,x'\in X\, .
%\end{displaymath}
%To derive an explicit formula for depth-2-kernels we fix 
%some
%first layer weight vectors
%$\mathbf v_1=(v_{i, 1})_{i\in I_1} , \dots,  \mathbf v_l=(v_{i, l})_{i\in I_l} $ and a second layer weight vector 
%$\mathbf w=(w_1,\dots w_l)$. Let us write  $\mathbf V:=\mathbf W^{(1)} := (\mathbf v_1,\dots\mathbf v_l)$.
%The first formula of Lemma \ref{depth-m-kernel-derivative} then shows that 
%the depth-2 kernel 
%$k_{\mathbf V,  \mathbf w, \g}$ defined in \eqref{depth-2-kernel} has the $\mathbf w$-parameter derivatives
%\begin{align*}
% \frac{\partial }{\partial w_j} k_{\mathbf V,  \mathbf w, \g}(x,x')  
% = -4w_j \g^{-2} \bigl( 1 - k_{\mathbf v_j} (x,x')\bigr) k_{\mathbf V,  \mathbf w, \g}(x,x')  \, .
%\end{align*}
%Moreover, the second formula of Lemma \ref{depth-m-kernel-derivative} gives
%\begin{align*}
% \frac{\partial}{\partial v_{i,j}} k_{\mathbf V,  \mathbf w, \g}(x,x')  
% = 2 \g^{-2} w_j^2
% \frac{\partial }{\partial v_{i,j}}   k_{\mathbf v_j}(x,x') 
% = - 4 v_{i,j}\g^{-2} w_j^2  (x_j-x_j')^2  k_{\mathbf v_j} (x,x')\, .
%\end{align*}

With the help of the formulas for the partial derivatives the gradient descent step at iteration $i$ now becomes 
\begin{displaymath}
 \mathbf W_{i+1} = \mathbf W_{i} - \eta \nabla \Rx L {D'}{\lb, \g, \a, \mathbf W_i}\, , 
\end{displaymath}
where the gradient $\nabla \Rx L {D'}{\lb, \g, \a, \mathbf W_i}$ is   the vector of partial derivatives and
$\eta$ is the step size. Although the step size is often simply a function of $i$, we 
decided to be more conservative, namely, we determined $\eta$
by a line search based on the Armijo–Goldstein condition, see e.g.~\cite[Chapter 3.5]{BoGiLeSa06}.
This choice ensures that we will find a local minimum, but on the other hand, it certainly
hinders a 
wider inspection of the parameter space. Like for neural networks less conservative approaches
may thus turn out to be more efficient in the future.


% 
% As we have already mentioned above, the objective function \eqref{opt-problem}
% is non-convex, so that gradient descent methods only find local minima. 
In this paper we decided to
 address the danger of getting stuck in a poor local minimum of the non-convex objective function \eqref{opt-problem} by
 simulated annealing, see \cite[Chapter 10.12]{PrTeVeFl07}. 
In iteration $i$ of
 our adaptation of this  meta-heuristic 
we randomly picked 
one weight $w$ from the current weights
$\mathbf W_i$, changed it randomly to obtain $\mathbf W_{i+1}$, 
and then kept the change if either 
an improvement of the objective function \eqref{opt-problem} was obtained, that is 
$\D := \Rx L {D'}{\lb, \g, \a, \mathbf W_{i+1}} - \Rx L {D'}{\lb, \g, \a,\mathbf W_i} < 0$, or a
uniformly generated  random number $r_{i+1}\in [0,1]$ satisfied
\begin{displaymath}
 r_{i+1} <
 0.5 \exp\Bigl(- \frac {100 i}{\sqrt N} 
%  \cdot \frac{\Rx L {D'}{\lb, \g, \a, \mathbf W_{i+1}}- \Rx L {D'}{\lb, \g, \a,\mathbf W_i}}{\Rx L {D'}{\lb, \g, \a,\mathbf W_i}}  \Bigr)\, .
 \cdot \frac{\D}{\Rx L {D'}{\lb, \g, \a,\mathbf W_i}}  \Bigr)\, .
\end{displaymath}
Here $N$ denotes the total number of iterations.




\begin{algorithm}[t]
\caption{Optimization of weights}
\label{opt-algo}
\begin{algorithmic}[1]
{\footnotesize
\REQUIRE A dataset $D$,  a hierarchical Gaussian kernel $k_{\mathbf W}$ of some depth, $L,M, N_1,N_2, N_3\geq 1$.
%   \hspace*{2.7em} %An algorithm that produces, for all data sets $D\in X^n$,
\ENSURE  Some good values for the weights contained in $\mathbf W$. 
\STATE Split the data set $D$ into three random parts $D_1$, $D_2$, and $D_3$.
\FORALL{$i=1,\dots,M$}
	\STATE Train an SVM $f_{D_1,\lb,\mathbf W}$ of the form \eqref{svm-solution}  
	with $k_{\mathbf W,\g}$ on $D_1$ including  grid search for $\lb$ and $\g$.
          \STATE Optimize $\Rx L {D_2}{\lb, \g, \a, \mathbf W}$ with respect to $\mathbf W$
               by simulated annealing with $N_1$ steps.
	\FORALL{$j=1,\dots,L$}
          \IF {Achieved local minimum of $\Rx L {D_2}{\lb, \g, \a, \mathbf W}$ in previous iteration}
          \STATE Optimize $\Rx L {D_2}{\lb, \g, \a, \mathbf W}$ with respect to $\mathbf W$
               by simulated annealing with $N_2$ steps
          \ELSE
          \STATE Optimize $\Rx L {D_2}{\lb, \g, \a, \mathbf W}$  with respect to $\mathbf W$
              by  gradient descent  with $N_3$ steps.
          \ENDIF
          \STATE Compute the test error $\Rx L {D_3}{\lb, \g, \a, \mathbf W}$ and store $\mathbf W$ if this  error is smaller than the previous one.
	\ENDFOR
	\IF {Test error did not decrease in the loop above}
          \STATE Reshuffle $D_1, D_2$ by splitting $D_1\cup D_2$ into two new parts $D_1$ and $D_2$.
         \ENDIF
\ENDFOR
\STATE \textbf{return} weights $\mathbf W$ that achieved the smallest test error.
}
\end{algorithmic}
\end{algorithm}



In the design of the overall optimization algorithm we again followed a very conservative approach, which 
focuses on reducing  the risk of overfitting. Namely, we split the data set into three parts, from  which the 
first two parts were used to find the SVM decision functions and the objective function \eqref{opt-problem}.
The third part was solely used to track a test error for $\mathbf W$.  The final 
weight $\mathbf W$ was then chosen according to the minimal test error. The corresponding 
algorithm can be found in Algorithm \ref{opt-algo}.
% In addition, we added an initialization phase before Algorithm \ref{opt-algo}
% in which some random start values for $\mathbf W$ 
% were tested. The details can be found in  Algorithm \ref{init-algo} in the appendix.




 

raw_errors.tex
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
Data Set & SVM & HKL & Ours & RF & DNN \\
\hline
\!\!{\sc bank}\!\!&\!\!.29780 {\small $\pm$\hspace*{0.2ex}.00240}\!\!&\!\!.29387 {\small $\pm$\hspace*{0.2ex}.00283}\!\!&\!\!\textbf{.25959} {\small $\pm$\hspace*{0.2ex}.00388}\!\!&\!\!\textbf{\textit{.26868}} {\small $\pm$\hspace*{0.2ex}.00269}\!\!&\!\!.29310 {\small $\pm$\hspace*{0.2ex}.00247}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!.05382 {\small $\pm$\hspace*{0.2ex}.00156}\!\!&\!\!.06247 {\small $\pm$\hspace*{0.2ex}.00138}\!\!&\!\!\textbf{\textit{.05252}} {\small $\pm$\hspace*{0.2ex}.00186}\!\!&\!\!\textbf{.05087} {\small $\pm$\hspace*{0.2ex}.00153}\!\!&\!\!.05500 {\small $\pm$\hspace*{0.2ex}.00146}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!.15745 {\small $\pm$\hspace*{0.2ex}.00234}\!\!&\!\!.17336 {\small $\pm$\hspace*{0.2ex}.00126}\!\!&\!\!\textbf{\textit{.13093}} {\small $\pm$\hspace*{0.2ex}.00498}\!\!&\!\!.17248 {\small $\pm$\hspace*{0.2ex}.00198}\!\!&\!\!\textbf{.11544} {\small $\pm$\hspace*{0.2ex}.00131}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!.52055 {\small $\pm$\hspace*{0.2ex}.00433}\!\!&\!\!.60997 {\small $\pm$\hspace*{0.2ex}.00418}\!\!&\!\!\textbf{.39955} {\small $\pm$\hspace*{0.2ex}.01484}\!\!&\!\!\textbf{\textit{.48784}} {\small $\pm$\hspace*{0.2ex}.00412}\!\!&\!\!.50274 {\small $\pm$\hspace*{0.2ex}.00629}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!.00361 {\small $\pm$\hspace*{0.2ex}.00022}\!\!&\!\!.00460 {\small $\pm$\hspace*{0.2ex}.00041}\!\!&\!\!\textbf{\textit{.00335}} {\small $\pm$\hspace*{0.2ex}.00018}\!\!&\!\!\textbf{.00323} {\small $\pm$\hspace*{0.2ex}.00016}\!\!&\!\!.00375 {\small $\pm$\hspace*{0.2ex}.00015}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!.01048 {\small $\pm$\hspace*{0.2ex}.00035}\!\!&\!\!.01215 {\small $\pm$\hspace*{0.2ex}.00032}\!\!&\!\!\textbf{\textit{.00984}} {\small $\pm$\hspace*{0.2ex}.00047}\!\!&\!\!\textbf{.00838} {\small $\pm$\hspace*{0.2ex}.00031}\!\!&\!\!.01208 {\small $\pm$\hspace*{0.2ex}.00035}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!.90208 {\small $\pm$\hspace*{0.2ex}.00169}\!\!&\!\!.81782 {\small $\pm$\hspace*{0.2ex}.00739}\!\!&\!\!\textbf{\textit{.80235}} {\small $\pm$\hspace*{0.2ex}.01746}\!\!&\!\!\textbf{.77696} {\small $\pm$\hspace*{0.2ex}.00237}\!\!&\!\!.91619 {\small $\pm$\hspace*{0.2ex}.00237}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!\textbf{\textit{.04508}} {\small $\pm$\hspace*{0.2ex}.00149}\!\!&\!\!.11505 {\small $\pm$\hspace*{0.2ex}.00176}\!\!&\!\!\textbf{.03394} {\small $\pm$\hspace*{0.2ex}.00136}\!\!&\!\!.05770 {\small $\pm$\hspace*{0.2ex}.00154}\!\!&\!\!\textbf{\textit{.04484}} {\small $\pm$\hspace*{0.2ex}.00185}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!.40070 {\small $\pm$\hspace*{0.2ex}.00828}\!\!&\!\!.42824 {\small $\pm$\hspace*{0.2ex}.00819}\!\!&\!\!.38999 {\small $\pm$\hspace*{0.2ex}.00930}\!\!&\!\!\textbf{.37719} {\small $\pm$\hspace*{0.2ex}.00787}\!\!&\!\!\textbf{.37829} {\small $\pm$\hspace*{0.2ex}.00846}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!\textbf{\textit{.00793}} {\small $\pm$\hspace*{0.2ex}.00075}\!\!&\!\!.02433 {\small $\pm$\hspace*{0.2ex}.00125}\!\!&\!\!\textbf{.00705} {\small $\pm$\hspace*{0.2ex}.00069}\!\!&\!\!.01266 {\small $\pm$\hspace*{0.2ex}.00121}\!\!&\!\!\textbf{\textit{.00789}} {\small $\pm$\hspace*{0.2ex}.00097}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!\textbf{\textit{.04883}} {\small $\pm$\hspace*{0.2ex}.00289}\!\!&\!\!.10783 {\small $\pm$\hspace*{0.2ex}.00588}\!\!&\!\!\textbf{.04670} {\small $\pm$\hspace*{0.2ex}.00300}\!\!&\!\!.05246 {\small $\pm$\hspace*{0.2ex}.00261}\!\!&\!\!.05247 {\small $\pm$\hspace*{0.2ex}.00334}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!.31134 {\small $\pm$\hspace*{0.2ex}.00132}\!\!&\!\!.31893 {\small $\pm$\hspace*{0.2ex}.00221}\!\!&\!\!\textbf{\textit{.29809}} {\small $\pm$\hspace*{0.2ex}.00160}\!\!&\!\!\textbf{.29555} {\small $\pm$\hspace*{0.2ex}.00121}\!\!&\!\!\textbf{\textit{.29746}} {\small $\pm$\hspace*{0.2ex}.00141}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.00457 {\small $\pm$\hspace*{0.2ex}.00035}\!\!&\!\!.01293 {\small $\pm$\hspace*{0.2ex}.00071}\!\!&\!\!\textbf{\textit{.00422}} {\small $\pm$\hspace*{0.2ex}.00037}\!\!&\!\!\textbf{.00083} {\small $\pm$\hspace*{0.2ex}.00017}\!\!&\!\!.00593 {\small $\pm$\hspace*{0.2ex}.00038}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!.17504 {\small $\pm$\hspace*{0.2ex}.00810}\!\!&\!\!.16368 {\small $\pm$\hspace*{0.2ex}.00832}\!\!&\!\!\textbf{\textit{.15380}} {\small $\pm$\hspace*{0.2ex}.00800}\!\!&\!\!\textbf{.02515} {\small $\pm$\hspace*{0.2ex}.00315}\!\!&\!\!\textbf{\textit{.15216}} {\small $\pm$\hspace*{0.2ex}.00803}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.05372 {\small $\pm$\hspace*{0.2ex}.00517}\!\!&\!\!.17739 {\small $\pm$\hspace*{0.2ex}.00896}\!\!&\!\!\textbf{.00588} {\small $\pm$\hspace*{0.2ex}.00215}\!\!&\!\!\textbf{\textit{.03047}} {\small $\pm$\hspace*{0.2ex}.00160}\!\!&\!\!.05306 {\small $\pm$\hspace*{0.2ex}.00424}\!\! \\
\hline 
\end{tabular}


scenario_experiments.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{\textit{0.117}} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.117} {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!1.845 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!1.787 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!\textbf{1.679} {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!1.846 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!4.809 {\tiny $\pm$\hspace*{0.2ex}9.36}\!\!&\!\!\textbf{\textit{1.679}} {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!1.870 {\tiny $\pm$\hspace*{0.2ex}.015}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!.0393 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0389 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0389 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0383} {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!.0385 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0384 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0395 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!\textbf{0.136} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!0.137 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.142 {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.139 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.151 {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!0.145 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!\textbf{\textit{0.133}} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!1.025 {\tiny $\pm$\hspace*{0.2ex}.022}\!\!&\!\!\textbf{0.995} {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!1.017 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!1.012 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! & ---&\!\!1.013 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!1.030 {\tiny $\pm$\hspace*{0.2ex}.019}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!1.354 {\tiny $\pm$\hspace*{0.2ex}.032}\!\!&\!\!1.321 {\tiny $\pm$\hspace*{0.2ex}.037}\!\! & ---&\!\!\textbf{1.307} {\tiny $\pm$\hspace*{0.2ex}.044}\!\! & --- & --- & ---&\!\!1.365 {\tiny $\pm$\hspace*{0.2ex}.021}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!\textbf{0.318} {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!0.325 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!0.343 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!0.326 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.346 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.341 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!\textbf{\textit{0.313}} {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.370 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!.0461 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0510 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0439 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0458 {\tiny $\pm$\hspace*{0.2ex}.006}\!\!&\!\!.0449 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{.0433} {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0434 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0686 {\tiny $\pm$\hspace*{0.2ex}.013}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{\textit{0.352}} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{0.352} {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!\textbf{.0054} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0078 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0057 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0067 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0063 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0055 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! & ---&\!\!\textbf{.0054} {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!0.171 {\tiny $\pm$\hspace*{0.2ex}0.11}\!\!&\!\!0.186 {\tiny $\pm$\hspace*{0.2ex}.039}\!\!&\!\!0.129 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.139 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.130 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.144 {\tiny $\pm$\hspace*{0.2ex}.020}\!\! & ---&\!\!\textbf{.0949} {\tiny $\pm$\hspace*{0.2ex}.006}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.280 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{0.278} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.281 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.280 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.281 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.282 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{\textit{0.277}} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.286 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!\textbf{.0031} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0034 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0033 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0032 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! & ---&\!\!.0032 {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!\textbf{\textit{.0031}} {\tiny $\pm$\hspace*{0.2ex}.000}\!\!&\!\!.0032 {\tiny $\pm$\hspace*{0.2ex}.000}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!.0428 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0417 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0425 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{.0411} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0421 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0417 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! & ---&\!\!.0453 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0480 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0620 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!.0450 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{.0380} {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!.0600 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!.0398 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! & ---&\!\!.0732 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline 
\end{tabular}


supplement.tex
\documentclass{article}

% if you need to pass options to natbib, use, e.g.:
% \PassOptionsToPackage{numbers, compress}{natbib}
% before loading nips_2016
%
% to avoid loading the natbib package, add option nonatbib:
% \usepackage[nonatbib]{nips_2016}

\usepackage{nips_2016}

% to compile a camera-ready version, add the [final] option, e.g.:
% \usepackage[final]{nips_2016}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing} 
\usepackage{algorithmic}
\usepackage{algorithm}

\renewcommand{\labelenumi}{\it\roman{enumi})}

\newlength{\myleftmargin}
\setlength{\myleftmargin}{-5ex}

\input{macros}
\input{local-macros}


\title{Learning with Hierarchical Kernels, Supplement}

% The \author macro works with any number of authors. There are two
% commands used to separate the names and addresses of multiple
% authors: \And and \AND.
%
% Using \And between authors leaves it to LaTeX to determine where to
% break the lines. Using \AND forces a line break at that point. So,
% if LaTeX puts 3 of 4 authors names on the first line, and the last
% on the second line, try using \AND instead of \And before the third
% author name.

\author{
  David S.~Hippocampus\thanks{Use footnote for providing further
    information about author (webpage, alternative
    address)---\emph{not} for acknowledging funding agencies.} \\
  Department of Computer Science\\
  Cranberry-Lemon University\\
  Pittsburgh, PA 15213 \\
  \texttt{hippo@cs.cranberry-lemon.edu} \\
  %% examples of more authors
  %% \And
  %% Coauthor \\
  %% Affiliation \\
  %% Address \\
  %% \texttt{email} \\
  %% \AND
  %% Coauthor \\
  %% Affiliation \\
  %% Address \\
  %% \texttt{email} \\
  %% \And
  %% Coauthor \\
  %% Affiliation \\
  %% Address \\
  %% \texttt{email} \\
  %% \And
  %% Coauthor \\
  %% Affiliation \\
  %% Address \\
  %% \texttt{email} \\
}

\begin{document}
% \nipsfinalcopy is no longer used

\maketitle



%\input{appendix}

\end{document}

table1.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!N\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& \!best Arch.\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{.0694} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0719 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0722 {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!\textbf{.0699} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0704 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{\textit{.0680}} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!.0754 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!31.56 {\tiny $\pm$\hspace*{0.2ex}0.40}\!\!&\!\!29.69 {\tiny $\pm$\hspace*{0.2ex}0.46}\!\!&\!\!\textbf{27.33} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!31.41 {\tiny $\pm$\hspace*{0.2ex}0.56}\!\! & ---&\!\!31.58 {\tiny $\pm$\hspace*{0.2ex}0.78}\!\!&\!\!\textbf{\textit{27.33}} {\tiny $\pm$\hspace*{0.2ex}0.71}\!\!&\!\!32.38 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{0.142} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.154 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.181 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.142 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!0.188 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!0.415 {\tiny $\pm$\hspace*{0.2ex}.018}\!\!&\!\!\textbf{0.414} {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!0.426 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.421 {\tiny $\pm$\hspace*{0.2ex}.019}\!\!&\!\!0.448 {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.432 {\tiny $\pm$\hspace*{0.2ex}.032}\!\!&\!\!\textbf{\textit{0.409}} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!0.527 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc cpusmall}\!\!&\!\!9.015 {\tiny $\pm$\hspace*{0.2ex}0.38}\!\!&\!\!\textbf{8.699} {\tiny $\pm$\hspace*{0.2ex}0.22}\!\!&\!\!8.750 {\tiny $\pm$\hspace*{0.2ex}0.28}\!\!&\!\!8.814 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!8.889 {\tiny $\pm$\hspace*{0.2ex}0.25}\!\! & ---&\!\!9.263 {\tiny $\pm$\hspace*{0.2ex}0.29}\!\! \\
\hline
\!\!{\sc cycle}\!\!&\!\!14.45 {\tiny $\pm$\hspace*{0.2ex}0.74}\!\!&\!\!14.24 {\tiny $\pm$\hspace*{0.2ex}0.76}\!\! & ---&\!\!\textbf{13.92} {\tiny $\pm$\hspace*{0.2ex}0.68}\!\! & --- & --- & ---&\!\!14.74 {\tiny $\pm$\hspace*{0.2ex}0.50}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!\textbf{0.819} {\tiny $\pm$\hspace*{0.2ex}.023}\!\!&\!\!0.833 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!0.867 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.832 {\tiny $\pm$\hspace*{0.2ex}.035}\!\!&\!\!0.869 {\tiny $\pm$\hspace*{0.2ex}.025}\!\!&\!\!0.859 {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!\textbf{\textit{0.810}} {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.905 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!5.880 {\tiny $\pm$\hspace*{0.2ex}0.44}\!\!&\!\!5.864 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!5.879 {\tiny $\pm$\hspace*{0.2ex}0.45}\!\!&\!\!\textbf{5.727} {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.998 {\tiny $\pm$\hspace*{0.2ex}0.23}\!\!&\!\!5.757 {\tiny $\pm$\hspace*{0.2ex}0.30}\!\!&\!\!5.755 {\tiny $\pm$\hspace*{0.2ex}0.33}\!\!&\!\!7.158 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{\textit{0.100}} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.103 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc pendigits}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.203 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!\textbf{0.157} {\tiny $\pm$\hspace*{0.2ex}.016}\!\!&\!\!0.179 {\tiny $\pm$\hspace*{0.2ex}.014}\!\!&\!\!0.164 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.159 {\tiny $\pm$\hspace*{0.2ex}.012}\!\! & ---&\!\!0.170 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! \\
\hline
\!\!{\sc satimage}\!\!&\!\!0.914 {\tiny $\pm$\hspace*{0.2ex}0.63}\!\!&\!\!0.910 {\tiny $\pm$\hspace*{0.2ex}0.18}\!\!&\!\!\textbf{0.610} {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.681 {\tiny $\pm$\hspace*{0.2ex}.070}\!\!&\!\!0.639 {\tiny $\pm$\hspace*{0.2ex}.045}\!\!&\!\!0.714 {\tiny $\pm$\hspace*{0.2ex}.042}\!\! & ---&\!\!4.898 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.298} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.303 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.304 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.305 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.318 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.0500 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!\textbf{.0460} {\tiny $\pm$\hspace*{0.2ex}.007}\!\!&\!\!.0713 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0519 {\tiny $\pm$\hspace*{0.2ex}.006}\!\! & ---&\!\!.0521 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!.0479 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0471 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc thyroid}\!\!&\!\!0.161 {\tiny $\pm$\hspace*{0.2ex}.010}\!\!&\!\!\textbf{0.158} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.166 {\tiny $\pm$\hspace*{0.2ex}.013}\!\!&\!\!\textbf{0.158} {\tiny $\pm$\hspace*{0.2ex}.009}\!\!&\!\!0.165 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!0.163 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!0.195 {\tiny $\pm$\hspace*{0.2ex}.014}\!\! \\
\hline
\!\!{\sc updrs}\!\!&\!\!.0301 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0409 {\tiny $\pm$\hspace*{0.2ex}.011}\!\!&\!\!.0267 {\tiny $\pm$\hspace*{0.2ex}.005}\!\!&\!\!\textbf{.0217} {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!.0397 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0235 {\tiny $\pm$\hspace*{0.2ex}.011}\!\! & ---&\!\!.0530 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! \\
\hline 
\end{tabular}


valtrain_experiments.tex
\begin{tabular}{|r|r|r|r|r|r|r|r|}
\hline
Data Set &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}4, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}8, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}2\!\! &\!\!l\hspace*{0.2ex}=\hspace*{0.2ex}16, S\hspace*{0.2ex}=\hspace*{0.2ex}4\!\!& Gauss \\
\hline
\!\!{\sc bank}\!\!&\!\!\textbf{.0682} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0706 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0711 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0683 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0702 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0691 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!.0739 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc cadata}\!\!&\!\!31.09 {\tiny $\pm$\hspace*{0.2ex}0.34}\!\!&\!\!29.42 {\tiny $\pm$\hspace*{0.2ex}0.57}\!\!&\!\!\textbf{27.43} {\tiny $\pm$\hspace*{0.2ex}0.69}\!\!&\!\!31.04 {\tiny $\pm$\hspace*{0.2ex}0.49}\!\! & ---&\!\!31.48 {\tiny $\pm$\hspace*{0.2ex}0.94}\!\!&\!\!31.80 {\tiny $\pm$\hspace*{0.2ex}0.68}\!\! \\
\hline
\!\!{\sc cod}\!\!&\!\!0.154 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!\textbf{0.132} {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.141 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.164 {\tiny $\pm$\hspace*{0.2ex}.004}\!\! & ---&\!\!0.167 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.176 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline
\!\!{\sc covtype}\!\!&\!\!\textbf{0.330} {\tiny $\pm$\hspace*{0.2ex}.020}\!\!&\!\!0.332 {\tiny $\pm$\hspace*{0.2ex}.012}\!\!&\!\!0.348 {\tiny $\pm$\hspace*{0.2ex}.033}\!\!&\!\!0.336 {\tiny $\pm$\hspace*{0.2ex}.024}\!\!&\!\!0.385 {\tiny $\pm$\hspace*{0.2ex}.027}\!\!&\!\!0.352 {\tiny $\pm$\hspace*{0.2ex}.036}\!\!&\!\!0.456 {\tiny $\pm$\hspace*{0.2ex}.008}\!\! \\
\hline
\!\!{\sc higgs}\!\!&\!\!\textbf{0.799} {\tiny $\pm$\hspace*{0.2ex}.021}\!\!&\!\!0.816 {\tiny $\pm$\hspace*{0.2ex}.015}\!\!&\!\!0.850 {\tiny $\pm$\hspace*{0.2ex}.025}\!\!&\!\!0.814 {\tiny $\pm$\hspace*{0.2ex}.035}\!\!&\!\!0.853 {\tiny $\pm$\hspace*{0.2ex}.025}\!\!&\!\!0.839 {\tiny $\pm$\hspace*{0.2ex}.017}\!\!&\!\!0.894 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc letter}\!\!&\!\!5.862 {\tiny $\pm$\hspace*{0.2ex}0.27}\!\!&\!\!5.861 {\tiny $\pm$\hspace*{0.2ex}0.33}\!\!&\!\!5.865 {\tiny $\pm$\hspace*{0.2ex}0.19}\!\!&\!\!\textbf{5.731} {\tiny $\pm$\hspace*{0.2ex}0.29}\!\!&\!\!5.983 {\tiny $\pm$\hspace*{0.2ex}0.27}\!\!&\!\!5.756 {\tiny $\pm$\hspace*{0.2ex}0.21}\!\!&\!\!7.096 {\tiny $\pm$\hspace*{0.2ex}0.31}\!\! \\
\hline
\!\!{\sc magic}\!\!&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.100} {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.100 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! & ---&\!\!0.101 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.103 {\tiny $\pm$\hspace*{0.2ex}.002}\!\! \\
\hline
\!\!{\sc seismic}\!\!&\!\!0.297 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!\textbf{0.294} {\tiny $\pm$\hspace*{0.2ex}.001}\!\!&\!\!0.299 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.298 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.300 {\tiny $\pm$\hspace*{0.2ex}.002}\!\!&\!\!0.301 {\tiny $\pm$\hspace*{0.2ex}.003}\!\!&\!\!0.314 {\tiny $\pm$\hspace*{0.2ex}.001}\!\! \\
\hline
\!\!{\sc shuttle}\!\!&\!\!.0455 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!\textbf{.0404} {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0646 {\tiny $\pm$\hspace*{0.2ex}.008}\!\!&\!\!.0486 {\tiny $\pm$\hspace*{0.2ex}.009}\!\! & ---&\!\!.0465 {\tiny $\pm$\hspace*{0.2ex}.004}\!\!&\!\!.0431 {\tiny $\pm$\hspace*{0.2ex}.003}\!\! \\
\hline 
\end{tabular}


master.bbl
\begin{thebibliography}{10}

\bibitem{Bach08a}
F.~R. Bach.
\newblock Exploring large feature spaces with hierarchical multiple kernel
  learning.
\newblock In D.~Koller, D.~Schuurmans, Y.~Bengio, and L.~Bottou, editors, {\em
  Advances in Neural Information Processing Systems 21}, pages 105--112. 2008.

\bibitem{BoGiLeSa06}
J.~F. Bonnans, J.~C. Gilbert, C.~Lemar{\'e}chal, and C.~A. Sagastiz\'{a}bal.
\newblock {\em Numerical Optimization: Theoretical and Practical Aspects}.
\newblock Springer-Verlag, Berlin, 2nd edition, 2006.

\bibitem{ChSa09a}
Y.~Cho and L.K. Saul.
\newblock Kernel methods for deep learning.
\newblock In Y.~Bengio, D.~Schuurmans, J.D. Lafferty, C.K.I. Williams, and
  A.~Culotta, editors, {\em Advances in Neural Information Processing Systems
  22}, pages 342--350. 2009.

\bibitem{ChSt10a}
A.~Christmann and I.~Steinwart.
\newblock Universal kernels on non-standard input spaces.
\newblock In J.~Lafferty, C.~K.~I. Williams, J.~Shawe-Taylor, R.S. Zemel, and
  A.~Culotta, editors, {\em Advances in Neural Information Processing Systems
  23}, pages 406--414, 2010.

\bibitem{CuZh07}
F.~Cucker and D.~X. Zhou.
\newblock {\em Learning Theory: An Approximation Theory Viewpoint}.
\newblock Cambridge University Press, Cambridge, 2007.

\bibitem{EbSt13a}
M.~Eberts and I.~Steinwart.
\newblock Optimal regression rates for {SVM}s using {G}aussian kernels.
\newblock {\em Electron. J. Stat.}, 7:1--42, 2013.

\bibitem{FeCeBaAm14a}
M.~Fern\'{a}ndez-Delgado, E.~Cernadas, S.~Barro, and D.~Amorim.
\newblock Do we need hundreds of classifiers to solve real world classification
  problems?
\newblock {\em J. Mach. Learn. Res.}, 15:3133--3181, 2014.

\bibitem{jia2014caffe}
Y.~Jia, E.~Shelhamer, J.~Donahue, S.~Karayev, J.~Long, R.~Girshick,
  S.~Guadarrama, and T.~Darrell.
\newblock Caffe: Convolutional architecture for fast feature embedding.
\newblock {\em arXiv preprint arXiv:1408.5093}, 2014.

\bibitem{mairal:hal-01005489}
J.~Mairal, P.~Koniusz, Z.~Harchaoui, and C.~Schmid.
\newblock {Convolutional Kernel Networks}.
\newblock In {\em {Advances in Neural Information Processing Systems}}, 2014.

\bibitem{PrTeVeFl07}
W.~H. Press, S.~A. Teukolskyand W.~T. Vetterling, and B.~P. Flannery.
\newblock {\em Numerical Recipes: The Art of Scientific Computing}.
\newblock Cambridge University Press, Cambridge, 3rd edition, 2007.

\bibitem{SmZh03a}
S.~Smale and D.-X. Zhou.
\newblock Estimating the approximation error in learning theory.
\newblock {\em Anal. Appl.}, 1:17--41, 2003.

\bibitem{SoRaScSc06a}
S.~Sonnenburg, G.~R{\"a}tsch, C.~Sch{\"a}fer, and B.~Sch{\"o}lkopf.
\newblock Large scale multiple kernel learning.
\newblock {\em J. Mach. Learn. Res.}, 7:1531--1565, 2006.

\bibitem{Steinwart14b}
I.~Steinwart.
\newblock {A fast SVM toolbox}.
\newblock \url{http://www.isa.uni-stuttgart.de/software/}, January 2016.

\bibitem{StCh08}
I.~Steinwart and A.~Christmann.
\newblock {\em Support Vector Machines}.
\newblock Springer, New York, 2008.

\bibitem{StVi13a}
E.V. Strobl and S.~Visweswaran.
\newblock Deep multiple kernel learning.
\newblock In {\em Machine Learning and Applications (ICMLA), 2013 12th
  International Conference on}, volume~1, pages 414--417, 2013.

\bibitem{Tang13a}
Yichuan Tang.
\newblock Deep learning using support vector machines.
\newblock In {\em ICML 2013 Challenges in Representation Learning Workshop},
  2013.

\bibitem{WiHuSaXi16a-art}
A.G. Wilson, Z.~Hu, R.~Salakhutdinov, and E.P. Xing.
\newblock Deep kernel learning.
\newblock {\em JMLR W\&CP}, 51:370--378, 2016.

\bibitem{ZhTsHo11a-art}
J.~Zhuang, I.W. Tsang, and S.~Hoi.
\newblock Two-layer multiple kernel learning.
\newblock {\em JMLR W\&CP}, 15:909--917, 2011.

\end{thebibliography}
