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

Posted: 2016-03-30

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

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

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

上から抑える方法として以下のCauchy–Schwarzの不等式を使う方法が考えられます。

\begin{aligned} \sum_{t = 1}^{T} \sqrt{\frac{g_{t, i}^{2}}{t}} & = (\begin{array}{c} \sqrt{g_{1, i}^{2}} \\ ⋮ \\ \sqrt{g_{T, i}^{2}} \end{array}) \cdot (\begin{array}{c} 1 / \sqrt{1} \\ ⋮ \\ 1 / \sqrt{T} \end{array}) \\ \leq {‖ (\begin{array}{c} \sqrt{g_{1, i}^{2}} \\ ⋮ \\ \sqrt{g_{T, i}^{2}} \end{array}) ‖}_{2} {‖ (\begin{array}{c} 1 / \sqrt{1} \\ ⋮ \\ 1 / \sqrt{T} \end{array}) ‖}_{2} \\ = {‖ g_{1 : T, i} ‖}_{2} \sqrt{\sum_{t = 1}^{T} \frac{1}{t}} \\ \leq {‖ g_{1 : T, i} ‖}_{2} \sqrt{\int_{1}^{T} (1 + \frac{1}{t}) d t} \\ = {‖ g_{1 : T, i} ‖}_{2} \sqrt{T - 1 + \log T} \end{aligned}

この変更を行っても $\sqrt{T - 1 + \log T}$ が $O (\sqrt{T})$ なので以降の議論に大きな影響はないはずです（あとできちんと確認します）。とりあえず自分の中ではこれで納得したいと思います。