The Road Less Scheduled — part 4/6

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

Let’s take a look at the update for u t = y t + 1 − y t u_{t}=y_{t+1}-y_{t} in the special case that w t = 1 w_{t}=1 for all t t : u t = ( β t + t ⁡ ( β t − β t + 1 ) ) ​ m t + ( 1 − β t ) ​ Δ t . \displaystyle u_{t}=\left(\beta_{t}+t(\beta_{t}-\beta_{t+1})\right)m_{t}+(1-\beta_{t})\Delta_{t}. Let us define α t = 1 − β t \alpha_{t}=1-\beta_{t} . Then we can re-write this update as: u t = ( 1 − α t + t ⁡ ( α t + 1 − α t ) ) ​ m t + α t ​ Δ t . \displaystyle u_{t}=\left(1-\alpha_{t}+t(\alpha_{t+1}-\alpha_{t})\right)m_{t}+\alpha_{t}\Delta_{t}. It looks like we might be able to set α t \alpha_{t} such that the coefficient of m t m_{t} vanishes. In this case, α t \alpha_{t} would play the role of a “schedule” as the update would just be u t = α t ​ Δ t u_{t}=\alpha_{t}\Delta_{t} . Solving the recursion we get: α t − 1 = t ⁡ ( α t + 1 − α t ) , \displaystyle\alpha_{t}-1=t(\alpha_{t+1}-\alpha_{t}), α t + 1 = ( t + 1 ) ​ α t − 1 t . \displaystyle\alpha_{t+1}=\frac{(t+1)\alpha_{t}-1}{t}. Amazingly, this recursion is satisfied by α t = T − t T \alpha_{t}=\frac{T-t}{T} , which is the linear decay schedule! Notably, this schedule has α T = 0 \alpha_{T}=0 , which in turn implies that y T = x T y_{T}=x_{T} , so that the last iterate of our algorithm is x T x_{T} , for which Theorem 2 provides a convergence guarantee.

The recursion is also satisfied by α t = 1 \alpha_{t}=1 for all t t (which recovers standard Polyak-Ruppert averaging). Notably, this recursion shows that α 1 \alpha_{1} will determine all subsequent α \alpha values. The values will decease linearly to zero, and then they will try to go negative, which is not allowed. So the linear decay schedule is the value of α 1 \alpha_{1} that is “just barely” allowed since it hits zero at α T \alpha_{T} .

In general with arbitrary w t w_{t} , the recursion is: 1 − α t + ( α t + 1 − α t ) w 1 : t w t + 1 = 0 . \displaystyle 1-\alpha_{t}+(\alpha_{t+1}-\alpha_{t})\frac{w_{1:t}}{w_{t+1}}=0. If we insist that α T = 0 \alpha_{T}=0 (so that y T = x T y_{T}=x_{T} and we get a “last iterate” guarantee), then solving the recursion yields: α t = w t + 1 : T w 1 : T , \displaystyle\alpha_{t}=\frac{w_{t+1:T}}{w_{1:T}}, which exactly recovers the main result of Defazio et al., (2023) .

## Appendix C Generalizing Theorem 2 via Bregman Divergences

Here, we provide a generalized version of Theorem 2 in the style of Joulani et al., (2020) . This result employs Bregman divergences to tighten the inequality of Theorem 2 to an equality.

###### Theorem 5 .

Let F F be a convex function. Let ζ 1 , … , ζ T \zeta_{1},\dots,\zeta_{T} be a sequence of i.i.d. random variables, and let g g be a function such that 𝔼 ⁡ [ g ⁡ ( x , ζ t ) ] ∈ ∂ F ⁡ ( x ) \mathbb{E}[g(x,\zeta_{t})]\in\partial F(x) for all x x and t t . Let z 1 , … , z T z_{1},\dots,z_{T} be arbitrary vectors and let w 1 , … , w T w_{1},\dots,w_{T} and α 1 , … , α T \alpha_{1},\dots,\alpha_{T} be arbitrary non-negative real numbers with α t ≤ 1 \alpha_{t}\leq 1 such that z t z_{t} , w t w_{t} and α t \alpha_{t} are independent of ζ t , … , ζ T \zeta_{t},\dots,\zeta_{T} . Define the Bregman divergence of F F as B F ​ ( a , b ) = F ⁡ ( a ) − F ⁡ ( b ) − ⟨ ∇ F ​ ( b ) , a − b ⟩ B_{F}(a,b)=F(a)-F(b)-\langle\nabla F(b),a-b\rangle 2 2 2 if F F is not differentiable, then by abuse of notation define ∇ F ​ ( b ) = 𝔼 ​ [ g ​ ( b , ζ ) ] \nabla F(b)=\mathbb{E}[g(b,\zeta)] , which is a particular choice of subgradient of F F . . Set: x t \displaystyle x_{t} = ∑ i = 1 t w i ​ z i ∑ i = 1 t w i = x t − 1 ​ ( 1 − w t ∑ i = 1 t w i ) + w i ∑ i = 1 t w i ​ z t \displaystyle=\frac{\sum_{i=1}^{t}w_{i}z_{i}}{\sum_{i=1}^{t}w_{i}}=x_{t-1}\left(1-\frac{w_{t}}{\sum_{i=1}^{t}w_{i}}\right)+\frac{w_{i}}{\sum_{i=1}^{t}w_{i}}z_{t} y t \displaystyle y_{t} = ( 1 − α t ) ​ x t + α t ​ z t \displaystyle=(1-\alpha_{t})x_{t}+\alpha_{t}z_{t} g t \displaystyle g_{t} = g ⁡ ( y t , ζ t ) . \displaystyle=g(y_{t},\zeta_{t}). Define the “compressed sum” notation: w 1 : t = ∑ i = 1 t w i w_{1:t}=\sum_{i=1}^{t}w_{i} , with w 1 : 0 = 0 w_{1:0}=0 .

Then we have for all x ⋆ x_{\star} : 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] = 𝔼 [ ∑ t = 1 T w t ​ ⟨ g t , z t − x ⋆ ⟩ w 1 : T ] \displaystyle=\mathbb{E}\left[\frac{\sum_{t=1}^{T}w_{t}\langle g_{t},z_{t}-x_{\star}\rangle}{w_{1:T}}\right] − 𝔼 [ ∑ t = 1 T w t α t ​ B F ​ ( y t , x t ) + w t ​ ( 1 − α t ) α t ​ B F ​ ( x t , y t ) w 1 : T ] \displaystyle\qquad-\mathbb{E}\left[\frac{\sum_{t=1}^{T}\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}}\right] − 𝔼 [ ∑ t = 1 T w 1 : t − 1 B F ( x t − 1 , x t ) + w t B F ( x ⋆ , y t ) w 1 : T ] . \displaystyle\qquad-\mathbb{E}\left[\frac{\sum_{t=1}^{T}w_{1:t-1}B_{F}(x_{t-1},x_{t})+w_{t}B_{F}(x_{\star},y_{t})}{w_{1:T}}\right].

Let’s take a minute to unpack this result since it is depressingly complicated. Recall that the Bregman divergence for a convex function must be positive, and so all the subtracted Bregman divergence terms can be dropped to make the bound only looser. This recovers Theorem 2 . However, in Section D , we show how to exploit the negative Bregman terms to achieve accelerated rates when F F is smooth, and in Section E we show how to exploit the negative Bregman terms to achieve faster rates when F F is strongly-convex.

###### Proof.

The proof is nearly the same as that of Theorem 2 . The only difference is that we keep track of all the error terms in the inequalities via Bregman divergences.

Throughout this proof, we use ∇ F ​ ( x ) \nabla F(x) to indicate 𝔼 ζ ​ [ g ​ ( x , ζ ) ] \mathbb{E}_{\zeta}[g(x,\zeta)] . When F F is differentiable, this is simply the ordinary gradient at x x . When F F is non-differentiable, this reprents a specific choice of subgradient at x x .

Recall that any convex function satisfies ⟨ ∇ F ​ ( b ) − ∇ F ​ ( a ) , a − b ⟩ = − B F ​ ( a , b ) − B F ​ ( b , a ) \langle\nabla F(b)-\nabla F(a),a-b\rangle=-B_{F}(a,b)-B_{F}(b,a) for all a , b a,b . This classical fact can be established by adding the following two subgradient identities: F ⁡ ( a ) = F ⁡ ( b ) + ⟨ ∇ F ​ ( b ) , a − b ⟩ + B F ​ ( a , b ) \displaystyle F(a)=F(b)+\langle\nabla F(b),a-b\rangle+B_{F}(a,b) F ⁡ ( b ) = F ⁡ ( a ) + ⟨ ∇ F ​ ( a ) , b − a ⟩ + B F ​ ( b , a ) \displaystyle F(b)=F(a)+\langle\nabla F(a),b-a\rangle+B_{F}(b,a) ⟨ ∇ F ​ ( b ) − ∇ F ​ ( a ) , a − b ⟩ = − B F ​ ( a , b ) − B F ​ ( b , a ) . \displaystyle\langle\nabla F(b)-\nabla F(a),a-b\rangle=-B_{F}(a,b)-B_{F}(b,a). (27)

The Theorem is established by showing the following identity: w 1 : t F ( x t ) − w 1 : t − 1 F ( x t − 1 ) − w t F ( x ⋆ ) \displaystyle w_{1:t}F(x_{t})-w_{1:t-1}F(x_{t-1})-w_{t}F(x_{\star}) = w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − w t α t ​ B F ​ ( y t , x t ) − w t ​ ( 1 − α t ) α t ​ B F ​ ( x t , y t ) \displaystyle\qquad-\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 ⋆ , y t ) . \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}). (28) Given the identity ( 28 ), we sum over all t t from 1 to T T . Then the LHS will telescope to obtain: w 1 : T ( F ( x T ) − F ( x ⋆ ) ) \displaystyle w_{1:T}(F(x_{T})-F(x_{\star})) = ∑ t = 1 T w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=\sum_{t=1}^{T}w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − ∑ t = 1 T w t α t B F ( y t , x t ) − w t ​ ( 1 − α t ) α t B F ( x t , y t ) \displaystyle\qquad-\sum_{t=1}^{T}\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}) − ∑ t = 1 T w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( x ⋆ , y t ) , \displaystyle\qquad-\sum_{t=1}^{T}w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}), from which the conclusion immediately follows since 𝔼 [ g t | g 1 , … , g t − 1 ] = 𝔼 [ ∇ F ( y t ) | g 1 , … , g t − 1 ] \mathbb{E}[g_{t}|g_{1},\dots,g_{t-1}]=\mathbb{E}[\nabla F(y_{t})|g_{1},\dots,g_{t-1}] . So, let us establish ( 28 ). To do so, it will help to observe the following identities: w t ​ z t \displaystyle w_{t}z_{t} = w 1 : t x t − w 1 : t − 1 x t − 1 \displaystyle=w_{1:t}x_{t}-w_{1:t-1}x_{t-1} w 1 : t − 1 ( x t − x t − 1 ) \displaystyle w_{1:t-1}(x_{t}-x_{t-1}) = w t ​ ( z t − x t ) \displaystyle=w_{t}(z_{t}-x_{t}) (29) z t − y t \displaystyle z_{t}-y_{t} = 1 − α t α t ​ ( y t − x t ) . \displaystyle=\frac{1-\alpha_{t}}{\alpha_{t}}(y_{t}-x_{t}). (30) So, we have: w 1 : t F ( x t ) − w 1 : t − 1 F ( x t − 1 ) − w t F ( x ⋆ ) \displaystyle w_{1:t}F(x_{t})-w_{1:t-1}F(x_{t-1})-w_{t}F(x_{\star}) = w 1 : t − 1 ( F ( x t ) − F ( x t − 1 ) + w t ( F ( x t ) − F ( x ⋆ ) ) \displaystyle=w_{1:t-1}(F(x_{t})-F(x_{t-1})+w_{t}(F(x_{t})-F(x_{\star})) = w 1 : t − 1 ⟨ ∇ F ( x t ) , x t − x t − 1 ⟩ + w t ( F ( x t ) − F ( x ⋆ ) ) \displaystyle=w_{1:t-1}\langle\nabla F(x_{t}),x_{t}-x_{t-1}\rangle+w_{t}(F(x_{t})-F(x_{\star})) − w 1 : t − 1 B F ( x t − 1 , x t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t}) using ( 29 ): = w t ⟨ ∇ F ( x t ) , z t − x t ⟩ + w t ( F ( x t ) − F ( x ⋆ ) ) − w 1 : t − 1 B F ( x t − 1 , x t ) \displaystyle=w_{t}\langle\nabla F(x_{t}),z_{t}-x_{t}\rangle+w_{t}(F(x_{t})-F(x_{\star}))-w_{1:t-1}B_{F}(x_{t-1},x_{t}) = w t ​ ⟨ ∇ F ​ ( x t ) , z t − x t ⟩ + w t ​ ( F ⁡ ( x t ) − F ⁡ ( y t ) ) + w t ​ ( F ⁡ ( y t ) − F ⁡ ( x ⋆ ) ) \displaystyle=w_{t}\langle\nabla F(x_{t}),z_{t}-x_{t}\rangle+w_{t}(F(x_{t})-F(y_{t}))+w_{t}(F(y_{t})-F(x_{\star})) − w 1 : t − 1 B F ( x t − 1 , x t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t}) = w t ​ ⟨ ∇ F ​ ( x t ) , z t − x t ⟩ + w t ​ ⟨ ∇ F ​ ( x t ) , x t − y t ⟩ + w t ​ ⟨ ∇ F ​ ( y t ) , y t − x ⋆ ⟩ \displaystyle=w_{t}\langle\nabla F(x_{t}),z_{t}-x_{t}\rangle+w_{t}\langle\nabla F(x_{t}),x_{t}-y_{t}\rangle+w_{t}\langle\nabla F(y_{t}),y_{t}-x_{\star}\rangle − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( y t , x t ) − w t B F ( x ⋆ , y t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(y_{t},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) = w t ​ ⟨ ∇ F ​ ( x t ) − ∇ F ​ ( y t ) , z t − y t ⟩ + w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=w_{t}\langle\nabla F(x_{t})-\nabla F(y_{t}),z_{t}-y_{t}\rangle+w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( y t , x t ) − w t B F ( x ⋆ , y t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(y_{t},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) using ( 30 ): = w t ​ 1 − α t α t ​ ⟨ ∇ F ​ ( x t ) − ∇ F ​ ( y t ) , y t − x t ⟩ + w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=w_{t}\frac{1-\alpha_{t}}{\alpha_{t}}\langle\nabla F(x_{t})-\nabla F(y_{t}),y_{t}-x_{t}\rangle+w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( y t , x t ) − w t B F ( x ⋆ , y t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(y_{t},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) using ( 27 ): = w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − w t ​ 1 − α t α t ​ ( B F ​ ( x t , y t ) + B F ​ ( y t , x t ) ) \displaystyle\qquad-w_{t}\frac{1-\alpha_{t}}{\alpha_{t}}(B_{F}(x_{t},y_{t})+B_{F}(y_{t},x_{t})) − w 1 : t − 1 B F ( x t − 1 , x t ) − w t B F ( y t , x t ) − w t B F ( x ⋆ , y t ) \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(y_{t},x_{t})-w_{t}B_{F}(x_{\star},y_{t}) = w t ​ ⟨ ∇ F ​ ( y t ) , z t − x ⋆ ⟩ \displaystyle=w_{t}\langle\nabla F(y_{t}),z_{t}-x_{\star}\rangle − w t α t ​ B F ​ ( y t , x t ) − w t ​ ( 1 − α t ) α t ​ B F ​ ( x t , y t ) \displaystyle\qquad-\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 ⋆ , y t ) . \displaystyle\qquad-w_{1:t-1}B_{F}(x_{t-1},x_{t})-w_{t}B_{F}(x_{\star},y_{t}). ∎

## Appendix D Acceleration

In this section, we show that by instantiating our framework with an optimistic online learning algorithm ( Rakhlin and Sridharan,, 2013 ) , we achieve accelerated convergence guarantees. Our results match those available in the prior literature ( Kavis et al.,, 2019 ; Joulani et al.,, 2020 ) . Our approach is inspired by Joulani et al., (2020) ,: their method is based upon a version of Theorem 5 for the special case that α t = 0 \alpha_{t}=0 . Our result simply extends their analysis to α t = O ⁡ ( 1 / t ) \alpha_{t}=O(1/t) .

First, we establish an important technical Corollary that simplifies Theorem 5 in the case that F F is smooth and α t \alpha_{t} is sufficiently small.

###### Corollary 1 .

Under the same conditions as Theorem 5 , suppose additionally that F F is L L -smooth and suppose α t ≤ w t 10 w 1 : t \alpha_{t}\leq\frac{w_{t}}{10w_{1:t}} for all t t . Then we have for all x ⋆ x_{\star} : 𝔼 ⁡ [ F ⁡ ( x T ) − F ⁡ ( x ⋆ ) ] \displaystyle\mathbb{E}[F(x_{T})-F(x_{\star})] ≤ 𝔼 [ ∑ t = 1 T w t ​ ⟨ g t , z t − x ⋆ ⟩ w 1 : T ] \displaystyle\leq\mathbb{E}\left[\frac{\sum_{t=1}^{T}w_{t}\langle g_{t},z_{t}-x_{\star}\rangle}{w_{1:T}}\right] − 𝔼 [ ∑ t = 1 T w 1 : t − 1 ∥ ∇ F ( y t ) − ∇ F ( y t − 1 ) ∥ 2 6 L w 1 : T ] , \displaystyle\qquad-\mathbb{E}\left[\frac{\sum_{t=1}^{T}w_{1:t-1}\|\nabla F(y_{t})-\nabla F(y_{t-1})\|^{2}}{6Lw_{1:T}}\right], where above the value of y 0 y_{0} is arbitrary (since the coefficient is w 1 : 0 = 0 w_{1:0}=0 ).

###### Proof.