## 4 Global Convergence  
This section aims to establish the global convergence of Algorithm 1 for various oracles. These oracles are controlled by two parameters: the error bound \(\epsilon_{x}\) and the descent target \(\gamma_{x}\). In Table 1, we present the choices of these two parameters for different type of instances described in Section 2, including Exact (Ex), Partially Inexact (PI), Inexact (IE), Asymptotically Exact (AE) and Partially Asymptotically Exact (PAE) oracles, where the constants are selected as \(\theta\), \(\kappa\in(0,1)\), and \(\kappa_{\epsilon}\in(0,\kappa)\). The following lemma is crucial to guarantee the global convergence of Algorithm 1. **Lemma 2**. : _The descent target is always reached at the stability centers, that is, \(F^{k}_{\hat{x}}\leq\gamma^{k}_{\hat{x}}\) for all \(k\geq 1\)._ \begin{table}
\begin{tabular}{c c c} \hline \hline
**Instances** & \(\epsilon^{k+1}_{x}\) & \(\gamma^{k+1}_{x}\) \\ \hline Ex & 0 & \(+\infty\) \\ PI & 0 & \(F^{k}_{\hat{x}}-\theta\kappa v_{k}\) \\ IE & \(\varepsilon>0\) & \(+\infty\) \\ AE & \(\kappa_{\epsilon}v_{k}\) & \(+\infty\) \\ PAE & \(\kappa_{\epsilon}v_{k}\) & \(F^{k}_{\hat{x}}-\theta\kappa v_{k}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The choices for the error bound and the descent target. Proof. : For instances Ex, IE and AE, since \(\gamma_{x}^{k}=+\infty\), the claim holds immediately. For instances PI and PAE, we have \(\gamma_{x}^{k+1}=F_{\hat{x}}^{k}-\theta xv_{k}\). Thus, for \(k=1\), from Step 0 it follows that \(\hat{x}^{1}=x^{1}\), \(f_{\hat{x}}^{1}=f_{x}^{1}\) and \(\gamma_{\hat{x}}^{1}=\gamma_{x}^{1}=+\infty\). This implies \(F_{\hat{x}}^{1}=f_{\hat{x}}^{1}+h(\hat{x}^{1})\leq\gamma_{\hat{x}}^{1}\). In addition, for \(k\geq 2\), since \(\theta\in(0,1)\), once the descent test (16) is satisfied at iteration \(k-1\), we have  
\[F_{\hat{x}}^{k}\leq F_{\hat{x}}^{k-1}-\kappa v_{k-1}\leq F_{\hat{x}}^{k-1}- \theta xv_{k-1}=\gamma_{x}^{k}=\gamma_{\hat{x}}^{k}.\]  
The following lemma shows that an (approximate) optimal solution can be obtained whenever the algorithm terminates finitely or loops infinitely between Steps 2 and 5. **Lemma 3**. : _If either Algorithm 1 terminates at the \(k\)th iteration at Step 4, or loops between Steps 2 and 5 infinitely, then_  
1. \(\hat{x}^{k}\) _is an optimal solution to problem (_1_) for instances Ex and PI._
2. \(\hat{x}^{k}\) _is_ \(\varepsilon\)_-optimal, that is,_ \(F(\hat{x}^{k})\leq F_{*}+\varepsilon\)_, for instance IE._
3. \(\hat{x}^{k}\) _is_ \(\varepsilon_{x}^{k(l)}\)_-optimal, that is,_ \(F(\hat{x}^{k})\leq F_{*}+\varepsilon_{x}^{k(l)}\)_, for instances AE and PAE._  
Proof. : Firstly, suppose that Algorithm 1 terminates at Step 4 with iteration \(k\). Then from (23), we have \(V_{k}=0\). This together with (24) shows that  
\[F_{\hat{x}}^{k}\leq\inf\{F(x):\ x\in\mathbb{R}^{n}\}=F_{*}. \tag{29}\]  
Thus, from (7), we can conclude that: \(F(\hat{x}^{k})=F_{\hat{x}}^{k}\leq F_{*}\) for instances Ex and PI; \(F(\hat{x}^{k})\leq F_{\hat{x}}^{k}+\varepsilon\leq F_{*}+\varepsilon\) for instance IE; \(F(\hat{x}^{k})\leq F_{\hat{x}}^{k}+\varepsilon_{x}^{k(l)}\leq F_{*}+\varepsilon _{x}^{k(l)}\) for instances AE and PAE. Secondly, suppose that Algorithm 1 loops between Steps 2 and 5 infinitely. Then from Lemma 2 and the condition at Step 5, it follows that (28) holds and \(t_{k}\uparrow\infty\). Thus, we obtain \(V_{k}\to 0\). This along with (24) implies (29), and therefore the claims hold by repeating the corresponding lines in first case. From the above lemma, in what follows, we may assume that Algorithm 1 neither terminates finitely nor loops infinitely between Steps 2 and 5. In addition, as in Reference [22], we assume that the model subgradients \(p_{f}^{k}\in\partial\tilde{f}_{k}(y^{k+1})\) in (17) satisfy that \(\{p_{f}^{k}\}\) is bounded if \(\{y^{k}\}\) is bounded. Algorithm 1 must take only one of the following two cases:  
1. the algorithm generates finitely many descent steps;
2. the algorithm generates infinitely many descent steps.