# How can I use induction to prove Convergence of stochastic gradient descend(SGD) for strongly convex problems with diminishing stepsize?

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

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