The Road Less Scheduled — part 5/6

Cleaned-text code points [59899, 74670). Bibliography omitted here; source.md includes it.

The key thing is to observe that smoothness implies B F ​ ( a , b ) ≥ 2 ​ L ​ ‖ ∇ F ​ ( a ) − ∇ F ​ ( b ) ‖ 2 B_{F}(a,b)\geq 2L\|\nabla F(a)-\nabla F(b)\|^{2} . The rest of the argument is straightforward manipulation of the terms in Theorem 5 : − w t α t ​ B F ​ ( y t , x t ) − w t ​ ( 1 − α t ) α t ​ B F ​ ( x t , y t ) \displaystyle-\frac{w_{t}}{\alpha_{t}}B_{F}(y_{t},x_{t})-\frac{w_{t}(1-\alpha_{t})}{\alpha_{t}}B_{F}(x_{t},y_{t}) ≤ − w t ​ ( 2 − α t ) 2 ​ L ​ α t ​ ‖ ∇ F ​ ( x t ) − ∇ F ​ ( y t ) ‖ 2 \displaystyle\leq-\frac{w_{t}(2-\alpha_{t})}{2L\alpha_{t}}\|\nabla F(x_{t})-\nabla F(y_{t})\|^{2} − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( x ⋆ , y t ) \displaystyle-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) ≤ − w 1 : t − 1 2 ​ L ∥ ∇ F ( x t ) − ∇ F ( x t − 1 ) ∥ 2 . \displaystyle\leq-\frac{w_{1:t-1}}{2L}\|\nabla F(x_{t})-\nabla F(x_{t-1})\|^{2}. Next, observe that for any vectors a , b , c a,b,c , for any λ > 0 \lambda>0 : − ‖ a + b + c ‖ 2 \displaystyle-\|a+b+c\|^{2} = − ‖ a ‖ 2 − ‖ b ‖ 2 − ‖ c ‖ 2 − 2 ​ ⟨ a , b ⟩ − 2 ​ ⟨ b , c ⟩ − 2 ​ ⟨ a , c ⟩ \displaystyle=-\|a\|^{2}-\|b\|^{2}-\|c\|^{2}-2\langle a,b\rangle-2\langle b,c\rangle-2\langle a,c\rangle ≤ − ( 1 − 2 / λ ) ​ ‖ a ‖ 2 + ( 2 ​ λ − 1 ) ​ ( ‖ b ‖ 2 + ‖ c ‖ 2 ) , \displaystyle\leq-(1-2/\lambda)\|a\|^{2}+(2\lambda-1)(\|b\|^{2}+\|c\|^{2}), where we have used Young’s inequality: | ⟨ v , w ⟩ | ≤ ‖ v ‖ 2 2 ​ λ + λ ​ ‖ w ‖ 2 2 |\langle v,w\rangle|\leq\frac{\|v\|^{2}}{2\lambda}+\frac{\lambda\|w\|^{2}}{2} . Therefore, setting λ t = 3 \lambda_{t}=3 we obtain: − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( x ⋆ , y t ) \displaystyle-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) ≤ − w 1 : t − 1 6 ​ L ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 \displaystyle\leq-\frac{w_{1:t-1}}{6L}\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2} + 5 w 1 : t − 1 2 ​ L ( ∥ ∇ F ( x t ) − ∇ F ( y t ) ∥ 2 + ∥ ∇ F ( x t − 1 ) − ∇ F ( y t − 1 ) ∥ 2 ) . \displaystyle\qquad+\frac{5w_{1:t-1}}{2L}(\|\nabla F(x_{t})-\nabla F(y_{t})\|^{2}+\|\nabla F(x_{t-1})-\nabla F(y_{t-1})\|^{2}). Now, since α t ≤ w t 10 w 1 : t ≤ 1 \alpha_{t}\leq\frac{w_{t}}{10w_{1:t}}\leq 1 , we obtain: − w t α t B F ( y t , x t ) − w t ​ ( 1 − α t ) α t B F ( x t , y t ) − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( x ⋆ , y t ) \displaystyle-\frac{w_{t}}{\alpha_{t}}B_{F}(y_{t},x_{t})-\frac{w_{t}(1-\alpha_{t})}{\alpha_{t}}B_{F}(x_{t},y_{t})-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) ≤ − w 1 : t − 1 6 ​ L ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 \displaystyle\qquad\leq-\frac{w_{1:t-1}}{6L}\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2} − 5 w 1 : t 2 ​ L ∥ ∇ F ( x t ) − ∇ F ( y t ) ∥ 2 + − 5 w 1 : t − 1 2 ​ L ∥ ∇ F ( x t − 1 ) − ∇ F ( y t − 1 ) ∥ 2 . \displaystyle\qquad-\frac{5w_{1:t}}{2L}\|\nabla F(x_{t})-\nabla F(y_{t})\|^{2}+-\frac{5w_{1:t-1}}{2L}\|\nabla F(x_{t-1})-\nabla F(y_{t-1})\|^{2}. Now summing over t t from 1 to T T (and dropping one negative term), the sum telescopes to: ∑ t = 1 T − w 1 : t − 1 6 ​ L ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 . \displaystyle\sum_{t=1}^{T}-\frac{w_{1:t-1}}{6L}\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}. The result now follows from Theorem 5 . ∎

Now, we consider the case that z t z_{t} is given by an optimistic mirror descent algorithm:

###### Corollary 2 .

Suppose F F is L L -smooth. Define g 0 = 0 g_{0}=0 and suppose also that for some D D satisfying D ≥ ‖ y 1 − x ⋆ ‖ D\geq\|y_{1}-x_{\star}\| : ∑ t = 1 T w t ​ ⟨ g t , z t − x ⋆ ⟩ ≤ D ​ ∑ t = 1 T w t 2 ​ ‖ g t − g t − 1 ‖ 2 . \displaystyle\sum_{t=1}^{T}w_{t}\langle g_{t},z_{t}-x_{\star}\rangle\leq D\sqrt{\sum_{t=1}^{T}w_{t}^{2}\|g_{t}-g_{t-1}\|^{2}}. Finally, suppose 𝔼 ⁡ [ ‖ g t − g t − 1 ‖ 2 ] ≤ ‖ ∇ F ​ ( y t ) − ∇ F ​ ( y t − 1 ) ‖ 2 + σ t 2 \mathbb{E}[\|g_{t}-g_{t-1}\|^{2}]\leq\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}+\sigma_{t}^{2} for some constants σ 1 , … , σ T \sigma_{1},\dots,\sigma_{T} (these are just variance bounds on the stochastic gradient oracle). Then with w t = t w_{t}=t and α t ≤ 1 5 ​ ( t − 1 ) \alpha_{t}\leq\frac{1}{5(t-1)} , we have: 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 14 ​ D 2 ​ L T ⁡ ( T + 1 ) + 2 ​ D ​ ∑ t = 1 T t 2 ​ σ t 2 T ⁡ ( T + 1 ) \displaystyle\leq\frac{14D^{2}L}{T(T+1)}+\frac{2D\sqrt{\sum_{t=1}^{T}t^{2}\sigma_{t}^{2}}}{T(T+1)} = O ⁡ ( D 2 ​ L T 2 + D ​ σ T ) , \displaystyle=O\left(\frac{D^{2}L}{T^{2}}+\frac{D\sigma}{\sqrt{T}}\right), where σ \sigma is uniform upper-bound on σ t \sigma_{t} . Note that the algorithm does not need to know L L or σ \sigma .

Algorithms producing z z sequences obtaining the guarantee stated here are called “optimistic online learning algorithms”.

###### Proof.

Applying Corollary 1 , we obtain immediately: T ⁡ ( T + 1 ) 2 ​ 𝔼 ​ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\frac{T(T+1)}{2}\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 𝔼 ⁡ [ D ​ ∑ t = 1 T t 2 ​ ‖ g t − g t − 1 ‖ 2 − ∑ t = 1 T ( t − 1 ) ​ t 12 ​ L ​ ‖ ∇ F ​ ( y t ) − ∇ F ​ ( y t − 1 ) ‖ 2 ] \displaystyle\leq\mathbb{E}\left[D\sqrt{\sum_{t=1}^{T}t^{2}\|g_{t}-g_{t-1}\|^{2}}-\sum_{t=1}^{T}\frac{(t-1)t}{12L}\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}\right] ≤ D ​ ∑ t = 1 T t 2 ​ 𝔼 ​ [ ‖ ∇ F ​ ( y t ) − ∇ F ​ ( y t − 1 ) ‖ 2 ] + t 2 ​ σ t 2 + ‖ ∇ F ​ ( y 1 ) ‖ 2 24 ​ L \displaystyle\leq D\sqrt{\sum_{t=1}^{T}t^{2}\mathbb{E}\left[\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}\right]+t^{2}\sigma_{t}^{2}}+\frac{\|\nabla F(y_{1})\|^{2}}{24L} − 1 24 ​ L ∑ t = 1 T t 2 𝔼 [ ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 ] \displaystyle\qquad-\frac{1}{24L}\sum_{t=1}^{T}t^{2}\mathbb{E}\left[\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}\right] ≤ D ​ ∑ t = 1 T t 2 ​ 𝔼 ​ [ ‖ ∇ F ​ ( y t ) − ∇ F ​ ( y t − 1 ) ‖ 2 ] + D ​ ∑ t = 1 T t 2 ​ σ t 2 + ‖ ∇ F ​ ( y 1 ) ‖ 2 24 ​ L \displaystyle\leq D\sqrt{\sum_{t=1}^{T}t^{2}\mathbb{E}\left[\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}\right]}+D\sqrt{\sum_{t=1}^{T}t^{2}\sigma_{t}^{2}}+\frac{\|\nabla F(y_{1})\|^{2}}{24L} − 1 24 ​ L ∑ t = 1 T t 2 𝔼 [ ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 ] \displaystyle\qquad-\frac{1}{24L}\sum_{t=1}^{T}t^{2}\mathbb{E}\left[\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}\right] Using the identity A ​ C − B ​ C ≤ A 2 4 ​ B A\sqrt{C}-BC\leq\frac{A^{2}}{4B} : ≤ 6 ​ D 2 ​ L + L ​ ‖ y 1 − x ⋆ ‖ 2 24 + D ​ ∑ t = 1 T t 2 ​ σ t 2 \displaystyle\leq 6D^{2}L+\frac{L\|y_{1}-x_{\star}\|^{2}}{24}+D\sqrt{\sum_{t=1}^{T}t^{2}\sigma_{t}^{2}} ≤ 7 ​ D 2 ​ L + D ​ ∑ t = 1 T t 2 ​ σ t 2 . \displaystyle\leq 7D^{2}L+D\sqrt{\sum_{t=1}^{T}t^{2}\sigma_{t}^{2}}. Divide by T ⁡ ( T + 1 ) 2 \frac{T(T+1)}{2} to conclude the result. ∎

### D.1 An Optimistic Regret Bound

In this section we provide an algorithm that achieves the optimistic regret bound required for our acceleration result Corollary 2 . This algorithm is a mild variation on the established literature ( Rakhlin and Sridharan,, 2013 ; Chiang et al.,, 2012 ; Hazan and Kale,, 2010 ; Joulani et al.,, 2017 ) to slightly improve a technical dependence on the maximum gradient value.

###### Lemma 1 .

For a sequence of vectors g 1 , … , g T g_{1},\dots,g_{T} , set η t = D 2 ​ ∑ i = 1 t ‖ g i − g i − 1 ‖ 2 \eta_{t}=\frac{D}{\sqrt{2\sum_{i=1}^{t}\|g_{i}-g_{i-1}\|^{2}}} with g 0 = 0 g_{0}=0 , define m t = max i ≤ t ⁡ ‖ g i − g i − 1 ‖ m_{t}=\max_{i\leq t}\|g_{i}-g_{i-1}\| and define the sequence of vectors z t , z t ′ z_{t},z^{\prime}_{t} and g ~ t \tilde{g}_{t} by the recursions: z 1 \displaystyle z_{1} = z 1 ′ = 0 \displaystyle=z^{\prime}_{1}=0 g ~ t \displaystyle\tilde{g}_{t} = g t − 1 + min ⁡ ( m t − 1 , ‖ g t − g t − 1 ‖ ) ​ g t − g t − 1 ‖ g t − g t − 1 ‖ \displaystyle=g_{t-1}+\min\left(m_{t-1},\|g_{t}-g_{t-1}\|\right)\frac{g_{t}-g_{t-1}}{\|g_{t}-g_{t-1}\|} η t \displaystyle\eta_{t} = D m t 2 + ∑ i = 1 t ‖ g ~ i − g i − 1 ‖ 2 \displaystyle=\frac{D}{\sqrt{m_{t}^{2}+\sum_{i=1}^{t}\|\tilde{g}_{i}-g_{i-1}\|^{2}}} z t + 1 ′ \displaystyle z^{\prime}_{t+1} = Π ‖ z t + 1 ′ ‖ ≤ D ​ z t ′ − η t ​ g ~ t \displaystyle=\Pi_{\|z^{\prime}_{t+1}\|\leq D}z^{\prime}_{t}-\eta_{t}\tilde{g}_{t} z t + 1 \displaystyle z_{t+1} = Π ‖ z t + 1 ‖ ≤ D ​ z t + 1 ′ − η t ​ g t . \displaystyle=\Pi_{\|z_{t+1}\|\leq D}z^{\prime}_{t+1}-\eta_{t}g_{t}. Then: ∑ t = 1 T ⟨ g t , z t − x ⋆ ⟩ ≤ 7 ​ D ​ 2 ​ ∑ t = 1 T ‖ g t − g t − 1 ‖ 2 . \displaystyle\sum_{t=1}^{T}\langle g_{t},z_{t}-x_{\star}\rangle\leq 7D\sqrt{2\sum_{t=1}^{T}\|g_{t}-g_{t-1}\|^{2}}.

###### Proof.

For purposes of notation, define g 0 = 0 g_{0}=0 and z 0 ′ = 0 z^{\prime}_{0}=0 . Further, observe that: ‖ g ~ t − g t − 1 ‖ \displaystyle\|\tilde{g}_{t}-g_{t-1}\| ≤ m t − 1 \displaystyle\leq m_{t-1} ‖ g ~ t − g t − 1 ‖ \displaystyle\|\tilde{g}_{t}-g_{t-1}\| ≤ ‖ g t − g t − 1 ‖ \displaystyle\leq\|g_{t}-g_{t-1}\| ‖ g ~ t − g t ‖ \displaystyle\|\tilde{g}_{t}-g_{t}\| = m t − m t − 1 \displaystyle=m_{t}-m_{t-1} η t \displaystyle\eta_{t} ≤ D ∑ i = 1 t + 1 ‖ g ~ i − g i − 1 ‖ 2 \displaystyle\leq\frac{D}{\sqrt{\sum_{i=1}^{t+1}\|\tilde{g}_{i}-g_{i-1}\|^{2}}} 1 η T \displaystyle\frac{1}{\eta_{T}} ≤ 2 ​ ∑ t = 1 T ‖ g t − g t − 1 ‖ 2 D . \displaystyle\leq\frac{\sqrt{2\sum_{t=1}^{T}\|g_{t}-g_{t-1}\|^{2}}}{D}.

Next, notice that z t + 1 ′ = argmin ‖ z ‖ ≤ D ⁡ ⟨ g ~ t , z ⟩ + 1 2 ​ η t ​ ‖ z − z t ′ ‖ 2 z^{\prime}_{t+1}=\mathop{\text{argmin}}_{\|z\|\leq D}\langle\tilde{g}_{t},z\rangle+\frac{1}{2\eta_{t}}\|z-z^{\prime}_{t}\|^{2} . Therefore since ‖ x ⋆ ‖ ≤ D \|x_{\star}\|\leq D , by first order optimality conditions: ⟨ g ~ t + z t + 1 ′ − z t ′ η t , z t + 1 ′ − x ⋆ ⟩ \displaystyle\left\langle\tilde{g}_{t}+\frac{z^{\prime}_{t+1}-z^{\prime}_{t}}{\eta_{t}},z^{\prime}_{t+1}-x_{\star}\right\rangle ≤ 0 \displaystyle\leq 0 ⟨ g ~ t , z t + 1 ′ − x ⋆ ⟩ \displaystyle\langle\tilde{g}_{t},z^{\prime}_{t+1}-x_{\star}\rangle ≤ 1 η t ​ ⟨ z t ′ − z t + 1 ′ , z t + 1 ′ − x ⋆ ⟩ \displaystyle\leq\frac{1}{\eta_{t}}\langle z^{\prime}_{t}-z^{\prime}_{t+1},z^{\prime}_{t+1}-x_{\star}\rangle = ‖ z t ′ − x ⋆ ‖ 2 2 ​ η t − ‖ z t + 1 ′ − x ⋆ ‖ 2 2 ​ η t − ‖ z t + 1 ′ − z t ′ ‖ 2 2 ​ η t . \displaystyle=\frac{\|z^{\prime}_{t}-x_{\star}\|^{2}}{2\eta_{t}}-\frac{\|z^{\prime}_{t+1}-x_{\star}\|^{2}}{2\eta_{t}}-\frac{\|z^{\prime}_{t+1}-z^{\prime}_{t}\|^{2}}{2\eta_{t}}.

Similarly, we have z t = argmin ‖ z ‖ ≤ D ⁡ ⟨ g t − 1 , z ⟩ + 1 2 ​ η t − 1 ​ ‖ z − z t ′ ‖ 2 z_{t}=\mathop{\text{argmin}}_{\|z\|\leq D}\langle g_{t-1},z\rangle+\frac{1}{2\eta_{t-1}}\|z-z^{\prime}_{t}\|^{2} . From this we have: ⟨ g t − 1 + z t − z t ′ η t − 1 , z t − z t + 1 ′ ⟩ \displaystyle\left\langle g_{t-1}+\frac{z_{t}-z^{\prime}_{t}}{\eta_{t-1}},z_{t}-z^{\prime}_{t+1}\right\rangle ≤ 0 \displaystyle\leq 0 ⟨ g t − 1 , z t − z t + 1 ′ ⟩ \displaystyle\langle g_{t-1},z_{t}-z^{\prime}_{t+1}\rangle ≤ ‖ z t ′ − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t ′ ‖ 2 2 ​ η t − 1 \displaystyle\leq\frac{\|z^{\prime}_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t}\|^{2}}{2\eta_{t-1}} ⟨ g ~ t , z t − z t + 1 ′ ⟩ \displaystyle\langle\tilde{g}_{t},z_{t}-z^{\prime}_{t+1}\rangle ≤ ‖ z t ′ − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t ′ ‖ 2 2 ​ η t − 1 \displaystyle\leq\frac{\|z^{\prime}_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t}\|^{2}}{2\eta_{t-1}} + ⟨ g ~ t − g t − 1 , z t − z t + 1 ′ ⟩ \displaystyle+\langle\tilde{g}_{t}-g_{t-1},z_{t}-z^{\prime}_{t+1}\rangle by Young’s inequality: ≤ ‖ z t ′ − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t + 1 ′ ‖ 2 2 ​ η t − 1 − ‖ z t − z t ′ ‖ 2 2 ​ η t − 1 \displaystyle\leq\frac{\|z^{\prime}_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}-\frac{\|z_{t}-z^{\prime}_{t}\|^{2}}{2\eta_{t-1}} + η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 + ‖ z t − z t + 1 ′ ‖ 2 2 ​ η t − 1 \displaystyle+\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2}+\frac{\|z_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}} ≤ ‖ z t ′ − z t + 1 ′ ‖ 2 2 ​ η t − 1 + η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 . \displaystyle\leq\frac{\|z^{\prime}_{t}-z^{\prime}_{t+1}\|^{2}}{2\eta_{t-1}}+\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2}. So, combining these facts (and noticing that η t − 1 ≥ η t \eta_{t-1}\geq\eta_{t} :) ⟨ g ~ t , z t − x ⋆ ⟩ \displaystyle\langle\tilde{g}_{t},z_{t}-x_{\star}\rangle ≤ ‖ z t ′ − x ⋆ ‖ 2 2 ​ η t − ‖ z t + 1 ′ − x ⋆ ‖ 2 2 ​ η t + η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 \displaystyle\leq\frac{\|z^{\prime}_{t}-x_{\star}\|^{2}}{2\eta_{t}}-\frac{\|z^{\prime}_{t+1}-x_{\star}\|^{2}}{2\eta_{t}}+\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2} ⟨ g t , z t − x ⋆ ⟩ \displaystyle\langle g_{t},z_{t}-x_{\star}\rangle ≤ ‖ z t ′ − x ⋆ ‖ 2 2 ​ η t − ‖ z t + 1 ′ − x ⋆ ‖ 2 2 ​ η t + η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 + ⟨ g t − g ~ t , z t − x ⋆ ⟩ \displaystyle\leq\frac{\|z^{\prime}_{t}-x_{\star}\|^{2}}{2\eta_{t}}-\frac{\|z^{\prime}_{t+1}-x_{\star}\|^{2}}{2\eta_{t}}+\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2}+\langle g_{t}-\tilde{g}_{t},z_{t}-x_{\star}\rangle ≤ ‖ z t ′ − x ⋆ ‖ 2 2 ​ η t − ‖ z t + 1 ′ − x ⋆ ‖ 2 2 ​ η t + η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 + 2 ​ D ​ ( m t − m t − 1 ) . \displaystyle\leq\frac{\|z^{\prime}_{t}-x_{\star}\|^{2}}{2\eta_{t}}-\frac{\|z^{\prime}_{t+1}-x_{\star}\|^{2}}{2\eta_{t}}+\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2}+2D(m_{t}-m_{t-1}). So, we have: ∑ t = 1 T ⟨ g t , z t − x ⋆ ⟩ \displaystyle\sum_{t=1}^{T}\langle g_{t},z_{t}-x_{\star}\rangle ≤ 2 ​ D ​ m T + ‖ z 1 ′ − x ⋆ ‖ 2 2 ​ η 1 + ∑ t = 2 T ‖ z t ′ − x ⋆ ‖ 2 2 ​ ( 1 η t − 1 η t − 1 ) \displaystyle\leq 2Dm_{T}+\frac{\|z^{\prime}_{1}-x_{\star}\|^{2}}{2\eta_{1}}+\sum_{t=2}^{T}\frac{\|z^{\prime}_{t}-x_{\star}\|^{2}}{2}\left(\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}\right) + ∑ t = 1 T η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 \displaystyle+\sum_{t=1}^{T}\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2} ≤ 2 ​ D ​ m T + 4 ​ D 2 / η T + ∑ t = 1 T η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 \displaystyle\leq 2Dm_{T}+4D^{2}/\eta_{T}+\sum_{t=1}^{T}\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2} ≤ 6 ​ D 2 / η T + ∑ t = 1 T η t − 1 ​ ‖ g ~ t − g t − 1 ‖ 2 2 \displaystyle\leq 6D^{2}/\eta_{T}+\sum_{t=1}^{T}\frac{\eta_{t-1}\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2} ≤ 6 ​ D 2 / η T + ∑ t = 1 T D ​ ‖ g ~ t − g t − 1 ‖ 2 2 ​ ∑ i = 1 t ‖ g ~ i − g i − 1 ‖ 2 \displaystyle\leq 6D^{2}/\eta_{T}+\sum_{t=1}^{T}\frac{D\|\tilde{g}_{t}-g_{t-1}\|^{2}}{2\sqrt{\sum_{i=1}^{t}\|\tilde{g}_{i}-g_{i-1}\|^{2}}} ≤ 6 ​ D 2 / η T + D ​ ∑ t = 1 T ‖ g ~ t − g t − 1 ‖ 2 \displaystyle\leq 6D^{2}/\eta_{T}+D\sqrt{\sum_{t=1}^{T}\|\tilde{g}_{t}-g_{t-1}\|^{2}} ≤ 7 ​ D ​ 2 ​ ∑ t = 1 T ‖ g t − g t − 1 ‖ 2 . \displaystyle\leq 7D\sqrt{2\sum_{t=1}^{T}\|g_{t}-g_{t-1}\|^{2}}.

∎

## Appendix E Strongly Convex Losses

Suppose that the expected loss F F is actually known to be μ \mu -strongly convex. Then we’d like to have a convergence guarantee of O ⁡ ( 1 / μ ​ T ) O(1/\mu T) . This is achieved in Theorem 6 below.

###### Theorem 6 .