1. はじめに
機械学習では、多くが目的関数(凸関数)を最適化する問題として定式化され、勾配・劣勾配をヒントとして逐次的に目的関数を下げていくわけです。その際、学習率のスケジューリングに頭を悩ませます。そこで、学習率のスケジューリングに関しAdaGrad[J.Duchi]と呼ばれる手法が有効である事が示されました。実装が容易という背景もあり、一気に広まりました。他にもAdaDelta, RMSProp, Adamなど有名で、Qiitaにも各種法を経験的に比較している投稿[1]があります。
ですので、本投稿では実装の話がありません。理論を整理します。なぜ、AdaGradの性能が良いかへの答えは、標準的なSGDよりタイトなRegret上限バウンドを理論的導出したためとなります。
以降で使用するAdaGradはComposite Mirror Descent
\mathbf{x}_{t+1} = argmax_{x \in X} \ \eta<\mathbf{g}_t, \mathbf{x}> + \eta \phi(\mathbf{x}) + B_{\phi_t}(\mathbf{x}, \mathbf{x}_t)
, where
\begin{eqnarray}
\mathbf{x} &:& \text{weight vector} \\
dim(\mathbf{x}) &=& d, \text{d is feature dim} \\
B_{\phi_t}(\mathbf{x}, \mathbf{x}_t) &=& \phi_t(\mathbf{x}) - \phi_t(\mathbf{x}_t) - <\nabla \phi_t(\mathbf{x}_t), \mathbf{x} - \mathbf{x}_t> \\
\phi_t &:& \text{differentiable and strongly-convex} \\
\varphi_t(\mathbf{x}) &=& f_t(\mathbf{x}) + \phi(\mathbf{x}) \\
\mathbf{g}_t &\in& \partial f_t(\mathbf{x}_t)
\end{eqnarray}
によりweigthを更新する場合を指します。論文中ではPrimal-dual subgrandientによるweightの更新も導出しています。
まず第2章でRegretがどの様な量かを整理します。その後、SGDとAdaGradにおけるRegretがどの様に定式化されるかを確認し、第4章ではこれを用いて収束レートを導出します。同時に、AdaGradではデータ適合的という文脈が使われることが多いですが、その説明を定性的にしたいと思います。最後に第5章では、第3章で用いたAdaGradに関するRegretを導出するための定理・命題・補題・系を簡単に導きます。詳細は[SlideShare]を参照して頂くとして、なるべく定性的に記したいと思います。
非常に簡潔にまとめると、AdaGradは$O(log(d))$で収束するのに対し、SGDは$O(\sqrt{d})$で収束するため、AdaGradの方がSGDより理論的にタイトなRegretバウントをもっていて、かつ学習率も自動的に定式化できるという仕組みです。
2. Regretとは
そもそもRegretという概念が必要になったのは、パラメータ更新の手段としてバッチ処理を代替する方法が必要だったという背景なのだと思います。大規模データをバッチ処理していてはいつまでたっても計算が終わらないので、部分データでパラメータを更新(ミニバッチ)し、バッチとミニバッチの目的関数にどの程度差があるかを測る意図があったのではないでしょうか。測る手段としてRegretが用いられています。他方、逐次処理が必要なシステムニーズも一因かなと思います。以下がRegretの定義です；
R_{\varphi}(T) = \sum_{t=1}^{T} \varphi_t(\mathbf{x}_t) - \varphi_t(\mathbf{x}^*)
, where
\begin{eqnarray}
\varphi_t(\mathbf{x}) &=& f_t(\mathbf{x}) + \phi(\mathbf{x}) \\
\mathbf{x}^* &:& \text{weight最適解} \\
\mathbf{x}_t &:& \text{weight逐次解}
\end{eqnarray}
式としてのポイントは
- 最適weight解から生じた損失。損失関数は$\varphi_t$
- 逐次weight解から生じた損失。損失関数は$\varphi_t$
つまり、損失関数は同じだけれども、weightに逐次解と最適解という違いが重要で、Regretが小さいとは逐次解と最適解から生じる誤差が小さいという意味になります。一種の最適化誤差のようなものです。
3. SGDとAdaGradにおけるRegret
以下では、ものすごくラフにSGDとAdaGradのRegretバウントを記します。
- SGD
\begin{eqnarray}
\sum_{t=1}^{T} \varphi_t(\mathbf{x}_t) - \varphi_t(\mathbf{x}^*) &\leq& \sqrt{2} D_2 \sqrt{\sum_{t=1}^{T} ||\mathbf{g_t}||_2^2} \\
sup_{x,y \in X} ||\mathbf{x} - \mathbf{y}||_2 &\leq& D_2 \\
\mathbf{g}_t &=& \partial f_t(\mathbf{x}_t)
\end{eqnarray}
- AdaGrad
\sum_{t=1}^{T} \varphi_t(\mathbf{x}_t) - \varphi_t(\mathbf{x}^*) \leq \sqrt{2} D_\infty \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2
, where
\begin{eqnarray}
sup_{x,y \in X} ||\mathbf{x} - \mathbf{y}||_{\infty} &\leq& D_{\infty} \\
\mathbf{g}_{1:t} &=& [\mathbf{g}_1, \mathbf{g}_2, ..., \mathbf{g}_t] \\
\mathbf{g}_{1:t, i} &:& \text{the i-th row in Matrix $\mathbf{g}_{1:t}$ }
\end{eqnarray}
4. SGDとAdaGradにおける収束レート
- SGD
- 上式の$D_2=2\sqrt{d}$とおき、$||\mathbf{g}_t||_2^2 \leq 1$とすればベストバウンドのオーダーは
\begin{eqnarray}
\frac{1}{T} E[Regret(SGD)] \propto O \Biggl( \frac{\sqrt{d}}{\sqrt{T}} \Biggr)
\end{eqnarray}
- AdaGrad
2通りの導出方法があるのですが、それぞれ$||\mathbf{g}_{1:T,i}||_2$をどの様にバウンドするかが異なっています。 また、以下の式は使うので、予めメモしておきます。
\begin{eqnarray}
\sum_{i=1}^{d} i^{-\frac{\alpha}{2}} = \left\{
\begin{array}{ll}
O(log(d)) & (2 \leq \alpha) \\
O(d^{1-\frac{\alpha}{2}}) & (\alpha \in (1,2)) \\
\end{array}
\right.
\end{eqnarray}
- 導出1
$\mathbf{g}_{1:T}$に関して以下の仮定をおく、
\begin{eqnarray}
\mathbf{g}_{1:T,i,t}^2 \leq G \ i^{-2}, i=(1,2,...,d), t=(1,...,T)
\end{eqnarray}
, where
\begin{eqnarray}
\mathbf{g}_{1:T} &:& \text{d $\times$ Tの行列} \\
d &:& \text{feature dim} \\
T &:& \text{Iteration Num} \\
\mathbf{g}_{1:T,i,t} &:& \text{行列$\mathbf{g}_{1:T}$のi行t列目の要素}
\end{eqnarray}
すると
\begin{eqnarray}
|| \mathbf{g}_{1:T,i} ||_2 &=& \sqrt{\sum_{t=1}^{T} \mathbf{g}_{1:T,i,t}^2} \\
& \leq & \sqrt{\sum_{t=1}^{T} G \ i^{-2}} = Gi^{-1}\sqrt{T}
\end{eqnarray}
となる。
よって、
\begin{eqnarray}
\frac{1}{T} E[Regret(AdaGrad)] & \leq & \frac{\sqrt{2}D_{\infty}}{T} \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 \\
& \leq & \frac{\sqrt{2}D_{\infty}}{\sqrt{T}} \sum_{i=1}^{d} i^{-1} \propto O \Biggl( \frac{\sqrt{2}D_{\infty}}{\sqrt{T}} log(d) \Biggr)
\end{eqnarray}
- 導出2
導出1では、どこがデータ適合的なのかサッパリわからないので、データ適合的の所以を説明してみたいと思います。
\begin{eqnarray}
||\mathbf{g}_{1:T,i}||_2 = |\{t: |g_{t,i}|=1 \}|
\end{eqnarray}
と仮定します。この仮定は、イテレーションtにおける(sub)gradientに対する仮定です。この仮定とJensenの不等式を用いて、
\begin{eqnarray}
E \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 & = & \sum_{i=1}^{d} E \sqrt{|\{t: |g_{t,i}|=1 \}|} \\
& \leq & \sum_{i=1}^{d} \sqrt{E |\{t: |g_{t,i}|=1 \}|}
\end{eqnarray}
次に、特徴量iがイテレーションtにおいて観測される確率$p_i$を以下の様に定義します；
\begin{eqnarray}
p_i = min \{1,c \ i^{-\alpha} \}
\end{eqnarray}
上式で定義された確率$p_i$は、スケーリング項cは置いておいて、$\alpha$乗で減衰しています。これは、y軸について対数をとると、傾き$-\alpha$の冪乗で減衰するheavy tailed分布となります。このような分布になるデータは・・・、スパースなデータにはよくある分布です。論文中に何気なく書いてありますが、この仮定がデータ適合的という意味です。(sub)gradientの情報を使って学習率を調整するので、直接的にはこれがデータ適合的という事になりますが、定性的には観測するデータのスパース性をRegertバウンドに反映させているという事が重要です。
\begin{eqnarray}
E \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 & \leq & \sum_{i=1}^{d} \sqrt{E |\{t: |g_{t,i}|=1 \}|} \\
& \leq & \sum_{i=1}^{d} \sqrt{p_i \ t} \\
& \leq & \sum_{i=1}^{d} \sqrt{p_i \ T} \propto \sum_{i=1}^{d} \sqrt{T} i^{-\frac{\alpha}{2}}
\end{eqnarray}
結果として、
\begin{eqnarray}
\frac{1}{T} E[Regret(AdaGrad)] & \leq & \frac{\sqrt{2}D_{\infty}}{T} \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 \\
& \leq & \frac{\sqrt{2}D_{\infty}}{T} \sum_{i=1}^{d} i^{-\frac{\alpha}{2}} \propto O \Biggl( \frac{\sqrt{2}D_{\infty}}{\sqrt{T}} max \{ log(d), d^{1-\frac{\alpha}{2}} \} \Biggr)
\end{eqnarray}
ここで覚えておきたいことは、データのスパース性により$log(d), d^{1-\frac{\alpha}{2}}$どちらが収束レートになるか、empiricalにはわからないという事です。冪指数$\alpha$によって$log(d)$や$d^{1-\frac{\alpha}{2}}$となる為、実験をして、どの様な学習率がよいか確かめる必要があることです。
5. AdaGradにおけるRegretを導出する定理・命題・補題・系
AdaGradのRegretバウント、$\sqrt{2} D_\infty \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2$、に至るために必要な道具をまとめます。まず書いておかなければいけないのは、dual normという量を理解できておりません。そもそもノルムは内積を計算するもので、L2ノルム($<\mathbf{x}, \mathbf{x}>$)をルジャンドル変換により、L2ノルムに対するdualノルム$<\mathbf{x},A \mathbf{x}>$と変換するということが、解釈として何を意味しているかが分からないということです。
出来ていることは、数学として証明です。ですので、個人的にはモヤモヤしていますが、当初の目的はAdaGradはなぜ機能するのかという事から勉強がスタートしましたので、まあ良いかなと。おそらくフェンシェル双対性を理解できると何となく解釈が進むのではという感触です。
脱線してしまいましたが、AdaGradのRegretバウントを導出するために必要な道具を整理します。なお、本投稿における定理・命題・補題・系の番号は[J.Duchi, etc]に準じるものとさせて頂きます。
- Lemma16
\begin{eqnarray}
\forall_{x^* \in X} \ \eta \{ f_t(\mathbf{x}_t) - f_t(\mathbf{x}^*) \} + \eta \{ \phi(\mathbf{x}_{t+1}) - \phi(\mathbf{x}^*) \} &\leq& B_{\psi_t}(\mathbf{x}^*, \mathbf{x}_t) - B_{\psi_t}(\mathbf{x}^*, \mathbf{x}_{t+1}) + \frac{\eta^2}{2} ||\dot{f}_t(\mathbf{x}_t)||_{\psi_{t}^{*}}^2 \\
||\mathbf{a}||_{\psi} &=& <\mathbf{a}, \psi \mathbf{a}>
\end{eqnarray}
証明は、SlideShareP4をお読みください。ここで重要なのはBergman Divergenceが突如出てきていることです。これは、Bergman Divergenceの性質とComposite Mirror Descent更新により発生した項です。Bergman Divergenceの定義は
B_{\phi}(\mathbf{a},\mathbf{b}) = \phi(\mathbf{a}) - \phi(\mathbf{b}) - <\nabla \phi(\mathbf{b}), \mathbf{a}-\mathbf{b}>
ですので、以下が成り立ちます
B_{\phi}(\mathbf{a},\mathbf{b}) + B_{\phi}(\mathbf{b},\mathbf{c}) = B_{\phi}(\mathbf{a},\mathbf{c}) + <\nabla \phi(\mathbf{c}) - \nabla \phi(\mathbf{b}), \mathbf{a} - \mathbf{b}>
上式の最後の項は勾配の引き算になっているのですが、この項によりBergman Divergenceが出てきます。詳細は[SlideShare]P5の⑨''を参照してください。
あと重要なのが、$<\mathbf{a},\mathbf{b}>$の上限をノルムと双対ノルムの足し算で抑えることです。ここを直感的に理解できると双対ノルムが何を表すかが分かる気もするのですが・・・。正則化の理論がすきすぎて、内積を二種類のノルムに分解しているように見えますw。ちなみに、以下の不等式です；
\text{For a function $\psi$} \\
<\mathbf{a}, \mathbf{b}> \ \leq \ \frac{1}{2} ||a||_{\psi}^2 + \frac{1}{2} ||b||_{\psi^*}^2
この式を見て思うのが、双対ノルムはノルムに対して計算されるものなので一対なわけですが、ノルムを計算する関数$\psi$は元の内積$<\mathbf{a}, \mathbf{b}>$に依存していないという事が気になっている、ということは書き留めておきたいと思います。
- Proposition3(Regret Bound with Compoisite Mirror Descent Update)
\begin{eqnarray}
\forall_{x^* \in X} \sum_{t=1}^{T} \{ f_t(\mathbf{x}_t) + \phi(\mathbf{x}_{t} \} - \{ f_t(\mathbf{x}^*) + \phi(\mathbf{x}^*) \} \leq \frac{1}{\eta} B_{\psi_1}(\mathbf{x}^*, \mathbf{x}_1) + \frac{1}{\eta} \sum_{t=1}^{T-1} \{ B_{\psi_{t+1}}(\mathbf{x}^*, \mathbf{x}_{t+1}) - B_{\psi_{t}}(\mathbf{x}^*, \mathbf{x}_{t+1}) \} + \frac{\eta}{2} \sum_{t=1}^{T} ||\dot{f}_t(\mathbf{x}_t)||_{\psi_{t}^{*}}^2
\end{eqnarray}
これは、Lemma16を足し上げる、ただし$\phi( \mathbf{x}_1 )=0$、でできます
AdaGradのRegretバウントを見据えた方針を述べておきますと、Prop3で導出されるバウントには大きく二種類の項があります。Bergman Divergenceと双対ノルムです。一見異なるこの二つをまとめあげないと、AdaGradのRegretバウントは導出できません。まずは、双対ノルムのバウントをLemma4と名無し①で導出します。次に、名無し②・名無し③でBergman Divergenceをバウンドします。これらを用いるとAdaGradのRegretバウントが導出できます。
- Lemma4
\sum_{t=1}^{T} <\mathbf{g}_t, diag(S_t)^{-1} \mathbf{g}_t> \ \leq \ 2 \sum_{i=1}^{d} ||\mathbf{g}_{1:T, i}||
,where
S_{\tau,i} = ||\mathbf{g}_{1:\tau, i}||_2
これは、淡々と証明していくしかありません。詳細はP6に記載してあります。
- 名無し①
||\dot{f}_t(\mathbf{x}_t)||_{\psi_{t}^{*}}^2 \ \leq \ <\mathbf{g}_t, diag(S_t)^-1 \mathbf{g}_t>
これもそんなに難しくなく、淡々と証明するのみです。詳細はP7に記載してあります。
すると、Lemma4と名無し①を組み合わせて
\sum_{t=1}^{T} ||\dot{f}_t(\mathbf{x}_t)||_{\psi_{t}^{*}}^2 \leq 2 \sum_{i=1}^{d} ||\mathbf{g}_{1:T, i}||
が導出できます。ようやく、双対ノルムを$||\mathbf{g}_{1:T,i}||_2$でバウンド出来ました
- 名無し②
B_{\psi_{t+1}} (\mathbf{x}^*, \mathbf{x}_{t+1}) - B_{\psi_{t}} (\mathbf{x}^*, \mathbf{x}_{t+1}) \leq \frac{1}{2} max_{i} (\mathbf{x}_i^* - \mathbf{x}_{t+1,i})^2 ||S_{t+1} - S_{t}||_1
これまた粛々と証明するだけです。詳細はP8の③を参照してください。
- 名無し③
\sum_{t=1}^{T-1} B_{\psi_{t+1}} (\mathbf{x}^*, \mathbf{x}_{t+1}) - B_{\psi_t} (\mathbf{x}^*, \mathbf{x}_{t+1}) \leq \frac{1}{2} max_{t \leq T} ||\mathbf{x}^* - \mathbf{x}_t||_{\infty}^2 \sum_{i=1}^{d} ||\mathbf{g}_{t:T,i}||_2 - \frac{1}{2} ||\mathbf{x}^* - \mathbf{x}_1||_{\infty}^2 <S_1, 1>
滝行は続きます、詳細はP9の(14)を参照してください。名無し②・名無し③でBergman Divergenceを$||\mathbf{g}_{1:T,i}||_2$でバウンド出来ました。Bergman Divergenceと双対ノルムをバウンドできたので、Theorem5が証明出来る様になりました。
- Theorem 5(Regret Bound for AdaGrad)
R_{\varphi}(T) \leq ||\mathbf{x}||_2^2 + \frac{1}{\eta} ||\mathbf{x}^*||_{\infty}^{2} \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 + \eta \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2
Lemma4・名無し①・名無し②・名無し③を用いれば、簡単にできます。詳細はP9を参照してください。
次のCorollary6でAdaGradのRegretバウント導出が完了します。
- Corollary6 Let
\begin{eqnarray}
D_{\infty} = sup_{x \in X} || \mathbf{x} - \mathbf{x}^* ||_{\infty} \\
\gamma_T = \sum_{i=1}^{d} ||\mathbf{g}_{1:T,i}||_2 = \sum_{i=1}^{d} <\mathbf{g}_t, diag(S)^{-1}\mathbf{g}_t> \\
\eta = \frac{D_{\infty}}{\sqrt{2}}
\end{eqnarray}
, then
\begin{eqnarray}
R_{\varphi}(T) \leq \sqrt{2}D_{\infty} \sum_{i=1}^{d} ||\mathbf{g}_{1:T, i}|| = \sum_{i=1}^{d} = \sqrt{2} D_{\infty} \gamma_T
\end{eqnarray}
6. 終わりに
いやー、latexを書くのに異様に疲れましたw。$\eta$というパラメータは計算する際にも設定するべきハイパーパラメータです。更新式は有名ですので、省略します。
キモは
- ノルムを双対ノルムへのルジャンドル変換して、メトリクスを変更する
- それにより、Bergman Divergenceと双対ノルムを$||\mathbf{g}_{1:T,i}||_2$でバウンドする
、以上が非常に印象に残っています。双対ノルムを直感的に理解していないので、どうしてもモヤモヤ感が残っていますが・・・。
実は、Composite Mirror Descent・FOBOSを証明した時もAdaGradを証明した時と同様に凸解析の基本を頻繁に用いたなと思っておりまして、一つ理解できると論文も大変読みやすくなるので、ご興味があれば全部書き下してみることをお勧めします。
発展的な内容として2つ挙げておきます。
対角行列でなくFull Matrix
今回は簡単のためLemma4にて対角行列($<\mathbf{g}_t, diag(S)^{-1}\mathbf{g}_t>$)を使いました。これは、Full Matrix版もあります。ただし、対角行列の逆行列が必要であることから分かるように、Full Matrixの逆行列が必要になります。逆行列の計算はとても重いので、一般的には対角行列を使っているようです効率的にFull Matrixを計算する
そんな中、Full Matrixを効率的に利用する論文がarXivに公開([N.A. Mehta, etc]、last revised 2016/10/4)されていました。まだ全然読んでいないのですが、論文の動機として、対角行列の要素が相関する場合はうまくいかないものの、Full Matrixを使うと逆行列の計算は重いが精度が良い。ですので、方針として、Full Matrixを逆行列の計算対象と非計算対象の二つに分解して、必要な逆行列の計算量を削減しているようです。間違っていたらごめんなさい。
参考文献
[J.Duchi, etc] Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, Journal of Machine
Learning Research, 12:2121 2159, 2011
[T.Suzuki] Stochastic Optimization Part II: Faster online stochastic methods and Batch stochastic optimization
[SlideShare] Note : Adaptive Subgradient Methods for Online Learning and Stochastic Optimization goo.gl/WduMNj
[Shalev-Shwartz S] Online Learning and Online Convex Optimization, Foundations and Trends in Machine Learning, 2011, 4(2): 107-194
[N.A. Mehta, etc] CompAdaGrad: A Compressed, Complementary, Computationally-Efficient Adaptive Gradient Method, arXiv:1609.03319, https://arxiv.org/abs/1609.03319
[1] ニューラルネットで最適化アルゴリズムを色々試してみる http://qiita.com/hogefugabar/items/1d4f6c905d0edbc71af2