rate statement for Algorithm \[algorithm:IRIG\].

\[**[A rate statement for Algorithm \[algorithm:IRIG\]]{}\] \[thm rate\] Assume $\{\bar x_N\}$ is generated by Algorithm \[algorithm:IRIG\] to solve problem . Let Assumption \[assum:properties\] and \[assumptions for conv INC\] hold and also $0<\epsilon<0.5$ and $r<1$ be arbitrary constants. Assume for $0<\epsilon<0.5$, $\{\gamma_k\}$ and $\{\lambda_k\}$ are sequences defined as $$\gamma_k=\frac{\gamma_0}{(k+1)^{0.5+0.5\epsilon}} \hbox{ and } \lambda_k=\frac{\lambda_0}{(k+1)^{0.5-\epsilon}},$$ such that $\gamma_0$ and $\lambda_0$ are positive scalars and $\gamma_0\lambda_0 \mu_h \leq 2m$. Then,\
(a) The sequence $\{\bar x_N\}$ converges to the unique optimal solution of problem , i.e., $x_h^*$.\
(b) $f(\bar x_N)$ converges to $f^*$ with the rate ${\cal O}\left(1/N^{0.5-\epsilon}\right)$.**

Throughout, we set $a:=0.5+0.5\epsilon$, $b:=0.5-\epsilon$.

\(a) From the values of $a$ and $b$, and that $r<1$ and $0<\epsilon<0.5$, we have $$\begin{aligned}
    a>b>0,\ a>0.5, \ a+b=1-0.5\epsilon<1,\\ ar= 0.5(1+\epsilon)r <0.5(1.5)=0.75<1.
    \end{aligned}$$ This implies that all conditions of Theorem \[thm conv for xbar INC\] are satisfied. Therefore, $\{\bar x_N\}$ converges to $x_h^*$ almost surely.

\(b) Since $\{\lambda_k\}$ is a non-increasing sequence from Lemma \[lemma averaging\] we have $$\begin{aligned}
&f(\bar x_N) - f^*  \leq   \left(\sum_{k=0}^{N-1} \gamma_k^r\right)^{-1} \left( m \left(C_f^2 + \lambda_0^2 C_h^2\right) \sum_{k=0}^{N-1} \gamma_k^{r+1}  \right. \cr\\& \left. 
+m^2 C_f\left( C_f + \lambda_0 C_h \right) \sum_{k=0}^{N-1} \gamma_k^{r+1} + 2 M_h   \sum_{k=0}^{N-1} \lambda_k \gamma_k^r + 2M^2\gamma_{N-1}^{r-1} \right). \end{aligned}$$ 