SA Stochastic Gradient Descent

Stochasitc Gradient Descent(SGD)

Algorithm

Suppose we aim to solve the following optimization problem:

$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]$$

• $w$ is the parameter to be optimized
• $X$ is the random variable. The expectation is with respect to $X$
• $w$ and $X$ can be either scalars or vectors. the function $f(\cdot )$ is a scalar function

Method 1: gradient descent (GD)

• Drawback: requires the distribution of $X$ to calculate the expectation

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_w\mathbb{E}[f(w_k,X)]\\ & =w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]\end{array}$$

Method 2: batch gradient descent (BGD)

• Drawback: requires many samples in each iteration for each $w_k$

$$\mathbb{E}[{\nabla }_{w}f(w_k,X)]\approx \frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$$ $$w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$$

Method 3: stochastic gradient descent (SGD) (batch_size=1)

$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$

Examples

We consider an example:

$$\underset{w}{\min }J(w)=\mathbb{E}[\frac{1}{2}\Vert w-X{\Vert }^2],$$

where

$$f(w,X)=\frac{1}{2}\Vert w-X{\Vert }^2\Rightarrow {\nabla }_{w}f(w,X)=w-X$$

Exercise 1: Show that the optimal solution is $$w^{\ast }=\mathbb{E}(X)$$

The optimal solution $w^{\ast }$ must satisfy:

$$\begin{array}{rl}{\nabla }_{w}J(w^{\ast })& =0\\ \Rightarrow {\nabla }_w\mathbb{E}[\frac{1}{2}\Vert w-X{\Vert }^2]& =0\\ \Rightarrow \mathbb{E}[{\nabla }_w\frac{1}{2}\Vert w-X{\Vert }^2]& =0\\ \Rightarrow \mathbb{E}[w-X]& =0\\ \Rightarrow w^{\ast }& =\mathbb{E}(X)\end{array}$$

Exercise 2: Write out the GD algorithm for solving this problem.

The GD algorithm is:

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_{w}J(w_k)\\ & =w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]\\ & =w_k-{\alpha }_k\mathbb{E}[w_k-X]\end{array}$$

Exercise 3: Write out the SGD algorithm for solving this problem.

The SGD algorithm is:

$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)=w_k-{\alpha }_k(w_k-x_k)$$

• It is the same as the mean estimation problem in the Incremental mean estimation
• mean estimation is a special SGD

Convergence

Question: Dose $w_k\to w^{\ast }$ as $k\to \infty$?

Consider use RM to minimize $J(w)$:

$$J(w)=\mathbb{E}[f(w,X)]$$

Convert the optimization problem to the root-finding problem:

$$g(w)={\nabla }_{w}J(w)=\mathbb{E}[{\nabla }_{w}f(w,X)]=0$$

What we can measure is:

$$\begin{array}{rl}\tilde{g}(w,\eta )& ={\nabla }_{w}f(w_k,x_k)\\ & =\underset{g(w)}{\underbrace{\mathbb{E}[{\nabla }_{w}f(w,X)]}}+\underset{\eta }{\underbrace{{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w,X)]}}\end{array}$$

Then, the RM algorithm is:

$$\begin{array}{rl}{w}_{k+1}& =w_k-a_k\tilde{g}(w_k,{\eta }_k)\\ & =w_k-a_k{\nabla }_{w}f(w_k,x_k)\end{array}$$

• It is exactly the same as the SGD algorithm
• SGD is a special RM
• SGD’s convergence is guaranteed by RM
• SGD convergence pattern see here

Convergence of SGD

In the SGD, if

1. $0<c_1\le {\nabla }_w^{2}f(w,x)\le c_2$;
2. ${\sum }_{k=1}^{\infty }{a}_k=\infty$ and ${\sum }_{k=1}^{\infty }{a}_k^2<\infty$;
3. $\{x_k{\}}_{k=1}^{\infty }$ is i.i.d.;

Then, $w_k\to w^{\ast }$ as $k\to \infty$ with probability 1, $w^{\ast }$ is the root of ${\nabla }_w\mathbb{E}[f(w,X)]=0$.

BGD, MBGD and SGD

Suppose we would like to minimize $J(w)=\mathbb{E}[f(w,X)]$ given a set of random samples $\{x_i{\}}_{i=1}^n$ of $X$.

• BGD: all the samples are used in every iteration. When $n$ is large, $\frac{1}{n}{\sum }_{i=1}^n{\nabla }_{w}f(w_k,x_i)$ is close to the true gradient $\mathbb{E}[{\nabla }_{w}f(w_k,X)]$ $$w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$$
• MBGD: ${\mathcal{I}}_k$ is a subset of $\{1,2,\dots ,n\}$ with the size as $|{\mathcal{I}}_k|=m$. The set ${\mathcal{I}}_k$ is obtained by $m$ times i.i.d. samplings. $$w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\sum _{j\in {\mathcal{I}}_k}{\nabla }_{w}f(w_k,x_j)$$
• SGD: $x_k$ is randomly sampled from $\{x_i{\}}_{i=1}^n$ at time $k$. $$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$

Compare MBGD with BGD and SGD

和之前的PI>TPI>VI的比较非常像，我们的MBGD其实也是BGD和SGD的一种折中(BGD > MBGD > SGD)。BGD的计算量太大，SGD的计算量太小但随机性太大，MBGD则是在这两者之间，可以通过调整batch_size（也就是上面的m）来控制计算量。

• 和SGD(相当于batch_size=1)比较，MBGD拥有更少的随机性（更鲁棒），因为它是从一个batch中取平均，而不是单个样本
• 和BGD(相当于batch_size=n)比较，MBGD的计算量更小，因为它只用了一个batch的样本，而不是全部样本

小结：对比一下之前的操作就是在policy-evaluation中通过减少迭代求解次数得到了TPI，而在这里通过减少batch_size得到了MBGD

• 另外：对于调整batch_size从而得到的不同效果可以查看here

Exercise 4

Given some numbers $\{x_i{\}}_{i=1}^n$, our aim is to calculate the mean $x=\frac{1}{n}{\sum }_{i=1}^n{x}_i$. This problem can be equivalently stated as the following optimization problem:

$$\underset{w}{\min }J(w)=\frac{1}{2n}\sum _{i=1}^n\Vert w-x_i{\Vert }^2$$

Use the BGD, MBGD and SGD algorithms to solve this problem.

The three algorithms for solving this problem are, respectively:

• BGD: $$w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n(w_k-x_i)=w_k-{\alpha }_k(w_k-\bar{x})$$
• MBGD: $$w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\sum _{j\in {\mathcal{I}}_k}(w_k-x_j)=w_k-{\alpha }_k(w_k-{\bar{x}}_k^{(m)})$$
• SGD: $$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

where $\bar{x}=\frac{1}{n}{\sum }_{i=1}^n{x}_i$ and ${\bar{x}}_k^{(m)}=\frac{1}{m}{\sum }_{j\in {\mathcal{I}}_k}{x}_j$.