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.

• 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 – itdxer Jun 13 '17 at 14:37

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.
• 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. – MotiN Jun 13 '17 at 10:55