I want to prove convergence rate of SGD for strongly convex problems with diminishing stepsize. I can't find the complete proof as most of papers and lecture slides skip the last step and say "use induction to conclude the proof". How can I use induction to conclude the proof of convergence theorem with \eqref{ineq:*}

The assumptions, SGD algorithm and convergence theorem are, \begin{align} \min_x F(x) \end{align} where
$F$: $\mu-$ strongly convex, $L-$ smooth
$g(x^t)$: an unbiased estimate of $\nabla F(x^t)$
for all $x$,
$\mathbb{E}[||g(x)||^2_2] \leq \sigma_g^2 +c_g||\nabla F(x^t)||^2_2 \tag{1}\label{ineq:bounded gradient}$

SGD algorithm: \begin{align} x^{t+1}=x^{t}-\eta_t g(x^t)\tag{2}\label{SGD} \end{align}

The convergence theorem:
Suppose $F$ is $\mu-$ strongly convex, and \eqref{ineq:bounded gradient} holds with cg = 0. If $\eta_t = \frac{\theta}{t+1}$ for some $\theta>\frac{1}{2\mu}$, then SGD \eqref{SGD} achieves $\mathbb{E}[||x^t-x^{*}||] \leq \frac{c_{\theta}}{t+1}$ where $c_{\theta}=\max\{\frac{2\theta\sigma_g^2}{2\mu\theta-1},||x^0-x^{*}||^2_2\}$.

After a series of derivation, we can obtain, \begin{align} \mathbb{E}[||x^{t+1}-x^*||^2_2] \leq (1-2\mu\eta_t)\mathbb{E}[||x^t-x^*||_2^2]+\eta_t^2\sigma_g^2\tag{3}\label{ineq:*} \end{align} where $\eta_t=\frac{\theta}{t+1}$
I tried base case $t=0$, it works. But I can't prove that if the theorem holds for any given case $t=k-1$, then it holds for the next case $t=k$. I have already use \eqref{ineq:*} and the case $t=k-1$. Can someone post the derivation for me?

Many thanks,
Jq H

  • $\begingroup$ Hi, what is $g(x^t, \eta^t)$ ? $\endgroup$ – Paresseux Nguyen Jun 10 at 18:02
  • $\begingroup$ Hi, it should be $g(x^t)$. $\endgroup$ – LdL Jun 10 at 20:04

Your Answer

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

Browse other questions tagged or ask your own question.