論文ノートライブラリに戻る
ICLR 2018arXiv 2019オプティマイザ論文ノート

AMSGrad

喉元過ぎれば熱さを忘れる

原論文

On the Convergence of Adam and Beyond

論文の著者

Sashank J. Reddi · Satyen Kale · Sanjiv Kumar

発表先
ICLR 2018国際会議
arXiv への初回投稿
arXiv:1904.09237
この論文を引用 · BibTeX

引用情報はリンク先の論文の版に対応し、原論文の著者を記載しています。

@misc{optimizersamsgrad2019,
  title = {{On the Convergence of Adam and Beyond}},
  author = {Sashank J. Reddi and Satyen Kale and Sanjiv Kumar},
  year = {2019},
  eprint = {1904.09237},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.09237}
}
このページの内容

まず小さなゲームをしよう。

パラメータ xx は −1-1 から 11 のあいだにしかいられない。3 ステップを 1 ラウンドとし、1 ステップ目の損失は 3x3x、2 ステップ目と 3 ステップ目の損失はどちらも −x-x だ。1 ラウンドの合計は 3x−x−x=x3x-x-x=x なので、xx は小さいほど良く、答えは x=−1x=-1 になる。

勾配は簡単に計算できて、1 ステップ目が +3+3、あとの 2 ステップが −1-1 だ。SGD は 1 ラウンドごとに負の方向へ正味 1 ステップ分進み、最後は −1-1 に止まる。

Adam は x=+1x=+1、区間全体で最悪の点に止まる。

この例は Google の Sashank Reddi、Satyen Kale、Sanjiv Kumar によるものだ。彼らはこれを使って Adam の元論文の収束定理が間違っていることを証明し、さらに誤りの箇所から、一行だけを変えた修正版 AMSGrad を導いた。

問題の定義

Adam が主張した収束

Adam の論文は、オンライン凸最適化の枠組みで収束を分析している。各ステップで、アルゴリズムはまずパラメータ xtx_t を選び、そのあとでこのステップの凸損失関数 ftf_t を見る。評価基準はリグレット(regret)、つまり累積損失が「後から見て最良の固定パラメータ」よりどれだけ多いかだ。

RT=∑t=1Tft(xt)−min⁡x∈F∑t=1Tft(x)R_T=\sum_{t=1}^{T}f_t(x_t)-\min_{x\in\mathcal F}\sum_{t=1}^{T}f_t(x)

平均リグレット RT/TR_T/T が 0 に近づけば、平均的にはアルゴリズムが最良の固定解に追いついたことになる。Adam の論文の Theorem 4.1 は、勾配が有界、β12/β2<1\beta_1^2/\sqrt{\beta_2}<1、学習率 αt=α/t\alpha_t=\alpha/\sqrt t などの条件のもとで、Adam のリグレットは O(T)O(\sqrt T) で、平均リグレットは 0 に近づくと主張した。

冒頭のゲームは、まさにオンライン凸最適化だ。どの ftf_t も線形関数で、実行可能領域は [−1,1][-1,1]。Adam は +1+1 に止まり、1 ラウンドごとに x=−1x=-1 より一定の損失を余計に払うので、平均リグレットはいつまでも 0 に近づかない。

実効学習率は大きくなりうるか

Reddi らは、問題をある量に絞り込んだ。各種の適応的手法を同じ枠組みで書くと、各ステップの更新は xt+1=xt−αtmt/Vtx_{t+1}=x_t-\alpha_t m_t/\sqrt{V_t} で、αt/Vt\alpha_t/\sqrt{V_t} が各パラメータの実際の学習率になる。その逆数が時間とともにどう変わるかを見る。

Γt+1=Vt+1αt+1−Vtαt\Gamma_{t+1}=\frac{\sqrt{V_{t+1}}}{\alpha_{t+1}}-\frac{\sqrt{V_t}}{\alpha_t}

SGD の VtV_t は固定で、αt\alpha_t は減っていく。AdaGrad の VtV_t は過去の勾配の二乗の平均で、α/t\alpha/\sqrt t と組み合わせると、分母は実質的に勾配の二乗和になり、増える一方だ。どちらも Γt\Gamma_t が負になることはなく、学習率は小さくなるだけだ。

Adam と RMSProp が使うのは指数移動平均だ。直近の勾配が小さくなると vtv_t もそれにつれて小さくなり、学習率はかえって大きくなる。Γt\Gamma_t は負になりうる。

論文の冒頭では、実際に見られる状況を説明している。出力空間がとても大きい問題では、一部のミニバッチがとても大きく情報量の多い勾配をもたらすが、それはめったに現れない。指数移動平均のせいでその影響はすぐに消え、訓練はうまく収束しない。この論文がやろうとしているのは、この直感を証明できる反例にすることだ。

問題の解決

反例:3 ステップに一度の大きな勾配

論文の Theorem 1 は、冒頭のゲームを一般化したものだ。損失関数は順に

ft(x)={Cx,t mod 3=1−x,それ以外x∈[−1,1], C>2f_t(x)= \begin{cases} Cx, & t \bmod 3 = 1\\ -x, & \text{それ以外} \end{cases} \qquad x\in[-1,1],\ C>2

1 ラウンドの勾配の合計は C−2>0C-2>0 で、最適解は x=−1x=-1 だ。Adam の設定は β1=0\beta_1=0、β2=1/(1+C2)\beta_2=1/(1+C^2)、αt=α/t\alpha_t=\alpha/\sqrt t で、さらに α<1−β2\alpha<\sqrt{1-\beta_2}。このパラメータは、Adam の論文が要求する β12/β2<1\beta_1^2/\sqrt{\beta_2}<1 を満たしている。論文の付録は帰納法で、x1=1x_1=1 から出発すると、毎ラウンドの終わりに xx が必ず 11 に戻ることを証明している。

なぜだろうか? C=3C=3 をとると β2=0.1\beta_2=0.1 になるので、1 ラウンドを直接計算してみよう。vtv_t は数ラウンドで一定の周期に入り、下の表はその周期の 1 ラウンドだ。表の最後の 2 列は gt/vtg_t/\sqrt{v_t} で、正の値は xx を −1-1 の方へ押し、負の値は +1+1 の方へ押すことを表す。実際の更新量にはさらに αt\alpha_t が掛かるが、同じラウンドの 3 ステップの αt\alpha_t はほぼ同じなので、ここでは無視する。

ステップgtg_tvtv_tAdamAMSGrad
1+3+38.21+1.05+1.05+1.05+1.05
2−1-11.72−0.76-0.76−0.35-0.35
3−1-11.07−0.97-0.97−0.35-0.35
1 ラウンド+1+1−0.68-0.68+0.35+0.35

本稿での試算。C=3C=3、β1=0\beta_1=0、β2=0.1\beta_2=0.1 で、Theorem 1 の設定。AMSGrad の分母は過去最大の vv、つまり 8.21 を使う。

まず Adam の列を見よう。1 ステップ目の勾配は +3+3 だが、vtv_t も同時にそれに押し上げられて 8.21 になり、3/8.21≈1.053/\sqrt{8.21}\approx1.05 と、大きな勾配が 3 倍近く縮められている。論文が、大きな勾配 CC は「ほぼ CC 倍」縮められると言っているのは、このことだ。続く 2 ステップでは勾配は −1-1 しかなく、vtv_t は 1 ステップごとに 1 割しか残らない速さで 1.72、1.07 まで下がり、学習率は 2 ステップのうちに 3 倍近くまで膨らむ。二つの小さな勾配は合わせて 1.731.73 押す。1 ラウンドを終えると、正味では間違った方向に 0.680.68 進んでいる。

これが Γt<0\Gamma_t<0 の具体的な姿だ。大きな勾配がもたらした教訓は、2 ステップ後にはほとんど忘れられている。

この設定で α=0.5\alpha=0.5 として実際に 30 万ステップ反復すると、Adam は x=1x=1 に止まり、平均リグレットは 0.6670.667、ちょうど論文が示す下界 (2C−4)/3(2C-4)/3 になる。同じ条件で AMSGrad は −0.999-0.999 まで進む。

論文はさらにいくつか補足している。この例は固定の歩幅 αt=α\alpha_t=\alpha でも同様に成り立つ。分母に ϵ\epsilon を足しても救えず、付録の Theorem 6 は、任意の ϵ>0\epsilon>0 に対して同様の反例を作れることを示している。SGD と AdaGrad は、同じ問題で平均リグレットがどちらも 0 に近づく。

実際に使う β\beta に変えると

β2=0.1\beta_2=0.1 はあまりに作為的で、実際には β2\beta_2 はどれも 1 に近い。論文は続けて、より強い結果を二つ証明している。

Theorem 2 は、β1<β2\beta_1<\sqrt{\beta_2} であれば(実際の設定はほぼすべて満たす)、Adam の平均リグレットが 0 に近づかないオンライン凸問題が存在すると述べる。構成の仕方は同じで、周期を 3 から CC に延ばすだけだ。CC ステップに一度勾配 CC が現れ、残りはすべて −1-1 になる。CC は十分大きく、β2\beta_2 の記憶が 1 周期もたないほど大きくなければならない。

十分大きいとは、どれくらいか? 付録には三つの条件が挙げられていて、その一つが β2(C−2)/2C2≤1\beta_2^{(C-2)/2}C^2\le1 だ。数字を代入して計算すると、β2=0.99\beta_2=0.99 では CC は少なくとも 3,218(付録 B は CC が偶数であることも求めている。この不等式だけなら 3,217)、β2=0.999\beta_2=0.999 では少なくとも 42,622 になる。つまり 4 万ステップあまりに一度、普段より 4 万倍以上大きい勾配が現れるということだ。

Theorem 3 は舞台を確率的最適化に移す。各ステップで独立にサンプリングし、確率 p=(1+δ)/(C+1)p=(1+\delta)/(C+1) で CxCx を、それ以外は −x-x を見る。損失の期待値は δx\delta x で、最適解はやはり −1-1 だ。しかし CC が十分大きいと、Adam の各ステップの移動量の期待値は正になり、パラメータは最適解から遠ざかる方向へ漂っていく。

著者らの結論は、こうした振る舞いを避けたければ、ϵ\epsilon、β1\beta_1、β2\beta_2 をすべて問題に応じて決める必要がある、というものだ。高次元の問題では次元ごとに一組ずつ必要になることさえあり、これはハイパーパラメータの調整がいらないという適応的手法の本来の趣旨に反する。彼らは例が意図的に構成されたものであることも認めているが、実際の状況でも似た現象が少なくとも収束を遅らせるだろうと考えている。

証明はどこで間違えたか

反例があるなら、Adam の元の証明のどこかの段階が成り立っていないはずだ。論文は第 4 節と付録 D で、Adam の証明は Γt\Gamma_t が半正定値、つまり学習率が大きくならないと仮定しており、この仮定は Adam では成り立たないと指摘している。さらに、Adam の証明の補題 10.3 と 10.4 にも問題がある。

SGD と AdaGrad の学習率はもともと単調非増加なので、この問題にはぶつからない。この観察が、そのまま修正の方法を指し示している。

AMSGrad

問題が vtv_t が小さくなることにあるなら、分母に過去の最大値を覚えさせればよい。

mt=β1t mt−1+(1−β1t) gtvt=β2 vt−1+(1−β2) gt2v^t=max⁡(v^t−1, vt)xt+1=ΠF,V^t(xt−αt mt/v^t)\begin{aligned} m_t &= \beta_{1t}\, m_{t-1} + (1-\beta_{1t})\, g_t\\ v_t &= \beta_2\, v_{t-1} + (1-\beta_2)\, g_t^2\\ \hat v_t &= \max(\hat v_{t-1},\, v_t)\\ x_{t+1} &= \Pi_{\mathcal F,\sqrt{\hat V_t}}\big(x_t-\alpha_t\, m_t/\sqrt{\hat v_t}\big) \end{aligned}

Adam との違いは 3 行目だけだ。vtv_t はこれまでどおり指数移動平均で更新するので、勾配のスケールの推定は直近の一定期間だけを見る。しかし実際に分母として使う v^t\hat v_t は増える一方なので、学習率 αt/v^t\alpha_t/\sqrt{\hat v_t} は単調非増加になり、Γt\Gamma_t が半正定値であることが保証される。追加のコストは、パラメータと同じ大きさのベクトル 1 本だけだ。

上の表の AMSGrad の列に戻ろう。分母はずっと 8.21 のままで、二つの −1-1 はそれぞれ 0.350.35 しか押さず、1 ラウンドの正味の効果は、正しい方向に 0.350.35 進むことになる。

著者らは AMSGrad を、ある状況で Adam、AdaGrad と比べている。あるステップで vt−1>gt2>0v_{t-1}>g_t^2>0、つまりこのステップの勾配が直近の平均より小さいとする。

  • Adam は積極的に学習率を大きくする。前の反例は、まさにこの点に足をすくわれた。
  • AdaGrad は学習率を少し小さくする。長期的に積み重なると、学習率はほとんど動かないほど小さくなりかねない。
  • AMSGrad は大きくも小さくもしない。

AMSGrad の収束保証(Theorem 4)は、Adam の論文の分析の枠組みを引き継ぎ、上の問題を修正したものだ。条件は αt=α/t\alpha_t=\alpha/\sqrt t、β1t≤β1\beta_{1t}\le\beta_1、β1/β2<1\beta_1/\sqrt{\beta_2}<1、そして実行可能領域の直径と勾配が有界であることで、リグレットの上界には 1+log⁡T\sqrt{1+\log T} が一つ加わる。論文によれば、β1t=β1λt−1\beta_{1t}=\beta_1\lambda^{t-1}、あるいはより穏やかな β1/t\beta_1/t をとれば、どちらでも O(T)O(\sqrt T) のリグレットが保証される。

注意すべき細部が二つある。証明には β1\beta_1 が時間とともに減ることが必要だが、著者らも、実際にはふつう β1\beta_1 を固定すると明記している。また、論文の Adam はバイアス補正を外している。脚注によれば簡単のためで、反例の議論は補正ありの版にも同様に当てはまる。AMSGrad の Algorithm 2 にもバイアス補正はない。

論文はもう一つの道として AdamNC も示している。構造は変えず、β2\beta_2 を時間とともに大きくするものだ。β2t=1−1/t\beta_{2t}=1-1/t とすると、vtv_t はちょうど過去のすべての勾配の二乗の平均になり、モーメンタム付きの AdaGrad と同じになる。

議論

合成実験

3 枚の折れ線グラフで、横軸はどれも反復回数(数百万ステップ)。左はオンライン設定の平均リグレットで、Adam(青の破線)は約 0.21 で止まり、AMSGrad(緑の実線)は 0 近くまで下がり続ける。中央はオンライン設定のパラメータ x で、Adam はすぐに 1 まで上がってそこに止まり、AMSGrad は −1 に止まる。右は確率的設定のパラメータ x で、Adam は 1 付近に止まり、AMSGrad は 1 から下がり続け、約 1,000 万ステップで −0.85 付近にいる。
原論文 Figure 1(Reddi ら)、PDF 6 ページより。arXiv ライセンス、学術引用。

実験に使ったのは、反例を拡大した版だ。101 ステップに一度損失 1010x1010x が現れ、残りの 100 ステップは −10x-10x で、1 周期の勾配の合計は +10+10、最適解はやはり −1-1 だ。今回は一般的な β1=0.9\beta_1=0.9、β2=0.99\beta_2=0.99 を使い、二つの手法のパラメータは同じにしている。

左図は平均リグレットだ。Adam の青い破線は 0.21 付近で平らになり、もう下がらない。AMSGrad の緑線は 0 近くまで下がる。中央の図はパラメータそのもので、Adam は +1+1 に、AMSGrad は −1-1 に止まる。

右図は確率的な版で、各ステップで 1% の確率で 1010x1010x を、それ以外は −10x-10x を見る。Adam はやはり +1+1 に止まる。AMSGrad はとてもゆっくり下がっていき、1,000 万ステップでおよそ −0.85-0.85 と、まだ −1-1 には届いていない。

実データ

上段の 3 枚はどれも MNIST で、横軸は 0 から 5000 反復。ロジスティック回帰の訓練損失とテスト損失では、AMSGrad(緑)がどちらも Adam(青の破線)よりわずかに低く、最後は約 0.25 と 0.27。隠れ層 1 層のネットワークの訓練損失でも AMSGrad がわずかに低い。下段の 2 枚は CIFAR-10 での CIFARNET で、横軸は約 200 万反復まで。訓練損失は AMSGrad が約 0.3、Adam が約 0.4。テスト損失は両者とも 0.6 付近で振動し、AMSGrad がわずかに低い。
原論文 Figure 2(Reddi ら)、PDF 7 ページより。arXiv ライセンス、学術引用。

実データの実験は三組あり、バッチサイズはどれも 128、β1=0.9\beta_1=0.9、β2\beta_2 は {0.99,0.999}\{0.99,0.999\} から選ぶ。

  1. MNIST のロジスティック回帰(上段の左と中央)。凸問題で、学習率は理論どおり α/t\alpha/\sqrt t で減衰させ、α\alpha と β2\beta_2 はグリッドサーチで決める。AMSGrad は訓練損失もテスト損失もわずかに低く、著者らは、パラメータの変動にも比較的鈍感だと述べている。
  2. MNIST の隠れ層 1 層のネットワーク(上段の右)。ReLU 100 個で、学習率は固定。AMSGrad の訓練損失はずっと Adam よりわずかに低い。
  3. CIFAR-10 の CIFARNET(下段)。64 チャネル、6×66\times6 の畳み込み 2 層に、384 と 192 の全結合層が続き、あいだに最大プーリング、局所応答正規化、dropout が入る。差が最もはっきり出るのは訓練損失で、およそ 0.3 対 0.4。テスト損失は両者とも 0.6 付近で、AMSGrad がわずかに低い。

この結果を読むときは、その範囲を知っておく必要がある。図には損失しかなく、正解率はない(本文では AMSGrad の正解率も良いと言っているが、数字は示していない)。どの曲線も 1 回の実行に見え、誤差の幅はない。モデルもどれも小さい。著者ら自身、貢献のリストでこれを予備的な実験と呼んでいる。

実務での反応

AMSGrad はすぐに主要なフレームワークに取り込まれ、PyTorch と Keras の Adam にはどちらも amsgrad 引数がある。デフォルトはオフだ。

実際に試した人たちの反応は、あまり熱のこもったものではなかった。fast.ai の Sylvain Gugger と Jeremy Howard は 2018 年 7 月の記事で、CIFAR-10 の Wide ResNet、Stanford Cars での ResNet-50 の微調整、WikiText-2 での AWD-LSTM と QRNN の言語モデルで比べ、amsgrad は正解率でもほかの指標でも一度も良い結果をもたらさなかったと書き、「非常に期待外れ」だったと評している。

AMSGrad 自身の証明も、のちに問題を指摘された。Phuong と Phong は 2019 年、その証明が β1t\beta_{1t} と β1\beta_1 を扱う際に両者を等しいものとみなしていると指摘した。Adam の元の証明にも同じ見落としがある。彼らは新しい証明を示し、別の変種 AdamX も提案した。

Adam は実は収束する?

反例は成り立つ。そして Adam は実際に使いやすい。この二つをどう両立させればよいのか? 後続のいくつかの研究が出した答えは、先に何を固定したかによって違う。

研究先に固定するもの結論
Reddi ら 2018先に β\beta を選び、次に問題を作るAdam は収束しないことがある
Zhang ら 2022先に問題を与え、次に β\beta を選ぶβ2\beta_2 が十分大きければ収束する
ADOPT 2024アルゴリズムを変えるどんな β2\beta_2 でも収束する

Zhang ら 2022 は、順序の問題を指摘した。Reddi らは先に (β1,β2)(\beta_1,\beta_2) を選び、それに合わせて悪い問題を構成している。前に計算したとおり、β2=0.999\beta_2=0.999 には 4 万ステップあまりの周期が必要だ。ところが実際には、問題が先にあって、私たちはそれからハイパーパラメータを調整する。彼らは、固定した問題に対して、β2\beta_2 が十分大きく(しきい値は問題による)、かつ β1<β2\beta_1<\sqrt{\beta_2} であれば、更新則を一切変えない Adam が臨界点の近くに収束し、その範囲の大きさは確率的勾配の分散に比例することを証明した。より強い条件のもとでは、臨界点そのものに収束する。この分析は非凸の有限和問題を対象とし、エポックごとにサンプルの順序をランダムに並べ替えるもので、勾配が有界という仮定を必要とせず、デフォルトの β1=0.9\beta_1=0.9 もカバーしている。逆に、β2\beta_2 が小さすぎると、発散する (β1,β2)(\beta_1,\beta_2) の領域が広く存在する。

同じ時期、Défossez らは、滑らかな非凸で勾配が有界という条件のもとで簡潔な収束証明を示し、デフォルトのパラメータの Adam は厳密には収束せず、振る舞いは固定歩幅の SGD に近いことも指摘した。

ADOPT 2024 は、AMSGrad を見直した。非凸問題での AMSGrad の収束証明は、どれも確率的勾配が一様有界だと仮定しているが、変分オートエンコーダや拡散モデルのように勾配にガウスノイズを注入するモデルは、この条件を満たさない。問題は最大値を取るステップにあり、期待値の制御が難しい。ADOPT は別のやり方をとる。一つ前のステップの vt−1v_{t-1} でこのステップの勾配を正規化して、分母に現在の勾配が含まれないようにし、さらに先に正規化してからモーメンタムを蓄積する。勾配の二次モーメントが有限という条件のもとで、任意の β2\beta_2 に対して O(1/T)O(1/\sqrt T) の収束レートを達成する。

最後に、脚注をもう一つ。2026 年 7 月のプレプリント〈On the Convergence of Adam, Revisited〉は、Reddi らと同じオンライン設定で、β1<β2\beta_1<\sqrt{\beta_2} という条件すら必要なく、任意の β1,β2\beta_1,\beta_2 に対して Adam の平均リグレットが 0 にならない例を見つけられると主張している。使っているのはやはり傾き c,−1,−1c,-1,-1 の 3 ステップの周期で、しかも AdamW や Muon などの変種にも一般化できるという。これは Zhang らの肯定的な結果と矛盾しない。両者は、順序の異なる問いに答えている。

結論

この論文は、3 ステップで 1 ラウンドの線形関数を使って Adam の元の収束定理が誤っていることを証明し、問題が、指数移動平均によって学習率が大きくなりうる点にあると突き止めた。AMSGrad は過去の最大値を分母に使って学習率を単調非増加にし、凸問題での収束保証を取り戻した。実データでの改善はわずかで、実験も予備的な段階にとどまり、のちの独立したテストの多くでは利点が見られなかった。この論文がのちの研究に残したのは、Γt\Gamma_t という分析の視点と、「どちらを先に固定するか」という問いだ。

実務では、amsgrad=True はただのスイッチだ。データにまれだが重要な大きい勾配があると疑われるときは、β2\beta_2 を大きくすることと並べて、比較の候補に入れるとよい。前者の追加コストはパラメータと同じ大きさの状態 1 本分だけで、後者はコストがまったく増えない。Zhang らは、β2\beta_2 が小さすぎると発散する領域が広く存在することを証明した。この結果に従うなら、反応を速くしようとして β2\beta_2 を下げ、訓練が不安定になったときは、まず 1 に近い値に戻してみることだ。

3 ステップで 1 ラウンドの小さなゲームは、その後も引退していない。8 年後もやはり同じ c,−1,−1c,-1,-1 で、今回は β1<β2\beta_1<\sqrt{\beta_2} すら仮定せず、ついでに AdamW と Muon まで巻き込んだ。