c(1+c)}{2\eta(c-1)}W^{t}+\frac{\eta}{2\gamma}\|\tilde{g}^{t}_{S^{t+1}}-g^{t}_{S^{t+1}}\|_{2}^{2}+c\|\tilde{w}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\qquad+\frac{(2c+3)\eta}{\gamma}(\|{g}^{t}_{S^{t}\backslash
S^{t+1}}-\tilde{g}^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}+\|{g}^{t}_{S^{t+1}\backslash
S^{t}}-\tilde{g}^{t}_{S^{t+1}\backslash S^{t}}\|_{2}^{2})$
$\displaystyle=\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash
S^{t}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+\frac{1}{c}(\frac{1}{4}+\frac{\eta}{2\gamma}+\frac{\eta}{2\gamma}\frac{3c+1}{(c-1)})\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle+\underbrace{\frac{\gamma
c(1+c)}{2\eta(c-1)}W^{t}+\frac{\eta}{2\gamma}\|\tilde{g}^{t}_{S^{t+1}}-g^{t}_{S^{t+1}}\|_{2}^{2}+c\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+\frac{(2c+3)\eta}{\gamma}(\|{g}^{t}_{S^{t}\backslash
S^{t+1}}-\tilde{g}^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}+\|{g}^{t}_{S^{t+1}\backslash
S^{t}}-\tilde{g}^{t}_{S^{t+1}\backslash S^{t}}\|_{2}^{2})}_{N^{t}}$
$\displaystyle\leq\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash
S^{t}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+C_{1}\frac{\eta}{\gamma
c}\|g^{t}_{S^{t+1}}\|_{2}^{2}+N^{t},$ (54)

where $C_{1}>0$ is some constant. We can easily see that

$\displaystyle\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash
S^{t}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle=-\frac{\eta}{2\gamma}\|g^{t}_{S^{t}\backslash
S^{t+1}}\|_{2}^{2}-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\bigcap
S^{t}}\|_{2}^{2}$ $\displaystyle=-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\bigcup
S^{t}}\|_{2}^{2}$

In total

$\langle
w^{t+0.75}-w^{t},g^{t}\rangle\leq-\frac{\eta}{2\gamma}\|g^{t}_{S^{t+1}\bigcup
S^{t}}\|_{2}^{2}+C_{1}\frac{\eta}{\gamma c}\|g^{t}_{S^{t+1}}\|_{2}^{2}+N_{1}.$
(55)

Take (55) into (46) we have

$\displaystyle
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{t})\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}}\|_{2}^{2}+(1-\eta)\langle
w^{t+0.75}-w^{t},g^{t}\rangle$
$\displaystyle\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}}\|_{2}^{2}-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\bigcup
S^{t}}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\qquad+(1-\eta)N^{t}$
$\displaystyle\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\bigcup
S^{t}}\|_{2}^{2}$
$\displaystyle+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+(1-\eta)N^{t}$
$\displaystyle\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}$
$\displaystyle-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+(1-\eta)N^{t},$
(56)

where the last inequality is due to $S^{t+1}\backslash(S^{*}\bigcup
S^{t})\subseteq S^{t+1}\bigcup S^{t}$. Next we will analyze the term
$\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}$ in (56). Let $R$ be a subset of ${S^{t}\backslash S^{t+1}}$
such that $|R|=|I^{t}\backslash(S^{*}\bigcup
S^{t})|=|S^{t+1}\backslash(S^{t}\bigcup S^{*})|$. In Lemma 12, we take
$v=w^{t}-\frac{\eta}{\gamma}\tilde{g}^{t}$, $R_{2}=R$ and
$R_{1}=I^{t}\backslash(S^{*}\bigcup S^{t})$ we have for $c>1$,

$\|w^{t}_{R}-\frac{\eta}{\gamma}\tilde{g}^{t}_{R}\|_{2}^{2}\leq(1+c)\|(w^{t}-\frac{\eta}{\gamma}\tilde{g}^{t})_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+(1+\frac{1}{c})W^{t}.$ (57)

Just as in (52) we have is for $c>1$,

$(\frac{\eta}{\gamma})^{2}\|g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}\geq(1-\frac{1}{c})\|w^{t}_{R}-\frac{\eta}{\gamma}g^{t}_{R}\|_{2}^{2}-cW^{t}-c\frac{\eta^{2}}{\gamma^{2}}(\|\tilde{g}^{t}_{R}-g^{t}_{R}\|_{2}^{2}+\|g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}-\tilde{g}^{t}_{I^{t}\backslash(S^{*}\bigcup S^{t})}\|_{2}^{2}).$ (58)

Then we have

$\displaystyle\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}$
$\displaystyle\leq\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+\frac{\gamma}{2}\|\hat{w}^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\gamma}{2}(1-\frac{1}{c})\|w^{t}_{R}-\frac{\eta}{\gamma}g^{t}_{R}\|_{2}^{2}+\frac{\gamma
c}{2}W^{t}$
$\displaystyle+c\frac{\eta^{2}}{2\gamma}(\|\tilde{g}^{t}_{R}-g^{t}_{R}\|_{2}^{2}+\|g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}-\tilde{g}^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2})+c\frac{\eta^{2}}{\gamma^{2}}(\|\tilde{g}^{t}_{R}-g^{t}_{R}\|_{2}^{2}$
(59)
$\displaystyle=\frac{\gamma}{2}\|\hat{w}^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\gamma}{2}\|\hat{w}^{t+0.75}_{R}-w^{t}_{R}+\frac{\eta}{\gamma}g^{t}_{R}\|_{2}^{2}+\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+\frac{\gamma
c}{2}W^{t}$
$\displaystyle+\frac{\gamma}{2c}\|w^{t}_{R}-\frac{\eta}{\gamma}g^{t}_{R}\|_{2}^{2}+c\frac{\eta^{2}}{2\gamma}(\|\tilde{g}^{t}_{R}-g^{t}_{R}\|_{2}^{2}+\|g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}-\tilde{g}^{t}_{I^{t}\backslash(S^{*}\bigcup S^{t})}\|_{2}^{2})$ (60)
$\displaystyle\leq\frac{\gamma}{2}\|\hat{w}^{t+0.75}_{I^{t}\backslash
R}-w^{t}_{I^{t}\backslash R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash
R}\|_{2}^{2}+\frac{\gamma}{2c}(1+\frac{1}{c})\|\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle+\underbrace{\frac{\gamma
c}{2}W^{t}+\frac{\gamma}{2c}(1+c)W^{t}+C_{2}c\frac{\eta^{2}}{2\gamma}(\|\tilde{g}^{t}_{R}-g^{t}_{R}\|_{2}^{2}+\|g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}-\tilde{g}^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2})}_{N_{1}^{t}}.$ (61)

(59) is due to that
$[\hat{w}^{t+0.75}_{I^{t}}-(w^{t}_{I^{t}}-\frac{\eta}{\gamma}g^{t}_{I^{t}})]_{S^{t+1}}=0$,
thus
$\langle\tilde{w}_{S^{t+1}},\hat{w}^{t+0.75}_{I^{t}}-(w^{t}_{I^{t}}-\frac{\eta}{\gamma}g^{t}_{I^{t}})\rangle=0$
and (58). (60) is due to $\hat{w}^{t+0.75}_{R}=0$, (61) is due to (57) by the
same technique as in (52) and $w^{t}_{I^{t}\backslash(S^{*}\bigcup S^{t})}=0$.
In the following we will consider the first term in (61).

In Lemma 13, take $v=w^{t}_{I^{t}\backslash
R}-\frac{\eta}{\gamma}\tilde{g}^{t}_{I^{t}\backslash R}$, $\hat{v}=w^{*}$,
$S=S^{t+1}$ we have for all $c>1$

$\|\hat{w}^{t+0.75}_{I^{t}\backslash R}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}\tilde{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}\leq(1+\frac{1}{c})\frac{|I^{t}\backslash R|-s}{|I^{t}\backslash
R|-s^{*}}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}+(1+c)W^{t}.$

Then we have

$\displaystyle(1-\frac{1}{c})\|\hat{w}^{t+0.75}_{I^{t}\backslash
R}-w^{t}_{I^{t}\backslash R}+\frac{\eta}{\gamma}{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}-(c-1)\frac{\eta^{2}}{\gamma^{2}}\|g^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}$
$\displaystyle\leq\|\hat{w}^{t+0.75}_{I^{t}\backslash
R}-w^{t}_{I^{t}\backslash R}+\frac{\eta}{\gamma}\tilde{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}$ $\displaystyle\leq(1+\frac{1}{c})\frac{|I^{t}\backslash
R|-s}{|I^{t}\backslash R|-s^{*}}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}+(1+c)W^{t}$
$\displaystyle\leq(1+\frac{1}{c})\frac{|I^{t}\backslash R|-s}{|I^{t}\backslash
R|-s^{*}}[(1+\frac{1}{c})\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}+(1+c)\frac{\eta^{2}}{\gamma^{2}}\|{g}^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}]+(1+c)W^{t}$

That is

$\|\hat{w}^{t+0.75}_{I^{t}\backslash R}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}\leq\frac{(c+1)^{2}}{c(c-1)}\frac{2s^{*}}{s+s^{*}}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash R}\|_{2}^{2}\\\
+\frac{(c+1)^{2}}{c-1}\frac{\eta^{2}}{\gamma^{2}}\|{g}^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash
R}\|_{2}^{2}+c\frac{\eta^{2}}{\gamma^{2}}\|g^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}+\frac{(1+c)c}{c-1}W^{t}$

Take $c\geq\frac{\sqrt{3}}{\sqrt{3}-\sqrt{2}}$, and since $|I^{t}\backslash
R|\leq 2s^{*}+s$, we have

$\displaystyle\|\hat{w}^{t+0.75}_{I^{t}\backslash R}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash
R}\|_{2}^{2}\leq\frac{3}{2}\frac{2s^{*}}{s+s^{*}}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash R}\|_{2}^{2}$
$\displaystyle+\underbrace{C_{3}c(\|{g}^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}+\|g^{t}_{I^{t}\backslash
R}-\tilde{g}^{t}_{I^{t}\backslash R}\|_{2}^{2}+W^{t})}_{N_{3}^{t}}.$ (62)

Take (A) into (61) we have

$\displaystyle\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}$ $\displaystyle\leq\frac{3\gamma
s^{*}}{2(s+s^{*})}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash
R}\|_{2}^{2}+\frac{\gamma}{2c}(1+\frac{1}{c})\|\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle+N_{1}^{t}+N_{3}^{t}$ (63) $\displaystyle=\frac{3\gamma
s^{*}}{2(s+s^{*})}\|w^{*}-w^{t}_{I^{t}\backslash
R}+\frac{\eta}{\gamma}g^{t}_{I^{t}\backslash
R}\|_{2}^{2}+\frac{\gamma}{2c}(1+\frac{1}{c})\|\frac{\eta}{\gamma}g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\qquad+\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+N_{1}^{t}+N_{3}^{t}$
(64) $\displaystyle=\frac{3s^{*}}{s+s^{*}}(\eta\langle
w^{*}-w^{t},g^{t}\rangle+\frac{\gamma}{2}\|w^{*}-w^{t}\|_{2}^{2}+\frac{\eta^{2}}{2c\gamma}\|g^{t}_{I^{t}}\|_{2}^{2})+\frac{\eta^{2}}{2c\gamma}(1+\frac{1}{c})\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\qquad+\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+N_{1}^{t}+N_{3}^{t}$
(65)
$\displaystyle\leq\frac{3s^{*}}{s+s^{*}}(\eta(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+\frac{\gamma-\eta\mu}{2}\|w^{*}-w^{t}\|_{2}^{2}+\frac{\eta^{2}}{2c\gamma}\|g^{t}_{I^{t}}\|_{2}^{2})+\frac{\eta^{2}}{2c\gamma}(1+\frac{1}{c})\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\qquad+\underbrace{\frac{\gamma}{2}\|\tilde{w}_{S^{t+1}}\|_{2}^{2}+N_{1}^{t}+N_{3}^{t}}_{N_{2}^{t}}.$
(66)

Take (66) into (56) we have

$\displaystyle
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{t})\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}$
$\displaystyle-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+(1-\eta)N^{t}$
$\displaystyle\leq\frac{3s^{*}}{s+s^{*}}(\eta(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+\frac{\gamma-\eta\mu}{2}\|w^{*}-w^{t}\|_{2}^{2}+\frac{\eta^{2}}{2c\gamma}\|g^{t}_{I^{t}}\|_{2}^{2})+\frac{\eta^{2}}{2c\gamma}(1+\frac{1}{c})\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle-\frac{\eta^{2}}{2\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}\|g^{t}_{S^{t+1}}\|_{2}^{2}+(1-\eta)N^{t}+N^{t}_{2}.$
(67)

We have when $c\rightarrow\infty$

$\displaystyle\frac{\eta^{2}}{2c\gamma}(1+\frac{1}{c})\|g^{t}_{S^{t+1}}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}\rightarrow
0.$

Thus, if $\eta\geq\frac{1}{2}$ there must exits a sufficient large $c$ such
that

$\displaystyle\frac{\eta^{2}}{2c\gamma}(1+\frac{1}{c})\|g^{t}_{S^{t+1}}\|_{2}^{2}+\frac{(1-\eta)}{c}(\frac{1}{4}+\frac{\eta}{2\gamma})\|g^{t}_{S^{t+1}}\|_{2}^{2}\leq\frac{\eta(1-\eta)}{4\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}$
$\displaystyle\leq\frac{\eta^{2}}{4\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}+\frac{(1-\eta)\eta}{4\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}$ (68)

Thus,

$\displaystyle
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{t})\leq\frac{\gamma}{2}\|w^{t+0.75}_{I^{t}}-w^{t}_{I^{t}}+\frac{\eta}{\gamma}g^{t}_{I^{t}}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{I^{t}\backslash(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\eta^{2}}{2\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}$
$\displaystyle-\frac{(1-\eta)\eta}{2\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+C_{1}\frac{(1-\eta)}{c}\frac{\eta}{\gamma}\|g^{t}_{S^{t+1}}\|_{2}^{2}+(1-\eta)N^{t}$
$\displaystyle\leq\frac{3s^{*}}{s+s^{*}}(\eta(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+\frac{\gamma-\eta\mu}{2}\|w^{*}-w^{t}\|_{2}^{2}+\frac{\eta^{2}}{2c\gamma}\|g^{t}_{I^{t}}\|_{2}^{2})$
$\displaystyle-\frac{\eta^{2}}{4\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{(1-\eta)\eta}{4\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+(1-\eta)N^{t}+N^{t}_{2}.$ (69)

Take $\eta=\frac{2}{3}$, $s=72\frac{\gamma^{2}}{\mu^{2}}s^{*}$ so that
$\frac{3s^{*}}{s+s^{*}}\leq\frac{\mu^{2}}{24\gamma(\gamma-\eta\mu)}\leq\frac{1}{8}$.
We have

$\displaystyle
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{t})\leq\frac{3s^{*}}{s+s^{*}}(\eta(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+\frac{\gamma-\eta\mu}{2}\|w^{*}-w^{t}\|_{2}^{2}+\frac{\eta^{2}}{2c\gamma}\|g^{t}_{I^{t}}\|_{2}^{2})$
$\displaystyle-\frac{\eta^{2}}{4\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{(1-\eta)\eta}{4\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+(1-\eta)N^{t}+N^{t}_{2}$
$\displaystyle\leq\frac{2s^{*}}{s+s^{*}}(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+\frac{\mu^{2}}{48\gamma}\|w^{*}-w^{t}\|_{2}^{2}+\frac{1}{36\gamma}\|g^{t}_{I^{t}}\|_{2}^{2}$
$\displaystyle\qquad-\frac{1}{9\gamma}\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{1}{18\gamma}\|g^{t}_{S^{t+1}\backslash(S^{*}\bigcup
S^{t})}\|_{2}^{2}+O(N^{t}+N^{t}_{2})$
$\displaystyle\leq\frac{2s^{*}}{s+s^{*}}(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))-\frac{3}{36\gamma}(\|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\mu^{2}}{4}\|w^{*}-w^{t}\|_{2}^{2})+O(N^{t}+N^{t}_{2})$
(70)
$\displaystyle\leq(\frac{2s^{*}}{s+s^{*}}+\frac{\mu}{24\gamma})(L_{\mathcal{D}}(w^{*})-L_{\mathcal{D}}(w^{t}))+O(N^{t}+N^{t}_{2}).$
(71)

Where (70) is due to the following lemma:

######  Lemma 14.

[Lemma 6 in [35]]

$|g^{t}_{(S^{t}\bigcup
S^{*})}\|_{2}^{2}-\frac{\mu^{2}}{4}\|w^{*}-w^{t}\|_{2}^{2}\geq\frac{\mu}{2}(L_{\mathcal{D}}(w^{t})-L_{\mathcal{D}}(w^{*})).$
(72)

Thus

$L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{*})\leq(1-\frac{5}{72}\frac{\mu}{\gamma})(L_{\mathcal{D}}(w^{t})-L_{\mathcal{D}}(w^{*}))+O(N^{t}+N^{t}_{2}).$

Where

$\displaystyle N^{t}+N^{t}_{2}\leq
O(\sum_{i\in[s]}\|w_{i}\|_{\infty}^{2}+(2s+s^{*})\|\tilde{g}^{t}-g^{t}\|_{\infty}^{2}+s\|\tilde{w}\|_{\infty}^{2}),$
(73)

where each coordinate of $w_{i},\tilde{w}$ sampled from
$\sim\text{Lap}(O(\frac{K^{2}\eta_{0}sT\sqrt{\log\frac{1}{\delta}}}{n\epsilon}))$.
We first bound the term of
$\sum_{i\in[s]}\|w_{i}\|_{\infty}^{2}+s\|\tilde{w}\|_{\infty}^{2}$. We recall
the following lemma:

######  Lemma 15 (Lemma A.1 in [13]).

For a random vector $w\in\mathbb{R}^{d}$, where
$w_{i}\sim\text{Lap}(\lambda)$, then for any $\zeta>0$,

$\text{Pr}(\|w\|^{2}_{\infty}\geq
4\lambda^{2}\log^{2}\frac{1}{\zeta}\log^{2}k)\leq\zeta.$

Take the union we have with probability at least $1-\zeta$,

$\sum_{i\in[s]}\|w_{i}\|_{\infty}^{2}+s\|\tilde{w}\|_{\infty}^{2}\leq
O(\frac{K^{4}\eta_{0}^{2}s^{3}T^{2}\log^{2}\frac{s}{\zeta}\log\frac{1}{\delta}}{n^{2}\epsilon^{2}}).$

For $s\|\tilde{g}^{t}-g^{t}\|_{\infty}^{2}$, follow the proof of Lemma 8, we
can see that when $K=\frac{{(n\epsilon)^{\frac{1}{4}}}}{(Ts)^{\frac{1}{4}}}$
with probability at least $1-\zeta$,

$s\|\tilde{g}^{t}-g^{t}\|_{\infty}^{2}\leq
O(\frac{sTM\log\frac{d}{\zeta}}{n}+\frac{sT^{2}K^{4}\log^{2}\frac{d}{\zeta}}{n^{2}}+\frac{sM^{2}}{K^{4}})=O(\frac{sTM\log\frac{d}{\zeta}}{n\epsilon}).$

In total, with probability $1-\zeta$ for each $t\in[T]$,

$N^{t}+N^{t}_{2}=O(\frac{\eta^{2}s^{2}T\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}n\epsilon}+\frac{sTM\log\frac{dT}{\zeta}}{n\epsilon})=O(\frac{\eta^{2}s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}n\epsilon}).$
(74)

In the following we will assume the above event holds. We note that by our
model for any $w$

$\gamma\|w-w^{*}\|_{2}^{2}\geq
L_{\mathcal{D}}(w)-L_{\mathcal{D}}(w^{*})\geq\mu\|w-w^{*}\|_{2}^{2}.$

Thus we have

$\displaystyle
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{*})\leq(1-\frac{5}{72}\frac{\mu}{\gamma})(L_{\mathcal{D}}(w^{t})-L_{\mathcal{D}}(w^{*}))+O(\frac{\eta^{2}s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}n\epsilon})$
(75)

In the following we will show that $w^{t+1}=w^{t+0.75}$ for all $t$. We will
use induction, assume $w^{i+1}=w^{i+0.75}$ holds for all $i\in[t-1]$, we will
show that it will also true for $t$. Use (75) for $i\in[t-1]$ we have

$\displaystyle\mu\|w^{t+0.75}-w^{*}\|_{2}^{2}\leq
L_{\mathcal{D}}(w^{t+0.75})-L_{\mathcal{D}}(w^{*})$
$\displaystyle\leq(1-\frac{5}{72}\frac{\mu}{\gamma})^{t}(L_{\mathcal{D}}(w^{1})-L_{\mathcal{D}}(w^{*}))+O(\frac{\gamma}{\mu}\frac{\eta^{2}s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}n\epsilon})$
$\displaystyle\leq\gamma(1-\frac{5}{72}\frac{\mu}{\gamma})^{t}\|w^{1}-w^{*}\|_{2}^{2}+O(\frac{\gamma}{\mu}\frac{\eta^{2}s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}n\epsilon}).$

When $\|w^{1}-w^{*}\|_{2}^{2}\leq\frac{1}{2}\frac{\mu}{\gamma}$, and $n$ is
large enough such that

$\displaystyle n\geq
O(\frac{1}{\mu^{3}}\frac{s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\gamma^{2}\epsilon})$

Then $\|w^{t+0.75}\|_{2}\leq\|w^{*}\|_{2}+\frac{1}{2}\leq 1$. Thus
$w^{t+1}=w^{t+0.75}$. So we have

$\displaystyle
L_{\mathcal{D}}(w^{T+1})-L_{\mathcal{D}}(w^{*})\leq(1-\frac{5}{72}\frac{\mu}{\gamma})^{T}(L_{\mathcal{D}}(w^{1})-L_{\mathcal{D}}(w^{*}))+O(\frac{s^{2}TM\log^{2}\frac{dT}{\zeta}\log\frac{1}{\delta}}{\mu^{2}\gamma
n\epsilon})$

Thus, take $T=\tilde{O}(\frac{\gamma}{\mu}\log n)$ and
$s=O((\frac{\gamma}{\mu})^{2}s^{*})$ we have the result. ∎