The AdaGrad summation inequality

ProofAdvanced⏱ 30 minSGDadagradtelescopingregret

Problem

Prove that for non-negative $h_1,\dots,h_T$ with $S_t = \sum_{s\le t}h_s^2$ ,

\sum_{t=1}^T\frac{h_t^2}{\sqrt{S_t}} \le 2\sqrt{S_T}.

This is the key lemma in the AdaGrad regret analysis. Explain why it produces the $\sum_i\sqrt{\sum_tg_{t,i}^2}$ form of the bound.

Write a complete argument. Every inequality you use should be one you could state precisely.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Derive Adam's bias correction	SGD	Proof	Beginner	15 min
Why AdamW differs from Adam with L2	SGD	Proof	Intermediate	30 min
The SVRG control variate	SGD	Proof	Advanced	1 hour
Open: why does Adam beat SGD on transformers? abyss	SGD	Proof	Research	Research