Appendix For any fixed l,we can take expectation for both sides of the Proof of Lemma 1 above inequality and then sum l from 1 to n.Then we can Proof. get: Ilp(x)2-Ip(y)I2≤2p(x)T(p(x)-py)》 Eq(im)-Eq(im+1）≤ ≤三p(x2+rp:(x)-p:y)2 ga)+9rr+z2∑a,) j=m- =p(x训2+rIfx)-Vfy)川 Here,we use the fact thatEll=(). ≤p.(x)2+r2Ix-yP Then,we will prove the conclusion by induction.For convenience,we use qi to denote Eq(ui). When m =0,we have 1 Proof of Lemma 2 90≤1--9rF+12P91≤p1 Proof.According to Lemma 1,we have Assuming that Vm≤Mo,we have qm-l≤pgm. llp()I2-llp(m)2 Then,for m Mo,we have ≤pu(am)川2+rL2lam-im+il2 qm-a1≤m+9rr+iz2r∑g Furthermore,we can get j=m一1 llum im+ill sn+9nr+12rn∑p叫 -lwm- j=m-7 Pm.i-a(m)Vi =a(m) -n+咖+1o*1- p-1 -(u(m+)-∑Pn+,i-am+v)l which means that =a(m+1) 1 ≤Ilm-ml+∑Isl gm≤1-是-c+9o西9m+1<p4m+1 p-1 i=a(m) 0 +n2 Proof of Lemma 3 =a(m+1) Proof.According to Lemma 1,we have su-+∑ a(m+1)-1 Ilpi()2-lpi(um)2 i=a(m) =a(m) ≤p(an产+r2Iaa-un +7 1 Similar to the proof of Lemma 2,we can get: =a(m+1) a(m+1)-1 m-1 lin-un‖= ta():-th ∑ +∑I i=a(m) i=a(m) i=a(m) +2 ≤I-n+g2l i=a(m）} i=a(m+1) ≤3∑. s-wl+ i=a(m) =a(m） =m-订 Then,we have 元+n罗 lpu(位n)川2-Ip(im+i)I2 i=a(m) =a(m) ≤Ipa+9r(r+1L2∑， ≤∑d (12) i=a(m)Appendix Proof of Lemma 1 Proof. kpi(x)k 2 − kpi(y)k 2 ≤ 2pi(x) T (pi(x) − pi(y)) ≤ 1 r kpi(x)k 2 + r kpi(x) − pi(y)k 2 = 1 r kpi(x)k 2 + r k∇fi(x) − ∇fi(y)k 2 ≤ 1 r kpi(x)k 2 + rL2 kx − yk 2 Proof of Lemma 2 Proof. According to Lemma 1, we have kpl(uˆm)k 2 − kpl(uˆm+1)k 2 ≤ 1 r kpl(uˆm)k 2 + rL2 kuˆm − uˆm+1k 2 . Furthermore, we can get kuˆm − uˆm+1k =kua(m) − η mX−1 i=a(m) Pm,i−a(m)vˆi − (ua(m+1) − η Xm i=a(m+1) Pm+1,i−a(m+1)vˆi)k ≤ ua(m) − ua(m+1) + η mX−1 i=a(m) kvˆik + η Xm i=a(m+1) kvˆik ≤ a(mX +1)−1 i=a(m) kui − ui+1k + η mX−1 i=a(m) kvˆik + η Xm i=a(m+1) kvˆik ≤η a(mX +1)−1 i=a(m) kvˆik + η mX−1 i=a(m) kvˆik + η Xm i=a(m+1) kvˆik ≤3η Xm i=m−τ kvˆik . Then, we have kpl(uˆm)k 2 − kpl(uˆm+1)k 2 ≤ 1 r kpl(uˆm)k 2 + 9r(τ + 1)L 2 η 2 Xm j=m−τ kvˆjk 2 For any fixed l, we can take expectation for both sides of the above inequality and then sum l from 1 to n. Then we can get: Eq(uˆm) − Eq(uˆm+1) ≤ 1 r Eq(uˆm) + 9r(τ + 1)L 2 η 2 Xm j=m−τ Eq(uˆj ) Here, we use the fact that E[kvˆjk 2 |uˆj ] = q(uˆj ). Then, we will prove the conclusion by induction. For convenience, we use qi to denote Eq(uˆi). When m = 0, we have q0 ≤ 1 1 − 1 r − 9r(τ + 1)L2η 2 q1 ≤ ρq1 Assuming that ∀m ≤ M0, we have qm−1 ≤ ρqm. Then, for m = M0, we have qm−qm+1 ≤ 1 r qm + 9r(τ + 1)L 2 η 2 Xm j=m−τ qj ≤ 1 r qm + 9r(τ + 1)L 2 η 2 qm Xm j=m−τ ρ m−j = 1 r qm + 9r(τ + 1)L 2η 2 (ρ τ+1 − 1) ρ − 1 qm which means that qm ≤ 1 1 − 1 r − 9r(τ+1)L2η2(ρτ+1−1) ρ−1 qm+1 < ρqm+1 Proof of Lemma 3 Proof. According to Lemma 1, we have kpl(uˆm)k 2 − kpl(um)k 2 ≤ 1 r kpl(uˆm)k 2 + rL2 kuˆm − umk 2 Similar to the proof of Lemma 2, we can get: kuˆm − umk = ua(m) − η mX−1 i=a(m) Pm,i−a(m)vˆi − um ≤ ua(m) − um + η mX−1 i=a(m) kvˆik ≤ mX−1 i=a(m) kui − ui+1k + η mX−1 i=a(m) kvˆik ≤η mX−1 i=a(m) kvˆik + η mX−1 i=a(m) kvˆik ≤2η mX−1 i=a(m) kvˆik (12)