A new accelerated algorithm with a linesearch technique for convex bilevel optimization problems with applications

1.   Introduction

Convex bilevel optimization problems play an important role in many real-word applications such as image-signal processing, data science, data prediction, data classification, and artificial intelligence. For some interesting applications, we refer to the recent papers ^[1,2]. More precisely, we recall the concept of the convex bilevel optimization problem as the following. Let $\psi$ and $\phi$ be two proper convex and lower semi-continuous functions from a real Hilbert space $H$ into $\mathbb{R} \cup \{+ \infty\}$, and $\phi$ is a smooth function. In this work, we consider the following convex bilevel optimization problem:

where $h$ is a strongly convex differentiable function of the form $H$ into $\mathbb{R}$ with parameter $s$, and $S^{\star}$ is the solution set of the problem:

Problems (1.1) and (1.2) are known as outer-level and inner-level problems, respectively. It is well-known that if $z^{\star}$ satisfies the variational inequality:

then $z^{\star}$ is a solution of the outer-level problem (1.1); for more details, see ^[3]. Generally, the solution of problem (1.2) usually exists under the assumption that $\nabla \phi$ is Lipschitz continuous with parameter $L_{\phi}$, that is, there exists $L_{\phi} > 0$ such that $\| \nabla \phi(w)- \nabla \phi (v) \| \leq L_{\phi} \|w-v\|$ for all $w, v \in H$.

The proximity operator, prox$_{\mu \psi}(z^\star) = J_{\mu}^{\partial \psi}(z^\star) = (I+ \mu \partial \psi)^{-1}(z^\star)$, where $I$ is an identity mapping and $\partial \psi$ is a subdifferential of $\psi$, is crucial in solving problem (1.2). It is known that a point $z^\star$ in $S^{\star}$ is a fixed point of proximity operator prox$_{\mu \psi}(I- \mu \nabla \phi)$. The following classical forward-backward splitting algorithm:

was proposed for solving problem (1.2). After that, Sabach and Shtern ^[4] introduced the bilevel gradient sequential averaging method (BiG-SAM), as seen in Algorithm 2. They also proved that sequence $\{ x_k \}$ generated by BiG-SAM converges strongly to the optimal point $z^\star$ in the convex bilevel optimization problem (1.1) and (1.2). Later, to speed up the rate of convergence of BiG-SAM, Shehu et al. ^[5] employed an inertial technique proposed by Polyak ^[6], as defined by Algorithm 3 (iBiGSAM). Moreover, they proved a strong convergence theorem of Algorithm 3 under some weaker assumptions on $\{ \lambda_k \}$ given in ^[7], that is, $\lim\limits_{k \to \infty} \lambda_k = 0$ and $\sum_{k = 1}^{\infty} \lambda_k = + \infty$. Moreover, the convergence rate of the iBiG-SAM was consecutively improved by adapting the inertial technique, which is called the alternated inertial bilevel gradient sequential averaging method ^[8] (aiBiG-SAM), as seen in Algorithm 4. It was shown by some examples in ^[8] that the convergence behavior of aiBiG-SAM is better than BiG-SAM and iBiG-SAM. Recently, Jolaoso et al. ^[9] proposed a double inertial technique to accelerate the convergence rate of the strongly convergent 2-step inertial PPA algorithm solving for a zero of the sum of two maximal monotone operators. Yao et al. ^[10] also introduced a method for solving such a problem, called the weakly convergent FRB algorithm with momentum. This problem is just the inner-level problem in this work.

It is worth noting that all methods mentioned above desire a Lipschitz continuity assumption of $\nabla \phi$. However, finding a Lipschitz constant of $\nabla \phi$ is sometimes too difficult. To solve the inner-level problem without computing the Lipschitz constant of gradient $\nabla \phi$, Cruz and Nghia ^[11] presented a linesearch technique (Linesearch 1) for finding some suitable step size for a forward-backward splitting algorithm. This notion provides weaker assumptions on the gradient of $\phi$, as seen in the following criteria:

A1. $\phi, \psi : H \to (-\infty, +\infty]$ are proper lower semicontinuous convex functions with $\text{dom} \psi \subseteq \text{dom} \phi$;

A2. $\phi$ is differentiable on an open set containing $\text{dom} \psi$, and $\nabla \phi$ is uniformly continuous on any bounded subset of $\text{dom} \psi$ and maps any bounded subset of $\text{dom} \psi$ to a bounded set in $H$.

It is observed that assumption A2 is weaker than the Lipschitz continuity assumption on $\nabla \phi$. Under assumptions A1 and A2, they proved that the sequence $\{ x_k \}$ generated by (1.3), where $\mu_k$ is derived from Linesearch 1 (see more detail in the appendix), converges weakly to the optimal solution of the inner level problem (1.2). Inspired by ^[11], several algorithms with the linesearch technique were proposed in order to solve problem (1.2); see ^{[12,13,14,15,16,17]}, for examples. Recently, Hanjing et al. ^[17] introduced a new linesearch technique (Linesearch 2) and a new algorithm (Algorithm 5), called the forward-backward iterative method with the inertial technical term and linesearch technique, to solve the inner-level problem (1.2). For more details on Linesearch 2 and Algorithm 5, see the appendix. They proved that the sequence $\{ x_k \}$ generated by Algorithm 7 converges weakly to a solution of problem (1.2) under some control conditions.

Note that Algorithm 7 was employed to find a solution of the inner-level problem (1.2) and it provided only weak convergence, but the strong convergence is more desired. Inspired by all of the mentioned works, we aim to develop Algorithm 7 for solving the convex bilevel problems (1.1) and (1.2) by employing Linesearch 2 together with the viscosity approximation methods. The strong convergence theorem of our developed algorithm is established under some suitable conditions and assumptions. Furthermore, we apply our proposed algorithm to solve image restoration and data classification problems including comparison of its performance with other algorithms.

2.   Notations and instruments for convergent analysis

In this section, we provide some important definitions, propositions, and lemmas which will be used in the next section. Let $H$ be a real Hilbert space and $X$ be a nonempty closed convex subset of $H$. Then, for each $w \in H$, there exists a unique element $P_X w$ in $X$ satisfying

The mapping $P_X$ is known as the metric projection of $H$ onto $X$. Moreover,

holds for all $w \in H$ and $z \in X$. A mapping $f: X \to H$ is called Lipschitz continuous if there exists $L_f > 0$ such that

If $L_f \in [0, 1)$, then $f$ is called a contraction. Moreover, $f$ is nonexpansive if $L_f = 1$. The domain of function $f: H \to [-\infty, +\infty]$ is denoted by $\text{dom} f$, when $\text{dom} f : = \{ v \in H : f(v) < \infty \}$. Let $\{ x_k \}$ be a sequence in $H$, and we adopt the following notations:

1) $x_k \rightharpoonup w$ denotes that sequence $\{ x_k \}$ converges weakly to $w \in H$;

2) $x_k \to w$ denotes that $\{ x_k \}$ converges strongly to $w \in H$.

For each $v, w \in H$, the following conditions hold:

1) $\|v \pm w \|^2 = \| v \|^2 \pm 2 \langle v, w \rangle + \|w\|^2$;

2) $\| v + w \|^2 \leq \|v \|^2 + 2 \langle w, v+w \rangle$;

3) $\|tv + (1-t)w \|^2 = t\|v\|^2 + (1-t)\|w\|^2 -t(1-t)\|v-w\|^2, \; \; \forall t \in \mathbb{R}$.

Let $\psi : H \to (-\infty, + \infty ]$ be a proper function. The subdifferential $\partial \psi$ of $\psi$ is defined by

If $\partial \psi (u) \neq \emptyset,$ then $\psi$ is subdifferentiable at $u$, and the elements of $\partial \psi (u)$ are the subgradients of $\psi$ at $u$. The proximal operator, prox$_{\psi}: H \to \; \text{dom} \psi$ with prox$_{\psi} (x) : = (I + \partial \psi)^{-1}$, is single-valued with a full domain. Moreover, we have from ^[18] that for each $x \in H$ and $\mu > 0$,

Let us next revisit some important properties for this work.

Lemma 1 (^[19]). Let $\partial \psi$ be a subdifferential of $\psi$. Then, the following hold:

1) $\partial \psi$ is maximal monotone,

2) Gph$(\partial \psi) : = \{ (v, w) \in H \times H : w \in \partial \psi(v) \}$ is demiclosed, i.e., if $\{ (v_k, w_k) \}$ is a sequence in Gph$(\partial \psi)$ such that $v_k \rightharpoonup v$ and $w_k \to w$, then $(v, w) \in$ Gph$(\partial \psi)$.

Using the same idea of [4, Proposition 3], the following result can be proven.

Proposition 2. Suppose $h : H \to \mathbb{R}$ is strongly convex with parameter $s > 0$ and continuously differentiable such that $\nabla h$ is Lipschitz continuous with constant $L_{h}$. Then, the mapping $I-t \nabla h$ is $c$-contraction for all $0 < t \leq \frac{2}{L_{h}+ s}$, where $c = \sqrt{1-\frac{2 st L_{h}}{s+ L_{h}}}$ and $I$ is the identity operator.

Proof: For any $x, y \in H$, we obtain

Using the same proof as in the case of $H = \mathbb{R}^n$ on [20, Theorem 2.1.12], we get

From (2.2) and (2.4), we get

Lemma 3 (^[21]). Let $\{ a_k \}$ be a sequence of nonnegative real numbers satisfying

where $\{ b_k \}$ is a sequence in $(0, 1)$ such that $\sum_{k = 1}^{\infty} b_k = +\infty$ and $\{ s_k \}$ is a sequence satisfying $\limsup_{k \to \infty} s_k \leq 0.$ Then, $\lim\limits_{k \to \infty} a_k = 0.$

Lemma 4 (^[22]). Let $\{ u_k \}$ be a sequence of real numbers such that there exists a subsequence $\{ u_{m_j} \}$ of $\{ u_k \}$ such that $u_{m_j} < u_{m_{j} + 1}$ for all $j \in \mathbb{N}$. Then there exists a nondecreasing sequence $\{ k_{\ell} \}$ of $\mathbb{N}$ such that $\lim_{ \ell \to \infty} k_{\ell} = \infty$ and for all sufficiently large $\ell \in \mathbb{N}$, the following holds:

3.   Main convergence theorems

We begin this section by introducing a new accelerated algorithm (Algorithm 1) by using a linesearch technique together with some modifications of Algorithm 5 for solving bilevel convex minimization problems (1.1) and (1.2). Throughout this section, we let $\Omega$ be the set of all solutions of convex bilevel problems (1.1) and (1.2), and we assume that $h : H \to \mathbb{R}$ is a strongly convex differentiable function with parameter $s$ such that $\nabla h$ is $L_{h}$-Lipschitz continuous and $t \in \left(0, \frac{2}{L_{h} + s} \right]$. Suppose $f : \text{dom} \psi \to \text{dom} \psi$ is a $c$-contraction for some $c \in (0, 1)$. Let $\{ \gamma_k \}$ be a real positive sequence, $\{ \xi_k \}$ a positive sequence, and $\{ \lambda_k \}$ be a sequence in $(0, 1)$. We propose the following Algorithm 1:

 

Remark 1. Our proposed algorithm uses a linesearch technique for finding the step size of the proximal gradient methods in order to relax the continuity assumption on the gradeint of f. Note that this linesearch technique employes two proximal evaluations which is appropriated from the algorithms consisting of two proximal evaluations at each iteration, see ^{[12,13,14,15,16,17]}. It is observed that those algorithms have a better convergence behavior than the others.

To prove the convergence results of Algorithm 1, we need to find the following results.

Lemma 5. Let $\{x_k \}$ be a sequence generated by Algorithm 1, and $v \in \text{dom} \psi$. Then, the following inequality holds:

Proof: Let $v \in \text{dom} \psi$. It follows from (2.2) that

and

Then, by the definition of $\partial \psi$, we get

and

By the convexity of $\phi$, we have for every $x \in \text{dom} \phi$ and $y \in \text{dom} \psi$,

which implies

and

From (3.2), (3.3), (3.5), and (3.6), we have

This together with (3.4) gives

By the definition of Linesearch 1, we get

From (3.7) and (3.8), we have

Moreover, we know that

and

By replacing (3.10) and (3.11) in (3.9), we obtain

Lemma 6. Let $\{ x_k \}$ be a sequence generated by Algorithm 1 and $S^{\star} \neq \emptyset$. Suppose that $\lim_{k \to \infty} \frac{\xi_k }{\lambda_k} = 0$. Then $\{ x_k \}$ is bounded. Furthermore, $\{ f(x_k) \}, \; \{ u_k \}, \; \{ y_k \}$, and $\{v_k \}$ are also bounded.

Proof: Let $v^{\star} \in S^{\star}$. By Lemma 5, we have

which implies

By the definition of $u_k$ and since $f$ is a contraction with constant $c$, we get

This together with (3.14) gives

From (3.1), we have

Using $\lim\limits_{k \to \infty} \frac{\xi_k}{\lambda_k} = 0$, we obtain $\lim_{k \to \infty} \frac{\eta_k}{\lambda_k}\| y_k - y_{k-1}\| = 0.$ Therefore, there exists $N > 0$ such that $\frac{\eta_k}{\lambda_k}\|y_k - y_{k-1}\| \leq N$ for all $k \in \mathbb{N}$. The above inequality implies

By induction, we have $\|x_{k+1} - v^{\star}\| \leq \max \left\{ \|x_1 - v^{\star} \|, \frac{\|f(v^{\star}) - v^{\star}\|}{1-c} + \frac{N}{1-c} \right\},$ and so $\{ x_k \}$ is bounded. It follows that $\{ f(x_k) \}$ is bounded. Combining this with the definition of $u_k$, we obtain that $\{ u_k \}$ is bounded. It follows by (3.14) that $\{y_k \}$ and $\{v_k \}$ are also bounded.

Theorem 7. Let $\{ x_k \}$ be a sequence generated by Algorithm 1 and $S^{\star} \neq \emptyset$. Suppose $\phi$ and $\psi$ satisfy A1 and A2 and the following conditions hold:

1) $\{ \lambda_k\}$ is a positive sequence in $(0, 1)$;

2) $\mu_k \geq \mu$ for some $\mu \in \mathbb{R}_{+}$;

3) $\lim_{k \to \infty} \lambda_k = 0$ and $\sum_{k = 1}^{\infty} \lambda_k = + \infty$;

4) $\lim_{k \to \infty} \frac{\xi_k }{\lambda_k} = 0$.

Then, $x_k \to v^\star \in S^{\star}$ such that $v^\star = P_{S^{\star}} f(v^\star)$. Moreover, if $f : = I-t \nabla h$, then $x_k \to v^\star \in \Omega.$

Proof: Let $v^{\star} \in S^{\star}$ be such that $v^\star = P_{S^{\star}} f(v^\star)$. By (3.17), Algorithm 1, and the fact that $f$ is a contraction with constant $c$, we have

Since $\lim\limits_{k \to \infty} \eta_k \|y_k - y_{k-1} \| = \lim\limits_{k \to \infty} (\lambda_k)\frac{\xi_k}{ \lambda_k} = 0,$ there exists $N_1 > 0$ such that $\eta_k \|y_k - y_{k-1} \| \leq N_1$ for all $k \in \mathbb{N}$. From Lemma 6, we have $\| y_k -v^{\star} \| \leq N_2$ for some $N_2 > 0$. Choose $\bar{N} = \sup_{k \in \mathbb{N}} \{ N_1, N_2 \}$. By (3.21), we get

In order to verify the convergence of $\{ x_k \}$, we analyze the proof into the following two cases.

Case 1. Suppose there exists $M \in \mathbb{N}$ such that $\|x_{k+1} - v^{\star} \| \leq \| x_k -v^{\star} \|$ for all $k \geq M$. This implies $\lim_{k \to \infty} \|x_k - v^{\star} \|$ exists. From (3.22), we set $a_k = \|x_k - v^{\star} \|^2, b_k = \lambda_k (1-c)$, and $s_k = \frac{2}{1-c}\langle f(v^{\star}) -v^{\star}, u_k -v^{\star} \rangle + \frac{ 3 \bar{N} \eta_{k}}{\lambda_k (1-c) }\|y_k - y_{k-1}\|$. It follows from $\sum\limits_{k = 1}^{\infty} \lambda_k = + \infty$ that $\sum\limits_{k = 1}^{\infty} b_k = (1-c)\sum\limits_{k = 1}^{\infty} \lambda_k = + \infty$. In addition,

Then, by $\lim\limits_{k \to \infty}\frac{\xi_k}{\lambda_k} = 0$, we get $\lim\limits_{k \to \infty} \frac{ 3 \bar{N} \eta_{k}}{\lambda_k (1-c) }\|y_k - y_{k-1}\| = 0.$

To employ Lemma 3, we need to guarantee that $\limsup\limits_{k \to \infty} s_k \leq 0.$ Since $\{ u_k\}$ is bounded, there exists a subsequence $\{ u_{k_j} \}$ of $\{ u_k \}$ such that $u_{k_j} \rightharpoonup w$, for some $w \in H$, and

Next, we show that $w \in S^{\star}$. We have from (3.19) and (3.20) that

Combining this with (3.18) and (3.20), we obtain

From (3.13), we have

and

From (3.23) and (3.24), we obtain

and

Moreover, we know that

The uniform convexity of $\nabla \phi$ and (3.26) yield

It implies, by assumption (2), that

This together with (3.26) and (3.27) yields

By the demiclosed nature of Gph($\partial (\phi + \psi)$), $0 \in \partial (\phi + \psi)(w)$, and so $w \in S^{\star}$. It derives from (2.1) that

which implies that $\limsup_{k \to \infty} s_k \leq 0.$ By Lemma 3, we obtain

Case 2. Suppose that there exists a subsequence $\{ x_{m_j} \}$ of $\{ x_k \}$ such that

for all $j \in \mathbb{N}$. By Lemma 4, there is a nondecreasing sequence $\{ k_{\ell} \}$ of $\mathbb{N}$ such that $\lim_{ \ell \to \infty} k_{\ell} = \infty$, and for all sufficiently large $\ell \in \mathbb{N}$, the following formula holds:

We have from (3.25) and (3.26) that

Since $\{ u_{k_{\ell}} \}$ is bounded, there exists a weakly convergent subsequence $\{ u_{k_{\ell_{i}}} \}$ of $\{ u_{k_{\ell}} \}$ such that $u_{k_{\ell_{i}}} \rightharpoonup w^{\star}$ for some $w^{\star} \in H$, and

The uniform convexity of $\nabla \phi$ and (3.29) imply

Moreover, we know that

It implies, by assumption (2), that

Using (3.29) and (3.30), we get

By demiclosedness of Gph($\partial (\phi + \psi)$), we obtain $0 \in \partial (\phi + \psi)(w^{\star})$ and thus $w \in S^{\star}$. This implies that

We derive from (3.22) and $\left\| x_{k_{\ell}} -v^{\star} \right\| \leq \left\| x_{k_{\ell} +1 } -v^{\star} \right\|$ that

which implies

Consequently,

From the above inequality and $\left\| x_{\ell} -v^{\star} \right\| \leq \left\| x_{k_{\ell} +1} -v^{\star} \right\|$, we obtain

Therefore, we can conclude that $x_k \to v^{\star}$. Finally, we show that $v^\star$ is the solution of problem (1.1). Since $f : = I- t \nabla h$, it follows that $f(v^\star) : = v^\star - t \nabla h (v^\star)$, which implies

for all $x \in S^\star$. This together with $0 < t$ give us that $0 \leq \langle \nabla h (v^\star), x - v^\star \rangle$ for all $x \in S^\star$. Hence $v^\star$ is the solution of the outer-level problem (1.1).

4.   Applications

In this section, we present an experiment on image restoration and data classification problems by using our algorithm, and compare the performance of the proposed algorithm with BiG-SAM, iBiG-SAM, and aiBiG-SAM. We apply MATLAB 9.6 (R2019a) to perform all numerical experiments throughout this work. It runs on a MacBook Air 13.3-inch, 2020, with an Apple M1 chip processor and 8-core GPU, configured with 8 GB of RAM.

4.1.   Image restoration problems

In this section, we apply the proposed algorithm to solve the true RGB image restoration problems, and compare its performance with BiG-SAM, iBiG-SAM, and aiBiG-SAM. Let $A$ be a blurring operator, and $x$ be an original image. If $b$ represents an observed image, then a linear image restoration problem is defined by

where $x \in \mathbb{R}^{n \times 1}$ and $w$ denotes an additive noise. In the traditional way, we apply the least absolute shrinkage and selection operator (LASSO) ^[23] method to approximate the original image $x$. It is given by

where $\alpha$ denotes a positive regularization parameter, $\|x \|_1 = \sum_{k = 1}^{n} \vert x_k \vert$, and $\|x \|_2 \! \! = \! \sqrt{\sum_{k = 1}^{n} \vert x_k \vert^2}.$ We see that (4.2) is the inner-level problem (1.2) when $\phi(x) = \|A x - b\|_{2}^2$ and $\psi(x) = \beta \|x \|_1.$ When the true RGB image is transformed as the matrix on the LASSO model, we see that the size of matrix $A$ and $x$ as well as their members have an effect on the computation for the multiplication of $Ax$ and $\| x \|$. To prevent this effect, we adopt the 2-D fast Fourier transform to convert the true RGB images into matrices instead. If $\mathcal{W}$ represents the 2-D fast Fourier transform, and $\mathcal{B}$ denotes the blurring matrix such that the blurring operator $\mathcal{A} = \mathcal{B} \mathcal{W}$, then problem (4.2) is transformed to the following problem:

where $b \in \mathbb{R}^{m \times n}$ is the observed image of size $m \times n$, and $\alpha > 0$ is a regularization parameter. Therefore, our proposed algorithm can be applied to solve an image restoration problem (4.1) by setting the inner-level problem as follows: $\phi(x) = \|\mathcal{A} x- b\|_{2}^2, \ \psi(x) = \alpha \|\mathcal{W}x\|_{1}$, and we choose the outer-level problem as $h(x) = \frac{1}{2}\|x\|^2.$ Next, we select all of the parameters satisfying the convergence theorem of each algorithm as seen in Table 1.

Also, the Lipschitz constant $L_{\phi}$ of $\nabla \phi$ for BiG-SAM, iBiG-SAM, and aiBiG-SAM is calculated by the maximum eigenvalue of the matrix $A^{T}A$. The efficiency of a restorative image is measured by the peak signal-to-noise ratio (PSNR) in decibel (dB), which is given by

where $\mbox{mse} = \frac{1}{K}\|x_k - v^{\star}\|_{2}^2$, $K$ denotes the number of image samples, and $v^{\star}$ indicates the original image. We select the regularization parameter $\alpha = 0.00001$ and consider the original image (Wat Lok Moli) of size $256 \times 256$ pixels from ^[24]. We employ a Gaussian blur to construct blurred and noisy images of size $9 \times 9$ with the standard deviation $\sigma = 4$. The original and blurred images are shown in Figure 2. The results of deblurring the image of Wat Lok Moli at 500 iterations is demonstrated in Table 2.

As seen in Table 2, our proposed algorithm (Algorithm 1) gives a higher value of PSNR than the others, which means that our algorithm has the best performance of the image restoration compared with others. The graph of PSNR for deblurring images at the 500th iteration are shown in Figure 1.

All restoration images of Wat Lok Moli of each algorithm at the 500th iteration are shown in Figure 2.

4.2.   Data classification

Machine learning is crucial because it allows computers to learn from data and make decisions or predictions. There are three types of machine learning such as supervised learning, unsupervised learning, and reinforcement learning. Our work uses supervised learning which uses the extreme learning machine (ELM) ^[25] and a single-layer feedback neural network (SLFNs) model while the reinforcement learning is typically used for decision-making problems where an agent learns to perform actions in an environment to maximize cumulative rewards (see more information in ^[26,27]). However, it is not commonly used directly for data classification, which is more traditionally tackled using supervised learning techniques.

In this work, we aim to use the studied algorithm to solve a binary data classification problem. We focus on classifying the patient datasets of heart disease ^[28] and breast cancer ^[29] into classes. The details of the studied datasets are given in Table 3.

Here, we accessed the above datasets on June 12, 2022 from https://archive.ics.uci.edu. We first start with a necessary notion for data classification problems. Now, we recall a concept of ELM. Suppose $p_k \in \mathbb{R}^n$ is an input data, and $q_k \in \mathbb{R}^m$ is the target. The training set of $N$ samples is given by $S : = \{(p_k, q_k): p_k \in \mathbb{R}^n, q_k \in \mathbb{R}^m, k = 1, 2, {\dots}, N\}.$ The output of the $i$-th hidden node for any single hidden layer of ELM is

where $\mathcal{G}$ is an activate function, $r_i$ is a bias, and $w_i$ is the weight vector connecting the $i$-th hidden node and the input node. If $M$ denotes the amount of the hidden nodes, then ELM for SLFNs gives the output function as:

where $m_i$ is the weight vector connecting the $i$-th hidden node and the output node. Thus, an output matrix of hidden layer $\textbf{A}$ is given by

A main purpose of ELM is to find a weight $m = [m^T_1, {\dots}, m^T_M ]^T$ such that

where $\textbf{Q} = [q^T_1, {\dots}, q^T_N ]^T$ is the training data. We observe from (4.5) that $m = \textbf{A}^{\dagger}\textbf{Q}$ whenever the Moore–Penrose generalized inverse $\textbf{A}^{\dagger}$ of $\textbf{A}$ exists. In some situations, if $\textbf{A}^{\dagger}$ does not exist, it may be difficult to find wight $m$, which satisfies (4.5). In order to overcome this situation, we utilize the following convex minimization problem (4.2) to solve $m$:

where $\beta$ is the regularized parameter and $\Vert (m_1, m_2, \ldots, m_p) \Vert_{1} = \sum_{i = 1}^{p} \vert m_i \vert.$ It derives from (4.2) that $\phi (m) : = \| \textbf{A}m - \textbf{Q} \|^2_2$ and $\psi : = \beta \| m \|_1$ are inner-level functions of problem (1.2). To employ the proposed algorithm, BiG-SAM, iBiG-SAM, and aiBiG-SAM for solving data classification, we choose the outer-level function $h(m) = \frac{1}{2}\|m\|^2$ for problem (1.1). With datasets from Table 3, we select an activation function $\mathcal{G}$ as sigmoid, and set the hidden node $M = 30$. Choose $t_0 = 1$ and $t_{k+1} = \frac{1+\sqrt{1+4 t_{k}^2}}{2},$ for all $k \geq 0.$ All parameters of each algorithm are chosen as in Table 4.

Also, the Lipschitz gradient $L_\phi$ of $\nabla \phi$ for BiG-SAM, iBiG-SAM, and aiBiG-SAM can be calculated by $2 \|\textbf{A} \|^2$. In order to measure the performance of the accuracy for prediction, we use the following formula:

where $TP$ is the number of cases correctly identified as patient, $TN$ represent the number of cases correctly identified as healthy, $FN$ means the number of cases incorrectly identified as healthy, and $FP$ denotes the number of cases incorrectly identified as patient. In what follows, Acc Train refers to the accuracy of training on the dataset, while Acc Test indicates the accuracy of testing on the dataset. We present the iteration numbers and training time on the learning model for each algorithm in Table 5.

As seen in Table 5, we observe that the training time of Algorithm 1 is not significantly different compared with the other algorithms. However, it needs to compute parameter $\mu_{k}$ occurring from the lineserch technique, while the other algorithms do not have this process. Note that under the linesearch technique, our algorithm has better convergence behavior than the others in terms of the number of iterations. This means that the proposed algorithm provides the best optimal weight compared with the others. To evaluate the performance of each algorithm, we construct a 10-fold cross validation. The 10-fold cross validation splits data into training sets and testing sets, as seen in Table 6.

In addition, we use the following formula in order to measure the success probability of making a correct positive class classification, which is defined by

Also, the sensitivity of the model toward identifying the positive class is estimated by

The appraising tool is the average accuracy which is given by

where $N$ is the number of sets considered during the cross validation ($N = 10$), $u_i$ is the number of correctly predicted data at fold $i$, and $v_i$ is the number of all data at fold $i$.

Let Err$_{M}$ be the sum of errors in all $10$ training sets, Err$_{K}$ be the sum of errors in all 10 testing sets, $M$ be the sum of all data in $10$ training sets, and $K$ be the sum of all data in $10$ testing sets. Then,

where ${\bf{error}}_{M\%} = \frac{{\bf{Err}}_{M}}{M} \times 100\%$ and ${\bf{error}}_{K \%} = \frac{{\bf{Err}}_{K}}{K} \times 100\%$.

We show the performance of each algorithm for patient prediction of heart disease and breast cancer with the 300th iteration in Tables 7 and 8.

According to Tables 7 and 8, Algorithm 1 gives the best average accuracy of training and testing datasets compared with BiG-SAM, iBiG-SAM, and aiBiG-SAM. We also see that our algorithm provides higher the recall and precision for diagnosis of heart disease and breast cancer. Furthermore, the proposed algorithm has the lowest percent error on prediction.

5.   Conclusions

Recently, there are various algorithms for solving convex bilevel optimization problems (1.1) and (1.2). These methods require the Lipschitz continuity assumption of the gradient of the objective function on problem (1.2). To relax this criteria, the linesearch technique is applied. In this work, we proposed a novel accelerated algorithm employing both linesearch and inertial techniques for solving convex bilevel optimization problems (1.1) and (1.2). The convergence theorem of the proposed algorithm was analyzed under some suitable conditions. Furthermore, we applied our algorithm to solve image restoration and data classification problems. According to our experiment, we obtained that the proposed algorithm has more efficiency on image restoration and data classification than the others.

It is worth mentioning that in real-world application, if we appropriately choose the objective function of the outer-level problem (1.1), our algorithm can provide more benefit and accuracy for the specific objective of data classifications. Note that we use $\frac{1}{2}\|x\|^2$ as the outer-level objective function, so our solution is a minimum norm problem. In order to improve the accuracy for prediction, in future work, we need a new mathematical model and deep learning algorithm. Very recently, a deep extreme learning machine is an appropriate model for improving accuracy for prediction, see ^[30,31]. However, deep extreme learning algorithms are also challenging to study and discuss. Moreover, we would like to employ our method for prediction of noncommunicable diseases of patient data from the Sriphat Medical Center, Faculty of Medicine, Chiang Mai University.

Author contributions

Adisak Hanjing: formal analysis, investigation, resources, methodology, writing-review & editing, validation, data curation, and funding acquisition; Panadda Thongpaen: formal analysis, invesigation, writing-original draft, software, visualization, data curation; Suthep Suantai: conceptualization, supervision, project administration, methodology, validation, and formal funding acquisition. All authors have read and agreed to the published version of the manuscript.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was partially supported by Chiang Mai University and the Fundamental Fund 2024 (FF030/2567), Chiang Mai University. The first author was supported by the Science Research and Innovation Fund, agreement no. FF67/P1-012. The authors would also like to thank the Rajamangala University of Technology Isan for partial financial support.

Conflict of interest

All authors declare no conflicts of interest in this paper.

Appendix A

In this section, we discuss the specific details of algorithms related to our work. These algorithms were proposed for solving convex bilevel optimization problems as follows:

 

 

 

Next, the details of the linesearch technique related to this work are provided as follows: