Recall that
$$\begin{aligned} {\hat{r}}_{b+1} = {\hat{r}}_b - \lambda \sum _{j=0}^p\sum _{i=1}^m \frac{n^{-1}\left\langle {\hat{r}}_b, g_{R^j_i, j} \right\rangle _n}{n^{-1}\left\| h_{R^j_i} \right\| _n^2}g_{R^j_i,j} ={\hat{r}}_b - \lambda \sum _{i=1}^{m(p+1)} \frac{n^{-1}\left\langle {\hat{r}}_b, g_{b, i} \right\rangle _n}{n^{-1}\left\| h_{b,i} \right\| _n^2} g_{b,i}, \end{aligned}$$
and
$$\begin{aligned} r_{b+1} =r_b - \lambda \sum _{j=0}^p\sum _{i=1}^m \frac{\left\langle r_b, g_{R^j_i, j} \right\rangle }{\left\| h_{R^j_i} \right\| ^2}g_{R^j_i,j} = r_b - \lambda \sum _{i=1}^{m(p+1)} \frac{\left\langle r_b, g_{b, i} \right\rangle }{\left\| h_{b,i} \right\| ^2} g_{b,i}. \end{aligned}$$
Therefore
$$\begin{aligned} {\hat{r}}_{b+1} - r_{b+1}&= ({\hat{r}}_b - r_b) + \lambda \sum _{j=0}^p\sum _{i=1}^m \left( \frac{\left\langle r_b, g_{R^j_i, j} \right\rangle }{\left\| h_{R^j_i} \right\| ^2} - \frac{n^{-1}\left\langle {\hat{r}}_b, g_{R^j_i, j} \right\rangle _n}{n^{-1}\left\| h_{R^j_i} \right\| _n^2} \right) g_{R^j_i, j} \\&= ({\hat{r}}_b - r_b) + \lambda \sum _{i=1}^{m(p+1)} \left( \frac{\left\langle r_b, g_{b,i} \right\rangle }{\left\| h_{b,i} \right\| ^2} - \frac{n^{-1}\left\langle {\hat{r}}_b, g_{b,i} \right\rangle _n}{n^{-1}\left\| h_{b,i} \right\| _n^2}\right) g_{b,i}\\&\triangleq ({\hat{r}}_b - r_b) + \lambda \delta _{b} \\&= ({\hat{r}}_0 - r_0)+\lambda \sum _{j=0}^b \delta _j = \epsilon + \lambda \sum _{j=0}^b \delta _j. \end{aligned}$$
Since for each fixed
j, all
\(R_i^j\) are disjoint, we therefore define that
$$\begin{aligned} \gamma _b = \sum _{j=0}^{p} \sup _{i=1,\dots , m} \left| \frac{\left\langle r_b, g_{R^j_i, j} \right\rangle }{\left\| h_{R^j_i} \right\| ^2} - \frac{n^{-1}\left\langle {\hat{r}}_b, g_{R^j_i, j} \right\rangle _n}{n^{-1}\left\| h_{R^j_i} \right\| _n^2} \right| , \end{aligned}$$
which guarantees
\(\sup _{x,z} |\delta _b| \le \gamma _b\). To bound
\(\gamma _b\), without loss of generality, we consider a single term involved such that
$$\begin{aligned} \frac{\left\langle r_b, g_{b} \right\rangle }{\left\| h_{b} \right\| ^2} - \frac{n^{-1}\left\langle {\hat{r}}_b, g_{b} \right\rangle _n}{n^{-1}\left\| h_{b} \right\| _n^2}&\triangleq \left( \frac{u}{v} - \frac{{\hat{u}}}{{\hat{v}}}\right) \\&= \left( \frac{u-{\hat{u}}}{v} + \left( \frac{1}{v}-\frac{1}{{\hat{v}}}\right) {\hat{u}}\right) . \end{aligned}$$
First consider
$$\begin{aligned} {\hat{u}} - u&= \frac{1}{n} \left\langle {\hat{r}}_b, g_{b} \right\rangle _n - \left\langle r_b, g_{b} \right\rangle \\&= \frac{1}{n} \left\langle \epsilon + r_b + \sum _{j=0}^{b-1}\delta _j, g_b \right\rangle _{n} - \left\langle r_b, g_{b} \right\rangle \\&= \frac{1}{n} \left\langle \epsilon , g_b \right\rangle _n + \left( \frac{1}{n}\left\langle r_b, g_b \right\rangle _n - \left\langle r_b, g_b \right\rangle \right) + \left( \sum _{j=0}^{b-1} \frac{1}{n}\left\langle \delta _j, g_b \right\rangle _n\right) . \end{aligned}$$
Per Lemma
3, we have
$$\begin{aligned} \left| \frac{1}{n} \left\langle \epsilon , g_b \right\rangle _n\right| \le \xi _n \end{aligned}$$
and, by iteratively applying Lemma
3 and setting
\(C_0 = \max (\sup _{x,z} |f|, 1),\)$$\begin{aligned}&\left| \frac{1}{n}\left\langle r_b, g_b \right\rangle _n - \left\langle r_b, g_b \right\rangle \right| \\&\quad = \left| \frac{1}{n}\left\langle f - \lambda \sum _{j=0}^{b-1}\sum _{i=1}^{m(p+1)}\frac{\left\langle r_j, g_{j, i} \right\rangle }{\left\| h_{j,i} \right\| ^2} g_{j,i}, g_b \right\rangle _n \right. \\&\qquad \left. - \left\langle f - \lambda \sum _{j=0}^{b-1}\sum _{i=1}^{m(p+1)}\frac{\left\langle r_j, g_{j, i} \right\rangle }{\left\| h_{j,i} \right\| ^2} g_{j,i}, g_b \right\rangle \right| \\&\quad \le \left| \frac{1}{n}\left\langle f, g_b \right\rangle _n - \left\langle f, g_b \right\rangle \right| + \lambda \sum _{j=0}^{b-1}\sum _{i=1}^{m(p+1)} \left| \frac{1}{n}\left\langle \frac{\left\langle r_j, g_{j, i} \right\rangle }{\left\| h_{j,i} \right\| ^2} g_{j,i}, g_b \right\rangle _n \right. \\&\qquad \left. - \left\langle \frac{\left\langle r_j, g_{j, i} \right\rangle }{\left\| h_{j,i} \right\| ^2} g_{j,i}, g_b \right\rangle \right| \\&\quad \le \left| \frac{1}{n}\left\langle f, g_b \right\rangle _n - \left\langle f, g_b \right\rangle \right| + \lambda \sum _{j=0}^{b-1}\sum _{i=1}^{m(p+1)} \left| \frac{\left\langle r_j, g_{j, i} \right\rangle }{\left\| h_{j,i} \right\| ^2}\right| \left| \frac{1}{n}\left\langle g_{j,i}, g_b \right\rangle _n - \left\langle g_{j,i}, g_b \right\rangle \right| \\&\quad \le \xi _n + \lambda \sum _{j=0}^{b-1} \sup |r_j| m(p+1) \xi _n \\&\quad \le \xi _n + C_0\sum _{j=0}^{b-1} 2^j m \xi _n \\&\quad \le C_02^bm\xi _n. \end{aligned}$$
The last term could be bounded by
$$\begin{aligned} \left| \sum _{j=0}^{b-1} \frac{1}{n}\left\langle \delta _j, g_b \right\rangle _n\right|&\le \frac{1}{n} \sum _{j=0}^{b-1} \left\| \delta _j \right\| _{n,\infty } \left\| g_b \right\| _{n,1} \le \frac{1}{n}\sum _{j=0}^{b-1} \gamma _j \left\| h_b \right\| _{n}^2, \end{aligned}$$
where
$$\begin{aligned} \left\| g_b \right\| _{n,1} = \sum _{i=1}^n |g_b(x_i)|,\quad \left\| \delta _j \right\| _{n,\infty } = \sup _{i=1,\dots , n} |\delta _j(x_i)|. \end{aligned}$$
Hence
$$\begin{aligned} |{\hat{u}} - u| \le C_02^bm\xi _n + \frac{1}{n}\sum _{j=0}^{b-1} \gamma _j \left\| h_b \right\| _{n}^2. \end{aligned}$$
In order to bound
\(|{\hat{u}}|\), we notice
$$\begin{aligned} |{\hat{u}}| = \left| \frac{1}{n}\left\langle {\hat{r}}_b, g_{b} \right\rangle _n\right|&\le \left( \frac{1}{n}\left\| {\hat{r}}_n \right\| _n^2\right) ^{\frac{1}{2}}\cdot \left( \frac{1}{n}\left\| g_b \right\| _n^2\right) ^{\frac{1}{2}}\\&\le \left( \frac{1}{n}\left\| {\hat{r}}_0 \right\| _n^2\right) ^{\frac{1}{2}}\cdot \left( \frac{1}{n}\left\| g_b \right\| _n^2\right) ^{\frac{1}{2}}\\&= \left( \frac{1}{n}\left\| f+\epsilon \right\| _n^2\right) ^{\frac{1}{2}}\cdot \left( \frac{1}{n}\left\| g_b \right\| _n^2\right) ^{\frac{1}{2}}\\&\le (M+\sigma ^2_{\epsilon } + \xi _n) \cdot \left\| g_b \right\| \\&\le (M_0 + \xi _n) \cdot \left\| h_b \right\| . \end{aligned}$$
Therefore, we get an upper bound for
$$\begin{aligned}&\left| \frac{\left\langle r_b, g_{b} \right\rangle }{\left\| h_{b} \right\| ^2} - \frac{n^{-1}\left\langle {\hat{r}}_b, g_{b} \right\rangle _n}{n^{-1}\left\| h_{b} \right\| _n^2} \right| \\&\quad \le \frac{|{\hat{u}}-u|}{|v|} + \left| \frac{1}{v} - \frac{1}{{\hat{v}}}\right| |{\hat{u}}| \\&\quad =\frac{C_02^bm\xi _n + n^{-1}\sum _{j=0}^{b-1} \gamma _j \left\| h_b \right\| _{n}^2}{\left\| h_b \right\| ^2} + \frac{\xi _n \cdot (M_0+\xi _n) \cdot \left\| h_b \right\| }{\left\| h_b \right\| ^2 \cdot n^{-1}\left\| h_b \right\| _n^2}\\&\quad \le \frac{C_02^bm\xi _n}{\left\| h_b \right\| ^2} + \sum _{j=0}^{b-1} \gamma _j \left( 1 + \frac{\xi _n}{\left\| h_b \right\| ^2}\right) + \frac{\xi _n(M_0 + \xi _n)}{\left\| h_b \right\| (\left\| h_b \right\| ^2-\xi _n)}. \end{aligned}$$
Denote
h be the global minimum of the ensemble that
\(h = \min _{b,i,j} \left\| h_{R^j_i} \right\| \), since
\(m \le (h^2-\xi _n)^{-1}\), we obtain
$$\begin{aligned} \gamma _b&\le (p+1) \left( \frac{C_02^b\xi _n}{h^2(h^2-\xi _n)} + \sum _{j=0}^{b-1} \gamma _j \left( 1 + \frac{\xi _n}{h^2}\right) + \frac{\xi _n(M_0 + \xi _n)}{h(h^2-\xi _n)} \right) . \end{aligned}$$
We would like to mention the elementary result that for a series
\(\{x_n\}\) satisfying
$$\begin{aligned} x_n \le 2^na + \sum _{i=0}^{n-1}bx_i + c, \end{aligned}$$
the partial sums satisfy
$$\begin{aligned} \sum _{i=0}^n x_n \le a\left( \frac{1-\left( \frac{2}{1+b}\right) ^{n+1}}{1-\frac{2}{1+b}} \right) (1+b)^n - \frac{c}{b}. \end{aligned}$$
Hence, we can verify this upper bound that
$$\begin{aligned}&\sum _{j=0}^{B-1} \gamma _j \le (1+p)^B\left( \frac{C_0}{h^2-\xi _n}\left( 2+\frac{\xi _n}{h^2}\right) ^{B}\left( 1-\left( 1-\frac{\frac{\xi _n}{h^2}}{2+\frac{\xi _n}{h^2}}\right) ^{B-1} \right) \right. \\&\quad \left. - \frac{\xi _n(M_0+\xi _n)}{h(h^2-\xi _n)\left( 1+\frac{\xi _n}{h^2}\right) }\right) \end{aligned}$$
Recall the rates that
\(B = o(\log n), h^2 = O_{p}\left( n^{-\frac{1}{4}+\eta }\right) , \xi _n = O_{p}\left( n^{-\frac{1}{2}}\right) \), thus
$$\begin{aligned}&\left( 2+\frac{\xi _n}{h^2}\right) ^B = 2^B \cdot O_{p}\left( 1\right) , \quad 1-\left( 1-\frac{\frac{\xi _n}{h^2}}{2+\frac{\xi _n}{h^2}}\right) ^{B-1} = \frac{\xi _n}{h^2} \cdot O_{p}\left( 1\right) , \\&\quad \frac{\xi _n(M_0+\xi _n)}{h(h^2-\xi _n)\left( 1+\frac{\xi _n}{h^2}\right) } = \frac{\xi _n}{h^3}\cdot O_{p}\left( 1\right) . \end{aligned}$$
Hence,
$$\begin{aligned} \sum _{j=0}^{B-1} \gamma _j&\le (1+p)^B \left( \frac{ C_0}{h^2} \cdot 2^B \cdot \frac{\xi _n}{h^2} - \frac{\xi _n}{h^3}\right) O_{p}\left( 1\right) = o_p(1), \end{aligned}$$
which is equivalent to
$$\begin{aligned} \left\| \sum _{j=0}^{B-1}\delta _j \right\| \le \sum _{j=0}^{B-1}\left\| \delta _j \right\| \le \sum _{j=0}^{B-1}\gamma _j = o_{p}\left( 1\right) . \end{aligned}$$
Combining all above we have
$$\begin{aligned} \left\| {\hat{r}}_B \right\| ^2&= \left\| r_B + \epsilon + \lambda \sum _{j=0}^{B-1} \delta {j} \right\| ^2 \\&\le \left\| \epsilon \right\| ^2 + \left\| r_B \right\| ^2 + \lambda ^2 \left\| \sum _{j=0}^{B-1}\delta _j \right\| ^2 + 2 \lambda \left\| r_B+\epsilon \right\| \left\| \sum _{j=0}^{B-1}\delta _j \right\| \\&=\sigma _{\epsilon }^2 + \left\| r_B \right\| ^2 + o_{p}\left( 1\right) . \end{aligned}$$
\(\square \)