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$
1
  • $\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, 2017 at 14:37

1 Answer 1

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$
3
  • 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$
    – MotiNK
    Jun 13, 2017 at 10:55
  • $\begingroup$ What is max y if y is a real number? $\endgroup$ Jun 13, 2017 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, 2017 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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