勾配法のハイパラを勾配法によって最適化する"Gradient Descent: The Ultimate Optimizer"の論文をスプレッドシートで実装してみる

# 概要
この論文では、勾配法のハイパーパラメータを勾配法によって最適化するというアイデアが提案されています。

https://arxiv.org/abs/1909.13371

まず、論文を要約した上でスプレッドシートでの実装を示します。
# この論文の要約
勾配法は、最適化問題を解く上でよく用いられる手法です。例えば、AIの訓練や非線形ソルバーの中でも勾配法が広く採用されています。この勾配法ですが、動かすのに何個かのハイパーパラメータが必要になります。例えば、最急降下法と呼ばれる勾配法では学習率$\alpha$が、Adamと呼ばれる勾配法では学習率$\alpha$、1次モーメント推定値の指数減衰率$\beta_1$、2次モーメント推定値の指数減衰率$\beta_2$の3つのハイパーパラメータが必要になります。

勾配法で良い結果を得るためには、これらのハイパーパラメータを適切な値に設定する必要があります。適切なハイパーパラメータを探すことも、これまた最適化問題なのです。

**最適化問題を解きたいのに、そのためには最適化問題を解かないといけない。** そんな事に直面しているのが現状です。

じゃあさ、**そのハイパーパラメータも勾配法によって最適化すればいいのでは？** というのがこの論文のアイデアになります。

具体的には、以下のようなステップを毎エポックで実行します。なお、評価関数を$f$、最適化させたい変数を$v$、ハイパーパラメータを$h$とします。

> 1. $h$を勾配$\partial f(v)/\partial h$に基づいて勾配法で更新する。
> 2. $v$を勾配$\partial f(v)/\partial v$に基づいて勾配法(ハイパーパラメータとして$h$を持つ)で更新する。

変数$v$だけでなく、ハイパーパラメータ$h$も評価関数$f$がより小さくなる方向に調整してあげようということです。

論文によると、この手法はただの勾配法単体と比べて、DNNやRNNの訓練において、損失がより速く減るのだそうです！

# スプレッドシートで実装してみる！
### SGD on SGDについて
簡単な例として、SGDのハイパーパラメータである学習率$\alpha$をSGDによって最適化する時の処理を、スプレッドシート上で再現してみようと思います。SGD on SGDの処理は論文にも載っていましたが、

```math
\alpha_{i+1}=\alpha_i-\kappa \frac{\partial f(v_i)}{\partial \alpha_i}\\
v_{i+1}=v_i-\alpha_{i+1}\frac{\partial f(v_i)}{\partial v_i}
```

とやればOK。なお、$\kappa$とは、**SGDの学習率を最適化するSGDの学習率(ややこしい)** です。で、1番目の$\frac{\partial f(v_i)}{\partial \alpha_i}$は、展開すると
```math
\frac{\partial f(v_i)}{\partial \alpha_i}=-\frac{\partial f(v_i)}{\partial v_i}\frac{\partial f(v_{i-1})}{\partial v_{i-1}}
```
となるので(詳しい導出は論文を参照してください)、要するに過去2回の$f$に対する$v$の微分を覚えておいて、それらを掛けてマイナス付ければ求まるねーー💖💖という感じになっております。

### 問題設定
今回は、評価関数を
```math
f(v)=0.5v^2
```
と置いてみました。最適解は$v^*=0$です。また、それぞれの初期値や定数は
```math
v_0=9.0, \alpha_0=0.1, \kappa=10^{-3}
```
とします。

### 結果
スプレッドシートでは、🔹従来手法であるSGD単体(水色)と、🔸提案手法であるSGD on SGD(オレンジ色)を動かして、比較してみました。

_🔹従来手法であるSGD単体(水色)/🔸提案手法であるSGD on SGD(オレンジ色)_
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/fec410cf-92a0-b695-d164-292f17f0c349.png)

関数$f$に対するハイパーパラメータ$\alpha$の微分は、上記の通り、過去2回分の$v$の微分を掛けてマイナスをつけるだけ✨

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/c6615b5c-fb87-e0a2-dc1b-7bcc941bb408.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/b0df0a77-ce70-bca8-8222-95709201493f.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/879bf5b4-7d80-4d11-943d-8262efe17945.png)

SGD on SGDの方が、SGDよりも速く最適解に収束していることが分かります！！
また、学習率$\alpha$がどう動いてるかを以下に示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/3f844388-87a3-8868-02d9-040cf542dbcb.png)

最初0.10だった学習率が、増加をして0.33くらいになりました。今回は学習率を上げた方がより速く解が最適解に収束すると判断したようです。学習率の推移については論文内で示されていなかったので、見られて満足😉

# さいごに
勾配法のハイパーパラメータを勾配法によって最適化するアイデアについて、実際にスプレッドシートで実装したところ、学習率が最適化され、勾配法単体よりも速く収束することを確認できました。
スプレッドシートだけでなく、TensorFlow版も作りました。GitHubにも上げました。こちらではAdamも実装してるので、Adam on Adamとかもできます。こちらについても、気が向いたら解説Qiitaを作ろうと思います。
![gdtuo-tfkeras.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3116310/5027a53d-6187-71b4-4da8-87d6182c026b.png)

https://github.com/Mya-Mya/gdtuo_tf

気が向いたらね。

# 参考
Kartik. C.,ほか. (2022). Gradient Descent: The Ultimate Optimizer. Advances in Neural Information Processing Systems. https://openreview.net/forum?id=-Qp-3L-5ZdI

# ......お気づきだろうか
？「じゃあ、そのSGDのSGDのハイパーパラメータは誰が決めるんや？」
？「そりゃあ、SGDのSGDのSGDやで」
？「じゃあ、そのSGDのSGDのSGDのハイパーパラメータは誰が決めるんや？」
？「そりゃあ、SGDのSGDのSGDのSGDやで」
？「じゃあ、そのSGDのSGDのSGDのSGDのハイパーパラメータは誰が決めるんや？」
？「そりゃあ、...

無　限　ル　ー　プ　っ　て　怖　く　ね　？

この事に関しては、論文では「様々な勾配法をビルのごとく積み上げることができ、積み上げれば積み上げるほど、最適化の結果がハイパーパラメータに依存しなくなる」とされています。