ABSTRACT

In this paper, we consider the regularized learning schemes based on l₁-regularizer and pinball loss in a data dependent hypothesis space. The target is the error analysis for the quantile regression learning. There is no regularized condition with the kernel function, excepting continuity and boundness. The graph-based semi-supervised algorithm leads to an extra error term called manifold error. Part of new error bounds and convergence rates are exactly derived with the techniques consisting of l₁-empirical covering number and boundness decomposition.

Keywords:

Semi-Supervised Learning, Conditional Quantile Regression, l₁-Regularizer, Manifold-Regularizer, Pinball Loss

1. Introduction

The classical least-squares regression models have focused mainly on estimating conditional mean functions. In contrast, quantile regression can provide richer information about the conditional distribution of response variables such as stretching or compressing tails, so it is particularly useful in applications when both lower and upper or all quantiles are of interest. Over the last years, quantile regression has become a popular statistical method in various research fields, such as reference charts in medicine [1] , survival analysis [2] and economics [3] .

In addition, relative to the least-squares regression, quantile regression estimates are more robust against outliers in the response measurements. We introduce a framework for data-dependent regularization that exploits the geometry of the marginal distribution. The labeled and unlabeled data learnt from the problem constructs a framework and incorporates the framework as an additional regularization term. The framework exploits the geometry of the probability distribution that generates the data. Hence, there are two regularization terms: one controlling the complexity of the classifier in the ambient space and the other controlling the complexity as measured by geometry of the distribution in the intrinsic space.

2. The Model

In this paper, under the framework of learning theory, we study l₁-regularized and manifold regularized quantile regression. Let $X$ be a compact subset of ${ℝ}^{l+u}$ and $Y\subset ℝ$ . There is a probability distribution $\rho$ on $X\times Y$ according to which examples are generated for function learning. Labeled examples are $\left(x\mathrm{,}y\right)$ pairs generated according to $\rho$ . Unlabeled examples are simply $x\in X$ drawn according to the marginal distribution ${\rho }_X$ of $\rho$ . We will make a specific assumption that an identifiable relation between ${\rho }_X$ and the conditional $\rho \left(y\mathrm{<mo>\; |\; </mo>}x\right)$ . The conditional t-quantile is a set-valued function defined by

$\rho \left(\left\{y\in \left(-\infty ,u\right]\right\}|x\right)\ge 1-\tau \text{and}\rho \left(\left\{y\in \left(u,\infty \right]\right\}|x\right)\ge \tau$ (2.1)

where $\tau \in \left(\mathrm{0,1}\right)$ , $x\in X$ and $u\in Y$ .

The empirical method for estimating the conditional t-quantile function is based on the t-pinball loss

${\rho }_{\tau }\left(r\right)=\{\begin{array}{l}\tau r,r>0\\ \left(\tau -1\right)r,\text{otherwise}\end{array}$ (2.2)

Then, denote the generalization error to minimize the conditional t-quantile function $f_{\rho }$ with the loss function ${\rho }_{\tau }$

${\epsilon }^{\tau }={\displaystyle {\int }_{X\times Y}}{\rho }_{\tau }\left(y-f\left(x\right)\right)\text{d}\rho$ (2.3)

where $f\mathrm{<mo>\; :\; </mo>}X\to ℝ$ . Based on observations, the empirical risk of the function $f$ is

${\epsilon }_z^{\tau }=\frac{1}{l}{\displaystyle \underset{i=1}{\overset{l}{\sum }}}{\rho }_{\tau }\left(y_i-f\left(x_i\right)\right)$ (2.4)

Next, We assume that $\left|f_{\rho }^{\tau }\right|\le 1,a.e.,x\in X$ with respect to ${\rho }_X$ .

In kernel-based learning, this minimization process usually takes place in a hypothesis space, Reproducing Kernel Hilbert Space (RKHS) [4] [5] ${\mathcal{H}}_k$ generated by a kernel function $K\mathrm{<mo>\; :\; </mo>}X\times X\to ℝ$ . In the empirical case, a graph-based regular quantile regression problem can be typically formulated in terms of the following optimization

${\hat{f}}_{z,\gamma }=\underset{f\in {\mathcal{H}}_K}{\min }\left\{{\displaystyle \underset{i=1}{\overset{l}{\sum }}}{\rho }_{\tau }\left(y_i-f\left(x_i\right)\right)+{\gamma }_A{\Vert f\Vert }_K+{\gamma }_I{\Vert f\Vert }_I\right\}.$ (2.5)

By the representers theorem, the solution to (2.5) can be written as

${\hat{f}}_{z,\gamma }\left(x\right)={\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\alpha }_{i}K\left(x,x_i\right)$ (2.6)

The l₁-norm penalty not only shrinks the fitted coefficients toward zero but also causes some of the coefficients to be exactly zero when making ${\gamma }_A$ sufficiently large. When the data lies on a low-dimensional manifold, the graph- based method seems more effective for semi-supervised learning and many approaches have been proposed for instance Transductive SVM [6] , Measure- based Regularization [7] and so on. Then the l₁-regularized and manifold regularized quantile regression are as following

$\begin{array}{c}{\hat{f}}_{z,\gamma }\left(x\right)=\underset{f\in {\mathcal{H}}_K}{\min }\left\{{\epsilon }_z^{\tau }\left(f\right)+{\gamma }_A\Omega \left(f\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{\displaystyle \underset{i,j=1}{\overset{l+u}{\sum }}}{\left(f\left(x_i\right)-f\left(x_j\right)\right)}^2{\omega }_{ij}\right\}\\ =\underset{f\in {\mathcal{H}}_K}{\min }\left\{{\epsilon }_z^{\tau }\left(f\right)+{\gamma }_A\Omega \left(f\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}^{\text{T}}Lf\right\}\end{array}$ (2.7)

where $\Omega \left(f\right)={\displaystyle {\sum }_{i=1}^{l+u}}\left|{\alpha }_i\right|$ , $f={\left(f\left(x_1\right)\mathrm{,}\cdots \mathrm{,}f\left(x_{l+u}\right)\right)}^{\text{T}}$ . ${\gamma }_A\mathrm{,}{\gamma }_I$ are nonnegative regularization parameters. $L=D-W$ is the unnormalized graph Laplacian, where $D$ is a diagonal matrix with diagonal entries $D_{ii}={\displaystyle {\sum }_{j=1}^{l+u}}{\omega }_{ij}$ . The weight ${\omega }_{ij}$ is given by a similar function $\omega \left(x_i\mathrm{,}{x}_j\right)$ . The more similar $x_i$ and $x_j$ , the larger ${\omega }_{ij}$ should be.

3. The Restriction

Definition 3.1. The projection operator on the space of function is defined by

$\pi \left(f\right)\left(x\right)=\{\begin{array}{l}1,\text{if}f\left(x\right)>1\hfill \\ f\left(x\right),\text{if}-1\le f\left(x\right)\le 1\hfill \\ -1,\text{if}f\left(x\right)<1\hfill \end{array}$ (3.1)

Hence, it is natural to measure the approximation ability by the distance ${\Vert \pi \left({\hat{f}}_{z\mathrm{,}\gamma }\right)-f_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^{p^{\ast }}}$ with $f_{\rho }^{\tau }\le 1$ .

Definition 3.2. Let $p\in \left(\mathrm{0,}\infty \right]$ and $q\in \left(\mathrm{1,}\infty \right)$ . We say that $\rho$ has a t-quantile of p-average type $q$ if for almost all $x\in X$ with respect to ${\rho }_X$ , there exist a $\tau$ quantile $t\in ℝ$ and constants $a_x\in \left(\mathrm{0,2}\right]$ , $b_x>0$ such that for each $s\in \left[\mathrm{0,}{a}_x\right]$ ,

$\rho \left(y\in \left(t-s\mathrm{,}t\right)\mathrm{<mo>\; |\; </mo>}x\right)\ge b_x{s}^{q-1}\mathrm{,}$ (3.2)

$\rho \left(y\in \left(t-s\mathrm{,}t\right)\mathrm{<mo>\; |\; </mo>}x\right)\ge b_x{s}^{q-1}\mathrm{,}$ (3.3)

and that the function $\varphi \mathrm{<mo>\; :\; </mo>}X\to \left[\mathrm{0,}\infty \right]$ , $\varphi \left(x\right)=b_x{a}_x^{q-1}$ satisfies ${\varphi }_{-1}\in L_{{\rho }_X}^p$ .

For $p\in \left(\mathrm{0,}\infty \right]$ and $q\in \left(\mathrm{1,}\infty \right)$ , denote

$\theta =\min \left\{\frac{2}{q},\frac{p}{p+1}\right\}\in \left(0,1\right]$ (3.4)

Lemma 3.1. If $\rho$ has a t-quantile of p-average type $q$ for some $p\in \left(\mathrm{0,}\infty \right]$ and $q\in \left(\mathrm{1,}\infty \right)$ , then for any measurable function $f\mathrm{<mo>\; :\; </mo>}X\to \left[-\mathrm{1,1}\right]$ , there holds

${\Vert f-f_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^{p^{\ast }}}\le C_{q\mathrm{,}\rho }{\left\{{\epsilon }^{\tau }\left(f\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}}^{\frac{1}{q}}$ (3.5)

where $C_{q\mathrm{,}\rho }=2^{1-\frac{1}{q}}{q}^{\frac{1}{q}}{\Vert {\left[{\left(b_x{a}_x^{q-1}\right)}^{-1}\right]}_{x\in X}\Vert }_{L_{{\rho }_X}^p}^{\frac{1}{q}}$ and $p_{\ast }=\frac{pq}{p+1}$

Definition 3.3. We say that the kernel function $K$ is a $C^c$ kernel with $c>0$ if there exists some constants $C^c>0$ , such that

$\left|K\left(t,x\right)-K\left(t,x^{\prime }\right)\right|\le C^c{\left|x-x^{\prime }\right|}^c,\forall t,x,x^{\prime }\in X$ (3.6)

We assume throughout the paper that $K\in C^c\left(X\times X\right)$ and denote $\kappa ={\sup }_{t,x\in X}\left|K\left(x,t\right)\right|<\infty$ . Our approximation condition is given as

$f_{\rho }^{\tau }=L_{\tilde{K}}^s{g}_{\rho }^{\tau },\text{for}\text{some}0<s<1,g_{\rho }^{\tau }\in L_{{\rho }_X}^2\left(X\right)$ (3.7)

here, the kernel $\tilde{K}$ is defined by

$\tilde{K}\left(x\mathrm{,}y\right)={\displaystyle {\int }_X}K\left(x\mathrm{,}t\right)K\left(y\mathrm{,}t\right)\text{d}{\rho }_X\left(t\right)$ (3.8)

Hence, although kernel $K$ in not positive semi-definite, $\tilde{K}$ is a Mercer kernel, ${\mathcal{H}}_{\tilde{K}}$ denotes the associated reproducing kernel Hilbert spaces. The kernel $\tilde{K}$ defines an integral operator $L_{\tilde{K}}\mathrm{<mo>\; :\; </mo>}{L}_{{\rho }_X}^2\to L_{{\rho }_X}^2$ by

$L_{\tilde{K}}f\left(x\right)={\displaystyle {\int }_X}\tilde{K}\left(x\mathrm{,}{x}^{\prime }\right)f\left(x^{\prime }\right)\text{d}{\rho }_X\left(x^{\prime }\right)\mathrm{,}x\in X\mathrm{.}$ (3.9)

Note that $L_{\tilde{K}}=L_K{L}_K^{\ast }$ is a self-adjoint positive operator on $L_{{\rho }_X}^2$ .Hence its s-th power $L_{\tilde{K}}^s$ is well defined for any $s>0$ . we take the RKHS ${\mathcal{H}}_{\hat{K}}$ with

$\hat{K}\left(X,Y\right)={\displaystyle {\int }_X}\tilde{K}\left(x,t\right)\tilde{K}\left(y,t\right)\text{d}{\rho }_X\left(t\right)$ (3.10)

It is easy to see $L_{\hat{K}}=L_{\tilde{K}}^2$ , so that any function $f\in {\mathcal{H}}_{\hat{K}}$ can be expressed as $L_{\tilde{K}}g$ for some $g\in L_{{\rho }_X}^2$ .

Definition 3.4. Define a Banach space ${\mathcal{H}}_1=\left\{f:f={\displaystyle {\sum }_{j=1}^{\infty }}{\alpha }_j\hat{K}\left(x,x_j\right),\left\{{\alpha }_j\right\}\in l_1,\left\{x_j\right\}\subset X\right\}$ with the norm

$\Vert f\Vert =\inf \left\{f={\displaystyle \underset{j=1}{\overset{\infty }{\sum }}}\left|{\alpha }_j\right|:f={\displaystyle \underset{j=1}{\overset{\infty }{\sum }}}{\alpha }_j\hat{K}(x,x_j),\left\{{\alpha }_j\right\}\in l_1,\left\{x_j\right\}\subset X\right\}$ (3.11)

Definition 3.5. For every $\eta >0$ , the l₂-empirical covering number of $\mathcal{F}$ is

$\begin{array}{l}{\mathcal{N}}_2\left(\mathcal{F}\mathrm{,}\eta \right)=\underset{k\in \mathbb{N}}{\min }\underset{\text{x}\in X^k}{\min }\inf \{l\in \mathbb{N}\mathrm{<mo>\; :\; </mo>}\exists {\left\{f_i\right\}}_{i=1}^l\text{such}\text{that}\text{for}\text{all}\\ f\in \mathcal{F}\mathrm{,}\text{there}\text{is}\underset{1\le i\le l}{\min }{d}_{\mathrm{2,}\text{x}}\left(f\mathrm{,}{f}_i\right)\le \eta \}\end{array}$ (3.12)

Lemma 3.2. There exist an exponent $\mu \in \left(\mathrm{0,2}\right)$ and a constant $c_{\mu \mathrm{,}K}$ such that

$log{\mathcal{N}}_2\left(B_r\mathrm{,}\eta \right)\le c_{\mu \mathrm{,}K}{\eta }^{-\mu }\mathrm{,}\forall \eta >0$ (3.13)

suppose that $K\in C^c\left(X\times X\right)$

$\mu =\{\begin{array}{l}2n/\left(n+2c\right),\text{when}0<c<1\hfill \\ 2n/\left(n+2\right),\text{when}0<c<1\hfill \\ n/c,\text{when}c>1+n/2\hfill \end{array}$ (3.14)

Define an operator $L_{\omega }$ on $L_{{\rho }_X}^2$ as

$L_{\omega }f\left(x\right)=f\left(x\right)p\left(x\right)-{\displaystyle {\int }_X}K\left(x\mathrm{,}{x}^{\prime }\right)f\left(x^{\prime }\right)\text{d}{\rho }_X\left(x^{\prime }\right)$ (3.15)

with $p\left(x\right)={\displaystyle {\int }_X}K\left(x\mathrm{,}{x}^{\prime }\right)\text{d}\rho \left(x^{\prime }\right)$ . The above equation tells us that

${\langle f\mathrm{,}{L}_{\omega }f\rangle }_2={\displaystyle \iint }{\left(f\left(x\right)-f\left(x^{\prime }\right)\right)}^2\text{d}{\rho }_X\left(x\right)\text{d}{\rho }_X\left(x^{\prime }\right)$ (3.16)

Next, The performance of ${\mathcal{H}}_{\hat{K}}$ approaching $f_{\rho }^{\tau }$ can be described through the regularizing function $f_{\gamma }$ defined as

$f_{\gamma }=\arg \underset{f\in {\mathcal{H}}_{\hat{K}}}{\min }\left\{{\epsilon }^{\tau }\left(f\right)-\epsilon \left(f_{\rho }^{\tau }\right)+{\gamma }_A{\Vert f\Vert }_{\hat{K}}+{\gamma }_I\langle f,L_{\omega }f\rangle \right\}$ (3.17)

the above function $f_{\gamma }$ given by (3.13 ) can be expressed as

$f_{\gamma }=L_{\tilde{K}}{h}_{\gamma }=L_K{g}_{\gamma }$ (3.18)

where $g_{\gamma }=L_K^{\ast }{h}_{\gamma }$ . Moreover, $g_{\gamma }$ is a continuous function on $X$ and

${\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}={\Vert f_{\gamma }\Vert }_{\tilde{K}},{\Vert f_{\gamma }\Vert }_{\tilde{K}}\le \kappa {\Vert f_{\gamma }\Vert }_{\hat{K}}=\kappa {\Vert h_{\gamma }\Vert }_{L_{{\rho }_X}^2}.$ (3.19)

Definition 3.6. Let $\mathcal{F}$ be a set of function on $X$ , $\text{x=}{\left(x_i\right)}_{i=1}^k\in X^k$ . The $l_2$ metric between function on $X$ is

$d_{\mathrm{2,}\text{x}}\left(f\mathrm{,}g\right)={\left\{\frac{1}{k}{\displaystyle \underset{i=1}{\overset{k}{\sum }}}{\left(f\left(x_i\right)-g\left(x_i\right)\right)}^2\right\}}^{\frac{1}{2}}\mathrm{,}\forall f\mathrm{,}g\in \mathcal{F}$ (3.20)

Denote the ball of radius $r\ge 1$ as $B_r=\left\{f\in {\mathcal{H}}_{\hat{K}}\mathrm{<mo>\; :\; </mo>}{\Vert f\Vert }_{\hat{K}}\le r\right\}$ .

4. Error Analysis

4.1. Error Decomposition

Proposition 4.1. Let $\gamma =\left({\gamma }_A,{\gamma }_I\right),{\gamma }_A>0,{\gamma }_I>0$ and $f_{z,\gamma }={\displaystyle {\sum }_{i=1}^{l+u}}{\alpha }_{i}K\left(x,x_i\right)$ given by (2.6). Then

$\begin{array}{l}{\epsilon }^{\tau }\left(\pi \left(f_{z\mathrm{,}\gamma }\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A\Omega \left(f_{z\mathrm{,}\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{z\mathrm{,}\gamma }^{\text{T}}L{f}_{z\mathrm{,}\gamma }\\ \le {\mathcal{S}}_1\left(z\mathrm{,}\gamma \right)+{\mathcal{S}}_2\left(z\mathrm{,}\gamma \right)+{\mathcal{H}}_1\left(z\mathrm{,}\gamma \right)+{\mathcal{H}}_2\left(z\mathrm{,}\gamma \right)+\left(1+\kappa \right)\mathcal{D}\left(\gamma \right)\end{array}$ (4.1.1)

where

${\mathcal{S}}_1\left(z\mathrm{,}\gamma \right)=\left\{{\epsilon }^{\tau }\left(\pi \left(f_{z\mathrm{,}\gamma }\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}-\left\{{\epsilon }_z^{\tau }\left(\pi \left(f_{z\mathrm{,}\gamma }\right)\right)-{\epsilon }_z^{\tau }\left(f_{\rho }^{\tau }\right)\right\}$ (4.1.2)

${\mathcal{S}}_2\left(z\mathrm{,}\gamma \right)=\left\{{\epsilon }_z^{\tau }\left({\hat{f}}_{z\mathrm{,}\gamma }\right)-{\epsilon }_z^{\tau }\left(f_{\rho }^{\tau }\right)\right\}-\left\{{\epsilon }^{\tau }\left({\hat{f}}_{z\mathrm{,}\gamma }\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}$ (4.1.3)

${\mathcal{H}}_1\left(z\mathrm{,}\gamma \right)={\gamma }_A\Omega \left({\hat{f}}_{z\mathrm{,}\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{\hat{f}}_{z\mathrm{,}\gamma }^{\text{T}}L{\hat{f}}_{z\mathrm{,}\gamma }-{\gamma }_A{\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}-\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{\gamma }^{\text{T}}L{f}_{\gamma }$ (4.1.4)

${\mathcal{H}}_2\left(z\mathrm{,}\gamma \right)={\epsilon }^{\tau }\left({\hat{f}}_{z\mathrm{,}\gamma }\right)-{\epsilon }^{\tau }\left(f_{\gamma }\right)$ (4.1.5)

$\mathcal{D}\left(\gamma \right)={\epsilon }^{\tau }\left(f_{\gamma }\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A{\Vert f_{\gamma }\Vert }_K+{\gamma }_I{\langle f_{\gamma }\mathrm{,}{L}_{\omega }{f}_{\gamma }\rangle }_2$ (4.1.6)

$\mathcal{M}\left(z\mathrm{,}\gamma \right)=\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{\gamma }^{\text{T}}L{f}_{\gamma }-{\gamma }_I{\langle f_{\gamma }\mathrm{,}{L}_{\omega }{f}_{\gamma }\rangle }_2$ (4.1.7)

Proof. A direct decomposition shows that

$\begin{array}{l}{\epsilon }^{\tau }\left(\pi \left(f_{z,\gamma }\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A\Omega \left(f_{z,\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{z,\gamma }^{\text{T}}L{f}_{z,\gamma }\\ =\left\{{\epsilon }^{\tau }\left(\pi \left(f_{z,\gamma }\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}-\left\{{\epsilon }_z^{\tau }\left(\pi \left(f_{z,\gamma }\right)\right)-{\epsilon }_z^{\tau }\left(f_{\rho }^{\tau }\right)\right\}\\ +\left\{{\epsilon }^{\tau }\left(\pi \left(f_{z,\gamma }\right)\right)+{\gamma }_A\Omega \left(f_{z,\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{z,\gamma }^{\text{T}}L{f}_{z,\gamma }\right\}\\ -\left\{{\epsilon }_z^{\tau }\left({\hat{f}}_{z,\gamma }\right)+{\gamma }_A\Omega \left({\hat{f}}_{z,\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{\hat{f}}_{z,\gamma }^{\text{T}}L{\hat{f}}_{z,\gamma }\right\}\\ +\left\{{\epsilon }_z^{\tau }\left({\hat{f}}_{z,\gamma }\right)-{\epsilon }_z^{\tau }\left(f_{\rho }^{\tau }\right)\right\}-\left\{{\epsilon }^{\tau }\left({\hat{f}}_{z,\gamma }\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}+{\epsilon }^{\tau }\left({\hat{f}}_{z,\gamma }\right)\\ -{\epsilon }^{\tau }\left(f_{\gamma }\right)+{\epsilon }^{\tau }\left(f_{\gamma }\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A{\Vert f_{\gamma }\Vert }_K+{\gamma }_I{\langle f_{\gamma },L_{\omega }{f}_{\gamma }\rangle }_2\\ +{\gamma }_A\Omega \left({\hat{f}}_{z,\gamma }\right)+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{\hat{f}}_{z,\gamma }^{\text{T}}L{\hat{f}}_{z,\gamma }-{\gamma }_A{\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}-\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{\gamma }^{\text{T}}L{f}_{\gamma }\\ +{\gamma }_A{\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}-{\gamma }_A{\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}+\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{\gamma }^{\text{T}}L{f}_{\gamma }-{\gamma }_I{\langle f_{\gamma },L_{\omega }{f}_{\gamma }\rangle }_2\end{array}$ (4.1.8)

The fact $\left|y\right|<1$ implies that ${\epsilon }_z^{\tau }\left(\pi \left(f_{z\mathrm{,}\gamma }\right)\right)\le {\epsilon }_z^{\tau }\left(f_{z\mathrm{,}\gamma }\right)$ . Hence, the second item in the right-hand side of the above equation is at most 0 by the reason that ${\hat{f}}_{z\mathrm{,}\gamma }\in {\mathcal{H}}_K$ is the minimizer of (2.7). Duo to ${\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}\le {\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}$ , we see that the last but one item is at most 0. The fifth item is less than by the $\left(1+\kappa \right)\mathcal{D}\left(\gamma \right)$ fact that ${\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}={\Vert f_{\gamma }\Vert }_{\tilde{K}}\le \kappa {\Vert f_{\gamma }\Vert }_K$ . Thus we complete the proof.,

4.2. Estimation of the Regularization Error

Proposition 4.2. Assume (3.7) holds, denoting ${\gamma }_I={\gamma }_A^{2-s}$ for some $0<s\le 1$ then we have

$\mathcal{D}\left(\gamma \right)\le C_0{\gamma }_A^s$ (4.2.1)

where $C_0=2{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}+6\omega {\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}^2$ .

Proof. Denote $f_{{\gamma }_A}=\arg {\min }_{f\in {\mathcal{H}}_K}\left\{{\epsilon }^{\tau }\left(f\right)+{\gamma }_A{\Vert f\Vert }_K\right\}$ . By proposition 2 in [8] , we get the following relationships ${\epsilon }^{\tau }\left(f_{{\gamma }_A}\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A{\Vert f_{{\gamma }_A}\Vert }_K\le 2{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}{\gamma }_A^s$ and ${\Vert f_{{\gamma }_A}\Vert }_K\le {\gamma }_A^{s-1}{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}$ . Connected with the definition of $\mathcal{D}\left(\gamma \right)$ , we have

$\begin{array}{c}\mathcal{D}\left(\gamma \right)\le {\epsilon }^{\tau }\left(f_{{\gamma }_A}\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)+{\gamma }_A{\Vert f_{\gamma }\Vert }_K+{\gamma }_I{\langle f_{\gamma },L_{\omega }{f}_{\gamma }\rangle }_2\\ \le 2{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}{\gamma }_A^s+{\gamma }_I{\displaystyle \iint }{\left(f_{{\gamma }_A}\left(x\right)-f_{{\gamma }_A}\left(x^{\prime }\right)\right)}^2\omega \left(x,x^{\prime }\right)\text{d}{\rho }_X\left(x\right)\text{d}{\rho }_X\left(x^{\prime }\right)\\ \le 2{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}{\gamma }_A^s+{\gamma }_A^{2-s}{\displaystyle \iint }2{\Vert f_{{\gamma }_A}\Vert }_K^2\omega \text{d}{\rho }_X\left(x\right)\text{d}{\rho }_X\left(x^{\prime }\right)\\ \le 2{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}{\gamma }_A^s+6\omega {\gamma }_A^{2\left(s-1\right)}{\Vert g_{\rho }^{\tau }\Vert }_{L_{{\rho }_X}^2}\end{array}$

where ${\gamma }_I={\gamma }_A^{2-s}$ . we derive the desired bound.,

4.3. Estimation of the Manifold Error

In this subsection, we estimation the manifold error. Denote

$A_{z,\gamma }=\frac{{\gamma }_I}{l+u}{\displaystyle \underset{j=1}{\overset{l+u}{\sum }}}\left(\left(\frac{1}{l+u}{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\xi }_1\left(x_i\right)\right)\left(x_j\right)-\left(E{\xi }_1\right)\left(x_j\right)\right)$ (4.3.1)

$B_{z,\gamma }={\gamma }_I{\displaystyle \int }{f}_{\gamma }^2\left(x\right)\left(\left(\frac{1}{l+u}{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\xi }_2\left(x_j\right)\right)\left(x\right)-\left(E{\xi }_2\right)\left(x\right)\right)\text{d}{\rho }_X\left(x\right)$ (4.3.2)

$C_{z,\gamma }=\frac{{\gamma }_I}{l+u}{\displaystyle \underset{j=1}{\overset{l+u}{\sum }}}{f}_{\gamma }\left(x_j\right)\left(\left(E{\xi }_3\right)\left(x_j\right)-\left(\frac{1}{l+u}{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\xi }_3\left(x_i\right)\left(x_j\right)\right)\right)$ (4.3.3)

$D_{z,\gamma }={\gamma }_I{\displaystyle \int }{f}_{\gamma }\left(x\right)\left(\left(E{\xi }_3\right)\left(x\right)\left(\frac{1}{l+u}{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\xi }_3\left(x_j\right)\right)\left(x\right)\right)\text{d}{\rho }_X\left(x\right)$ (4.3.4)

where ${\xi }_1\left(x\right)=f_{\gamma }^2\left(x\right)\omega \left(x,\cdot \right)$ , ${\xi }_2\left(x\right)=\omega \left(\cdot ,x\right)$ , ${\xi }_3\left(x\right)=f_{\gamma }\left(x\right)\omega \left(\cdot ,x\right)$ . So we can see that $\mathcal{M}\left(z\mathrm{,}\gamma \right)=2\left(A_{z\mathrm{,}\gamma }+B_{z\mathrm{,}\gamma }+C_{z\mathrm{,}\gamma }+D_{z\mathrm{,}\gamma }\right)$

Lemma 4.1. Let $\xi$ be a random variable on a probability space $X$ with ${\sigma }^2=E{\Vert \xi \Vert }^2$ satisfying $\Vert \xi \Vert \le M_{\xi }$ for some constant $M_{\xi }$ . Then for any $0<\delta <1$ , we have

$\frac{1}{l}{\displaystyle \underset{i=1}{\overset{l}{\sum }}}\xi \left(z_i\right)-E\xi \le \frac{2M_{\xi }\log \left(1/\delta \right)}{l}+\sqrt{\frac{2{\sigma }^2\log \left(1/\delta \right)}{l}}$ (4.3.5)

Proposition 4.3. under the approximation condition (3.13), let $0<{\gamma }_A\le 1$ and ${\gamma }_I={\gamma }_A^{2-s}$ for some $0<s\le 1$ . then for any $0<\delta <1$ with the confidence $1-\delta$ , there holds

$\mathcal{M}\left(z,\gamma \right)\le 4\omega {\kappa }^4{C}_0^2\sqrt{2\log \left(4/\delta \right)}{\gamma }_A^s{\left(l+u\right)}^{-1/2}$ (4.3.6)

Proof. By the definition of ${\xi }_1\left(x\right)$ , we have $\left|{\xi }_1\left(x\right)\right|\le \omega {\left|f\right|}_{\gamma }^2=\omega {\left|L_K{g}_{\gamma }\right|}^2\le \kappa {\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}^2$ . Since ${\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^2}^2\le \kappa {\Vert f_{\gamma }\Vert }_{\hat{K}}\le \kappa C_0{\gamma }_A^{s-1}$ , there holds $\left|{\xi }_1\left(x\right)\right|\le {\kappa }^4{C}_0^2{\gamma }_A^{2\left(s-1\right)}$ , $\left|{\xi }_2\left(x\right)\right|\le \omega$ , $\left|{\xi }_3\left(x\right)\right|\le \omega {\kappa }^2{C}_0{\gamma }_A^{s-1}$ . Applying lemma 4.1, with confidence $1-4/\delta$ ,

$A_{z\mathrm{,}\gamma }\le {\gamma }_I\omega {\kappa }^4{C}_0^2{\gamma }_A^{2\left(s-1\right)}\left(\frac{2log\left(2/\delta \right)}{l+u}+\sqrt{\frac{2log\left(2/\delta \right)}{l+u}}\right)$ (4.3.7)

$B_{z\mathrm{,}\gamma }\le {\gamma }_I\omega {\kappa }^4{C}_0^2{\gamma }_A^{2\left(s-1\right)}\left(\frac{2log\left(2/\delta \right)}{l+u}+\sqrt{\frac{2log\left(2/\delta \right)}{l+u}}\right)$ (4.3.8)

$C_{z\mathrm{,}\gamma }\le {\gamma }_I\omega {\kappa }^4{C}_0^2{\gamma }_A^{2\left(s-1\right)}\left(-\frac{2log\left(2/\delta \right)}{l+u}+\sqrt{\frac{2log\left(2/\delta \right)}{l+u}}\right)$ (4.3.9)

$D_{z\mathrm{,}\gamma }\le {\gamma }_I\omega {\kappa }^4{C}_0^2{\gamma }_A^{2\left(s-1\right)}\left(-\frac{2log\left(2/\delta \right)}{l+u}+\sqrt{\frac{2log\left(2/\delta \right)}{l+u}}\right)$ (4.3.10)

Then we find the manifold error bound holds true.,

4.4. Estimation of the Hypothesis Error

This subsection is devoted to estimate the hypothesis errors. Under the assumption that the sample is i.i.d. drawn from $\rho$ and $\left|y\right|\le 1$ a.e., we estimate ${\mathcal{H}}_1\mathrm{,}{\mathcal{H}}_2$ as following.

Proposition 4.4. For any $0<\delta <1$ ,with confidence $1-\delta$ , we have

${\mathcal{H}}_1\le \kappa \frac{\mathcal{D}\left(\gamma \right)}{\sqrt{l+u}}\left\{\frac{2\log \left(4/\delta \right)}{\sqrt{l+u}}+\sqrt{2\log \left(4/\delta \right)}\right\}+8{\kappa }^4\sqrt{2\log \left(4/\delta \right)}\frac{\mathcal{D}{\left(\gamma \right)}^2}{{\gamma }_A^s\sqrt{l+u}}$ (4.4.1)

${\mathcal{H}}_2\le {\kappa }^2\frac{\mathcal{D}\left(\gamma \right)}{{\gamma }_A\sqrt{l+u}}\left\{\frac{2\log \left(4/\delta \right)}{\sqrt{l+u}}+\sqrt{2\log \left(4/\delta \right)}\right\}$ (4.4.2)

Proof. We estimate ${\mathcal{H}}_1$ . Recall ${\hat{f}}_{z,\gamma }=\frac{1}{l+u}{\displaystyle {\sum }_{i=1}^{l+u}}{g}_{\gamma }\left(x_i\right)K_{x_i}$ , then $\Omega \left({\hat{f}}_{z,\gamma }\right)=\frac{1}{l+u}{\displaystyle {\sum }_{i=1}^{l+u}}\left|g_{\gamma }\left(x_i\right)\right|$ .

Applying Lemma 4.1 to the random variable $\xi =\left|g_{\gamma }\left(x\right)\right|$ on $\left(X\mathrm{,}{\rho }_X\right)$ with value in $ℝ$ . There is

$\xi =\left|g_{\gamma }\left(x\right)\right|\le \kappa \mathcal{D}\left(\gamma \right)/{\gamma }_A$ (4.4.3)

$E\xi ={\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}\text{and}{\sigma }^2\left(\xi \right)\le {\kappa }^2\mathcal{D}{\left(\gamma \right)}^2/{\gamma }_A^2$ (4.4.4)

with confidence $1-\delta /2$ , there holds

$\Omega \left({\hat{f}}_{z\mathrm{,}\gamma }\right)-{\Vert g_{\gamma }\Vert }_{L_{{\rho }_X}^1}\le \frac{2\kappa \mathcal{D}\left(\gamma \right)log\left(4/\delta \right)}{{\gamma }_A\left(l+u\right)}+\sqrt{\frac{2{\kappa }^2\mathcal{D}{\left(\gamma \right)}^{2}log\left(4/\delta \right)}{{\gamma }_A^2\left(l+u\right)}}$ (4.4.5)

since

$\begin{array}{l}{\left(f_{z,\gamma }\left(x_i\right)-f_{z,\gamma }{\left(x_j\right)}^2\right)}^2-{\left(f_{\gamma }\left(x_i\right)-f_{\gamma }\left(x_j\right)\right)}^2\\ =[\frac{1}{l+u}{\displaystyle \underset{t=1}{\overset{l+u}{\sum }}}\left(g_{\gamma }\left(x_t\right)K\left(x_i,x_t\right)-g_{\gamma }\left(x_t\right)K\left(x_j,x_t\right)\right)\\ -{\displaystyle {\int }_X}\left(g_{\gamma }\left(x^{\prime }\right)K\left(x_i,x^{\prime }\right)-g_{\gamma }\left(x^{\prime }\right)K\left(x_j,x^{\prime }\right)\right)\text{d}{\rho }_X\left(x^{\prime }\right)]\\ \times [\frac{1}{l+u}{\displaystyle \underset{t=1}{\overset{l+u}{\sum }}}\left(g_{\gamma }\left(x_t\right)K\left(x_i,x_t\right)-g_{\gamma }\left(x_t\right)K\left(x_j,x_t\right)\right)\\ +{\displaystyle {\int }_X}\left(g_{\gamma }\left(x^{\prime }\right)K\left(x_i,x^{\prime }\right)-g_{\gamma }\left(x^{\prime }\right)K\left(x_j,x^{\prime }\right)\right)\text{d}{\rho }_X\left(x^{\prime }\right)]\\ \le 2{\kappa }^2\frac{\mathcal{D}\left(\gamma \right)}{{\gamma }_A}\sqrt{\frac{2\log \left(2/\delta \right)}{l+u}}\cdot 4{\kappa }^2\frac{\mathcal{D}\left(\gamma \right)}{{\gamma }_A}\\ \le 8{\kappa }^2\sqrt{2\log \left(2/\delta \right)}\frac{\mathcal{D}{\left(\gamma \right)}^2}{{\gamma }_A^2}{\left(l+u\right)}^{-1/2}\end{array}$ (4.4.6)

Then the bound of the following is derived with ${\gamma }_I={\gamma }_A^{2-s}$

$\begin{array}{l}\frac{{\gamma }_I}{{\left(l+u\right)}^2}{\hat{f}}_{z\mathrm{,}\gamma }^{\text{T}}L{\hat{f}}_{z\mathrm{,}\gamma }-\frac{{\gamma }_I}{{\left(l+u\right)}^2}{f}_{\gamma }^{\text{T}}L{f}_{\gamma }\\ \le 8{\kappa }^2\sqrt{2log\left(4/\delta \right)}\mathcal{D}{\left(\gamma \right)}^2{\gamma }_A^{-s}{\left(l+u\right)}^{-1/2}\end{array}$ (4.4.7)

Finally, we have

${\mathcal{H}}_1\le \kappa \frac{\mathcal{D}\left(\gamma \right)}{\sqrt{l+u}}\left\{\frac{2log\left(4/\delta \right)}{\sqrt{l+u}}+\sqrt{2log\left(4/\delta \right)}\right\}+8{\kappa }^4\sqrt{2log\left(4/\delta \right)}\frac{\mathcal{D}{\left(\gamma \right)}^2}{{\gamma }_A^s\sqrt{l+u}}$ (4.4.8)

The ${\mathcal{H}}_2$ has been proved in [8] .,

4.5. Estimation of the Sample Error

Since ${\hat{f}}_{z\mathrm{,}\gamma }$ is a function valued random variable which depends on the sample error in the data independent space ${\mathcal{H}}_{\infty }$ which contains all possible hypothesis spaces ${\mathcal{H}}_{K\mathrm{,}z}$ . Our estimations for ${\mathcal{H}}_1\mathrm{,}{\mathcal{H}}_2$ are based on the following concentration inequality see [8] .

Lemma 4.2. Let $\mathcal{F}$ be a class of measurable function on $Z$ . Assume that there are constants $B,c>0$ and $\beta \in \left[\mathrm{0,1}\right]$ such that ${\Vert f\Vert }_{\infty }\le B$ and $E{f}^2\le c{\left(Ef\right)}^{\beta }$ for every $f\in \mathcal{F}$ . If for some $a>0$ and $\mu \in \left(\mathrm{0,2}\right)$ ,

$log{\mathcal{N}}_2\left(\mathcal{F}\mathrm{,}\zeta \right)\le a{\zeta }^{-\mu }\mathrm{,}\forall \zeta >0$ (4.5.1)

then there exists a constant $c_{\mu }$ depending only on $\mu$ such that for any $0<\delta <1$ , with confidence $1-\delta$ , there holds

$\begin{array}{l}Ef-\frac{1}{l}{\displaystyle \underset{i\mathrm{<mo>\; =\; </mo>1}}{\overset{l}{\sum }}}f\left(z_i\right)\le \frac{1}{2}{w}^{1-\beta }{\left(Ef\right)}^{\beta }+c_{\mu }w+2{\left(\frac{clog\left(1/\delta \right)}{l}\right)}^{1/\left(2-\beta \right)}\\ +\frac{18Blog\left(1/\delta \right)}{l}\mathrm{,}\forall f\in \mathcal{F}\end{array}$ (4.5.2)

where $w=\max \left\{c^{\frac{2-\mu }{4-2\beta }}{\left(\frac{a}{l}\right)}^{\frac{2}{4-2\beta +\mu \beta }},B^{\frac{2-\mu }{2+\mu }}{\left(\frac{a}{l}\right)}^{\frac{2}{2+\mu }}\right\}$ .The same bound also holds true for $\frac{1}{l}{\displaystyle {\sum }_{i=1}^l}f\left(z_i\right)-Ef$ .

The following proposition which has been proved in [9] will be utilized to bound ${\mathcal{S}}_1$ .

Proposition 4.5. suppose that $\rho$ has a t-quantile of p-average type $q$ for some $p\in \left(\mathrm{0,}\infty \right]$ , $q\in \left(\mathrm{1,}\infty \right)$ . Let $r\le 1$ and $0<{\gamma }_A\le 1$ . Assume $B_1$ satisfies the capacity assumption (3.12) with some $0<\mu <2$ . Then, for any $0<\delta <1$ , with confidence $1-\delta$ , there holds, for all $f\in B_r$ ,

$\begin{array}{l}\left\{{\epsilon }^{\tau }\left(\pi \left(f\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}-\left\{{\epsilon }_z^{\tau }\left(\pi \left(f\right)\right)-{\epsilon }_z^{\tau }\left(f_{\rho }^{\tau }\right)\right\}\\ \le \frac{1}{2}{C}_1^{1-\theta }{r}^{\frac{2\mu \left(1-\theta \right)}{2+\mu }}{l}^{\frac{2\left(1-\theta \right)}{4-2\theta +\mu \theta }}{\left\{{\epsilon }^{\tau }\left(\pi \left(f\right)\right)-{\epsilon }^{\tau }\left(f_{\rho }^{\tau }\right)\right\}}^{\theta }\\ +\left(36+2C_{\theta }^{\frac{1}{2-\theta }}\right)log\left(1/\delta \right)l^{\frac{-1}{2-\theta }}+C_2{r}^{\frac{2\mu }{2+\mu }}{l}^{\frac{2}{4-2\theta +\mu \theta }}\end{array}$ (4.5.3)

Here $C_1$ and $C_2$ are the constants depending on $\mu \mathrm{,}\theta \mathrm{,}{c}_{\mu \mathrm{,}K}$ and $C_{\theta }$ .

The following proposition which has been proved in [9] will be utilized to bound ${\mathcal{S}}_2$ .

Proposition 4.6. Under the assumptions of proposition 4.5. Then, for any $0<\delta <0$ ,with confidence $1-\delta$ , there holds,

$\begin{array}{c}{\mathcal{S}}_2\le C_3\left(1+\frac{1}{l}log\frac{5}{\delta }\right)log\left(\frac{10}{\delta }\right)\times l^{-\frac{2\left(1-\theta \right)}{4-2\theta +\mu \theta }}\\ \times \left({\gamma }_A^{s-1}{\left(l+u\right)}^{-\frac{1}{2}}+{\gamma }_A^{s-1+\theta }{\left(l+u\right)}^{\frac{1-\theta }{2}}\right)\end{array}$ (4.5.4)