Convergence of online learning algorithm with a parameterized loss

1.   Introduction

Let $X\subset\mathbf{R}^{d}$ be the input space, $Y = [-M, M]$ be the output space for some $M > 0$. $z = \{(x_{t}, y_{t})\}_{t = 1}^{T}$ are the random samples i.i.d. (independently and identically drawn) according to a Borel probability measure $\rho(x, y) = \rho(y|x)\rho_X(x)$ on $Z = X\times Y$. Based on these samples, the goal of regression problems is to look for a predictor $f: X\rightarrow \mathbf{R}$ from some hypothesis space such that $f(x)$ is a "good" approximation of $y$. The quality of the predictor $f$ is measured by the generalization error

where $V(r):\mathbf{R}\rightarrow \mathbf{R}_{+}$ is a prescribed loss function.

The hypothesis space considered in this paper is the reproducing kernel Hilbert space(RKHS) $\mathcal{H}_{K}$. This means that there exists a unique symmetric and positive definite continuous function $K: X\times X\rightarrow \mathbf{R}$, called the reproducing kernel of $\mathcal{H}_{K}$, or Mercer kernel, and an inner product $\langle\cdot, \cdot\rangle_{K}$ such that $f(x) = \langle K(x, \cdot), f\rangle _{K}$ which is the reproducing property of the kernel, and all $f\in\mathcal{H}_{K}$ are linear combinations of kernel functions. In other words, the RKHS $\mathcal{H}_{K}$ is the closure of the linear span of the set of functions $\{K_{x}(\cdot) = K(x, \cdot): x\in X\}$ with the inner product $\langle\cdot, \cdot\rangle_{K}$. For each $x\in X$ and $f\in \mathcal{H}_{K}$ the evaluation functional $e_{x}(f): = f(x)$ is continuous (i.e.bounded) in the topology of $\mathcal{H}_{K}$, and $|f(x)|\leq \kappa\Vert f\Vert _{K}$ with $\kappa: = \sup\limits_{x\in X}\sqrt{K(x, x)}$ (see ^[1]).

Traditional off-line learning is also called batch learning, all sample points need to be tested in each training. When the amount of data is large or new sample points are added, the learning ability of batch learning decreases significantly. Online learning is one effective approach raised for analyzing and processing big data in various applications, such as communication, electronics, medicine, biology, and other fields (see e.g., ^[2,3,4,5,6]). The performance of the kernel-based regularized online learning algorithms have been researched and their effectiveness has been verified (see e.g., ^{[7,8,9,10,11]} and references therein). Unlike the off-line learning algorithms, online learning algorithms process the observations one by one, and the output is adjusted in time according to the results of the last learning.

With the observations $z = \{(x_{t}, y_{t})\}_{t = 1}^{T}$, the kernel regularized online learning algorithm based on the stochastic descent method is given by (see e.g., ^[8,9,10])

where $\eta_{t}$ is called the stepsize, $\lambda > 0$ is a regularization parameter and the sequence $\{f_t: t = 1, \dots, T+1\}$ is the learning sequence.

When the least-square loss function $V(x, y, f(x)) = (f(x)-y)^2$ is selected, the specific iteration format of the online learning algorithm is given by

To study the learning performance of online learning algorithms we need to bound the convergence rate of the iterative sequence $\{f_{t}: t = 1, \cdots, T+1\}$. The convergence of the online learning algorithm (1.2) has been extensively studied in the literature (see e.g., ^[8,9,12]). The research results in ^[12] show that under mild conditions the regularized online learning algorithm can converge comparably fast as the off-line learning algorithm.

The least square-loss is the most widely utilized criterion for regression in practice. However, from a robustness point of view, the least square loss is not a good choice. In many practical applications, outliers or heavy-tailed distributions often occur in real data sets. In recent years, how to improve the robustness of algorithms has become one of the hot topics in the field of machine learning. In the literature on learning theory, a lot of efforts have been made and there have been some results on generalization analysis (see e.g., ^{[13,14,15,16,17]}) and empirical experiments (see e.g., ^[18,19]) of learning algorithms when outliers or heavy-tailed noise are allowed.

One of the main strategies to improve robustness is to use some robust loss function with a scale parameter(see e.g., ^[20,21]). Based on the quadratic function $\sqrt{1+t^2}, t\in \mathbf{R}$ which plays an important role in constructing shape preserving quasi-interpolation and solving partial differential equations with mesh-free method since its strong nonlinear property and its convexity, ^[21] constructed a robust loss function $V_{\sigma}(r)$ with a scale parameter $\sigma\in (0, 1]$. For $\sigma\in (0, 1]$, the parameterized loss function $V_{\sigma}(r): \mathbf{R}\rightarrow [0, \infty)$ is defined as

The analysis results in ^[21] show that the learning algorithm based on the parameterized loss function $V_{\sigma}(r)$ has a good generalization ability.

Encouraged by these researches, we want to further improve the performance and applicability of the online algorithm. In this paper, we introduce the parameterized loss function $V_{\sigma}(r)$ into the online learning algorithm, and analyze the influence of the scale parameter on the convergence rate of the algorithm.

To give the specific format of the learning algorithm with the parameterized loss function, we give the following notations correspondingly. We denote

and

The kernel-based regularized off-line algorithm is the following optimization problem:

Based on the random observations $z = \{(x_{t}, y_{t})\}_{t = 1}^{T}$, the approximate solution of the problem (1.5) is obtained through the following learning process

It is easy to see that the gradient of the loss function $V_{\sigma}$ is given by

Along with the online algorithm (1.1), the kernel regularized online learning algorithm with the parameterized loss function $V_{\sigma}(r)$ is defined by

In this paper, we focus on the performance of the sequence $\{f_t: t = 1, ..., T+1\}$ produced by the algorithm (1.6).

The remaining parts of this paper are organized as follows: we present the main results of this paper in Section 2. The proofs of the main results are given in Section 3. Discussions and comparisons with related works are given in Section 4. Conclusions and some questions for further study are mentioned in Section 5.

In the present paper, we write $A = O(B)$ if there is a constant $C\geq0$ such that $A\leq CB$. We use $\mathbb{E}_{z}[\cdot]$ to denote the expectation with respect to $z$. When its meaning is clear from the context, we use the shorthand notation $\mathbb{E}[\cdot]$.

2.   The main results

In this section, we present our main results about the performance of the algorithm (1.6), proofs are given in Section 3.

2.1.   The convergence of the learning sequence

Our first main result establishes the convergence of the sequence $\{f_t: t = 1, ..., T+1\}$ in expectation, under mild conditions on the stepsize.

Theorem 2.1. Let $f_{\lambda}^{\sigma}$ be defined as in (1.5), and let $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6), $\lambda > 0$. If $\{\eta_{t}\}$ satisfies $\sum\limits^\infty_{t = 1}\eta_{t} = +\infty$, $\lim\limits_{t\rightarrow +\infty}\eta_{t} = 0$ and $\eta_{t}\leq\frac{1}{\lambda}$, then it holds that

2.2.   Error analysis

Our second main result gives the explicit convergence rate of the last iterate by specifying the step sizes in the algorithm (1.6).

Theorem 2.2. Let $f_{\lambda}^{\sigma}$ be defined as in (1.5), and let $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6). For any $0 < \lambda\leq1$, $0 < \theta\leq1$, take $\eta_{t} = \frac{1}{C}t^{-\theta}$ with $C\geq\lambda+4(\kappa^2+1)$. Then, it holds that

where $D_{\sigma}(\lambda) = \frac{2M\sigma}{\lambda}, C_{\sigma} = 4M\sigma(\kappa^2+1)$.

Corollary 2.1. Let $f_{\lambda}^{\sigma}$ be defined as in (1.5), and let $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6). For any $\theta\in(0, 1), 0 < \alpha\leq\min\{1-\theta, \theta\}$, take $\lambda = T^{-\alpha}$. If the stepsize is chosen as $\eta_{t} = \frac{1}{C}t^{-\theta}$, then it holds that

where $C_{M, C, \kappa, \theta}$ is a constant depending only on $\theta, \kappa, C$ and $M$.

Remark 1. The results given in Theorem 2.2 and Corollary 2.1 show that the scale parameter $\sigma$ can effectively control the convergence rate of $\|f_{T+1}-f^{\sigma}_{\lambda}\|_{K}$, which is usually referred to as the sample error. Depending on the circumstances, the sample error bound can be greatly improved by choosing the parameter $\sigma$ properly. In fact, take $\sigma = \lambda = T^{-\alpha}$. Then by (2.1), we have $\mathbb{E}\left[\|f_{T+1}-f_{\lambda}^{\sigma}\|_{K}^2\right] = O\big(T^{-\theta}\big)$ which is better than the sample error bound $O\big(T^{-(\theta-\alpha)}\big)$ given in ^[9].

The results provided above mainly describe the convergence rate of the sample error. However, in the studying the learning performance of learning algorithms, we are often interested in the excess generalization error $\mathcal{E}_{\sigma}(f_{T+1})-\mathcal{E}_{\sigma}(f_{\sigma})$. Define

which is often used to denote the approximation error, whose convergence is determined by the capacity of $\mathcal{H}_K$. We assume the $\mathcal{K}$-functional satisfies the following decay

with $0 < \beta\leq1$.

By combining the sample error with the approximation error, we obtain the overall learning rate stated as follows.

Corollary 2.2. Let $\mathcal{E}_{\sigma}(f)$ be the generalization error defined as in (1.3), $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6). For $\theta\in(0, 1), 0 < \alpha\leq\min\{1-\theta, \theta\}$, take $\lambda = T^{-\alpha}$. If the stepsize is chosen as $\eta_{t} = \frac{1}{C}t^{-\theta}$, then it holds that

Now, we compare the performance of the algorithm (1.6) with that of the online kernel regularized learning algorithm based on the least square loss.

In ^[22], the online kernel regularized learning algorithm with the least-square loss is researched, and the learning rates are established under some assumptions. Namely, for $0 < \beta\leq1$, $0 < \delta < \frac{\beta}{\beta+1}$, there holds

and for $\frac{1}{2} < \beta\leq1$, $0 < \delta < \frac{2\beta-1}{2\beta+1}$, there holds

For $0 < \beta\leq1$, we choose $\sigma = T^{-\frac{\mu}{3}}$ with $0 < \mu\leq\frac{2\beta-1}{2\beta+1}$. Take $\lambda$ = $T^{\frac{\delta}{2\beta}-\frac{1}{2(\beta+1)}-\frac{\mu}{2\beta+1}}$ and $\eta_t$ = $\frac{1}{4\kappa^2+5}t^{\frac{2\beta+1}{2\beta}\delta-\frac{2\beta+1}{2(\beta+1)}}$ with $\frac{\beta}{\beta+1}-\frac{2\beta}{2\beta+1}\mu < \delta < \frac{\beta}{\beta+1}+\frac{2\beta}{2\beta+1}$. By Corollary 2.2, we have

And for $\frac{1}{2} < \beta\leq1$, we choose $\sigma^3 = \lambda = T^{\frac{2\beta}{2\beta-1}\delta-\frac{2\beta}{2\beta+1}}$ with $0 < \delta < \frac{2\beta-1}{2\beta+1}$. Take $\eta_t = \frac{1}{4\kappa^2+5}t^{\frac{2\beta}{2\beta-1}\delta-\frac{2\beta}{2\beta+1}}$. By Corollary 2.2, we have that

The rate (2.6) is better than (2.4), and (2.7) is better than (2.5). The analysis results illustrate that the convergence rate of the algorithm (1.6) can be improved by choosing the parameter $\sigma$ appropriately.

3.   Proofs

Lemma 3.1. Let $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6). If $\eta_{t}\leq\frac{1}{\lambda}$, then, for any $t = 1, ..., T+1$, it holds that

Proof. We prove (3.1) by induction on $t$. The inequality (3.1) is true for $t = 1$ because of the initialization condition $f_{1} = 0$. Suppose the bound (3.1) holds for any $t$, and consider $f_{t+1}$. The iteration (1.6) can be rewritten as

This implies that

Since

Combined with the assumption $\|f_{t}\|_K\leq\frac{\kappa \sigma}{\lambda}$, we have

This completes the proof.

Lemma 3.2. Assume $f_{\lambda}^{\sigma}$ is defined as in (1.5). Then, for any $f\in\mathcal{H}_{K}$, it holds that

Proof. By Taylor formula, for any $u, v\in \mathbf{R}$, we have

where $\xi\in \mathbf{R}$ is between $u$ and $v$.

Note that, $V_{\sigma}^{''}(\xi) = \frac{1}{\sqrt{\left(1+(\frac{\xi}{\sigma})^2\right)^3}} > 0$. Then,

Therefore, for any $f, g\in\mathcal{H}_{K}$, we have

By ($i$) of Lemma 5.1 in ^[23], we know $\mathcal{E}_{\sigma}(f)$ is a convex function on $\mathcal{H}_{K}$. And $\|f\|^2_{K}$ is a strictly convex function on $\mathcal{H}_{K}$. Then, $\Omega_{\sigma}(f) = \mathcal{E}_{\sigma}(f)+\frac{\lambda}{2}\|f\|^2_{K}$ is a convex function on $\mathcal{H}_{K}$. Based on ($ii$) of Lemma 5.1 in ^[23], we have

Taking inner product with $f-f_{\lambda}^{\sigma}$ on both sides of the above formula, we get

This proves our conclusion.

Lemma 3.3. Let $f_{\lambda}^{\sigma}$ be defined as in (1.5). For any $f\in\mathcal{H}_{K}$, we denote $\Omega_{\sigma}(f) = \mathcal{E}_{\sigma}(f)+\frac{\lambda}{2}\|f\|^2_{K}$. Then, it holds that

Proof. For any $f\in\mathcal{H}_{K}$, we define a function$f_{(\theta)} = f_{\lambda}^{\sigma}+\theta(f-f_{\lambda}^{\sigma}), \theta\in[0, 1]$. Then, $f_{(0)} = f_{\lambda}^{\sigma}$ and $f_{(1)} = f$. Denote $F(\theta) = \Omega_{\sigma}(f_{(\theta)}) = \int_{Z}V_{\sigma}(y-f_{(\theta)}(x))d\rho+\frac{\lambda}{2}\|f_{(\theta)}\|^{2}_{K}$, then $F(1) = \Omega_{\sigma}(f), F(0) = \Omega_{\sigma}(f_{\lambda}^{\sigma})$. Since $V_{\sigma}$ is differentiable, as a function of $\theta$, $F(\theta)$ is differentiable. And for any $\theta\in[0, 1]$, we have

By the median value theorem, there holds

where $\xi\in(y-f_{(\theta)}(x))-\triangle\theta(f(x)-f_{\lambda}^{\sigma}(x), y-f_{(\theta)}(x))$.

This in connection with $\|f_{(\theta)}+\triangle\theta(f-f_{\lambda}^{\sigma})\|^{2}_{K}-\|f_{(\theta)}\|^{2}_{K} = 2\triangle\theta\langle f-f_{\lambda}^{\sigma}, f_{(\theta)}\rangle_{K}+(\triangle\theta)^2\|f-f_{\lambda}^{\sigma})\|^{2}_{K}$, according to (3.10), tells us that

By Lemma 3.2, we see that

On the other hand, since $V_{\sigma}(u)$ is a convex function in $\mathbf{R}$, by discussions in ^[24], we know that

Therefore, for $\theta\in(0, 1)$, we have

By the definition of $f_{\lambda}^{\sigma}$, we know that $F(\theta)\geq F(0) = \Omega_{\sigma}(f_{\lambda}^{\sigma}), \theta\in[0, 1]$. Therefore, (3.14) implies that

The proof is completed.

Lemma 3.4. Let $f_{\lambda}^{\sigma}$ be defined as in (1.5), $\{f_t: t = 1, ..., T+1\}$ be the sequence produced by the algorithm (1.6), if $\lambda > 0$, $\eta_{t}\leq\frac{1}{\lambda}$, then

Furthermore, there holds

Proof. According to the algorithm (1.6), we know

where $A = \langle \lambda f_{t}-\frac{y_{t}-f_{t}(x_{t})}{\sqrt{1+(\frac{y_{t}-f_{t}(x_{t})}{\sigma})^2}}K_{x_{t}}, f_{\lambda}^{\sigma}-f_{t}\rangle_{K}$.

By using the inequality $\langle a, b-a \rangle_{K}\leq\frac{1}{2}(\|b\|_{K}^2-\|a\|_{K}^2), a, b\in \mathcal{H}_{K}$, with $a = f_{t}, b = f_{\lambda}^{\sigma}$, we have

Since $f_{t}$ depends on $\{z_{1}, ..., z_{t-1}\}$ but not on $z_{t}$, it follows that

Combining (3.18) with (3.20), we have

According to Lemma 3.3, we know

Therefore, (3.21) implies that

By Lemma 3.1, we know

Substituting (3.24) into (3.23), we obtain

Applying the relation iteratively for $t = T, T-1, ..., 1$, we have

Denote $\prod\limits^T_{j = T+1}(1-\lambda\eta_{j}) = 1$. From the definition of $f_{\lambda}^{\sigma}$, we see that

This in connection with the initialization condition $f_{1} = 0$, it follows that

This shows (3.16). (3.17) follows from (3.16) and the inequality $1-u\leq e^{-u}$ for any $u\geq0$.

3.1.   Proof of Theorem 2.1

Proof. It is easy to see that

It implies that, for any $\varepsilon > 0$, there exists some $T_{1}\in\mathbb{N}$ such that

whenever $T\geq T_1$.

And according to the assumption $\lim\limits_{t\rightarrow +\infty}\eta_{t} = 0$, we know that there exists some $t(\varepsilon)\in\mathbb{N}$ such that $\eta_t\leq\lambda\varepsilon$, for every $t\geq t(\varepsilon)$. Furthermore, we have

Since $t(\varepsilon)$ is fixed, there exists some $T_{2}\in\mathbb{N}$ such that, for every $T\geq T_{2}$, it holds that

So, for any $1\leq t\leq t(\varepsilon)$, we have

Hence

From (3.26) and (3.27), we know that for any $\varepsilon > 0$, there exists some $T_{2}\in\mathbb{N}$ such that

whenever $T\geq T_2$. Let $T^{'} = \max\{T_{1}, T_{2}\}$, then by (3.16), (3.26) and (3.27) we have

when $T\geq T^{'}$. Thus we complete the proof of Theorem 2.1.

3.2.   Proof of Theorem 2.2

Proof. By (3.21), we know

From the inequality $\|a-b\|_{K}^2\leq2\|a\|_{K}^2+2\|b\|_{K}^2$, we have

On the other hand, for any $r\in\mathbf{R}$, it holds that $\big|\frac{r}{\sqrt{1+(\frac{r)}{\sigma}})^2}\big|^2\leq2\sigma^2\big(\frac{\sqrt{\sigma^2+r^2}}{\sigma}-1\big) = 2V_{\sigma}(r)$. This implies that

Combining (3.30) with (3.31), we get

Substituting (3.32) into (3.29), we get

where

Based on the assumptions about $\eta$, we know that $1-2(\kappa^2+1)\eta_t\geq\frac{1}{2}$. And by Lemma 3.3, we know

This implies that

Combining (3.33) with (3.34), we obtain

Denote $C_{\sigma} = 4M\sigma^2(\kappa^2+1)$. For $t = T, T-1, ..., 1$, we apply the relation iteratively. Then we have

For any $u\geq0$, we know that the inequality $1-u\leq e^{-u}$ holds. And (3.36) implies that

Denote

and

Then, by (3.37) and the assumptions about the stepsize $\eta_{t}$, we know

Now, we estimate $I_{1}$ and $I_{2}$ respectively. By Lemma 4 of ^[9], we obtain the following estimate of $I_{1}$

On the other hand, by Lemma 5.10 of ^[23] with $\nu = \frac{\lambda}{2C}, s = \theta$, we have

So,

Furthermore, we have the following estimate of $I_{2}$

Since $T^{-2\theta}\leq T^{-\theta}$ and $\lambda\leq C$, the conclusion can be established by combining (3.38) with (3.39) and (3.40).

3.3.   Proof of Corollary 2.1

Proof. For $\theta\in(0, 1), 0 < \alpha\leq\min\{1-\theta, \theta\}$, by Theorem 2.2 with $\lambda = T^{-\alpha}$, we have

Since for any $\nu > 0, c > 0, \eta > 0$, there exists $L > 0$ such that $\exp\{-cT^\nu\}\leq LT^{-\eta}$, and hence the first term on the right-hand side of (3.41) decays in the form of $O(\frac{\sigma}{T^{\eta}})$ for any large $\eta > 0$. However, the second term on the right-hand side of (3.41) is bounded by $O(\frac{\sigma}{T^{\theta-\alpha}})$. Consequently, there exists a constant $C_{M, C, \kappa, \theta}$ depending only on $\theta, \kappa, C$ and $M$ such that

The proof is completed.

3.4.   Proof of Corollary 2.2

Proof. According to the median value theorem, there exists $\xi$ between $y-f_{T+1}(x)$ and $y-f_{\lambda, \sigma}(x)$ such that

Then, we have

And we get

Combined which with Corollary 2.1 and the assumption 2.2, the desired result follows.

4.   Discussions

$\bullet$ Most studies of online learning algorithms focus on the convergence in expectation (for example ^[8,9,10,25]). However, these results were established based on some fixed loss functions, such as the least-square loss function (see e.g., ^[9,22]). Our results are established based on a parameterized loss function with a scale parameter $\sigma$. The analysis results in Section 2 show that the scale parameter $\sigma$ can effectively control the convergence rate of the learning algorithm, and a better convergence rate is obtained. On the other hand, the previous researches on online learning algorithms rely on integral operator theory (see ^[25]), this paper establishes the error bounds for the learning sequence by applying the convex analysis method. Convex analysis method has been widely used in various research fields, for example, in the analysis of machine learning algorithms (see e.g., ^[21,23,26]) and the studies of discrete fractional operators (see e.g., ^[27,28]), and it has been proved to be a very effective analysis method.

$\bullet$ In ^[23], the online pairwise regression problem with the quadratic loss is researched. Different from the reference ^[23], in this paper, we use the parameterized loss function for the pointwise learning model, which has a wider range of applications than the pairwise learning model. It is known that deep convolution networks can increase approximation order (see e.g., ^{[29,30,31,32]}), then it is hopeful that the convergence rate provided in this paper can be improved by choosing the deep neural network method.

5.   Conclusions

In the present paper, we analyze the learning performance of the kernel regularized online algorithm with a parameterized loss. The convergence of the learning sequence is proved and the error bound is provided in the expectation sense by using the convex analysis method. There are some questions for further study. In this paper, we focus on the theoretical analysis of the kernel regularized online algorithm with a parameterized loss $V_{\sigma}$. However, there is still a gap between theoretical analysis and the optimization process of empirical risk minimization based on a parameterized loss. In the future study, it would be interesting to apply the online learning algorithm based on $V_{\sigma}$ to solve some practical problems and construct an effective solution method. In addition, we mainly analyze the sample error in this paper, and the approximation error is represented by $\mathcal{K}$-functional. How to make a more accurate analysis of the approximation error and further study the influence of the scale parameter $\sigma$ on the approximation error still need to be further studied.

Acknowledgments

This work is supported by the Special Project for Scientific and Technological Cooperation (Project No. 20212BDH80021) of Jiangxi Province, the Science and Technology Project in Jiangxi Province Department of Education (Project No. GJJ211334).

Conflict of interest

No potential conflict of interest was reported by the author.