optimal solution of $\x^*$, and (c) $\gamma_D^0$ depends only on the $\c$.

Now, we present a upper bound in terms of only $\delta$ and $\gamma$.

Assume that the $k$th iterate generated by Algorithm \[mainAlg\] is not an optimizer. Let $$t = m \frac{\gamma}{\delta}
\log\left( m \frac{\gamma}{\delta} \right)
\label{tIter}$$ then there is a $\bar{j} \in B^k$, a corresponding $x_{\bar{j}}^k>0$, after at most another $\lceil t \rceil$ iterations, $x_{\bar{j}}^{k+t}$ becomes zero and stay zero since then. \[thm2\]

In view of (\[est1\]) in Lemma \[firstL\], since $\x^*$ has at most $m$ nonzero elements and $\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* \ge -\gamma_D^k (m \gamma)$, we have $${\c}^{\Tr} \x^k -z^* \le m \gamma \gamma_D^k.$$ Using this inequality, together with (\[myIneq1\]) in Lemma \[diffObj\] and (\[enteringVar\]), we have $$\begin{aligned}
\c^{\Tr} \x^k - \c^{\Tr} \x^{k+1} 
& = & - \bar{\c}_{(\jmath_1^k,\jmath_2^k)}^{\T}
\bar{\x}_{(\jmath_1^k,\jmath_2^k)}  
\nonumber \\
& \ge &  -\bar{c}_{\jmath_1^k}\bar{x}_{\jmath_1^k}
\nonumber \\
& \ge &  \gamma_D^k \delta
\nonumber \\
& \ge &  \frac{\delta}{m\gamma}
\left( {\c}^{\Tr} \x^k -z^*  \right).
\nonumber $$ This shows $$\begin{aligned}
\c^{\Tr} \x^k - z^* - (\c^{\Tr} \x^{k+1} -z^*)
\ge  \frac{\delta}{m\gamma}
\left( {\c}^{\Tr} \x^k -z^*  \right)
\nonumber $$ or equivalently $$\begin{aligned}
\c^{\Tr} \x^{k+1} -z^*
\le  \left( 1 - \frac{\delta}{m\gamma} \right)
\left( {\c}^{\Tr} \x^k -z^*  \right).
\nonumber $$ Therefore, for any integer $t>0$, 