Optimality of the Approximation and Learning by the Rescaled Pure Super Greedy Algorithms

Abstract

We propose the Weak Rescaled Pure Super Greedy Algorithm (WRPSGA) for approximation with respect to a dictionary $\mathcal{D}$ in Hilbert space. The WRPSGA is simpler than some popular greedy algorithms. We show that the convergence rate of the RPSGA on the closure of the convex hull of the $\mu$-coherent dictionary $\mathcal{D}$ is optimal. Then, we design the Rescaled Pure Super Greedy Learning Algorithm (RPSGLA) for kernel-based supervised learning. We prove that the convergence rate of the RPSGLA can be arbitrarily close to the best rate $O\left(m^{-1}\right)$ under some mild assumptions.

1. Introduction

Non-linear sparse approximation with respect to dictionaries has been widely used in many application areas, such as machine learning, signal processing, and numerical computation, see [1,2,3,4,5,6,7,8]. Greedy algorithms have been used extensively for generating such approximations, see [9,10,11,12]. Among others, super greedy algorithms are very efficient for signal processing and machine learning, see [13,14,15]. In this paper, we propose a new super greedy algorithm—the Weak Rescaled Pure Super Greedy Algorithm (WRPSGA), which is simpler than some well-known greedy algorithms. We estimate the error of the WRPSGA and show that its convergence rate on the convex hull of the dictionary is optimal.

Then, we consider the application of the RPSGA to supervised learning. Since the greedy algorithms have been proven to possess charming generalization capacity with a lower computational burden in [16], they have been used in supervised learning, see Refs. [13,16,17,18,19,20,21,22]. In this paper, we design the Rescaled Pure Super Greedy Learning Algorithm (RPSGLA) and derive an almost optimal convergence rate.

We first recall some basic notions of greedy approximation from [10]. Let H be a Hilbert space with an inner product $\langle ·,·\rangle$ and the norm $\parallel x\parallel =\sqrt{\langle x,x\rangle }$. A set of elements $\mathcal{D}\subset H$ is called a dictionary if $\parallel \phi \parallel =1$ for every $\phi \in \mathcal{D}$, and $\overline{\mathrm{span}}\left(\mathcal{D}\right)$ is H. We consider symmetric dictionaries, i.e., $\phi \in \mathcal{D}\mathrm{implies}-\phi \in \mathcal{D}$.

Let $f_m$ be the output of a greedy-type algorithm with respect to a dictionary $\mathcal{D}$ after m iterations. We want to estimate the decay of $\parallel f-f_m\parallel$ as $m\to \infty$. To solve this problem, we need the following classes of sparse elements.

For a dictionary $\mathcal{D}$, we define the class of the elements

$${\mathcal{A}}_1^0(\mathcal{D},N):=\left\{f:f=\sum _{k\in \mathrm{\Lambda }}{c}_k{\phi }_k,{\phi }_k\in \mathcal{D},\#(\mathrm{\Lambda })<\infty ,\sum _{k\in \mathrm{\Lambda }}\left|c_k\right|\le N\right\},$$

and by ${\mathcal{A}}_1(\mathcal{D},N)$ its closure in H. Let ${\mathcal{A}}_1\left(\mathcal{D}\right)$ be the union of the classes ${\mathcal{A}}_1(\mathcal{D},N)$ over all $N>0$. For $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, we define the norm of f as

$${\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}:=inf\left\{N:f\in {\mathcal{A}}_1(\mathcal{D},N)\right\}.$$

The most natural greedy algorithm with respect to $\mathcal{D}$ is the Pure Greedy Algorithm (PGA). We recall the definition of it from [10].

PGA(H, $\mathcal{D}$):  

• Step 0: Define $f_0=0$.
• Stepm:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$|\langle f-f_{m-1},{\phi }_m\rangle |=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

Define the next approximant to be

$$f_m=\sum _{i=1}^m\langle f-f_{m-1},{\phi }_i\rangle {\phi }_i,$$

and proceed to Step $m+1$.  

We recall the result about the upper estimate of the convergence rate of the PGA in [10].

Theorem 1.

Let $\mathcal{D}$ be an arbitrary dictionary in H. Then, for each $f\in {\mathcal{A}}_1(\mathcal{D},N),$ the PGA has the following convergence rate

$$\parallel f-f_m\parallel \le N{m}^{-1/6},m=0,1,2,\dots .$$

Since the rate of convergence of PGA was unsatisfying, some modified greedy algorithms, such as the Orthogonal Greedy Algorithm (OGA) and the Rescaled Pure Greedy Algorithm (RPGA), were proposed. We first recall the definition of the OGA in [10].

OGA(H, $\mathcal{D}$):  

• Step 0: Define $f_0=0$.
• Stepm:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$|\langle f-f_{m-1},{\phi }_m\rangle |=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

Define the next approximant to be

$$f_m=P_m\left(f\right),$$

where $P_m$ is the orthogonal projection operator onto span$\{{\phi }_1,{\phi }_2,···,{\phi }_m\}$, and proceed to Step $m+1$.  

In [10], the authors derived the following convergence rate for the OGA.

Theorem 2.

Let $\mathcal{D}$ be an arbitrary dictionary in H. Then, for each $f\in {\mathcal{A}}_1(\mathcal{D},N),$ the OGA has the following convergence rate

$$\parallel f-f_m\parallel \le N{m}^{-1/2},m=0,1,2,\dots .$$

It is clear that when $\mathcal{D}$ is an orthonormal basis, the rate $O\left(m^{-1/2}\right)$ is sharp, see [6]. Thus, this convergence rate serves as a benchmark for the approximation ability of the greedy-type algorithms.

To study the error for $f\in H$, in [16], the authors defined the K-functional for the pair $(H,{\mathcal{A}}_1\left(\mathcal{D}\right))$ as follows

$$K(f,\zeta ;H,{\mathcal{A}}_1\left(\mathcal{D}\right)):=\underset{h\in {\mathcal{A}}_1\left(\mathcal{D}\right)}{inf}\left\{{\parallel f-h\parallel }_H+\zeta {\parallel h\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\right\},\forall f\in H,\zeta >0.$$

They proved that for any $f\in H$, the output ${\left\{f_m\right\}}_{m\ge 1}$ of the OGA satisfies

$$\parallel f-f_m\parallel \le 2K(f,m^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)).$$

In [11], Petrova proposed the RPGA as follows:

RPGA(H, $\mathcal{D})$:  

• Step 0: Define $f_0=0$.
• Stepm:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$|\langle f-f_{m-1},{\phi }_m\rangle |=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

With

$${\lambda }_m=\langle f-f_{m-1},{\phi }_m\rangle ,{\widehat{f}}_m:=f_{m-1}+{\lambda }_m{\phi }_m,s_m=\frac{\langle f,{\widehat{f}}_m\rangle }{\parallel {\widehat{f}}_m{\parallel }^2},$$

define the next approximant to be $f_m=s_m{\widehat{f}}_m,$ and proceed to Step $m+1$.  

From the definition, we find that the RPGA is simpler than the OGA from the viewpoint of computational complexity. In [11], the author derived the following convergence rate for the RPGA.

Theorem 3.

Let $\mathcal{D}$ be an arbitrary dictionary in H. If $f\in {\mathcal{A}}_1\left(\mathcal{D}\right),$ then the RPGA has the following convergence rate

$$\parallel f-f_m{\parallel \le \parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{(m+1)}^{-1/2},m=0,1,2,\dots .$$

He also proved that for any $f\in H$, the output ${\left\{f_m\right\}}_{m\ge 1}$ of the RPGA satisfies

$$\parallel f-f_m\parallel \le 2K(f,{(m+1)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)).$$

Now we recall super greedy algorithms. In [14], Liu and Temlyakov proposed the Weak Orthogonal Super Greedy Algorithm (WOSGA). The WOSGA with parameter s and a weakness sequence $\tau :={\left\{t_m\right\}}_{m=1}^{\infty }$, where $t_m\in (0,1],m=1,2,...,$ was defined as follows:

WOSGA(s, $\tau$):  

Initially, we define $f_0:=0$. Then for a natural number $s\ge 1$ and each $m\ge 0$, we inductively define:

(1):

Denote $I_m:=[(m-1)s+1,ms]$. Let ${\phi }_{(m-1)s+1},\dots ,{\phi }_{ms}\in \mathcal{D}$ satisfy the inequality

$$\underset{i\in I_m}{min}|\langle f-f_{m-1},{\phi }_i\rangle |\ge t_m\underset{\phi \in \mathcal{D},\phi \ne {\phi }_i,i\in I_m}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

(2):

Let $H_m:=H_m\left(f\right):=\mathrm{span}({\phi }_1,\dots ,{\phi }_{ms})$ and $P_{H_m}$ denote the orthogonal projection operator onto $H_m$. Define

$$f_m\left(f\right):=f_m^{s,\tau }(f,\mathcal{D}):=P_{H_m}\left(f\right).$$

The WOSGA selects more than one element from a dictionary in each iteration step and hence reduces the computational burden of the conventional OGA. Thus, compared with OGA, the WOSGA can construct the approximant more quickly. We recall some results on the error estimates of the WOSGA. When $t_1=,\dots ,=t_m=t$, we use the notation OSGA(s, t) instead of WOSGA(s, $\tau$). We denote

$$\mu \left(\mathcal{D}\right):=\underset{{\phi }_1\ne {\phi }_2\in \mathcal{D}}{sup}|\langle {\phi }_1,{\phi }_2\rangle |$$

the coherence of a dictionary $\mathcal{D}$. It is clear that the smaller the $\mu \left(\mathcal{D}\right),$ the more the $\mathcal{D}$ resembles an orthonormal basis. Throughout this paper, we consider dictionaries with small values of coherence $\mu \left(\mathcal{D}\right)>0,$ and call them $\mu$-coherent dictionaries.

In [14], the authors derived the following convergence rate for the OSGA(s, t).

Theorem 4.

Let $\mathcal{D}$ be a dictionary with coherence $\mu .$ Then, for $f\in H$ and $s\le {\left(2\mu \right)}^{-1},$ the OSGA(s,t) provides, after m iterations, an approximation of $f\in {\mathcal{A}}_1(\mathcal{D},1)$ with the following convergence rate:

$$\parallel f-f_m\parallel \le \sqrt{81/8}(1+t)/t^2{\left(sm\right)}^{-1/2},k=1,2,\dots .$$

In [13], the authors established the following error bound for the OSGA(s,t).

Theorem 5.

Let $\mathcal{D}$ be a dictionary with coherence $\mu .$ Then for $f\in H,$ and $s\le {\left(2\mu \right)}^{-1}+1,$ the OSGA(s,t) provides, after m iterations, an approximation of f with the error bound

$$\parallel f-f_m\parallel \le C_1(s,\mu ,t)K(f,{\left(sm\right)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)),k=1,2,\dots .$$

(1)

Motivated by the above results, in Section 2, we propose the Weak Rescaled Pure Super Greedy Algorithm (WRPSGA) and estimate the error of this algorithm by means of K-functional. We give an error estimate of the form (1) for the WRPSGA. This estimation implies the convergence rate of the WRPSGA for ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is $O\left(m^{-1/2}\right)$ which is optimal. In Section 3, we design the Rescaled Pure Super Greedy Learning Algorithm (RPSGLA) for solving the regression problem which is fundamental in statistical learning. We derive a learning rate that can be arbitrarily close to the best rate $O\left(m^{-1}\right)$. In Section 4, we prove the main result derived in Section 3. In Section 5, we test the performance of the RPSGLA by numerical experiments. The simulation results show that RPSGLA is very efficient for regression. In Section 6, we compare the RPSGA with other greedy algorithms to show that the efficiency of RPSGA is the best. In Section 7, we give the conclusions of our study and make some suggestions for further studies.

2. The Weak Rescaled Pure Super Greedy Algorithms

In this section, we present the definition of the Weak Rescaled Pure Super Greedy Algorithm (WRPSGA) and study its approximation ability.

The WRPSGA with parameter s and a weakness sequence $\tau :={\left\{t_m\right\}}_{m=1}^{\infty }$, where $t_m\in (0,1],m=1,2,\dots ,$ is defined as follows:

WRPSGA(s, $\tau$):  

Initially, we define $f_0=0$. Then for a natural number $s\ge 1$ and each $m\ge 0$, we inductively define:

(1):

Denote $I_m:=[(m-1)s+1,ms]$. Let ${\phi }_{(m-1)s+1},\dots ,{\phi }_{ms}\in \mathcal{D}$ satisfy the inequality

$$\underset{i\in I_m}{min}|\langle f-f_{m-1},{\phi }_i\rangle |\ge t_m\underset{\phi \in \mathcal{D},\phi \ne {\phi }_i,i\in I_m}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

(2):

Let $F_m:=\mathrm{span}({\phi }_{(m-1)s+1},\dots ,{\phi }_{ms})$ and $P_{F_m}$ denote the orthogonal projection operator onto $F_m$. With

$${\widehat{f}}_m=f_{m-1}+P_{F_m}(f-f_{m-1}),$$

define the next approximant to be

$$f_m:=f_m^{s,\tau }(f,\mathcal{D}):=s_m{\widehat{f}}_m,with{s}_m=\frac{\langle f,{\widehat{f}}_m\rangle }{\langle {\widehat{f}}_m,{\widehat{f}}_m\rangle }.$$

When $t_1=,\dots ,=t_m=t$, we write the RPSGA(s, t) for the WRPSGA(s, $\tau$).

We now state the main result about the error estimate for the RPSGA(s, t).

Theorem 6.

Let $\mathcal{D}$ be a dictionary with coherence parameter $\mu :=\mu \left(\mathcal{D}\right)$, and $0<t\le 1$. Then, for $f\in H$ and $s\le \frac{1}{2\mu }+\frac{3}{2}$, the error of the RPSGA(s, t) satisfies

$$\parallel f-f_m\parallel \le C(s,\mu ,t)K\left(f,{\left(s(1+m)\right)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)\right),m=1,2,\dots ,$$

where $C(s,\mu ,t)=(3+5t)(1+\mu (s-1))/t^2\sqrt{(1-\mu (s-1\left)\right)}.$

Theorem 6 implies the following corollary.

Corollary 1.

Under the assumption of Theorem 6, if $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, then the error of the RPSGA(s, t) satisfies

$$\parallel f-f_m{\parallel \le C(s,\mu ,t)\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{\left(s(1+m)\right)}^{-1/2},m=1,2,\dots .$$

Remark 1.

We remark that the RPSGA(s, t) adds s new elements at each iteration, while the RPGA adds only one element at each iteration, so the RPSGA(s, t) can reduce the computational cost of RPGA. Theorem 4 and Corollary 1 show that the performance of the RPSGA(s, t) is as good as the performance of the OSGA(s, t) in sense of the rate of convergence. However, from a computational point of view, the OSGA(s, t) is more expensive to implement since at each step it requires the evaluation of the orthogonal projection of f onto span$\{{\phi }_1,{\phi }_2,\dots ,{\phi }_{ms}\}$. While the output of the RPSGA(s, t) is the orthogonal projection of f onto the one dimensional space spanned by $\left\{{\widehat{f}}_m\right\}$.

Remark 2.

Although the convergence rate of the OSGA(s, t) and RPSGA(s, t) on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ are almost the same, see Theorem 4 and Corollary 1, the corresponding constants are different. The constant $C(s,\mu ,t)$ in Corollary 1 is not as good as that in Theorem 4. This is because $C(s,\mu ,t)$ is obtained from Theorem 4 which holds for any $f\in H$ not just for $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$. There is a trade-off between universality and accuracy. Therefore, the constant $C(s,\mu ,t)$ is not so good. Nevertheless, our results still have some advantages. The range of s in Corollary 1 is wider than that in Theorem 4. The factor ${(1+m)}^{-1/2}$ is slightly better than $m^{-1/2}$ in Theorem 4. It would be very interesting to derive the error of the RPSGA(s,t) for $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$ directly. This would help us to see if the constant $C(s,\mu ,t)$ can be improved.

In order to prove Theorem 6, we need the following two lemmas.

Lemma 1

([13]). Assume a dictionary $\mathcal{D}$ has coherence μ. Let ${\left\{g_i\right\}}_{i=1}^s\subset \mathcal{D}$ and $H_{\left(s\right)}=span(g_1,\dots ,g_s)$. Then, we have

$$\frac{1}{1+\mu (s-1)}\sum _{i=1}^s{\langle f,g_i\rangle }^2\le {\parallel P_{H_{\left(s\right)}}\left(f\right)\parallel }^2\le \frac{1}{1-\mu (s-1)}\sum _{i=1}^s{\langle f,g_i\rangle }^2.$$

Lemma 2

([23]). Let $\ell >0$, $r>0$, $B>0$, $J\in \mathbb{N}$ be fixed, and ${\left\{a_m\right\}}_{m=1}^{\infty }$ and ${\left\{b_m\right\}}_{m=2}^{\infty }$ be sequences of non-negative numbers satisfying the inequalities

$$a_J\le B,a_m\le a_{m-1}\left(1-\frac{b_m}{r}{a}_{m-1}^{\ell }\right),m=J+1,J+2,....$$

Then, we have

$$a_m\le max\left\{1,{\ell }^{-1/\ell }\right\}{r}^{1/\ell }{\left(r{B}^{-\ell }+\sum _{k=J+1}^m{b}_k\right)}^{-1/\ell },m=J+1,J+2,\dots .$$

Proof of Theorem 6: 

First, we show that for any $f\in H$ and any $h\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, the inequality

$$\parallel f-f_m{\parallel }^2\le {\parallel f-h\parallel }^2+\frac{C{(s,\mu ,t)}^2}{s(1+m)}{\parallel h\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}^2$$

(2)

holds for $m=1,2,\dots .$

Since ${\mathcal{A}}_1^0(\mathcal{D},N)$ is dense in ${\mathcal{A}}_1(\mathcal{D},N)$, it is enough to prove (2) for elements that are finite sums $h={\sum }_j{c}_j{g}_j$ with ${\sum }_j|c_j|\le N$ and $g_j\in \mathcal{D}$. Let us fix $ϵ>0$, and choose a representation for $h={\sum }_{j=1}^{\infty }{c}_j{g}_j$, such that

$$\sum _{j=1}^{\infty }|c_j|<N+ϵ,|c_1|\ge |c_2|\ge |c_3|\ge \dots .$$

Let $P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right)$ be the projection of f onto ${\mathcal{A}}_1\left(\mathcal{D}\right)$. Note that $P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right)$ can be approximated arbitrarily well by the form of some above elements in ${\mathcal{A}}_1\left(\mathcal{D}\right)$.

Suppose q is such that $|c_q|\ge \frac{a}{s}(N+ϵ)\ge |c_{q+1}|$ with $a=\frac{3+t}{2t}$. Then, the above assumption on the sequence $c_j$ implies that $q\le \lfloor \frac{s}{a}\rfloor$ and $|c_{s+1}|<\frac{N+ϵ}{s}.$

We claim that the elements $g_1,\dots ,g_q$ will be chosen among ${\phi }_1,\dots ,{\phi }_s$ at the first iteration.

Indeed, for $i\in [1,q]$, we have

$$\begin{array}{ccc}\hfill \left|\langle P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right),g_i\rangle \right|& =& \left|〈\sum _{j=1}^{\infty }{c}_j{g}_j,g_i〉\right|\hfill \\ & \ge & \left|c_i\right|-\left|\sum _{j\ne i}^{\infty }〈c_j{g}_j,g_i〉\right|\hfill \\ & \ge & \left|c_i\right|-\mu (N+ϵ-|c_i|)\hfill \\ & \ge & \frac{a}{s}(N+ϵ)(1+\mu )-\mu (N+ϵ).\hfill \end{array}$$

For all g distinct from $g_1,\dots ,g_s$, we have

$$\begin{array}{ccc}\hfill \left|〈P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right),g〉\right|& =& \left|〈\sum _{j=1}^{\infty }{c}_j{g}_j,g〉\right|\hfill \end{array}$$

$$\begin{array}{ccc}& \le & |c_g|+\left|〈\sum _{g_j\ne g}^{\infty }{c}_j{g}_j,g〉\right|\hfill \\ & \le & \frac{N+ϵ}{s}+\mu (N+ϵ)\hfill \\ & =& (N+ϵ)(\mu +\frac{1}{s}).\hfill \end{array}$$

Our assumption $s\le \frac{1}{2\mu }+\frac{3}{2}$ implies $\frac{a}{s}t(N+ϵ)(1+\mu )-t\mu (N+ϵ)\ge (N+ϵ)(\mu +\frac{1}{s}).$ Then, we obtain $|\langle P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right),g_i\rangle |\ge |\langle P_{{\mathcal{A}}_1\left(\mathcal{D}\right)}\left(f\right),g\rangle |.$ This implies that $|\langle f,g_i\rangle |\ge |\langle f,g\rangle |.$ Thus, we do not pick any $g\in \mathcal{D}$ distinct from $g_1,\dots ,g_s$ until we have chosen all $g_1,\dots ,g_q.$

We denote $r_m=f-f_m$ and $a_m=\parallel r_m{\parallel }^2-{\parallel f-h\parallel }^2,m=0,1,2,....$ Since $f_m$ is the orthogonal projection of f onto span$\left\{\widehat{f_m}\right\}$, we have

$$\langle r_m,f_m\rangle =0,$$

(3)

and

$$\parallel r_m{\parallel }^2=\parallel f-s_m{\widehat{f}}_m{\parallel }^2\le {\parallel f-{\widehat{f}}_m\parallel }^2.$$

(4)

According to the definition of ${\widehat{f}}_m$ and the choice of ${\phi }_i,i\in I_m$, we obtain

$$\begin{array}{ccc}\hfill \parallel f-{\widehat{f}}_m{\parallel }^2& =& 〈r_{m-1}-P_{F_m}\left(r_{m-1}\right),r_{m-1}-P_{F_m}\left(r_{m-1}\right)〉\hfill \\ & =& \parallel r_{m-1}{\parallel }^2-2\langle r_{m-1},P_{F_m}\left(r_{m-1}\right)\rangle +{\parallel P_{F_m}\left(r_{m-1}\right)\parallel }^2.\hfill \end{array}$$

We deduce

$$\begin{array}{cc}\hfill & \langle r_{m-1},P_{F_m}\left(r_{m-1}\right)\rangle \hfill \\ \hfill & =\langle P_{F_m}\left(r_{m-1}\right)+r_{m-1}-P_{F_m}\left(r_{m-1}\right),P_{F_m}\left(r_{m-1}\right)\rangle \hfill \\ \hfill & =\parallel P_{F_m}\left(r_{m-1}\right){\parallel }^2.\hfill \end{array}$$

Denote $p_m=\parallel P_{F_m}\left(r_{m-1}\right)\parallel$. We have

$$\parallel f-{\widehat{f}}_m{\parallel }^2={\parallel r_{m-1}\parallel }^2-p_m^2.$$

(5)

Combining (4) with (5), we have

$$\parallel r_m{\parallel }^2\le {\parallel r_{m-1}\parallel }^2-p_m^2.$$

(6)

It follows from (6) that $\parallel r_m{\parallel }_{m=0}^{\infty }$ is a decreasing sequence, and hence, ${\left\{a_m\right\}}_{m=0}^{\infty }$ is also a decreasing sequence.

Now the proof is divided into two cases, according to whether $a_0\le 0$ or $a_0>0$.

Case 1: $a_0:={\parallel f\parallel }^2-{\parallel f-h\parallel }^2\le 0$. Therefore $a_m\le 0$ for all $m\ge 1$, hence inequality (2) holds for $m=1,2,\dots .$

Case 2: $a_0>0$. With (3), we notice that

$$\begin{array}{ccc}\hfill \parallel r_{m-1}{\parallel }^2={\parallel f-f_{m-1}\parallel }^2& =& \langle f-f_{m-1},f-f_{m-1}\rangle \hfill \\ \hfill & =& \langle f-f_{m-1},f\rangle =\langle f-f_{m-1},h+f-h\rangle \hfill \\ & \le & \frac{1}{2}(\parallel r_{m-1}{\parallel }^2{+\parallel f-h\parallel }^2)+\langle r_{m-1},h\rangle .\hfill \end{array}$$

(7)

We proceed with a lower estimate for $p_m^2$. We consider the following quantity for $r_{m-1}$

$$p_s^{\prime }:=\underset{h_i\in \mathcal{D},i\in [1,s]}{sup}\parallel P_{H\left(s\right)}\left(r_{m-1}\right)\parallel ,$$

where $H\left(s\right):=\mathrm{span}(h_1,\dots ,h_s).$ Applying Lemma 1, we have

$${p_s^{\prime }}^2\le \underset{h_i\in \mathcal{D},i\in [1,s]}{sup}{(1-\mu (s-1))}^{-1}\sum _{i=1}^s{\langle r_{m-1},h_i\rangle }^2.$$

(8)

In order to get the relation between $p_s^{\prime }$ and $p_m$, we consider an arbitrary set $\{h_i,i\in [1,s]\}$ of distinct elements of $\mathcal{D}$. Let $W=\{i\in [1,s]|h_i={\phi }_{k\left(i\right)},k\left(i\right)\in I_m\}$ and $W^{\prime }=\{k\left(i\right),i\in W\}$. Then

$$\begin{array}{ccc}\hfill \sum _{i=1}^s{〈f-G_{m-1}\left(f\right),h_i〉}^2& =& \sum _{i\in W}{〈r_{m-1},h_i〉}^2+\sum _{i\in [1,s]\setminus W}{〈r_{m-1},h_i〉}^2.\hfill \end{array}$$

Using the choice of ${\left\{{\phi }_k\right\}}_{k\in I_m}$, we have

$$\underset{k\in I_m\setminus W^{\prime }}{min}|〈r_{m-1},{\phi }_k〉|\ge t\underset{i\in [1,s]\setminus W}{sup}|〈r_{m-1},h_i〉|,$$

and hence

$$\begin{array}{ccc}\hfill \sum _{i=1}^s{〈r_{m-1},h_i〉}^2& \le & \sum _{k\in W^{\prime }}{〈r_{m-1},{\phi }_k〉}^2+t^{-2}\sum _{k\in I_m\setminus W^{\prime }}{〈r_{m-1},{\phi }_k〉}^2\hfill \\ & \le & t^{-2}\sum _{k\in I_m}{〈r_{m-1},{\phi }_k〉}^2.\hfill \end{array}$$

Therefore, by (8) and Lemma 1, we obtain

$${p_s^{\prime }}^2\le {\left(1-\mu (s-1)\right)}^{-1}{t}^{-2}\sum _{k\in I_m}{〈r_{m-1},{\phi }_k〉}^2\le \frac{1+\mu (s-1)}{(1-\mu (s-1))t^2}{p}_m^2.$$

(9)

For any $h\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, we turn to bound $\langle r_{m-1},h\rangle$. For $m\ge 2$, we write $\langle r_{m-1},h\rangle$ as

$$〈r_{m-1},h〉=〈r_{m-1},\sum _{j=1}^q{c}_j{g}_j〉+〈r_{m-1},\sum _{j=q+1}^{\infty }{c}_j{g}_j〉.$$

(10)

By setting $J_l:=[(l-1)s+q+1,ls+q]$, we first bound $〈r_{m-1},{\sum }_{j=q+1}^{\infty }{c}_j{g}_j〉$ as follows

$$\begin{array}{ccc}\hfill 〈r_{m-1},\sum _{j=q+1}^{\infty }{c}_j{g}_j〉& \le & \sum _{l=1}^{\infty }{\left(\sum _{j\in J_l}{c}_j^2\right)}^{1/2}{\left(\sum _{j\in J_l}{\langle r_{m-1},g_j\rangle }^2\right)}^{1/2}\hfill \\ \hfill & \le & \sum _{l=1}^{\infty }{\left(\sum _{j\in J_l}{c}_j^2\right)}^{1/2}{\left(1+\mu (s-1)\right)}^{1/2}\parallel P_{H_{\left(J_l\right)}}\left(r_{m-1}\right)\parallel \hfill \\ & \le & \sum _{l=1}^{\infty }{\left(\sum _{j\in J_l}{c}_j^2\right)}^{1/2}{\left(1+\mu (s-1)\right)}^{1/2}{p}_s^{\prime }.\hfill \end{array}$$

(11)

Since the sequence $c_j$ has the property

$$|c_{q+1}|\ge |c_{q+2}|\ge |c_{q+3}|\ge \dots ,\sum _{j=q+1}^{\infty }|c_j|\le N+ϵ,|c_{q+1}|\le \frac{a}{s}(N+ϵ),$$

we may use the simple inequality

$${\left(\sum _{j\in J_l}{c}_j^2\right)}^{1/2}\le s^{1/2}\left|c_{(l-1)s+q+1}\right|$$

to derive

$$\begin{array}{ccc}\hfill \sum _{l=1}^{\infty }{\left(\sum _{j\in J_l}{c}_j^2\right)}^{1/2}& \le & \sum _{l=1}^{\infty }{s}^{1/2}\left|c_{(l-1)s+q+1}\right|\hfill \\ & \le & s^{1/2}\left(\frac{a}{s}(N+ϵ)+s^{-1}\sum _{l=2}^{\infty }\sum _{j\in J_{l-1}}|c_j|\right)\hfill \\ & \le & s^{-1/2}(N+ϵ)(a+1).\hfill \end{array}$$

Next, we bound $〈r_{m-1},{\sum }_{j=1}^q{c}_j{g}_j〉$ as follows

$$〈r_{m-1},\sum _{j=1}^q{c}_j{g}_j〉\le s^{1/2}\frac{N+ϵ}{s}{\left(1+\mu (s-1)\right)}^{1/2}{p}_s^{\prime }.$$

(12)

Furthermore, by (7) and (10)–(12), we have

$$p_s^{\prime }\ge \frac{s^{1/2}(\parallel r_{m-1}{\parallel }^2{-\parallel f-h\parallel }^2)}{2(a+2)(N+ϵ){(1+\mu (s-1))}^{1/2}}.$$

(13)

By (6), (9), and (13), we get

$$\begin{array}{ccc}\hfill \parallel r_m{\parallel }^2& \le & \parallel r_{m-1}{\parallel }^2-\frac{(1-\mu (s-1))t^2}{1+\mu (s-1)}{p_s^{\prime }}^2\hfill \\ & \le & \parallel r_{m-1}{\parallel }^2-\frac{s{t}^2(1-\mu (s-1))(\parallel r_{m-1}{\parallel }^2{-\parallel f-h\parallel }^2{)}^2}{4{(1+\mu (s-1))}^2{(a+2)}^2{(N+ϵ)}^2}.\hfill \end{array}$$

(14)

Let $ϵ\to 0$. Subtracting ${\parallel f-h\parallel }^2$ from both sides in (14), we obtain

$$a_m\le a_{m-1}\left(1-\frac{s{a}_{m-1}}{N^{2}C{(s,\mu ,t)}^2}\right),$$

(15)

where the constant $C(s,\mu ,t)$ is defined in Theorem 6.

Case 2.1: $0<a_0<N^{2}C{(s,\mu ,t)}^2{s}^{-1}$. In terms of the decreasing property of the sequence ${\left\{a_m\right\}}_{m=0}^{\infty }$, either ${\left\{a_m\right\}}_{m\ge 0}\subset (0,N^{2}C{(s,\mu ,t)}^2{s}^{-1})$, or for some $m^{*}\ge 1$ we have that $a_{m^{*}}\le 0$. Then for $m\ge m^{*}$ the arguments are as in Case 1. Applying Lemma 2 to the positive numbers in the sequence ${\left\{a_m\right\}}_{m=0}^{\infty }$ with $\ell =1$, $b_m=1$, $B=N^{2}C{(s,\mu ,t)}^2{s}^{-1}$, $J=0$ and $r=N^{2}C{(s,\mu ,t)}^2{s}^{-1}$, we obtain

$$a_m\le N^{2}C{(s,\mu ,t)}^2{\left(s(1+m)\right)}^{-1}.$$

Case 2.2: $a_0\ge N^{2}C{(s,\mu ,t)}^2{s}^{-1}$. Taking $m=1$ in inequality (15), we get

$$a_1\le a_0\left(1-\frac{s{a}_0}{N^{2}C{(s,\mu ,t)}^2}\right).$$

Therefore $a_1\le 0$, that is, $\parallel r_1\parallel \le \parallel f-h\parallel$, which gives (2) because of monotonicity.

Now inequality (2) has been proved completely. Then, we have

$$\begin{array}{ccc}\hfill \parallel f-f_m\parallel & \le & K\left(f,C(s,\mu ,t){\left(s(1+m)\right)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)\right)\hfill \\ & \le & C(s,\mu ,t)K\left(f,{\left(s(1+m)\right)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)\right).\hfill \end{array}$$

   □

Proof of Corollary 1: 

If $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, then

$$K\left(f,{\left(s(1+m)\right)}^{-1/2};H,{\mathcal{A}}_1\left(\mathcal{D}\right)\right)\le {\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{\left(s(1+m)\right)}^{-1/2}.$$

Thus we get the desired result from Theorem 6.    □

3. The Rescaled Pure Super Greedy Learning Algorithms

In this section, we consider the application of the RPSGA(s, 1) to supervised learning. In this context, the RPSGA(s, 1) has its new form. We call it the Rescaled Pure Super Greedy Learning Algorithm (RPSGLA). The precise definition of the RPSGLA will be given later.

We first formulate the problem of supervised learning. Let the input space $X\subset {\mathbb{R}}^d$ be a compact subset and the output space $Y\subset \mathbb{R}$. Let $\rho$ be a Borel probability measure on $Z=X\times Y.$ The generalization error for a function $f:X\to Y$ is defined as

$$\mathcal{E}\left(f\right):={\int }_Z{(f\left(x\right)-y)}^{2}d\rho .$$

For each input $x\in X$ and output $y\in Y$, ${(f\left(x\right)-y)}^2$ is the error suffered from the use of f as a model for the process producing y from x. By integrating over $X\times Y$ with respect to $\rho$, we average out the error over all pairs $(x,y)$.

Denote by $L_{{\rho }_X}^2$ the Hilbert space of the square integrable functions defined on X with respect to the measure ${\rho }_X$, where ${\rho }_X\left(x\right)$ is the marginal measure of $\rho$ on X and

$${\parallel f(·)\parallel }_{L_{{\rho }_X}^2}={\left({\int }_X{|f(·)|}^2|d{\rho }_X\right)}^{1/2}.$$

The regression function $f_{\rho }$ which minimizes $\mathcal{E}\left(f\right)$ over all $f\in L_{{\rho }_X}^2$ is given by

$$f_{\rho }\left(x\right):={\int }_{Y}yd\rho (y|x),$$

where $\rho (·|x)$ is the conditional distribution induced by $\rho$ at $x\in X$. In the framework of supervised learning, $\rho$ is unknown and what we have in hand is a set of random samples $\mathbf{z}={(x_i,y_i)}_{i=1}^m\in Z^m$, without loss of generality, we assume that $|y_i|\le M$ for a fixed $M>0$, drawn from the measure $\rho$ identically and independently. The task is to find a good approximation $f_{\mathbf{z}}$ of the regression function, which is derived from some learning algorithm. To measure the approximation ability of $f_{\mathbf{z}}$, we estimate the excess generalization error

$$\mathcal{E}\left(f_{\mathbf{z}}\right)-\mathcal{E}\left(f_{\rho }\right)={\parallel f_{\mathbf{z}}-f_{\rho }\parallel }_{L_{{\rho }_X}^2}^2.$$

(16)

In the designation of the learning algorithm, we replace the generalization error $\mathcal{E}\left(f\right)$ with the empirical error

$${\mathcal{E}}_{\mathbf{z}}\left(f\right):=\frac{1}{m}\sum _{i=1}^m{\left|(f\left(x_i\right)-y_i)\right|}^2.$$

We expect to find a good approximation of $f_{\rho }$ by minimizing ${\mathcal{E}}_{\mathbf{z}}\left(f\right)$ in a suitable way.

Given a training data $\mathbf{z}={(x_i,y_i)}_{i=1}^m$, the empirical inner product and empirical norm are defined as follows:

$${\langle f,g\rangle }_m=\frac{1}{m}\sum _{i=1}^{m}f\left(x_i\right)g\left(x_i\right),$$

$${\parallel f\parallel }_m^2:=\frac{1}{m}\sum _{i=1}^m{|f\left(x_i\right)|}^2.$$

With the definition of the empirical inner product and empirical norm, the empirical error can be represented as follow

$${\mathcal{E}}_{\mathbf{z}}\left(f\right):={\parallel f-y\parallel }_m^2.$$

We consider the kernel-based greedy learning algorithms, which have been studied extensively in machine learning, see [13,16,18,20,22,24]. We will use the continuous kernels, which are more general than the usual Mercer kernels, see [25,26]. The hypothesis spaces based on continuous kernels were used widely in many fields of machine learning, see, for instance, Refs. [18,27,28]. In this way, a wider selection of the kernel offers more flexibility. We say a function K defined on $X\times X$ is a continuous kernel if K is continuous at every $(u,v)\in X\times X$. Let K be a continuous and symmetric kernel. Assume that, in addition, K is positive definite. Then, the space $H=\mathrm{span}\{K_x:=K(x,·):x\in X\}$ is a pre-Hilbert space equipped with the inner product ${\langle K_{x_1},K_{x_2}\rangle }_H=K(x_1,x_2).$ Let $\overline{H}$ be the closure of H with respect to the norm induced by the above inner product. Then, $\overline{H}$ is a reproducing kernel Hilbert space (RKHS) associated with the kernel K. The reproducing property is given by ${\langle K_x,f\rangle }_H=f\left(x\right),\forall x\in X,f\in \overline{H}$. For more details, one can see [25].

We define a data-independent hypothesis space as follows.

Definition 1.

Define a data-independent hypothesis space

$${\mathcal{L}}_1=\left\{f:f=\sum _{j=0}^{\infty }{\beta }_j{\tilde{K}}_{v_j},\sum _{j=0}^{\infty }|{\beta }_j|<\infty ,\left\{v_j\right\}\subset X,{\tilde{K}}_{v_j}=\frac{K_{v_j}}{\parallel K_{v_j}{\parallel }_{L_{{\rho }_X}^2}}\right\},$$

with the norm

$${\parallel f\parallel }_{{\mathcal{L}}_1}=inf\left\{\sum _{j=0}^{\infty }|{\beta }_j|:f\in {\mathcal{L}}_1\right\}.$$

Note that the space ${\mathcal{L}}_1$ is a special kind of ${\mathcal{A}}_1$ space which was introduced in [10], see Section 1.

It follows from the definition of $f_{\rho }$ that $|f_{\rho }|\le M$, so it is natural to restrict the approximation functions to $[-M,M]$. The following truncation operator has been used in the error analysis of learning algorithms for improving the learning rate, see [16,18,22].

Definition 2.

The truncation operator ${\pi }_M$ is defined on the space of measurable functions $f:X\to \mathbb{R}$ as

$${\pi }_M\left(f\right)\left(x\right)=\left\{\begin{array}{ccc}\hfill M,& & iff\left(x\right)>M;\hfill \\ \hfill -M,& & iff\left(x\right)<-M;\hfill \\ \hfill f\left(x\right),& & otherwise.\hfill \end{array}\right.$$

Given a training data $\mathbf{z}={(x_i,y_i)}_{i=1}^m\subset X\times Y$, we define the data-dependent hypothesis space as

$${\mathcal{L}}_{\mathbf{z}}:=\left\{f:f=\sum _{i=0}^m{\alpha }_i{\tilde{K}}_{x_i},\sum _{i=1}^m|{\alpha }_i|<\infty \right\},$$

and define the norm on ${\mathcal{L}}_{\mathbf{z}}$ as

$${\parallel f\parallel }_{{\mathcal{L}}_{\mathbf{z}}}=inf\left\{\sum _{i=0}^m|{\alpha }_i|,f\in {\mathcal{L}}_{\mathbf{z}}\right\}.$$

So, ${\mathcal{L}}_{\mathbf{z}}$ is a subspace of ${\mathcal{L}}_1$.

We will choose an approximant for $f_{\rho }$ from ${\mathcal{L}}_{\mathbf{z}}$ by the RPSGLA.

We now present the RPSGLA as follows Algorithm 1:

Algorithm 1 The RPSGLA

Input:$\mathbf{z}={(x_i,y_i)}_{i=1}^m$, and K, and $T>0$, we get ${\mathcal{D}}_m=\{K_{x_i},i=1,2,...,m\}.$ step 1. Normalization: ${\widehat{K}}_{x_i}=K_{x_i}/{\parallel K_{x_i}\parallel }_m$ and dictionary:${\mathcal{D}}_m^{*}=\{\pm {\widehat{K}}_{x_i}\},i=1,2,...,m.$ step 2. Computation: Let $f_0=0$, $r_k=y-f_k.$ 1: Denote $I_k:=[(k-1)s+1,ks]$. Let ${\phi }_{(k-1)s+1},\dots ,{\phi }_{ks}\in {\mathcal{D}}_m^{*}$ satisfy the inequality $$\underset{i\in I_k}{min}|{\langle r_{k-1},{\phi }_i\rangle }_m|\ge \underset{\phi \in {\mathcal{D}}_m^{*},\phi \ne {\phi }_i,i\in I_k}{sup}|{\langle r_{k-1},\phi \rangle }_m|.$$ 2: Let $F_k:=\mathrm{span}({\phi }_{(k-1)s+1},\dots ,{\phi }_{ks})$ and $P_{F_k}$ denote the orthogonal projection operator onto $F_m$. With $$\widehat{f_k}=f_{k-1}+P_{F_k}\left(r_{k-1}\right),$$ define the next approximant to be $$f_k:=s_k\widehat{f_k},with{s}_k=\frac{{\langle y,\widehat{f_k}\rangle }_m}{{\langle \widehat{f_k},\widehat{f_k}\rangle }_m}.$$ 3: if $\parallel y-f_k{\parallel }_m^2+\parallel f_k{\parallel }_{{\mathcal{L}}_{\mathbf{z}}}\le {\parallel y\parallel }_m^2$ and $k\ge T$ then break. end Output:${\pi }_M\left(f_k\right)$

In the case of $s=1,$ this algorithm coincides with the Rescaled Pure Greedy Learning Algorithm (RPGLA), which was studied in [24]. Here we concentrate on $s>1$.

We recall the following condition which has been widely used for error analysis, see, for instance, Refs. [18,20,26,27,29].

Definition 3.

We say that a kernel K is a $C^{\gamma }$ kernel with $\gamma >0$ if there exists some constant $C_{\gamma }>0,$ such that

$$\left|K^{\left(\right[\gamma \left]\right)}(u,x)-K^{\left(\right[\gamma \left]\right)}(u,x^{{}^{\prime }})\right|\le C_{\gamma }{|x-x^{{}^{\prime }}|}^{\gamma -\left[\gamma \right]},\forall u,x,x^{{}^{\prime }}\in X,$$

where $\left[\gamma \right]$ denotes the largest integer not exceeding γ and $K^{\left(\right[\gamma \left]\right)}(u,x)$ denotes $\left[\gamma \right]$-th partial derivative of $K(u,x)$ with respect to variable x. We set $K^{\left(0\right)}(u,x)=K(u,x)$.

We recall two types of kernels that are used widely in practice. They are all the $C^{\gamma }$ kernels for any $\gamma >0$.

The first one is Guassian kernels: $K_{\sigma }(u,x)=exp(-{\sigma }^2{\parallel u-x\parallel }^2),u,x\in {\mathbb{R}}^d,\sigma >0.$

The second one is polynomial kernels: $K_n(u,x)={(1+u·x)}^n,u,x\in {\mathbb{R}}^d,n\in \mathbb{N}.$

Here $u·x$ is the Euclidean inner product of u and x in ${\mathbb{R}}^d$.

Let $C\left(X\right)$ denote the space of continuous functions defined on X.

Definition 4.

For $0<r\le \frac{1}{2}$, we define the space ${\mathcal{L}}_1^r$ to be the set of all functions f such that, for all m, there exist $h^{{}^{\prime }}\in span\left\{{\mathcal{D}}_m\right\}$ such that

$$\parallel h^{{}^{\prime }}{\parallel }_{{\mathcal{L}}_1}\le \mathcal{B},\parallel f-h^{{}^{\prime }}\parallel \le \mathcal{B}{m}^{-r},$$

where $\parallel ·\parallel$ denotes the uniform norm on $C\left(X\right)$, and the smallest constant $\mathcal{B}$ such that this holds defines a norm for ${\mathcal{L}}_1^r$.

Under the assumption of $f_{\rho }\in {\mathcal{L}}_1^r$, we obtain the following convergence rate of the RPSGLA.

Theorem 7.

Assume that $f_{\rho }\in {\mathcal{L}}_1^r$ and $\delta \in (0,1)$. Let K be a $C^{\gamma }$ kernel with $0<k_1\le K(u,v)\le k_2$, for any $u,v\in X$. Choose $T\ge m.$ For $s\le \frac{1}{2\mu }+\frac{3}{2}$, the output of the RPSGLA satisfies the following inequality with confidence $1-\delta$,

$$\mathcal{E}\left({\pi }_M\left(f_m\right)\right)-\mathcal{E}\left(f_{\rho }\right)\le c{\mathcal{B}}^{2}log\frac{3}{\delta }\left({\left(sm\right)}^{-1}+m^{-2r}+m^{-\frac{2}{p+2}}\right),$$

(17)

where

$$p=\left\{\begin{array}{ccc}\hfill 2d/(d+2\gamma ),& & 0<\gamma \le 1,\hfill \\ \hfill 2d/(d+2),& & 1<\gamma \le 1+d/2,\hfill \\ \hfill d/\gamma ,& & \gamma >1+d/2,\hfill \end{array}\right.$$

and the constant c depends at most on $C_{\gamma }$, δ, K, and M.

Remark 3.

If we take K as an infinitely smooth kernel, such as a Gaussian kernel, then when r is sufficiently close to 1/2, the convergence rate of RPSGLA can be arbitrarily close to $O(m^{-1})$, which is the best learning rate one can obtain so far, see [18,30]. Since in this case the result of Theorem 7 is valid for any $\gamma >0$, the convergence rate of RPSGLA can be arbitrarily close to $O(m^{-1})$ when γ is sufficiently large. To see this, let $\gamma \to \infty$ and $r\to 1/2$, then the right-hand side of (17) tends to $c·m^{-1}$. Note that if we take a finite smooth kernel, then we could not obtain the above convergence rate. In this case, inequality (17) holds only for some fix γ but not all γ.

Remark 4.

We show that the efficiency of the RPSGLA is better than some existing greedy learning algorithms. The convergence rate of the RPSGLA is faster than that of the Orthogonal Super Greedy Learning Algorithm (OSGLA) in [13]. In [13], the rate $O({(mlogm)}^{-1/2})$ was derived. Our convergence rate is also faster than $O({(mlogm)}^{-1/2})$ the convergence rate of the Orthogonal Greedy Learning Algorithm (OGLA) and Relaxed Greedy Learning Algorithm (RGLA) in [16] and $O(m^{-(2\gamma +d)/(2\gamma +2d)})$ the convergence rate of the RGLA in [20]. Additionally, our convergence rate is almost the same as that of the OGLA in [18] and RPGLA in [24]. However, the complexity of the RPSGLA is smaller than the OGLA and RPGLA. We will illustrate this in Section 5 and Section 6. On the other hand, since greedy learning is a large field, there are other greedy learning procedures that are quite different from ours, see [17,19,21].

Remark 5.

Kernel-based greedy algorithms can be used to solve different problems. We only mention some typical works. Moreover, we focus on the approximation problems on RKHS. In [31], the authors proposed kernel-based greedy algorithms to approximate non-linear vectorial functions and derived the rate $O(m^{-1/2})$. In [7,32], kernel-based greedy algorithms were used to approximate a linear functional defined on an RKHS. The authors proved that for the square-integrable functions, the convergence rate can attain $O(m^{-1/2})$. Roughly speaking, the convergence rate of greedy algorithms for functional approximation is similar to that of function approximation, while for the regression problem, one can obtain a faster convergence rate.

4. Error Analysis of the RPSGLA

In this section, we prove Theorem 7. The proof is divided into five parts, the error decomposition strategy, the estimate of sample error, the estimate of hypothesis error, and the estimate of approximation error. Finally, the Theorem 7 is proved by synthesizing the results of each error estimate.

4.1. Error Decomposition Strategy

Before we show the error decomposition strategy of the error analysis, we construct a stepstone function $f_k^{*}\in \mathrm{span}\left({\mathcal{D}}_m\right)$ as follows. As $f_{\rho }\in {\mathcal{L}}_1^r$, there exists a $h_{\rho }:={\displaystyle \sum _{i=0}^m}{a}_i{K}_{x_i}\in \mathrm{span}\left\{{\mathcal{D}}_m\right\}$ such that

$$\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}\le \mathcal{B},\parallel f_{\rho }-h_{\rho }\parallel \le \mathcal{B}{m}^{-r}.$$

(18)

Define $f_0^{*}=0$,

$$\begin{array}{ccc}\hfill f_k^{*}& =& \left(1-\frac{1}{k}\right)f_{k-1}^{*}+\frac{\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}}{k}{\phi }_k^{*},\hfill \\ \hfill \end{array}$$

(19)

where

$${\phi }_k^{*}:=arg\underset{\phi \in {\mathcal{D}}_m^{{}^{\prime }}}{max}\left|{〈h_{\rho }-\left(1-\frac{1}{k}\right)f_{k-1}^{*},\phi 〉}_{L_{{\rho }_X}^2}\right|,$$

and

$${\mathcal{D}}_m^{{}^{\prime }}={\left\{K_{x_i}/\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}\right\}}_{i=1}^m\cup {\left\{-K_{x_i}/\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}\right\}}_{i=1}^m.$$

Lemma 3.

Let $f_k^{*}$ be defined in (19). Then we have $\parallel f_k^{*}{\parallel }_{{\mathcal{L}}_1}\le \mathcal{B}.$

Proof. 

By the definition of $f_k^{*}$, we have

$$\begin{array}{ccc}\hfill f_k^{*}& =& \left(1-\frac{1}{k}\right)\left(1-\frac{1}{k-1}\right)···\left(1-\frac{1}{2}\right){\parallel h_{\rho }\parallel }_{{\mathcal{L}}_1}{\phi }_1^{*}+\left(1-\frac{1}{k}\right)···\left(1-\frac{1}{3}\right)\frac{\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}}{2}{\phi }_2^{*}\hfill \\ & +& ···+\left(1-\frac{1}{k}\right)\frac{\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}}{k-1}{g}_{k-1}^{*}+\frac{\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}}{k}{\phi }_k^{*},\hfill \end{array}$$

then the conclusion of the lemma 3 follows from the fact $\parallel h_{\rho }{\parallel }_{{\mathcal{L}}_1}\le \mathcal{B}$ and $\parallel {\phi }_i^{*}{\parallel }_{L_{{\rho }_X}^2}=1,i=1,2\dots k.$    □

With $f_k^{*}$ at hand, we can give an upper bound of $\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)$ as follows.

Proposition 1.

Let $f_k$ be defined in Algorithm 1. Then, for the $f_k^{*}$ in (19), we have the error decomposition as follows:

$$\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\le \mathcal{S}(\mathcal{z},k)+\mathcal{D}\left(k\right)+\mathcal{P}(\mathcal{z},k),$$

where

$$\mathcal{S}(\mathcal{z},k)=\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-{\mathcal{E}}_{\mathcal{z}}\left(\pi \left(f_k\right)\right)+{\mathcal{E}}_{\mathcal{z}}\left(f_k^{*}\right)-\mathcal{E}\left(f_k^{*}\right),$$

$$\mathcal{D}\left(k\right)=\mathcal{E}\left(f_k^{*}\right)-\mathcal{E}\left(f_{\rho }\right),$$

$$\mathcal{P}(\mathcal{z},k)={\mathcal{E}}_{\mathcal{z}}\left({\pi }_M\left(f_k\right)\right)-{\mathcal{E}}_{\mathcal{z}}\left(f_k^{*}\right).$$

are known as the sample error, the approximation error, and the hypothesis error, respectively, in learning theory.

4.2. Estimate of Sample Error

In this subsection, we will bound the sample error $\mathcal{S}(\mathbf{z},k)$. We set

$$S_1(\mathbf{z},k)=\left\{{\mathcal{E}}_{\mathbf{z}}\left(f_k^{*}\right)-{\mathcal{E}}_{\mathbf{z}}\left(f_{\rho }\right)\right\}-\{\mathcal{E}\left(f_k^{*}\right)-\mathcal{E}\left(f_{\rho }\right)\}$$

and

$$S_2(\mathbf{z},k)=\{\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\}-\{{\mathcal{E}}_{\mathbf{z}}\left({\pi }_M\left(f_k\right)\right)-{\mathcal{E}}_{\mathbf{z}}\left(f_{\rho }\right)\}.$$

Then, the sample error can be written as $\mathcal{S}(\mathbf{z},k)=S_1(\mathbf{z},k)+S_2(\mathbf{z},k)$.

The bound of $S_1(\mathbf{z},k)$ has been proved in [20] by using the one-side Bernstein inequality and the inequality $\parallel f_k^{*}{\parallel }_{{}_{{\mathcal{L}}_1}}\le \mathcal{B}$.

Proposition 2.

For any $0<\delta <1$, with confidence at least $1-\frac{\delta }{3}$, we have

$$S_1(\mathbf{z},k)\le \frac{7{(3M+\mathcal{B})}^{2}log(3/\delta )}{3m}+\frac{1}{2}\mathcal{D}\left(k\right).$$

For the function $f_k$ changed with the sample $\mathbf{z}$, we should obtain the uniform upper bound of $S_2(\mathbf{z},k)$.

We should consider the data-dependent space

$$B_{\varrho }=\left\{f\in {\mathcal{L}}_1:{\parallel f\parallel }_{{\mathcal{L}}_1}\le \varrho \right\}.$$

To estimate the capacity of $B_{\varrho }$, we need the concept of the empirical covering number.

Definition 5.

Let E be a metric space with metric d and F be a subset of E. For any $ϵ>0$, the covering number $\mathcal{N}(F,ϵ,d)$ of F with respect to ϵ and d is defined as the minimal number of balls of radius ϵ whose union covers F, that is,

$$\mathcal{N}(F,ϵ,d):=min\left\{l\in N:F\subset \bigcup _{j=1}^{l}B(t_j,ϵ),forsome{\left\{t_j\right\}}_{j=1}^l\subset E\right\},$$

where $B(t_j,ϵ)=\{t\in E:d(t_j,t)\le ϵ\}.$

Definition 6.

($l_2$ empirical covering number) Let $\mathcal{F}$ be a set of functions on X, $x={\left(x_i\right)}_{i=1}^m\subset X^m$ and let ${\mathcal{F}|}_x=\{{\left(f\left(x_i\right)\right)}_{i=1}^m,f\in \mathcal{F}\}\subset {\mathbb{R}}^m.$ Set ${\mathcal{N}}_{2,x}(\mathcal{F},ϵ)=\mathcal{N}(\mathcal{F}{|}_x,ϵ,d),$ for arbitrary $ϵ>0$. The $l_2$ empirical covering number of $\mathcal{F}$ is defined by

$${\mathcal{N}}_2(\mathcal{F},ϵ)=\underset{m\in N}{sup}\underset{x\in X_m}{sup}{\mathcal{N}}_{2,x},$$

where the $l_2$ metric

$$d_2(\mathit{a},\mathit{b})={\left(\frac{1}{m}\sum _{i=0}^m{|a_i-b_i|}^2\right)}^{\frac{1}{2}},\forall \mathit{a}={\left(a_i\right)}_{i=1}^m\in {\mathbb{R}}^m,\mathit{b}={\left(b_i\right)}_{i=1}^m\in {\mathbb{R}}^m.$$

We will use the following result on the capacity of the unit ball ${\mathcal{B}}_1$.

Lemma 4

([30]). Let X be a compact subset of ${\mathbb{R}}^d$ and K be a $C^{\gamma }$ kernel with some $\gamma >0$. Then, there exist an exponent p, $0<p<2$, and a constant $c_p$, for arbitrary $ϵ>0$, such that

$$log{\mathcal{N}}_2({\mathcal{B}}_1,ϵ)\le c_p{ϵ}^{-p},$$

where

$$p=\left\{\begin{array}{ccc}\hfill 2d/(d+2\gamma ),& & 0<\gamma \le 1,\hfill \\ \hfill 2d/(d+2),& & 1<\gamma \le 1+d/2,\hfill \\ \hfill d/\gamma ,& & \gamma >1+d/2.\hfill \end{array}\right.$$

Now we recall the concentration inequality from [29].

Lemma 5.

Assume that there are constants $B,c>0$ and $\alpha \in [0,1]$ such that ${\parallel f\parallel }_{\infty }\le B$ and $E{f}^2\le c{\left(Ef\right)}^{\alpha }$, for every $f\in \mathcal{F}.$ If for arbitrary $ϵ>0$,

$$log\left({\mathcal{N}}_2(\mathcal{F},ϵ)\right)\le a{ϵ}^{-p}$$

holds for some $a>0$ and $p\in (0,2)$, then there exists a constant $c_p^{{}^{\prime }}$ depending only on p such that for any $t>0$, with probability at least $1-e^{-t}$, there

$$Ef-\frac{1}{m}\sum _{i=1}^{m}f\left(z_i\right)\le \frac{1}{2}{\eta }^{1-\alpha }{\left(Ef\right)}^{\alpha }+c_p^{{}^{\prime }}\eta +2{\left(\frac{ct}{m}\right)}^{\frac{1}{2-\alpha }}+\frac{18Bt}{m},\forall f\in \mathcal{F},$$

where

$$\eta :=max\left\{c^{\frac{2-p}{4-2\alpha +p\alpha }}{\left(\frac{a}{m}\right)}^{\frac{2}{4-2\alpha +p\alpha }},B^{\frac{2-p}{2+p}}{\left(\frac{a}{m}\right)}^{\frac{2}{2+p}}\right\}.$$

Proposition 3.

If K is a $C^{\gamma }$ kernel, then for any $0<\delta <1$, with confidence at least $1-\frac{\delta }{3}$, we have

$$S_2(\mathbf{z},k)\le \frac{1}{2}\{\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\}+C_{2}log\frac{3}{\delta }{m}^{-\frac{2}{p+2}}.$$

Proof. 

Denote

$${\mathcal{F}}_{\varrho }=\{g\left(z\right)={(y-{\pi }_M\left(f\right)\left(x\right))}^2-{(y-f_{\rho }\left(x\right))}^2,f\in B_{\varrho }\}.$$

Hence

$$Eg=\mathcal{E}\left({\pi }_M\left(f\right)\right)-\mathcal{E}\left(f_{\rho }\right)={\parallel {\pi }_M\left(f\right)-f_{\rho }\parallel }_{L_{{\rho }_X}^2}^2,$$

and

$$\frac{1}{m}\sum _{i=1}^{m}g\left(z_i\right)={\mathcal{E}}_{\mathbf{z}}\left({\pi }_M\left(f\right)\right)-{\mathcal{E}}_{\mathbf{z}}\left(f_{\rho }\right).$$

Observe that

$$g\left(z\right)=({\pi }_M\left(f\right)\left(x\right)-f_{\rho }\left(x\right))({\pi }_M\left(f\right)\left(x\right)-y)+(f_{\rho }\left(x\right)-y)).$$

From the obvious inequalities ${\parallel f\parallel }_{\infty }\le M$ and $|f_{\rho }|\le M$, we get the inequalities

$$|g\left(z\right)|\le 8M^2$$

and

$$E{g}^2={\int }_Z{({\pi }_M\left(f\right)\left(x\right)-f_{\rho }\left(x\right))}^2{(({\pi }_M\left(f\right)\left(x\right)-y)+(f_{\rho }\left(x\right)-y))}^{2}d\rho \le 16M^{2}Eg.$$

For $g_1,g_2\in {\mathcal{F}}_{\varrho },$ we have

$$\begin{array}{ccc}\hfill |g_1\left(z\right)-g_2\left(z\right)|& =& \left|{(y-{\pi }_M\left(f_1\right)\left(x\right))}^2-{(y-{\pi }_M\left(f_2\right)\left(x\right))}^2\right|\hfill \\ & \le & 4M\left|{\pi }_M\left(f_1\right)\left(x\right)-{\pi }_M\left(f_2\right)\left(x\right)\right|\hfill \\ & \le & 4M\left|f_1\left(x\right)-f_2\left(x\right)\right|.\hfill \end{array}$$

For any $ϵ>0$, it follows that

$${\mathcal{N}}_{2,z}\left({\mathcal{F}}_r,ϵ\right)\le {\mathcal{N}}_{2,x}\left(B_r,\frac{ϵ}{4M}\right)\le {\mathcal{N}}_{2,x}\left(B_1,\frac{ϵ}{4M\varrho }\right).$$

By Lemma 4, we have

$$log{\mathcal{N}}_2({\mathcal{F}}_{\varrho },ϵ)\le c_p{\left(4M\varrho \right)}^p{ϵ}^{-p},\forall ϵ>0,$$

where $c_p$ is a constant independent of $ϵ$.

Applying Lemma 5 with $B=16M^2,$$\alpha =1$, $c=16M^2,$ and $a=c_p{\left(4M\varrho \right)}^p$, then for any $0<\delta <1$ and any $g\in {\mathcal{F}}_{\varrho }$, the inequality

$$Eg-\frac{1}{m}\sum _{i=1}^{m}g\left(z_i\right)\le \frac{1}{2}Eg+C_1\eta +C_2{M}^2\frac{log(3/\delta )}{m}$$

holds with confidence $1-\frac{\delta }{3}$, where $C_1$ and $C_2$ are constants depending at most on d, X, and the kernel K and

$$\eta =B^{\frac{2-p}{p+2}}{\left(\frac{{\left(4M\varrho \right)}^p}{m}\right)}^{\frac{2}{2+p}}.$$

It follows from the definition of $f_k$ in Algorithm 1 that $\parallel f_k{\parallel }_{{\mathcal{L}}_1}\le k_2{M}^2$. Then, there exists a constant C depending at most on d, X, M, and kernel K, such that

$$S_2(z,k)\le \frac{1}{2}\left\{\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\right\}+Clog\frac{3}{\delta }{m}^{-\frac{2}{p+2}}.$$

   □

4.3. Estimate of Hypothesis Error

In this subsection, we give an error estimate for $\mathcal{P}(\mathbf{z},k)$. For this purpose, we need the following two lemmas.

The first one is Hoeffding inequality, which was established by Wassily Hoeffding in 1963.

Lemma 6

([33]). Let $X_1,\dots ,X_n$ be independent random variables bounded by the interval $[0,1]:$$0\le X_i\le 1$. We define the empirical mean of these variables by

$$\overline{X}=\frac{1}{n}(X_1+\dots +X_n).$$

Then, the following inequality holds for any given $t>0$

$$\mathrm{Prob}(\overline{\mathrm{X}}-\mathrm{E}\left(\overline{\mathrm{X}}\right)\ge \mathrm{t})\le exp(-2{\mathrm{t}}^2\mathrm{n}).$$

When $X_i$ are strictly bounded by the intervals $[a_i,b_i],i=1,\dots ,n$, the generalization of the above inequality holds for any given $t>0$

$$\mathrm{Prob}(\overline{\mathrm{X}}-\mathrm{E}\left(\overline{\mathrm{X}}\right)\ge \mathrm{t})\le exp\left(\frac{-2{\mathrm{t}}^2\mathrm{n}}{{\sum }_{\mathrm{i}=1}^{\mathrm{n}}{({\mathrm{b}}_{\mathrm{i}}-{\mathrm{a}}_{\mathrm{i}})}^2}\right).$$

The second one is an immediate consequence of Theorem 6.

Equip $H=\{f={\sum }_{i=1}^{\infty }{\alpha }_i{K}_{v_i},{\left\{{\alpha }_i\right\}}_{i=1}^{\infty }\subset {\ell }_1,\left\{v_i\right\}\subset X\}$ with the empirical inner product. Then H is a Hilbert space. Given a training data $\mathbf{z}={(x_i,y_i)}_{i=1}^m\subset X\times Y$, ${\mathcal{D}}_m=\{{\widehat{K}}_{x_i}:=\frac{K_{x_i}}{\parallel K_{x_i}{\parallel }_m}\}$ is a dictionary of H. We denote its coherence by $\mathcal{K}.$

Lemma 7.

Let K be a $C^{\gamma }$ kernel with $0<k_1\le K(u,v)\le k_2$. For any $g\in span\left({\mathcal{D}}_m^{{}^{\prime }}\right),$ there exists ${\left\{{\xi }_i\right\}}_{i=1}^m$ such that $g=\sum _{i=1}^m{\xi }_i\frac{K_{x_i}}{\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}}$, $\sum _{i=1}^m|{\xi }_i|<\infty$. We define

$${\parallel g\parallel }_{{\mathcal{L}}_1^m}=inf\left\{\sum _{i=1}^m|{\xi }_i^m|,{\xi }_i^m={\xi }_i\frac{\parallel K_{x_i}{\parallel }_m}{\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}}\right\}.$$

Then, for any $f\in H$ and any $g\in span\left({\mathcal{D}}_m^{{}^{\prime }}\right),$ and $s\le \frac{1}{2\mu }+\frac{3}{2}$, the error of the RPSGLA satisfies

$$\parallel f-f_k{\parallel }_m^2\le {\parallel f-g\parallel }_m^2+\frac{C{(s,\mathcal{K},1)}^2{\parallel g\parallel }_{{\mathcal{L}}_1^m}^2}{sk},k=1,2,\dots .$$

Proof. 

According to (2), for any $f\in H$ and any $g\in \mathrm{span}\left({\mathcal{D}}_m^{{}^{\prime }}\right)\subset {\mathcal{A}}_1\left({\mathcal{D}}_m\right)$, the inequality

$$\parallel f-f_k{\parallel }_m^2\le {\parallel f-g\parallel }_m^2+\frac{C{(s,\mathcal{K},1)}^2}{s(1+k)}{\parallel g\parallel }_{{\mathcal{A}}_1\left({\mathcal{D}}_m\right)}^2$$

(20)

holds for $k=1,2,....$

Given a training data $\mathbf{z}={(x_i,y_i)}_{i=1}^m\subset X\times Y$, since

$$\begin{array}{ccc}\hfill {\parallel g\parallel }_{{\mathcal{A}}_1\left({\mathcal{D}}_m\right)}& =& {∥\sum _{i=1}^m{\xi }_i\frac{K_{x_i}}{\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}}∥}_{{\mathcal{A}}_1\left({\mathcal{D}}_m\right)}\hfill \\ \hfill & =& {∥\sum _{i=1}^m{\xi }_i\frac{\parallel K_{x_i}{\parallel }_m}{\parallel K_{x_i}{\parallel }_{L_{{\rho }_X}^2}}{\widehat{K}}_{x_i}∥}_{{\mathcal{A}}_1\left({\mathcal{D}}_m\right)}\hfill \\ & =& inf\left\{\sum _{i=1}^m|{\xi }_i^m|\right\}={\parallel g\parallel }_{{\mathcal{L}}_1^m},\hfill \end{array}$$

(21)

then, combining (20) with (21), we get the desired result.    □

Proposition 4.

For any $0<\delta <1$, with confidence at least $1-\frac{\delta }{3}$, we have

$${\mathcal{E}}_{\mathbf{z}}\left({\pi }_M\left(f_k\right)\right)-{\mathcal{E}}_{\mathbf{z}}\left(f_k^{*}\right)\le 4min\left\{k_2^2{k}_1^{-2},{\left(1+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}\right)}^2\right\}{\mathcal{B}}^2{\left(sk\right)}^{-1}.$$

Proof. 

Applying Lemma 7 with $g=f_k^{*}$, we have

$$\parallel f-f_k{\parallel }_m^2\le {\parallel f-f_k^{*}\parallel }_m^2+\frac{C{(s,\mathcal{K},1)}^2{\parallel f_k^{*}\parallel }_{{\mathcal{L}}_1^m}^2}{sk}.$$

(22)

Since $\parallel f_k^{*}{\parallel }_{{\mathcal{L}}_1^m}$ changes with training data $\mathbf{z}$, we should find its relation with $\parallel f_k^{*}{\parallel }_{{\mathcal{L}}_1}.$ We know that $\parallel f_k^{*}{\parallel }_{{\mathcal{L}}_1^m}\le \frac{k_2}{k_1}{\parallel f_k^{*}\parallel }_{{\mathcal{L}}_1}.$ We also have that

$$E{\tilde{K}}_{v_i}^2=\left({\int }_Z{\tilde{K}}_{v_i}^{2}d\rho \right)={\parallel {\tilde{K}}_{v_i}\parallel }_{L_{{\rho }_x}^2}^2=1,$$

and

$$\parallel {\tilde{K}}_{v_i}{\parallel }_m={\left(\frac{1}{m}\sum _{i=1}^m{|{\tilde{K}}_{v_i}\left(x_i\right)|}^2\right)}^{\frac{1}{2}}.$$

(23)

Based on Lemma 6, for $t>0$ and any i, we have

$$\mathrm{Prob}\left\{\frac{1}{\mathrm{m}}\sum _{\mathrm{i}=1}^{\mathrm{m}}{|{\tilde{\mathrm{K}}}_{{\mathrm{v}}_{\mathrm{i}}}\left({\mathrm{x}}_{\mathrm{i}}\right)|}^2-\mathrm{E}{\tilde{\mathrm{K}}}_{{\mathrm{v}}_{\mathrm{i}}}^2<\mathrm{t}\right\}\ge 1-exp\left\{-\frac{2{\mathrm{k}}_1^2{\mathrm{t}}^2\mathrm{m}}{{\mathrm{k}}_2^2}\right\}.$$

(24)

By setting $\delta =3exp\left\{-\frac{2k_1^2{t}^{2}m}{k_2^2}\right\}$, we have $t=\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}$. From (23) and (24), with the confidence $1-\frac{\delta }{3}$, we have

$$\begin{array}{ccc}\hfill \parallel {\tilde{K}}_{v_i}{\parallel }_m& \le & \frac{1}{m}\sum _{i=1}^m{|{\tilde{K}}_{v_i}\left(x_i\right)|}^2\le E{\tilde{K}}_{v_i}^2+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}\hfill \\ & \le & 1+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}.\hfill \end{array}$$

By the definition of $f_k^{*}$, we observe that the following inequality

$$\parallel f_k^{*}{\parallel }_{{\mathcal{L}}_1^m}\le \left(1+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}\right){\parallel f_k^{*}\parallel }_{{\mathcal{L}}_1},$$

(25)

holds with the confidence $1-\frac{\delta }{3}.$

Combining (22), (25) with Lemma 3, with the confidence at least $1-\frac{\delta }{3}$, we have

$${\mathcal{E}}_{\mathbf{z}}\left({\pi }_M\left(f_k\right)\right)-{\mathcal{E}}_{\mathbf{z}}\left(f_k^{*}\right)\le C{(s,\mathcal{K},1)}^{2}min\left\{k_2^2{k}_1^{-2},{\left(1+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}\right)}^2\right\}{\mathcal{B}}^2{\left(sk\right)}^{-1}.$$

   □

4.4. Estimate of Approximation Error

Finally, we estimate the approximation error.

Proposition 5.

If $f_{\rho }\in {\mathcal{L}}_1^r$, then $\mathcal{D}\left(k\right)\le {\mathcal{B}}^2{\left(k^{-1/2}+m^{-r}\right)}^2.$

Proof. 

From the definition of $\mathcal{D}\left(k\right)$ and (16), there holds:

$$\mathcal{D}\left(k\right)=\mathcal{E}\left(f_k^{*}\right)-\mathcal{E}\left(f_{\rho }\right)={\parallel f_k^{*}-f_{\rho }\parallel }_{L_{{\rho }_X}^2}^2.$$

For $h_{\rho }$ satisfying (18), and $\parallel h_{\rho }{\parallel }_{L_{{\rho }_X}^2}\le \parallel h_{\rho }\parallel$, from Theorem 2.2 in [16], we obtain

$$\begin{array}{ccc}\hfill \mathcal{D}\left(k\right)& \le & {\left(\parallel h_{\rho }-f_k^{*}{\parallel }_{L_{{\rho }_X}^2}+{\parallel h_{\rho }-f_{\rho }\parallel }_{L_{{\rho }_X}^2}\right)}^2\hfill \\ & \le & {\left(\parallel h_{\rho }-f_k^{*}\parallel +\parallel h_{\rho }-f_{\rho }\parallel \right)}^2\hfill \\ & \le & {\mathcal{B}}^2{\left(k^{-1/2}+m^{-r}\right)}^2.\hfill \end{array}$$

   □

4.5. Proof of Theorem 7

Now we prove Theorem 7.

Proof of Theorem 7 

Assembling the results in Proposition 1–5 together, we have the inequality

$$\begin{array}{ccc}\hfill \mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)& \le & \mathcal{D}\left(k\right)+\mathcal{S}(\mathbf{z},k)+\mathcal{P}(\mathbf{z},k)\hfill \\ & \le & \frac{3}{2}{\mathcal{B}}^2{\left(k^{-1/2}+m^{-r}\right)}^2+\frac{7{(3M+\mathcal{B})}^{2}log(3/\delta )}{3m}\hfill \\ & +& \frac{1}{2}\{\mathcal{E}\left(\pi \left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\}+Clog\frac{3}{\delta }{m}^{-\frac{2}{p+2}}\hfill \\ & +& C(s,\mathcal{K},1)min\left\{k_2^2{k}_1^{-2},{\left(1+\frac{k_2}{k_1}\sqrt{\frac{log(3/\delta )}{2m}}\right)}^2\right\}{\mathcal{B}}^2{\left(sk\right)}^{-1}\hfill \end{array}$$

holds with confidence at least $1-\delta$.

Therefore,

$$\mathcal{E}\left({\pi }_M\left(f_k\right)\right)-\mathcal{E}\left(f_{\rho }\right)\le c{\mathcal{B}}^{2}log\frac{3}{\delta }\left({\left(sk\right)}^{-1}+m^{-2r}+m^{-\frac{2}{p+2}}\right).$$

holds with confidence at least $1-\delta$, where

$$p=\left\{\begin{array}{ccc}\hfill 2d/(d+2\gamma ),& & 0<\gamma \le 1,\hfill \\ \hfill 2d/(d+2),& & 1<\gamma \le 1+d/2,\hfill \\ \hfill d/\gamma ,& & \gamma >1+d/2.\hfill \end{array}\right.$$

This completes the proof of Theorem 7.

   □

5. Simulation Results

In this section, we test the performance of the RPSGLA and present the results of our experiments. We first describe the details relevant to our experiments in Section 5.1. We demonstrate the effectiveness of the RPSGLA in Section 5.2. In Section 5.3, we compare the RPSGLA with existing greedy learning algorithms to show the efficiency and robustness of our algorithm. We also study the effects of the parameter s in Section 5.4.

5.1. Implementation

For all experiments, we uniformly sample 500 data from the objective function

$$\begin{array}{c}\hfill x\mapsto f\left(x\right),x\in [-1,1].\end{array}$$

Let $x_0=-1$ and $\left\{x_i\right\}$ be the 200 equally spaced points in $[-1,1]$, i.e., $x_i=\frac{i-1}{200}$, $0\le i<200$. We use $\{e^{-\parallel x-x_i{\parallel }^2}:i=0,\dots ,199\}$ as a dictionary for the learning algorithms. We also add a Gaussian noise from $\mathcal{N}(0,{\delta }^2)$, with ${\delta }^2=0.2$ for testing the performance. When the matrix is singular during calculating the orthogonal projection, we take the Moore–Penrose pseudoinverse instead of the inverse matrix.

To demonstrate the performance of learning algorithms, we use the mean square error (MSE) to measure the error between objective function f and its approximant $f_{\rho }$ on the unlabeled samples $\mathbf{x}={\left\{{\tilde{x}}_j\right\}}_{j=1}^{500}$, which is defined as follows

$$\begin{array}{c}\hfill \mathrm{MSE}=\frac{1}{500}\sum _{j=1}^{500}{(f\left({\tilde{x}}_j\right)-f_{\rho }\left({\tilde{x}}_j\right))}^2.\end{array}$$

5.2. Effectiveness of the RPSGLA

In the first numerical experiment, we use the uniformly sampled data from the function

$$\begin{array}{c}\hfill x\mapsto x·sin\pi x,x\in [-1,1],\end{array}$$

and set $s=5$.

Figure 1 shows the performance of the RPSGLA ($s=5$) after 100 iterations with noiseless data for the target function $f\left(x\right)=xsin\pi x$, where the blue points represent noiseless samples and the red line represents the approximation. By repeating the test 100 times, we calculate the mean square error: MSE $=3.4159\times {10}^{-4}$.

Figure 2 shows the performance of the RPSGLA ($s=5$) after 100 iterations with Gaussian noise from $\mathcal{N}(0,0.2)$ for the target function $f\left(x\right)=xsin\pi x$, where the blue points represent noisy samples and the red line represents the approximation. By repeating the test 100 times, we calculate the mean square error: MSE $=2.4\times {10}^{-3}$.

The above results show that the RPSGLA is very effective for regression. Although the prediction performance will be affected when noise occurs, our method still has stable effectiveness.

5.3. Comparison with Existing Algorithms

In order to demonstrate the efficiency and robustness of the RPSGLA, we implement the RPGLA (when $s=1$ for RPSGLA) and the Orthogonal Super Greedy Learning Algorithm (OSGLA) based on the WOSGA with the same objective function and parameters as in Section 5.2 for comparison. We first recall the definition of the OSGLA in [13] (Algorithm 2):  

Algorithm 2 The OSGLA

Input:$\mathbf{z}={(x_i,y_i)}_{i=1}^m$, and K, and $T>0$, we get ${\mathcal{D}}_m=\{K_{x_i},i=1,2,...,m\}.$ step 1. Normalization: ${\widehat{K}}_{x_i}=K_{x_i}/{\parallel K_{x_i}\parallel }_m$ and dictionary:${\mathcal{D}}_m^{*}=\{\pm {\widehat{K}}_{x_i}\},i=1,2,...,m.$ step 2. Computation: Let $f_0=0$, $r_k=y-f_k.$ 1: Denote $I_k:=[(k-1)s+1,ks]$. Let ${\phi }_{(k-1)s+1},\dots ,{\phi }_{ks}\in {\mathcal{D}}_m^{*}$ satisfy the inequality $$\underset{i\in I_k}{min}|{\langle r_{k-1},{\phi }_i\rangle }_m|\ge \underset{\phi \in {\mathcal{D}}_m^{*},\phi \ne {\phi }_i,i\in I_k}{sup}|{\langle r_{k-1},\phi \rangle }_m|.$$ 2: Let $H_k=\mathrm{span}\{{\phi }_1,\dots ,{\phi }_{ks}\}$ and $P_{H_k}$ denote the orthogonal projection operator onto $H_k$. Define the next approximant to be $$\begin{array}{c}\hfill f_k=P_{H_k}\left(f\right).\end{array}$$ 3: if $\parallel y-f_k{\parallel }_m^2+\parallel f_k{\parallel }_{{\mathcal{L}}_{\mathbf{z}}}\le {\parallel y\parallel }_m^2$ and $k\ge T$ then break. end Output:${\pi }_M\left(f_k\right)$

By repeating the test 100 times, the mean square error of RPGLA and OSGLA ($s=5$) after 100 iterations with noiseless data and Gaussian noise from $\mathcal{N}(0,0.2)$ are shown in

Table 1. The average MSE (repeating 100 times) of the RPGLA, RPSGLA, and OSGLA obtained on noiseless data and noisy data (Gaussian).

Algorithm	Noiseless Data	Noisy Data (Gaussian)
RPGLA	0.0291	0.0301
OSGLA	$1.1246\times {10}^{-7}$	$3.3\times {10}^{-3}$
RPSGLA	$3.4159\times {10}^{-4}$	$2.4\times {10}^{-3}$

. Additionally, the running time of the RPGLA, OSGLA, and RPSGLA on different types of data are reported in

Table 2. The average running time (repeating 100 times) of the RPGLA, RPSGLA, and OSGLA obtained on noiseless data and noisy data (Gaussian).

Algorithm	Noiseless Data	Noisy Data (Gaussian)
RPGLA	0.1151 s	0.1173 s
OSGLA	2.2322 s	1.5415 s
RPSGLA	0.1105 s	0.1093 s

.

According to the mean square error, obviously, our algorithm is more effective than the RPGLA on both the noiseless data and the noisy data (Gaussian). The performance of the OSGLA on noiseless data outperforms the RPSGLA by a lot. This trend is expected because the approximant of the OSGLA is updated by solving a $s\times k$-dimensional least squares problem at k-th iteration, while for the RPSGLA, it is updated by solving a s-dimensional least squares problem. That is also the reason why the RPSGLA runs much more quickly than the OSGLA as reported in Table 2. However, for the data with Gaussian noise from $\mathcal{N}(0,0.2)$, the performance of the RPSGLA outperforms the OSGLA, showing the robustness and effectiveness of our proposed algorithm.

In Table 2, we compare the running time of the RPGLA, OSGLA, and RPSGLA. We can observe that the RPSGLA runs more quickly than the RPGLA and the existing super algorithm, the OSGLA, demonstrating the efficiency of our algorithm.

5.4. Effects of the Parameter S

In this subsection, we study the effects of the parameter $s\in \{1,2,\dots ,10\}$. We take the same dictionary and Gaussian noise as in Section 5.2. By repeatedly implementing the RPSGLA 100 times on the uniformly sampled data from the function

$$\begin{array}{c}\hfill x\mapsto x^2,x\in [-1,1],\end{array}$$

we calculate the mean square error respectively with $s=1,2,\dots ,10$, which are reported in Figure 3 and Figure 4.

Figure 3 and Figure 4, respectively, show the MSE with noiseless data and Gaussian noise from $\mathcal{N}(0,0.2)$ for the target function $f\left(x\right)=x^2$ when s increases from 1 to 10, which implies that the error of the RPSGLA will decrease with the increased $s\in \{1,2,\dots ,10\}$. For the data with Gaussian noise, according to MSE, the accuracy of the RPSGLA is roughly increased when parameter s increases from 1 to 10. For the noiseless data, the accuracy of the RPSGLA is increased and then decreased, reaching its best when $s=6$.

As shown in Figure 5 and Figure 6, with the increase of the parameter s, the running time of the RPSGLA is decreased and then increased. The running time of the RPSGLA reaches its lowest when $s=2$ (for both noiseless data and the data with Gaussian noise), which implies that our algorithms reach their best computational cost in this case. Although the running time would change with different settings of parameter s, the RPSGLA is fairly efficient overall. In particular, the RPSGLA is more efficient than the RPGLA in general.

6. Discussion

The experiments in Section 5 show the superiority of the RPSGA(s, t) directly. In this section, we will explain why the tested results are achieved. By using the super selection step and one-dimensional optimization together for the first time, we get the simplest good greedy algorithm so far. We provide more details. First, we recall the other three greedy algorithms—the Relaxed Greedy Algorithm (RGA), the Greedy Algorithm with Free Relaxation (GAFR), and the Rescaled Relaxed Greedy Algorithm (RRGA).

In [10], the RGA was defined as the following steps.

RGA(H, $\mathcal{D}$):

• Step 0: Define $f_0=0$.
• Stepm:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$\left|〈f-f_{m-1},{\phi }_m〉\right|=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

For $m=1$, define

$$f_1=\langle f,{\phi }_1\rangle {\phi }_1.$$

For $m\ge 2$, define the next approximant to be

$$f_m=\left(1-\frac{1}{m}\right)f_{m-1}+\frac{1}{m}{\phi }_m,$$

and proceed to Step $m+1$.

In [10], the authors proved that the RGA converged only for the target elements from ${\mathcal{A}}_1\left(\mathcal{D}\right)$ and derived the following convergence rate for the RGA.

Theorem 8.

Let $\mathcal{D}$ be an arbitrary dictionary in H. Then, for each $f\in {\mathcal{A}}_1\left(\mathcal{D}\right),$ we take the approximant as $f_m=\left(1-\frac{1}{m}\right)f_{m-1}+\frac{{\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}}{m}{\phi }_m,m\ge 2$ the RGA has the following convergence rate

$$∥f-f_m∥\le 2{\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-1/2},m=0,1,2,\dots .$$

In [9], the GAFR was defined as follows:

GAFR(H, $\mathcal{D})$:

• Step 0: Define $f_0=0$.
• Stepm:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$\left|〈f-f_{m-1},{\phi }_m〉\right|=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

With $({\omega }_m,{\theta }_m)=arg{min}_{(\omega ,\theta )\in R^2}\parallel f-\omega f_{m-1}-\theta {\phi }_m\parallel ,$ define the next approximant to be

$$f_m={\omega }_m{f}_{m-1}+{\theta }_m{\phi }_m,$$

and proceed to Step $m+1$.

In [9], the RRGA was defined as follows:

RRGA(H, $\mathcal{D})$:

Step 0: Define $f_0=0$.

Step m:

-

If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

-

If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$$|\langle f-f_{m-1},{\phi }_m\rangle |=\underset{\phi \in \mathcal{D}}{sup}|\langle f-f_{m-1},\phi \rangle |.$$

With

$${\lambda }_m=arg\underset{\theta \in R}{min}\parallel f-f_{m-1}-{\theta }_m\parallel ,{\omega }_m=arg\underset{\omega \in R}{min}\parallel f-\omega (f_{m-1}+{\theta }_m{\phi }_m)\parallel ,$$

define the next approximant to be $f_m={\omega }_m(f_{m-1}+{\theta }_m{\phi }_m),$ and proceed to Step $m+1$.

In [9], the authors derived the following convergence rate for the GAFR and RRGA.

Theorem 9.

Let $\mathcal{D}$ be an arbitrary dictionary in H. Then, for each $f\in {\mathcal{A}}_1\left(\mathcal{D}\right),$ the GAFR and RRGA have the following convergence rate

$$∥f-f_m∥\le C{\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-1/2},m=0,1,2,\dots .$$

From Theorems 2–4, Corollary 1, and Theorems 8 and 9, for each $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, the OGA, RPGA, RGA, GAFR, RRGA, OSGA(s, t), and RPSGA(s, t) all have the following convergence rate

$$\parallel f-f_m{\parallel \le C\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-1/2}.$$

The rate is optimal and the results show that these algorithms have almost identical error performances. We call these types of greedy algorithms Good Greedy Algorithms (GGA). Therefore, we just compare the complexity and execution time of the GGA.

In terms of scope of application, the RGA converges only for the target elements from ${\mathcal{A}}_1\left(\mathcal{D}\right)$. Obviously, the RPSGA(s, t) is better than the RGA.

From the viewpoint of complexity, the OGA has to solve a m-dimensional optimization problem

$$f_m=P_{\{{\phi }_1,\dots ,{\phi }_m\}}f=\sum _{k=1}^m{\theta }_k^m{\phi }_k,$$

where $({\theta }_1^m,\dots ,{\theta }_m^m)=arg{min}_{({\theta }_1,\dots ,{\theta }_m)\in R^m}\parallel f-{\sum }_{k=1}^m{\theta }_k{\phi }_k\parallel .$ The GAFR has to solve a two-dimensional optimization problem

$$f_m={\omega }_m{f}_{m-1}+{\theta }_m{\phi }_m,$$

where $({\omega }_m,{\theta }_m)=arg{min}_{(\omega ,\theta )\in R^2}\parallel f-(\omega f_{m-1}+\theta {\phi }_m)\parallel .$ The RRGA employs two one-dimensional optimization problems

$$f_m={\omega }_m(f_{m-1}+{\theta }_m{\phi }_m),$$

where ${\theta }_m=arg{min}_{\theta \in R}\parallel f-(f_{m-1}+\theta {\phi }_m)\parallel$, ${\omega }_m=arg{min}_{\omega \in R}\parallel f-\omega (f_{m-1}+{\theta }_m{\phi }_m)\parallel .$ However, the RPGA only needs to solve a one-dimensional optimization problem

$$f_m=s_m{\widehat{f}}_m,\mathrm{where}{\mathrm{s}}_{\mathrm{m}}=arg\underset{\mathrm{s}\in \mathrm{R}}{min}\parallel \mathrm{f}-\mathrm{s}{\widehat{\mathrm{f}}}_{\mathrm{m}}\parallel .$$

Then, the RPGA is simpler than the OGA, RGA, GAFR, and RRGA. So the RPGA can save much execution time. According to the definition, the RPSGA(s, t) selects more than one element from a dictionary in each iteration step and hence reduces the computational burden of the RPGA (taking s=1 in the RPSGA(s, t)), especially when the RPGA and RPSGA(s, t) run with noisy data, see Figure 6. Combining with the empirical test results in Table 1 and Table 2 in Section 5, it can be easily found that from the viewpoints of error performance and execution time, the RPSGA(s, t) is more effective than the RPGA. The commonly used super algorithm is only the OSGA(s, t), as far as we know, and the OSGA(s, t) always needs to solve an $ms$-dimensional optimization problem. While the RPSGA(s, t) only need to solve a s-dimensional optimization problem and an one-dimensional optimization problem. Table 2 also shows the robustness and effectiveness of the RPSGA(s, t) compared with the OSGA(s, t). Therefore, the efficiency of the RPSGA(s, t) is the best among the GGA.

7. Conclusions and Further Studies

We propose a new type of super greedy algorithm—the WRPSGA. The RPSGA(s, t) is simpler than the OGA, RGA, RRGA, RPGA, and OSGA(s, t) from the viewpoint of computational complexity. The convergence rate of RPSGA(s, t) on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is optimal. Based on this result, we design the RPSGLA for solving kernel-based regression problems in supervised learning. When the kernel is infinitely smooth, we derive a significantly faster learning rate that can be arbitrarily close to the best rate $O(m^{-1})$ under some mild assumptions of the regression function. The efficiency of the RPSGLA is better than some existing greedy learning algorithms. For instance, the convergence rate of the RPSGLA is faster than the OSGLA in [13], RGLA in [20], and the OGLA and RGLA in [16]. Additionally, our convergence rate is almost the same as that of the OGLA in [18]. However, the complexity of the RPSGLA is smaller than the OGLA. We test the performance of the RPSGLA by numerical experiments. Our simulation results show that the RPSGLA is very efficient for regression.

In addition to the applications in machine learning, the greedy algorithms can also be used to solve convex optimization problems which are quite different from the approximation problems, see Refs. [23,34,35,36]. We formulate the problem of convex optimization as follows.

Let H be a Hilbert space with an inner product $\langle ·,·\rangle$, and E be a convex function on H which is called the objective function. We assume that E has a Fréchet derivative $E^{{}^{\prime }}\left(x\right)\in H$ at each point $x\in H$, that is

$$\underset{h\to 0}{lim}{\displaystyle \frac{|E(x+h)-E\left(x\right)-\langle E^{\prime }\left(x\right),h\rangle |}{\parallel h\parallel }}=0,$$

where $\parallel ·\parallel$ is the norm induced by $\langle ·,·\rangle$. We want to find an approximate solution to the problem

$$\underset{x\in \mathrm{\Omega }}{inf}E\left(x\right),$$

(26)

where $\mathrm{\Omega }$ is a bounded convex subset of H.

For a dictionary $\mathcal{D}$ of H, we denote ${\Sigma }_m\left(\mathcal{D}\right)$ as the set of all at most m-term linear combinations with respect to $\mathcal{D},$

$${\Sigma }_m:={\Sigma }_m\left(\mathcal{D}\right)=\{g:g=\sum _{i\in \mathrm{\Lambda }}{c}_i{g}_i,g_i\in \mathcal{D},\mathrm{\Lambda }\subset \mathbb{N},\#(\mathrm{\Lambda })\le m\}.$$

Let $\overline{x}=arg{inf}_{x\in \mathrm{\Omega }}E\left(x\right).$ We will develop a new greedy algorithm to produce an approximation $x_m\in {\Sigma }_m\left(\mathcal{D}\right)$ of $\overline{x}$. This algorithm is a modification of the RPSGA. We denote it as the RPSGA(co). We present the definition of the RPSGA(co) as follows:

RPSGA(co):

• Step 0: Define $x_0=0$. If $E^{{}^{\prime }}\left(x_0\right)=0$, stop the algorithm and define $x_k:=x_0,k\ge 1$.
• Step m: Assume that $x_{m-1}$ has been defined and $E^{{}^{\prime }}\left(x_{m-1}\right)\ne 0$. Denote $I_m:=$

$\left[\right(m-1)s+1,ms]$. Let ${\phi }_{(m-1)s+1},\dots ,{\phi }_{ms}\in \mathcal{D}$ satisfy the inequality

$$\underset{i\in I_m}{min}|\langle E^{{}^{\prime }}\left(x_{m-1}\right),{\phi }_m\rangle |\ge \underset{\phi \in \mathcal{D},\phi \ne {\phi }_i,i\in I_m}{sup}|\langle E^{{}^{\prime }}\left(x_{m-1}\right),\phi \rangle |.$$

Let $F_m:=\mathrm{span}({\phi }_{(m-1)s+1},\dots ,{\phi }_{ms})$. With

$${\widehat{x}}_m:=x_{m-1}+arg\underset{x\in F_m}{min}{E}^{{}^{\prime }}\left(x\right)$$

define the next approximant to be $x_m=s_m{\widehat{x}}_m,$ where $s_m=\frac{\langle x,{\widehat{x}}_m\rangle }{\langle {\widehat{x}}_m,{\widehat{x}}_m\rangle }.$

If $E\left(x_m\right)=0$, then stop the algorithm and define $x_k=x_m,k>m$, otherwise go to Step $m+1$.

We will impose the following assumptions on the objective function E.

Condition 0: E has a Fréchet derivative $E^{{}^{\prime }}\left(x\right)\in H$ at each point x in $\mathrm{\Omega }$ and

$$\parallel E^{{}^{\prime }}\left(x\right)\parallel \le M_0,x\in \mathrm{\Omega }.$$

Uniform Smoothness: There are constants $\beta >0$, $1<q\le 2$, and $U>0$, such that for all x, $x^{{}^{\prime }}$ with $\parallel x-x^{{}^{\prime }}\parallel \le U$, x in $\mathrm{\Omega }$,

$$E\left(x^{{}^{\prime }}\right)-E\left(x\right)-\langle E^{{}^{\prime }}\left(x\right),x-x^{{}^{\prime }}\rangle \le \beta {\parallel x-x^{{}^{\prime }}\parallel }^q.$$

It is known from [23] that the OGA(co) can be used effectively to solve convex optimization problems. Since the RPSGA(s, t) is more efficient than the OGA, the RPSGA(co) can solve these problems more efficiently. For the RPSGA(co), by estimating the decay of $E\left(x_m\right)-E\left(\overline{x}\right)$ as $m\to \infty$, we will obtain the convergence rate $O\left(m^{1-q}\right)$, which is independent of the dimension of the underlying space H. So, the curse of dimensionality for problem (26) can be overcome by using the RPSGA(co). This work will be of great interest in practical applications. It is also important to compare the efficiency of the RPSGA(co) with other greedy optimization algorithms in future work.