# Pairwise Ranking with Gaussian Kernels†00footnotetext: † The work described
in this paper is supported by the National Natural Science Foundation of China
(Grants Nos.12171039 and 12061160462) and Shanghai Science and Technology
Program [Project Nos. 21JC1400600 and 20JC1412700]. Email addresses:
<EMAIL_ADDRESS>(G. Lei<EMAIL_ADDRESS>(L. Shi).

Guanhang Lei  School of Mathematical Sciences, ShanghaiKey Laboratory for
Contemporary Applied MathematicsFudan University, Shanghai, 200433, P. R.
China  Lei Shi  School of Mathematical Sciences, ShanghaiKey Laboratory for
Contemporary Applied MathematicsFudan University, Shanghai, 200433, P. R.
China

###### Abstract

Regularized pairwise ranking with Gaussian kernels is one of the cutting-edge
learning algorithms. Despite a wide range of applications, a rigorous
theoretical demonstration still lacks to support the performance of such
ranking estimators. This work aims to fill this gap by developing novel oracle
inequalities for regularized pairwise ranking. With the help of these oracle
inequalities, we derive fast learning rates of Gaussian ranking estimators
under a general box-counting dimension assumption on the input domain combined
with the noise conditions or the standard smoothness condition. Our
theoretical analysis improves the existing estimates and shows that a low
intrinsic dimension of input space can help the rates circumvent the curse of
dimensionality.

Keywords and phrases: Pairwise ranking, Oracle inequality, Pairwise Gaussian
kernel, Box-counting dimension, Learning rates

##  1 Introduction

Ranking a set of objects based on their underlying utility, relevance, or
quality is an important topic in statistical inference. It has been an intense
recent study in various fields as diverse as economics, information retrieval,
advertising, and collaborative filtering, see, e.g., [45, 20, 8]. Ranking is
closely related to classification, which can also be formulated as a
supervised learning problem. However, they are essentially different because
ranking aims at the correct ordering of objects rather than the correct
prediction of their categories. This paper considers the _pairwise ranking_
problem, which involves comparing two objects. Generally, we denote the data
relevant to one single object as $(x,y)$, where $x$ is a $d$-dimensional
feature vector belonging to a compact set $\mathcal{X}\subset\mathbb{R}^{d}$
and $y\in\mathcal{Y}$ is the label of the object. Here
$\mathcal{Y}\subset\mathbb{R}$ consists of either discrete or continuous
values. For any two distinct objects, described by $z=(x,y)$ and
$z^{\prime}=(x^{\prime},y^{\prime})$, we assign a relation of order according
to their labels: $z$ ranking higher than $z^{\prime}$ is equivalent to
$y>y^{\prime}$. In a pairwise ranking task, we predict the ordering between
objects based on their features $x$ and $x^{\prime}$. To this end, a bivariate
function $f:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$, called a _ranking
rule_ , is introduced to make predictions. Namely, if $f(x,x^{\prime})\geq 0$
then we predict that $y>y^{\prime}$ implying $f$ ranks $z$ higher than
$z^{\prime}$ (here we break tie when $f(x,x^{\prime})=0$ in favor of
$y>y^{\prime}$). Let $P$ be a probability distribution on
$\mathcal{Z}:=\mathcal{X}\times\mathcal{Y}$. We assume that the objects are
randomly selected, meaning that they are described by independent and
identically distributed (i.i.d.) random samples of distribution $P$. The
predictive performance of a ranking rule $f$ is measured by the _ranking risk_
, given by

$\begin{split}\mathcal{R}(f):=&P\left(\left\\{z=(x,y)\in\mathcal{Z},z^{\prime}=(x^{\prime},y^{\prime})\in\mathcal{Z}\mid
y>y^{\prime},f(x,x^{\prime})<0\right\\}\right)\\\
&+P\left(\left\\{z=(x,y)\in\mathcal{Z},z^{\prime}=(x^{\prime},y^{\prime})\in\mathcal{Z}\mid
y<y^{\prime},f(x,x^{\prime})\geq 0\right\\}\right),\end{split}$ (1.1)

or equivalently, the _excess ranking risk_

$\mathcal{E}(f):=\mathcal{R}(f)-\inf\left\\{\mathcal{R}(g)\mid\textrm{$g:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$
is Borel measurable}\right\\}.$ (1.2)

In this paper, we construct ranking rules through a regularized pairwise
learning scheme with a loss
$\phi:\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}\to[0,\infty)$ and Gaussian
kernels. We call $\phi$ a margin-based loss if $\phi$ is defined through a
margin-based loss for classification, namely,
$\phi(y,y^{\prime},t)=\psi(\mathrm{sgn}(y-y^{\prime})t)$ where
$\psi:\mathbb{R}\to[0,\infty)$ is taken to be a margin-based classification
loss (cf. [51, 26, 5]). Here for $t\in\mathbb{R}$, $\mathrm{sgn}(t)=1$ if
$t>0$, $\mathrm{sgn}(t)=-1$ if $t<0$, and $\mathrm{sgn}(t)=0$ if $t=0$.
Typical choices of $\psi$, which will be the prime consideration in this work,
are the hinge loss $\psi_{\mathrm{hinge}}(t):=\max\left\\{1-t,0\right\\}$ and
the square loss $\psi_{\mathrm{square}}(t):=(1-t)^{2}$. Let
$\mathcal{X}^{2}:=\mathcal{X}\times\mathcal{X}$. The _pairwise Gaussian
kernel_ with variance $\sigma>0$ is a function on
$\mathcal{X}^{2}\times\mathcal{X}^{2}$ given by

$\begin{split}K^{\sigma}((x,x^{\prime}),(u,u^{\prime}))&:=\frac{1}{2}\exp\left(-\frac{\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)\\\
&\qquad-\frac{1}{2}\exp\left(-\frac{\|(x^{\prime},x)-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right),\end{split}$
(1.3)

where $\|\cdot\|_{2}$ denotes the usual Euclidean norm. One can verify that
$K^{\sigma}$ is continuous and positive semi-definite (thus is symmetric) on
$\mathcal{X}^{2}\times\mathcal{X}^{2}$. According to [4], $K^{\sigma}$
uniquely defines a reproducing kernel Hilbert space (RKHS)
$\mathcal{H}_{K^{\sigma}}$. Concretely, let
$K^{\sigma}_{(u,u^{\prime})}:\mathcal{X}^{2}\to\mathbb{R}$ be a function
defined by
$K^{\sigma}_{(x,x^{\prime})}(\cdot,\cdot):=K^{\sigma}((x,x^{\prime}),(\cdot,\cdot))$
for any $(x,x^{\prime})\in\mathcal{X}^{2}$. The RKHS
$\mathcal{H}_{K^{\sigma}}$ induced by $K^{\sigma}$ is the completion of the
linear span of
$\left\\{K^{\sigma}_{(x,x^{\prime})}\mid(x,x^{\prime})\in\mathcal{X}^{2}\right\\}$
with inner product denoted by $\langle\cdot,\cdot\rangle_{K^{\sigma}}$
satisfying the reproducing property, that is, $\langle
K^{\sigma}_{(x,x^{\prime})},f\rangle_{K^{\sigma}}=f(x,x^{\prime})$ for any
$(x,x^{\prime})\in\mathcal{X}^{2}$ and all $f\in\mathcal{H}_{K^{\sigma}}$.
Moreover, $\mathcal{H}_{K^{\sigma}}$ consists of skew-symmetric continuous
functions on $\mathcal{X}^{2}$, i.e.,
$f(x,x^{\prime})=-f(x^{\prime},x),\forall f\in\mathcal{H}_{K^{\sigma}}$. The
construction of $K^{\sigma}$ follows the idea of [32], which introduces the
so-called intransitive kernels on pairs of data to characterize the pairwise
skew-symmetric relation. Let $\|\cdot\|_{K^{\sigma}}$ denote the norm of
$\mathcal{H}_{K^{\sigma}}$ induced by the inner product. Given an i.i.d.
sample ${\mathbf{z}}:=\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{n}$ of $P$, the
pairwise learning algorithm seeks ranking rules in $\mathcal{H}_{K^{\sigma}}$
through solving an optimization problem of the form

$f_{\mathbf{z}}:=f^{\phi}_{\mathbf{z},\sigma,\lambda}\in\mathop{\arg\min}_{f\in\mathcal{H}_{K^{\sigma}}}\left\\{\mathcal{R}^{\phi}_{\mathbf{z}}(f)+\lambda\|f\|^{2}_{K^{\sigma}}\right\\},$
(1.4)

where $\lambda>0$ is a tuning parameter and
$\mathcal{R}^{\phi}_{\mathbf{z}}(f)$ denotes the _empirical $\phi$-ranking
risk_ given by

$\begin{split}\mathcal{R}^{\phi}_{\mathbf{z}}(f)&:=\mathbb{E}_{\mathbf{z}}\phi(Y,Y^{\prime},f(X,X^{\prime}))\\\
&=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\phi\left(Y_{i},Y_{j},f(X_{i},X_{j})\right).\end{split}$ (1.5)

When using a margin-based loss, $\mathcal{R}^{\phi}_{\mathbf{z}}(f)$ takes the
following form

$\begin{split}\mathcal{R}^{\phi}_{\mathbf{z}}(f)&=\mathbb{E}_{\mathbf{z}}\psi(\mathrm{sgn}(Y-Y^{\prime})f(X,X^{\prime}))\\\
&=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\psi\left(\mathrm{sgn}(Y_{i}-Y_{j})f(X_{i},X_{j})\right).\end{split}$ (1.6)

Choosing $\mathcal{H}_{K^{\sigma}}$ as the family of candidate ranking rules
naturally imposes the skew-symmetry restriction on $f_{\mathbf{z}}$, which
will lead to ordering predictions capable of guaranteeing the reciprocal
relations from data. Note that $\mathcal{R}^{\phi}_{\mathbf{z}}(f)$ is the
empirical analogy of _$\phi$ -ranking risk_

$\begin{split}\mathcal{R}^{\phi}(f):&=\mathbb{E}\phi\left(Y,Y^{\prime},f(X,X^{\prime})\right)\\\
&=\int_{\mathcal{Z}}\int_{\mathcal{Z}}\phi\left(y,y^{\prime},f(x,x^{\prime})\right)dP(x,y)dP(x^{\prime},y^{\prime}).\end{split}$
(1.7)

Thus, the _excess $\phi$-ranking risk_ is defined by

$\mathcal{E}^{\phi}(f):=\mathcal{R}^{\phi}(f)-\inf\left\\{\mathcal{R}^{\phi}(g)\mid\textrm{$g:\mathcal{X}^{2}\to\mathbb{R}$
is Borel measurable}\right\\}.$ (1.8)

To a certain extent, it also reflects the generalization performance of the
ranking rule $f$.

The algorithm (1.4), or more precisely, the kernel-based regularized empirical
risk minimization, is one of the learning schemes that have recently drawn
much theoretical attention. Its cutting-edge empirical performance in
applications, relatively simple implementation, and, last but not least, its
flexibility all contribute to the grown interest. The flexibility of algorithm
(1.4) is made possible by its two main ingredients, namely the RKHS
$\mathcal{H}_{K^{\sigma}}$ and the loss function $\phi$. To be more specific,
the loss function can be used to model the learning target, while
$\mathcal{H}_{K^{\sigma}}$ with varying width $\sigma$ adapts to the
smoothness of the target function, which incorporates the information of the
distribution and the input domain. It is worthwhile to note that kernels can
be defined on arbitrary input domains, allowing them to handle various types
of data in addition to standard $\mathbb{R}^{d}$-valued data. For example,
using a bivariate kernel on ${\mathcal{X}}\times{\mathcal{X}}$, we can define
a general pairwise kernel $K$ to model reciprocal or antisymmetric relations.
Concretely, let $G:{\cal X}\times{\cal X}\rightarrow\mathbb{R}$ be a positive
semi-definite kernel and $({\cal H}_{G},\langle\cdot,\cdot\rangle_{G})$ be its
associated RKHS. A pairwise kernel $K:{\cal X}^{2}\times{\cal
X}^{2}\rightarrow\mathbb{R}$ can be defined by

$\displaystyle K((x,x^{\prime}),(u,u^{\prime}))=\langle
G_{x}-G_{x^{\prime}},G_{u}-G_{u^{\prime}}\rangle_{G},$

where $G_{x}:=G(x,\cdot)$, $x\in{\cal X}.$ One may refer to [32, 29] for more
details about these specific pairwise kernels. Moreover, the optimization
problem related to algorithm (1.4), which can reduce to a convex quadratic
optimization problem, are well understood for widely used loss functions such
as the hinge loss and the square loss, see, e.g., [15, 39].

One of the main topics in theoretical studies on nonparametric ranking methods
is the _learning rates_ , i.e., the convergence rates of excess ranking error
or excess $\phi$-ranking risk, which describe their ranking performance on
specific classes of distributions. Therefore, more and more effort has been
put into deriving well-established learning rates for various ranking
algorithms. One can refer to [12, 33, 10, 50, 25] and references therein for
some recent progress. However, there is little known about under which
nontrivial conditions we can obtain fast learning rates. In this paper, we
introduce suitable noise conditions in pairwise ranking and employ local
Rademacher analysis to establish tight learning rates of algorithm (1.4). Our
methodology combines the local Rademacher averages with the theory of
U-statistics, which incorporates peeling and symmetrization tricks as well as
a contraction principle for U-processes. Our work is also motivated by the
recent work of [18] in which the authors theoretically analyze the performance
of Gaussian support vector machines under an assumption of a low intrinsic
dimension of the input domain. As far as we know, our paper is the first to
consider the learning behavior of regularized pairwise ranking with Gaussian
kernels. This is in contrast with existing literature, which either only
considers ranking with unregularized empirical risk minimization, e.g., [12,
33], or only handles the case, where the kernel is fixed during the training
process, e.g., [10, 52, 25, 44]. We discuss the findings of these articles and
compare them to our results in Section 3. Our main contributions are
summarized as follows.

  * •

We establish an oracle inequality to bound the excess $\phi$-ranking risk of
the estimators produced by regularized empirical risk minimization (2.1) with
a general pairwise kernel $K$ (see Theorem 1). Our conclusion is based on a
capacity assumption, which requires the RKHS $\mathcal{H}_{K}$ to satisfy the
empirical entropy condition (see Assumption 2). This well-established
inequality deals with the stochastic part of the convergence analysis and
provides a framework for bounding the excess $\phi$-ranking risk. Directly
applying this inequality to the marginal-based loss refines the previous
analysis of regularized ranking with general pairwise kernels and yields the
best learning rates so far (see Theorem 2 and Section 3 for detailed
comparisons).

  * •

Inspired by the analysis of support vector machine for classification, see,
e.g., [36], we introduce two noise conditions in the pairwise ranking setting.
The first condition describes the amount of noise in the labels, which is
analogous to Tsybakov’s noise condition in binary classification (see
Assumption 4). This condition enables us to establish an elegant calibration
inequality that bounds the excess ranking risk by their excess $\phi$-ranking
risk, and a refined variance bound for marginal-based losses which further
improves the stochastic part of the analysis. The second condition is a
geometric assumption for distributions that allows us to estimate the
approximation properties of Gaussian kernels (see Assumption 5 and Subsection
5.2). Both of these two conditions play pivotal roles in deriving fast
learning rates.

  * •

We obtain the learning rates of the Gaussian regularized ranking algorithm
(1.4) under a general box-counting dimension assumption on the input domain
combined with the noise conditions or the standard regularity condition (see
Theorem 3 and Theorem 4). Specifically, we first estimate the capacity of
pairwise Gaussian kernel space $\mathcal{H}_{K^{\sigma}}$ under the assumption
that the marginal of the data generating distribution on the input space
$\mathcal{X}\subset\mathbb{R}^{d}$ is supported on a set of upper box-counting
dimension $\varrho\in(0,d]$. Then, we derive approximation error bounds for
the hinge loss under noise conditions and the square loss under the Besov
smoothness. Finally, we apply the well-established oracle inequality and
calibration inequality to derive fast learning rates for the excess ranking
risk. We show that a low intrinsic dimension of input space can help the rates
circumvent the curse of dimensionality.

The rest of this paper is organized as follows. In Section 2, we first
introduce basic notations and necessary assumptions. Then we present the main
results of this paper, including a general oracle inequality for excess
$\phi$-ranking risk and its application to Gaussian ranking estimators (1.4)
with hinge loss and square loss. Section 3 provides an overview of related
work and compares our results with other contributions on pairwise ranking.
Section 4 presents a detailed proof of the general oracle inequality
established in Theorem 1. In Section 5, we apply the oracle inequality to
derive learning rates for Gaussian ranking estimators with hinge loss and
square loss, which gives proofs of Theorem 3 and Theorem 4. Section 4 and
Section 5 also include some preliminary estimates that deserve attention in
their own right.

##  2 Main Results

In this section, we state our main results. Let
$(\mathcal{H}_{K},\langle\cdot,\cdot\rangle_{K})$ be an RKHS consisting of
skew-symmetric functions on $\mathcal{X}^{2}:=\mathcal{X}\times\mathcal{X}$
which is induced by a positive semi-definite kernel
$K:\mathcal{X}^{2}\times\mathcal{X}^{2}\to\mathbb{R}$. The first result is an
oracle inequality established in Theorem 1, providing upper bounds for excess
$\phi$-ranking risk of the regularized estimator

$f_{\mathbf{z}}:=f^{\phi}_{\mathbf{z},\lambda}\in\mathop{\arg\min}_{f\in\mathcal{H}_{K}}\left\\{\mathcal{R}^{\phi}_{\mathbf{z}}(f)+\lambda\|f\|^{2}_{K}\right\\},$
(2.1)

where $\lambda>0$,
$\phi:\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}\to[0,\infty)$ is a general
loss function and $\mathcal{R}^{\phi}_{\mathbf{z}}(f)$ is defined by (1.5).
Hereinafter, we will use $f_{\mathbf{z}}$ to denote either
$f^{\phi}_{\mathbf{z},\lambda}$ in (2.1) or
$f^{\phi}_{\mathbf{z},\sigma,\lambda}$ in (1.4) which will be specified in the
context. The oracle inequalities have been extensively studied in the
literature of nonparametric statistics (see [21] and references therein). An
oracle inequality provides bounds on the risk of a statistical estimator
compared with the one called an oracle that has an infinite amount of
observation and minimizes the population risk over a specific function class.
Recall that the $\phi$-ranking risk $\mathcal{R}^{\phi}(f)$ is given by (1.7).
The oracle in our setting is the infimum that achieves
$\min_{f\in\mathcal{H}_{K}}\lambda\|f\|^{2}_{K}+\mathcal{R}^{\phi}(f)$. The
oracle inequality bounds the excess $\phi$-ranking risk and can be used to
establish both consistency and learning rates for the ranking algorithm. We
give a literature review on the existing oracle inequalities for different
ranking algorithms in Section 3.

To state the oracle inequality for $f_{\mathbf{z}}$ defined by (2.1), we
introduce some necessary notations and assumptions. Define the _Bayes
$\phi$-ranking rule_ as

$f^{*}_{\phi}:=\mathop{\arg\min}\big{\\{}\mathcal{R}^{\phi}(f)\mid\textrm{$f:\mathcal{X}^{2}\to\mathbb{R}$
is Borel measurable}\big{\\}}.$ (2.2)

In the following, the terminology “measurable” means “Borel measurable” unless
otherwise specified. Given a measurable function
$f:\mathcal{X}^{2}\to\mathbb{R}$, define
$\phi_{f}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ and
$Q\phi_{f}:\mathcal{Z}\to\mathbb{R}$ by

$\displaystyle\phi_{f}(z,z^{\prime})$
$\displaystyle:=\phi(y,y^{\prime},f(x,x^{\prime})),$ (2.3) $\displaystyle
Q\phi_{f}(z)$
$\displaystyle:=\mathbb{E}[\phi_{f}(z,Z^{\prime})]=\int_{\mathcal{Z}}\phi\left(y,y^{\prime},f(x,x^{\prime})\right)dP(x^{\prime},y^{\prime}).$
(2.4)

We then introduce the truncation operation, allowing us to derive Bernstein
conditions of sup-norm bound and variance bound for the truncated random
variables, which is essential to establish tight concentration inequalities
and derive fast learning rates. We say that the loss function
$\phi:\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}\to[0,\infty)$ can be
truncated at $M>0$, if for all
$(y,y^{\prime},t)\in\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}$, there holds
$\phi(y,y^{\prime},\pi(t))\leq\phi(y,y^{\prime},t)$, where

$\pi(t):=\begin{cases}-M&t<-M\\\ t&t\in[-M,M]\\\ M&t>M,\end{cases}$

denotes the truncated value of $t$ at $\pm M$. For any
$f:\mathcal{X}^{2}\to\mathbb{R}$, $\pi(f)$ denotes the truncation of $f$ onto
$[-M,M]$ which is given by
$\pi(f)(x,x^{\prime}):=\pi(f(x,x^{\prime})),\forall(x,x^{\prime})\in\mathcal{X}^{2}$.
The idea of truncation has already been used in the literature of binary
classification, see e.g., [16, 36]. We first give the following assumption on
the general loss $\phi$.

######  Assumption 1.

The loss $\phi:\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}\to[0,\infty)$ can
be truncated at some $M>0$ and for all
$(y,y^{\prime})\in\mathcal{Y}\times\mathcal{Y}$,
$\phi(y,y^{\prime},\cdot):\mathbb{R}\to[0,\infty)$ is convex and locally
$L$-Lipschitz on $[-M,M]$. The Bayes $\phi$-ranking rule $f^{*}_{\phi}$
defined by (2.2) is measurable and skew-symmetric. For any skew-symmetric
function $f$, $\phi_{f}$ defined by (2.3) satisfies

$\phi_{f}(z,z^{\prime})=\phi_{f}(z^{\prime},z),\quad\forall(z,z^{\prime})\in\mathcal{Z}\times\mathcal{Z}.$

Furthermore, there exist constants $B>0,\tau\in[0,1]$ and $V\geq B^{2-\tau}$
such that

$\phi(y,y^{\prime},t)\leq
B,\quad\forall(y,y^{\prime},t)\in\mathcal{Y}\times\mathcal{Y}\times[-M,M]$
(2.5)

and for all measurable and skew-symmetric $f:\mathcal{X}^{2}\to\mathbb{R}$,
there holds

$\mathbb{E}(Q\phi_{\pi(f)}-Q\phi_{f^{*}_{\phi}})^{2}\leq
V\big{(}\mathbb{E}(Q\phi_{\pi(f)}-Q\phi_{f^{*}_{\phi}})\big{)}^{\tau},$ (2.6)

where $Q\phi_{\pi(f)}$ and $Q\phi_{f^{*}_{\phi}}$ are defined through (2.4).

Next, we introduce a capacity assumption on $\mathcal{H}_{K}$ which is
described by the covering number or, equivalently, the entropy number of the
unit norm ball in $\mathcal{H}_{K}$.

######  Definition 1.

Let $(\mathcal{T},\mathrm{d})$ be a pseudo-metric space and $\varepsilon>0$.
We call $\mathcal{S}\subset\mathcal{T}$ an $\varepsilon$-net of $\mathcal{T}$,
if for all $t\in\mathcal{T}$ there exists an $s\in\mathcal{S}$ with
$\mathrm{d}(s,t)\leq\varepsilon$. The _$\varepsilon$ -covering number_ of
$(\mathcal{T},\mathrm{d})$ is defined by

$\mathcal{N}(\mathcal{T},\mathrm{d},\varepsilon):=\inf\big{\\{}|\mathcal{S}|:\mathcal{S}\subset\mathcal{T}\text{
and }\mathcal{S}\text{ is an }\varepsilon\text{-net of }\mathcal{T}\big{\\}},$

where $\inf\emptyset=\infty$. For $i\in\mathbb{N}$, the _$i$ -th entropy
number_ of $(\mathcal{T},\mathrm{d})$ is defined by

$e_{i}(\mathcal{T},\mathrm{d}):=\inf\bigg{\\{}\text{$\varepsilon>0:\exists
s_{1},\ldots,s_{2^{i-1}}\in\mathcal{T}$ such that
$\mathcal{T}\subset\bigcup_{j=1}^{2^{i-1}}\mathcal{B}_{\mathrm{d}}(s_{j},\varepsilon)$}\bigg{\\}},$

where
$\mathcal{B}_{\mathrm{d}}(s,\varepsilon):=\big{\\{}t\in\mathcal{T}:\mathrm{d}(t,s)\leq\varepsilon\big{\\}}$
denotes the closed ball with center $s\in\mathcal{T}$ and radius
$\varepsilon$. In particular, if $(\mathcal{T},\mathrm{d})$ is a subspace of a
normed space $(\mathcal{F},\|\cdot\|_{\mathcal{F}})$ and the metric
$\mathrm{d}$ is given by $\mathrm{d}(s,t):=\|s-t\|_{\mathcal{F}},\forall
s,t\in\mathcal{T}$, we write
$\mathcal{N}(\mathcal{T},\|\cdot\|_{\mathcal{F}},\varepsilon):=\mathcal{N}(\mathcal{T},\mathrm{d},\varepsilon)$.
Moreover, if $S:\mathcal{F}\to\mathcal{F}^{\prime}$ is a bounded, linear
operator between the normed spaces $\mathcal{F}$ and $\mathcal{F}^{\prime}$,
we write
$e_{i}(S):=e_{i}(S\mathcal{B}_{\mathcal{F}},\|\cdot\|_{\mathcal{F}^{\prime}})$
and
$\mathcal{N}(S,\varepsilon):=\mathcal{N}(S\mathcal{B}_{\mathcal{F}},\|\cdot\|_{\mathcal{F}^{\prime}},\varepsilon)$,
where $\mathcal{B}_{\mathcal{F}}$ is the closed unit ball of $\mathcal{F}$.

Let $P_{\mathcal{X}}$ denote the marginal distribution of $P$ on
$\mathcal{X}$. Given i.i.d. sample
${\mathbf{x}}=\left\\{X_{i}\right\\}_{i=1}^{n}$ of $P_{\mathcal{X}}$, define
two empirical measures:
$P^{n}_{\mathbf{x}}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}$ and
$P^{n}_{\mathbf{x}^{2}}:=\frac{1}{n(n-1)}\sum_{i\neq
j}\delta_{(X_{i},X_{j})}$, where $\delta_{(\cdot)}$ is the counting measure.
We give the following capacity assumption on the RKHS $\mathcal{H}_{K}$.

######  Assumption 2.

For all $n\in\mathbb{N}$ and i.i.d. sample
${\mathbf{x}}=\left\\{X_{i}\right\\}_{i=1}^{n}$ of $P_{\mathcal{X}}$, there
exist constants $0<p_{1},p_{2}<1/2$, $a_{1}>0$ and $a_{2}>0$ such that

$\displaystyle
e_{i}(\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}))$ $\displaystyle\leq a_{1}i^{-\frac{1}{2p_{1}}},\quad\forall
i\in\mathbb{N},$ $\displaystyle
e_{i}(\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}}))$
$\displaystyle\leq a_{2}i^{-\frac{1}{2p_{2}}},\quad\forall i\in\mathbb{N}.$

Here $\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes P_{\mathcal{X}})$ and
$\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})$ are the Hilbert spaces of square-
integrable functions with respect to $P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}$ and $P^{n}_{\mathbf{x}^{2}}$ in which the norms are defined
for $f\in\mathcal{H}_{K}$ by

$\displaystyle\|f\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}})}$
$\displaystyle:=\bigg{(}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{P_{\mathcal{X}}}\left[f(X_{i},X)^{2}\right]\bigg{)}^{\frac{1}{2}},$
$\displaystyle\|f\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})}$
$\displaystyle:=\bigg{(}\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}f(X_{i},X_{j})^{2}\bigg{)}^{\frac{1}{2}}.$

Due to the connection between entropy numbers and covering numbers, cf. Lemma
6.21 of [36], the capacity assumption on entropy numbers can be restated by
using the metric entropy, namely the logarithm of the covering number, i.e.,
there exist constants $0<p_{1},p_{2}<1/2$, $a_{1}>0$ and $a_{2}>0$ such that

$\displaystyle\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}),\varepsilon)$
$\displaystyle\leq\log(4)a_{1}^{2p_{1}}\varepsilon^{-2p_{1}},$
$\displaystyle\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}}),\varepsilon)$
$\displaystyle\leq\log(4)a_{2}^{2p_{2}}\varepsilon^{-2p_{2}}.$

Recall that the $\phi$-ranking risk $\mathcal{R}^{\phi}(\cdot)$ is given by
(1.7) and the Bayes $\phi$-ranking rule $f^{*}_{\phi}$ is defined by (2.2).
Note that if the loss $\phi$ can be truncated at some $M>0$, there holds

$\mathcal{R}^{\phi}(\pi(f))-\mathcal{R}^{\phi}(f^{*}_{\phi})\leq\mathcal{R}^{\phi}(f)-\mathcal{R}^{\phi}(f^{*}_{\phi})$

for all $f:\mathcal{X}^{2}\to\mathbb{R}$. In the following, we can always
consider truncated estimators because projecting the values of decision
functions onto $[-M,M]$ does not increase their excess $\phi$-ranking risk.
Now we can give our oracle inequality for the estimators generated by
algorithm (2.1) with a general loss $\phi$.

######  Theorem 1.

Let ${\mathbf{z}}=\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{n}$ be an i.i.d.
sample of a probability distribution $P$ on $\mathcal{X}\times\mathcal{Y}$.
Given a loss function
$\phi:\mathcal{Y}\times\mathcal{Y}\times\mathbb{R}\to[0,\infty)$ and a
measurable positive semi-definite kernel
$K:\mathcal{X}^{2}\times\mathcal{X}^{2}\to\mathbb{R}$ with the associated RKHS
$\mathcal{H}_{K}$ consisting of skew-symmetric functions, the estimator
$f_{\mathbf{z}}$ is defined by (2.1) with $\lambda>0$. Assume that $\phi$
satisfies Assumption 1 with $L>0,B>0,\tau\in[0,1]$ and $V\geq B^{2-\tau}$, and
$\mathcal{H}_{K}$ satisfies Assumption 2 with $0<p_{1},p_{2}<1/2$, $a_{1}\geq
B$ and $a_{2}\geq B$. If there exists some $f_{0}\in\mathcal{H}_{K}$
satisfying $\|\phi_{f_{0}}\|_{\infty}\leq B_{0}$ for some constant $B_{0}\geq
0$, then for all $n\geq 2$ and $t>0$, with probability at least
$1-(c_{0}+5)\exp(-t)$, there holds

$\begin{split}&\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi({f}_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\\\
\leq{}&8\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+6c_{1}\left(\frac{a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}\\\
&+\frac{6c_{2}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}+\frac{3c_{3}a_{1}^{2p_{1}}L^{2p_{1}}B^{1-p_{1}}t}{\lambda^{p_{1}}n}+\frac{3c_{4}a_{2}^{2p_{2}}L^{2p_{2}}B^{1-p_{2}}t}{\lambda^{p_{2}}n}\\\
&+\left(\frac{1872Vt}{n}\right)^{\frac{1}{2-\tau}}+\frac{900Bt}{n}+\frac{456B_{0}t}{n}+\frac{3c_{5}t}{n}.\end{split}$
(2.7)

where $c_{i},i=0,1,2,3,4,5$ are constants independent of $\lambda$, $n$ or $t$
and explicitly given in the proof.

Next, we apply the oracle inequality to the margin-based loss function
$\phi(y,y^{\prime},t)=\psi(\mathrm{sgn}(y-y^{\prime})t)$ with
$\psi:\mathbb{R}\to[0,\infty)$, where $\psi$ satisfies the following
assumption.

######  Assumption 3.

The univariate function $\psi:\mathbb{R}\to[0,\infty)$ is convex,
differentiable at $t=0$ with $\psi^{\prime}(0)<0$, and the smallest zero of
$\psi$ is 1.

Examples of $\psi$ in Assumption 3 include the hinge loss
$\psi_{\mathrm{hinge}}$, square loss $\psi_{\mathrm{square}}$ and the the
$r$-norm hinge loss with $1\leq r<\infty$ defined by
$\psi_{r}(t):=(\psi_{\mathrm{hinge}}(t))^{r}$. Due to Lemma 9 in Subsection
5.3, if $\psi$ satisfies Assumption 3, the margin-based loss
$\phi(y,y^{\prime},t)=\psi(\mathrm{sgn}(y-y^{\prime})t)$ can be truncated at
$M=1$ and the Bayes $\phi$-ranking rule $f^{*}_{\phi}$ can be taken as skew-
symmetric. Now we can give the oracle inequality for the estimators generated
by algorithm (2.1) with the margin-based loss.

######  Theorem 2.

Let ${\mathbf{z}}=\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{n}$ be an i.i.d.
sample of a probability distribution $P$ on $\mathcal{X}\times\mathcal{Y}$.
Given a margin-based loss
$\phi(y,y^{\prime},t)=\psi(\mathrm{sgn}(y-y^{\prime})t)$ with
$\psi:\mathbb{R}\to[0,\infty)$ satisfying Assumption 3 and a measurable
positive semi-definite kernel
$K:\mathcal{X}^{2}\times\mathcal{X}^{2}\to\mathbb{R}$ with the associated RKHS
$\mathcal{H}_{K}$ consisting of skew-symmetric functions, the estimator
$f_{\mathbf{z}}$ is defined by (2.1) with $\lambda>0$. Assume that there exist
constants $L>0$, $B>0,\tau\in[0,1]$ and $V\geq B^{2-\tau}$ such that $\psi$ is
locally $L$-Lipschitz and $\psi(t)\leq B$ over $t\in[-1,1]$, and the variance
bound (2.6) of Assumption 1 holds with truncation parameter $M=1$. If there
exists some $f_{0}\in\mathcal{H}_{K}$ satisfying
$\|\phi_{f_{0}}\|_{\infty}\leq B_{0}$ for some constant $B_{0}\geq 0$ and
$\mathcal{H}_{K}$ satisfies Assumption 2 with $0<p_{1},p_{2}<1/2$, $a_{1}\geq
B$ and $a_{2}\geq B$, then the conclusion of Theorem 1 holds true.

######  Remark 1.

Under the assumptions of Theorem 2, we further assume that $p_{1}=p_{2}=p$ and
there exist constants $c>0$ and $\gamma\in(0,1]$ such that, for all
$\lambda>0$, the approximation error $\mathcal{A}(\lambda)$ is bounded as

$\mathcal{A}(\lambda):=\inf_{f\in\mathcal{H}_{K}}\lambda\|f\|^{2}_{K}+\mathcal{R}^{\phi}(f)-\mathcal{R}^{\phi}(f^{*}_{\phi})\leq
c\lambda^{\gamma}.$

Then by choosing

$\lambda=n^{-b},\ b=\frac{1}{(2-\tau-p+p\tau)\gamma+p},$

we have

$\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\lesssim
n^{-\frac{\gamma}{(2-\tau-p+p\tau)\gamma+p}}.$

This learning rate significantly improves the existing results for pairwise
ranking with margin-based losses. See Section 3 for a detailed comparison.

We will prove Theorem 1 and Theorem 2 in Section 4. Having derived the oracle
inequality, we now focus on the pairwise ranking scheme (1.4) with pairwise
Gaussian kernel $K^{\sigma}$ and two typical margin-base losses:

$\phi_{\mathrm{hinge}}(y,y^{\prime},t):=\psi_{\mathrm{hinge}}(\mathrm{sgn}(y-y^{\prime})t)=\max\\{1-\mathrm{sgn}(y-y^{\prime})t,0\\}$

and

$\phi_{\mathrm{square}}(y,y^{\prime},t):=\psi_{\mathrm{square}}(\mathrm{sgn}(y-y^{\prime})t)=(1-\mathrm{sgn}(y-y^{\prime})t)^{2}.$

Recall that the excess ranking risk $\mathcal{E}(f)$ and the excess
$\phi$-ranking risk $\mathcal{E}^{\phi}(f)$ are defined by (1.2) and (1.8),
respectively. To derive learning rates for excess ranking risk using Theorem
2, the following problems remain to be solved:

  * •

Verify Assumption 1 for $\phi_{\mathrm{hinge}}$, $\phi_{\mathrm{square}}$;

  * •

Construct an $f_{0}\in\mathcal{H}_{K^{\sigma}}$ to bound the approximation
error $\mathcal{A}(\lambda)$;

  * •

Verify the capacity condition (Assumption 2) for the RKHS
$\mathcal{H}_{K^{\sigma}}$;

  * •

Establish calibration inequality for ranking, i.e., bounding the excess
ranking risk $\mathcal{E}(f)$ by the excess $\phi$-ranking risk
$\mathcal{E}^{\phi}(f)$.

In Section 5, we will solve these problems and establish the corresponding
estimates under proper regularity assumptions. In the rest part of this
section, We introduce these assumptions to characterize the distribution, the
smoothness of the target function and the intrinsic dimension of the input
domain. Then we present our results on fast learning rates of Gaussian ranking
estimator (1.4) equipped with $\phi_{\mathrm{hinge}}$ and
$\phi_{\mathrm{square}}$.

We first introduce two noise conditions to describe the distribution. Recall
that $P$ is a probability distribution on $\mathcal{X}\times\mathcal{Y}$. For
distinct $(x,y)$ and $(x^{\prime},y^{\prime})$, define the posterior
probabilities of $P$, denoted by
$\eta_{+},\eta_{-},\eta_{=}:\mathcal{X}^{2}\to[0,1]$, as

$\displaystyle\eta_{+}(x,x^{\prime})$
$\displaystyle:=P(y>y^{\prime}|x,x^{\prime}),$
$\displaystyle\eta_{-}(x,x^{\prime})$
$\displaystyle:=P(y<y^{\prime}|x,x^{\prime}),$
$\displaystyle\eta_{=}(x,x^{\prime})$
$\displaystyle:=P(y=y^{\prime}|x,x^{\prime}).$

Then partition $\mathcal{X}^{2}$ into

$\begin{split}\mathcal{X}^{2}_{+}&:=\\{(x,x^{\prime})\in\mathcal{X}^{2}:\eta_{+}(x,x^{\prime})>\eta_{-}(x,x^{\prime})\\},\\\
\mathcal{X}^{2}_{-}&:=\\{(x,x^{\prime})\in\mathcal{X}^{2}:\eta_{+}(x,x^{\prime})<\eta_{-}(x,x^{\prime})\\},\\\
\mathcal{X}^{2}_{=}&:=\\{(x,x^{\prime})\in\mathcal{X}^{2}:\eta_{+}(x,x^{\prime})=\eta_{-}(x,x^{\prime})\\}.\end{split}$
(2.8)

Following Proposition 1 of [12], the _Bayes ranking rule_
$f^{*}_{\mathrm{rank}}:\mathcal{X}^{2}\to\mathbb{R}$ which minimizes the
ranking risk $\mathcal{R}(f)$ in (1.1) over all measurable functions is given
by

$f^{*}_{\mathrm{rank}}(x,x^{\prime})=\mathrm{sgn}\bigl{(}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{)}=\begin{cases}1&\mbox{
if }(x,x^{\prime})\in\mathcal{X}^{2}_{+},\\\ 0&\mbox{ if
}(x,x^{\prime})\in\mathcal{X}^{2}_{=},\\\ -1&\mbox{ if
}(x,x^{\prime})\in\mathcal{X}^{2}_{-}.\end{cases}$

Then the minimal ranking risk is
$\mathcal{R}(f^{*}_{\mathrm{rank}})=\mathbb{E}\min\left\\{\eta_{+}(X,X^{\prime}),\eta_{-}(X,X^{\prime})\right\\}$.

Now we introduce a condition analogous to Tsybakov’s noise condition in binary
classification, describing the amount of noise in the labels. In order to
motivate this condition, we note by

$\min\left\\{\eta_{+}(x,x^{\prime}),\eta_{-}(x,x^{\prime})\right\\}=\frac{\eta_{+}(x,x^{\prime})+\eta_{-}(x,x^{\prime})}{2}-\frac{\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}}{2}$

that the function
$\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}$ can be used to
describe the noise in comparing the labels of a distribution $P$. Indeed, in
regions where this function is close to $1$, there is only a small amount of
noise in comparing $y$ and $y^{\prime}$, whereas function values close to $0$
only occur in regions with a high level of noise in comparing $y$ and
$y^{\prime}$. The following condition in which we use the convention
$t^{\infty}:=0$ for $t\in(0,1)$ describes the size of the latter regions.
Recall that $P_{\mathcal{X}}$ is the marginal distribution of $P$ on
$\mathcal{X}$. Let $P^{2}_{\mathcal{X}}:=P_{\mathcal{X}}\otimes
P_{\mathcal{X}}$.

######  Assumption 4.

There exist constants $C_{*}>0$ and $q\in[0,\infty]$ such that

$P^{2}_{\mathcal{X}}\bigl{(}\bigl{\\{}(x,x^{\prime})\in\mathcal{X}^{2}:\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}\leq
t\bigr{\\}}\bigr{)}\leq C_{*}t^{q}$ (2.9)

for all $t>0$.

Obviously, $P^{2}_{\mathcal{X}}$ has the noise exponent $q>0$ if and only if
$\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}^{-1}$ belongs
to the Lorentz space $\mathcal{L}_{q,\infty}(P^{2}_{\mathcal{X}})$ (see [27]).
It is also easy to see that all distributions satisfy (2.9) with $C_{*}=1$ and
$q=0$. Furthermore, the extreme case $q=\infty$ requires that
$\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}$ is lower
bounded by some positive constant for almost every
$(x,x^{\prime})\in\mathcal{X}^{2}$, including the case of a noise-free
distribution in which
$\bigl{|}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{|}=1$ almost
surely. Under Assumption 4, we will demonstrate the variance bound (2.6) for
$\phi_{\mathrm{hinge}}$. We also leverage this assumption to establish a
refined calibration inequality to bound $\mathcal{E}(f)$ by
$\mathcal{E}^{\phi}(f)$. See Proposition 9 and Lemma 11. The work of [12] and
[13] introduced another two noise conditions for bipartite ranking problems.
Their noise conditions are stronger than ours which leads to a better variance
bound exponent $\tau$ in (2.6). We will make detailed comparisons of these
noise conditions in Subsection 5.5.

The second noise condition is a geometric condition for distributions that
describes the location of the noise sets and allows us to estimate the
approximation error for Gaussian kernels. According to our discussion in
Subsection 5.3, the Bayes ranking rule of $\phi_{\mathrm{hinge}}$ can be
defined pointwisely, i.e., given $(x,x^{\prime})\in\mathcal{X}^{2}$,

$f^{*}_{\mathrm{hinge}}(x,x^{\prime}):=\mathop{\arg\min}_{t\in\mathbb{R}}\eta_{+}(x,x^{\prime})\psi_{\mathrm{hinge}}(t)+\eta_{-}(x,x^{\prime})\psi_{\mathrm{hinge}}(-t).$

Then $f^{*}_{\mathrm{hinge}}$ can be explicitly given by

$f^{*}_{\mathrm{hinge}}(x,x^{\prime})=\mathrm{sgn}\bigl{(}\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})\bigr{)},\
\forall(x,x^{\prime})\in\mathcal{X}^{2},$ (2.10)

which is exactly the optimal ranking rule $f^{*}_{\mathrm{rank}}$. Note that
$f^{*}_{\mathrm{hinge}}$ is typically a step function. Therefore, employing
the classical smoothness assumption to describe the regularity of
$f^{*}_{\mathrm{hinge}}$ seems rather restrictive. Inspired by the theoretical
analysis of binary classification with hinge loss (cf. [36]), we introduce the
second noise condition which is called the margin-noise condition. It relates
the noise to the distance to the decision boundary and is applied to bound the
approximation error with respect to hinge loss and Gaussian kernels. See
Proposition 5.

######  Assumption 5.

There exist constant $C_{**}>0$ and $\beta\geq 0$ such that for all $t\geq 0$,

$\int_{\\{(x,x^{\prime})\in\mathcal{X}^{2}:\Delta(x,x^{\prime})<t\\}}|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|dP_{\mathcal{X}}(x)dP_{\mathcal{X}}(x^{\prime})\leq
C_{**}t^{\beta}.$ (2.11)

Here, $\Delta(x,x^{\prime})$ is the distance to the decision boundary, defined
as

$\Delta(x,x^{\prime}):=\begin{cases}\mathrm{dist}((x,x^{\prime}),\mathcal{X}^{2}_{-}\cup\mathcal{X}^{2}_{=})&(x,x^{\prime})\in\mathcal{X}^{2}_{+}\\\
\mathrm{dist}((x,x^{\prime}),\mathcal{X}^{2}_{+}\cup\mathcal{X}^{2}_{=})&(x,x^{\prime})\in\mathcal{X}^{2}_{-}\\\
0&(x,x^{\prime})\in\mathcal{X}^{2}_{=},\end{cases}$ (2.12)

where $\text{dist}(x,A):=\inf_{y\in A}\|x-y\|_{2}.$

Note that in condition (2.11) we neither impose any kind of smoothness
assumption nor require that $P^{2}_{\mathcal{X}}$ is absolutely continuous
with respect to the Lebesgue measure. If $P^{2}_{\mathcal{X}}$ has only a low
concentration near the decision boundary $\mathcal{X}^{2}_{=}$ or it is
particularly noisy in this region, Assumption 5 is satisfied for a large
exponent $\beta$. For instance, we can select arbitrary large values for
$\beta$ in the extreme case where $\mathcal{X}^{2}_{+}$ and
$\mathcal{X}^{2}_{-}$ have positive distance.

Next, we introduce the box-counting dimension condition which takes full
advantage of the low-dimensional intrinsic structure of the input data.
Assumption 2 requires upper bounds of the entropy number of RKHS
$\mathcal{H}_{K}$ with respect to $\mathcal{L}_{2}$-seminorm
$\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes P_{\mathcal{X}})}$ and
$\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})}$, both of which are
dominated by the sup-norm $\|\cdot\|_{\infty}$. The covering number of
Gaussian RKHS $\mathcal{H}_{K^{\sigma}}$ with respect to the sup-norm has been
intensively studied in the literature, cf. [23, 37], some of which have
related it to the uniform covering number
$\mathcal{N}(\mathcal{X},\|\cdot\|_{\infty},\sigma)$ of the input space. Since
$\mathcal{N}(\mathcal{X},\|\cdot\|_{\infty},\sigma)$ exponentially depends on
the dimension of the input space $\mathcal{X}\subset\mathbb{R}^{d}$. When $d$
is large, the learning rate suffers from the curse of dimensionality. This
phenomenon is usually inevitable for high-dimensional data. However, we can
derive much faster rates of convergence when the intrinsic dimension of the
data is much smaller than the dimension of its ambient space. We describe the
low-dimensional intrinsic structure of the input domain through the box-
counting dimension which is introduced to describe the low-dimensional
intrinsic fractal structure in fractal geometry, see, e.g., [17]. For a metric
space $(\mathcal{T},\mathrm{d})$ and a subset $\mathcal{S}\subset\mathcal{T}$,
if the limit

$\lim_{\varepsilon\to
0}\frac{\log\mathcal{N}(\mathcal{S},\mathrm{d},\varepsilon)}{\log\frac{1}{\varepsilon}}$

exists, it is called the _box-counting dimension_ of $\mathcal{S}$. If not, we
define the upper box-counting dimension

$\limsup_{\varepsilon\to
0}\frac{\log\mathcal{N}(\mathcal{S},\mathrm{d},\varepsilon)}{\log\frac{1}{\varepsilon}},$

and lower box-counting dimension

$\liminf_{\varepsilon\to
0}\frac{\log\mathcal{N}(\mathcal{S},\mathrm{d},\varepsilon)}{\log\frac{1}{\varepsilon}}.$

######  Assumption 6.

There exists a constant $\varrho>0$ such that

$\limsup_{\varepsilon\to
0}\frac{\log\mathcal{N}(\mathcal{X},\|\cdot\|_{\infty},\varepsilon)}{\log\frac{1}{\varepsilon}}\leq\varrho,$
(2.13)

or, equivalently, there exist constants $C_{\mathcal{X}}\geq 1$ and
$\varrho>0$ such that

$\mathcal{N}(\mathcal{X},\|\cdot\|_{\infty},\varepsilon)\leq
C_{\mathcal{X}}\varepsilon^{-\varrho}.$ (2.14)

The infimum over all $\varrho$ satisfying (2.13) coincides with the upper box-
counting dimension of $\mathcal{X}$. This assumption is rather general because
it captures the intrinsic dimension of low-dimensional smooth submanifold
$\mathcal{M}\subset\mathbb{R}^{d}$. When a bounded
$\mathcal{X}\subset\mathbb{R}^{d}$ has a non-empty interior, the assumption is
fulfilled precisely for $\varrho=d$. Under Assumption 6, we will show that the
learning rate of the concerned algorithms mainly depends on the intrinsic
dimension $\varrho$ of the input domain.

######  Remark 2.

In Subsection 5.2, we define a convolution operator
$\mathcal{K}^{\sigma}*\cdot:\mathcal{L}_{2}(\mathbb{R}^{2d})\to\mathcal{H}_{K^{\sigma}}$
and show that acting the convolution operator on the Bayes $\phi$-ranking rule
$f^{*}_{\phi}$ can lead to the desired approximator. Hence, a proper extension
of $f^{*}_{\phi}:\mathcal{X}^{2}\to\mathbb{R}$ to
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ should be taken into consideration. In many
cases, it is enough to use the zero extension. However, If $\mathcal{X}$ has a
low intrinsic dimension $\varrho<d$, $\mathcal{X}$ may have a zero Lebesgue
measure and the trivial zero extension of $f^{*}_{\phi}$ only yields the zero
function in $\mathcal{L}_{2}(\mathbb{R}^{2d})$. For the case of square loss,
we can fix this issue with the help of Whitney’s extension theorem (see
Theorem 2.3.6 of [19]), in which we directly regard $f^{*}_{\mathrm{square}}$
(defined in (2.16)) as a function in $\mathcal{L}_{2}(\mathbb{R}^{2d})$, and
impose Besov smoothness assumption on $f^{*}_{\mathrm{square}}$. As is
explained in [18]: if $\mathcal{X}^{2}$ is a compact $C^{k}$-manifold, by
Whitney’s extension theorem, any $f\in C^{k}(\mathcal{X}^{2})$ has an
extension to a function $\widetilde{f}\in C^{k}(\mathcal{X}^{2}_{+\delta})$
where $\mathcal{X}^{2}_{+\delta}$ is the $\delta$-neighbourhood of
$\mathcal{X}^{2}$ in $\mathbb{R}^{2d}$. However, for the case of hinge loss,
the situation is more challenging because we need to extend
$f^{*}_{\mathrm{hinge}}$ to $\mathcal{L}_{2}(\mathbb{R}^{2d})$ without
violating the margin-noise condition (5) which is necessary to bound the
approximation error. There is no trivial way to fix this issue to the best of
our knowledge. In this work, we will give a construction of this extension in
the proof of Proposition 5.

Under the noise conditions, i.e., Assumption 4 and Assumption 5, and
Assumption 6, we derive fast learning rates for of Gaussian ranking estimator
(1.4) equipped with $\phi_{\mathrm{hinge}}$. Let
$\mathcal{B}_{\mathbb{R}^{d}}$ denote the unit ball in $\mathbb{R}^{d}$.

######  Theorem 3.

Let ${\mathbf{z}}=\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{n}$ be an i.i.d.
sample of a probability distribution $P$ on $\mathcal{X}\times\mathcal{Y}$.
The estimator $f_{\mathbf{z}}$ is defined by (1.4) with
$\lambda>0,\sigma\in(0,1)$, and
$\phi_{\mathrm{hinge}}(y,y^{\prime},t)=\max\\{1-\mathrm{sgn}(y-y^{\prime})t,0\\}$.
Further, let $P$ satisfy Assumption 4 for constant $C_{*}$ and $q$ and
Assumption 5 for constants $C_{**}$ and $\beta$. Assume that there exits some
$r>0$ such that $\mathcal{X}\subset r\mathcal{B}_{\mathbb{R}^{d}}$ and
Assumption 6 is satisfied for constants $C_{\mathcal{X}}$ and
$\varrho\in(0,d]$. Then for all $n\geq 2,t>0$, and $p\in(0,1/4]$, with
probability at least $1-(c_{0}+5)\exp(-t)$, there holds

$\begin{split}&\lambda\|f_{\mathbf{z}}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi_{\mathrm{hinge}}}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})\\\
\leq{}&\frac{2^{3d+4}r^{2d}}{\Gamma(d)}\lambda\sigma^{-2d}+\frac{2^{\beta/2+4}C_{**}\Gamma(d+\frac{\beta}{2})}{\Gamma(d)}\sigma^{\beta}+36c_{6}\left(\frac{C^{*}_{\mathcal{X}}C_{*}^{\frac{1-p}{q+1}}}{\lambda^{p}p^{2d+1}\sigma^{2\varrho}n}\right)^{\frac{q+1}{q-p+2}}\\\
&+\frac{12C^{*}_{\mathcal{X}}c_{6}(t+1)}{\lambda^{p}p^{2d+1}\sigma^{2\varrho}n}+\left(\frac{11232C_{*}^{\frac{1}{q+1}}t}{n}\right)^{\frac{q+1}{q+2}}+\frac{(2712+3c_{6})t}{n},\end{split}$
(2.15)

where

$C^{*}_{\mathcal{X}}:=12C^{2}_{\mathcal{X}}\binom{4e+2d}{2d}\frac{(2d+1)^{2d+1}}{2^{2d+1}e^{4d+1}}$

and $c_{0},c_{6}$ are constants independent of $\lambda,\sigma,n,t$ or $p$
which are explicitly given in the proof. In particular, choose

$\displaystyle\sigma=n^{-a},\quad a=\frac{q+1}{\beta(q+2)+2\varrho(q+1)};$
$\displaystyle\lambda=n^{-b},\quad
b\geq\frac{(2d+\beta)(q+1)}{\beta(q+2)+2\varrho(q+1)},\quad p=\frac{\log
2}{4\log n}.$

Then for all $n\geq 2$ and $t\geq 1$, we have

$\mathcal{E}(\pi(f_{\mathbf{z}}))\leq\mathcal{E}^{\phi_{\mathrm{hinge}}}(\pi(f_{\mathbf{z}}))\lesssim
tn^{-\frac{\beta(q+1)}{\beta(q+2)+2\varrho(q+1)}}\log^{2d+1}n$

with probability at least $1-(c_{0}+5)\exp(-t)$.

For the case of square loss, the Bayes ranking rule of
$\phi_{\mathrm{square}}$ is defined pointwise by

$f^{*}_{\mathrm{square}}(x,x^{\prime}):=\mathop{\arg\min}_{t\in\mathbb{R}}\eta_{+}(x,x^{\prime})\psi_{\mathrm{square}}(t)+\eta_{-}(x,x^{\prime})\psi_{\mathrm{square}}(-t)$

which can be explicitly expressed as

$f^{*}_{\mathrm{square}}(x,x^{\prime}):=\frac{\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})}{\eta_{+}(x,x^{\prime})+\eta_{-}(x,x^{\prime})},\
\forall(x,x^{\prime})\in\mathcal{X}^{2}.$ (2.16)

The function $f^{*}_{\mathrm{square}}$ enjoys a smoothness property inherited
from $\eta_{+}(x,x^{\prime})$ and $\eta_{-}(x,x^{\prime})$, allowing us to
derive an approximation error bound more directly. Here we introduce the
notation of Besov smoothness which is also adopted in [22, 40, 41, 18]. Given
a function $f:\mathbb{R}^{2d}\to\mathbb{R},h\in\mathbb{R}^{2d}$ and
$s\in\mathbb{N}$, define the $s$-fold application of the difference operator

$\Delta^{s}_{h}f(x):=\sum_{j=0}^{s}(-1)^{s-j}\binom{s}{j}f(x+jh).$

Given a measure $\mu$ on $\mathcal{X}^{2}\subset\mathbb{R}^{2d}$, define the
$s$-th modulus of smoothness

$\omega_{s,\mathcal{L}_{2}(\mu)}(f,t):=\sup_{\|h\|_{2}\leq
t}\left\|\Delta_{h}^{s}f\right\|_{\mathcal{L}_{2}(\mu)}.$

Finally, given an $\alpha>0$ and set $s=\left\lfloor\alpha\right\rfloor+1$,
define the semi-norm

$|f|_{\mathcal{B}_{2,\infty}^{\alpha}(\mu)}:=\sup_{t>0}t^{-\alpha}\omega_{s,\mathcal{L}_{2}(\mu)}(f,t).$

Under Assumption 4, Assumption 6 and the Besov smoothness assumption of
$f^{*}_{\mathrm{square}}$, we derive fast learning rates for of Gaussian
ranking estimator (1.4) equipped with $\phi_{\mathrm{square}}$.

######  Theorem 4.

Let ${\mathbf{z}}=\left\\{(X_{i},Y_{i})\right\\}_{i=1}^{n}$ be an i.i.d.
sample of a probability distribution $P$ on $\mathcal{X}\times\mathcal{Y}$.
The estimator $f_{\mathbf{z}}$ is defined by (1.4) with
$\lambda>0,\sigma\in(0,1)$, and
$\phi_{\mathrm{square}}(y,y^{\prime},t)=(1-\mathrm{sgn}(y-y^{\prime})t)^{2}$.
Assume that Assumption 6 is satisfied for constants $C_{\mathcal{X}}$ and
$\varrho\in(0,d]$. Further assume that
$f^{*}_{\mathrm{square}}\in\mathcal{L}_{2}(\mathbb{R}^{2d})$ and
$|f^{*}_{\mathrm{square}}|_{\mathcal{B}_{2,\infty}^{\alpha}(P^{2}_{\mathcal{X}})}<\infty$
for some $\alpha>0$. Then for all $n\geq 2,t>0$, and $p\in(0,1/4]$, with
probability at least $1-(c_{0}+5)\exp(-t)$, there holds

$\begin{split}&\lambda\|f_{\mathbf{z}}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi_{\mathrm{square}}}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi_{\mathrm{square}}}(f^{*}_{\mathrm{square}})\\\
\leq{}&\frac{2^{2s+3}\|f^{*}_{\mathrm{square}}\|^{2}_{\mathcal{L}_{2}(\mathbb{R}^{2d})}}{\pi^{d}}\lambda\sigma^{-2d}+2^{3-\alpha}\left(\frac{\Gamma\left(d+\frac{\alpha}{2}\right)}{\Gamma(d)}\right)^{2}|f^{*}_{\mathrm{square}}|^{2}_{\mathcal{B}_{2,\infty}^{\alpha}(P^{2}_{\mathcal{X}})}\sigma^{2\alpha}\\\
&+\frac{C^{*}_{\mathcal{X}}(96c_{6}+72c_{6}t)}{\lambda^{p}p^{2d+1}\sigma^{2\varrho}n}+\frac{(33552+1824\cdot
2^{2s}+3c_{6})t}{n},\end{split}$ (2.17)

where

$C^{*}_{\mathcal{X}}:=12C^{2}_{\mathcal{X}}\binom{4e+2d}{2d}\frac{(2d+1)^{2d+1}}{2^{2d+1}e^{4d+1}}$

and $c_{0},c_{6}$ are constants independent of $\lambda,\sigma,n,t$ or $p$
which are explicitly given in the proof. In particular, choose

$\displaystyle\sigma=n^{-a},\quad a=\frac{1}{2\alpha+2\varrho};$
$\displaystyle\lambda=n^{-b},\quad b\geq\frac{\alpha+d}{\alpha+\varrho},\quad
p=\frac{\log 2}{4\log n}.$

Then for all $n\geq 2,t\geq 1$, we have

$\mathcal{E}(\pi(f_{\mathbf{z}}))\lesssim\sqrt{\mathcal{E}^{\phi_{\mathrm{square}}}(\pi(f_{\mathbf{z}}))}\lesssim\sqrt{t}n^{-\frac{\alpha}{2(\alpha+\varrho)}}\log^{d+\frac{1}{2}}n$

with probability at least $1-(c_{0}+5)\exp(-t)$. Furthermore, if $P$
additionally satisfies Assumption 4 with $q>0$, then with probability at least
$1-(c_{0}+5)\exp(-t)$, there holds

$\mathcal{E}(\pi(f_{\mathbf{z}}))\lesssim
t^{\frac{q+1}{q+2}}n^{-\frac{(q+1)\alpha}{(q+2)(\alpha+\varrho)}}\log^{\frac{(q+1)(2d+1)}{q+2}}n.$

Finally, we would like to point out that, in light of Proposition 3.2 in [18],
the class of functions $f$ satisfying
$|f|_{\mathcal{B}_{2,\infty}^{\alpha}(P^{2}_{\mathcal{X}})}<\infty$ is indeed
very rich, even when the upper box-counting dimension of $\mathcal{X}$ is
strictly less than $d$. For instance, if $f$ is the Hölder $\alpha$-continuous
function on $\mathcal{X}^{2}$, then
$|f|_{\mathcal{B}_{2,\infty}^{\alpha}(\mu)}<\infty$ for every measure $\mu$
with $\mbox{supp}\mu\subset\mathcal{X}^{2}$. The proofs of Theorem 3 and
Theorem 4 are postponed to Section 5 after establishing some preliminary
results.

##  3 Discussions on Related Work

In this section, we compare our convergence analysis with some existing
results in the literature. Our paper contributes to several rapidly growing
literature, we give only those citations of particular relevance. More
references can be found within these works.

In this paper, we consider the pairwise ranking model which aims to learn a
bivariate ranking rule $f:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$. Our
model is more general compared with the score-based ranking model, in which we
learn a scoring function $s:\mathcal{X}\to\mathbb{R}$ and construct the
ranking rule as $f(x,x^{\prime})=s(x)-s(x^{\prime})$. Some popular ranking
algorithms including RankSVM in [20], RankNet in [7] and RankRLS in [30, 14,
31] are closely related to the score-based ranking model. For the error
analysis of the score-based ranking model, [1] proved generalization bounds
via algorithmic stability for the bipartite ranking problem where the label
$Y$ is binary. [11] derived a capacity-independent learning rate for RankRLS
from the viewpoint of operator approximation. Whereafter, [52] developed a
capacity-dependent generalization analysis for RankRLS by virtue of covering
numbers and Hoeffding’s decomposition for U-statistics.

In some learning tasks, for example, learning binary relations between two
objects, we can assign a vertex to each object and an edge to represent the
binary relations between two vertices, which naturally forms a graph
structure. Denote $\mathcal{X}$ the vertex set and $\mathcal{X}^{2}$ the edge
set. A positive semi-definite kernel
$G:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ induces an RKHS
$\mathcal{H}_{G}$ in which we can learn a function
$f:\mathcal{X}\to\mathbb{R}$ defined on the vertex set. However, in such graph
learning tasks, if we want to figure out the binary relations, pairwise
learning is more applicable, in which we need to learn a function
$f:\mathcal{X}^{2}\to\mathbb{R}$ defined on the edge set. In fact, the kernel
function $G$ defined between vertices can induce the so-called Kronecker
product pairwise kernel $K:\mathcal{X}^{2}\times\mathcal{X}^{2}\to\mathbb{R}$
by Kronecker product
$K((x,x^{\prime}),(u^{\prime},u^{\prime})):=G(x,u)G(x^{\prime},u^{\prime})$.
Kronecker kernel ridge regression (KKRR) is a pairwise learning algorithm
based on the Kronecker product pairwise kernel $K$, where the induced
regularized empirical minimization problem is solved in the RKHS
$\mathcal{H}_{K}$. In Subsection 5.1, we see that the RKHS $\mathcal{H}_{K}$
consists of functions on $\mathcal{X}^{2}$ and we can decompose any
$f\in\mathcal{H}_{K}$ into a direct sum of its symmetric part and skew-
symmetric part, which corresponds to a direct sum of two subspaces of
$\mathcal{H}_{K}$ and leads to a decomposition of the pairwise kernel $K$ as
well. The pairwise Gaussian kernel $K^{\sigma}$ is indeed the skew-symmetric
part of the traditional Gaussian kernel $\widetilde{K}^{\sigma}$ on
$\mathcal{X}^{2}$ defined as
$\widetilde{K}^{\sigma}((x,x^{\prime}),(u,u^{\prime})):=\exp\left(-\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}/\sigma^{2}\right)$,
and hence the corresponding RKHS $\mathcal{H}_{K^{\sigma}}$ is one subspace in
the direct sum of $\mathcal{H}_{\widetilde{K}^{\sigma}}$. Although
$\mathcal{H}_{K^{\sigma}}$ is a smaller hypothesis space, the universality of
the kernel can be still maintained when only learning skew-symmetric
relations. That is to say, if the Kronecker product pairwise kernel $K$ can
approximate any continuous function on $\mathcal{X}^{2}$ arbitrarily well,
then the skew-symmetric part of the pairwise kernel can also approximate any
continuous skew-symmetric function arbitrarily well, cf. Theorem III.4. of
[42]. Therefore, when we use pairwise learning algorithms including KKRR to
learn skew-symmetric relations between data, we only need to restrict the
estimators in the hypothesis spaces $\mathcal{H}_{K^{\sigma}}$. A similar
observation also holds when using the symmetric part of the kernel to learn
symmetric relations. One can refer to [6, 42, 29, 43] for more details.

As the pairwise ranking model is more general, some theoretical frameworks
have been established to analyze its convergence behaviors. The main
distinction in convergence analysis between ranking and classification or
regression is that in ranking problems, the stochastic part of the convergence
analysis involves a second-order $U$-process rather than summations of i.i.d.
random variables. [12] and [33] used Hoeffding’s decomposition to the
unregularized ranking algorithm and obtained generalization bounds with faster
rates than $\frac{1}{\sqrt{n}}$. Hoeffding’s decomposition breaks the sample
error of a ranking algorithm into an empirical term based on a sum of i.i.d.
random variables and a degenerate U-process. In our work, we make full use of
Talagrand’s inequality, local Rademacher analysis, and capacity information of
the hypothesis space to derive tight bounds on the empirical term as well as
the degenerate part (see Section 4). For regularized pairwise ranking, [9]
considered $\ell_{1}$-norm regularized SVM ranking and established a learning
rate under a similar noise condition as Assumption 4. [34] proved an oracle
inequality for parametric pairwise ranking with the Lasso penalty in high-
dimensional settings. In contrast with our work, the work of [10, 25, 44]
considered regularized pairwise ranking with a fixed kernel and derive
learning rates by assuming a $\gamma$-decaying rate of the approximation
error. We further emphasize the differences between our results and the work
of [12, 33, 10, 25, 44]. [12] formulated the question if one can get
generalization bounds with fast rates for the excess risk in ranking. They
gave a positive answer for unregularized ranking estimators with non-convex
$0-1$ loss, i.e.,
$\phi(y,y^{\prime},t)=\psi_{\mathrm{0-1}}(\mathrm{sgn}(y-y^{\prime})t)$ where
$\psi_{\mathrm{0-1}}(t):=\mathbb{I}_{[0,\infty)}(t)$, and left the case of
convex risk minimization to future study. The work of [33] advanced this line
of research, in which it established generalization bounds with better rates
than $\frac{1}{\sqrt{n}}$ for the excess ranking risk with convex margin-based
losses. Both of these two papers constructed ranking estimators in a general
hypothesis space and required the optimal ranking rule to reside in this
function space. Hence they did not need to consider the analysis of the
approximation error. Moreover, a noise condition was also proposed by [12], we
postpone the comparison of different noise conditions to Subsection 5.5. The
work of [10, 44] also developed capacity-dependent empirical process technique
to analyze regularized ranking estimators, in which the capacity condition is
based on the sup-norm $\|\cdot\|_{\infty}$, which is more restrictive than the
empirical $\mathcal{L}_{2}$-seminorm adopted in this paper. Moreover, [10]
only focused on hinge loss and derived a rate of
$n^{-\frac{\gamma}{(2-\tau+p)\gamma+p}}$ which is slower than the rate of
$n^{-\frac{\gamma}{(2-\tau-p+p\tau)\gamma+p}}$ derived in Remark 1. The work
of [25] considered a general loss function similar to ours and derived a rate
of $n^{-\frac{\gamma}{\gamma+1}}$ without any capacity condition of the
hypothesis spaces nor Bernstein conditions on the bias and variance. We note
that even for the case $\tau=0$ in which the variance bound (2.6) is trivially
satisfied, our rate given by $n^{-\frac{\gamma}{(2-p)\gamma+p}}$ is still
faster than $n^{-\frac{\gamma}{\gamma+1}}$ provided $\gamma<1$. [44]
considered the least square loss
$\phi_{\mathrm{ls}}(y,y^{\prime},t):=(y-y^{\prime}-t)^{2}$ in a regression
setting. We can apply our analysis developed for the square loss to derive the
rate of $n^{-\frac{\gamma}{\gamma+p}}$ for the case of
$\phi_{\mathrm{ls}}(y,y^{\prime},t)$ loss, which is much faster than
$n^{-\frac{2\gamma}{(p+1)\gamma+4}}$ obtained by [44]. We also note that the
rate $n^{-\frac{\gamma}{\gamma+p}}$ actually achieves the well-known minimax
lower rate derived by [38] when approximating functions on $\mathbb{R}^{2d}$.
From this point of view, the oracle inequalities established in Theorem 1 and
Theorem 2 are more general than existing results but can lead to more tight
bounds on excess risk. Besides, [35] shows that the $\gamma$-decaying
assumption of the approximation error is indeed a very restrictive assumption
when describing the approximation ability of Gaussian RKHS and hence the
setting of ranking with varying Gaussian kernels can not be handled by the
approaches developed in the work of [10, 25, 44], in which they only focused
on the regularized ranking with fixed pairwise kernels.

The intrinsic dimension of the data can be utilized to improve the dependence
on the dimension of learning rates. To describe the intrinsic dimension
structure, the probably most popular notion is to assume that
$\mathcal{X}\subset\mathbb{R}^{d}$ is a low-dimensional submanifold, see,
e.g., [47, 48, 49]. The more general notion adopted in our paper is based on
the box-counting dimension which considerably generalizes the manifold
assumption. To the best of our knowledge, our paper is the first to consider
the learning behavior of regularized Gaussian ranking estimators under the
assumption that the gap between the intrinsic dimension of the data and the
dimension of its ambient space is large.

To sum up, in this paper we consider a regularized pairwise ranking problem
with a general convex loss under substantially general assumptions. The oracle
inequality established in our work can lead to an elegant framework of
convergence analysis which significantly improves the learning rates of
existing work. It also enables us to derive fast learning rates of Gaussian
ranking estimators which can avoid the curse of dimensionality by employing a
low intrinsic dimensional assumption of the data.

##  4 Proofs of the General Oracle Inequalities

In this section, we provide detailed proofs of the general oracle inequality
established in Theorem 1 and its variant in Theorem 2. Following a standard
error decomposition process, we use Hoeffding’s decomposition and
concentration estimates with U-process and local Rademacher analysis to bound
the stochastic parts of the error terms.

###  4.1 Error Decomposition and Hoeffding’s Decomposition

Given an $f_{0}\in\mathcal{H}_{K}$, by the definition of $f_{\mathbf{z}}$ we
have
$\mathcal{R}^{\phi}_{\mathbf{z}}(f_{\mathbf{z}})+\lambda\|f_{\mathbf{z}}\|^{2}_{K}\leq\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})+\lambda\|f_{0}\|^{2}_{K}.$
Then

$\displaystyle\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{\mathbf{z}})-\mathcal{R}^{\phi}(f^{*}_{\phi})$
$\displaystyle\leq{}$
$\displaystyle\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+\big{(}\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})-\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})-\mathcal{R}^{\phi}(f_{0})+\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}$
$\displaystyle+\big{(}\mathcal{R}^{\phi}(f_{\mathbf{z}})-\mathcal{R}^{\phi}(f^{*}_{\phi})-\mathcal{R}^{\phi}_{\mathbf{z}}(f_{\mathbf{z}})+\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})\big{)}.$

For a loss function $\phi$ that can be truncated at some $M>0$, since
$\phi(y,y^{\prime},\pi(t))\leq\phi(y,y^{\prime},t)$, we have
$\mathcal{R}^{\phi}_{\mathbf{z}}(\pi(f_{\mathbf{z}}))\leq\mathcal{R}^{\phi}_{\mathbf{z}}(f_{\mathbf{z}})$
which implies
$\mathcal{R}^{\phi}_{\mathbf{z}}(\pi(f_{\mathbf{z}}))+\lambda\|f_{\mathbf{z}}\|^{2}_{K}\leq\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})+\lambda\|f_{0}\|^{2}_{K}$
for any $f_{0}\in\mathcal{H}_{K}$. Hence we can bound
$\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})$
by the following error decomposition

$\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\leq\mathcal{A}(\lambda,f_{0})+\mathcal{S}_{\bf
z}(f_{0})+\mathcal{S}_{\bf z}(\pi(f_{\bf z}))$ (4.1)

where

$\begin{split}\mathcal{A}(\lambda,f_{0})&:=\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi}),\\\
\mathcal{S}_{\bf
z}(f_{0})&:=\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})-\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})-\mathcal{R}^{\phi}(f_{0})+\mathcal{R}^{\phi}(f^{*}_{\phi}),\\\
\mathcal{S}_{\bf z}(\pi(f_{\bf
z}))&:=\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-\mathcal{R}^{\phi}_{\mathbf{z}}(\pi(f_{\mathbf{z}}))+\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi}).\end{split}$

The first term $\mathcal{A}(\lambda,f_{0})$ reflects the approximation error
of using $f_{0}$ to approximate $f^{*}_{\phi}$. The other two terms
$\mathcal{S}_{\bf z}(f_{0})$ and $\mathcal{S}_{\bf z}(\pi(f_{\bf z}))$
constitute the stochastic parts of the error decomposition.

Under Assumption 1, we can bound $\mathcal{S}_{\bf z}(f_{0})$ by Bernstein’s
inequality of $U$-statistics, cf. [2], stated below.

######  Lemma 1.

Let $\mathbf{z}=\\{Z_{i}\\}_{i=1}^{n}$ be an i.i.d. sample of a probability
distribution $P$ on a measurable space $\mathcal{Z}$,
$h:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ be a symmetric measurable
function with $\mathbb{E}[h(Z,Z^{\prime})]=0$ and $\|h\|_{\infty}=b$. The
$U$-statistics with kernel $h$ is defined as

$U_{\mathbf{z}}(h)=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}h(Z_{i},Z_{j}).$

Let $f:\mathcal{Z}\to\mathbb{R}$ be defined as
$f(z):=\mathbb{E}[h(z,Z^{\prime})]$ and $\zeta^{2}:=\mathbb{E}[f(Z)^{2}]$.
Then for all $t>0$ we have

$P\big{(}\sqrt{n}|U_{\mathbf{z}}(h)|\geq t\big{)}\leq
4\exp\left(-\frac{t^{2}}{8\zeta^{2}+\left(\frac{64}{\sqrt{n-1}}+\frac{1}{3\sqrt{n}}\right)bt}\right),$

which implies that

$P\left(U_{\mathbf{z}}(h)\geq\sqrt{\frac{8\zeta^{2}t}{n}}+\frac{150bt}{n}\right)\leq
2\exp(-t).$ (4.2)

Recall that $\mathcal{S}_{\bf
z}(f_{0})=\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})-\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})-\mathcal{R}^{\phi}(f_{0})+\mathcal{R}^{\phi}(f^{*}_{\phi})$.

######  Proposition 1.

Given $f_{0}\in\mathcal{H}_{K}$ satisfying $\|\phi_{f_{0}}\|_{\infty}\leq
B_{0}$ for some constant $B_{0}\geq 0$. If Assumption 1 holds, then with
probability at least $1-4\exp(-t)$,

$\mathcal{S}_{\bf
z}(f_{0})\leq\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})+\left(\frac{8Vt}{n}\right)^{\frac{1}{2-\tau}}+\frac{300Bt}{n}+\frac{152B_{0}t}{n}.$
(4.3)

###### Proof.

Define $v_{f}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ as
$v_{f}:=\phi_{f}-\phi_{f^{*}_{\phi}}$, then

$\mathcal{S}_{\bf
z}(f_{0})=\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})-\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})-\mathcal{R}^{\phi}(f_{0})+\mathcal{R}^{\phi}(f^{*}_{\phi})=\mathbb{E}_{\mathbf{z}}v_{f_{0}}-\mathbb{E}v_{f_{0}}.$

We further decompose $\mathbb{E}_{\mathbf{z}}v_{f_{0}}-\mathbb{E}v_{f_{0}}$
into two terms by introducing the truncation $\pi(f_{0})$, which is given by

$\mathbb{E}_{\mathbf{z}}v_{f_{0}}-\mathbb{E}v_{f_{0}}=[\mathbb{E}_{\mathbf{z}}(v_{f_{0}}-v_{\pi(f_{0})})-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})]+(\mathbb{E}_{\mathbf{z}}v_{\pi(f_{0})}-\mathbb{E}v_{\pi(f_{0})}).$

Each term above is a difference between a $U$-statistics and its expectation,
hence we can apply Bernstein’s inequality in Lemma 1 to bound them. To this
end, we need to establish the sup-norm bound and variance bound for the
related U-statistics.

We first bound
$\mathbb{E}_{\mathbf{z}}(v_{f_{0}}-v_{\pi(f_{0})})-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})$.
Since

$\phi_{f_{0}}(z,z^{\prime})-\phi_{\pi(f_{0})}(z,z^{\prime})=\phi(y,y^{\prime},f_{0}(x,x^{\prime}))-\phi(y,y^{\prime},\pi(f_{0})(x,x^{\prime}))\geq
0$

for all $(z,z^{\prime})\in\mathcal{Z}\times\mathcal{Z}$, we have

$v_{f_{0}}-v_{\pi(f_{0})}=\phi_{f_{0}}-\phi_{\pi(f_{0})}:\mathcal{Z}\times\mathcal{Z}\to[0,B_{0}]$

and

$\|v_{f_{0}}-v_{\pi(f_{0})}-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})\|_{\infty}\leq
B_{0}.$

Define $g:\mathcal{Z}\to\mathbb{R}$ as

$g(z):=\mathbb{E}[v_{f_{0}}(z,Z^{\prime})-v_{\pi(f_{0})}(z,Z^{\prime})-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})].$

Then

$\mathbb{E}[g(Z)^{2}]\leq\mathbb{E}\bigg{[}\big{(}\mathbb{E}[v_{f_{0}}(Z,Z^{\prime})-v_{\pi(f_{0})}(Z,Z^{\prime})]\big{)}^{2}\bigg{]}\leq
B_{0}\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})}).$

Now we apply Bernstein’s inequality (4.2) to the zero-mean symmetric function
$v_{f_{0}}-v_{\pi(f_{0})}-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})$, showing that

$P\left(\mathbb{E}_{\mathbf{z}}(v_{f_{0}}-v_{\pi(f_{0})})-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})\geq\sqrt{\frac{8B_{0}\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})t}{n}}+\frac{150B_{0}t}{n}\right)\leq
2\exp(-t).$

By basic inequality $\sqrt{ab}\leq(a+b)/2,$ we have

$\sqrt{\frac{8B_{0}\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})t}{n}}\leq\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})+\frac{2B_{0}t}{n}.$

Hence with probability at least $1-2\exp(-t)$, there holds

$\mathbb{E}_{\mathbf{z}}(v_{f_{0}}-v_{\pi(f_{0})})-\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})\leq\mathbb{E}(v_{f_{0}}-v_{\pi(f_{0})})+\frac{152B_{0}t}{n}.$
(4.4)

To bound the second term
$\mathbb{E}_{\mathbf{z}}v_{\pi(f_{0})}-\mathbb{E}v_{\pi(f_{0})}$, define
$u:\mathcal{Z}\to\mathbb{R}$ as

$u(z):=\mathbb{E}[v_{\pi(f_{0})}(z,Z^{\prime})-\mathbb{E}v_{\pi(f_{0})}].$

By (2.5) and (2.6) of Assumption 1, we have

$v_{\pi(f_{0})}=\phi_{\pi(f_{0})}-\phi_{f^{*}_{\phi}}\in[-B,B],$
$\|v_{\pi(f_{0})}-\mathbb{E}v_{\pi(f_{0})}\|_{\infty}\leq 2B,$

and

$\mathbb{E}[u(Z)^{2}]\leq\mathbb{E}\bigg{[}\big{(}\mathbb{E}[v_{\pi(f_{0})}(Z,Z^{\prime})]\big{)}^{2}\bigg{]}=\mathbb{E}\big{(}Q\phi_{\pi(f_{0})}(Z)-Q\phi_{f^{*}_{\phi}}(Z)\big{)}^{2}\leq
V(\mathbb{E}v_{\pi(f_{0})})^{\tau}.$

We apply Bernstein’s inequality to the zero-mean symmetric function
$v_{\pi(f_{0})}-\mathbb{E}v_{\pi(f_{0})}$, showing that

$P\left(\mathbb{E}_{\mathbf{z}}(v_{\pi(f_{0})})-\mathbb{E}v_{\pi(f_{0})}\geq\sqrt{\frac{8V(\mathbb{E}v_{\pi(f_{0})})^{\tau}t}{n}}+\frac{300Bt}{n}\right)\leq
2\exp(-t).$

If $\tau>0$, we use Young’s inequality $ab\leq a^{q}/q+b^{p}/p$ by setting

$a=\sqrt{\frac{2^{3-\tau}\tau^{\tau}Vt}{n}},\quad
b=\left(\frac{2\mathbb{E}v_{\pi(f_{0})}}{\tau}\right)^{\tau/2},\quad
q=\frac{2}{2-\tau},\quad p=\frac{2}{\tau},$

to yield

$\sqrt{\frac{8V(\mathbb{E}v_{\pi(f_{0})})^{\tau}t}{n}}=ab\leq\frac{2-\tau}{2}\cdot\left(\frac{2^{3-\tau}\tau^{\tau}Vt}{n}\right)^{\frac{1}{2-\tau}}+\mathbb{E}v_{\pi(f_{0})}\leq\left(\frac{8Vt}{n}\right)^{\frac{1}{2-\tau}}+\mathbb{E}v_{\pi(f_{0})}.$

Since $\mathbb{E}v_{\pi(f_{0})}\geq 0$, this inequality also holds for
$\tau=0$. Hence with probability at least $1-2\exp(-t)$, there holds

$\mathbb{E}_{\mathbf{z}}(v_{\pi(f_{0})})-\mathbb{E}v_{\pi(f_{0})}\leq\mathbb{E}v_{\pi(f_{0})}+\left(\frac{8Vt}{n}\right)^{\frac{1}{2-\tau}}+\frac{300Bt}{n}.$
(4.5)

Consequently, combining (4.4) and (4.5), we derive the desired bound (4.3).
This completes the proof. ∎

It is more involved to bound $\mathcal{S}_{\bf z}(\pi(f_{\bf z}))$. Recall
that

$\mathcal{S}_{\bf z}(\pi(f_{\bf
z}))=\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-\mathcal{R}^{\phi}_{\mathbf{z}}(\pi(f_{\mathbf{z}}))+\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi}).$

We apply Hoeffding’s decomposition of $U$-statistics (cf. [24]) to
$\mathcal{S}_{\bf z}(\pi(f_{\bf z}))$, which is given by

$\begin{split}&\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-\mathcal{R}^{\phi}_{\mathbf{z}}(\pi(f_{\mathbf{z}}))+\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})\\\
&=2Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f_{\mathbf{z}})}+Q\phi_{f^{*}_{\phi}}]-U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})\\\
&=:2\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))-\mathcal{S}_{{\bf z},2}(\pi(f_{\bf
z})).\end{split}$ (4.6)

Here the functionals $Q_{\mathbf{z}},U_{\mathbf{z}}$ and function
$h_{f}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}$ are defined by

$\begin{split}Q_{\mathbf{z}}(g)&:=\frac{1}{n}\sum_{i=1}^{n}g(Z_{i}),\forall
g:\mathcal{Z}\to\mathbb{R},\\\
U_{\mathbf{z}}(g^{\prime})&:=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}g^{\prime}(Z_{i},Z_{j}),\forall
g^{\prime}:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R},\\\
h_{f}(z,z^{\prime})&:=\phi_{f}(z,z^{\prime})-Q\phi_{f}(z)-Q\phi_{f}(z^{\prime})+\mathcal{R}^{\phi}(f).\end{split}$

Hoeffding’s decomposition breaks $\mathcal{S}_{\bf z}(\pi(f_{\bf z}))$ into a
sum of i.i.d. random variables $\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))$
called _empirical term_ and a degenerate $U$-statistics $\mathcal{S}_{{\bf
z},2}(\pi(f_{\bf z}))$ called _degenerate term_ which has zero conditional
expectation

$\mathbb{E}[h_{\pi(f_{\mathbf{z}})}(Z,Z^{\prime})-h_{f^{*}_{\phi}}(Z,Z^{\prime})|Z=z]=0.$

We derive bounds for the empirical term and degenerate term in the following
two subsections respectively.

###  4.2 Bounding the Empirical Term

In this subsection, we estimate the empirical term

$\mathcal{S}_{{\bf z},1}(\pi(f_{\bf
z}))=Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f_{\mathbf{z}})}+Q\phi_{f^{*}_{\phi}}]$

which can be further bounded by the supremum norm of an empirical process
indexed by $\mathcal{H}_{K}$, i.e.,

$\mathcal{S}_{{\bf z},1}(\pi(f_{\bf
z}))\leq\sup_{f\in\mathcal{H}_{K}}Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f)}+Q\phi_{f^{*}_{\phi}}].$

In the remaining part of this subsection, we will use Talagrand’s
concentration inequality together with local Rademacher averages to derive a
tight bound for the supremum norm of the empirical process. The idea of our
estimates can be found in Chapter 7 of [36], in which the authors established
refined oracle inequalities for classification with support vector machines.

Define $s_{f},g_{f,r}:\mathcal{Z}\to\mathbb{R}$ as
$s_{f}:=Q\phi_{f}-Q\phi_{f^{*}_{\phi}}$ with $Q\phi_{f}$ given by (2.4) and

$g_{f,r}:=\frac{\mathbb{E}s_{\pi(f)}-s_{\pi(f)}}{\lambda\|f\|^{2}_{K}+\mathbb{E}s_{\pi(f)}+r}$

for all $f\in\mathcal{H}_{K}$ and $r>0.$ Under Assumption 1, we apply
Talagrand’s inequality to obtain the following lemma.

######  Lemma 2.

If Assumption 1 holds, then for all $t>0$, with probability at least
$1-\exp(-t)$,

$\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|\leq\frac{5}{4}\mathbb{E}\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|+\sqrt{\frac{2Vt}{nr^{2-\tau}}}+\frac{28Bt}{3nr}.$

###### Proof.

Analogous to the proof of Proposition 1, by (2.5) of Assumption 1, obviously
$\|g_{f,r}\|_{\infty}\leq 2Br^{-1}$. For the variance bound, if $\tau>0$,
using Young’s inequality, we can prove that
$(qa)^{2/q}(pb)^{2/p}\leq(a+b)^{2}$, then setting
$a=r,b=\mathbb{E}s_{\pi(f)},q=2/(2-\tau),p=2/\tau$ yields

$\mathbb{E}g^{2}_{f,r}\leq\frac{\mathbb{E}s^{2}_{\pi(f)}}{(\mathbb{E}s_{\pi(f)}+r)^{2}}\leq\frac{(2-\tau)^{2-\tau}\tau^{\tau}V}{4r^{2-\tau}}\leq
Vr^{\tau-2}$

which also holds for $\tau=0$. Hence we can apply Talagrand’s inequality, cf.
Theorem 7.5 of [36], to $(g_{f,r})_{f\in\mathcal{H}_{K}}$, to derive the
desired bound. This completes the proof. ∎

In order to derive an upper bound of
$\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|$, we leverage standard
tools including peeling, symmetrization and Dudley’s chaining to estimate
$\mathbb{E}\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|$. Define

$\displaystyle r^{*}$
$\displaystyle:=\inf\\{\lambda\|f\|^{2}_{K}+\mathbb{E}s_{\pi(f)}:f\in\mathcal{H}_{K}\\},$
$\displaystyle\mathcal{F}_{r}$
$\displaystyle:=\\{f\in\mathcal{H}_{K}:\lambda\|f\|^{2}_{K}+\mathbb{E}s_{\pi(f)}\leq
r\\},\ \forall r>r^{*},$ $\displaystyle\mathcal{S}_{r}$
$\displaystyle:=\\{s_{\pi(f)}:f\in\mathcal{F}_{r}\\},\ \forall r>r^{*},$

and the _empirical Rademacher complexity_ of $\mathcal{S}_{r}$

$\text{Rad}(\mathcal{S}_{r},\mathbf{z}):=\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}_{r}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}s_{\pi(f)}(Z_{i})\bigg{|},$

where $\\{\varepsilon_{i}\\}_{i=1}^{n}$ is the Rademacher sequence, i.e.,
$\\{\varepsilon_{i}\\}_{i=1}^{n}$ are i.i.d. random variables uniformly chosen
from $\\{-1,1\\}$. The following two lemmas present peeling and symmetrization
arguments to handle
$\mathbb{E}\sup_{f\in\mathcal{F}_{r}}|Q_{\mathbf{z}}(\mathbb{E}s_{\pi(f)}-s_{\pi(f)})|$,
which can be proved according to Theorem 7.7 and Proposition 7.10 in [36].

######  Lemma 3.

Let $\varphi:(r^{*},\infty)\to[0,\infty)$ such that $\varphi(4r)\leq
2\varphi(r)$ and

$\mathbb{E}\sup_{f\in\mathcal{F}_{r}}|Q_{\mathbf{z}}(\mathbb{E}s_{\pi(f)}-s_{\pi(f)})|\leq\varphi(r)$

for all $r>r^{*}$. Then for all $r>r^{*}$, we have

$\mathbb{E}\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|\leq\frac{4\varphi(r)}{r}.$

######  Lemma 4.

$\mathbb{E}\sup_{f\in\mathcal{F}_{r}}|Q_{\mathbf{z}}(\mathbb{E}s_{\pi(f)}-s_{\pi(f)})|\leq
2\mathbb{E}\operatorname{Rad}(\mathcal{S}_{r},\mathbf{z}).$

We then apply Theorem 7.16 of [36] to derive the following lemma.

######  Lemma 5.

If Assumption 1 and Assumption 2 hold, then there exist constants $k_{1}>0$
and $k_{2}>0$ such that

$\displaystyle\mathbb{E}\operatorname{Rad}(\mathcal{S}_{r},\mathbf{z})\leq{}\max\bigg{\\{}$
$\displaystyle
2^{p_{1}}k_{1}a_{1}^{p_{1}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{2}}(Vr^{\tau})^{\frac{1-p_{1}}{2}}L^{p_{1}}n^{-\frac{1}{2}},$
$\displaystyle
4^{\frac{p_{1}}{1+p_{1}}}k_{2}a_{1}^{\frac{2p_{1}}{1+p_{1}}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{1+p_{1}}}B^{\frac{1-p_{1}}{1+p_{1}}}L^{\frac{2p_{1}}{1+p_{1}}}n^{-\frac{1}{1+p_{1}}}\bigg{\\}}.$

###### Proof.

We first establish the sup-norm bound and variance bound for
$s_{\pi(f)}\in\mathcal{S}_{r}.$ By Assumption 1 we have
$\|s_{\pi(f)}\|_{\infty}\leq B$ and

$\mathbb{E}(s^{2}_{\pi(f)})=\mathbb{E}(Q\phi_{\pi(f)}-Q\phi_{f^{*}_{\phi}})^{2}\leq
V\big{(}\mathbb{E}(Q\phi_{\pi(f)}-Q\phi_{f^{*}_{\phi}})\big{)}^{\tau}=V(\mathbb{E}s_{\pi(f)})^{\tau}\leq
Vr^{\tau}.$

For $\mathbf{z}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, the empirical norm
$\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{z}})}$ on $\mathcal{S}_{r}$ is
defined as

$\|s_{\pi(f)}\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{z}})}:=Q_{\mathbf{z}}^{\frac{1}{2}}(s^{2}_{\pi(f)})=\bigg{(}\frac{1}{n}\sum_{i=1}^{n}s_{\pi(f)}(Z_{i})^{2}\bigg{)}^{\frac{1}{2}}.$

According to Theorem 7.16 of [36], it remains to bound
$\mathbb{E}e_{i}(\textrm{id}:\mathcal{S}_{r}\to\mathcal{L}_{2}(P^{n}_{\mathbf{z}})).$
For all $(y,y^{\prime})\in\mathcal{Y}\times\mathcal{Y}$, function
$\phi(y,y^{\prime},\cdot)$ is locally $L$-Lipschitz over $[-M,M]$. Hence for
all $s_{\pi(f)},s_{\pi(f^{\prime})}\in\mathcal{S}_{r}$ and
$\mathbf{z}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ we have

$\displaystyle\|s_{\pi(f)}-s_{\pi(f^{\prime})}\|^{2}_{\mathcal{L}_{2}(P^{n}_{\mathbf{z}})}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\big{(}s_{\pi(f)}(Z_{i})-s_{\pi(f^{\prime})}(Z_{i})\big{)}^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\bigg{(}\mathbb{E}\bigg{[}\phi(Y_{i},Y^{\prime},\pi(f)(X_{i},X^{\prime}))-\phi(Y_{i},Y^{\prime},\pi(f^{\prime})(X_{i},X^{\prime}))\bigg{]}\bigg{)}^{2}$
$\displaystyle\leq\frac{L^{2}}{n}\sum_{i=1}^{n}\bigg{(}\mathbb{E}\bigg{|}\pi(f)(X_{i},X^{\prime})-\pi(f^{\prime})(X_{i},X^{\prime})\bigg{|}\bigg{)}^{2}$
$\displaystyle\leq\frac{L^{2}}{n}\sum_{i=1}^{n}\mathbb{E}\bigg{|}\pi(f)(X_{i},X^{\prime})-\pi(f^{\prime})(X_{i},X^{\prime})\bigg{|}^{2}$
$\displaystyle\leq
L^{2}\|f-f^{\prime}\|^{2}_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}})}.$

Therefore, an $\varepsilon$-net of
$(\mathcal{F}_{r},\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}})})$ induces an $L\varepsilon$-net of
$(\mathcal{S}_{r},\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{z}})})$. Besides,
notice that
$\mathcal{F}_{r}\subset(r/\lambda)^{1/2}\mathcal{B}_{\mathcal{H}_{K}}$.
Combine with Assumption 2 we have

$\displaystyle\mathbb{E}e_{i}(\textrm{id}:\mathcal{S}_{r}\to\mathcal{L}_{2}(P^{n}_{\mathbf{z}}))$
$\displaystyle\leq
L\mathbb{E}e_{i}(\textrm{id}:\mathcal{F}_{r}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}))$ $\displaystyle\leq
2L(r/\lambda)^{1/2}\mathbb{E}e_{i}(\textrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}))$ $\displaystyle\leq
2L(r/\lambda)^{1/2}a_{1}i^{-\frac{1}{2p_{1}}}.$

Now we apply Theorem 7.16 of [36] and derive the desired bound. The proof is
then finished. ∎

With the help of the preceding lemmas, we can now establish an upper bound for
empirical term $\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))$.

######  Proposition 2.

If Assumption 1 and Assumption 2 hold, there exist constants

$c_{1}:=\frac{\big{(}2^{p_{1}}\cdot 270k_{1}\big{)}^{\frac{2}{2-\tau-
p_{1}+p_{1}\tau}}}{3},\quad
c_{2}:=\frac{2^{1+3p_{1}}\big{(}135k_{2}\big{)}^{1+p_{1}}}{3}$

such that for all $t>0$ , $n\geq 72t$ and $f_{0}\in\mathcal{H}_{K}$, with
probability at least $1-\exp(-t)$,

$\displaystyle\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))$
$\displaystyle\leq\frac{1}{3}\left(\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)+\frac{1}{3}\left(\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)$
$\displaystyle+c_{1}\left(\frac{a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}+\frac{c_{2}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}+\left(\frac{24Vt}{n}\right)^{\frac{1}{2-\tau}}.$

###### Proof.

By Lemma 5 we have

$\displaystyle\mathbb{E}\operatorname{Rad}(\mathcal{S}_{r},\mathbf{z})\leq{}\max\bigg{\\{}$
$\displaystyle
2^{p_{1}}k_{1}a_{1}^{p_{1}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{2}}(Vr^{\tau})^{\frac{1-p_{1}}{2}}L^{p_{1}}n^{-\frac{1}{2}},$
$\displaystyle
4^{\frac{p_{1}}{1+p_{1}}}k_{2}a_{1}^{\frac{2p_{1}}{1+p_{1}}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{1+p_{1}}}B^{\frac{1-p_{1}}{1+p_{1}}}L^{\frac{2p_{1}}{1+p_{1}}}n^{-\frac{1}{1+p_{1}}}\bigg{\\}}.$

Define

$\displaystyle\varphi(r):=\max\bigg{\\{}$ $\displaystyle
2^{p_{1}+1}k_{1}a_{1}^{p_{1}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{2}}(Vr^{\tau})^{\frac{1-p_{1}}{2}}L^{p_{1}}n^{-\frac{1}{2}},$
$\displaystyle
2^{\frac{1+3p_{1}}{1+p_{1}}}k_{2}a_{1}^{\frac{2p_{1}}{1+p_{1}}}\left(\frac{r}{\lambda}\right)^{\frac{p_{1}}{1+p_{1}}}B^{\frac{1-p_{1}}{1+p_{1}}}L^{\frac{2p_{1}}{1+p_{1}}}n^{-\frac{1}{1+p_{1}}}\bigg{\\}}.$

One can verify that $\varphi(4r)\leq 2\varphi(r)$. By Lemma 2, Lemma 3 and
Lemma 4, for all $t>0$ we have

$P\left(\sup_{f\in\mathcal{H}_{K}}|Q_{\mathbf{z}}(g_{f,r})|\leq\frac{5\varphi(r)}{r}+\sqrt{\frac{2Vt}{r^{2-\tau}n}}+\frac{28Bt}{3nr}\right)\geq
1-\exp(-t).$

For $f_{\mathbf{z}}\in\mathcal{H}_{K}$, by the definition of
$g_{f_{\mathbf{z}},r}$, we have, with probability at least $1-\exp(-t)$,

$\displaystyle
Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f_{\mathbf{z}})}+Q\phi_{f^{*}_{\phi}}]$
$\displaystyle\leq{}$
$\displaystyle(\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})+r)\left(\frac{5\varphi(r)}{r}+\sqrt{\frac{2Vt}{r^{2-\tau}n}}+\frac{28Bt}{3nr}\right).$

If there exists an

$r\geq\max\bigg{\\{}135\varphi(r),\left(\frac{72Vt}{n}\right)^{\frac{1}{2-\tau}},r^{*}\bigg{\\}},$

then using simple algebra and the assumption $n\geq 72t$ we have

$\frac{5\varphi(r)}{r}\leq\frac{1}{27},\quad\sqrt{\frac{2Vt}{r^{2-\tau}n}}\leq\frac{1}{6},\quad\frac{28Bt}{3nr}\leq\frac{28V^{\frac{1}{2-\tau}}t}{3nr}\leq\frac{7}{54}.$

Hence with probability at least $1-\exp(-t)$,

$\begin{split}&Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f_{\mathbf{z}})}+Q\phi_{f^{*}_{\phi}}]\\\
\leq{}&\frac{1}{3}(\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})+r).\end{split}$
(4.7)

It remains to find such $r$. By definition of $\varphi(r)$, if

$\displaystyle r$
$\displaystyle\geq\left(\frac{4^{p_{1}}\big{(}270k_{1}\big{)}^{2}a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}$
$\displaystyle\quad+\frac{2^{1+3p_{1}}\big{(}135k_{2}\big{)}^{1+p_{1}}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n},$

we have $r\geq 135\varphi(r)$. Besides, notice that
$r^{*}\leq\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})$,
it is sufficient to choose

$\displaystyle r={}$
$\displaystyle\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})+\left(\frac{4^{p_{1}}\big{(}270k_{1}\big{)}^{2}a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}$
$\displaystyle+\frac{2^{1+3p_{1}}\big{(}135k_{2}\big{)}^{1+p_{1}}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}+\left(\frac{72Vt}{n}\right)^{\frac{1}{2-\tau}}.$

Substitute this $r$ into (4.7) and choose

$c_{1}=\frac{\big{(}2^{p_{1}}\cdot 270k_{1}\big{)}^{\frac{2}{2-\tau-
p_{1}+p_{1}\tau}}}{3},\quad
c_{2}=\frac{2^{1+3p_{1}}\big{(}135k_{2}\big{)}^{1+p_{1}}}{3}.$

The proof of Proposition 2 is then finished. ∎

Here we remark that the condition $n\geq 72t$ in Proposition 2 is not
essential and we will leave the case $n<72t$ to the final proof of the general
oracle inequality in the next subsection.

###  4.3 Bounding the Degenerate Term

In this subsection, we use arguments of symmetrization and Dudley’s chaining
to bound the degenerate term

$\mathcal{S}_{{\bf z},2}(\pi(f_{\bf
z}))=U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}}).$

If Assumption 1 holds, since
$\mathcal{R}^{\phi}_{\mathbf{z}}(f_{\mathbf{z}})+\lambda\|f_{\mathbf{z}}\|^{2}_{K}\leq\mathcal{R}^{\phi}_{\mathbf{z}}(0)\leq
B$, we have $\|f_{\mathbf{z}}\|_{K}\leq\sqrt{B/\lambda}$. Recalling the
Rademacher sequence $\\{\varepsilon_{i}\\}_{i=1}^{n}$, define

$\displaystyle\mathcal{F}$
$\displaystyle:=\\{f\in\mathcal{H}_{K}:\|f\|_{K}\leq\sqrt{B/\lambda}\\},$
$\displaystyle S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})$
$\displaystyle:=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\varepsilon_{i}\varepsilon_{j}\big{(}h_{\pi(f)}(Z_{i},Z_{j})-h_{f^{*}_{\phi}}(Z_{i},Z_{j})\big{)}.$

Then $f_{\mathbf{z}}\in\mathcal{F}$.

######  Lemma 6.

There exist constants $C_{1}>0,C_{2}>0$ such that, for all $\xi>0$

$\displaystyle\mathbb{E}\exp\left(\xi\sqrt{\sup_{f\in\mathcal{F}}|(n-1)U_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|}\right)$
$\displaystyle\leq{}$ $\displaystyle
C_{1}\mathbb{E}\mathbb{E}_{\varepsilon}\exp\left(C_{2}\xi\sqrt{\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|}\right)$

###### Proof.

Define $\varphi_{1}(t):=\exp(\xi\sqrt{t})$ and

$\varphi_{2}(t):=\begin{cases}e&0\leq t\leq\xi^{-2}\\\
\exp(\xi\sqrt{t})&t\geq\xi^{-2}.\\\ \end{cases}$

Then $\varphi_{2}$ is convex, non-decreasing, and the following inequality
holds:

$\varphi_{2}(t)e^{-1}\leq\varphi_{1}(t)\leq\varphi_{2}(t).$ (4.8)

We can apply the symmetrization argument in the theory of $U$-processes with
$\varphi_{2}$, cf. Remarks 3.5.4 of [24], to show that there exist constants
$C^{\prime}_{1}>0$ and $C^{\prime}_{2}>0$ such that

$\mathbb{E}\varphi_{2}(\sup_{f\in\mathcal{F}}|(n-1)U_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|)\leq
C^{\prime}_{1}\mathbb{E}\mathbb{E}_{\varepsilon}\varphi_{2}\big{(}C^{\prime}_{2}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|\big{)}.$

Combining this with the inequality (4.8) finishes the proof. ∎

######  Lemma 7.

There exist constants $C_{3}>0,C_{4}>0$ such that, for all $\xi>0$,

$\displaystyle
C_{1}\mathbb{E}\mathbb{E}_{\varepsilon}\exp\left(C_{2}\xi\sqrt{\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|}\right)$
$\displaystyle\leq{}$ $\displaystyle
C_{3}\mathbb{E}\exp\left(C_{4}\xi^{2}\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|\right).$

###### Proof.

Define a Rademacher chaos of order two
$R_{1}:=C_{2}^{2}\xi^{2}(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})$, and

$\|R_{1}\|:=\sup_{f\in\mathcal{F}}C_{2}^{2}\xi^{2}(n-1)|S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|.$

By formula (3.5) of [3], there exist constants
$C^{\prime}_{3}>0,C^{\prime}_{4}>0$ such that

$\mathbb{E}_{\varepsilon}\exp(\|R_{1}\|^{1/2})\leq
C^{\prime}_{3}\exp(C^{\prime}_{4}(\mathbb{E}_{\varepsilon}\|R_{1}\|^{2})^{1/2}).$
(4.9)

Besides, by Hölder’s inequality and formula (3.4) of [3] we have

$\displaystyle(\mathbb{E}_{\varepsilon}\|R_{1}\|^{2})^{1/2}$
$\displaystyle=(\mathbb{E}_{\varepsilon}\|R_{1}\|^{1/2}\|R_{1}\|^{3/2})^{1/2}$
$\displaystyle\leq(\mathbb{E}_{\varepsilon}\|R_{1}\|)^{1/4}(\mathbb{E}_{\varepsilon}\|R_{1}\|^{3})^{1/4}$
$\displaystyle\leq
2^{3/4}(\mathbb{E}_{\varepsilon}\|R_{1}\|)^{1/4}(\mathbb{E}_{\varepsilon}\|R_{1}\|^{2})^{3/8},$

which is equivalent to

$(\mathbb{E}_{\varepsilon}\|R_{1}\|^{2})^{1/2}\leq
8\mathbb{E}_{\varepsilon}\|R_{1}\|.$

Combining this with (4.9) we complete the proof. ∎

Next we bound
$\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|$
by the chaining argument.

######  Lemma 8.

If Assumption 1 and Assumption 2 hold, then there exists a constant $C_{5}>0$
such that

$\displaystyle\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|$
$\displaystyle\leq{}$ $\displaystyle(\log
4)C_{5}B\bigg{[}\bigg{(}\frac{3a_{1}^{2}L^{2}}{2\lambda
B}\bigg{)}^{p_{1}}\frac{4^{1-2p_{1}}}{1-2p_{1}}+\bigg{(}\frac{3a_{2}^{2}L^{2}}{4\lambda
B}\bigg{)}^{p_{2}}\frac{4^{1-2p_{2}}}{1-2p_{2}}\bigg{]}+\frac{(1+\log
4\sqrt{3})C_{5}B}{4}.$

###### Proof.

Define

$\mathcal{G}:=\\{h_{\pi(f)}-h_{f^{*}_{\phi}}:f\in\mathcal{F}\\}\cup\\{0:\mathcal{Z}\times\mathcal{Z}\to\mathbb{R}\\}.$

By (2.5) of Assumption 1, $\|h\|_{\infty}\leq 4B$ for all $h\in\mathcal{G}$.
Now given $\mathbf{z}=\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, define a stochastic
process $J_{\mathbf{z}}$ and a pseudometric $\rho$ on $\mathcal{G}$ as

$\displaystyle J_{\mathbf{z}}(h)$
$\displaystyle:=\frac{1}{4Bn}\sum_{i=1}^{n}\sum_{j\neq
i}\varepsilon_{i}\varepsilon_{j}h(Z_{i},Z_{j}),\quad h\in\mathcal{G},$
$\displaystyle\rho(h,h^{\prime})$
$\displaystyle:=\frac{1}{4B}\sqrt{\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}^{2}},\quad
h,h^{\prime}\in\mathcal{G}.$

We will apply chaining lemma for $U$-processes to
$\\{J_{\mathbf{z}}(h):h\in\mathcal{G}\\}$, cf. Lemma 5 of [28]. To this end we
need to find a convex, strictly increasing function
$\varphi:[0,\infty)\to[0,\infty)$ such that $0\leq\varphi(0)\leq 1$ and for
all $\rho(h,h^{\prime})>0$,

$\mathbb{E}_{\varepsilon}\varphi\left(\frac{|J_{\mathbf{z}}(h)-J_{\mathbf{z}}(h^{\prime})|}{\rho(h,h^{\prime})}\right)\leq
1.$

Define a Rademacher chaos of order two
$R_{2}:=J_{\mathbf{z}}(h)-J_{\mathbf{z}}(h^{\prime}).$ By Corollary 3.2.6 of
[24], there exists a constant $\kappa>0$ which is independent of
$h,h^{\prime},n$ such that

$\mathbb{E}_{\varepsilon}\exp\left(\frac{|R_{2}|}{\kappa(\mathbb{E}_{\varepsilon}|R_{2}|^{2})^{1/2}}\right)\leq
e.$ (4.10)

Notice that

$\displaystyle\mathbb{E}_{\varepsilon}|R_{2}|^{2}={}$
$\displaystyle\frac{1}{16B^{2}n^{2}}\mathbb{E}_{\varepsilon}\bigg{(}\sum_{i\neq
j}\varepsilon_{i}\varepsilon_{j}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}\bigg{)}^{2}$
$\displaystyle={}$ $\displaystyle\frac{1}{16B^{2}n^{2}}\bigg{(}\sum_{i=k\neq
j=l}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}\big{(}h(Z_{k},Z_{l})-h^{\prime}(Z_{k},Z_{l})\big{)}$
$\displaystyle+\sum_{i=l\neq
j=k}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}\big{(}h(Z_{k},Z_{l})-h^{\prime}(Z_{k},Z_{l})\big{)}\bigg{)}$
$\displaystyle={}$ $\displaystyle\frac{1}{8B^{2}n^{2}}\sum_{i\neq
j}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}^{2}$
$\displaystyle\leq{}$ $\displaystyle 2\rho(h,h^{\prime})^{2}.$ (4.11)

Hence if we choose $\varphi(t)=\exp(\frac{t}{\sqrt{2}\kappa}-1)$, by (4.10)
and (4.3), we have

$\displaystyle\mathbb{E}_{\varepsilon}\varphi\left(\frac{|J_{\mathbf{z}}(h)-J_{\mathbf{z}}(h^{\prime})|}{\rho(h,h^{\prime})}\right)$
$\displaystyle\leq\mathbb{E}_{\varepsilon}\varphi\left(\frac{\sqrt{2}|R_{2}|}{(\mathbb{E}_{\varepsilon}|R_{2}|^{2})^{1/2}}\right)$
$\displaystyle=\mathbb{E}_{\varepsilon}\exp\left(\frac{|R_{2}|}{\kappa(\mathbb{E}_{\varepsilon}|R_{2}|^{2})^{1/2}}-1\right)\leq
1.$

Fix $h^{\prime}=0\in\mathcal{G}$, obviously
$\sup_{h\in\mathcal{G}}\rho(h,0)\leq 1$, and

$4B\mathbb{E}_{\varepsilon}\sup_{h\in\mathcal{G}}|J_{\mathbf{z}}(h)-J_{\mathbf{z}}(0)|=\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|.$

Therefore, by Lemma 5 of [28], we obtain

$\begin{split}\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|&\leq
32B\int_{0}^{\frac{1}{4}}\varphi^{-1}(\mathcal{N}(\mathcal{G},\rho,\delta))\,d\delta\\\
&\leq
C_{5}B\int_{0}^{\frac{1}{4}}\log\mathcal{N}(\mathcal{G},\rho,\delta)\,d\delta,\end{split}$
(4.12)

where $C_{5}=64\sqrt{2}\kappa$. It remains to bound the metric entropy
$\log\mathcal{N}(\mathcal{G},\rho,\delta)$. We write

$\displaystyle 16B^{2}\rho^{2}(h,h^{\prime})$ $\displaystyle={}$
$\displaystyle\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\big{(}h(Z_{i},Z_{j})-h^{\prime}(Z_{i},Z_{j})\big{)}^{2}$
$\displaystyle\leq{}$ $\displaystyle\frac{4}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\bigg{[}\big{(}\phi_{\pi(f)}(Z_{i},Z_{j})-\phi_{\pi(f^{\prime})}(Z_{i},Z_{j})\big{)}^{2}$
$\displaystyle+\big{(}Q\phi_{\pi(f)}(Z_{i})-Q\phi_{\pi(f^{\prime})}(Z_{i})\big{)}^{2}+\big{(}Q\phi_{\pi(f)}(Z_{j})-Q\phi_{\pi(f^{\prime})}(Z_{j})\big{)}^{2}$
$\displaystyle+\big{(}\mathcal{R}^{\phi}(\pi(f))-\mathcal{R}^{\phi}(\pi(f^{\prime}))\big{)}^{2}\bigg{]}$
$\displaystyle\leq{}$ $\displaystyle\frac{4}{n(n-1)}\sum_{i=1}^{n}\sum_{j\neq
i}\bigg{[}L^{2}\big{(}\pi(f)(X_{i},X_{j})-\pi(f^{\prime})(X_{i},X_{j})\big{)}^{2}$
$\displaystyle+L^{2}\mathbb{E}\big{(}\pi(f)(X_{i},X^{\prime})-\pi(f^{\prime})(X_{i},X^{\prime})\big{)}^{2}+L^{2}\mathbb{E}\big{(}\pi(f)(X_{j},X^{\prime})-\pi(f^{\prime})(X_{j},X^{\prime})\big{)}^{2}$
$\displaystyle+\big{(}\mathcal{R}^{\phi}(\pi(f))-\mathcal{R}^{\phi}(\pi(f^{\prime}))\big{)}^{2}\bigg{]}$
$\displaystyle\leq{}$ $\displaystyle
4L^{2}\|f-f^{\prime}\|^{2}_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})}+8L^{2}\|f-f^{\prime}\|^{2}_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}})}+4\big{(}\mathcal{R}^{\phi}(\pi(f))-\mathcal{R}^{\phi}(\pi(f^{\prime}))\big{)}^{2},$

where the second inequality follows from the assumption that $\phi$ is
$L$-Lipschitz with respect to the third argument. This implies that

$\displaystyle\mathcal{N}(\mathcal{G},\rho,\delta)\leq{}$
$\displaystyle\mathcal{N}\bigg{(}\mathcal{F},\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})},\frac{2B\delta}{\sqrt{3}L}\bigg{)}\cdot\mathcal{N}\bigg{(}\mathcal{F},\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}})},\frac{\sqrt{2}B\delta}{\sqrt{3}L}\bigg{)}\cdot\mathcal{N}\bigg{(}[0,B],|\cdot|,\frac{2B\delta}{\sqrt{3}}\bigg{)}$
$\displaystyle={}$
$\displaystyle\mathcal{N}\bigg{(}\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}}),2\sqrt{\frac{\lambda
B}{3}}\frac{\delta}{L}\bigg{)}\cdot\mathcal{N}\bigg{(}\mathrm{id}:\mathcal{H}_{K}\to\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes
P_{\mathcal{X}}),\sqrt{\frac{2\lambda B}{3}}\frac{\delta}{L}\bigg{)}$
$\displaystyle\cdot\mathcal{N}\bigg{(}[0,B],|\cdot|,\frac{2B\delta}{\sqrt{3}}\bigg{)}.$

By Assumption 2 we have

$\log\mathcal{N}(\mathcal{G},\rho,\delta)\leq\log
4\cdot\bigg{(}\frac{3a_{1}^{2}L^{2}}{2\lambda
B\delta^{2}}\bigg{)}^{p_{1}}+\log
4\cdot\bigg{(}\frac{3a_{2}^{2}L^{2}}{4\lambda
B\delta^{2}}\bigg{)}^{p_{2}}+\log\frac{\sqrt{3}}{\delta}.$

Since $p_{1},p_{2}\in(0,1/2)$, we integrate the right-hand side and yield the
desired bound by (4.12). The proof is then finished. ∎

With the help of the preceding lemmas, we can now establish an upper bound for
degenerate term $\mathcal{S}_{{\bf z},2}(\pi(f_{\bf z}))$.

######  Proposition 3.

If Assumption 1 and Assumption 2 hold, there exist constants

$\displaystyle c_{0}:=C_{3},\quad c_{3}:=\frac{(64\log
2)C_{4}C_{5}3^{p_{1}}}{32^{p_{1}}(1-2p_{1})},\quad c_{4}:=\frac{(64\log
2)C_{4}C_{5}3^{p_{2}}}{64^{p_{2}}(1-2p_{2})},\quad c_{5}:=(2+\log
48)C_{4}C_{5},$

such that for all $t>0$ and $n\geq 2$, with probability at least
$1-c_{0}\exp(-t)$ we have

$\displaystyle|\mathcal{S}_{{\bf z},2}(\pi(f_{\bf
z}))|\leq\frac{c_{3}a_{1}^{2p_{1}}L^{2p_{1}}B^{1-p_{1}}t}{\lambda^{p_{1}}n}+\frac{c_{4}a_{2}^{2p_{2}}L^{2p_{2}}B^{1-p_{2}}t}{\lambda^{p_{2}}n}+\frac{c_{5}t}{n}.$

###### Proof.

Recall that $\mathcal{S}_{{\bf z},2}(\pi(f_{\bf
z}))=U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})$. Denote

$\omega:=(\log 4)C_{5}B\bigg{[}\bigg{(}\frac{3a_{1}^{2}L^{2}}{2\lambda
B}\bigg{)}^{p_{1}}\frac{4^{1-2p_{1}}}{1-2p_{1}}+\bigg{(}\frac{3a_{2}^{2}L^{2}}{4\lambda
B}\bigg{)}^{p_{2}}\frac{4^{1-2p_{2}}}{1-2p_{2}}\bigg{]}+\frac{(1+\log
4\sqrt{3})C_{5}B}{4}.$

Combine Lemma 6, Lemma 7 and Lemma 8 we have

$\displaystyle\mathbb{E}\exp\left(\xi\sqrt{|(n-1)U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})|}\right)$
$\displaystyle\leq{}$ $\displaystyle
C_{1}\mathbb{E}\mathbb{E}_{\varepsilon}\exp\left(C_{2}\xi\sqrt{\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|}\right)$
$\displaystyle\leq{}$ $\displaystyle
C_{3}\mathbb{E}\exp\left(C_{4}\xi^{2}\mathbb{E}_{\varepsilon}\sup_{f\in\mathcal{F}}|(n-1)S_{\mathbf{z}}(h_{\pi(f)}-h_{f^{*}_{\phi}})|\right)\leq
C_{3}\exp\left(C_{4}\xi^{2}\omega\right).$

By Markov’s inequality we conclude that for all $t^{\prime}>0$ and $\xi>0$, we
have

$P\left(|(n-1)U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})|\geq
t^{\prime}\right)\leq C_{3}\exp(C_{4}\xi^{2}\omega-\xi\sqrt{t^{\prime}}).$

Let $t^{\prime}=4C_{4}\omega t$ and
$\xi=\frac{\sqrt{t^{\prime}}}{2C_{4}\omega}$, we have

$\begin{split}&P\left(|U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})|\geq\frac{8C_{4}\omega
t}{n}\right)\\\
\leq{}&P\left(|(n-1)U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})|\geq
4C_{4}\omega t\right)\\\ \leq{}&C_{3}\exp(-t).\end{split}$

This completes the proof of Proposition 3. ∎

Now we are in the position to prove Theorem 1 which presents the general
oracle inequality for excess $\phi$-ranking risk and its variant in Theorem 2
for margin-based losses.

###### Proof of Theorem 1.

By error decomposition (4.1) and Hoeffding’s decomposition (4.6) we have

$\displaystyle\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})$
$\displaystyle\leq{}$
$\displaystyle\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+\big{(}\mathcal{R}^{\phi}_{\mathbf{z}}(f_{0})-\mathcal{R}^{\phi}_{\mathbf{z}}(f^{*}_{\phi})-\mathcal{R}^{\phi}(f_{0})+\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}$
$\displaystyle+2Q_{\mathbf{z}}[\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})-Q\phi_{\pi(f_{\mathbf{z}})}+Q\phi_{f^{*}_{\phi}}]-U_{\mathbf{z}}(h_{\pi(f_{\mathbf{z}})}-h_{f^{*}_{\phi}})$
$\displaystyle={}$ $\displaystyle\mathcal{A}(\lambda,f_{0})+\mathcal{S}_{\bf
z}(f_{0})+2\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))-\mathcal{S}_{{\bf
z},2}(\pi(f_{\bf z})).$

If $n<72t$, by (2.5) of Assumption 1 and $\|\phi_{f_{0}}\|_{\infty}\leq
B_{0}$, we have

$\displaystyle\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})$
$\displaystyle\leq{}$
$\displaystyle\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+(B_{0}+B)+(2B+2B)+4B$
$\displaystyle={}$
$\displaystyle\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+9B+B_{0}$
$\displaystyle\leq{}$ $\displaystyle
8\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+\frac{900Bt}{n}+\frac{456B_{0}t}{n}.$

The conclusion then follows immediately.

If $n\geq 72t$, by Proposition 1, with probability at most $4\exp(-t)$, there
holds

$\mathcal{S}_{\bf
z}(f_{0})\geq\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})+\left(\frac{8Vt}{n}\right)^{\frac{1}{2-\tau}}+\frac{300Bt}{n}+\frac{152B_{0}t}{n}.$

By Proposition 2, with probability at most $\exp(-t)$, there holds

$\displaystyle\mathcal{S}_{{\bf z},1}(\pi(f_{\bf z}))\geq{}$
$\displaystyle\frac{1}{3}\left(\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)+\frac{1}{3}\left(\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)$
$\displaystyle+c_{1}\left(\frac{a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}+\frac{c_{2}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}+\left(\frac{24Vt}{n}\right)^{\frac{1}{2-\tau}}.$

By Proposition 3, with probability at most $c_{0}\exp(-t)$, there holds

$\displaystyle|\mathcal{S}_{{\bf z},2}(\pi(f_{\bf
z}))|\geq\frac{c_{3}a_{1}^{2p_{1}}L^{2p_{1}}B^{1-p_{1}}t}{\lambda^{p_{1}}n}+\frac{c_{4}a_{2}^{2p_{2}}L^{2p_{2}}B^{1-p_{2}}t}{\lambda^{p_{2}}n}+\frac{c_{5}t}{n}$

Finally, combing all the estimates above, with probability at least
$1-(c_{0}+5)\exp(-t)$, we have

$\displaystyle\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})$
$\displaystyle\leq{}$
$\displaystyle\big{(}\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\big{)}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})+\left(\frac{8Vt}{n}\right)^{\frac{1}{2-\tau}}+\frac{300Bt}{n}+\frac{152B_{0}t}{n}$
$\displaystyle+\frac{2}{3}\left(\lambda\|f_{\mathbf{z}}\|^{2}_{K}+\mathcal{R}^{\phi}(\pi(f_{\mathbf{z}}))-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)+\frac{2}{3}\left(\lambda\|f_{0}\|^{2}_{K}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})\right)$
$\displaystyle+2c_{1}\left(\frac{a_{1}^{2p_{1}}V^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}\right)^{\frac{1}{2-\tau-
p_{1}+p_{1}\tau}}+\frac{2c_{2}a_{1}^{2p_{1}}B^{1-p_{1}}L^{2p_{1}}}{\lambda^{p_{1}}n}+\left(\frac{96Vt}{n}\right)^{\frac{1}{2-\tau}}$
$\displaystyle+\frac{c_{3}a_{1}^{2p_{1}}L^{2p_{1}}B^{1-p_{1}}t}{\lambda^{p_{1}}n}+\frac{c_{4}a_{2}^{2p_{2}}L^{2p_{2}}B^{1-p_{2}}t}{\lambda^{p_{2}}n}+\frac{c_{5}t}{n}.$

The proof is then finished. ∎

###### Proof of Theorem 2.

Using the conditions on $\psi$ and the analysis conducted in subsection 5.3,
we see that Assumption 1 is satisfied and hence we apply Theorem 1 to yield
the conclusion. ∎

##  5 Deriving the Learning Rates for Gaussian Ranking Estimators

In this section, we apply the oracle inequality to derive fast learning rates
of Gaussian ranking estimator (1.4) with hinge loss and square loss. We first
estimate the capacity of pairwise Gaussian kernel space
$\mathcal{H}_{K^{\sigma}}$ under the assumption that the marginal of the data
generating distribution on the input space $\mathcal{X}\subset\mathbb{R}^{d}$
is supported on a set of upper box-counting dimension $\varrho\in(0,d]$. Then,
we derive approximation error bounds for the hinge loss under noise conditions
and the square loss under the Besov smoothness. Finally, we apply the well-
established oracle inequality and calibration inequality to derive fast
learning rates for the excess ranking risk. We also make some comparisons of
different noise conditions at the end of this section.

###  5.1 Entropy Number Estimate of Pairwise Gaussian Kernel Spaces

In this subsection, we write $\mathcal{H}_{K}(\mathcal{X}^{2})$ to emphasize
that the RKHS induced by the pairwise reproducing kernel $K$ consists of
functions defined on $\mathcal{X}^{2}=\mathcal{X}\times\mathcal{X}$, or
equivalently, $K$ is defined or restricted on
$\mathcal{X}^{2}\times\mathcal{X}^{2}$, where $\mathcal{X}$ will be specified
in the context. The traditional Gaussian kernel on
$\mathbb{R}^{2d}\times\mathbb{R}^{2d}$ with variance $\sigma>0$ is defined as

$\widetilde{K}^{\sigma}((x,x^{\prime}),(u,u^{\prime})):=\exp\left(-\frac{\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)$
(5.1)

and we denote by $\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$ the
induced RKHS restricted on $\mathcal{X}^{2}$, cf. [4]. Note that we require
the ranking estimators to be skew-symmetric. It is not suitable to choose
$\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$ as the hypothesis
space directly. However, we can decompose
$\widetilde{f}\in\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$ into a
symmetric part $(\widetilde{f}-f)$ and a skew-symmetric part $f$:

$\widetilde{f}(x,x^{\prime})=\frac{\widetilde{f}(x,x^{\prime})+\widetilde{f}(x^{\prime},x)}{2}+\frac{\widetilde{f}(x,x^{\prime})-\widetilde{f}(x^{\prime},x)}{2}=:(\widetilde{f}-f)+f$
(5.2)

which leads to an orthogonal decomposition of
$\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$ in
$\mathcal{L}_{2}(P^{2}_{\mathcal{X}})$ and also a decomposition of the
traditional Gaussian kernel given by

$\displaystyle\widetilde{K}^{\sigma}((x,x^{\prime})(u,u^{\prime}))$
$\displaystyle=\frac{\widetilde{K}^{\sigma}((x,x^{\prime}),(u,u^{\prime}))+\widetilde{K}^{\sigma}((x^{\prime},x),(u,u^{\prime}))}{2}$
$\displaystyle\qquad+\frac{\widetilde{K}^{\sigma}((x,x^{\prime}),(u,u^{\prime}))-\widetilde{K}^{\sigma}((x^{\prime},x),(u,u^{\prime}))}{2}.$

The skew-symmetric part of
$\widetilde{K}^{\sigma}((x,x^{\prime})(u,u^{\prime}))$ yields the pairwise
Gaussian kernel $K^{\sigma}((x,x^{\prime}),(u,u^{\prime}))$ of the form (1.3)
considered in this paper. According to the properties of reproducing kernels,
cf. [4], $\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})$ is a subspace of
$\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$ with
$\|f\|_{K^{\sigma}}=\|f\|_{\widetilde{K}^{\sigma}}$ for all
$f\in\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})$. Therefore, we can carry out
the entropy number estimate of $\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})$ by
using the existing estimates developed for
$\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})$. Concretely, [23]
showed that

$\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{\widetilde{K}^{\sigma}}([0,1]^{2d})\to
C([0,1]^{2d}),\varepsilon)\asymp\frac{\left(\log\frac{1}{\varepsilon}\right)^{2d+1}}{{\left(\log\log\frac{1}{\varepsilon}\right)^{2d}}},\quad\varepsilon\to
0.$

A refined analysis in [37] clarified the crucial dependency of constants on
$\sigma$ and the underlying space $\mathcal{X}\subset\mathbb{R}^{d}$:

$\begin{split}&\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}),\varepsilon)\\\
{}&\leq\mathcal{N}(\mathcal{X}^{2},\|\cdot\|_{\infty},\sigma)\cdot\binom{4e+2d}{2d}e^{-2d}\frac{\left(\log\frac{1}{\varepsilon}\right)^{2d+1}}{{\left(\log\log\frac{1}{\varepsilon}\right)^{2d}}}.\end{split}$
(5.3)

Based on these results above, we obtain the following proposition under the
intrinsic dimension assumption of $\mathcal{X}$.

######  Proposition 4.

If Assumption 6 holds, then $\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})$
satisfies Assumption 2 for all $p_{1}=p_{2}=p\in(0,1/2)$ and
$a_{1}=a_{2}=a:=(C^{*}_{\mathcal{X}}p^{-2d-1}\sigma^{-2\varrho})^{\frac{1}{2p}}.$

###### Proof.

First we show that

$\mathcal{N}(\mathrm{id}:\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}),\varepsilon)\leq\mathcal{N}(\mathrm{id}:\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}),\varepsilon).$

Recall that $\mathcal{B}_{\mathcal{F}}$ denotes the unit ball of a normed
space $(\mathcal{F},\|\cdot\|_{\mathcal{F}})$. Given an $\varepsilon$-net
$\\{\widetilde{f}_{1},\ldots,\widetilde{f}_{m}\\}$ of
$(\mathcal{B}_{\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})},\|\cdot\|_{\infty})$,
by the decomposition (5.2), it induces a set of skew-symmetric functions
$\\{f_{1},\ldots,f_{m}\\}\subset\mathcal{B}_{\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})}$.
Let
$f\in\mathcal{B}_{\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})}\subset\mathcal{B}_{\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})}$.
There exists a
$\widetilde{f}_{i}\in\\{\widetilde{f}_{1},\ldots,\widetilde{f}_{m}\\}$ such
that $\|\widetilde{f}_{i}-f\|_{\infty}\leq\varepsilon$. Notice that $f$ is
skew-symmetric. Then due to the decomposition (5.2), we have
$\|f_{i}-f\|_{\infty}\leq\|\widetilde{f}_{i}-f\|_{\infty}\leq\varepsilon$.
Hence $\\{f_{1},\ldots,f_{m}\\}$ is a $\varepsilon$-net of
$(B_{\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})},\|\cdot\|_{\infty})$. Then we
have the following estimate for all $p\in(0,1/2)$ by (2.14) and (5.3).

$\displaystyle\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}),\varepsilon)$ $\displaystyle\leq{}$
$\displaystyle\log\mathcal{N}(\mathrm{id}:\mathcal{H}_{\widetilde{K}^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}),\varepsilon)$ $\displaystyle\leq{}$
$\displaystyle\mathcal{N}(\mathcal{X}^{2},\|\cdot\|_{\infty},\sigma)\cdot\binom{4e+2d}{2d}e^{-2d}\frac{\left(\log\frac{4}{\varepsilon}\right)^{2d+1}}{{\left(\log\log\frac{4}{\varepsilon}\right)^{2d}}}$
$\displaystyle\leq{}$ $\displaystyle
C^{2}_{\mathcal{X}}\sigma^{-2\varrho}\binom{4e+2d}{2d}e^{-2d}\frac{\left(\log\frac{4}{\varepsilon}\right)^{2d+1}}{{\left(\log\log\frac{4}{\varepsilon}\right)^{2d}}}$
$\displaystyle\leq{}$ $\displaystyle
C^{2}_{\mathcal{X}}\sigma^{-2\varrho}\binom{4e+2d}{2d}e^{-2d}\left(\log\frac{4}{\varepsilon}\right)^{2d+1}$
$\displaystyle\leq{}$ $\displaystyle
C^{2}_{\mathcal{X}}\sigma^{-2\varrho}\binom{4e+2d}{2d}e^{-2d}\left(\frac{2d+1}{2p}\right)^{2d+1}4^{2p}e^{-2d-1}\varepsilon^{-2p}$
$\displaystyle\leq{}$ $\displaystyle
4C^{2}_{\mathcal{X}}\binom{4e+2d}{2d}\frac{(2d+1)^{2d+1}}{2^{2d+1}e^{4d+1}}p^{-2d-1}\sigma^{-2\varrho}\varepsilon^{-2p}.$

We then use the above estimate to establish a bound for the entropy number,
cf. Exercise 6.8 of [36], which is given by

$e_{i}(\mathrm{id}:\mathcal{H}_{K^{\sigma}}(\mathcal{X}^{2})\to
C(\mathcal{X}^{2}))\leq(C^{*}_{\mathcal{X}}p^{-2d-1}\sigma^{-2\varrho})^{\frac{1}{2p}}i^{-\frac{1}{2p}}$

where

$C^{*}_{\mathcal{X}}:=12C^{2}_{\mathcal{X}}\binom{4e+2d}{2d}\frac{(2d+1)^{2d+1}}{2^{2d+1}e^{4d+1}}.$

Notice that $\mathcal{L}_{2}$-seminorm
$\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}}\otimes P_{\mathcal{X}})}$ and
$\|\cdot\|_{\mathcal{L}_{2}(P^{n}_{\mathbf{x}^{2}})}$ are both dominated by
the sup-norm $\|\cdot\|_{\infty}$. Therefore, Assumption 2 holds for all
$p_{1}=p_{2}=p\in(0,1/2)$ and
$a_{1}=a_{2}=a:=(C^{*}_{\mathcal{X}}p^{-2d-1}\sigma^{-2\varrho})^{\frac{1}{2p}}.$
The proof is then finished. ∎

###  5.2 Bounding the Approximation Error

In this subsection, we aim to construct a suitable
$f_{0}\in\mathcal{H}_{K^{\sigma}}$ and bound the approximation error
$\lambda\|f_{0}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi}(f_{0})-\mathcal{R}^{\phi}(f^{*}_{\phi})$
for $\phi=\phi_{\mathrm{hinge}}$ and $\phi=\phi_{\mathrm{square}}$. Inspired
by the work of [36, 46], define

$\widetilde{\mathcal{K}}^{\sigma}(x,x^{\prime}):=\left(\frac{2}{\sigma\sqrt{\pi}}\right)^{d}\exp\left(-\frac{2\|(x,x^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)$

and an operator $\widetilde{\mathcal{K}}^{\sigma}*\cdot$ on
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ as

$\widetilde{\mathcal{K}}^{\sigma}*f(x,x^{\prime}):=\int_{\mathbb{R}^{2d}}\widetilde{\mathcal{K}}^{\sigma}(u,u^{\prime})f((x,x^{\prime})+(u,u^{\prime}))d(u,u^{\prime}),\forall
f\in\mathcal{L}_{2}(\mathbb{R}^{2d}).$

One can verify that

$\displaystyle\widetilde{\mathcal{K}}^{\sigma}*f(x,x^{\prime})$
$\displaystyle=\left(\frac{1}{\sigma\sqrt{\pi}}\right)^{d}\int_{\mathbb{R}^{2d}}\widetilde{K}^{\sigma}((x,x^{\prime}),(u,u^{\prime}))f\bigg{(}\bigg{(}1-\frac{1}{\sqrt{2}}\bigg{)}(x,x^{\prime})+\frac{1}{\sqrt{2}}(u,u^{\prime})\bigg{)}d(u,u^{\prime})$

where $\widetilde{K}^{\sigma}$ is the traditional Gaussian kernel given by
(5.1). Therefore, $\widetilde{\mathcal{K}}^{\sigma}*\cdot$ is essentially a
convolution operator which is a metric surjection from
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ to $\mathcal{H}_{\widetilde{K}^{\sigma}}$,
i.e.,
$\widetilde{\mathcal{K}}^{\sigma}*f\in\mathcal{H}_{\widetilde{K}^{\sigma}}$
and
$\|\widetilde{\mathcal{K}}^{\sigma}*f\|_{\widetilde{K}^{\sigma}}\leq\|f\|_{\mathcal{L}_{2}(\mathbb{R}^{2d})}$.
This motivates us to consider the following operator on
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ defined by

$\mathcal{K}^{\sigma}*f(x,x^{\prime}):=\frac{1}{2}\int_{\mathbb{R}^{2d}}\widetilde{\mathcal{K}}^{\sigma}(u,u^{\prime})\bigg{(}f((x,x^{\prime})+(u,u^{\prime}))-f((x^{\prime},x)+(u,u^{\prime}))\bigg{)}d(u,u^{\prime}).$

In fact, for all $f\in\mathcal{L}_{2}(\mathbb{R}^{2d})$,
$\mathcal{K}^{\sigma}*f(x,x^{\prime})$ is skew-symmetric, i.e.,
$\mathcal{K}^{\sigma}*f(x,x^{\prime})=-\mathcal{K}^{\sigma}*f(x^{\prime},x)$,
and if $f$ is skew-symmetric,
$\mathcal{K}^{\sigma}*f(x,x^{\prime})=\widetilde{\mathcal{K}}^{\sigma}*f(x,x^{\prime}).$
Moreover, if $f$ is symmetric, we have
$\mathcal{K}^{\sigma}*f(x,x^{\prime})=0$. For all
$\widetilde{f}\in\mathcal{L}_{2}(\mathbb{R}^{2d})$, by decomposition (5.2), we
write $\widetilde{f}=(\widetilde{f}-f)+f$ where $f$ is skew-symmetric while
$\widetilde{f}-f$ is symmetric. Then we have

$\|\mathcal{K}^{\sigma}*\widetilde{f}\|_{K^{\sigma}}=\|\mathcal{K}^{\sigma}*f\|_{K^{\sigma}}=\|\widetilde{\mathcal{K}}^{\sigma}*f\|_{\widetilde{K}^{\sigma}}\leq\|f\|_{\mathcal{L}_{2}(\mathbb{R}^{2d})}\leq\|\widetilde{f}\|_{\mathcal{L}_{2}(\mathbb{R}^{2d})}.$

Hence $\mathcal{K}^{\sigma}*\cdot$ is a metric surjection from
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ to $\mathcal{H}_{K^{\sigma}}$. Note that
the Bayes ranking rule $f^{*}_{\phi}$ of $\phi=\phi_{\mathrm{hinge}}$ and
$\phi=\phi_{\mathrm{square}}$, which we need to approximate, are skew-
symmetric. In the followings, we will act the convolution operator
$\widetilde{\mathcal{K}}^{\sigma}*\cdot$ on skew-symmetric functions to
construct efficient approximations of $f^{*}_{\phi}$ in
$\mathcal{H}_{K^{\sigma}}$ and then carry out the approximation analysis.

We first deal with hinge loss. Under margin-noise condition Assumption 5, we
establish the following proposition to bound the approximation error.

######  Proposition 5.

Denote $\mathcal{B}_{\mathbb{R}^{2d}}$ the unit closed ball in
$\mathbb{R}^{2d}$. Suppose that $\mathcal{X}^{2}\subset
r\mathcal{B}_{\mathbb{R}^{2d}}$ for $r>0$ and Assumption 5 holds with
$C_{**}>0$ and $\beta>0$. Then for all $\lambda>0,\sigma>0$, there exists an
$f_{0}\in\mathcal{H}_{K^{\sigma}}$ such that $\|f_{0}\|_{\infty}\leq 1$ and

$\displaystyle\lambda\|f_{0}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi_{\mathrm{hinge}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})\leq\frac{2^{2d+1}r^{2d}}{\Gamma(d)}\lambda\sigma^{-2d}+\frac{2^{\beta/2+1}C_{**}\Gamma(d+\frac{\beta}{2})}{\Gamma(d)}\sigma^{\beta}.$

###### Proof.

Recall that the Bayes ranking rule for hinge loss
$f^{*}_{\mathrm{hinge}}:\mathcal{X}^{2}\to\mathbb{R}$ takes the form

$f^{*}_{\mathrm{hinge}}(x,x^{\prime})=\mathrm{sgn}(\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})).$

Denote $\mathrm{vol}(\cdot)$ the Lebesgue measure on Euclidean space. Note
that if $\mathrm{vol}(\mathcal{X})=0$, for example, when $\mathcal{X}$ is a
submanifold with upper box-counting dimension $\varrho<d$, the trivial zero
extension of $f^{*}_{\phi}$ only yields the zero function in
$\mathcal{L}_{2}(\mathbb{R}^{2d})$. Hence, before we construct the
approximator using $\widetilde{\mathcal{K}}^{\sigma}*f^{*}_{\mathrm{hinge}}$,
we need to extend $f^{*}_{\mathrm{hinge}}$ to a domain with a positive measure
in a nontrivial way, while still maintaining the margin-noise condition.

To this end, we extend the posterior probabilities
$\eta_{+},\eta_{-},\eta_{=}:\mathcal{X}^{2}\to[0,1]$ to
$2r\mathcal{B}_{\mathbb{R}^{2d}}$. For all $(x,x^{\prime})\in\mathcal{X}^{2}$,
with a slight abuse of notation, denote
$\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2)$ the
open ball centered at $(x,x^{\prime})$ with radius $\Delta(x,x^{\prime})/2$,
where $\Delta(x,x^{\prime})$ is defined as (2.12). Since
$\mathcal{X}^{2}\subset r\mathcal{B}_{\mathbb{R}^{2d}}$, we have
$\Delta(x,x^{\prime})\leq 2r$ and
$\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2)\subset
2r\mathcal{B}_{\mathbb{R}^{2d}}$. For all $(u,u^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}\backslash\mathcal{X}^{2}$, define the
extension as

$\displaystyle\eta_{+}(u,u^{\prime})=1,\eta_{-}(u,u^{\prime})=\eta_{=}(u,u^{\prime})=0,$
$\displaystyle\qquad\forall(u,u^{\prime})\in\bigcup_{(x,x^{\prime})\in\mathcal{X}^{2}_{+}}\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2),$
$\displaystyle\eta_{-}(u,u^{\prime})=1,\eta_{+}(u,u^{\prime})=\eta_{=}(u,u^{\prime})=0,$
$\displaystyle\qquad\forall(u,u^{\prime})\in\bigcup_{(x,x^{\prime})\in\mathcal{X}^{2}_{-}}\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2),$
$\displaystyle\eta_{=}(u,u^{\prime})=1,\eta_{+}(u,u^{\prime})=\eta_{-}(u,u^{\prime})=0,$
$\displaystyle\qquad\forall(u,u^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}\backslash\bigcup_{(x,x^{\prime})\in\mathcal{X}^{2}_{+}\cup\mathcal{X}^{2}_{-}}\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2).$

Since
$\bigcup_{(x,x^{\prime})\in\mathcal{X}^{2}_{+}}\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2)$
and
$\bigcup_{(x,x^{\prime})\in\mathcal{X}^{2}_{-}}\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\Delta(x,x^{\prime})/2)$
have an empty intersection by definition of $\Delta(x,x^{\prime})$ and
triangle inequality, the extension is well-defined. Using extended
$\eta_{+},\eta_{-},\eta_{=}:2r\mathcal{B}_{\mathbb{R}^{2d}}\to[0,1]$, define

$\displaystyle(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+}$
$\displaystyle:=\\{(x,x^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}:\eta_{+}(x,x^{\prime})>\eta_{-}(x,x^{\prime})\\},$
$\displaystyle(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}$
$\displaystyle:=\\{(x,x^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}:\eta_{+}(x,x^{\prime})<\eta_{-}(x,x^{\prime})\\},$
$\displaystyle(2r\mathcal{B}_{\mathbb{R}^{2d}})_{=}$
$\displaystyle:=\\{(x,x^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}:\eta_{+}(x,x^{\prime})=\eta_{-}(x,x^{\prime})\\},$

and a new distant function $\widetilde{\Delta}:\mathcal{X}^{2}\to\mathbb{R}$
as

$\widetilde{\Delta}(x,x^{\prime}):=\begin{cases}\mathrm{dist}((x,x^{\prime}),(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}\cup(2r\mathcal{B}_{\mathbb{R}^{2d}})_{=})&(x,x^{\prime})\in\mathcal{X}^{2}_{+}\\\
\mathrm{dist}((x,x^{\prime}),(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+}\cup(2r\mathcal{B}_{\mathbb{R}^{2d}})_{=})&(x,x^{\prime})\in\mathcal{X}^{2}_{-}\\\
0&(x,x^{\prime})\in\mathcal{X}^{2}_{=}.\end{cases}$

Here $\mathcal{X}^{2}_{+},\mathcal{X}^{2}_{-}$ and $\mathcal{X}^{2}_{=}$ are
defined in (2.8) with original $\eta_{+},\eta_{-}$ and $\eta_{=}$.

We claim that with the redefined $\widetilde{\Delta}$, the margin-noise
condition holds with the power index $\beta$ and constant $2^{\beta}C_{**}$.
To see this, one may notice that for all
$(x,x^{\prime})\in\mathcal{X}^{2}_{+}$, if
$\widetilde{\Delta}(x,x^{\prime})<\Delta(x,x^{\prime})/2$, then there exists a
$(u,u^{\prime})\in(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}$ or
$(u,u^{\prime})\in(2r\mathcal{B}_{\mathbb{R}^{2d}})_{=}$ such that
$\mathrm{dist}((x,x^{\prime}),(u,u^{\prime}))<\Delta(x,x^{\prime})/2$. If
$(u,u^{\prime})\in(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}$, then it must be the
case that
$(u,u^{\prime})\in\mathcal{B}_{\mathbb{R}^{2d}}((v,v^{\prime}),\Delta(v,v^{\prime})/2)$
for some $(v,v^{\prime})\in\mathcal{X}^{2}_{-}$. By triangle inequality we
have

$\displaystyle\mathrm{dist}((x,x^{\prime}),(v,v^{\prime}))$
$\displaystyle\leq\mathrm{dist}((x,x^{\prime}),(u,u^{\prime}))+\mathrm{dist}((u,u^{\prime}),(v,v^{\prime}))$
$\displaystyle<\Delta(x,x^{\prime})/2+\Delta(v,v^{\prime})/2,$

which is a contradiction to the definition of $\Delta$. If
$(u,u^{\prime})\in(2r\mathcal{B}_{\mathbb{R}^{2d}})_{=}$, then

$(u,u^{\prime})\in
2r\mathcal{B}_{\mathbb{R}^{2d}}\backslash\bigcup_{(v,v^{\prime})\in\mathcal{X}^{2}_{+}\cup\mathcal{X}^{2}_{-}}\mathcal{B}_{\mathbb{R}^{2d}}((v,v^{\prime}),\Delta(v,v^{\prime})/2),$

which also contradicts to the fact that
$\mathrm{dist}((x,x^{\prime}),(u,u^{\prime}))<\Delta(x,x^{\prime})/2$.
Following the same argument, one can discuss the case when
$(x,x^{\prime})\in\mathcal{X}^{2}_{-}$. Hence we conclude that
$\widetilde{\Delta}(x,x^{\prime})\geq\Delta(x,x^{\prime})/2$ for all
$(x,x^{\prime})\in\mathcal{X}^{2}$. Then the margin-noise condition holds for
$\widetilde{\Delta}$, given by

$\begin{split}&\int_{\\{(x,x^{\prime})\in\mathcal{X}^{2}:\widetilde{\Delta}(x,x^{\prime})<t\\}}|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|dP_{\mathcal{X}}^{2}(x,x^{\prime})\\\
\leq{}&\int_{\\{(x,x^{\prime})\in\mathcal{X}^{2}:\Delta(x,x^{\prime})<2t\\}}|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|dP_{\mathcal{X}}^{2}(x,x^{\prime})\\\
\leq{}&2^{\beta}C_{**}t^{\beta}.\end{split}$ (5.4)

Now we extend the original $f^{*}_{\mathrm{hinge}}$ as

$f^{*}_{\mathrm{hinge}}(x,x^{\prime})=\mathbb{I}_{2r\mathcal{B}_{\mathbb{R}^{2d}}}(x,x^{\prime})\mathrm{sgn}(\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})).$

One can verify that $f^{*}_{\mathrm{hinge}}$ maintains skew-symmetric and
$f^{*}_{\mathrm{hinge}}\in\mathcal{L}_{2}(\mathbb{R}^{2d})$ with
$\|f^{*}_{\mathrm{hinge}}\|_{\mathcal{L}_{2}(\mathbb{R}^{2d})}\leq\sqrt{\mathrm{vol}(2r\mathcal{B}_{\mathbb{R}^{2d}})}=(2r)^{d}\sqrt{\mathrm{vol}(\mathcal{B}_{\mathbb{R}^{2d}})}.$
We choose $f_{0}\in\mathcal{H}_{K^{\sigma}}$ as

$f_{0}(x,x^{\prime})=(\pi\sigma^{2})^{-d/2}\widetilde{\mathcal{K}}^{\sigma}*f^{*}_{\mathrm{hinge}}(x,x^{\prime}).$

Since $\widetilde{\mathcal{K}}^{\sigma}*\cdot$ is a metric surjection,

$\|f_{0}\|_{K^{\sigma}}\leq(\pi\sigma^{2})^{-d/2}\|f^{*}_{\mathrm{hinge}}\|_{\mathcal{L}_{2}(\mathbb{R}^{2d})}\leq(\pi\sigma^{2})^{-d/2}(2r)^{d}\sqrt{\mathrm{vol}(\mathcal{B}_{\mathbb{R}^{2d}})}.$
(5.5)

Besides, by Young’s convolution inequality, there holds

$\|f_{0}\|_{\infty}\leq\frac{2^{d}}{\sigma^{2d}\pi^{d}}\|f^{*}_{\mathrm{hinge}}\|_{\infty}\int_{\mathbb{R}^{2d}}\exp\left(-\frac{2\|(x,x^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(x,x^{\prime})=1.$
(5.6)

It remains to bound the excess risk
$\mathcal{R}^{\phi_{\mathrm{hinge}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})$.
Fix a
$(x,x^{\prime})\in\mathcal{X}^{2}_{+}\subset(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+}$.
For all
$(u,u^{\prime})\in\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))$,
we have $(u,u^{\prime})\in(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+}$. Hence

$\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))\subset(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+},\quad(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}\subset\mathbb{R}^{2d}\backslash\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))$

and

$\displaystyle f_{0}(x,x^{\prime})$ $\displaystyle={}$
$\displaystyle\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\int_{\mathbb{R}^{2d}}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)f^{*}_{\mathrm{hinge}}(u,u^{\prime})d(u,u^{\prime})$
$\displaystyle={}$
$\displaystyle\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\left(\int_{(2r\mathcal{B}_{\mathbb{R}^{2d}})_{+}}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})\right.$
$\displaystyle\left.-\int_{(2r\mathcal{B}_{\mathbb{R}^{2d}})_{-}}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})\right)$
$\displaystyle\geq{}$
$\displaystyle\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\left(\int_{\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})\right.$
$\displaystyle\left.-\int_{\mathbb{R}^{2d}\backslash\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})\right)$
$\displaystyle={}$ $\displaystyle
2\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\int_{\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})-1.$

By (5.6) and $f^{*}_{\mathrm{hinge}}(x,x^{\prime})=1$, we derive that

$\displaystyle|f_{0}(x,x^{\prime})-f^{*}_{\mathrm{hinge}}(x,x^{\prime})|$
$\displaystyle={}$ $\displaystyle 1-f_{0}(x,x^{\prime})$ $\displaystyle\leq{}$
$\displaystyle
2-2\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\int_{\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})$
$\displaystyle={}$ $\displaystyle
2\left(\frac{2}{\pi\sigma^{2}}\right)^{d}\int_{\mathbb{R}^{2d}\backslash\mathcal{B}_{\mathbb{R}^{2d}}((x,x^{\prime}),\widetilde{\Delta}(x,x^{\prime}))}\exp\left(-\frac{2\|(x,x^{\prime})-(u,u^{\prime})\|^{2}_{2}}{\sigma^{2}}\right)d(u,u^{\prime})$
$\displaystyle={}$
$\displaystyle\frac{2^{d+2}}{\sigma^{2d}\Gamma(d)}\int_{\widetilde{\Delta}(x,x^{\prime})}^{\infty}\exp(-2\sigma^{-2}\rho^{2})\rho^{2d-1}d\rho$
$\displaystyle={}$
$\displaystyle\frac{2}{\Gamma(d)}\int_{2\widetilde{\Delta}(x,x^{\prime})^{2}\sigma^{-2}}^{\infty}e^{-\rho}\rho^{d-1}d\rho.$

This inequality also holds for all $(x,x^{\prime})\in\mathcal{X}^{2}_{-}$ by
the same argument. Note that

$\displaystyle\mathcal{R}^{\phi_{\mathrm{hinge}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})$
$\displaystyle=\mathbb{E}[\mathrm{sgn}(Y-Y^{\prime})\cdot(f^{*}_{\mathrm{hinge}}(X,X^{\prime})-f_{0}(X,X^{\prime}))]$
$\displaystyle=\mathbb{E}_{P_{\mathcal{X}}^{2}}[(\eta_{+}(X,X^{\prime})-\eta_{-}(X,X^{\prime}))\cdot(f^{*}_{\mathrm{hinge}}(X,X^{\prime})-f_{0}(X,X^{\prime}))],$

we apply our claim (5.4) and yield that

$\displaystyle\mathcal{R}^{\phi_{\mathrm{hinge}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})$
$\displaystyle={}$
$\displaystyle\int_{\mathcal{X}^{2}_{-}\cup\mathcal{X}^{2}_{+}}|f_{0}(x,x^{\prime})-f^{*}_{\mathrm{hinge}}(x,x^{\prime})|\cdot|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|dP^{2}_{\mathcal{X}}(x,x^{\prime})$
$\displaystyle\leq{}$
$\displaystyle\frac{2}{\Gamma(d)}\int_{\mathcal{X}^{2}_{-}\cup\mathcal{X}^{2}_{+}}\int_{2\widetilde{\Delta}(x,x^{\prime})^{2}\sigma^{-2}}^{\infty}e^{-\rho}\rho^{d-1}|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|d\rho
dP^{2}_{\mathcal{X}}(x,x^{\prime})$ $\displaystyle={}$
$\displaystyle\frac{2}{\Gamma(d)}\int_{0}^{\infty}e^{-\rho}\rho^{d-1}\int_{\mathcal{X}^{2}_{+}\cup\mathcal{X}^{2}_{-}}\mathbb{I}_{[0,\sigma(\rho/2)^{1/2})}(\widetilde{\Delta}(x,x^{\prime}))|\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})|dP^{2}_{\mathcal{X}}(x,x^{\prime})d\rho$
$\displaystyle\leq{}$
$\displaystyle\frac{2^{1+\beta/2}C_{**}\sigma^{\beta}}{\Gamma(d)}\int_{0}^{\infty}e^{-\rho}\rho^{d-1+\beta/2}d\rho$
$\displaystyle={}$
$\displaystyle\frac{2^{1+\beta/2}C_{**}\Gamma(d+\frac{\beta}{2})}{\Gamma(d)}\sigma^{\beta}.$

Combine with (5.5) (5.6) we conclude that $f_{0}\in\mathcal{H}_{K^{\sigma}}$,
$\|f_{0}\|_{\infty}\leq 1$ and

$\lambda\|f_{0}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi_{\mathrm{hinge}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{hinge}}}(f^{*}_{\mathrm{hinge}})\leq\frac{2^{2d+1}r^{2d}}{\Gamma(d)}\lambda\sigma^{-2d}+\frac{2^{1+\beta/2}C_{**}\Gamma(d+\frac{\beta}{2})}{\Gamma(d)}\sigma^{\beta}.$

The proof is then finished. ∎

Next, we establish the approximation error estimates for the square loss under
the standard Besov smoothness condition on the Bayes ranking rule

$f^{*}_{\mathrm{square}}(x,x^{\prime})=\frac{\eta_{+}(x,x^{\prime})-\eta_{-}(x,x^{\prime})}{\eta_{+}(x,x^{\prime})+\eta_{-}(x,x^{\prime})}.$

Due to the discussion in Remark 2, we can regard $f^{*}_{\mathrm{square}}$ as
a function in $\mathcal{L}_{2}(\mathbb{R}^{2d})$, or equivalently,
$f^{*}_{\mathrm{square}}$ is the restriction of a function in
$\mathcal{L}_{2}(\mathbb{R}^{2d})$ on $\mathcal{X}^{2}$.

######  Proposition 6.

Suppose that $f^{*}_{\mathrm{square}}\in\mathcal{L}_{2}(\mathbb{R}^{2d})$ and
$|f^{*}_{\mathrm{square}}|_{\mathcal{B}_{2,\infty}^{\alpha}(P^{2}_{\mathcal{X}})}<\infty$
for some $\alpha>0$. Then for all $\lambda>0,\sigma>0$, there exists an
$f_{0}\in\mathcal{H}_{K^{\sigma}}$ such that $\|f_{0}\|_{\infty}\leq 2^{s}$
and

$\displaystyle\lambda\|f_{0}\|^{2}_{K^{\sigma}}+\mathcal{R}^{\phi_{\mathrm{square}}}(f_{0})-\mathcal{R}^{\phi_{\mathrm{square}}}(f^{*}_{\mathrm{square}})$
$\displaystyle\leq{}$
$\displaystyle\frac{2^{2s}\|f^{*}_{\mathrm{square}}\|^{2}_{\mathcal{L}_{2}(\mathbb{R}^{2d})}}{\pi^{d}}\lambda\sigma^{-2d}+\frac{|f^{*}_{\mathrm{square}}|^{2}_{\mathcal{B}_{2,\infty}^{\alpha}(P^{2}_{\mathcal{X}})}}{2^{\alpha}}\left(\frac{\Gamma\left(d+\frac{\alpha}{2}\right)}{\Gamma(d)}\right)^{2}\sigma^{2\alpha}.$

###### Proof.

Define the $s$-fold application of the convolution operator
$\widetilde{\mathcal{K}}^{\sigma}$ as

$\widetilde{\mathcal{K}}^{\sigma}_{s}*\cdot:=\sum_{j=1}^{s}(-1)^{1-j}\binom{s}{j}(j\sigma\sqrt{\pi})^{-d}\widetilde{\mathcal{K}}^{j\sigma}*\cdot$

and we define the approximator $f_{0}\in\mathcal{H}_{K^{\sigma}}$ as

$\displaystyle
f_{0}(x,x^{\prime}):=\widetilde{\mathcal{K}}^{\sigma}_{s}*f^{*}_{\mathrm{square}}(x,x^{\prime})$
$\displaystyle={}$
$\displaystyle\int_{\mathbb{R}^{2d}}\sum_{j=1}^{s}(-1)^{1-j}\binom{s}{j}\left(\frac{2}{\pi
j^{2}\sigma^{2}}\right)^{d}\exp\left(-\frac{2\|(u,u^{\prime})\|^{2}_{2}}{(j\sigma)^{2}}\right)f^{*}_{\mathrm{square}}((x,x^{\prime})+(u,u^{\prime}))d(u,u^{\prime})$
$\displaystyle={}$