ABSTRACT

In this paper, we construct a modified least squares regression algorithm which can provide privacy protection. A new concentration inequality is applied and the expected error bound is derived by error decomposition. Furthermore, via the error analysis, we find a method to choose an appropriate parameter $ϵ$ to balance the error and privacy.

Keywords:

Differential Privacy, Least Squares Regularization, Concentration Inequality, Error Decomposition

1. Introduction

Privacy protection attracts much attention in many branches of computer sci- ence. To deal with this, Dwork et al. proposed differential privacy in [1] . Soon [2] builds an exponential mechanism which is a useful approach to construct a differential private algorithm. The concept is introduced into learning theory in [3] . There, the authors consider output perturbation and object perturbation for ERM algorithms. Analysis of privacy and generalization for those algorithms also has been conducted. P. Jain and his collaborators have done a lot of work on differential private learning afterwards [4] [5] and etc. Recently, in [6] , the authors find that the empirical average of the output from a differential private algorithm can converge to its expectation. And [7] provides another analysis of this convergence, which motivates our work.

In this paper, we consider the following statistical learning model (see [8] [9] for more details): The input space $X$ is a compact metric space, and the output space is $Y\subset ℝ$ as a regression problem. Throughout the paper, we assume the output $Y$ is uniformly bounded, i.e., $\left|y\right|\le M$ for some $M>0$ almost surely. On the sample space $Z:=X\times Y$ , we try to find a function $f:X\to Y$ via some algorithms $\mathcal{A}$ , reflecting the relationship between the input and output. Algorithm $\mathcal{A}$ relies on the random chosen sample $z={\left\{z_i\right\}}_{i=1}^m={\left\{\left(x_i,y_i\right)\right\}}_{i=1}^m$ , while the sample is drawn according to a distribution function $\rho$ on $Z$ . Furthermore, we assume there is a marginal distribution ${\rho }_X$ on $X$ and conditional distribution $\rho \left(y|x\right)$ on $Y$ given some $x$ .

Now we expect the algorithm can provide some privacy protection. We assume $\mathcal{A}$ satisfies the $\left(ϵ\mathrm{,}\gamma \right)$ differential private condition [1] . Denoting the Hamming distance between two sample sets $\left\{z_1,z_2\right\}$ is

$d\left(z_1,z_2\right)=\#\left\{i=1,\cdots ,m:z_{1,i}\ne z_{2,i}\right\},$

i.e., there is only one element is different. Then $\left(ϵ\mathrm{,}\gamma \right)$ -differential private is defined as follows:

Definition 1 A random algorithm $A:Z^m\to \mathcal{H}$ is $\left(ϵ\mathrm{,}\gamma \right)$ -differential private if for every two data sets $z_1\mathrm{,}{z}_2$ satisfying $d\left(z_1,z_2\right)=1$ , and every sets $\mathcal{O}\in \mathcal{H}$ we have

$\mathrm{Pr}\left\{A\left(z_1\right)\in \mathcal{O}\right\}\le {\text{e}}^{ϵ}\cdot \mathrm{Pr}\left\{A\left(z_2\right)\in \mathcal{O}\right\}+\gamma .$

Here $\mathcal{H}$ is a function space from $X$ to $Y$ , which is called the hypothesis space. In the sequel, we focus on the $\left(ϵ\mathrm{,0}\right)$ -differential privacy with some $0<ϵ<1$ , which is always called $ϵ$ -differential privacy for simplicity. How to choose an appropriate $ϵ$ is a fundamental problem in differential private algorithms [10] , and we will provide a method during our error estimation in the following sections.

2. Concentration Inequality

In this section, we study the error between average and expectation for an algorithm $\mathcal{A}$ providing $ϵ$ -differential privacy. Our first result can be stated as follow:

Theorem 1 If an algorithm $\mathcal{A}$ provides $ϵ$ -differential privacy, and outputs a positive function $g_{z,\mathcal{A}}:X\times Y\to ℝ$ with bounded expectation ${\mathbb{E}}_{z,\mathcal{A}}{g}_{z,\mathcal{A}}\le G$ for some $G>0$ , where the expectation is taken over the sample via the algorithm output. Then

${\mathbb{E}}_{z,\mathcal{A}}\left(\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_i\right)-{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho \right)\le 2Gϵ,$

and

${\mathbb{E}}_{z,\mathcal{A}}\left({\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_i\right)\right)\le 2Gϵ.$

Denote sample sets $w_j=\left\{z_1,z_2,\cdots ,z_{j-1},{z^{\prime }}_j,z_{j+1},\cdots ,z_m\right\}$ for $j\in \left\{1,2,\cdots ,m\right\}$ . We observe that

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}\left(\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_i\right)\right)=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{\mathcal{A}}\left(g_{z,\mathcal{A}}\left(z_i\right)\right)\\ =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{{z^{\prime }}_i}{\displaystyle {\int }_0^{+\infty }}\underset{\mathcal{A}}{{\displaystyle \mathrm{Pr}}}\left\{g_{z,\mathcal{A}}\left(z_i\right)\ge t\right\}\text{d}t\end{array}$

$\begin{array}{c}\le \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{{z^{\prime }}_i}{\displaystyle {\int }_0^{+\infty }}{\text{e}}^{ϵ}\underset{\mathcal{A}}{{\displaystyle \mathrm{Pr}}}\left\{g_{w_i,\mathcal{A}}\left(z_i\right)\ge t\right\}\text{d}t\\ ={\text{e}}^{ϵ}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i}{\mathbb{E}}_{z_i}{\mathbb{E}}_{\mathcal{A}}\left(g_{w_i,\mathcal{A}}\left(z_i\right)\right)={\text{e}}^{ϵ}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i,\mathcal{A}}{\mathbb{E}}_{z_i}\left(g_{w_i,\mathcal{A}}\left(z_i\right)\right)\\ ={\text{e}}^{ϵ}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i,\mathcal{A}}{\displaystyle {\int }_Z}{g}_{w_i,\mathcal{A}}\left(z\right)\text{d}\rho ={\text{e}}^{ϵ}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{z,\mathcal{A}}{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho \\ ={\text{e}}^{ϵ}{\mathbb{E}}_{z,\mathcal{A}}{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho .\end{array}$

Then

$\begin{array}{l}{\mathbb{E}}_{z,\mathcal{A}}\left(\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_i\right)-{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho \right)\\ \le \left({\text{e}}^{ϵ}-1\right){\mathbb{E}}_{z,\mathcal{A}}\left({\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho \right)\le 2Gϵ.\end{array}$

On the other hand,

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{\mathcal{A}}{\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho \\ =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i}{\mathbb{E}}_{\mathcal{A}}{\displaystyle {\int }_Z}{g}_{w_i,\mathcal{A}}\left(z\right)\text{d}\rho =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i}{\mathbb{E}}_{\mathcal{A}}{\displaystyle {\int }_Z}{g}_{w_i,\mathcal{A}}\left(z_i\right)\text{d}\rho \left(z_i\right)\\ =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_{w_i}{\mathbb{E}}_{z_i}{\mathbb{E}}_{\mathcal{A}}\left(g_{w_i,\mathcal{A}}\left(z_i\right)\right)=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{{z^{\prime }}_i}{\displaystyle {\int }_0^{+\infty }}\underset{\mathcal{A}}{{\displaystyle \mathrm{Pr}}}\left\{g_{w_i,\mathcal{A}}\left(z_i\right)\ge t\right\}\text{d}t\\ \le \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{{z^{\prime }}_i}{\text{e}}^{ϵ}{\displaystyle {\int }_0^{+\infty }}\underset{\mathcal{A}}{{\displaystyle \mathrm{Pr}}}\left\{g_{z,\mathcal{A}}\left(z_i\right)\ge t\right\}\text{d}t\\ ={\text{e}}^{ϵ}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\mathbb{E}}_z{\mathbb{E}}_{\mathcal{A}}\left(g_{z,\mathcal{A}}\left(z_i\right)\right)={\text{e}}^{ϵ}{\mathbb{E}}_{z,\mathcal{A}}\frac{1}{m}{g}_{z,\mathcal{A}}\left(z_i\right).\end{array}$

This leads to

$\begin{array}{l}{\mathbb{E}}_{z,\mathcal{A}}\left({\displaystyle {\int }_Z}{g}_{z,\mathcal{A}}\left(z\right)\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_i\right)\right)\\ =\left({\text{e}}^{ϵ}-1\right){\mathbb{E}}_{z,\mathcal{A}}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{g}_{z,\mathcal{A}}\left(z_j\right)\le 2Gϵ.\end{array}$

These verify our results.

Remark 1 Similar results are proposed in [6] and [7] . However, there the authors limits the function to take value in $\left[0,1\right]$ or $\left\{0,1\right\}$ , our result here extends theirs to the function taking value in ${ℝ}^{+}$ . This makes our following error analysis implementable.

3. Differential Private Learning Algorithm

In this section we consider the differential private least squares regularization algorithm. For a Mercer kernel $K$ defined on $X\times X$ , the function space ${\mathcal{H}}_K:=\overline{\text{span}\left\{K\left(x,\cdot \right),x\in X\right\}}$ is the induced reproducing kernel Hilbert space (RKHS). Denote $K_x\left(y\right)=K\left(x,y\right)$ for any $x,y\in X$ , and $\kappa ={\sup }_{x,y\in X}\sqrt{K\left(x,y\right)}$ . It is well known that $f\left(x\right)={\langle f,K_x\rangle }_K$ as the reproducing property. In the sequel, we always assume $\left|y\right|\le M$ for some constant $M>0$ . The least squares regularization algorithm, which has been extensively studied in such as [8] [11] [12] and etc. is:

$f_{z,\lambda }=\arg \underset{f\in {\mathcal{H}}_K}{\min }\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f\left(x_i\right)-y_i\right)}^2+\lambda {\Vert f\Vert }_K^2.$ (1)

Denote $\pi$ as a projection operator as we did in [13] [14] :

$\pi \left(f\left(x\right)\right)=\{\begin{array}{ll}M,\hfill & f\left(x\right)>M\hfill \\ f\left(x\right),\hfill & -M\le f\left(x\right)\le M\hfill \\ -M,\hfill & f\left(x\right)<-M\hfill \end{array}.$

Then we add a noise term $b$ in the original algorithm (1) like the output perturbation algorithm in [3] :

$f_{z,\mathcal{A}}\left(x\right)=\pi \left(f_{z,\lambda }\left(x\right)\right)+b$ (2)

where the density of $b$ is independent with $z$ which will be clarified in the following analysis. Moreover, we take the following notation for simplicity:

$\mathcal{E}\left(f\right)={\displaystyle {\int }_Z}{\left(f\left(x\right)-y\right)}^2\text{d}\rho ,{\mathcal{E}}_z\left(f\right)=\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f\left(x_i\right)-y_i\right)}^2.$

Definition 2 We denote $\Delta f_z$ as the maximum infinite norm of difference when changing one sample point in $z$ , i.e., if $d\left(z,z^{\prime }\right)=1$ ,

$\Delta f_z=\underset{z,z^{\prime }}{\sup }{\Vert f_z-f_{z^{\prime }}\Vert }_{\infty }.$

Then we have the following result:

Lemma 1 Assume $\Delta \pi \left(f_{z,\lambda }\left(x\right)\right)$ is bounded, and $b$ has density function

proportion to $\exp \left\{-\frac{ϵ\left|b\right|}{\Delta \pi \left(f_{z,\lambda }\right)}\right\}$ , then algorithm (2) provides $ϵ$ -differential

privacy.

The proof is just as Theorem 4 in [15] . For all possible function $r$ , and $z\mathrm{,}{z}^{\prime }$ differ in one element, then

$\mathrm{Pr}\left\{f_{z,\mathcal{A}}=r\right\}=\underset{b}{{\displaystyle \mathrm{Pr}}}\left\{b=r-\pi \left(f_{z,\lambda }\right)\right\}\propto \exp \left(-\frac{ϵ{\Vert r-\pi \left(f_{z,\lambda }\right)\Vert }_{\infty }}{\Delta \pi \left(f_{z,\lambda }\right)}\right),$

and

$\mathrm{Pr}\left\{f_{z^{\prime },\mathcal{A}}=r\right\}=\underset{b}{{\displaystyle \mathrm{Pr}}}\left\{b=r-\pi \left(f_{z^{\prime },\lambda }\right)\right\}\propto \exp \left(-\frac{ϵ{\Vert r-\pi \left(f_{z^{\prime },\lambda }\right)\Vert }_{\infty }}{\Delta \pi \left(f_{z^{\prime },\lambda }\right)}\right).$

So

$\mathrm{Pr}\left\{f_{z,\mathcal{A}}=r\right\}\le \mathrm{Pr}\left\{\pi \left(f_{z^{\prime },\mathcal{A}}\right)=r\right\}\times {\text{e}}^{\frac{ϵ{\Vert \pi \left(f_{z,\lambda }\right)-\pi \left(f_{z^{\prime },\lambda }\right)\Vert }_{\infty }}{\Delta \pi \left(f_{z,\lambda }\right)}}\le {\text{e}}^{ϵ}\mathrm{Pr}\left\{f_{z^{\prime },\mathcal{A}}=r\right\}.$

Then the lemma is proved by a union bound.

Now we will bound the term $\Delta f_{z,\lambda }$ .

Lemma 2 For the function $f_{z,\lambda }$ obtained from algorithm (1), assume ${\Vert f_{z,\lambda }\Vert }_K\le R$ for any $z\in Z^m$ for some $R\ge M$ , and $0<\lambda \le 1$ , we have

$\Delta f_{z,\lambda }\le \frac{2R{\kappa }^2\left(\kappa +1\right)}{\lambda m}.$

Assume $f_{z\mathrm{,}\lambda }$ and $f_{z^{\prime },\lambda }$ are two results derived via algorithm (1) given any sample set $z\mathrm{,}{z}^{\prime }$ satisfying $d\left(z,z^{\prime }\right)=1$ . Without loss of generality, we set $z^{\prime }=\left(z_1,z_2,\cdots ,z_{m-1},z_{m^{\prime }}\right)$ . Since the two functions are both the optimizer of algorithm (1), take derivative for $f$ we have

$\frac{2}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}\left(f_{z,\lambda }\left(x_i\right)-y_i\right)K_{x_i}+2\lambda f_{z,\lambda }=0$

and

$\frac{2}{m}{\displaystyle \underset{i=1}{\overset{m-1}{\sum }}}\left(f_{z^{\prime },\lambda }\left(x_i\right)-y_i\right)K_{x_i}+\frac{2}{m}\left(f_{z^{\prime },\lambda }\left({x^{\prime }}_m\right)-{y^{\prime }}_m\right)K_{x_m}+2\lambda f_{z^{\prime },\lambda }=0.$

These lead to

$\begin{array}{l}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}\left(f_{z,\lambda }\left(x_i\right)-f_{z^{\prime },\lambda }\left(x_i\right)\right)K_{x_i}+\lambda \left(f_{z,\lambda }-f_{z^{\prime },\lambda }\right)\\ =\frac{1}{m}\left[\left(f_{z^{\prime },\lambda }\left({x^{\prime }}_m\right)-{y^{\prime }}_m\right)K_{{x^{\prime }}_m}-\left(f_{z,\lambda }\left(x_m\right)-y_m\right)K_{x_m}\right].\end{array}$

Take inner product with $f_{z,\lambda }-f_{z^{\prime },\lambda }$ by both sides we have

$\begin{array}{l}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f_{z,\lambda }\left(x_i\right)-f_{z^{\prime },\lambda }\left(x_i\right)\right)}^2+\lambda {\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_K^2\\ =\frac{1}{m}[\left(f_{z^{\prime },\lambda }\left({x^{\prime }}_m\right)-{y^{\prime }}_m\right)\left(f_{z,\lambda }\left({x^{\prime }}_m\right)-f_{z^{\prime },\lambda }\left({x^{\prime }}_m\right)\right)\\ -\left(f_{z,\lambda }\left(x_m\right)-y_m\right)\left(f_{z,\lambda }\left(x_m\right)-f_{z^{\prime },\lambda }\left(x_m\right)\right)].\end{array}$

This means

$\begin{array}{c}\lambda {\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_K^2\le \frac{1}{m}\left[\left|f_{z^{\prime },\lambda }\left({x^{\prime }}_m\right)-{y^{\prime }}_m\right|+\left|f_{z,\lambda }\left(x_m\right)-y_m\right|\right]\cdot {\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_{\infty }\\ \le \frac{1}{m}\left({\Vert f_{z^{\prime },\lambda }\Vert }_{\infty }+{\Vert f_{z,\lambda }\Vert }_{\infty }+2M\right)\kappa {\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_K.\end{array}$

The last inequality is from the fact that

${\Vert f\Vert }_{\infty }=\underset{x\in X}{\sup }f\left(x\right)=\underset{x\in X}{\sup }{\langle f,K_x\rangle }_K\le {\Vert K_x\Vert }_K\cdot {\Vert f\Vert }_K\le \kappa {\Vert f\Vert }_K.$

Since ${\Vert f_{z,\lambda }\Vert }_K\le R$ , then ${\Vert f_{z^{\prime },\lambda }\Vert }_K\le R$ as well. Therefore,

${\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_K\le \frac{1}{\lambda m}\left(2R\kappa +2M\right)\kappa \le \frac{2R\kappa \left(\kappa +1\right)}{\lambda m}$

for any $0<\lambda \le 1$ . So

${\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_{\infty }\le \frac{2R{\kappa }^2\left(\kappa +1\right)}{\lambda m}$

for any $z\mathrm{,}{z}^{\prime }$ , and our lemma holds.

It can be easily verified by discussion that

${\Vert \pi \left(f_{z,\lambda }\right)-\pi \left(f_{z^{\prime },\lambda }\right)\Vert }_{\infty }\le {\Vert f_{z,\lambda }-f_{z^{\prime },\lambda }\Vert }_{\infty }$

for any $z\mathrm{,}{z}^{\prime }$ , so we have the choice of noise $b$ and the result for algorithm (2).

Proposition 1 Assume ${\Vert f_{z,\lambda }\Vert }_K\le R$ for any $z\in Z^m$ for some $R\ge M$ , and $b$ takes value in $\left(-\infty ,+\infty \right)$ , we choose the density of $b$ to be

$\frac{1}{\alpha }\exp \left(-\frac{\lambda mϵ\left|b\right|}{2R{\kappa }^2\left(\kappa +1\right)}\right)$ , where $\alpha =\frac{4R{\kappa }^2\left(\kappa +1\right)}{\lambda mϵ}$ , then the algorithm (2) pro-

vides $ϵ$ -differential privacy.

The proof is by combining the two lemmas and the inequality above. And by simply calculation we can get the expression of $\alpha$ .

4. Error Analysis for Differential Private Learning Algorithm

In this section, we will study the expectation of the error between $\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)$ , where $f_{\rho }={\displaystyle {\int }_Y}y\text{d}\rho \left(y|x\right)$ is the regression function which minimizes $\mathcal{E}\left(f\right)$ . Firstly we shall introduce the error decomposition:

$\begin{array}{l}\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)\le \mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)+\lambda {\Vert f_{z,\lambda }\Vert }_K^2\hfill \\ \begin{array}{l}\le \mathcal{E}\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)+{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)\\ +{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)+\lambda {\Vert f_{z,\lambda }\Vert }_K^2-\mathcal{E}\left(f_{\rho }\right)\end{array}\hfill \\ \begin{array}{l}\le \mathcal{E}\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)+{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)\\ +{\mathcal{E}}_z\left(f_{z,\lambda }\right)+\lambda {\Vert f_{z,\lambda }\Vert }_K^2-\mathcal{E}\left(f_{\rho }\right)\end{array}\hfill \\ \begin{array}{l}\le \mathcal{E}\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)+{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)\\ +{\mathcal{E}}_z\left(f_{\lambda }\right)+\lambda {\Vert f_{\lambda }\Vert }_K^2-\mathcal{E}\left(f_{\rho }\right)\end{array}\hfill \\ \le {\mathcal{R}}_1+{\mathcal{R}}_2+\mathcal{S}+D\left(\lambda \right),\hfill \end{array}$ (3)

where $f_{\lambda }$ is a function in ${\mathcal{H}}_K$ to be determined and

${\mathcal{R}}_1=\mathcal{E}\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right),$

${\mathcal{R}}_2={\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right),$

$\mathcal{S}={\mathcal{E}}_z\left(f_{\lambda }\right)-\mathcal{E}\left(f_{\lambda }\right),$

$D\left(\lambda \right)=\mathcal{E}\left(f_{\lambda }\right)-\mathcal{E}\left(f_{\rho }\right)+\lambda {\Vert f_{\lambda }\Vert }_K^2.$

Here ${\mathcal{R}}_1$ and ${\mathcal{R}}_2$ involve the function $f_{z\mathrm{,}\mathcal{A}}$ from random algorithm (2) so we call them random errors. $\mathcal{S}$ and $D\left(\lambda \right)$ are similar as classical ones in the past literature in learning theory and we still call them sample error and approximation error. In the following, we will study these errors respectively.

4.1. Error Bounds for Random Errors

Proposition 2 For function $f_{z\mathrm{,}\mathcal{A}}$ obtained from algorithm (2) with density of $b$ as described in Proposition 1, we have

${\mathbb{E}}_{z,\mathcal{A}}{\mathcal{R}}_1\le 8ϵ\left(\frac{2R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+M^2\right).$

Note that

${\mathcal{R}}_1={\displaystyle {\int }_Z}{\left(f_{z,\mathcal{A}}\left(x\right)-y\right)}^2\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f_{z,\mathcal{A}}\left(x_i\right)-y_i\right)}^2,$

analogous analysis to the proof of Theorem 1 tells us that

$\begin{array}{l}{\mathbb{E}}_{z,\mathcal{A}}\left({\displaystyle {\int }_Z}{\left(f_{z,\mathcal{A}}\left(x\right)-y\right)}^2\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f_{z,\mathcal{A}}\left(x_i\right)-|y_i\right)}^2\right)\\ \le \left({\text{e}}^{ϵ}-1\right){\mathbb{E}}_z{\mathbb{E}}_{\mathcal{A}}\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(\pi \left(f_{z,\lambda }\left(x_i\right)\right)+b-y_i\right)}^2\text{d}\rho \\ =2ϵ{\mathbb{E}}_z{\mathbb{E}}_b\left(b^2+b\left(\pi \left(f_{z,\lambda }\left(x_i\right)\right)-y_i\right)+{\left(\pi \left(f_{z,\lambda }\left(x_i\right)\right)-y_i\right)}^2\right)\\ \le 2ϵ\left(\frac{8R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+4M^2\right),\end{array}$

which verifies the proposition.

For the term ${\mathcal{R}}_2$ , we have the same analysis.

Proposition 3 For function $f_{z\mathrm{,}\mathcal{A}}$ obtained from algorithm (2) with density of $b$ as described in Proposition 1, we have

${\mathbb{E}}_{z,\mathcal{A}}{\mathcal{R}}_2\le \frac{8R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}.$

Since

$\begin{array}{c}{\mathcal{R}}_2={\mathcal{E}}_z\left(f_{z,\mathcal{A}}\right)-{\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)\\ =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}\left[{\left(f_{z,\mathcal{A}}\left(x_i\right)-y_i\right)}^2-{\left(\pi \left(f_{z,\lambda }\left(x_i\right)\right)-y_i\right)}^2\right]\\ =\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}b\left(b+2\pi \left(f_{z,\lambda }\left(x_i\right)\right)-2y_i\right)\\ =b^2+2b\cdot \frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}\left(\pi \left(f_{z,\lambda }\left(x_i\right)\right)-y_i\right),\end{array}$

we have

${\mathbb{E}}_{z,\mathcal{A}}{\mathcal{R}}_2={\mathbb{E}}_z{\mathbb{E}}_b{b}^2\le \frac{8R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}.$

And the proposition is proved.

4.2. Error Estimates for Sample Error and Approximation Error

Error estimates for sample error and approximation error have been extensively studied since [8] . Here we provide the proof for completeness. It is known that $f_{\lambda }$ in the error decomposition (3) can be arbitrarily chosen in ${\mathcal{H}}_K$ in [12] [13] [14] and etc. Here we simply choose it to be the classical one

$f_{\lambda }=\arg \underset{f\in {\mathcal{H}}_K}{\min }\mathcal{E}\left(f\right)+\lambda {\Vert f\Vert }_K^2.$

From [16] [17] we have the expression of $f_{\lambda }$ is

$f_{\lambda }={\left(L_K+\lambda \right)}^{-1}{L}_K{f}_{\rho },$

where $L_K$ is the operator defined on $L_{{\rho }_X}^2$ as

$L_{K}f\left(t\right)={\displaystyle {\int }_X}f\left(x\right)K\left(x,t\right)\text{d}{\rho }_X.$

[8] told us that $L_K$ has a eigenvalue sequence ${\left\{{\mu }_i\right\}}_{i\ge 1}$ satisfies ${\mu }_i>0{\mu }_i\to 0$ when $i\to \infty$ , and $\Vert L_K\Vert \le {\kappa }^2$ . Now we recall the Hoeffding inequality [18] .

Lemma 3 Let $\xi$ be a random variable on a probability space $Z$ satisfying $\left|\xi \left(z\right)-\mathbb{E}\xi \right|\le B$ for some $B>0$ for almost all $z\in Z$ , then

$\mathrm{Pr}\left\{\left|\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}\xi \left(z_i\right)-\mathbb{E}\xi \ge \epsilon \right|\right\}\le 2\exp \left\{-\frac{m{\epsilon }^2}{2B^2}\right\}.$

Then we have the following analysis.

Proposition 4 For $f_{\lambda }$ and $f_{\rho }$ defined as above, assume $f_{\rho }\in L_K^r\left(L_{{\rho }_X}^2\right)$ , we have

${\mathbb{E}}_{z,\mathcal{A}}\mathcal{S}+D\left(\lambda \right)\le \frac{8\sqrt{2\text{π}}{M}^2}{\sqrt{m}}+{\lambda }^{\min \left\{2r,1\right\}}\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.$

Firstly we bound the sample error.

$\begin{array}{c}\mathcal{S}=\mathcal{E}\left(f_{\lambda }\right)-{\mathcal{E}}_z\left(f_{\lambda }\right)\\ ={\displaystyle {\int }_Z}{\left(f_{\lambda }\left(x\right)-y\right)}^2\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f_{\lambda }\left(x_i\right)-y_i\right)}^2.\end{array}$

Let $\xi \left(z\right)=-{\left(f_{\lambda }\left(x\right)-y\right)}^2$ , since $\left|f_{\rho }\left(x\right)\right|=\left|{\displaystyle {\int }_Y}y\text{d}\rho \left(y|x\right)\right|\le M$ , and

$\begin{array}{c}{\Vert f_{\lambda }\Vert }_{\infty }={\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K{f}_{\rho }\Vert }_{\infty }\\ \le \Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K\Vert \cdot {\Vert f_{\rho }\Vert }_{\infty }\le M,\end{array}$

we have $\left|\xi -\mathbb{E}\xi \right|\le 8M^2$ . So from Hoeffding inequality there holds

$\begin{array}{l}\underset{z}{{\displaystyle \mathrm{Pr}}}\left\{\left|{\displaystyle {\int }_Z}{\left(f_{\lambda }\left(x\right)-y\right)}^2\text{d}\rho -\frac{1}{m}{\displaystyle \underset{i=1}{\overset{m}{\sum }}}{\left(f_{\lambda }\left(x_i\right)-y_i\right)}^2\right|\ge \epsilon \right\}\\ \le 2\exp \left\{-\frac{m{\epsilon }^2}{128M^4}\right\}.\end{array}$

Then we have

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}\mathcal{S}\le {\mathbb{E}}_z\left|\mathcal{S}\right|={\displaystyle {\int }_0^{+\infty }}\underset{z}{{\displaystyle \mathrm{Pr}}}\left\{\left|\mathcal{S}\right|\ge t\right\}\text{d}t\\ ={\displaystyle {\int }_0^{+\infty }}2\exp \left\{-\frac{m{t}^2}{128M^4}\right\}\text{d}t\le \frac{8\sqrt{2\text{π}}{M}^2}{\sqrt{m}}.\end{array}$

For the approximation error, note that $\mathcal{E}\left(f_{\lambda }\right)-\mathcal{E}\left(f_{\rho }\right)={\Vert f_{\lambda }-f_{\rho }\Vert }_{\rho }^2$ [9]

which is independent with $z$ and $b$ , we have

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}\mathcal{E}\left(f_{\lambda }\right)-\mathcal{E}\left(f_{\rho }\right)={\Vert f_{\lambda }-f_{\rho }\Vert }_{\rho }^2\\ ={\Vert {\left(L_K+\lambda I\right)}^{-1}\left(L_K-\left(L_K+\lambda I\right)\right)f_{\rho }\Vert }_{\rho }^2\\ ={\lambda }^2{\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K^r{L}_K^{-r}{f}_{\rho }\Vert }_{\rho }^2\\ \le {\lambda }^2{\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K^r\Vert }^2{\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2\\ \le \{\begin{array}{ll}{\lambda }^{2r}{\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2,\hfill & r\le 1\hfill \\ {\lambda }^2{\kappa }^{4\left(r-1\right)}{\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2,\hfill & r>1\hfill \end{array}\\ \le {\lambda }^{\min \left\{2r,2\right\}}\left({\kappa }^{4\left(r-1\right)}+1\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.\end{array}$

On the other hand, in [8] , the authors pointed out that ${\Vert f\Vert }_K={\Vert L_K^{-\frac{1}{2}}f\Vert }_{\rho }$ for

any $f\in {\mathcal{H}}_K$ . So

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}\lambda {\Vert f_{\lambda }\Vert }_K^2=\lambda {\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K{f}_{\rho }\Vert }_K^2\\ =\lambda {\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K^{\frac{1}{2}}{f}_{\rho }\Vert }_{\rho }^2\\ \le \lambda {\Vert {\left(L_K+\lambda I\right)}^{-1}{L}_K^{\frac{1}{2}+r}\Vert }^2\cdot {\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2\\ \le \{\begin{array}{ll}{\lambda }^{2r}{\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2,\hfill & r\le \frac{1}{2}\hfill \\ \lambda \cdot {\kappa }^{4r-2}{\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2,\hfill & r>\frac{1}{2}\hfill \end{array}\\ \le {\lambda }^{\min \left\{2r,1\right\}}\left({\kappa }^{4r-2}+1\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.\end{array}$

Combining the 3 bounds above, we can verify the proposition.

4.3. Convergence Result with Fixed $ϵ$

In our analysis for ${\mathbb{E}}_{z,\mathcal{A}}{\mathcal{R}}_1$ above, we indeed have the following result

${\mathbb{E}}_{z,\mathcal{A}}{\mathcal{R}}_1\le \frac{16R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2ϵ}+2ϵ{\mathbb{E}}_z{\epsilon }_z\left(\pi \left(f_{z,\lambda }\right)\right).$

Therefore, the error decomposition can be

$\begin{array}{l}{\mathbb{E}}_{z,\mathcal{A}}\left(\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\left(1+2ϵ\right)\mathcal{E}\left(f_{\rho }\right)\right)\\ ={\mathbb{E}}_{z,\mathcal{A}}\left({\mathcal{R}}_1+{\mathcal{R}}_2+\mathcal{S}+D\left(\lambda \right)-2ϵ\mathcal{E}\left(f_{\rho }\right)\right)\\ \le \frac{16R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2ϵ}+\frac{8R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+{\mathbb{E}}_{z}2ϵ\left({\mathcal{E}}_z\left(\pi \left(f_{z,\lambda }\right)\right)-\mathcal{E}\left(f_{\rho }\right)\right)+{\mathbb{E}}_z\left(\mathcal{S}+D\left(\lambda \right)\right)\\ \le \frac{24R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+2ϵ{\mathbb{E}}_z\left({\mathcal{E}}_z\left(f_{z,\lambda }\right)+\lambda {\Vert f_{z,\lambda }\Vert }_K^2-\mathcal{E}\left(f_{\rho }\right)\right)+{\mathbb{E}}_z\left(\mathcal{S}+D\left(\lambda \right)\right)\\ \le \frac{24R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+2ϵ{\mathbb{E}}_z\left({\mathcal{E}}_z\left(f_{\lambda }\right)+\lambda {\Vert f_{\lambda }\Vert }_K^2-\mathcal{E}\left(f_{\rho }\right)\right)+{\mathbb{E}}_z\left(\mathcal{S}+D\left(\lambda \right)\right)\\ \le \frac{24R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+\left(1+2ϵ\right){\mathbb{E}}_z\left(\mathcal{S}+D\left(\lambda \right)\right)\\ \le \frac{24M^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^3{m}^2{ϵ}^2}+\frac{3\sqrt{2\text{π}}{M}^2\left(1+2ϵ\right)}{\sqrt{m}}+{\lambda }^{\min \left\{1,2r\right\}}\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.\end{array}$

Then by choosing $\lambda ={\left(\frac{1}{m}\right)}^{2/\min \left\{4,3+2r\right\}}$ for balance we have the following

result.

Theorem 2 Let $f_{z,\mathcal{A}}$ derived from algorithm (2), $f_{z,\lambda }$ , $f_{\lambda }$ defined in the

above subsections, and assume $f_{\rho }\in L_K^r\left(L_{{\rho }_{X^2}}\right)$ , take $\lambda ={\left(\frac{1}{m}\right)}^{2/\min \left\{4,3+2r\right\}}$ ,

there holds

${\mathbb{E}}_{z,\mathcal{A}}\left(\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\left(1+2ϵ\right)\mathcal{E}\left(f_{\rho }\right)\right)\le C_{ϵ}{\left(\frac{1}{m}\right)}^{\min \left\{\frac{1}{2},\frac{4r}{3+2r}\right\}},$

where constant

$C_{ϵ}=\frac{24M^2{\kappa }^4{\left(\kappa +1\right)}^2}{{ϵ}^2}+8\sqrt{2\text{π}}{M}^2\left(1+2ϵ\right)+\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2$ .

4.4. Selection of $ϵ$ and Total Error Bound

From the analysis for random error, sample error and approximation error above, we can obtain the whole error bound as follow.

Theorem 3 Let $f_{z,\mathcal{A}}$ derived from algorithm (2), $f_{z,\lambda }$ , $f_{\lambda }$ defined in the

above subsections, and assume $f_{\rho }\in L_K^r\left(L_{{\rho }_{X^2}}\right)$ , take

$\lambda ={\left(\frac{1}{mϵ}\right)}^{2/\min \left\{4,3+2r\right\}},$

and

$ϵ={\left(\frac{1}{\sqrt{m}}\right)}^{\min \left\{1/3,4r/\left(3+6r\right)\right\}}$

we have

${\mathbb{E}}_{z,\mathcal{A}}\left(\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)\right)\le \tilde{C}{\left(\frac{1}{m}\right)}^{\min \left\{\frac{1}{3},\frac{4r}{3+6r}\right\}},$

where constant

$\begin{array}{l}\tilde{C}=8\left(1+\sqrt{2\text{π}}\right)M^2+24M^2{\kappa }^4{\left(\kappa +1\right)}^2\\ +\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.\end{array}$

It can be seen from error decomposition (3) that

$\begin{array}{c}{\mathbb{E}}_{z,\mathcal{A}}\left(\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)\right)\le {\mathbb{E}}_{z,\mathcal{A}}\left(\mathcal{E}\left(f_{z,\mathcal{A}}\right)-\mathcal{E}\left(f_{\rho }\right)+\lambda {\Vert f_{z,\lambda }\Vert }_K^2\right)\\ \le {\mathbb{E}}_{z,\mathcal{A}}\left({\mathcal{R}}_1+{\mathcal{R}}_2+\mathcal{S}+D\left(\lambda \right)\right)\\ \le 8ϵ\left(\frac{2R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+M^2\right)+\frac{8R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}\\ +\frac{8\sqrt{2\text{π}}{M}^2}{\sqrt{m}}+{\lambda }^{\min \left\{2r,1\right\}}\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2\\ \le 8M^2ϵ+\frac{24R^2{\kappa }^4{\left(\kappa +1\right)}^2}{{\lambda }^2{m}^2{ϵ}^2}+\frac{8\sqrt{2\text{π}}{M}^2}{\sqrt{m}}\\ +{\lambda }^{\min \left\{2r,1\right\}}\left({\kappa }^{4r-2}+{\kappa }^{4r-4}+2\right){\Vert L_K^{-r}{f}_{\rho }\Vert }_{\rho }^2.\end{array}$