Sources:

1. Shiyu Zhao. Chapter 6: Stochastic Approximation. Mathematical Foundations of Reinforcement Learning
2. --> Youtube: Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) algorithm: minimize $J(w)=\mathbb{E}[f(w,X)]$ using $\left\{{\mathrm{\nabla }}_{w}f(w_k,x_k)\right\}$ $$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)$$

Stochastic gradient descent

The iterative mean estimation algorithm is a special form of the Stochastic Gradient Descent (SGD) algorithm.

The SGD algorithm is a special form of the RM algorithm.

RM --> iterative mean estimation --> SGD

Problem statement

Suppose we aim to solve problem $$\underset{w}{min}J(w)$$ where $$J(w)=\mathbb{E}[f(w,X)]$$

• $w$ is the parameter to be optimized.
• $X$ is a 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.

Method 1: gradient descent (GD)

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J(w)=w_k-{\alpha }_k{\mathrm{\nabla }}_w\mathbb{E}\left[f(w_k,X)\right]=w_k-{\alpha }_k\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]$$

It is not practical since if we don't know the probability distribution of $X$, we don't know $\mathbb{E}[f(w,X)]$.

Method 2: batch gradient descent (BGD)

We can use Monte Carlo estimation to compute the estimate $\mathbb{E}[f(w,X)]$. $$\begin{array}{c}\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]\approx \frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i).\\ w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i).\end{array}$$ where $n$ is the number of the dataset (remember that we have a dataset $\{x_1,x_2,\dots ,x_n\}$ of $X$).

Drawback: it requires many samples in each iteration for each $w_k$.

Method 3: stochastic gradient descent (SGD)

$$\begin{array}{}\text{(1)}& w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k),\end{array}$$ - Compared to the gradient descent method: Replace the true gradient $\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]$ by the stochastic gradient ${\mathrm{\nabla }}_{w}f(w_k,x_k)$. - Compared to the batch gradient descent method: let $n=1$.

From GD to SGD: $$\begin{array}{c}{w}_{k+1}=w_k-{\alpha }_k\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]\\ \Downarrow \\ w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)\end{array}$$

The so-called stocastic gradient ${\mathrm{\nabla }}_{w}f(w_k,x_k)$ can be viewed as a noisy measurement of the true gradient $\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]$: $${\mathrm{\nabla }}_{w}f(w_k,x_k)=\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]+\underset{\eta }{\underbrace{{\mathrm{\nabla }}_{w}f(w_k,x_k)-\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]}}.$$

An example of SGD

We next consider an example: $$\underset{w}{min}J(w)=\mathbb{E}[f(w,X)]=\mathbb{E}[\frac{1}{2}\Vert w-X{\Vert }^2],$$ where $$f(w,X)=\Vert w-X{\Vert }^2/2{\mathrm{\nabla }}_{w}f(w,X)=w-X$$

It can be verified that the optimal solution is by solving ${\mathrm{\nabla }}_{w}J(w)=0$. Therefore, this optimization problem is equivalent to the iterative mean estimation problem.

The GD algorithm for solving the above problem is $$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J\left(w_k\right)\\ & =w_k-{\alpha }_k\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]\\ & =w_k-{\alpha }_k\mathbb{E}[w_k-X].\end{array}$$

The SGD algorithm for solving the above problem is $$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)=w_k-{\alpha }_k(w_k-x_k)$$

We can therefore see that the iterative mean estimation algorithm is a special form of the SGD algorithm.

Convergence analysis

We next show that SGD is a special RM algorithm, Then, the convergence naturally follows.

The aim of SGD is to minimize $$J(w)=\mathbb{E}[f(w,X)]$$

This problem can be converted to a root-finding problem²: $${\mathrm{\nabla }}_{w}J(w)=\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]=0$$

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

Then, the aim of SGD is to find the root of $g(w)=0$.

As in RM algorithm, we don't know $g(w)$. Knowing it needs GD (gradient descent), not SGD.

What we can measure is $$\begin{array}{rl}\tilde{g}(w,\eta )& ={\mathrm{\nabla }}_{w}f(w,x)\\ & =\underset{g(w)}{\underbrace{\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]}}+\underset{\eta }{\underbrace{{\mathrm{\nabla }}_{w}f(w,x)-\mathbb{E}[{\mathrm{\nabla }}_{w}f(w,X)]}}.\end{array}$$

Then, the RM algorithm for solving $g(w)=0$ is $$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k)=w_k-a_k{\mathrm{\nabla }}_{w}f(w_k,x_k).$$

• It is exactly the SGD algorithm.
• Therefore, SGD is a special RM algorithm.

Convergence of SGD

Since SGD is a special RM algorithm, its convergence naturally follows.

Theorem (Convergence of SGD): In the SGD algorithm, if

1. $0<c_1\le {\mathrm{\nabla }}_w^{2}f(w,X)\le c_2$ ³;
2. $\sum _{k=1}^{\mathrm{\infty }}{a}_k=\mathrm{\infty }$ and $\sum _{k=1}^{\mathrm{\infty }}{a}_k^2<\mathrm{\infty }$;
3. ${\left\{x_k\right\}}_{k=1}^{\mathrm{\infty }}$ is iid;

then $w_k$ converges to the root of ${\mathrm{\nabla }}_w\mathbb{E}[f(w,X)]=0$ with probability 1.

Convergence pattern

Question: Since the stochastic gradient is random and hence the approximation is inaccurate, whether the convergence of SGD is slow or random? To answer this question, we consider the relative error between the stochastic and batch gradients:

The relative error between the stochastic and true gradients is $${\delta }_k\triangleq \frac{|{\mathrm{\nabla }}_{w}f(w_k,x_k)-\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]|}{\left|\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]\right|}.$$

For the sake of simplicity, we consider the case where $w$ and ${\mathrm{\nabla }}_{w}f(w,x)$ are both scalars. Since $w^{\ast }$ is the optimal solution, it holds that $\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w^{\ast },X)\right]=0$. Then, the relative error can be rewritten as $${\delta }_k=\frac{|{\mathrm{\nabla }}_{w}f(w_k,x_k)-\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]|}{|\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]-\mathbb{E}[{\mathrm{\nabla }}_{w}f(w^{\ast },X)]|}=\frac{|{\mathrm{\nabla }}_{w}f(w_k,x_k)-\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]|}{|\mathbb{E}[{\mathrm{\nabla }}_w^{2}f({\tilde{w}}_k,X)(w_k-w^{\ast })]|},$$ where the last equality is due to the mean value theorem and ${\tilde{w}}_k\in [w_k,w^{\ast }]$. Suppose that $f$ is strictly convex such that ${\mathrm{\nabla }}_w^{2}f\ge c>0$ for all $w,X$. Then, the denominator becomes $$\begin{array}{rl}\left|\mathbb{E}\left[{\mathrm{\nabla }}_w^{2}f({\tilde{w}}_k,X)(w_k-w^{\ast })\right]\right|& =\left|\mathbb{E}\left[{\mathrm{\nabla }}_w^{2}f({\tilde{w}}_k,X)\right]\right|\left|(w_k-w^{\ast })\right|\\ & \ge c|w_k-w^{\ast }|.\end{array}$$

Substituting the above inequality into the above equation yields $${\delta }_k\le \frac{|\stackrel{\text{stochastic gradient }}{\overbrace{{\mathrm{\nabla }}_{w}f(w_k,x_k)}}-\stackrel{\text{true gradient }}{\overbrace{\mathbb{E}\left[{\mathrm{\nabla }}_{w}f(w_k,X)\right]}}|}{\underset{\text{distance to the optimal solution }}{\underbrace{c|w_k-w^{\ast }|}}}.$$

The above inequality suggests an interesting convergence pattern of SGD: the relative error ${\delta }_k$ is inversely proportional to $|w_k-w^{\ast }|$.

As a result, when $|w_k-w^{\ast }|$ is large, ${\delta }_k$ is small. In this case, the SGD algorithm behaves like the gradient descent algorithm and hence $w_k$ quickly converges to $w^{\ast }$. When $w_k$ is close to $w^{\ast }$, the relative error ${\delta }_k$ may be large, and the convergence exhibits more randomness.

A deterministic formulation of SGD

The formulation of SGD in $\text{(1)}$ involves random variables. One may often encounter deterministic formulation of SGD without involving any random variables.

In particular, consider a set of real numbers ${\left\{x_i\right\}}_{i=1}^n$, where $x_i$ does not have to be a ample of any random variable. The optimization problem to be solved is to minimize he average: $$\underset{w}{min}J(w)=\frac{1}{n}\sum _{i=1}^{n}f(w,x_i)$$ where $f(w,x_i)$ is a parameterized function, and $w$ is the parameter to be optimized. The batch gradient descent (BGD) algorithm for solving this problem is $$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J\left(w_k\right)=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i).$$

Suppose that the set ${\left\{x_i\right\}}_{i=1}^n$ is large and we can only fetch a single number each time.

In this case, it is favorable to update $w_k$ in an incremental manner: $$\begin{array}{}\text{(2)}& w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k).\end{array}$$

It must be noted that $x_k$ here is the number fetched at time step $k$ instead of the $k$ th element in the set ${\left\{x_i\right\}}_{i=1}^n$.

The algorithm in $\text{(2)}$ is very similar to SGD, but its problem formulation is subtly different because it does not involve any random variables or expected values.

Then, many questions arise. For example, is this algorithm SGD? How should we use the finite set of numbers ${\left\{x_i\right\}}_{i=1}^n$ ? Should we sort these numbers in a certain order and then use them one by one, or should we randomly sample a number from the set?

A quick answer to the above questions is that, although no random variables are involved in the above formulation, we can convert the deterministic formulation to the stochastic formulation by introducing a random variable.

In particular, let $X$ be a random variable defined on the set ${\left\{x_i\right\}}_{i=1}^n$. Suppose that its probability distribution is uniform such that $p(X=x_i)=1/n$. Then, the deterministic optimization problem becomes a stochastic one: $$\underset{w}{min}J(w)=\frac{1}{n}\sum _{i=1}^{n}f(w,x_i)=\mathbb{E}[f(w,X)].$$

The last equality in the above equation is strict instead of approximate. Therefore, the algorithm in $\text{(2)}$ is SGD, and the estimate converges if $x_k$ is uniformly and independently sampled from ${\left\{x_i\right\}}_{i=1}^n$. Note that $x_k$ may repeatedly take the same number in ${\left\{x_i\right\}}_{i=1}^n$ since it is sampled randomly.

BGD, MBGD, and SGD

Suppose we would like to minimize $J(w)=\mathbb{E}[f(w,X)]$, given a set of random samples ${\left\{x_i\right\}}_{i=1}^n$ of $X$. The BGD, SGD, MBGD algorithms solving this problem are, respectively, $$\begin{array}{rl}& w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\mathrm{\nabla }}_{w}f(w_k,x_i),\text{(BGD)}\\ & w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\sum _{j\in {\mathcal{I}}_k}{\mathrm{\nabla }}_{w}f(w_k,x_j),\text{(MBGD)}\\ & w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}f(w_k,x_k)\text{(SGD)}\end{array}$$

where $n$ is the size of the dataset, $m$ can be smaller.

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

Comparison

Compare MBGD with BGD and SGD: - Compared to SGD, MBGD has less randomness because it uses more samples instead of just one as in SGD. - Compared to BGD, MBGD does not require to use all the samples in every iteration, making it more flexible and efficient. - If $m=1$, MBGD becomes SGD. - If $m=n$, MBGD does NOT become BGD strictly speaking, because MBGD uses randomly fetched $n$ samples whereas BGD uses all $n$ numbers. In particular, MBGD may use a value in ${\left\{x_i\right\}}_{i=1}^n$ multiple times whereas BGD uses each number once.

An example

Given some numbers ${\left\{x_i\right\}}_{i=1}^n$, our aim is to calculate the mean $\overline{x}=\sum _{i=1}^n{x}_i/n$. 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$$

The three algorithms for solving this problem are, respectively, $$\begin{array}{rl}& w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n(w_k-x_i)=w_k-{\alpha }_k(w_k-\overline{x}),\text{(BGD)}\\ & 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-{\overline{x}}_k^{(m)}),\text{(MBGD)}\\ & w_{k+1}=w_k-{\alpha }_k(w_k-x_k),\text{ (SGD) }\end{array}$$ where ${\overline{x}}_k^{(m)}=\sum _{j\in {\mathcal{I}}_k}{x}_j/m$.

Furthermore, if ${\alpha }_k=1/k$, the above equation can be solved as $$\begin{array}{rl}& w_{k+1}=\frac{1}{k}\sum _{j=1}^k\overline{x}=\overline{x},\text{(BGD)}\\ & w_{k+1}=\frac{1}{k}\sum _{j=1}^k{\overline{x}}_j^{(m)},\text{(BGD)}\\ & w_{k+1}=\frac{1}{k}\sum _{j=1}^k{x}_j.\text{(BGD)}\end{array}$$ - The estimate of BGD at each step is exactly the optimal solution $w^{\ast }=\overline{x}$. - The estimate of MBGD approaches the mean faster than SGD because ${\overline{x}}_k^{(m)}$ is already an average.

---

1. The progability distribution of $X$ is fixed, but we don't know it.↩︎

2. The optimal solution $w^{\ast }$ must be a root of the equation. But a root may not be optimal solution. This relates to the convex optimization problem.↩︎

3. Recall that in RM algorithm we need $0<c_1\le {\mathrm{\nabla }}_{w}g(w)\le c_2$. In SGD we have $g(w)={\mathrm{\nabla }}_{w}J(w)$. Therefore, we obtain ${\mathrm{\nabla }}_w^{2}f(w,X)$.↩︎