このエントリーをはてなブックマークに追加

確率的最適化手法 Adam の論文の Lemma 10.3

Posted: 2016-03-30

Adam: A Method for Stochastic Optimization の Lemma 10.3 が、少し腑に落ちなかったので自分用に書いたメモです。

論文中の証明では、帰納法の仮定から導かれる式 \begin{align} \sum_{t = 1}^T \sqrt{\frac{g_{t,i}^2}{t}} \leq 2 G_\infty\sqrt{\norm{g_{1:T,i}}_2^2 - g_{T,i}^2} + \sqrt{\frac{g_{T,i}^2}{T}} \end{align} に、以下の不等式 \begin{align} \sqrt{\norm{g_{1:T,i}}_2^2 - g_{T,i}^2} \leq \norm{g_{1:T,i}}_2 - \frac{g_{T,i}^2}{2\sqrt{TG_\infty^2}} \end{align} を代入して \begin{align} \sum_{t = 1}^T \sqrt{\frac{g_{t,i}^2}{t}} \leq 2 G_\infty\norm{g_{1:T,i}}_2 \end{align} を示す、と書いてあります。

しかし実際に代入してみると \begin{align} \sum_{t = 1}^T \sqrt{\frac{g_{t,i}^2}{t}} & \leq 2 G_\infty\sqrt{\norm{g_{1:T,i}}_2^2 - g_{T,i}^2} + \sqrt{\frac{g_{T,i}^2}{T}} \\ &\leq 2G_\infty \parentheses{ \norm{g_{1:T,i}}_2 - \frac{g_{T,i}^2}{2\sqrt{TG_\infty^2}} } + \sqrt{\frac{g_{T,i}^2}{T}} \\ &= 2G_\infty \norm{g_{1:T,i}}_2 - \frac{g_{T,i}^2}{\sqrt{T}} + \sqrt{\frac{g_{T,i}^2}{T}} \\ &= 2G_\infty \norm{g_{1:T,i}}_2 + \frac{\sqrt{g_{T,i}^2} - g_{T,i}^2}{\sqrt{T}} \end{align} となるので,\(0 < \abs{g_{T,i}} < 1\) のとき成り立たないような気がします。大きな誤差にはならないのでこれでもいいのかもしれませんが、せっかくなので別な方法を考えてみたいと思います。

上から抑える方法として以下の Cauchy-Schwarz の不等式を使う方法が考えられます。 \begin{align} \sum_{t = 1}^T \sqrt{\frac{g_{t,i}^2}{t}} &= \parentheses{ \begin{array}{c} \sqrt{g_{1,i}^2} \\ \vdots \\ \sqrt{g_{T,i}^2} \end{array} } \cdot \parentheses{ \begin{array}{c} 1/\sqrt{1} \\ \vdots \\ 1/\sqrt{T} \\ \end{array} } \\ &\leq \norm{ \parentheses{ \begin{array}{c} \sqrt{g_{1,i}^2} \\ \vdots \\ \sqrt{g_{T,i}^2} \end{array} } }_2 \norm{ \parentheses{ \begin{array}{c} 1/\sqrt{1} \\ \vdots \\ 1/\sqrt{T} \\ \end{array} } }_2 \\ &= \norm{g_{1:T,i}}_2 \sqrt{\sum_{t = 1}^T \frac{1}{t}} \\ &\leq \norm{g_{1:T,i}}_2 \sqrt{\int_1^T \parentheses{1 + \frac{1}{t}} dt } \\ &= \norm{g_{1:T,i}}_2 \sqrt{T - 1 + \log T} \end{align} この変更を行っても \(\sqrt{T - 1 + \log T}\) が \(O\parentheses{\sqrt{T}}\) なので以降の議論に大きな影響はないはずです(あとできちんと確認します)。とりあえず自分の中ではこれで納得したいと思います。