The SVRG control variate

ProofAdvanced⏱ 1 hourSGDsvrgvariance reductioncontrol variate

Problem

For the SVRG direction $v_k = \nabla f_i(x_k)-\nabla f_i(\tilde x)+\nabla f(\tilde x)$ with $i$ uniform:

Show $\E_i[v_k] = \nabla f(x_k)$ .
Show $\E_i\|v_k-\nabla f(x_k)\|_2^2 \le 2L^2\big(\|x_k-x^\star\|_2^2+\|\tilde x-x^\star\|_2^2\big)$ when each $f_i$ is $L$ -smooth.
Explain why this vanishes at the optimum, and why the same construction fails for a non-finite-sum objective.

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 AdaGrad summation inequality	SGD	Proof	Advanced	30 min
Open: why does Adam beat SGD on transformers? abyss	SGD	Proof	Research	Research