Lemma 3.7. The number of iterations for the FW Algorithm to reach an iterate $u$ with $\delta(u)\le1$ is at most
(ii) $4n(\ln\ln n + 7/2)$ if the initial iterate is $u_{KY}$
Proof. Consider any iteration proceeding from the iterate $u$ with $\delta \triangleq \delta(u) \ge 1$ to the next iterate $u_+$ , and let $\gamma \triangleq g^{\ast}-g(u)$ and $\gamma_+ \triangleq g^{\ast}-g(u_+)$ denote the corresponding optimality gaps. From Lemmas 3.4 and 3.6 we have
$$
\gamma-\gamma_+=g(u_+)-g(u)\ge\ln(1+\delta)-\frac{\delta}{1+\delta} \ge \frac14 \ln(1+\delta) \ge \frac1{4n} \gamma \tag{3.3.2}
$$
where the last inequality follows from Proposition 2.9. We conclude that
$$
\gamma_+ \le \left(1-\frac1{4n} \right)\gamma \le \exp\left(-\frac1{4n}\right)\gamma
$$
Since the initial value of $\gamma$ is at most $5n\ln n$ if we use $u_{KY}$ from Proposition 3.5, we deduce that within
$$
4n\ln \left( \frac{5n \ln n}{n} \right)= 4n \left(\ln\ln n +ln5\right)\le 4n(\ln\ln n +2)
$$
iterations, $\gamma$ is at most $n$. Moreover, while $\delta$ is at least $1$, $\gamma$ decreases by at least $1/6$, so since $\gamma$ remains nonnegative, at most $n/(1/6)=6n$ further iterations are possible. This establishes (ii).