確率的最適化手法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(\sqrt{T})\) なので以降の議論に大きな影響はないはずです(あとできちんと確認します)。とりあえず自分の中ではこれで納得したいと思います。