Learning capability of the rescaled pure greedy algorithm with non-iid sampling

1.   Introduction and assumptions

Greedy learning algorithms, or more specifically, applying greedy algorithms to tackle supervised learning problems, have triggered enormous recent research activities since they possess the lower computational burden^[1,2,3,4]. {Theoretical attempts of greedy learning have been widely concerned recently in the framework of learning theory ^[1,2,3,5,6]. We consider the learning capability of the rescaled pure greedy algorithm (RPGA) in a non-i.i.d sampling setting, which was initiated by Petrova in ^[7].

A fast review of regression learning as well as greedy algorithms will be given as follows, respectively. Let $X$ be a compact metric space and $Y = \mathbb{R}$. Let ${\bf z} = \{z_{i}\}_{i = 1}^{n} = \{(x_i, \, y_i)\}_{i = 1}^n \in Z^n$ be a stationary real-valued sequence with unknown Borel probability distribution $\rho$ on $Z = X\times Y$.

The generalization error can be defined by

Minimizing $\mathcal {E}(f)$, we can obtain the following regression function

where $\rho(\cdot\vert x)$ denotes the conditional probability measure (given $x$) on $Y$. The empirical error $\mathcal {E}_{{\bf z}}(f)$ which is a good approximation of the generalization error $\mathcal {E}(f)$ for a fixed function $f$ on $X$ can be defined by

The regression problem in learning theory aims at a good approximation $f_{{\bf z} }$ of $f_{\rho}$, constructed by learning algorithms. Denote by $L_{\rho_X} ^2(X)$ the Hilbert space of the square integrable functions defined on $X$ with respect to the measure $\rho_X$, where $\rho_{X}$ denotes the marginal probability distribution on $X$ and $\|f(\cdot)\|_{\rho_{X}} = (\int_{X}\vert f(\cdot)\vert^{2}d{\rho_{X}})^{\frac{1}{2}}$. It is known that, for any $f\in L_{\rho_X} ^2(X)$, it holds that

where

The learning ability of the regression algorithm can be measured by the excess generalization error

Let $\mathcal {H}$ be a real, separable Hilbert space endowed with inner product $\langle\cdot, \cdot\rangle$ and norm $\|\cdot\|: = \|\cdot\|_{\mathcal {H}} = \langle\cdot, \cdot\rangle^{\frac{1}{2}}$. A set of functions $\mathcal {D}\subset\mathcal {H}$ is called a dictionary if $\|g\| = 1$ for every $g\in\mathcal {D}$, $g\in\mathcal {D}$ implies $-g\in\mathcal {D}$ and the closure of $span(\mathcal {D})$ is $\mathcal {H}$. We define the RPGA($\mathcal {D}$) as follows:

$\bf{RPGA(\mathcal {D})}$:

Step 0: Define $f_0 : = 0$.

Step $m$ ($m \geq 1$):

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

(2) If $f\neq f_{m-1}$, choose a direction $\varphi_{m}\in D$ such that

With

define the next approximant to be

and proceed to Step $m+1$.

Note that the RPGA uses the just appropriate scaling of the output of the pure greedy algorithm (PGA) which can boost convergence rate of the PGA to the optimal approximation rate $\mathcal {O}(m^{-\frac{1}{2}})$ for functions in $\mathcal {A}_{1}(\mathcal {D})$, see ^[7].

Throughout this paper, we derive the error bounds under the assumption that $\vert y\vert\leq M$ almost surely for $M\geq0$, hence $\vert f_{\rho}(x)\vert\leq M$ for any $x\in X$. We also define the following truncation function as in ^[8,9,10].

Definition 1. Fix $M > 0$, we define the truncation function $\pi_{M}$ on the space of the measurable functions $f:X\rightarrow \mathbb{R}$ as

Now we use the RPGA to realize the greedy learning. Here we consider leaning by the indefinite kernel $K: X\times X\longrightarrow\mathbb{R}$ ^{[11,12,13,14]} and define the following hypothesis space by

where

We now present the rescaled pure greedy learning algorithm (RPGLA) as follows:

Many greedy learning schemes were recently successfully used for the i.i.d. sampling^{[1,2,3,4,5,6,15]}. For example, Barron et al. ^[5] have used a complexity regularization principle as the stopping criterion and deduced the best learning rate $\mathcal {O}\big(n/\log n)^{-\frac{1}{2}}\big)$ of various greedy algorithms. Lin et al.^[3] have provided the learning capability of the relaxed greedy learning algorithm (RGLA) and proved that the learning rate is faster than the order $\mathcal {O}(n^{-\frac{1}{2}})$. Their numerous numerical simulation results have confirmed that the relax greedy algorithm (RGA) is more stable in dealing with noisy machine learning problems than the orthogonal greedy algorithm (OGA). Chen et al. ^[16] have introduced a sparse semi-supervised method to learn the regression functions from samples using the OGA. They can derive the learning rate $\mathcal {O}(n^{-1})$ under mild assumptions. To reduce the computational burden of the OGA, Fang et al. ^[1] have considered the applications of the orthogonal super greedy algorithm (OSGA) which selects more than one atoms from a dictionary in each iteration in supervise learning and deduced an almost same learning rate as that of the orthogonal greedy learning algorithm (OGLA) in ^[5]. Different from the traditional variants RGA and OGA, Xu et al.^[4] proposed the truncated greedy algorithm (TGA) which truncates the step size of the PGA at a specified value in each greedy iteration to cut down the model complexity. They also proved that for some specified learning tasks, the truncated greedy learning algorithm (TGLA) can remove the logarithmic factor in the learning rates of the OGLA and the RGLA. All these results show that in the realm of supervised learning, each greedy algorithm possesses its own pros and cons. For instance, compared with the OGA, the PGA and the RGA have benefits in computation but suffer from the low convergence rate. In this paper, we study the learning capability of the RPGA which is the very simple modified version of the PGA. Motivated by the researches of ^[7], we proceed to deduce the error bound of the RPGLA. Our results will show that the RPGLA furthermore reduce the computational burden without sacrificing the generalization capability when compared with the OGLA and the RGLA. However, usually the independent and identity assumption is rather restrictive. For example, in ^[17,18,19], the authors presented the non-i.i.d. sampling setting for different learning algorithms, respectively. We shall study $\beta$-mixing and non-identical sampling, see ^[20] and the references therein for the details.

Definition 2. Let ${\bf{z}} = \{z_t\}_{t\geq 1}$ be a sequence of random variables. For any $i, j\in\mathbb{N}\cup\{+\infty\}$, $\sigma_{i}^{j}$ denotes the $\sigma$-algebra generated by the random variables $\{z_t = (x_t, \, y_t)\}_{t = i}^j$. Then for any $l\in\mathbb{N}$, the $\beta$-mixing coefficients of the stochastic process ${\bf z}$ are defined as

$\bf{z}$ is said to be $\beta$-mixing, if $\beta(l)\rightarrow0$ as $l\rightarrow \infty$. Specifically, it is said to be polynomially $\beta$-mixing, if there exists some $\beta_{0} > 0$ and $\gamma > 0$ such that, for all $l\geq1$,

The $\beta$-mixing condition is "just the right" assumption, which has been adopted in previous studies for learning with weakly dependent samples, see ^[18,21] and the references therein. It is quite easy to establish and covers a more general non-i.i.d. cases such as Gaussian and Markov processes. Markov chains appear so often and naturally in applications, especially in marking prediction, biological speech recognition, sequence analysis, content-based web search and character recognition.

We assume that $\{z_{i}\}_{i = 1}^{n}$ is drawn according to the Borel probability measures $\{\rho^{(i)}\}_{i = 1, 2, \cdot\cdot\cdot}$ on $Z$. Let $\rho_{X}^{(i)}$ be the marginal distribution of $\rho^{(i)}$. For every $x \in X$, the conditional distribution of $\{\rho^{(i)}\}_{i = 1, 2, \cdot\cdot\cdot}$ at $x$ is $\rho(\cdot\vert x)$.

Definition 3. We say that $\big\{\rho_{X}^{(i)}\big\}$ converges to $\rho_{X}$ exponentially in $(C^{s}(X))^{\ast}$, if for $C > 0$ and $0 < \alpha < 1$,

The above condition (1.14) is also equivalent to

where

and

Before giving our key analysis, we firstly need to impose some mild assumptions concerning $K$, $\mathcal {H}_{K, \, {\bf z}}$ and $\{\rho(y\vert x): x\in X\}$ below.

The kernel function $K$ is said to satisfy a Lipschitz condition of order $(\alpha, \beta)$ with $0 < \alpha$, $\beta\leq1$, if for some $C_{\alpha}, C_{\beta} > 0$,

Let $R > 0$ and $B_{R}$ be the ball of $\mathcal {H}_{K, \, {\bf z}}$ with radius $R$:

As ^[22], we give the complexity assumption of the unit ball $B_{1}$.

Capacity assumption. We say that $B_{1}$ has polynomial complexity exponent $0 < p < 2$ if there is some constant $c_{p} > 0$ such that

The following concept describes the continuity of $\{\rho(y\vert x):x\in X\}$.

Definition 4. We say that $\{\rho(y\vert x): x\in X\}$ satisfies a Lipschitz condition of order $s$ in $(C_{s}(Y))^{\ast}$ if there is some constant $C_{\rho}\geq0$ such that

Throughout this paper, we denote $\kappa^2 = \sup_{t, x\in X} \vert K(x, t)\vert$. Since all the constants are independent of $\delta$, $n$ or $\lambda$, for simplicity of notation, we denote by $C$ all the constants.

The rest of this paper is organized as follows: in Section 2, we will state the error decomposition of the algorithm (1) and the rate of uniform convergence. In the forthcoming Sections 3–5, we will analyze the drift error, the sample error and the hypothesis error. Finally, we conclude the main results in Section 6.

2.   Error decomposition and main results

We use the developed technique for coefficient regularization algorithms for the non-i.i.d. sampling ^[19,21] to analyze the learning ability of the algorithm (1). We first define the following function space

with the norm

We define the regularizing function

In order to describe the error caused by the change of $\{\rho_{X}^{(i)}\}$, we introduce

Now we can give the error decomposition for the algorithm (1).

where

The drift error $\mathcal {P}(\lambda)$ describes the change of $\rho^{(i)}$ from $\rho$, and the sample error $\mathcal {S}({\bf z}, \lambda)$ connects the estimator $\pi_{M}(\widetilde{f}_{k})$ with $f_{\lambda}$. $\mathcal {H}({\bf z}, \lambda)$ and $\mathcal {D}(\lambda)$ are known as the hypothesis error and the approximation error, respectively.

To compared with the main results in ^[16], we shall assume $\mathcal {D}(\lambda)$ satisfies the same decay rate as follows

for some exponent $0 < q\leq1$ and a constant $c_{q} > 0$.

Next we can state the generalization error bound and give the proofs in Sections 3–6.

Theorem 1. Assume $z_i = (x_i, y_i)_{i = 1}^{n}$ satisfy condition (1.13), the hypothesis space $\mathcal {H}_{K, \, {\bf z}}$ satisfies the capacity assumption (1.21) with $0 < p < 2$, the kernel $K$ satisfies a Lipschitz condition of order $(\alpha, \beta)$ with $0 < k_{0}\leq K(u, v)\leq k_{1}$ for any $u, v\in X$, the target function $f_{\rho}$ can be approximated with the exponent $0 < q\leq1$ in $\mathcal {H}_{1}$, (1.14) for $\rho_{X}$ and (1.22) for $\rho(y\vert x)$ hold. Take $k\geq T\geq n$. Then for any $0 < \delta < 1$, with confidence $1-\delta$, we have

where $t = \log\Big(\frac{6}{\delta-6b_{n}\beta(a_{n})}\Big)$ with $b_{n}$ and $a_{n}$ given explicitly later.

Theorem 2. Under the assumptions of Theorem 1, if

then we obtain

where

Let $\alpha = 0$ and $\zeta = 1$. Then we obtain the following learning rate of the i.i.d. sampling

which is the same as that in ^[16]. In particular, as $p\rightarrow0$, $\frac{2}{2+p}\rightarrow1$ which is the optimal convergence rate.

3.   Estimates for the drift error

Proposition 3. Under the assumptions of Theorem 1, the inequality

holds.

Proof. By (1.1) and (2.4), we get

Now (1.15) tells us that

where the last inequality holds true since $\|fg\|_{C^{s}(X)}\leq\|f\|_{C(X)}\|g\|_{C^{s}(X)}+\|f\|_{C^{s}(X)}\|g\|_{C(X)}$, see ^[19].

In the following, we estimate $\|f_{\lambda}\|_{\infty}$, $\vert f_{\lambda}\vert_{C^{s}(X)}$, $\vert \widetilde{f}_{k}\vert_{C^{s}(X)}$ and $\vert f_{\rho}\vert_{C^{s}(X)}$ separately. Let $f_{\lambda}(x) = \sum_{j = 1}^{\infty}\alpha_{j, \lambda}\overline{K}_{u_{j}}(x)$, $\{\alpha_{j, \lambda}\}\in l_{1}$. It follows that

Furthermore,

The Lipschitz condition (1.18) of the kernel function $K$ yields for any $f\in \mathcal {H}_{1}$ that

Together with (1.17), this implies that

In the same way, from the definition of $\widetilde{f}_{k}$, we have

In addition, combining (1.17) with (1.22) gives

Plugging (3.5), (3.6), (3.7) and (3.8) into (3.3), the desired estimate (3.1) follows, and the proposition is proved.

4.   Estimates for the sample error

In our analysis, we apply the method in ^[18,23] to deal with the original weakly dependent sequence. Let $(a_{n}, b_{n})$ be any integer pair with $b_{n} = [n/2a_{n}]$. The dependent observations are split into $2b_{n}$ blocks, each of size $a_{n}$. For $1\leq k\leq2b_{n}$, $Q^{a_{n}}_{k}$ denotes the marginal distribution of block $(z_{(k-1)a_{n}+1}, z_{(k-1)a_{n}+2}, \cdot\cdot\cdot, z_{ka_{n}})$. With the constructed blocks, one can then take a new sequence $(z'_{1}, \cdot\cdot\cdot, z'_{2b_{n}a_{n}})$ with product distribution $\prod_{k = 1}^{2b_{n}}Q_{k}^{a_{n}}$. We further define

and correspondingly

The sample error $\mathcal {S}({\bf z}, \lambda)$ can be rewritten as

We analyze the term $\mathcal {S}_{1}({\bf z}, \lambda)$ by using the following inequality from ^[18].

Lemma 4.1. If $g$ is a measurable function on $Z$ satisfying $\big\|g(z)-\int_{Z}gd\rho^{(i)}\big\|_{\infty}\leq M$, then for any $\delta > 0$, with confidence $1-\delta$, there holds

Proposition 4. Under the assumptions of Theorem 1, for any $0 < \delta < 1$, with confidence $1-\delta/3$,

Proof. Let $g(z) = (y-f_{\lambda}(u))^{2}-(y-f_{\rho}(u))^{2}$, $z = (u, y)\in Z$. Thus

and

Using Lemma 4.1, with confidence $1-\delta/3$, we have

Observe that

By (1.15), we have

where the last inequality follows from (3.6) and (3.8).

Combining (4.2), (4.3) and (4.4), we get the desired error bound (4.1) of $\mathcal {S}_{1}({\bf z}, \lambda)$. Proposition 4 is proved.

We continue to analyze $\mathcal {S}_{2}({\bf z}, k)$ by applying the following probability inequality for the $\beta$-mixing sequences from ^[18].

Lemma 4.2. Let $\mathscr{G}$ be a class of measurable functions on $Z$. Moreover, assume that $\big\|g-\int_{Z}gd ^{(i)}\big\|_{\infty}\leq M$ for all $g\in\mathscr{G}$. Then

where

To get the upper bounds of the terms $\prod_{1}$ and $\prod_{2}$, we need to invoke the following inequality for the non-identical sequence of probability distributions.

Proposition 5. Assume $\{X_{i}\}_{i = 1}^{n}$ is a random sequence in the measurable space $\big(\mathfrak{X}^{n}, \prod_{i = 1}^{n}Q_{i}\big)$. Let $\mathscr{F}$ be a set of measurable functions on $\mathfrak{X}$ and $B > 0$ be a constant such that each $f\in\mathscr{F}$ satisfies $\|f\|_{\infty}\leq B$. Suppose there exists a nonnegative functional $w$ on $\mathscr{F}$ and some positive constants $(\Delta_{i})_{i = 1}^{n}$ such that

Also assume for some $a > 0$ and $p\in(0, 2)$,

Then for any $x > 0$ and any $D > 0$, with probability at least $1-e^{-x}$ there holds

where $c_{p}'$ is a constant depending only on $p$ and

The above inequalities imply the estimate of $\mathcal {S}_{2}({\bf z}, k)$.

Proposition 6. Under the assumptions of Theorem 1, for any $0 < \delta < 1$, with confidence $1-\delta/3$,

where

Proof. Define the function set $\widetilde{\mathscr{G}}$ on $Z^{a_{n}}$ by

and

It follows that

We see from (1.15) and (1.22) that

By (4.8) and (4.9), we know that $\Delta_{k}$ in (4.5) satisfies

Let $w = \{\vec{t_{j}} = (t_{1}^{j}, \cdot\cdot\cdot, t_{a_{n}}^{j})\}_{j = 1}^{d}\subset(Z^{a^{}_{n}})^{d}$, $d\in\mathbb{N}$. We know that for any functions $G_{1} = \frac{2b_{n}}{n}\sum_{k = 1}^{a_{n}}g_{1}(t_{k})$ and $G_{2} = \frac{2b_{n}}{n}\sum_{k = 1}^{a_{n}}g_{2}(t_{k})$ in $\widetilde{\mathscr{G}}$,

so

Moreover,

This together with (4.10) yields

Note that $\|G\|_{\infty}\leq\|g\|_{\infty}\leq8M^{2}$. It is also easy to see that

and

Now applying Proposition 5 to $\widetilde{\mathscr{G}}$ in $\big((Z^{a_{n}})^{b_{n}}, \prod_{j = 1}^{b_{n}}Q_{2j-1}^{a_{n}}\big)$. Let $B = 8M^{2}$ and $a = c_{p}(4M)^{p}R^{p}$. Then for any $D > 0$, $g\in\mathscr{G}$, with confidence at least $1-e^{-t}$, we have

Here

It follows by taking $\epsilon_{1} = c_{p}'\eta_{1}+\frac{(D+144M^{2}+2)t}{b_{n}}$ that

Applying Proposition 5 to $\widetilde{\mathscr{G}}$ in $\big((Z^{a_{n}})^{b_{n}}, \prod_{j = 1}^{b_{n}}Q_{2j-1}^{a_{n}}\big)$ once again, we have

Here $\epsilon_{2} = c_{p}'\eta_{2}+\frac{(D+144M^{2}+2)t}{b_{n}}$ with

Moreover, we obviously have

and

We know from Lemma 4.2 by taking $\varepsilon = c_{p}'\tilde{\eta}+\frac{(D+144M^{2}+2)t}{b_{n}}$ with

then

Then we obtain (4.6) by taking $2e^{-t}+2b_{n}\beta(a_{n}): = \frac{\delta}{3}$ and $D = 32M^{2}$.

5.   Estimates for the hypothesis error

Different from the widely regularized method with data-dependent hypothesis spaces ^[8,10,21,22], our estimation for the hypothesis error $\mathcal {E}_{{\bf z}}(\pi_{M}(\widetilde{f}_{k})) -\mathcal {E}_{{\bf z}}(f_{\lambda})$ is based on the following lemma, see Theorem 3.3 in ^[7].

Lemma 5.1. If $f\in\mathcal {H}$, $h\in\mathcal {H}_{1}^{n}$, then the output $(f_{m})_{m\geq0}$ of the RPGA satisfies the inequality

where

with

Proposition 7. Under the assumptions of Theorem 1, for $k\geq T$ and any $0 < \delta < 1$, with the confidence at least $1-\delta/3$, there holds

Proof. By Lemma 5.1, we have

From the definitions of $\|f\|_{\mathcal {H}_{1}^{n}}$ and $\|f\|_{\mathcal {H}_{1}}$, we have

Meanwhile, we define the function $g(x) = \vert\overline{K}_{u_{i}}(x)\vert^{2}$, for any $i$. Notice that

and

Using Lemma 4.1, with confidence $1-\delta/3$, we have

By (1.17) and (1.15), we get

This in connection with (5.7) tells us that

It is easy to see that $\|\overline{K}_{u_{j}}\|_{\rho_{X}}^{2} = E\overline{K}_{u_{j}}^{2} = 1$. Now (5.9) implies that

Therefore,

Combining (5.5), (5.6), (5.11), we obtain (5.4).

6.   Proofs of main results

Proof of Theorem 1. Combining the bounds (2.7), (3.1), (4.1), (4.6) and (5.4), with confidence at least $1-\delta$,

Note that $k\geq T\geq n$. By taking $R = M^{2}$, then

This finishes the proof of Theorem 1.

Proof of Theorem 2. Under the conditions of Theorem 1, let $n^{1-\zeta}\leq a_{n} < n^{1-\zeta}+1$, $\zeta\in[0, 1]$ and $n\geq8^{\frac{1}{\zeta}}$. Then

Substitute (6.3) into (6.2), we obtain

By setting $\lambda = n^{-\theta}$, we know that

where

To balance the errors in (2.5), we take $\theta = \frac{\zeta}{2-q}$. Then

Finally, we choose

it follows from $\beta(a_{n})\leq\beta_{0}(a_{n})^{-\gamma}$ and $a_{n}\geq n^{1-\zeta}$ that

thus

This finishes the proof of Theorem 2.

Acknowledgments

This research is supported by the National Science Foundation for Young Scientists of China (Grant No. 12001328), Doctoral Research Fund of Shandong Jianzhu University (No. XNBS1942), the Development Plan of Youth Innovation Team of University in Shandong Province (No. 2021KJ067) and Shandong Provincial Natural Science Foundation of China (Grant No. ZR2022MF223). All authors contributed substantially to this paper, participated in drafting and checking the manuscript. All authors read and approved the final manuscript.

Conflict of interest

The authors declare that they have no competing of interests regarding the publication of this paper.