and $R > 0$. Set $k=0, \sigma_0 = 0, f_{-1}^{rec} = \infty, \ell=0, k(\ell) = 0$.

Step 1.

:   If $f(x_k) < f_{k-1}^{rec},$ set $f_{k}^{rec} = f(x_k)$ and $x_{k}^{rec}= x_k,$ else set $f_{k}^{rec} = f_{k-1}^{rec}$ and $x_{k}^{rec}=x_{k-1}^{rec}$

Step 2.

:   If $0\in \partial f(x_k)$, then [**stop**]{}.

Step 3.

:   If $f(x_k) \leq f_{k(\ell)}^{rec} - \frac{1}{2} \delta_\ell $, set $k(\ell+1) = k, \sigma_k = 0, \delta_{\ell+1} = \delta_\ell$, replace $\ell$ by $\ell+1,$ and go to Step 5.

Step 4.

:   If $\sigma_k > R$, set $k(\ell+1) = k, \sigma_k = 0, \delta_{\ell+1} = \frac{1}{2} \delta_\ell$, $x_k=x_k^{rec}$, and $\ell\leftarrow\ell+1$.

Step 5.

:   Set $f_k^{lev} := f_{k(\ell)}^{rec} - \delta_\ell$. Select $\beta_k \in [\underline{\beta}, \bar{\beta}]$ and calculate $x_{k+1}$ via Algorithm \[Alg:INP\] with the stepsize given by Rule \[Dynamic.Step\].

Step 6.

:   Set $\sigma_{k+1}:= \sigma_k + \tilde{t}_k$, $k\leftarrow k+1$, and go to Step 1.

Following [@GoffinKiwiel1999; @nedic_bertsekas2001rate; @nedic_bertsekas2001; @xmwang2018], we describe the main features of the Subgradient-InexP method.

\[eq:bfkrec\] Note that in Step 1, $f_{k}^{rec}$ keeps the record of the smallest functional value attained by the iterates generated so far, i.e., $f_{k}^{rec}:=\min\{f(x_j):~j=0, \ldots,k\}$. Splitting the iterations into groups $$K_\ell := \{k(\ell), k(\ell) + 1, \ldots, k(\ell+1)-1\}, \quad \ell = 0, 1, \dots,$$ Algorithm \[Alg:INPDyn\] uses 