MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters — part 4/10

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

Consider the following partitions of G t G_{t} , G t meta ​ = def ​ [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t ] , G^{\textrm{meta}}_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right], (17) G t base ​ = def ​ [ d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] . G^{\textrm{base}}_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]. (18) Then, G t = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t d ​ 𝒙 t + 1 d ​ 𝒚 t d ​ 𝒙 t + 1 d ​ 𝒙 t d ​ 𝒙 t + 1 d ​ 𝒉 t d ​ 𝒉 t + 1 d ​ 𝒚 t d ​ 𝒉 t + 1 d ​ 𝒙 t d ​ 𝒉 t + 1 d ​ 𝒉 t ] = [ G t meta G t base ] . G_{t}={\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{x}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\\ \hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{h}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]}=\left[\begin{array}[]{c}\hskip-7.0pt\begin{array}[]{c}\\ {G^{\textrm{meta}}_{t}}\\ \\ \end{array}\\ \hline\cr\hskip-7.0pt\begin{array}[]{c}\\ {G^{\textrm{base}}_{t}}\\ \\ \end{array}\end{array}\right]. (19)

In the sequel, we study base and meta updates separately, because Alg base \operatorname{Alg}_{\textrm{base}} and Alg meta \operatorname{Alg}_{\textrm{meta}} impact disjoint sets of blocks in G t G_{t} . In particular, as we will see, the choice of Alg base \operatorname{Alg}_{\textrm{base}} only affects G base G^{\textrm{base}} while the choice of Alg meta \operatorname{Alg}_{\textrm{meta}} only affects G meta G^{\textrm{meta}} .

Notation conventions in all Appendices: For any vector 𝒗 \boldsymbol{v} , we denote by [ 𝒗 ] \left[\boldsymbol{v}\right] a diagonal matrix with diagonal entries derived from 𝒗 \boldsymbol{v} . We denote by σ ′ ​ ( 𝜷 t ) \sigma^{\prime}(\boldsymbol{\beta}_{t}) the Jacobian of 𝜶 t \boldsymbol{\alpha}_{t} with respect to 𝜷 t \boldsymbol{\beta}_{t} .

Before delving into computing G t base G^{\textrm{base}}_{t} and G t meta G^{\textrm{meta}}_{t} for different base and meta algorithms, we further simplify these matrices.

### A.1 Derivation of G meta G^{\textrm{meta}} for Different Meta Updates

We start by simplifying G meta G^{\textrm{meta}} , and introducing some notations.

Note that the meta update has no dependence on internal variables, 𝒙 ~ \tilde{\boldsymbol{x}} , of the base algorithm. As a result, d ​ 𝒚 t + 1 d ​ 𝒙 ~ t = 0 . \frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{x}}_{t}}=0. (20) Then, G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒙 t d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t d ​ 𝒚 t + 1 d ​ 𝒙 ~ t d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] , G^{\textrm{meta}}_{t}=\left[\begin{array}[]{ccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{x}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\tilde{\boldsymbol{x}}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right], (21) where the third equality is due to ( 20 ). Let L t ​ = def ​ [ ∇ f t ( 𝒘 t ) T 0 0 0 0 ∇ f t ( 𝒘 t ) T 0 0 0 0 ⋱ 0 0 0 0 ∇ f t ( 𝒘 t ) T ] ​ ← 1 ← 2 ⋮ ← m L_{t}\overset{\text{\tiny def}}{=}\left[\begin{array}[]{c|c|c|c}\quad\nabla f_{t}(\boldsymbol{w}_{t})^{T}&0&0&0\\ \hline\cr 0&\begin{array}[]{c}\\ \quad\nabla f_{t}(\boldsymbol{w}_{t})^{T}\end{array}&0&0\\ \hline\cr 0&0&\begin{array}[]{c}\\ \quad\ddots\\ \\ \end{array}&0\\ \hline\cr 0&0&0&\begin{array}[]{c}\\ \quad\nabla f_{t}(\boldsymbol{w}_{t})^{T}\end{array}\end{array}\right]\,\,\begin{array}[]{l}\begin{array}[]{c}{\color[rgb]{0.75,0.75,0.75}\leftarrow 1}\end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow 2}\end{array}\\ \begin{array}[]{c}\\ \,\,{\color[rgb]{0.75,0.75,0.75}\vdots}\\ \\ \end{array}\\ \begin{array}[]{c}\\ {\color[rgb]{0.75,0.75,0.75}\leftarrow m}\end{array}\end{array} (22) and recall that 𝒉 t \boldsymbol{h}_{t} is a vectorization of ℋ t \mathcal{H}_{t} . Then, ℋ t ∇ f t ( 𝒘 t ) = L t 𝒉 t . \mathcal{H}_{t}\nabla f_{t}(\boldsymbol{w}_{t})=L_{t}\boldsymbol{h}_{t}. (23)

We now proceed to derivation of G meta G^{\textrm{meta}} for different choices of Alg meta \operatorname{Alg}_{\textrm{meta}} .

#### A.1.1 Meta SGD

Here, we consider SGD for the meta update ( 8 ), 𝜷 t + 1 = 𝜷 t − η ∇ 𝜷 F ^ t = 𝜷 t − η ℋ t T ∇ f t ( 𝒘 t ) , \boldsymbol{\beta}_{t+1}=\boldsymbol{\beta}_{t}-\eta\widehat{\nabla_{\boldsymbol{\beta}}F}_{t}=\boldsymbol{\beta}_{t}-\eta\,\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t}), (24) where η \eta is a scalar, called the meta step size . In this case, 𝒚 t = 𝜷 t \boldsymbol{y}_{t}=\boldsymbol{\beta}_{t} . It then follows from ( 24 ) that d ​ 𝜷 t + 1 d ​ 𝒉 t = − η d d ​ 𝒉 t ( ℋ t T ∇ f t ( 𝒘 t ) ) = − η d d ​ 𝒉 t ( L t 𝒉 t ) = − η L t , \frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}\,=\,-\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(\mathcal{H}_{t}^{T}\nabla f_{t}(\boldsymbol{w}_{t})\big)\,=\,-\eta\frac{\mathrm{d}\,}{\mathrm{d}\,\boldsymbol{h}_{t}}\big(L_{t}\boldsymbol{h}_{t}\big)\,=\,-\eta L_{t}, (25) where the second equality is due to ( 23 ). Consequently, from ( 21 ), we obtain G t meta = [ d ​ 𝒚 t + 1 d ​ 𝒚 t d ​ 𝒚 t + 1 d ​ 𝒘 t 0 d ​ 𝒚 t + 1 d ​ 𝒉 t ] = [ d ​ 𝜷 t + 1 d ​ 𝜷 t d ​ 𝜷 t + 1 d ​ 𝒘 t 0 d ​ 𝜷 t + 1 d ​ 𝒉 t ] = [ I − η ​ ℋ t T ​ ∇ 2 f t ​ ( 𝒘 t ) 0 − η ​ L t ] , \begin{split}G^{\textrm{meta}}_{t}&=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{y}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{y}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{\beta}_{t}}}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{w}_{t}}}\\ \\ \end{array}&0&\hskip-7.0pt\begin{array}[]{c}\\ {\frac{\mathrm{d}\,\boldsymbol{\beta}_{t+1}}{\mathrm{d}\,\boldsymbol{h}_{t}}}\\ \\ \end{array}\end{array}\right]\\ &=\left[\begin{array}[]{cccc}\hskip-7.0pt\begin{array}[]{c}\\ {I}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {-\eta\mathcal{H}^{T}_{t}\nabla^{2}f_{t}(\boldsymbol{w}_{t})}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {0}\\ \\ \end{array}&\hskip-7.0pt\begin{array}[]{c}\\ {-\eta L_{t}}\\ \\ \end{array}\end{array}\right],\end{split} (26) where the last equality follows from ( 25 ) and simple differentiations of ( 24 ). Here, ∇ 2 f t ​ ( 𝒘 t ) \nabla^{2}f_{t}(\boldsymbol{w}_{t}) denotes the Hessian of f t f_{t} at 𝒘 t \boldsymbol{w}_{t} .

#### A.1.2 Meta Adam