> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/stochastic-gradient-descent-sgd.md).

# Stochastic Gradient Descent (SGD)

### Gradient Descent

$$\min\_{x\in C}f(x)$$

$$f$$: convex differentiable $$C$$

objective function is an “expectation”

$$f(x)=\frac{1}{m}\left\[f\_1(x)+f\_2(x)+\cdots+f\_m(x)\right]=\mathbb{E}\_i f\_i(x)$$,

where $$i$$ is random variable uniform distributed over $$\left {1,\cdots,m\right }$$

**Example**: least-squares

$$\begin{aligned}f(x)&=\frac{1}{m}\left\[\frac{1}{2}\lVert Ax-b\rVert\_2^2\right] \\&=\frac{1}{m}\left\[\frac{1}{2}\lVert \begin{bmatrix}a\_1^T \ \vdots \ a\_m^T\end{bmatrix}x-\begin{bmatrix}b\_1 \ \vdots \ b\_m\end{bmatrix}\rVert^2\right] \ &=\frac{1}{m}\sum\_{i=1}^m \frac{1}{2}(a\_i^Tx-b\_i)^2 \ &=\frac{1}{m}\sum\_{i=1}^mf\_i(x)\end{aligned}$$

### Gradient Descent

$$x\_{k+1}=x\_k-\alpha\_k\nabla f(x\_k)$$

Main cost at each iteration $$k$$ is $$\nabla f(x\_k)=\frac{1}{m}\sum\_{i=1}^m\nabla f\_i(x)$$

Ex: for LS,

$$\begin{aligned}\nabla f(x)&=\nabla \left\[ \frac{1}{2}\lVert Ax-b\rVert^2\right] \ &=A^T(Ax-b) \ &=A^Tr \ &=\begin{bmatrix}a\_1 \cdots a\_m\end{bmatrix}\begin{bmatrix}r\_1 \ \vdots \ r\_m\end{bmatrix}=\sum\_{i=1}^m a\_ir\_i\end{aligned}$$

### Approximate the Gradient

randomly sample $$i\in\left {1,\cdots,m\right }$$

Stochastic gradient approx to $$\nabla f(x)$$ is $$g=\nabla f\_i(x)$$

$$\begin{aligned}\mathbb{E}g & =\sum\_{i=1}^m \frac{1}{m}\nabla f\_i(x) \ &=\frac{1}{m}\sum\_{i=1}^m\nabla f\_i(x) \ &\equiv \nabla f(x)\end{aligned}$$

### Stochastic Gradient Method

$$x\_{k+1}=x\_k-\alpha\_kg\_k$$

cost at iteration $$k$$: choose $$i\_k \in \left { 1,\ldots, m\right}$$, compute $$g\_k:=\nabla f\_{i\_k}(x)$$

Variant: instead of sampling single element $$\left {1,\cdots,m\right }$$, sample a “batch” $$B\_k \subseteq \left { 1,\ldots, m\right }$$

$$k$$th Stochastic gradient estimation: $$g\_k=\frac{1}{\lvert B\_k\rvert}\sum\_{i\in B\_k}\nabla f\_i(x)$$

### Convergence of function values $$f(x\_k)$$ in expectation:

$$f\_k:=f(x\_k)$$

$$\nabla f\_k := \nabla f(x\_k)$$

By the descent lemma, if $$f$$ has an L-Lip continuous gradient

$$\lVert \nabla f(x)-\nabla f(y)\rVert\_2 \le L\cdot \lVert x-y\rVert\_2$$ for some $$L \gt 0, \forall x,y$$

$$f(z)\le f(x)+\nabla f(x)^T(z-x)+\frac{L}{2}\lVert z-x\rVert^2, \forall x,z$$

so take $$z=x\_{k+1}$$, $$x=x\_k$$:

$$f\_{k+1}\le f\_k+\nabla f\_k^T(x\_{k+1}-x\_k)+\frac{L}{2}\lVert x\_{k+1}-x\_k\rVert^2$$

SGD: $$x\_{k+1}=x\_k-\alpha g\_k$$ ⇒ $$x\_{k+1}-x\_k=-\alpha g\_k$$

⇒ $$f\_{k+1}\le f\_k-\alpha \nabla f\_k^Tg\_k+\frac{L\alpha^2}{2}\lVert g\_k\rVert^2$$

Take expectations of both sides:

$$\begin{aligned}\mathbb{E}f\_{k+1} &\le \mathbb{E}f\_k-\alpha\mathbb{E}\lVert \nabla f\_k\rVert^2+\frac{L\alpha^2}{2}\mathbb{E}\lVert g\_k\rVert^2 \ &\le \mathbb{E}f\_k-\alpha\mathbb{E}\lVert \nabla f\_k\rVert^2+\frac{L\alpha^2}{2}(\sigma^2+\mathbb{E}\lVert \nabla f\_k\rVert^2) \ &\le \mathbb{E}f\_k-\alpha(1-\frac{L\alpha}{2})\mathbb{E}\lVert \nabla f\_k\rVert^2+\frac{L\alpha^2\sigma^2}{2} \ &\le \mathbb{E}f\_k-\frac{\alpha}{2}\mathbb{E}\lVert \nabla f\_k\rVert^2+\frac{L\alpha^2\sigma^2}{2} \text{ if } \alpha \le \frac{1}{L}...\end{aligned}$$

Assumption: need to assume mean-squared error in stochastic approx is bounded:

$$\mathbb{E}\left\[\lVert g\_k-\nabla f\_k \rVert^2\right]=\mathbb{E}\left\[\lVert g\_k\rVert^2\right]-\lVert \nabla f\_k\rVert^2 \le \sigma^2 ,\forall k$$

for some $$\sigma \gt 0$$ fixed ⇒ $$\mathbb{E}\left\[\lVert g\_k\rVert^2\right] \le \sigma^2+\lVert \nabla f\_k\rVert^2$$

Sum and reverse for all $$k=0,1,2,\cdots,T$$

$$\mathbb{E}f\_k \le f(x\_0)-\frac{\alpha}{2}\sum\_{k=1}^{T-1}\mathbb{E} \left\[\lVert \nabla f\_k \rVert^2\right]+\frac{\alpha^2\sigma L T}{2}$$

Divide both sides by $$\alpha \frac{T}{2}$$,

$$\frac{1}{T}\sum\_{k=0}^{T-1}\mathbb{E} \lVert \nabla f\_k\rVert^2 \le\frac{2(f(x\_0)-f^\*)}{\alpha T}+\underbrace{\alpha \sigma L}\_{\text{error term}}$$.