Optimal Rates for Random Fourier Features
Bharath K.~Sriperumbudur$^*$
Department of Statistics
Pennsylvania State University
University Park
PA 16802
USA
bks18@psu.edu
\input{./parts/section0_abstract
nips2015.tex
\documentclass{article} % For LaTeX2e
\usepackage{nips15submit_e,times,url,hyperref}

%--------------------
%added (Zoltan):
\usepackage{xcolor,amssymb,amsmath,bm,paralist,amsthm,appendix}
\usepackage{enumitem} %customizing list: leftmargin, ...
\usepackage[mathscr]{eucal}
\newcommand{\tb}{\textbf} %bold text
\newcommand{\R}{\mathbb{R}}  %real numbers
\newcommand{\C}{\mathbb{C}}  %complex numbers
\newcommand{\N}{\mathbb{N}}  %natural numbers
\renewcommand{\b}{\mathbf} %bold math
\newcommand{\M}{\mathscr{M}^1_+(\R^d)}%probability measure
\newcommand{\bo}{\bm{\omega}} %bold omega
\renewcommand{\d}{\mathrm{d}}%dx
\newcommand{\p}{\partial}%partial
\newcommand{\E}{\mathbb{E}}  %expectation
\renewcommand{\P}{\mathbb{P}}  %probability
\newcommand{\K}{\mathscr{S}}%compact set
\renewcommand{\S}{\Lambda}%spectral measure
\newcommand{\G}{\mathcal{G}}%function set used in the emp. process formulation
\newcommand{\A}{\mathscr{A}}%sigma-alg.
\newcommand{\Rad}{\mathscr{R}}%Rademacher complexity
\newcommand{\PS}{\mathscr{P}}  %power set
\newcommand{\CN}{\mathcal{N}}  %covering number
\renewcommand{\O}{O} %OrdP(r_n)
\renewcommand{\o}{o} %ordo(r_n)

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}

\usepackage{fancyhdr}
\fancyheadoffset{0pt}

%redefine margin in the supplement (only!; note: it does not modify the margin widths):
\newenvironment{changemargin}[2]{%
  \begin{list}{}{%
    \setlength{\topsep}{0pt}%
    \setlength{\leftmargin}{#1}%
    \setlength{\rightmargin}{#2}%
    \setlength{\listparindent}{\parindent}%
    \setlength{\itemindent}{\parindent}%
    \setlength{\parsep}{\parskip}%
  }%
  \item[]}{\end{list}}

%Bharath:
\newcommand{\bb}{\mathbb} 
\newcommand{\Cal}{\mathcal}
%\usepackage[sort&compress]{natbib}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{appxthm}{Theorem}[section]
\newtheorem{appxlem}[appxthm]{Lemma}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
%--------------------

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\title{Optimal Rates for Random Fourier Features}

\author{
Bharath K.~Sriperumbudur$^*$\\
Department of Statistics\\
Pennsylvania State University\\
University Park, PA 16802, USA\\
\texttt{bks18@psu.edu} \\
\And
Zolt{\'a}n Szab{\'o}\thanks{Contributed equally.}\\
Gatsby Unit, CSML, UCL\\
Sainsbury Wellcome Centre, 25 Howland Street\\
London - W1T 4JG, UK\\
\texttt{zoltan.szabo@gatsby.ucl.ac.uk}
}

\nipsfinalcopy % Uncomment for camera-ready version

\setdefaultleftmargin{2em}{2.2em}{1.87em}{1.7em}{1em}{1em}%paralist doc: default; compactenum/... with small(er) indentification
\usepackage{bibunits}
\begin{document}

\maketitle
\begin{abstract}
\input{./parts/section0_abstract}
\end{abstract}

\begin{bibunit}[plain_with_initials]
\section{Introduction} \label{sec:intro}
\input{./parts/section1_introduction}

\section{Notations \& preliminaries}\label{sec:problem-formulation}
\input{./parts/section2_notations_definitions}

\section{Main results: approximation of $k$}\label{sec:kernel}
\input{./parts/section3_kernel_values}

\section{Approximation of kernel derivatives}\label{sec:kernel-derivatives}
\input{./parts/section4_derivatives_bounded_supp}
\input{./parts/section4_derivatives_unbounded_supp}

\section{Discussion}\label{sec:conclusions}
\input{./parts/section5_conclusions}

\subsubsection*{Acknowledgments}
Z. Szab{\'o} wishes to thank the Gatsby Charitable Foundation for its generous support.

{\small \putbib[./BIB/nips2015_short_conf_names]}
\end{bibunit}

\newpage
\begin{bibunit}[plain_with_initials]
\begin{changemargin}{-2cm}{-2cm}
\appendix
{\Large\tb{Supplement}}
\begin{appendices}\label{appendix}
\numberwithin{equation}{section}
\input{./parts/section6_supplement}
{\small \putbib[./BIB/nips2015_short_conf_names]}
\end{appendices}
\end{changemargin}
\end{bibunit}
\end{document}

section0_abstract.tex
Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives 
due to their capability to represent and model complex relations. While these methods show good versatility, they are computationally intensive and have poor scalability to large data as they require operations on Gram matrices.
In order to mitigate this serious computational limitation, recently randomized constructions have been proposed in the literature, which allow the application of fast linear algorithms.
Random Fourier features (RFF) are among the most popular and widely applied constructions: they provide an easily computable, low-dimensional feature representation for shift-invariant kernels.
Despite the popularity of RFFs, very little is understood theoretically about their approximation quality. In this paper, we provide a detailed finite-sample theoretical analysis about the approximation quality of RFFs 
by (i) establishing optimal (in terms of the RFF dimension, and growing set size) performance guarantees in uniform norm, and (ii) presenting guarantees in $L^r$ ($1\le r<\infty$) norms. 
We also propose an RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.
section1_introduction.tex
Kernel methods \cite{scholkopf02learning} have enjoyed tremendous success in solving several fundamental problems of machine learning ranging from classification, regression, 
feature extraction, dependency estimation, causal discovery, Bayesian inference and hypothesis testing. Such a success owes to their capability to represent and model complex relations
by mapping points into high (possibly infinite) dimensional feature spaces. 
At the heart of all these techniques is the kernel trick, which allows to \emph{implicitly} compute inner products between these high dimensional feature maps, $\lambda$ via
a kernel function $k$: $k(\b{x},\b{y})=\langle\lambda(\b{x}),\lambda(\b{y})\rangle$. However, this flexibility and richness of kernels has a price: by resorting to implicit computations these methods operate on the Gram matrix of the data, which raises serious computational challenges while 
dealing with large-scale data. In order to resolve this bottleneck, numerous solutions have been proposed, such as low-rank matrix approximations \cite{Williams-01,drineas05nystrom,alaoui15fast}, 
explicit feature maps designed for additive kernels \cite{vedaldi12efficient,maji13efficient}, hashing \cite{shi09hash,kulis12kernelized},
and random Fourier features (RFF) \cite{rahimi07random} constructed for shift-invariant kernels, the focus of the current paper.

RFFs implement an extremely simple, yet efficient idea: instead of relying on the implicit feature map $\lambda$ associated with the kernel, by appealing to 
Bochner's theorem \cite{wendland05scattered}---any bounded, continuous, shift-invariant kernel is the Fourier transform of a probability measure----\cite{rahimi07random} proposed 
an explicit low-dimensional random Fourier feature map $\phi$ obtained by empirically approximating the Fourier integral so that $k(\b{x},\b{y})\approx \langle \phi(\b{x}),\phi(\b{y})\rangle$.
The advantage of this explicit low-dimensional feature representation is that the kernel machine can be efficiently solved in the primal form through fast linear solvers, thereby
enabling to handle large-scale data. Through numerical experiments, it has also been demonstrated that kernel algorithms constructed using the approximate kernel
do not suffer from significant performance degradation \cite{rahimi07random}. Another advantage with the RFF approach is that unlike low rank matrix approximation approach \cite{Williams-01,drineas05nystrom} 
which also speeds up kernel machines, it approximates the entire kernel function and not just the kernel matrix. This property is particularly useful while dealing with out-of-sample
data and also in online learning applications. The RFF technique has found wide applicability in several 
areas such as fast function-to-function regression \cite{oliva15fast}, differential privacy preserving \cite{chaudhuri11differentially} and causal discovery \cite{lopezpaz15towards}.

Despite the success of the RFF method, surprisingly, very little is known about its performance guarantees. To the best of our knowledge, the  only paper in the machine learning literature
providing certain theoretical insight into the accuracy of kernel approximation via RFF is \cite{rahimi07random,sutherland15error}:\footnote{\cite{sutherland15error} derived tighter constants compared to \cite{rahimi07random} and also considered different RFF implementations.} it shows that $A_m:=\sup\{|k(\b{x},\b{y})-\langle \phi(\b{x}),\phi(\b{y})\rangle_{\bb{R}^{2m}}|:\b{x},\b{y}\in\K\}=O_p(\sqrt{\log(m)/m})$
for any compact set $\K\subset\bb{R}^d$, where $m$ is the number of random Fourier features. However, since the approximation proposed by the RFF method involves empirically approximating
the Fourier integral, the RFF estimator can be thought of as an \emph{empirical characteristic function} (ECF). 
In the probability literature, the systematic study of ECF-s was initiated by 
\cite{feuerverger77empirical} and followed up by \cite{csorgo83howlong,csorgo81multivariate,yukich87some}. While \cite{feuerverger77empirical} shows the almost sure (a.s.) convergence of $A_m$ to zero, 
\cite[Theorems 1 and 2]{csorgo83howlong} and \cite[Theorems 6.2 and 6.3]{yukich87some} show that the optimal rate is $m^{-1/2}$. In addition, \cite{feuerverger77empirical} shows that almost sure
convergence cannot be attained over the entire space (i.e., $\bb{R}^d$) if the characteristic function decays to zero at infinity. Due to this, \cite{csorgo83howlong,yukich87some} study the
convergence behavior of $A_m$ when the diameter of $\K$ grows with $m$ and show that almost sure convergence of $A_m$ is guaranteed as long as the diameter of $\K$ is $e^{o(m)}$. Unfortunately,
all these results (to the best of our knowledge) are asymptotic in nature and the only known finite-sample guarantee by \cite{rahimi07random,sutherland15error} is non-optimal. In this paper (see Section~\ref{sec:kernel}), 
we present a finite-sample probabilistic bound for $A_m$ that holds for any $m$ and provides the optimal rate of $m^{-1/2}$ for any compact set $\K$ along with guaranteeing the almost sure convergence of $A_m$ as long as the diameter of $\K$ is $e^{o(m)}$.
Since convergence in uniform norm might sometimes be a too strong requirement and may not be suitable to attain correct rates in the generalization bounds associated with learning algorithms involving RFF,\footnote{For example, in applications like kernel ridge regression based on RFF, it is more appropriate to consider the approximation guarantee in $L^2$ norm than in the uniform norm.} 
we also study the behavior of $k(\b{x},\b{y})-\langle \phi(\b{x}),\phi(\b{y})\rangle_{\bb{R}^{2m}}$ in $L^r$-norm ($1\le r<\infty$) and obtain an optimal rate of $m^{-1/2}$. The RFF approach 
to approximate a translation-invariant kernel can be seen as a special of the problem of approximating a function in the barycenter of a family (say $\Cal{F}$) of functions, which was considered in
\cite{rahimi08uniform}. However, the approximation guarantees in \cite[Theorem 3.2]{rahimi08uniform} do not directly apply to RFF as the assumptions on $\Cal{F}$ are not satisfied by the cosine
function, which is the family of functions that is used to approximate the kernel in the RFF approach. While a careful modification of the proof of \cite[Theorem 3.2]{rahimi08uniform} could yield
$m^{-1/2}$ rate of approximation for any compact set $\K$, this result would still be sub-optimal by providing a linear dependence on $|\K|$ similar to the theorems in \cite{rahimi07random,sutherland15error}, 
in contrast to the optimal logarithmic dependence on $|\K|$ that is guaranteed by our results.

Traditionally, kernel based algorithms involve computing the value of the kernel. Recently, kernel algorithms involving the derivatives of the kernel (i.e., the Gram matrix consists of
derivatives of the kernel computed at training samples) have been used to address numerous machine learning tasks, e.g., 
semi-supervised or Hermite learning with gradient information \cite{zhou08derivative, shi10hermite}, nonlinear variable selection \cite{rosasco10regularization,rosasco13nonparametric}, (multi-task) gradient learning \cite{ying12learning} and
fitting of distributions in an infinite-dimensional exponential family \cite{sriperumbudur14density}. 
Given the importance of these derivative based kernel algorithms, similar to \cite{rahimi07random}, 
in Section~\ref{sec:kernel-derivatives}, we propose a finite dimensional random feature map approximation to
kernel derivatives, which can be used to speed up the above mentioned derivative based kernel algorithms. We present a finite-sample bound that quantifies the quality of approximation in uniform and $L^r$-norms
and show the rate of convergence to be $m^{-1/2}$ in both these cases.

A summary of our \emph{contributions} are as follows. We
\begin{enumerate}[labelindent=0cm,leftmargin=*,topsep=0cm,partopsep=0cm,parsep=0cm,itemsep=0cm]
    \item provide the first detailed finite-sample performance analysis of RFFs for approximating kernels and their derivatives. 
    \item prove uniform and $L^r$ convergence on fixed compacts sets with optimal rate in terms of the RFF dimension ($m$);
    \item give sufficient conditions for the growth rate of compact sets while preserving a.s.\ convergence uniformly and in $L^r$; specializing our result we match the best attainable asymptotic growth rate.
\end{enumerate}
Various notations and definitions that are used throughout the paper are provided in Section~\ref{sec:problem-formulation} along with a brief review of RFF approximation proposed by \cite{rahimi07random}. 
The missing proofs of the results in Sections~\ref{sec:kernel} and \ref{sec:kernel-derivatives} are provided in the supplementary material.


section2_notations_definitions.tex
In this section, we introduce notations that are used throughout the paper and then present preliminaries on kernel approximation
through random feature maps as introduced by \cite{rahimi07random}.\vspace{1.5mm}\\
\tb{Definitions \& Notation:} For a topological
space $\Cal{X}$, $C(\Cal{X})$ (\emph{resp.} $C_b(\Cal{X})$) denotes the space of
all continuous (\emph{resp.} bounded continuous) functions on $\Cal{X}$. For $f\in
C_b(\Cal{X})$, $\Vert f\Vert_\Cal{X}:=\sup_{x\in\Cal{X}}|f(x)|$ is the supremum norm of $f$. $M_b(\Cal{X})$ and $M^1_+(\Cal{X})$ is the set of all finite
Borel and probability measures on $\Cal{X}$, respectively. For $\mu\in M_b(\Cal{X})$, $L^r(\Cal{X},\mu)$
denotes the Banach space of $r$-power ($r\ge
1$) $\mu$-integrable functions. For $\Cal{X}\subseteq\bb{R}^d$, we will use
$L^r(\Cal{X})$ for $L^r(\Cal{X},\mu)$ if $\mu$ is a Lebesgue measure on
$\Cal{X}$. For $f\in L^r(\Cal{X},\mu)$, $\Vert
f\Vert_{L^r(\Cal{X},\mu)}:=\left(\int_\Cal{X}|f|^r\,\d\mu\right)^{1/r}$ denotes
the $L^r$-norm of $f$ for $1\le r<\infty$ and we write it as
$\Vert\cdot\Vert_{L^r(\Cal{X})}$ if $\Cal{X}\subseteq\bb{R}^d$ and $\mu$ is the
Lebesgue measure. For any $f\in L^1(\Cal{X},\bb{P})$ where $\bb{P}\in M^1_+(\Cal{X})$, we define $\bb{P}f:=\int_\Cal{X} f(x)\,\d\bb{P}(x)$ and 
$\bb{P}_mf:=\frac{1}{m}\sum^m_{i=1}f(X_i)$ where $(X_i)^m_{i=1}\stackrel{i.i.d.}{\sim}\bb{P}$, $\bb{P}_m:=\frac{1}{m}\sum^m_{i=1}\delta_{X_i}$ 
is the empirical measure and $\delta_x$ is a Dirac measure supported on $x\in\Cal{X}$.  $\text{supp}(\P)$ denotes the support of $\P$. $\bb{P}^m:=\otimes_{j=1}^m\bb{P}$ denotes the $m$-fold product measure.

For $\b{v}:=(v_1,\ldots,v_d)\in\R^d$, $\Vert \b{v}\Vert_2:=\sqrt{\sum^d_{i=1}v^2_i}$. The diameter of $A\subseteq\Cal{Y}$ where $(\Cal{Y},\rho)$ is 
a metric space is defined as $|A|_\rho:=\sup\{\rho(x,y):x,y\in \Cal{Y}\}$. If $\Cal{Y}=\bb{R}^d$ with $\rho=\Vert\cdot\Vert_2$, we denote the diameter of $A$ as $|A|$; $|A|<\infty$ if $A$ is compact. The volume of $A\subseteq\bb{R}^d$ is defined as
$\text{vol}(A)=\int_A 1\, \d\b{x}$. For $A\subseteq\bb{R}^d$, we define $A_\Delta:=A-A=\{\b{x}-\b{y}:\b{x},\b{y}\in A\}$. 
$conv(A)$ is the convex hull of $A$. 
For a function $g$ 
defined on open set $B\subseteq \bb{R}^d\times \bb{R}^d$,
$\p^{\b{p},\b{q}}g(\b{x},\b{y}) := \frac{\partial^{|\b{p}|+|\b{q}|} g(\b{x},\b{y})}{\partial x_1^{p_1}\cdots\partial x_d^{p_d} \partial y_1^{q_1}\cdots\partial y_d^{q_d}},\,(\b{x},\b{y})\in B$, where 
$\b{p},\b{q}\in\N^d$ are multi-indices, $|\b{p}|=\sum_{j=1}^dp_j$ and $\bb{N}:=\{0,1,2,\ldots\}$. Define $\b{v}^{\b{p}}=\prod_{j=1}^d v_j^{p_j}$. For positive sequences $(a_n)_{n\in \N}$, $(b_n)_{n\in \N}$, $a_n = \o(b_n)$ if $\lim_{n\rightarrow \infty}\frac{a_n}{b_n} = 0$. 
$X_n=\O_{p}(r_n)$ (\emph{resp.} 
$\O_{a.s.}(r_n)$) denotes that $\frac{X_n}{r_n}$ is bounded in probability (\emph{resp.} almost surely). $\Gamma(t)=\int_0^{\infty}x^{t-1}e^{-x}\,\d x$ is the Gamma function, $\Gamma\left(\frac{1}{2}\right) = \sqrt{\pi}$ and $\Gamma(t+1)=t\Gamma(t)$.\vspace{1.5mm}\\
\tb{Random feature maps:} Let $k:\bb{R}^d\times\bb{R}^d\rightarrow\bb{R}$ be a bounded, continuous, positive definite, translation-invariant kernel, i.e., there exists a positive definite function $\psi:\bb{R}^d\rightarrow\bb{R}$ such that
$k(\b{x},\b{y})=\psi(\b{x}-\b{y}),\,\b{x},\b{y}\in\bb{R}^d$ where $\psi\in C_b(\bb{R}^d)$. By Bochner's theorem \cite[Theorem 6.6]{wendland05scattered}, $\psi$ can be represented 
as the Fourier transform of a finite non-negative Borel measure $\Lambda$ on $\bb{R}^d$, i.e., 
\begin{equation}
k(\b{x},\b{y}) = \psi(\b{x}-\b{y}) = \int_{\R^d} e^{\sqrt{-1}\bo^T(\b{x}-\b{y})}\d\S(\bo) \stackrel{(\star)}{=} \int_{\R^d} \cos\left(\bo^T(\b{x}-\b{y})\right)\d\S(\bo),\label{eq:Bochner0} 
\end{equation}
where $(\star)$ follows from the fact that $\psi$ is real-valued and symmetric. Since $\S(\bb{R}^d)=\psi(0)$, $k(\b{x},\b{y})=\psi(0)\int e^{\sqrt{-1}\bo^T(\b{x}-\b{y})}\,\d\bb{P}(\bo)$ where $\bb{P}:=\frac{\S}{\psi(0)}\in M^1_+(\bb{R}^d)$. Therefore, w.l.o.g., we 
assume throughout the paper that $\psi(0)=1$ and so $\S\in M^1_+(\bb{R}^d)$. Based on (\ref{eq:Bochner0}), \cite{rahimi07random} proposed an approximation to $k$ by replacing $\S$ with its empirical measure, $\S_m$
constructed from $(\bo_i)^m_{i=1}\stackrel{i.i.d.}{\sim}\S$ so that resultant approximation can be written as the Euclidean inner product of finite dimensional random feature maps, i.e.,
\begin{equation}
\hat{k}(\b{x},\b{y})=\frac{1}{m}\sum^m_{i=1}\cos\left(\bo^T_i(\b{x}-\b{y})\right)\stackrel{(*)}{=}\left\langle \phi(\b{x}),\phi(\b{y})\right\rangle_{\bb{R}^{2m}},\label{eq:kernel-approx}
\end{equation}
where $\phi(\b{x})=\frac{1}{\sqrt{m}}(\cos(\bo^T_1\b{x}),\ldots,\cos(\bo^T_m\b{x}),\sin(\bo^T_1\b{x}),\ldots,\sin(\bo^T_m\b{x}))$
and $(*)$ holds based on the basic trigonometric identity: $\cos(a-b)=\cos a\cos b+\sin a\sin b$. This elegant approximation to $k$ is particularly useful in speeding up kernel-based
algorithms as the finite-dimensional random feature map $\phi$ can be used to solve these algorithms in the primal thereby offering better computational complexity (than by solving them in the dual)
while at the same time not lacking in performance. 
Apart from these practical advantages, \cite[Claim 1]{rahimi07random} (and similarly, \cite[Prop.~1]{sutherland15error}) provides a theoretical guarantee that $\|\hat{k}-k\|_{\K\times \K}\rightarrow 0$ as $m\rightarrow\infty$ for
any compact set $\K\subset\bb{R}^d$. Formally, \cite[Claim 1]{rahimi07random} showed that---note that (\ref{eq:rr-orig}) is slightly different but more precise than the one in the statement of Claim 1 in \cite{rahimi07random}---for any $\epsilon>0$,
\begin{equation}
\S^m\left(\left\{(\bo_i)^m_{i=1}:  \|\hat{k}-k\|_{\K\times \K}\ge\epsilon\right\}\right)\le C_d\left(\vert\K\vert \sigma \epsilon^{-1}\right)^{\frac{2d}{d+2}}e^{-\frac{m\epsilon^2}{4(d+2)}},
\label{eq:rr-orig}
\end{equation}
where $\sigma^2:=\int \Vert\bo\Vert^2\,d\Lambda(\bo)$ and $C_d:=2^{\frac{6d+2}{d+2}}\left(\left(\frac{2}{d}\right)^{\frac{d}{d+2}}+\left(\frac{d}{2}\right)^{\frac{2}{d+2}}\right)\le 2^7d^{\frac{2}{d+2}}$ when $d\ge 2$.
The condition $\sigma^2<\infty$ implies that $\psi$ (and therefore $k$) is twice differentiable.
From (\ref{eq:rr-orig}) it is clear that the probability has polynomial tails
if $\epsilon<|\K|\sigma$ (i.e., small $\epsilon$) and Gaussian tails if $\epsilon\ge |\K|\sigma$ (i.e., large $\epsilon$) and can be equivalently written as
\begin{equation}
\Lambda^m\left(\left\{(\bo_i)^m_{i=1}: \|\hat{k}-k\|_{\K\times \K}\ge C^\frac{d+2}{2d}_d|\K|\sigma\sqrt{m^{-1}\log m}\right\}\right)\le m^{\frac{\alpha}{4(d+2)}}(\log m)^{-\frac{d}{d+2}},\label{eq:rr}
\end{equation}
where $\alpha:=4d-C^\frac{d+2}{d}_d|\K|^2\sigma^2$. For $|\K|$ sufficiently large (i.e., $\alpha<0$), it follows from (\ref{eq:rr}) that
\begin{equation}
\|\hat{k}-k\|_{\K\times \K}=\O_{p}\left(|\K|\sqrt{m^{-1}\log m}\right).\label{eq:rate-rr}
\end{equation}
While (\ref{eq:rate-rr}) shows that $\hat{k}$ is a consistent estimator of $k$ in the topology of compact convergence (i.e., $\hat{k}$ convergences to $k$ uniformly over compact sets), the
rate of convergence of $\sqrt{(\log m)/m}$ is not optimal. In addition, the order of dependence on $|\K|$ is not optimal. While a faster rate (in fact, an optimal rate) of 
convergence is desired---better rates in (\ref{eq:rate-rr}) can lead to better convergence rates for the excess error of the kernel machine constructed using $\hat{k}$---, the order of dependence on $|\K|$ is also important as
it determines the the number of RFF features (i.e., $m$) that are needed to achieve a given approximation accuracy. In fact, the order of dependence on $|\K|$ controls the rate at which $|\K|$ can be grown as a function of $m$ when $m\rightarrow\infty$
(see Remark~\ref{rem:optim}\emph{(ii)} for a detailed discussion about the significance of growing $|\K|$). 
In the following section, we present an analogue of (\ref{eq:rr})---see Theorem~\ref{Thm:conc}---that provides
optimal rates and has correct dependence on $|\K|$. 

section3_kernel_values.tex
As discussed in Sections~\ref{sec:intro} and \ref{sec:problem-formulation}, while the random feature map approximation of $k$ introduced by \cite{rahimi07random} has many 
practical advantages, it does not seem to be theoretically well-understood. The existing theoretical results on the quality of approximation do not provide a complete picture owing 
to their non-optimality. In this section, we first present our main result (see Theorem~\ref{Thm:conc}) that improves upon (\ref{eq:rr}) and provides a rate of $m^{-1/2}$ with logarithm dependence on $|\K|$. We then
discuss the consequences of Theorem~\ref{Thm:conc} along with its optimality in Remark~\ref{rem:optim}. 
Next, in Corollary~\ref{cor:lr} and Theorem~\ref{Thm:Lr}, we discuss the $L^r$-convergence ($1\le r<\infty$) of $\hat{k}$ to $k$ over compact subsets of $\bb{R}^d$. 
\begin{theorem}\label{Thm:conc}
Suppose $k(\b{x},\b{y})=\psi(\b{x}-\b{y}),\,\b{x},\,\b{y}\in\bb{R}^d$ where $\psi\in C_b(\bb{R}^d)$ is positive definite and $\sigma^2:=\int \Vert\bo\Vert^2\,\d\Lambda(\bo)<\infty$. 
Then for any $\tau>0$ and non-empty compact set $\K\subset\bb{R}^d$,
$$\S^m\left(\left\{(\bo_i)^m_{i=1}: \|\hat{k}-k\|_{\K\times \K}\ge\frac{h(d,|\K|,\sigma)+\sqrt{2\tau}}{\sqrt{m}}\right\}\right)\le e^{-\tau},$$
where $h(d,|\K|,\sigma):=32\sqrt{2d\log(2|\K|+1)}+32\sqrt{2d\log(\sigma+1)}+16\sqrt{2d[\log(2|\K|+1)]^{-1}}$.\vspace{-2mm}
\end{theorem}
\begin{proof}[Proof (sketch)]
Note that $\|\hat{k}-k\|_{\K\times \K} = \sup_{\b{x},\b{y}\in\K}|\hat{k}(\b{x},\b{y})-k(\b{x},\b{y})|=\sup_{g\in\Cal{G}}|\S_mg-\S g|$, where $\Cal{G}:=\{g_{\b{x},\b{y}}(\bo)=\cos(\bo^T(\b{x}-\b{y}))\,:\,\b{x},\b{y}\in\K\}$, which means the object of interest is the suprema of an empirical process indexed by $\Cal{G}$. 
Instead of bounding $\sup_{g\in\Cal{G}}|\S_mg-\S g|$ by using Hoeffding's inequality on a cover of $\Cal{G}$ and then applying union bound as carried out in \cite{rahimi07random,sutherland15error}, we use the 
refined technique of applying concentration via McDiarmid's inequality, followed by symmetrization and bound the Rademacher average by Dudley entropy bound. The result is obtained 
by carefully bounding the $L^2(\S_m)$-covering
number of $\Cal{G}$. The details are provided in Section~\ref{sec:proof:derivatives:suppS-bounded} of the supplementary material.
\end{proof}
\begin{remark}\label{rem:optim}
    \emph{(i)} Theorem~\ref{Thm:conc} shows that $\hat{k}$ is a consistent estimator of $k$ in the topology of compact convergence as $m\rightarrow\infty$ with the rate of a.s.~convergence being
	  $\sqrt{m^{-1}\log|\K|}$ (almost sure convergence is guaranteed by the first Borel-Cantelli lemma). In comparison to (\ref{eq:rr}), it is clear that Theorem~\ref{Thm:conc} provides improved rates with better constants and logarithmic dependence on $|\K|$ instead of a linear
	  dependence. The logarithmic dependence on $|\K|$ ensures that we need $m=O(\epsilon^{-2}\log|\K|)$ random features instead of $O(\epsilon^{-2}|\K|^{2}\log(|\K|/\epsilon))$ random features, i.e., significantly 
	  fewer features to achieve the same approximation accuracy of $\epsilon$.\vspace{2.5mm}\\
     \emph{(ii)} \textbf{Growing diameter:} While Theorem~\ref{Thm:conc} provides almost sure convergence uniformly over compact sets, one might wonder whether it is possible to achieve uniform 
	  convergence over $\bb{R}^d$. \cite[Section 2]{feuerverger77empirical} showed that such a result is possible if $\S$ is a discrete measure but not possible for $\S$ that is absolutely continuous w.r.t.~the Lebesgue measure (i.e., if $\S$ has a 
	  density). Since uniform convergence of $\hat{k}$ to $k$ over $\bb{R}^d$ is not possible for many interesting $k$ (e.g., Gaussian kernel), it is of interest to study the convergence on $\K$ whose diameter grows with $m$. Therefore,
	  as mentioned in Section~\ref{sec:problem-formulation}, the order of dependence of rates on $|\K|$ is critical. Suppose $|\K_m|\rightarrow\infty$ as $m\rightarrow\infty$ (we write $|\K_m|$ instead of $|\K|$ to show the explicit dependence on $m$). Then Theorem~\ref{Thm:conc} shows that
	  $\hat{k}$ is a consistent estimator of $k$ in the topology of compact convergence if $m^{-1}\log|\K_m|\rightarrow 0$ as $m\rightarrow\infty$ (i.e., $|\K_m|=e^{o(m)}$) in contrast to
	  the result in (\ref{eq:rr}) which requires $|\K_m|=o(\sqrt{m/\log m})$. In other words, Theorem~\ref{Thm:conc} ensures consistency even when $|\K_m|$ grows exponentially in $m$ whereas (\ref{eq:rr})
	  ensures consistency only if $|\K_m|$ does not grow faster than $\sqrt{m/\log m}$.\vspace{2.5mm}\\
     \emph{(iii)} \textbf{Optimality:} Note that $\psi$ is the characteristic function of $\S\in M^1_+(\bb{R}^d)$ since $\psi$ is the Fourier transform of $\S$ (by Bochner's theorem). Therefore, the object of interest $\|\hat{k}-k\|_{\K\times\K}=\Vert\hat{\psi}-\psi\Vert_{\K_\Delta}$, 
	  is the uniform norm of the difference between $\psi$ and the empirical characteristic function $\hat{\psi}=\frac{1}{m}\sum^m_{i=1}\cos(\langle\bo_i,\cdot\rangle)$, when both are 
	  restricted to a compact set $\K_\Delta\subset\bb{R}^d$. The question of the convergence behavior of $\Vert\hat{\psi}-\psi\Vert_{\K_\Delta}$ is not new and has been studied in great
	  detail in the probability and statistics literature (e.g., see \cite{feuerverger77empirical,yukich87some} for $d=1$ and \cite{csorgo81multivariate,csorgo83howlong} for $d>1$) where the characteristic function is not just a real-valued symmetric function (like $\psi$) 
	  but is Hermitian. \cite[Theorems 6.2 and 6.3]{yukich87some} show that the optimal rate of convergence of $\Vert\hat{\psi}-\psi\Vert_{\K_\Delta}$ is $m^{-1/2}$ when $d=1$, which matches
	  with our result in Theorem~\ref{Thm:conc}. Also Theorems 1 and 2 in \cite{csorgo83howlong} show that
	  the logarithmic dependence on $|\K_m|$ is optimal asymptotically. In particular, \cite[Theorem 1]{csorgo83howlong} matches with the growing diameter result in Remark~\ref{rem:optim}\emph{(ii)}, while
	  \cite[Theorem 2]{csorgo83howlong} shows that if $\Lambda$ is absolutely continuous w.r.t.~the Lebesgue measure and if $\lim\sup_{m\rightarrow\infty} m^{-1}\log|\K_m|>0$,
	  then there exists a positive $\varepsilon$ such that $\lim\sup_{m\rightarrow\infty}\S^m(\Vert \hat{\psi}-\psi\Vert_{\K_{m,\Delta}}\ge\varepsilon)>0$. This means the rate $|\K_m|=e^{o(m)}$
	  is not only the best possible in general for almost sure convergence, but if faster sequence $|\K_m|$ is considered then even stochastic convergence cannot be retained for any characteristic function
	  vanishing at infinity along at least one path. While these previous results match with that of Theorem~\ref{Thm:conc} (and its consequences), we would like to highlight the fact that
	  all these previous results are asymptotic in nature whereas Theorem~\ref{Thm:conc} provides a finite-sample probabilistic inequality that holds for any $m$. We are not aware of any 
	  such finite-sample result except for the one in \cite{rahimi07random,sutherland15error}.\null\hfill$\blacksquare$
\end{remark}
Using Theorem~\ref{Thm:conc}, one can obtain a probabilistic inequality for the $L^r$-norm of $\hat{k}-k$ over any compact set $\K\subset\bb{R}^d$, as given by
the following result.
\begin{corollary}\label{cor:lr}
Suppose $k$ satisfies the assumptions in Theorem~\ref{Thm:conc}. Then for any $1\le r<\infty$, $\tau>0$ and non-empty compact set $\K\subset\bb{R}^d$,
$$\S^m\left(\left\{(\bo_i)^m_{i=1}:\Vert \hat{k}-k\Vert_{L^r(\K)}\ge\left(\frac{\pi^{d/2}|\K|^d}{2^d\Gamma(\frac{d}{2}+1)}\right)^{2/r}\frac{h(d,|\K|,\sigma)+\sqrt{2\tau}}{\sqrt{m}}\right\}\right)\le e^{-\tau},$$
where $\Vert \hat{k}-k\Vert_{L^r(\K)}:=\Vert \hat{k}-k\Vert_{L^r(\K\times\K)}=\left(\int_{\K}\int_{\K}|\hat{k}(\b{x},\b{y})-k(\b{x},\b{y})|^r\,\d\b{x}\,\d\b{y}\right)^{\frac{1}{r}}.$
\end{corollary}
\begin{proof}
 Note that $$\Vert \hat{k}-k\Vert_{L^r(\K)}\le \Vert \hat{k}-k\Vert_{\K\times\K} \text{vol}^{2/r}(\K).$$ The result follows by combining Theorem~\ref{Thm:conc} and the fact that $\text{vol}(\K)\le \text{vol}(A)$
where $A:=\left\{\b{x}\in\bb{R}^d:\Vert\b{x}\Vert_2\le \frac{|\K|}{2}\right\}$ and $\text{vol}(A)=\frac{\pi^{d/2}|\K|^d}{2^d\Gamma\left(\frac{d}{2}+1\right)}$ (which follows from \cite[Corollary 2.55]{folland99real}).
\end{proof}
Corollary~\ref{cor:lr} shows that $\Vert \hat{k}-k\Vert_{L^r(\K)}=O_{a.s.}(m^{-1/2}|\K|^{2d/r}\sqrt{\log|\K|})$ and therefore if $|\K_m|\rightarrow\infty$ as $m\rightarrow\infty$,
then consistency of $\hat{k}$ in $L^r(\K_m)$-norm is achieved as long as $m^{-1/2}|\K_m|^{2d/r}\sqrt{\log|\K_m|}\rightarrow 0$ as $m\rightarrow\infty$. This means, in comparison to the uniform
norm in Theorem~\ref{Thm:conc} where $|\K_m|$ can grow exponential in $m^\delta$ ($\delta<1$), $|\K_m|$ cannot grow faster than $m^{\frac{r}{4d}}(\log m)^{-\frac{r}{4d}-\theta}$ ($\theta>0$) to achieve consistency in $L^r$-norm. 

Instead of using Theorem~\ref{Thm:conc}
to obtain a bound on $\Vert \hat{k}-k\Vert_{L^r(\K)}$ (this bound may be weak as $\Vert \hat{k}-k\Vert_{L^r(\K)}\le \Vert \hat{k}-k\Vert_{\K\times \K}\text{vol}^{2/r}(\K)$ for any $1\le r<\infty$), a better
bound (for $2\le r<\infty$) can be obtained by directly
bounding $\Vert \hat{k}-k\Vert_{L^r(\K)}$, as shown in the following result.
\begin{theorem}\label{Thm:Lr}
Suppose $k(\b{x},\b{y})=\psi(\b{x}-\b{y}),\,\b{x},\,\b{y}\in\bb{R}^d$ where $\psi\in C_b(\bb{R}^d)$ is positive definite. Then for any $1< r<\infty$, $\tau>0$ and non-empty compact set $\K\subset\bb{R}^d$,
$$\S^m\left(\left\{(\bo_i)^m_{i=1}:\Vert \hat{k}-k\Vert_{L^r(\K)}\ge\left(\frac{\pi^{d/2}|\K|^d}{2^d\Gamma(\frac{d}{2}+1)}\right)^{2/r}\left(\frac{C^\prime_{r}}{m^{1-\max\{\frac{1}{2},\frac{1}{r}\}}}+\frac{\sqrt{2\tau}}{\sqrt{m}}\right)\right\}\right)\le e^{-\tau},$$
where $C^\prime_{r}$ is the Khintchine constant given by $C^\prime_r=1$ for $r\in(1,2]$ and $C^\prime_r = \sqrt{2} \left[ \Gamma\left(\frac{r+1}{2}\right) / \sqrt{\pi} \right]^{\frac{1}{r}}$ for $r\in[2,\infty)$.\vspace{-1mm}
\end{theorem}
\begin{proof}[Proof (sketch)]
As in Theorem~\ref{Thm:conc}, we show that $\Vert k-\hat{k}\Vert_{L^r(\K)}$ satisfies the bounded difference property, hence by the McDiarmid's inequality, it concentrates 
around its expectation $\E\Vert k-\hat{k}\Vert_{L^r(\K)}$. By symmetrization, we then show that $\E\Vert k-\hat{k}\Vert_{L^r(\K)}$ is upper bounded in terms of $\bb{E}_{\bm{\varepsilon}}\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)}$,
where $\bm{\varepsilon}:=(\varepsilon_i)^m_{i=1}$ are Rademacher random variables. By exploiting 
the fact that
$L^r(\K)$ is a Banach space of type $\min\{r,2\}$, the result follows. The details are provided in Section~\ref{sec:proof:Lr} of the supplementary material.
\end{proof}

\begin{remark}
    Theorem~\ref{Thm:Lr} shows an improved dependence on $|\K|$
	without the extra $ \sqrt{\log|\K|}$ factor given in Corollary~\ref{cor:lr} and therefore provides a better rate for $2\le r<\infty$ when the diameter of $\K$ grows, i.e., $\Vert \hat{k}-k\Vert_{L^r(\K_m)}\stackrel{a.s.}{\rightarrow} 0$
	if $|\K_m|=o(m^{\frac{r}{4d}})$ as $m\rightarrow\infty$. However, for $1< r<2$, Theorem~\ref{Thm:Lr} provides a slower rate than Corollary~\ref{cor:lr} and therefore it is appropriate
	to use the bound in Corollary~\ref{cor:lr}. While one might wonder why we only considered the convergence of $\Vert \hat{k}-k\Vert_{L^r(\K)}$ and not $\Vert \hat{k}-k\Vert_{L^r(\bb{R}^d)}$, 
	it is important to note that the latter is not well-defined because $\hat{k}\notin L^r(\bb{R}^d)$ even if $k\in L^r(\bb{R}^d)$.\null\hfill$\blacksquare$
\end{remark}
section4_derivatives_bounded_supp.tex
In the previous section we focused on the approximation of the kernel function where we presented uniform and $L^r$ convergence guarantees on compact sets for the random Fourier feature approximation, and discussed how fast the diameter of these sets can grow to preserve 
uniform and $L^r$ convergence almost surely. In this section, we propose an approximation to derivatives of the kernel and analyze the uniform and $L^r$ convergence behavior 
of the proposed approximation. As motivated in Section~\ref{sec:intro}, the question of approximating the derivatives of the kernel through finite dimensional random feature map 
is also important as it enables to speed up several interesting machine learning tasks that 
involve the derivatives of the kernel \cite{zhou08derivative,shi10hermite,rosasco10regularization,rosasco13nonparametric,ying12learning,sriperumbudur14density}, see for example the recent 
infinite dimensional exponential family fitting technique \cite{strathmann15gradient}, which implements this idea.

To this end, we consider $k$ as in (\ref{eq:Bochner0}) and define $h_a:=\cos(\frac{\pi a}{2}+\cdot),\,a\in\bb{N}$ (in other words $h_0=\cos$, $h_1=-\sin$, $h_2=-\cos$, $h_3=\sin$ and $h_a=h_{a\!\!\!\mod\!4}$). For $\b{p},\b{q}\in\bb{N}^d$,
assuming $\int|\bo^{\b{p}+\b{q}}|\,\d\Lambda(\bo)<\infty$, it follows from the dominated convergence theorem that
\begin{align}
    \p^{\b{p},\b{q}} k(\b{x},\b{y})  &= \int_{\R^d} \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T(\b{x}-\b{y})\right)\d\S(\bo)\nonumber\\% \label{eq:k-derivative}\\
                                     &= \int_{\R^d} \bo^{\b{p}+\b{q}}\left[ h_{|\b{p}|}(\bo^T\b{x}) h_{|\b{q}|}(\bo^T\b{y}) + h_{3+|\b{p}|}(\bo^T\b{x}) h_{3+|\b{q}|}(\bo^T\b{y}) \right] \d\S(\bo),\nonumber%\label{eq:k-derivative-2}
\end{align}
so that $\p^{\b{p},\b{q}} k(\b{x},\b{y})$ can be approximated by replacing $\S$ with $\S_m$, resulting in 
\begin{align}
    \widehat{\p^{\b{p},\b{q}} k}(\b{x},\b{y}):=s^{\b{p},\b{q}}(\b{x},\b{y})  =\frac{1}{m} \sum_{j=1}^m \bo_j^{\b{p}}(-\bo_j)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo_j^T(\b{x}-\b{y})\right)
                                  = \left\langle \phi^{\b{p}}(\b{x}),\phi^{\b{q}}(\b{y})\right\rangle_{\bb{R}^{2m}},\label{eq:deriv-approx}
\end{align}
where $\phi^{\b{p}}(\b{u}):=\frac{1}{\sqrt{m}}\left(\bo_1^{\b{p}}h_{|\b{p}|}(\bo_1^T\b{u}),\cdots,\bo_m^{\b{p}}h_{|\b{p}|}(\bo_m^T\b{u}),\bo_1^{\b{p}}h_{3+|\b{p}|}(\bo_1^T\b{u}),\cdots,\bo_m^{\b{p}}h_{3+|\b{p}|}(\bo_m^T\b{u})\right)$ 
and $(\bo_j)^m_{j=1}\stackrel{i.i.d.}{\sim}\S$. Now the goal is to understand the behavior of $\Vert s^{\b{p},\b{q}}-\p^{\b{p},\b{q}} k\Vert_{\K\times\K}$ and $\Vert s^{\b{p},\b{q}}-\p^{\b{p},\b{q}} k\Vert_{L^r(\K)}$ for $r\in[1,\infty)$, i.e.,
obtain analogues of Theorems~\ref{Thm:conc} and \ref{Thm:Lr}. 

As in the proof sketch of Theorem~\ref{Thm:conc}, while $\Vert s^{\b{p},\b{q}}-\p^{\b{p},\b{q}} k\Vert_{\K\times \K}$ can be analyzed 
as the suprema of an empirical process indexed by a suitable function class (say $\G$), some technical issues arise because $\G$ is not uniformly bounded. This means McDiarmid or Talagrand's
inequality cannot be applied to achieve concentration and bounding Rademacher average by Dudley entropy bound may not be reasonable. While these issues can be tackled by resorting to
more technical and refined methods, in this paper, we generalize (see Theorem~\ref{theorem:rates:k-and-derivatives} which is proved in Section~\ref{sec:proof:derivatives:suppS-bounded} of the supplement) 
Theorem~\ref{Thm:conc} to derivatives under the restrictive assumption that $\text{supp}(\S)$
is bounded (note that many popular kernels including the Gaussian do not satisfy this assumption). We also present another result (see Theorem~\ref{theorem:rates:k-and-derivatives-unboundedS})
by generalizing the proof technique\footnote{We also correct some technical issues in the proof of \cite[Claim 1]{rahimi07random}, where  (i) a shift-invariant argument was applied to the 
\emph{non-shift invariant} kernel estimator $\hat{k}(\b{x},\b{y})=\frac{1}{m}\sum_{j=1}^m 2\cos(\bo_j^T \b{x} +b_j)\cos(\bo_j^T \b{y}+b_j)=\frac{1}{m}\sum_{j=1}^m\left[\cos(\bo_j^T(\b{x}-\b{y})) + \cos(\bo_j^T(\b{x}+\b{y})+2b_j)\right]$, 
(ii) the \emph{convexity} of $\K$ was not imposed leading to possibly undefined Lipschitz constant ($L$) and 
(iii) the randomness of $\bm{\Delta}^*=\argmax_{\bm{\Delta}\in \K_{\Delta}} \big\|\nabla[k(\bm{\Delta})-\hat{k}(\bm{\Delta})]\big\|_2$ 
was not taken into account, thus the upper bound on the expectation of the squared Lipschitz constant ($\E[L^2]$) does not hold.}
of \cite{rahimi07random} to \emph{unbounded} functions where the boundedness assumption of $\text{supp}(\S)$ is relaxed but at the expense of a worse rate (compared to Theorem~\ref{theorem:rates:k-and-derivatives}).
\begin{theorem}\label{theorem:rates:k-and-derivatives}
Let $\b{p},\b{q}\in\N^{d}$, $T_{\b{p},\b{q}}:= \sup_{\bo\in \emph{supp}(\S)}\left|\bo^{\b{p}+\b{q}}\right|$, 
$C_{\b{p},\b{q}} :=  \E_{\bo\sim \S}\left[ \left|\bo^{\b{p}+\b{q}}\right| \left\|\bo \right\|_2^2\right]$, and assume that $C_{2\b{p},2\b{q}}<\infty$. Suppose 
$\emph{supp}(\S)$ is bounded if $\b{p}\ne \b{0}$ and $\b{q}\ne \b{0}$.
Then for any $\tau>0$ and non-empty compact set $\K\subset\bb{R}^d$,
\begin{align*}
\S^m\left(\left\{(\bo_i)^m_{i=1}: \|\p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\|_{\K\times \K}\ge \frac{H(d,\b{p},\b{q},|\K|) + T_{\b{p},\b{q}}\sqrt{2\tau}}{\sqrt{m}}\right\}\right)\le e^{-\tau},
\end{align*}
where $$H(d,\b{p},\b{q},|\K|)= 32 \sqrt{2 d\, T_{2\b{p},2\b{q}}} \left[ \sqrt{U(\b{p},\b{q},|\K|)} + \frac{1}{2\sqrt{U(\b{p},\b{q},|\K|)}}
	+ \sqrt{ \log(\sqrt{C_{2\b{p},2\b{q}}} + 1) } \right],$$
  \hspace*{.52cm} $U(\b{p},\b{q},|\K|) =  \log\left(2|\K|T^{-1/2}_{2\b{p},2\b{q}}+1\right)$.\vspace{1mm}
\end{theorem}

\begin{remark}\label{rem:bounded-supp}
      \emph{(i)} Note that Theorem~\ref{theorem:rates:k-and-derivatives} reduces to Theorem~\ref{Thm:conc} if $\b{p}=\b{q}=0$, in which case $T_{\b{p},\b{q}}=T_{2\b{p},2\b{q}}=1$. 
	    If $\b{p}\ne \b{0}$ or $\b{q}\ne \b{0}$, then the boundedness of $\text{supp}(\S)$ implies that $T_{\b{p},\b{q}}<\infty$ and $T_{2\b{p},2\b{q}}<\infty$.\vspace{2.5mm}\\
      \emph{(ii)} \textbf{Growth of $|\K_m|$:} By the same reasoning as in Remark~\ref{rem:optim}\emph{(ii)} and Corollary~\ref{cor:lr}, it follows that 
	    $\|\p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\|_{\K_m\times \K_m}\stackrel{a.s.}{\longrightarrow}0$ if $|\K_m| = e^{o(m)}$ and 
	    $\Vert \p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\Vert_{L^r(\K_m)}\stackrel{a.s.}{\longrightarrow}0$ if $m^{-1/2}|\K_m|^{2d/r}\sqrt{\log|\K_m|}\rightarrow 0$ (for $1\le r<\infty$) as 
	    $m\rightarrow \infty$. An exact analogue of Theorem~\ref{Thm:Lr} can be obtained (but with different constants) under the assumption that $\text{supp}(\S)$ is bounded and it can be shown that
	    for $r\in[2,\infty)$, $\Vert \p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\Vert_{L^r(\K_m)}\stackrel{a.s.}{\longrightarrow}0$ if $|\K_m|=o(m^{\frac{r}{4d}})$.\null\hfill$\blacksquare$
\end{remark}

section4_derivatives_unbounded_supp.tex
The following result relaxes the boundedness of $\text{supp}(\S)$ by imposing certain moment conditions on $\S$ but at the expense of a worse rate. The proof relies on
applying Bernstein inequality at the elements of a net (which exists by the compactness of $\K$) combined with a union bound, and extending the approximation error from the anchors 
by a probabilistic Lipschitz argument.
\begin{theorem}\label{theorem:rates:k-and-derivatives-unboundedS}
    Let $\b{p},\b{q}\in\N^{d}$, $\psi$ be continuously differentiable, $\b{z}\mapsto \nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z}) \right]$ be continuous,  $\K\subset \R^d$ be any non-empty compact set, 
     $D_{\b{p},\b{q},\K}:=\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z}) \right]\right\|_2$ and
    $E_{\b{p},\b{q}} := \E_{\bo\sim \S}\left[|\bo^{\b{p}+\b{q}}| \left\|\bo \right\|_2\right]$. Assume that $E_{\b{p},\b{q}}<\infty$. Suppose
    $\exists L>0, \sigma>0$ such that
    \begin{align}
	\E_{\bo\sim \S}\left[|f(\b{z};\bo)|^M\right] &\le \frac{M!\,\sigma^2 L^{M-2}}{2}  \quad (\forall M \ge 2, \forall \b{z}\in \K_{\Delta}),   \label{eq:moment-constraint-on-g}
    \end{align}
    where $f(\b{z};\bo)= \p^{\b{p},\b{q}}k(\b{z}) - \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)$. Define $F_d:=d^{-\frac{d}{d+1}}+d^{\frac{1}{d+1}}$.\footnote{$F_d$ is monotonically decreasing in $d$, $F_1 = 2$.} Then 
    \begin{eqnarray}
    \lefteqn{\S^m\left(\left\{(\bo_i)_{i=1}^m: \|\p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\|_{\K\times \K}\ge \epsilon \right\}\right) \le }\nonumber\\
     &&\hspace*{0.1cm}\le 2^{d-1}e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}} + F_d 2^{\frac{4d-1}{d+1}} \left[ \frac{|\K|(D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}})}{\epsilon} \right]^{\frac{d}{d+1}} e^{-\frac{m\epsilon^2}{8(d+1) \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}}.
	  \label{eq:unif-rates-for-derivatives-unboundedS}
    \end{eqnarray}
\end{theorem}
\begin{remark}
  \emph{(i)} The compactness of $\K$ implies that of $\K_{\Delta}$. Hence, by the continuity of $\b{z}\mapsto \nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z}) \right]$, one gets $D_{\b{p},\b{q},\K}<\infty$.
	  \eqref{eq:moment-constraint-on-g} holds if $|f(\b{z};\bo)|\le \frac{L}{2}$ and $\E_{\bo\sim \S}\left[|f(\b{z};\bo)|^2\right]\le \sigma^2$ ($\forall \b{z}\in \K_{\Delta}$). 
	  If $\text{supp}(\S)$ is bounded, then the boundedness of $f$ is guaranteed (see Section~\ref{lemma:supp(S)-bounded=>moment-constraint-is-OK} in the supplement).\vspace{2mm}\\
	  \emph{(ii)} In the special case when $\b{p}=\b{q}=\b{0}$, our requirement boils down to the continuously differentiability of $\psi$, $E_{\b{0},\b{0}} = \E_{\bo\sim \S}\left\|\bo\right\|_2 < \infty$, and \eqref{eq:moment-constraint-on-g}.\vspace{2mm}\\
	  \emph{(iii)} Note that (\ref{eq:unif-rates-for-derivatives-unboundedS}) is similar to (\ref{eq:rr-orig}) and therefore based on the discussion in Section~\ref{sec:problem-formulation}, one has
	  $\| \p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\|_{\K\times \K}=O_{a.s.}(|\K|\sqrt{m^{-1}\log m})$. But the advantage with Theorem~\ref{theorem:rates:k-and-derivatives-unboundedS}
	  over \cite[Claim 1]{rahimi07random} and \cite[Prop.~1]{sutherland15error} is that it can handle unbounded functions. In comparison to Theorem~\ref{theorem:rates:k-and-derivatives}, we obtain worse rates and it 
	  will be of interest to improve the rates of Theorem~\ref{theorem:rates:k-and-derivatives-unboundedS} while handling unbounded functions.\null\hfill$\blacksquare$
\end{remark}
section5_conclusions.tex
In this paper, we presented the first detailed theoretical analysis about the approximation quality of random Fourier features (RFF) that was proposed by \cite{rahimi07random} in the context of
improving the computational complexity of kernel machines. While \cite{rahimi07random,sutherland15error} provided a probabilistic bound on the uniform approximation (over compact subsets of $\bb{R}^d$) of a kernel by random features, the 
result is not optimal. We improved this result by providing a finite-sample bound with optimal rate of convergence and also analyzed the quality of approximation in $L^r$-norm ($1\le r<\infty$).
We also proposed an RFF approximation for derivatives of a kernel and provided theoretical guarantees on the quality of approximation in uniform and $L^r$-norms over compact
subsets of $\bb{R}^d$.

While all the results in this paper (and also in the literature) dealt with the approximation quality of RFF over only compact subsets of $\bb{R}^d$, it is of
interest to understand its behavior over entire $\bb{R}^d$. However, as discussed in Remark~\ref{rem:optim}\emph{(ii)} and in the paragraph following Theorem~\ref{Thm:Lr}, RFF cannot approximate the kernel uniformly
or in $L^r$-norm over $\bb{R}^d$. By truncating the Taylor series expansion of the exponential function, \cite{cotter11explicit} proposed a non-random finite dimensional representation to
approximate the Gaussian kernel which also enjoys the computational advantages of RFF. However, this representation also does not approximate the Gaussian kernel uniformly over $\bb{R}^d$. Therefore, the question remains whether it is possible to approximate a kernel uniformly or in $L^r$-norm over $\bb{R}^d$ but still retaining the 
computational advantages associated with RFF.

section6_supplement.tex
\section{Definitions \& notation}\label{sec:def}
Let $(Z,\rho)$ be 
a metric space, $(\Omega,\A)$ a measurable space and $L_0(\Omega,\A)$ denotes the set of $(\Omega,\A)\mapsto \R$ measurable functions. A family of maps 
$\G=\{g_z\}_{z\in Z} \subseteq L_0(\Omega,\A)$ is called a separable Carath{\'e}odory family w.r.t.\ $Z$ if $(Z,\rho)$ is separable and $z\mapsto g_z(\omega)$ is continuous for all $\omega\in \Omega$. 
Let $\G\subseteq L_0(\Omega,\A)$, $\bm{\varepsilon}=(\varepsilon_1,\ldots,\varepsilon_m)$ be a Rademacher sequence, i.e., $\varepsilon_j$-s are i.i.d.\ and 
$\P(\varepsilon_j=1) = \P(\varepsilon_j=-1) = \frac{1}{2}$, and $(\omega_j)_{j=1}^m\in \Omega^m$. The Rademacher average of $\G$ is defined as $\Rad\left(\G,\bo_{1:m}\right):=\E_{\bm{\varepsilon}} \sup_{g\in \G} \left|\frac{1}{m} \sum_{j=1}^m \varepsilon_j g(\omega_j)\right|$; we use the shorthand $\bo_{1:m}=(\bo_1,\ldots,\bo_m)$.
$S\subseteq Z$ is said to be an $r$-net of $Z$ if for any $z\in Z$ there is an $s\in S$ such that $\rho(s,z)\le r$. The $r$-covering number of $Z$ is defined as the size of the smallest $r$-net, i.e., 
$\CN(Z,\rho,r)=\inf\left\{\ell\ge 1: \exists\, s_1,\ldots,s_\ell \text{ such that } Z \subseteq \cup_{j=1}^\ell B_{\rho}(s_j,r)\right\}$, where 
$B_{\rho}(s,r)=\{z\in Z: \rho(z,s)\le r\}$ is the closed ball with center $s\in Z$ and radius $r$. $\log \CN(Z,\rho,r)$ is called the metric entropy.  A $(Z,\left\|\cdot\right\|)$ Banach space is said to be of type $q\in (1,2]$ if there exists a constant $C\in \R$  such that the  
 $\E_{\bm{\varepsilon}} \left\|\sum_{j=1}^m \varepsilon_j f_j\right\| \le C \left(\sum_{j=1}^m\left\|f_j\right\|^q\right)^{\frac{1}{q}}$ holds for every finite set of vectors
$\{f_j\}_{j=1}^m \subseteq Z$.
For example, $L^r(\Omega,\A,\mu)$ spaces are of type $q=\min(2,r)$ \cite[page~73]{lindenstrauss79classical}, where the $C$ constant only depends on $r$ ($C=C_r$). For a $(Z,\left\|\cdot\right\|)$ normed space, $Z^*$ denotes the space of continuous linear functionals on $Z$.

\section{Proofs}\label{sec:supplement}
We provide proofs of the results presented in Sections~\ref{sec:kernel} and \ref{sec:kernel-derivatives}. Lemmas used in the proofs are enlisted in Section~\ref{sec:suppl:lemmas}.

\subsection{Proof of Theorems~\ref{Thm:conc} and \ref{theorem:rates:k-and-derivatives}} \label{sec:proof:derivatives:suppS-bounded}
Below we prove Theorem~\ref{theorem:rates:k-and-derivatives}, thereby Theorem~\ref{Thm:conc} ($\b{p}=\b{q}=\b{0}$). The idea of the proof is as follows: \emph{(i)} We note that
\begin{align}
  \|\p^{\b{p},\b{q}} k - s^{\b{p},\b{q}}\|_{\K\times \K}= \sup_{\b{x},\b{y}\in \K} \left| \p^{\b{p},\b{q}} k(\b{x},\b{y}) - s^{\b{p},\b{q}}(\b{x},\b{y})\right| = \sup_{g\in\G}|\S g-\S_mg|=:\left\|\S-\S_m\right\|_{\G},\label{eq:emproc}
\end{align}
where $\G:=\{g_{\b{z}}: \b{z}\in \K_{\Delta}\}$ and $g_{\b{z}}: \text{supp}(\S) \rightarrow \bb{R}$, $\bo\mapsto\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)$, which means the object
of interest is the suprema of an empirical process indexed by $\G$. \emph{(ii)} We show that $\left\|\S-\S_m\right\|_{\G}$ is measurable w.r.t.~$\S^m$ by verifying that $\Cal{G}$ is 
a separable Carath{\'e}odory family (see the discussion following Definition 7.4 in \cite{steinwart08support}).
\emph{(iii)} (\ref{eq:emproc}) can be shown to satisfy the bounded difference property in \ref{eq:bdd} and therefore by McDiarmid's inequality (Lemma~\ref{lemma:McDiarmid}), 
$\left\|\S-\S_m\right\|_{\G}$ concentrates around its expectation. 
\emph{(iv)} By applying the symmetrization lemma \cite[Proposition~7.10]{steinwart08support} for the uniformly bounded function family $\G$, we obtain an 
upper bound in terms of the expected Rademacher average of $\G$. \emph{(v)} The Rademacher average is bounded by
the metric entropy of $\G$ (making use of the Dudley's entropy integral \cite[Equation 4.4]{bousquet03new}), for which we can get an estimate by showing that $\G$ is a smoothly parametrized function class 
using the compactness of $\K_{\Delta}$. 

\begin{compactitem}
\item \tb{$\G$ is a separable Carath{\'e}odory family:} $\G$ is a separable Carath{\'e}odory family w.r.t.\ $\K_{\Delta}$ since 
    \begin{compactenum}
      \item $g_{\b{z}}: \text{supp}(\S)\rightarrow\bb{R}$, $\bo \mapsto \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)$ is measurable  for all $\b{z}\in \K_{\Delta}$.
      \item $\K_{\Delta}\subseteq\R^d$ is separable since $\R^d$ is separable.
      \item $\b{z}\mapsto \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)$ is continuous for all $\bo\in \text{supp}(\S)$.\vspace{1mm}
    \end{compactenum}
    
\item \tb{Concentration of $\left\|\S-\S_m\right\|_{\G}$ by its bounded difference property}:
	By defining $f(\bo_1,\ldots,\bo_m):=\left\|\S-\S_m\right\|_{\G}$, we have that for $\forall i\in\{1,\ldots,m\}$,
	\begin{eqnarray*}
	  \lefteqn{|f(\bo_1,\ldots,\bo_{i-1},\bo_i,\bo_{i+1},\ldots,\bo_m) - f(\bo_1,\ldots,\bo_{i-1},\bo_i',\bo_{i+1},\ldots,\bo_m)|= }\\
	    &&\hspace*{1cm}= \left|\sup_{g\in\G}\Big|\S g-\frac{1}{m}\sum^m_{j=1}g(\bo_j)\Big| - \sup_{g\in\G}\Big|\S g-\frac{1}{m}\sum^m_{j=1}g(\bo_j)+\frac{1}{m}\left[g(\bo_i)-g(\bo_i')\right]\Big|\right|
	    \le \frac{1}{m} \sup_{g\in \G} \left| g(\bo_i)-g(\bo_i') \right|\\
	    &&\hspace*{1cm} \le \frac{1}{m} \sup_{g\in \G} \left(\left| g(\bo_i)\right| + \left|g(\bo_i') \right|\right) 
	      \le \frac{1}{m} \left[\sup_{g\in \G} \left| g(\bo_i)\right| + \sup_{g\in \G} \left|g(\bo_i') \right|\right]
	      \le \frac{1}{m}\left[| \bo_i^{\b{p}+\b{q}}| + |(\bo_i')^{\b{p}+\b{q}}|\right]
	    \le \frac{2 T_{\b{p},\b{q}}}{m}.
	\end{eqnarray*}
	Applying McDiarmid's inequality (Lemma~\ref{lemma:McDiarmid}) to $f$, for any $\tau>0$, with probability at least $1-e^{-\tau}$ over the choice of 
	$(\bo_i)^m_{i=1}\stackrel{i.i.d.}{\sim}\S$, 
\begin{align}
  \left\|\S-\S_m\right\|_{\G} &\le \E_{\bo_{1:m}}\left\|\S-\S_m\right\|_{\G} + T_{\b{p},\b{q}}\sqrt{\frac{2\tau}{m}}. \label{eq:bound-by-bdiff}
\end{align}
\item \tb{Bounding $\E_{\bo_{1:m}}\left\|\S-\S_m\right\|_{\G}$:} 
By the symmetrization lemma \cite[Proposition~7.10]{steinwart08support} applied for the uniformly bounded function family $\G$ ($\sup_{g\in\G}\left\|g\right\|_{\infty}\le T_{\b{p},\b{q}} <\infty$), we have
    \begin{align}
    \E_{\bo_{1:m}}\left\|\S-\S_m\right\|_{\G} &\le 2\, \E_{\bo_{1:m}} \Rad\left(\G,\bo_{1:m}\right). \label{eq:convert-to-Rad}
    \end{align}
\item 
\tb{Bounding $\Rad\left(\G,\bo_{1:m}\right)$:}
      Using Dudley's  entropy integral \cite[Equation 4.4]{bousquet03new}, we have
      \begin{align}
	  \Rad\left(\G,\bo_{1:m}\right) &\le \frac{8\sqrt{2}}{\sqrt{m}}\int_0^{|\G|_{L^2(\S_m)}} \sqrt{\log \CN(\G,L^2(\S_m),r)}\, \d r. \label{eq:Rad-logN}
      \end{align}
      The upper limit of the integral can be bounded as
\begin{eqnarray}
|\G|_{L^2(\S_m)} = \sup_{g_1,g_2\in \G} \left\|g_1-g_2\right\|_{L^2(\S_m)} \le \sup_{g_1,g_2\in \G} \left(\left\|g_1\right\| +\left\|g_2\right\|_{L^2(\S_m)}\right)\le 2\sup_{g\in \G} \left\|g\right\|_{L^2(\S_m)}
\stackrel{(\ast)}{\le} 2 \sqrt{T_{2\b{p},2\b{q}}}, \label{eq:int-b2}
\end{eqnarray}
where $(\ast)$ follows from
\begin{align*}
 \sup_{g\in\G}\left\| g\right\|_{L^2(\S_m)} =\sup_{\b{z}\in\K_{\Delta}}\sqrt{\frac{1}{m}\sum^m_{j=1}g^2_{\b{z}}(\bo_j)}
		  =\sup_{\b{z}\in\K_{\Delta}}\sqrt{\frac{1}{m}\sum^m_{j=1} \left[\bo_j^{\b{p}}(-\bo_j)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo_j^T\b{z}\right)\right]^2}
		  \le \sqrt{\frac{1}{m}\sum^m_{j=1} \bo_j^{2(\b{p}+\b{q})}} \le \sqrt{T_{2\b{p},2\b{q}}}.
\end{align*}
\item 
\tb{Bounding $\Cal{N}(\G,L^2(\S_m),r)$ by the compactness of $\K_{\Delta}$}: For any
    $g_{\b{z}_1}$, $g_{\b{z}_2} \in \G$, $$\left\| g_{\b{z}_1} - g_{\b{z}_2} \right\|_{L^2(\S_m)} = \left\|\bo\mapsto \bo^{\b{p}}(-\bo)^{\b{q}} \left(h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}_1\right) - h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}_2\right)\right)\right\|_{L^2(\S_m)}.$$
    By the mean value theorem, there exists $c\in(0,1)$ such that 
    $$\left|h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}_1\right) - h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}_2\right) \right|\le \left\|\nabla_{\b{z}} h_{|\b{p}+\b{q}|}\left(\bo^T(c\b{z}_1+(1-c)\b{z}_2)\right) \right\|_2 \left\|\b{z}_1-\b{z}_2\right\|_2,$$
    where $$\left\|\nabla_{\b{z}} h_{|\b{p}+\b{q}|}\left(\bo^T(c\b{z}_1+(1-c)\b{z}_2)\right) \right\|_2\le\Vert\bo\Vert_2.$$
Therefore,
\begin{align}
 \left\| g_{\b{z}_1} - g_{\b{z}_2} \right\|_{L^2(\S_m)} &\le \sqrt{\frac{1}{m}\sum_{j=1}^m\left(\left|\bo_j^{\b{p}+\b{q}}\right| \left\|\bo_j \right\|_2 \left\|\b{z}_1-\b{z}_2\right\|_2\right)^2}
	  = \left\|\b{z}_1-\b{z}_2\right\|_2 \sqrt{\frac{1}{m}\sum_{j=1}^m\left|\bo_j^{2(\b{p}+\b{q})}\right| \left\|\bo_j \right\|_2^2 }. \label{eq:norm-upper-bound}
\end{align}
\eqref{eq:norm-upper-bound} shows that the existence of an $\epsilon$-net on $\left(\K_{\Delta},\left\|\cdot\right\|_2\right)$ implies an 
$r=\epsilon\sqrt{\frac{1}{m}\sum_{j=1}^m\left|\bo_j^{2(\b{p}+\b{q})}\right| \left\|\bo_j \right\|_2^2}$-net on $(\G,L^2(\S_m))$. In other words,
\begin{equation}
\CN\left(\G,L^2(\S_m),r\right)\le \CN\left(\K_{\Delta},\left\|\cdot\right\|_2,r\left(\frac{1}{m}\sum_{j=1}^m\left|\bo_j^{2(\b{p}+\b{q})}\right| \left\|\bo_j \right\|_2^2\right)^{-\frac{1}{2}}\right).\nonumber 
\end{equation}
Define $$A_{\b{p},\b{q}}:=\sqrt{\frac{1}{m}\sum_{j=1}^m\left|\bo_j^{2(\b{p}+\b{q})}\right| \left\|\bo_j \right\|_2^2}.$$ By using the fact that 
$\K_\Delta\subseteq B_{\Vert\cdot\Vert_2}\left(\b{t},\frac{|\K_\Delta|}{2}\right)$ for some $\b{t}\in\bb{R}^d$ and $\CN(B_{\Vert\cdot\Vert_2}(\b{s},R),\left\|\cdot\right\|_2,\epsilon)\le \left(\frac{4R}{\epsilon}+1\right)^d$ for any $\b{s}\in\bb{R}^d$ \cite[Lemma~2.5, page~20]{geer09empirical}, 
we obtain
\begin{equation}
\CN\left(\G,L^2(\S_m),r\right) \le \left( \frac{4|\K|A_{\b{p},\b{q}}}{r}+1 \right)^d,\label{eq:CN-bound:1}
\end{equation}
by noting that $|\K_\Delta|\le 2|\K|$. Using (\ref{eq:int-b2}) and (\ref{eq:CN-bound:1}) in (\ref{eq:Rad-logN}), we have
\begin{align}
	  \Rad\left(\G,\bo_{1:m}\right) &\le \frac{8 \sqrt{2d} }{\sqrt{m}} \int_0^{2 \sqrt{T_{2\b{p},2\b{q}}}} \sqrt{\log\left( \frac{4|\K|A_{\b{p},\b{q}}}{r}+1 \right)} \, \d r
	    &\le \frac{8 \sqrt{2d} }{\sqrt{m}} \int_0^{2 \sqrt{T_{2\b{p},2\b{q}}}} \sqrt{\log\left( \frac{4|\K|A_{\b{p},\b{q}} + 2 \sqrt{T_{2\b{p},2\b{q}}}}{r} \right)}\,\d r,
	    \label{eq:R-bound-final-0}
    \end{align}
where in the last inequality we used the fact that $r\le 2\sqrt{T_{2\b{p},2\b{q}}}$. By bounding $2|\K|A_{\b{p},\b{q}} + \sqrt{T_{2\b{p},2\b{q}}}\le (2|\K|+\sqrt{T_{2\b{p},2\b{q}}})(A_{\b{p},\b{q}}+1)$, 
(\ref{eq:R-bound-final-0}) reduces to
\begin{eqnarray}
 \Rad\left(\G,\bo_{1:m}\right) &{}\le{}& \frac{8 \sqrt{2d} }{\sqrt{m}}\left(\int_0^{2 \sqrt{T_{2\b{p},2\b{q}}}} \sqrt{\log\frac{2\left(2|\K|+\sqrt{T_{2\b{p},2\b{q}}}\right)}{r}}\,\d r+2 \sqrt{T_{2\b{p},2\b{q}}\log(A_{\b{p},\b{q}}+1)}\right)\nonumber\\
 &{}={}& \frac{16 \sqrt{2d} }{\sqrt{m}}\sqrt{T_{2\b{p},2\b{q}}}\left(\int_0^{1} \sqrt{\log\frac{B_{\b{p},\b{q}}+1}{r}}\,\d r+\sqrt{\log(A_{\b{p},\b{q}}+1)}\right), 
 \label{eq:rad-final}
 \end{eqnarray}
 where the last equality is obtained by changing the variable of integration and defining $B_{\b{p},\b{q}}:=\frac{2|\K|}{\sqrt{T_{2\b{p},2\b{q}}}}$.
By applying Lemma~\ref{lemma:integral} to bound the integral in (\ref{eq:rad-final}), we obtain
\begin{equation}
 \Rad\left(\G,\bo_{1:m}\right) \le \frac{16 \sqrt{2d} }{\sqrt{m}}\sqrt{T_{2\b{p},2\b{q}}}\left(\sqrt{\log(B_{\b{p},\b{q}}+1)}+\frac{1}{2\sqrt{\log(B_{\b{p},\b{q}}+1)}}+\sqrt{\log(A_{\b{p},\b{q}}+1)}\right).
 \label{eq:rad-final-1}
 \end{equation}
\item 
\tb{Bounding the expectation of the Rademacher average}: From \eqref{eq:rad-final-1}, we have
\begin{align}
\E_{\bo_{1:m}} \Rad\left(\G,\bo_{1:m}\right) &\le \frac{16 \sqrt{2d} }{\sqrt{m}}\sqrt{T_{2\b{p},2\b{q}}}\left[\sqrt{\log(B_{\b{p},\b{q}}+1)}+\frac{1}{2\sqrt{\log(B_{\b{p},\b{q}}+1)}}
+\sqrt{\log\left(\sqrt{C_{2\b{p},2\b{q}}}+1\right)}\right],\label{eq:E-bound-1}
\end{align}
which is obtained by repeated applications of Jensen's inequality to bound $\bb{E}_{\bo_{1:m}}\sqrt{\log(A_{\b{p},\b{q}}+1)}\le \sqrt{\bb{E}_{\bo_{1:m}}\log(A_{\b{p},\b{q}}+1)}\le \sqrt{\log(\bb{E}_{\bo_{1:m}} A_{\b{p},\b{q}}+1)}$
where $\bb{E}_{\bo_{1:m}}A_{\b{p},\b{q}}\le \sqrt{\frac{1}{m}\sum^m_{j=1}\bb{E}_{\bo_j}\left[ \left|\bo_j^{2(\b{p}+\b{q})}\right| \left\|\bo_j \right\|_2^2 \right]}\le \sqrt{C_{2\b{p},2\b{q}}}$.\vspace{.5mm}\\
\item \tb{Final bound:} Combining \eqref{eq:bound-by-bdiff}, \eqref{eq:convert-to-Rad} and \eqref{eq:E-bound-1} yields the result.\qed
\end{compactitem}

\subsection{Proof of Theorem~\ref{Thm:Lr}}\label{sec:proof:Lr}
Below we prove Theorem~\ref{Thm:Lr}: (i) We show that $f(\bo_1,\ldots,\bo_m):=\Vert k-\hat{k}\Vert_{L^r(\K)}$ satisfies the bounded difference property, hence by the McDiarmid's inequality (Lemma~\ref{lemma:McDiarmid}) it concentrates 
around its expectation $\E\Vert k-\hat{k}\Vert_{L^r(\K)}$. (ii) By $L^r(\K) = \left[L^{\tilde{r}}(\K)\right]^*$ ($\frac{1}{r}+\frac{1}{\tilde{r}}=1$), the separability of $L^{\tilde{r}}(\K)$ and the symmetrization lemma \cite[Lemma~2.3.1]{Vaart-96} 
the value of $\E\Vert k-\hat{k}\Vert_{L^r(\K)}$ is upper bounded in terms of $\bb{E}_{\bm{\varepsilon}}\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)}$. (iii) Exploiting that
$L^r(\K)$ is of type $\min(r,2)$ with a constant independent of $\K$, we get the result.

\begin{compactitem}
 \item \tb{Concentration of $\Vert k-\hat{k}\Vert_{L^r(\K)}$ by its bounded difference property}:
      Define $\hat{k}_i(\b{x},\b{y})=\frac{1}{m}\sum_{j\ne i}\cos(\bo^T_j(\b{x}-\b{y}))+\frac{1}{m}\cos(\tilde{\bo}^T_i(\b{x}-\b{y}))$ where $\tilde{\bo}_i$ is an i.i.d.~copy of $\bo_i$.
      Then $\Vert k-\hat{k}\Vert_{L^r(\K)}$ satisfies the bounded difference property in (\ref{eq:bdd}):
      \begin{align}
      \sup_{(\bo_i)^m_{i=1},\tilde{\bo}_i}\left|\Vert k-\hat{k}\Vert_{L^r(\K)} - \Vert k-\hat{k}_i\Vert_{L^r(\K)}\right| &\le 
      \sup_{(\bo_i)^m_{i=1},\tilde{\bo}_i}\Vert \hat{k}_i - \hat{k}\Vert_{L^r(\K)} \le\frac{2}{m}\sup_{\bo_i}\Vert\cos(\langle\bo_i,\cdot-\cdot\rangle)\Vert_{L^r(\K)}
      \le \frac{2}{m}\text{vol}^{2/r}(\K)\nonumber
      \end{align}
      and therefore by McDiarmid's inequality (Lemma~\ref{lemma:McDiarmid}), for any $\tau>0$, with probability at least $1-e^{-\tau}$ over the choice of $(\bo_i)^m_{i=1}\sim\Lambda$, we have
      \begin{equation}
	  \Vert k-\hat{k}\Vert_{L^r(\K)}\le \bb{E}_{\bo_{1:m}}\Vert k-\hat{k}\Vert_{L^r(\K)}+\text{vol}^{2/r}(\K)\sqrt{\frac{2\tau}{m}}.\label{Eq:mcd1}
      \end{equation}
  \item \tb{Symmetrization, reduction to $\E_{\bm{\varepsilon}}\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)}$}: Let $\tilde{r}$ be the dual exponent of 
	  $r$, in other words $\frac{1}{r}+\frac{1}{\tilde{r}}=1$. Then, by $L^r(\K) = \left[L^{\tilde{r}}(\K)\right]^*$ and the separability of $L^{\tilde{r}}(\K)$, there exists (see Lemma~\ref{lemma:Lr-as-countable-sup}) a 
	  countable $\G\subseteq L^{\tilde{r}}(\K)$ ($\forall g\in\G$, $\left\|g\right\|_{L^{\tilde{r}}(\K)}=1$) such that
	\begin{align}
	    \Vert k-\hat{k}\Vert_{L^r(\K)} &= \sup_{g\in \G} \left|\int_{\K\times \K} g(\b{x},\b{y}) \left[k(\b{x},\b{y})-\hat{k}(\b{x},\b{y})\right]\d \b{x} \d \b{y}\right|.\label{eq:norm-repr}
	\end{align}
	One can rewrite the argument of this supremum by Eqs.~\eqref{eq:Bochner0}-\eqref{eq:kernel-approx} as
	\begin{align*}
	    \int_{\K\times \K} g(\b{x},\b{y}) \left[k(\b{x},\b{y})-\hat{k}(\b{x},\b{y})\right]\d \b{x} \d \b{y} 
	    &= \int_{\K\times \K} g(\b{x},\b{y}) \left[\int_{\R^d}\cos(\bo^T(\b{x}-\b{y})) \d (\S-\S_m)(\bo)\right]\d \b{x} \d \b{y}\\
	    &= \int_{\R^d} \left[\int_{\K\times \K} g(\b{x},\b{y}) \cos(\bo^T(\b{x}-\b{y})) \d \b{x} \d \b{y} \right]\d (\S-\S_m)(\bo),
	\end{align*}
	and thus 
	\begin{align}
	    \Vert k-\hat{k}\Vert_{L^r(\K)} = \sup_{\tilde{g}\in \tilde{\G}} \left|(\S-\S_m)\tilde{g}\right|, \label{eq:k-hatk:repr}
	\end{align}
	where $\tilde{\G}:=\left\{\tilde{g}_g: g\in \G\right\}$, $\tilde{g}_g(\bo) = \int_{\K\times \K} g(\b{x},\b{y}) \cos(\bo^T(\b{x}-\b{y})) \d \b{x} \d \b{y}$ and $\tilde{g}_g$ is continuous. 
	Hence, using \eqref{eq:k-hatk:repr} with the symmetrization lemma \cite[Lemma~2.3.1]{Vaart-96} and  \eqref{eq:norm-repr}, we have 
	\begin{eqnarray}
	  \lefteqn{\bb{E}_{\bo_{1:m}}\Vert k-\hat{k}\Vert_{L^r(\K)} \le 2 \E_{\bo_{1:m}} \E_{\bm{\varepsilon}} \sup_{\tilde{g}\in \tilde{\G}} \left|\frac{1}{m} \sum_{i=1}^m \varepsilon_i \tilde{g}(\bo_i)\right|
	   = \frac{2}{m} \E_{\bo_{1:m}} \E_{\bm{\varepsilon}} \sup_{g\in \G} \left| \sum_{i=1}^m \varepsilon_i \int_{\K\times \K} g(\b{x},\b{y}) \cos\left(\bo_i^T(\b{x}-\b{y})\right) \d \b{x} \d \b{y} \right|}\nonumber\\
	  &&\hspace*{-0.5cm} = \frac{2}{m} \E_{\bo_{1:m}} \E_{\bm{\varepsilon}} \sup_{g\in \G} \left|  \int_{\K\times \K} g(\b{x},\b{y}) \left[\sum_{i=1}^m \varepsilon_i  \cos\left(\bo_i^T(\b{x}-\b{y})\right)\right] \d \b{x} \d \b{y} \right|
	  = \frac{2}{m}\bb{E}_{\bo_{1:m}}\bb{E}_{\bm{\varepsilon}}\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)},\label{Eq:symm}
	\end{eqnarray}
	where $(\varepsilon_i)^m_{i=1}$ is a Rademacher sequence and $\bb{E}_{\bm{\varepsilon}}$ is the conditional expectation w.r.t.~$(\varepsilon_i)^m_{i=1}$ with $(\bo_i)^m_{i=1}$ being the conditioning random variables.
	Notice that the  measurability of $\tilde{g}_{g}$-s with the countable cardinality of $\tilde{\G}$ enabled us to write expectations instead of outer expectations in \cite[Lemma~2.3.1, page 108-110]{Vaart-96}, and hence in Eq.~\eqref{Eq:symm}.\vspace{.5mm}\\
  \item \tb{Bounding $\bb{E}_\varepsilon\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)}$ by the type of $L^r(\K)$}:
	\begin{align}
	  \bb{E}_ {\bm{\varepsilon}}\left\Vert \sum^m_{i=1}\varepsilon_i\cos(\langle\bo_i,\cdot-\cdot\rangle)\right\Vert_{L^r(\K)} & \stackrel{(*)}{\le} C^{\prime}_{r}\left(\sum^m_{i=1}\Vert \cos(\langle\bo_i,\cdot-\cdot\rangle)\Vert^{\min\{r,2\}}_{L^r(\K)}\right)^{\frac{1}{\min\{r,2\}}}
	  \le C^{\prime}_{r}\text{vol}^{2/r}(\K)m^{\max\{\frac{1}{2},\frac{1}{r}\}},\label{Eq:type}
	\end{align}
	since $L^r(\K)$ is of type $\min(2,r)$ \cite[page~73]{lindenstrauss79classical} and there exists a universal constant $C^{\prime}_{r}$ independent of $\K$ (the so-called Khintchine constant) \cite[page~247]{ledoux02probability} such that $(*)$ holds; in addition we 
      used 
      \begin{align*}
	\sum^m_{i=1}\Vert \cos(\langle\bo_i,\cdot-\cdot\rangle)\Vert^{\min\{2,r\}}_{L^r(\K)}  
	  = \sum_{i=1}^m \left(\int_{\K\times \K}\left|\cos(\bo_i^T(\b{x}-\b{y}))\right|^r \d \b{x} \d \b{y}\right)^{\frac{\min\{2,r\}}{r}}
	    \le m\left[\text{vol}^2(\K)\right]^{\frac{\min\{2,r\}}{r}},
      \end{align*}
      and $\frac{1}{\min\{2,r\}} = \max\left\{\frac{1}{2},\frac{1}{r}\right\}$.

\end{compactitem}
Combining (\ref{Eq:mcd1})--(\ref{Eq:type}) and using the bound on $\text{vol}(\K)$ given in the proof of Corollary~\ref{cor:lr} 
yields the result.\qed

\subsection{Proof of Theorem~\ref{theorem:rates:k-and-derivatives-unboundedS}} \label{sec:proof:derivatives:suppS-unbounded}
Below we give the detailed proof of Theorem~\ref{theorem:rates:k-and-derivatives-unboundedS}. At high-level the proof goes as follows: 
\emph{(i)} By the compactness of $\K_{\Delta}$ (implied by that of $\K$) one can take an $r$-net covering $\K_{\Delta}$ (for any $r>0$). \emph{(ii)} Small approximation error can be guaranteed at the 
centers of the $r$-net by Bernstein's inequality 
combined with a union bound. \emph{(iii)} Propagation of the error from the centers to arbitrary points
is achieved by Lipschitzness. \emph{(iv)} The Lipschitz constant is, however, a random quantity and we show with high probability that it is `not too large'. \emph{(v)} Union bounding the two events 
(small errors at the centers and small Lipschitz constant) leads to a uniform bound for arbitrary $r$, which holds with high probability. \emph{(vi)} Optimizing over $r$ gives the stated result. 

Formally, the proof is as follows. Let us define  $$B_{\b{p},\b{q},\K}:= \E_{\bo\sim \S}\left[\sup_{\b{z}\in conv(\K_{\Delta})} \left\| \nabla_{\b{z}} f(\b{z};\bo) \right\|_2\right],$$ where 
$f(\b{z};\bo)= \p^{\b{p},\b{q}}k(\b{z}) - \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)$. Let us notice that since $conv(\K_{\Delta})$ is compact (by the compactness of $\K_{\Delta}$, implied by that of $\K$) and $\b{z} \mapsto \left\|\nabla_{\b{z}}f(\b{z};\bo)\right\|_2$ is continuous, the supremum inside the expectation in $B_{\b{p},\b{q},\K}$ is finite for any $\bo$.
    
\begin{compactitem}
    \item \tb{Covering of $\K_{\Delta}$:} By the compactness of $\K_{\Delta}$ there exist an 
	$r$-net with at most 
	\begin{equation}
	N=\left(\frac{2|\K_{\Delta}|}{r}+1\right)^d \le \left(\frac{4|\K|}{r}+1\right)^d\label{eq:cover-nn}
	\end{equation} balls covering $\K_{\Delta}$ \cite[Lemma~2.5, page~20]{geer09empirical}, 
	where we used that $|\K_{\Delta}|\le 2|\K|$. Let us denote the centers of this $r$-net by 
	$\b{c}_1, \ldots, \b{c}_N$.
    \item \tb{Bounding $\bar{f}(\b{b};\bo_{1:m}) - \bar{f}(\b{a};\bo_{1:m})$},  \tb{where $\b{a}, \b{b}\in \K_{\Delta}$; $\bo_{1:m}=(\bo_1,\ldots,\bo_m)$ is fixed:} Let 
      \begin{align*}
	  \bar{f}(\b{z};\bo_{1:m}) = \frac{1}{m} \sum_{j=1}^m f(\b{z};\bo_j) = \frac{1}{m}\sum_{j=1}^m \left[\p^{\b{p},\b{q}}k(\b{z}) - \bo_j^{\b{p}}(-\bo_j)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo_j^T\b{z}\right)\right].
      \end{align*}
       $\b{z}\mapsto \bar{f}(\b{z};\bo_{1:m})$ is continuously differentiable since $\psi$ is so. Thus by the mean value theorem 
       $\exists\,t\in(0,1)$ such that
       $$\bar{f}(\b{b};\bo_{1:m}) - \bar{f}(\b{a};\bo_{1:m}) = \left \langle \nabla_{\b{z}}\bar{f}(t\b{a}+(1-t)\b{b};\bo_{1:m}), \b{b}-\b{a}\right\rangle.$$
    Hence by the Cauchy-Bunyakovsky-Schwarz inequality, we get
    \begin{align}
     |\bar{f}(\b{b};\bo_{1:m}) - \bar{f}(\b{a};\bo_{1:m})| & \le \left\|\nabla_{\b{z}}\bar{f}(t\b{a}+(1-t)\b{b};\bo_{1:m})\right\|_2 \left\|\b{b}-\b{a}\right\|_2
     \le \sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}\bar{f}(\b{z};\bo_{1:m})\right\|_2 \left\|\b{b}-\b{a}\right\|_2 \nonumber\\
     &=: L(\bo_{1:m}) \left\|\b{b}-\b{a}\right\|_{2},
	  \label{eq:gbar-diff}
    \end{align}
    where we used the compactness of $conv(\K_{\Delta})$ (implied by that of $\K_{\Delta}$) and the continuity of the $\b{z}\mapsto \left\|\nabla_{\b{z}}\bar{f}(\b{z};\bo_{1:m})\right\|_2$ mapping to guarantee that $L(\bo_{1:m})$ exists, and it is finite for any $\bo_{1:m}$.\vspace{.5mm}\\
\item \tb{Bound  on $\E_{\bo_1,\ldots,\bo_m}[L(\bo_{1:m})]$:} Using the definition of $\bar{f}(\b{z};\bo_{1:m})$, the linearity of differentiation, and the triangle inequality, we get
    \begin{align*}
      \left\|\nabla_{\b{z}}\bar{f}(\b{z};\bo_{1:m})\right\|_2 &= \left\|\nabla_{\b{z}}\left[\frac{1}{m}\sum_{j=1}^m f(\b{z};\bo_j)\right]\right\|_2
         = \left\|\frac{1}{m}\sum_{j=1}^m\nabla_{\b{z}} f(\b{z};\bo_j) \right\|_2 \le \frac{1}{m}\sum_{j=1}^m \left\|\nabla_{\b{z}} f(\b{z};\bo_j)\right\|_2.
    \end{align*}
    Therefore, $$\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}\bar{f}(\b{z};\bo_{1:m})\right\|_2 \le \frac{1}{m}\sum_{j=1}^m \sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}f(\b{z};\bo_j)\right\|_2$$
    and 
   \begin{align}
     \E_{\bo_{1:m}}[L(\bo_{1:m})] & =  \E_{\bo_{1:m}}\left[\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}f(\b{z};\bo_{1:m})\right\|_2\right]
			 \le \frac{1}{m}\sum_{j=1}^m \E_{\bo_{1:m}}\left[\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}} f(\b{z};\bo_j)\right\|_2\right]\nonumber\\
		      &= \frac{1}{m} \sum_{j=1}^m B_{\b{p},\b{q},\K} = B_{\b{p},\b{q},\K}.\label{eq:L-1}
    \end{align}
 \item \tb{Bound on $B_{\b{p},\b{q},\K}$}: 
 Note that
    \begin{align}
	\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}} f(\b{z};\bo)\right\|_2 &= \sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z})-\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right) \right] \right\|_2\nonumber\\
	&\le \sup_{\b{z}\in conv(\K_{\Delta})}\left( \left\|\nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z}) \right]\right\|_2 + \left\|\nabla_{\b{z}}\left[\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right) \right] \right\|_2 \right)\nonumber\\
        &\le \sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}}\left[ \p^{\b{p},\b{q}}k(\b{z}) \right]\right\|_2 + \sup_{\b{z}\in conv(\K_{\Delta})}\left\|\nabla_{\b{z}}\left[\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right) \right] \right\|_2\nonumber\\
	&= D_{\b{p},\b{q},\K} + \sup_{\b{z}\in conv(\K_{\Delta})}\left\|\nabla_{\b{z}}\left[\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right) \right] \right\|_2.\label{eq:kder:B1}
    \end{align}
    By the homogenity of norms ($\left\|a\b{v}\right\| = |a|\left\|\b{v}\right\|$), the chain rule, and $|h_a(v)|\le 1$ ($\forall a$, $\forall v$)
    \begin{align}
	\left\|\nabla_{\b{z}}\left[\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right) \right] \right\|_2 &= |\bo^{\b{p}+\b{q}}|  \left\| h_{|\b{p}+\b{q}|+1}\left(\bo^T\b{z}\right)\bo \right\|_2  \le |\bo^{\b{p}+\b{q}}| \left\|\bo \right\|_2. \label{eq:kder:B2}
    \end{align}
    Combining Eq.~\eqref{eq:kder:B1} and \eqref{eq:kder:B2} results in the bound
    \begin{align}
     B_{\b{p},\b{q},\K} = \E_{\bo\sim\S}\left[\sup_{\b{z}\in conv(\K_{\Delta})} \left\|\nabla_{\b{z}} f(\b{z};\bo)\right\|_2\right] & \le D_{\b{p},\b{q},\K} + \E_{\bo\sim \S}\left[|\bo^{\b{p}+\b{q}}| \left\|\bo \right\|_2\right]
     = D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}}. \label{eq:L-2}
    \end{align}
\item \tb{Error propagation from the net centers:} We will use the following note to propagate the error from the net centers ($\b{c}_j$, $j=1,\ldots,N$) to an arbitrary $\b{z}\in \K_{\Delta}$ point.
		  Note: If $|\bar{f}(\b{c}_j;\bo_{1:m})|<\frac{\epsilon}{2}$ ($\forall j$) and $L(\bo_{1:m})<\frac{\epsilon}{2r}$, then 
			      \begin{align}
				|\bar{f}(\b{z};\bo_{1:m})| &< \epsilon \quad (\forall \b{z} \in \K_{\Delta}). \label{eq:gbar-small}
			      \end{align}
		  Indeed
			    \begin{align*}
			      \big| |\bar{f}(\b{z};\bo_{1:m})| - \underbrace{|\bar{f}(\b{c}_j;\bo_{1:m})|}_{<\frac{\epsilon}{2}} \big| &\le |\bar{f}(\b{z};\bo_{1:m}) - \bar{f}(\b{c}_j;\bo_{1:m})| \le \underbrace{L(\bo_{1:m})}_{<\frac{\epsilon}{2r}} \underbrace{\left\| \b{z}- \b{c}_j\right\|_2}_{\le r} <  \frac{\epsilon}{2},
			    \end{align*}
			    where we used \eqref{eq:gbar-diff} and our assumptions in the note, thereby yielding \eqref{eq:gbar-small}.
\item \tb{Guaranteeing the conditions of \eqref{eq:gbar-small} with high probability:}
    \begin{compactitem}
	\item Notice that $\E_{\bo\sim \S}[f(\b{z};\bo)]=\b{0}$ ($\forall  \b{z}$). Also since \eqref{eq:moment-constraint-on-g} holds, applying Bernstein's inequality for the 
	individual $\b{c}_j$ points (Lemma~\ref{lemma:Bernstein}; $\xi_n:=f(\b{c}_j;\bo_n)$, $n=1,\ldots,m$; $S:=\sqrt{m}\sigma$) gives that for any $\eta>0$
	      \begin{align}
		  \S^m\left( |\bar{f}(\b{c}_j;\bo_{1:m})| \ge  \frac{\eta \sigma}{\sqrt{m}}\right) \le e^{-\frac{1}{2}\frac{\eta^2}{1+\frac{\eta L}{\sqrt{m}\sigma}}}. \label{eq:Bernstein-eta}
	      \end{align}
	      Setting $\epsilon=\frac{2\eta\sigma}{\sqrt{m}}$, (\ref{eq:Bernstein-eta}) is written as
	      \begin{align*}
		\S^m\left( |\bar{f}(\b{c}_j;\bo_{1:m})| <\frac{\epsilon}{2}\right) \ge  1 - e^{-\frac{1}{2}\frac{\left(\frac{\sqrt{m}\epsilon}{2 \sigma}\right)^2}{1+\frac{\frac{\sqrt{m}\epsilon}{2 \sigma} L}{\sqrt{m}\sigma}}}
		    = 1 - e^{- \frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}}.
	      \end{align*}
    	  By union bounding ($j=1,\ldots,N$), we get
					\begin{align}
					      \S^m\left(\cap_{j=1}^N \left\{|\bar{f}(\b{c}_j;\bo_{1:m})| < \frac{\epsilon}{2}\right\} \right) & \ge 1- N e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}}. \label{eq:condition-1:A}
					  \end{align}

	\item \tb{Condition $L(\bo_{1:m})<\frac{\epsilon}{2r}$}:  Applying Markov's inequality to $L(\bo_{1:m})$ (note that $L(\bo_{1:m})$ is non-negative), for any $t>0$, we obtain
	$$\S^m\left(L(\bo_{1:m})\ge t\right) \le \frac{\E_{\bo_1,\ldots,\bo_m}\left[L(\bo_{1:m})\right]}{t} \le \frac{D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}}}{t},$$
	by invoking \eqref{eq:L-1} and \eqref{eq:L-2}. Choosing $t=\frac{\epsilon}{2r}$, we have
	\begin{equation}
	 \S^m\left(L (\bo_{1:m})< \frac{\epsilon}{2r}\right) \ge 1-\frac{2r}{\epsilon} (D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}}). \label{eq:condition-2} 
	\end{equation}
    \end{compactitem}
 \item  \tb{Final bound for any $r>0$}: By \eqref{eq:condition-1:A} and \eqref{eq:condition-2}, and substituting the explicit form of $N$ in (\ref{eq:cover-nn}), we get
 	    \begin{align}
				  \S^m \left( \sup_{\b{z}\in  \K_{\Delta}} |\bar{f}(\b{z};\bo_{1:m})| < \epsilon\right) &\ge \S^m\left(\left\{L(\bo_{1:m})< \frac{\epsilon}{2r}\right\} \bigcap \cap_{j=1}^N \left\{|\bar{f}(\b{c}_j;\bo_{1:m})| < \frac{\epsilon}{2}\right\} \right)\nonumber\\
				  &\ge 1- \left(\frac{4|\K|}{r}+1\right)^d e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}} -  \frac{2r}{\epsilon} (D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}})
				  \stackrel{(\dagger)}{\ge} 1-c_*-\kappa_1r^{-d}-\kappa_2r,\label{eq:r-matching}
\end{align}
      where we invoked the 
      \begin{align*}
	  \left(\frac{4|\K|}{r}+1\right)^d & = \left[2\left(\frac{\frac{4|\K|}{r}}{2}+\frac{1}{2}\right)\right]^d = 2^d  \left(\frac{\frac{4|\K|}{r}}{2}+\frac{1}{2}\right)^d  \stackrel{(\dagger)}{\le} 2^d \frac{1}{2}
	    \left[\left(\frac{4|\K|}{r}\right)^d + 1^d\right] = 2^{d-1} \left[ \left(\frac{4|\K|}{r}\right)^d + 1 \right]
      \end{align*}
      Jensen's inequality in ($\dagger$), $c_*:=2^{d-1}e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}}$, $\kappa_1:=4^{d}|\K|^dc_*$ and $\kappa_2=\frac{2}{\epsilon} (D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}})$.\vspace{.5mm}\\
  \item \tb{Matching the two terms to choose $r$}: 
      Maximizing w.r.t.~$r$ in (\ref{eq:r-matching})
      \begin{align*}
	f(r) &= \kappa_1 r^{-d} + \kappa_2 r \Rightarrow f'(r) = \kappa_1 (-d)r^{-d-1} + \kappa_2 =0 \Rightarrow  \frac{d \kappa_1}{\kappa_2} = r^{d+1}
      \end{align*}
      we note that $r = \left( \frac{d\kappa_1}{\kappa_2} \right)^{\frac{1}{d+1}}$ maximizes it.
      Using this in (\ref{eq:r-matching}), we have 
      \begin{align*}
       \S^m \left( \sup_{\b{z}\in  \K_{\Delta}} |\bar{f}(\b{z};\bo_{1:m})| \ge \epsilon\right)& \le c_* +\kappa_1 \left( \frac{d\kappa_1}{\kappa_2} \right)^{-\frac{d}{d+1}} + \kappa_2 \left( \frac{d\kappa_1}{\kappa_2} \right)^{\frac{1}{d+1}}
	    =c_*+F_d\kappa_1^{\frac{1}{d+1}} \kappa_2^{\frac{d}{d+1}}\\ 
	    &= 2^{d-1}e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}} + F_d \left[2^{3d-1}|\K|^d e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}} \right]^{\frac{1}{d+1}} \left[ \frac{2}{\epsilon} (D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}}) \right]^{\frac{d}{d+1}}\\
	    &= 2^{d-1}e^{-\frac{m\epsilon^2}{8 \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}} + F_d 2^{\frac{4d-1}{d+1}} \left[ \frac{|\K|(D_{\b{p},\b{q},\K} + E_{\b{p},\b{q}})}{\epsilon} \right]^{\frac{d}{d+1}} e^{-\frac{m\epsilon^2}{8(d+1) \sigma^2 \left(1+\frac{\epsilon L}{2\sigma^2}\right)}},
      \end{align*}
      where $F_d:=d^{-\frac{d}{d+1}}+d^{\frac{1}{d+1}}$.
\end{compactitem}

\subsection{Proof of bounded $\text{supp}(\S)$ $\Rightarrow$ \eqref{eq:moment-constraint-on-g}}\label{lemma:supp(S)-bounded=>moment-constraint-is-OK}
We prove that the boundedness of $\text{supp}(\S)$ implies that of $f$ [see \eqref{eq:g-def}], specifically \eqref{eq:moment-constraint-on-g}.

\emph{Proof}: Indeed, let
\begin{align}
  f(\b{z};\bo) &= \p^{\b{p},\b{q}}k(\b{z}) - \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)
  = \left[\int_{\R^d} \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)\d\S(\bo)\right] - \bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right).\label{eq:g-def}
\end{align}
Applying the triangle inequality and $|h_a(v)| \le 1$ ($\forall a, \forall v$) we have 
\begin{align*}
   |f(\b{z};\bo)| &\le \left|\int_{\R^d} \b{s}^{\b{p}}(-\b{s})^{\b{q}} h_{|\b{p}+\b{q}|}\left(\b{s}^T\b{z}\right)\d\S(\b{s})\right| + \left|\bo^{\b{p}}(-\bo)^{\b{q}} h_{|\b{p}+\b{q}|}\left(\bo^T\b{z}\right)\right|
		  \le \int_{\R^d} \left| \b{s}^{\b{p}}(-\b{s})^{\b{q}} h_{|\b{p}+\b{q}|}\left(\b{s}^T\b{z}\right)\right| \d\S(\b{s}) + \left|\bo^{\b{p}+\b{q}}\right| \nonumber\\
		  &\le \int_{\R^d} \left| \b{s}^{\b{p}+\b{q}}\right| \d\S(\b{s}) + \left|\bo^{\b{p}+\b{q}}\right| =
		  \int_{\text{supp}(\S)} \left| \b{s}^{\b{p}+\b{q}}\right| \d\S(\b{s}) + \left|\bo^{\b{p}+\b{q}}\right| \le 2 \sup_{\b{s}\in \text{supp}(\S)}|\b{s}^{\b{p}+\b{q}}|.
\end{align*}
$K:= \sup_{\b{s}\in \text{supp}(\S)}|\b{s}^{\b{p}+\b{q}}|$ is finite since $\text{supp}(\S)$ is bounded, thus $|f(\b{z};\bo)|$ is bounded.

\section{Supplementary results}\label{sec:suppl:lemmas}
In this section, we present some technical results that are used in
the proofs.\vspace{1mm}\\

\begin{appxlem}[McDiarmid Inequality \cite{taylor04kernel}]\label{lemma:McDiarmid}
Let $(X_i)^m_{i=1}$ be $\Cal{X}$-valued independent random variables. 
Suppose $f: \Cal{X}^m\rightarrow \R$ satisfies the bounded difference property,
\begin{equation}\sup_{u_1,\ldots,u_m,u_r'\in \Cal{X}}\left|f(u_1,\ldots,u_m) - f(u_1,\ldots,u_{r-1},u_r',u_{r+1},\ldots,u_m)\right| \le c_r\,\, (\forall r=1,\ldots,m).\label{eq:bdd}\end{equation}
Then for any $\epsilon>0$, 
\begin{align*}
  \P\left( f(X_1,\ldots,X_m) - \E\left[f(X_1,\ldots,X_m)\right]\ge \epsilon\right) & \le e^{-\frac{2\epsilon^2}{\sum_{r=1}^mc_r^2}}.
\end{align*}
Note: specifically, if $c=c_r$ $(\forall r)$ then applying a $\tau=\frac{2\epsilon^2}{\sum_{r=1}^mc_r^2}=\frac{2\epsilon^2}{mc^2} \Leftrightarrow \epsilon = c \sqrt{\frac{\tau m}{2}}$ reparameterization one gets $\P\left( f(X_1,\ldots,X_m) < \E\left[f(X_1,\ldots,X_m)\right] +  c \sqrt{\frac{\tau m}{2}}\right) \ge 1-e^{-\tau}$.\vspace{1mm}\\
\end{appxlem}

\begin{appxlem}\label{lemma:integral} 
For $a>1$,
$\int^1_0 \sqrt{\log\frac{a}{\epsilon}}\,\d\epsilon\le \sqrt{\log a}+\frac{1}{2\sqrt{\log a}}$.\vspace{-1mm}
\end{appxlem}
\begin{proof}
By change of variables, we have $\int^1_0 \sqrt{\log\frac{a}{\epsilon}}\,d\epsilon=a\int^\infty_{\log a}\sqrt{t}e^{-t}\,dt$. Applying partial integration, we have
$$\int^\infty_{\log a}\sqrt{t}e^{-t}\,\d t=[\sqrt{t}e^{-t}]^{\log a}_{\infty}+\int^\infty_{\log a}\frac{1}{2\sqrt{t}}e^{-t}\,\d t\le\frac{\sqrt{\log a}}{a}+\frac{1}{2\sqrt{\log a}}\int^\infty_{\log a}e^{-t}\,\d t=\frac{\sqrt{\log a}}{a}+\frac{1}{2a\sqrt{\log a}},$$
thereby yields the result.
\end{proof}

\begin{appxlem}[Bernstein inequality \cite{yurinsky95sums}]\label{lemma:Bernstein}
Let $\xi\in\R$ be a random variable, $\E_{\xi\sim \P}[\xi]=0$, and assume that $\exists L>0, S>0$ satisfying 
\begin{align*}
\sum_{j=1}^m\E_{\xi_j\sim \P}\left[|\xi_j|^M\right]\le \frac{M!S^2 L^{M-2}}{2}\quad (\forall M \ge 2),
\end{align*}
where $(\xi_j)_{j=1}^m\stackrel{i.i.d.}{\sim}\P$. 
Then for any $0<m\in\N$, $\eta>0$,
\begin{align*}
\P^m\left(\left|\sum_{j=1}^m \xi_j\right| \ge \eta S\right)  \le e^{-\frac{1}{2}\frac{\eta^2}{1+\frac{\eta L}{S}}}.
\end{align*}
\end{appxlem}


\begin{appxlem}[$L^r$ norm as countable supremum]\label{lemma:Lr-as-countable-sup}
Assume that $1< \tilde{r} < \infty$. If $(X,\mathscr{A},\mu)$, $\mu(X)<\infty$, $\frac{1}{r}+ \frac{1}{\tilde{r}} = 1$, then 
$\left[L^{\tilde{r}}(X,\mathscr{A},\mu)\right]^* = \left\{F_f: f\in L^{r}(X,\mathscr{A},\mu)\right\}$, where $F_f(u)  = \int_X uf \d\mu$,
and $\left\|f\right\|_{L^{r}} = \left\|F_f\right\|(=\sup_{\left\|g\right\|_{L^{\tilde{r}}}=1}|F_f(g)|)$; see \cite[Theorem~4.1]{stein11functional}. Specifically, if 
$X=\K\subseteq \R^d$ compact and it is endowed with the Borel $\sigma$-algebra, then by the separability of $\K$, $L^{\tilde{r}}(\K)$ is also separable \cite[Prop.~3.4.5]{cohn13measure} since the Borel $\sigma$-algebra is countably generated \cite[page~17 (vol.~2)]{bogachev07measure}, thus there exists a countable 
$\G\subseteq L^{\tilde{r}}(\K)$, \cite[Lemma 6.7]{carothers04short} such that $\left\|g\right\|_{ L^{\tilde{r}(\K)}}=1$ ($\forall g\in \G$) and $\left\|F_f\right\| =  \sup_{g\in \G}|F_f(g)|$.

Note: the $\sigma$-algebra of \emph{Lebesgue} measurable sets is typically \emph{not} countably generated \cite[page~106 (vol.~I)]{bogachev07measure}.
 \end{appxlem}









bu1.bbl
\begin{thebibliography}{10}

\bibitem{alaoui15fast}
A.~E. Alaoui and M. Mahoney.
\newblock Fast randomized kernel ridge regression with statistical guarantees.
\newblock In {\em NIPS}, 2015.

\bibitem{chaudhuri11differentially}
K. Chaudhuri, C. Monteleoni, and A.~D. Sarwate.
\newblock Differentially private empirical risk minimization.
\newblock {\em Journal of Machine Learning Research}, 12:1069--1109, 2011.

\bibitem{cotter11explicit}
A. Cotter, J. Keshet, and N. Srebro.
\newblock Explicit approximations of the {G}aussian kernel.
\newblock Technical report, 2011.
\newblock \url{http://arxiv.org/pdf/1109.4603.pdf}.

\bibitem{csorgo81multivariate}
S. Cs{\"o}rg{\H{o}}.
\newblock Multivariate empirical characteristic functions.
\newblock {\em Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie und Verwandte
  Gebiete}, 55:203--229, 1981.

\bibitem{csorgo83howlong}
S. Cs{\"o}rg{\H{o}} and V. Totik.
\newblock On how long interval is the empirical characteristic function
  uniformly consistent?
\newblock {\em Acta Scientiarum Mathematicarum}, 45:141--149, 1983.

\bibitem{drineas05nystrom}
P. Drineas and M.~W. Mahoney.
\newblock On the {N}ystr{\"{o}}m method for approximating a {G}ram matrix for
  improved kernel-based learning.
\newblock {\em Journal of Machine Learning Research}, 6:2153--2175, 2005.

\bibitem{feuerverger77empirical}
A. Feuerverger and R.~A. Mureika.
\newblock The empirical characteristic function and its applications.
\newblock {\em Annals of Statistics}, 5(1):88--98, 1977.

\bibitem{folland99real}
G.~B. Folland.
\newblock {\em Real Analysis: Modern Techniques and Their Applications}.
\newblock Wiley-Interscience, 1999.

\bibitem{kulis12kernelized}
B. Kulis and K. Grauman.
\newblock Kernelized locality-sensitive hashing.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  34:1092--1104, 2012.

\bibitem{lopezpaz15towards}
D. Lopez-Paz, K. Muandet, B. Sch{\"o}lkopf, and I. Tolstikhin.
\newblock Towards a learning theory of cause-effect inference.
\newblock {\em JMLR W\&CP -- ICML}, pages 1452--1461, 2015.

\bibitem{maji13efficient}
S. Maji, A.~C. Berg, and J. Malik.
\newblock Efficient classification for additive kernel {SVM}s.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  35:66--77, 2013.

\bibitem{oliva15fast}
J. Oliva, W. Neiswanger, B. P{\'o}czos, E. Xing, and J. Schneider.
\newblock Fast function to function regression.
\newblock {\em JMLR W\&CP -- AISTATS}, pages 717--725, 2015.

\bibitem{rahimi07random}
A. Rahimi and B. Recht.
\newblock Random features for large-scale kernel machines.
\newblock In {\em NIPS}, pages 1177--1184, 2007.

\bibitem{rahimi08uniform}
A. Rahimi and B. Recht.
\newblock Uniform approximation of functions with random bases.
\newblock In {\em Allerton}, pages 555--561, 2008.

\bibitem{rosasco10regularization}
L. Rosasco, M. Santoro, S. Mosci, A. Verri, and S. Villa.
\newblock A regularization approach to nonlinear variable selection.
\newblock {\em JMLR W\&CP -- AISTATS}, 9:653--660, 2010.

\bibitem{rosasco13nonparametric}
L. Rosasco, S. Villa, S. Mosci, M. Santoro, and A. Verri.
\newblock Nonparametric sparsity and regularization.
\newblock {\em Journal of Machine Learning Research}, 14:1665--1714, 2013.

\bibitem{scholkopf02learning}
B. Sch{\"o}lkopf and A.~J. Smola.
\newblock {\em Learning with Kernels: Support Vector Machines, Regularization,
  Optimization, and Beyond}.
\newblock MIT Press, 2002.

\bibitem{shi10hermite}
L. Shi, X. Guo, and D.-X. Zhou.
\newblock Hermite learning with gradient data.
\newblock {\em Journal of Computational and Applied Mathematics},
  233:3046--3059, 2010.

\bibitem{shi09hash}
Q. Shi, J. Petterson, G. Dror, J. Langford, A. Smola, A. Strehl, and V.
  Vishwanathan.
\newblock Hash kernels.
\newblock {\em AISTATS}, 5:496--503, 2009.

\bibitem{sriperumbudur14density}
B.~K. Sriperumbudur, K. Fukumizu, A. Gretton, A. Hyv{\"a}rinen, and R. Kumar.
\newblock Density estimation in infinite dimensional exponential families.
\newblock Technical report, 2014.
\newblock \url{http://arxiv.org/pdf/1312.3516.pdf}.

\bibitem{strathmann15gradient}
H. Strathmann, D. Sejdinovic, S. Livingstone, Z. Szab{\'o}, and A. Gretton.
\newblock Gradient-free {H}amiltonian {M}onte {C}arlo with efficient kernel
  exponential families.
\newblock In {\em NIPS}, 2015.

\bibitem{sutherland15error}
D.~J. Sutherland and J. Schneider.
\newblock On the error of random {F}ourier features.
\newblock In {\em UAI}, pages 862--871, 2015.

\bibitem{vedaldi12efficient}
A. Vedaldi and A. Zisserman.
\newblock Efficient additive kernels via explicit feature maps.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  34:480--492, 2012.

\bibitem{wendland05scattered}
H. Wendland.
\newblock {\em Scattered Data Approximation}.
\newblock Cambridge University Press, 2005.

\bibitem{Williams-01}
C.~K.~I. Williams and M. Seeger.
\newblock Using the {N}ystr{\"{o}}m method to speed up kernel machines.
\newblock In {\em NIPS}, pages 682--688, 2001.

\bibitem{ying12learning}
Y. Ying, Q. Wu, and C. Campbell.
\newblock Learning the coordinate gradients.
\newblock {\em Advances in Computational Mathematics}, 37:355--378, 2012.

\bibitem{yukich87some}
J.~E. Yukich.
\newblock Some limit theorems for the empirical process indexed by functions.
\newblock {\em Probability Theory and Related Fields}, 74:71--90, 1987.

\bibitem{zhou08derivative}
D.-X. Zhou.
\newblock Derivative reproducing properties for kernel methods in learning
  theory.
\newblock {\em Journal of Computational and Applied Mathematics}, 220:456--463,
  2008.

\end{thebibliography}

bu2.bbl
\begin{thebibliography}{10}

\bibitem{bogachev07measure}
V.~I. Bogachev.
\newblock {\em Measure Theory}.
\newblock Springer, 2007.

\bibitem{bousquet03new}
O. Bousquet.
\newblock New approaches to statistical learning theory.
\newblock {\em Annals of the Institute of Statistical Mathematics},
  55:371--389, 2003.

\bibitem{carothers04short}
N.~L. Carothers.
\newblock {\em A Short Course on Banach Space Theory}.
\newblock Cambridge University Press, 2004.

\bibitem{cohn13measure}
D.~L. Cohn.
\newblock {\em Measure Theory: Second Edition}.
\newblock Birkh{\"a}user Basel, 2013.

\bibitem{ledoux02probability}
M. Ledoux and M. Talagrand.
\newblock {\em Probability in {B}anach Spaces -- Isoperimetry and Processes}.
\newblock Springer-Verlag, 2002.

\bibitem{lindenstrauss79classical}
J. Lindenstrauss and L. Tzafriri.
\newblock {\em Classical {B}anach Spaces {II} -- Function Spaces}.
\newblock Springer-Verlag, 1979.

\bibitem{taylor04kernel}
J. Shawe-Taylor and N. Cristianini.
\newblock {\em Kernel Methods for Pattern Analysis}.
\newblock Cambridge University Press, 2004.

\bibitem{stein11functional}
E.~M. Stein and R. Shakarchi.
\newblock {\em Functional Analysis: Introduction to Further Topics in
  Analysis}.
\newblock Princeton University Press, 2011.

\bibitem{steinwart08support}
I. Steinwart and A. Christmann.
\newblock {\em Support Vector Machines}.
\newblock Springer, 2008.

\bibitem{geer09empirical}
S.~A. van~de Geer.
\newblock {\em Empirical Processes in {M}-Estimation}.
\newblock Cambridge University Press, 2009.

\bibitem{Vaart-96}
A.~W. van~der Vaart and J.~A. Wellner.
\newblock {\em Weak Convergence and Empirical Processes}.
\newblock Springer-Verlag, 1996.

\bibitem{yurinsky95sums}
V. Yurinsky.
\newblock {\em Sums and Gaussian Vectors}.
\newblock Springer, 1995.

\end{thebibliography}
