1
$\begingroup$

I've read ADAM paper (https://arxiv.org/abs/1412.6980) and found out a suspicious part.

In Lemma 10.3 of Appendix, \begin{align*} \sqrt{\|g_{1:T,i}\|_2^2 - g_{T,i}^2} & \le \|g_{1:T,i}\|_2 - \frac{g_{T,i}^2}{2\|g_{1:T,i}\|_2}\\ & \le \|g_{1:T,i}\|_2 - \frac{g_{T,i}^2}{2\sqrt{TG_\infty^2}} \end{align*}

They set the bound of 2-norm, $\|g_{1:T,i}\|_2$ of gradient using $G_\infty$, not $G_2$.

Infinity norm is less than or equal to 2-norm, so I think the proof might be wrong.

Can someone tell me what went wrong? Thanks.

$\endgroup$
  • $\begingroup$ It's less, but reciprocal value for this norms give you opposite sign for comparison. Which means that reciprocals is larger value for inf-norm $\endgroup$ – itdxer Jun 13 '17 at 14:37
2
$\begingroup$

The paper is correct, since $$\|x\|_2 = \sqrt{\sum x_i^2} \le \sqrt{\sum \max_i x_i^2 } = \sqrt{ T \|x\|_\infty^2 },$$ and for scalars $0 < y_1 \le y_2$, $$\frac{-1}{y_1} \le \frac{-1}{y_2}$$

hence $$- \frac{g_{T,i}^2}{2 \| g_{1:T,i}\|_2} \le - \frac{g_{T,i}^2}{2 \sqrt{T\|g_{1:T,i}\|_\infty^2}} \le - \frac{g_{T,i}^2}{2 \sqrt{T G^2_\infty}} $$

The important distinction is that we are comparing the 2-norm to the square root of $T$ times the infinity norm squared, rather than the 2-norm directly with the infinity norm.

$\endgroup$
  • 1
    $\begingroup$ Could you please change your middle row to use a new variable (e.g. $y \in \mathcal {R}$)? It is confusing when you use $x$ as a vector in the first row, and then as a real number in row 2. $\endgroup$ – MotiN Jun 13 '17 at 10:55
  • $\begingroup$ What is max y if y is a real number? $\endgroup$ – user0 Jun 13 '17 at 20:55
  • $\begingroup$ Fair point, and given the context I don't need to make a statement about the reals. I've edited the answer so it is hopefully clear now. $\endgroup$ – combo Jun 13 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.