6.4 Stochastic gradient descent

This section introduces stochastic gradient descent (SGD) algorithms, which are widely used in the field of machine learning. We will see that SGD is a special RM algorithm, and the mean estimation algorithm is a special SGD algorithm.

Consider the following optimization problem:

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

A straightforward method for solving (6.10) is gradient descent. In particular, the gradient of $\mathbb{E}[f(w,X)]$ is $\nabla_w\mathbb{E}[f(w,X)] = \mathbb{E}[\nabla_w f(w,X)]$ . Then, the gradient descent algorithm is

This gradient descent algorithm can find the optimal solution $w^{*}$ under some mild conditions such as the convexity of $f$ . Preliminaries about gradient descent algorithms can be found in Appendix D.

The gradient descent algorithm requires the expected value $\mathbb{E}[\nabla_w f(w_k, X)]$ . One way to obtain the expected value is based on the probability distribution of $X$ . The

distribution is, however, often unknown in practice. Another way is to collect a large number of i.i.d. samples $\{x_{i}\}_{i = 1}^{n}$ of $X$ so that the expected value can be approximated as

Then, (6.11) becomes

One problem of the algorithm in (6.12) is that it requires all the samples in each iteration. In practice, if the samples are collected one by one, then it is favorable to update $w$ every time a sample is collected. To that end, we can use the following algorithm:

where $x_{k}$ is the sample collected at time step $k$ . This is the well-known stochastic gradient descent algorithm. This algorithm is called "stochastic" because it relies on stochastic samples $\{x_{k}\}$ .

Compared to the gradient descent algorithm in (6.11), SGD replaces the true gradient $\mathbb{E}[\nabla_w f(w, X)]$ with the stochastic gradient $\nabla_w f(w_k, x_k)$ . Since $\nabla_w f(w_k, x_k) \neq \mathbb{E}[\nabla_w f(w, X)]$ , can such a replacement still ensure $w_k \to w^*$ as $k \to \infty$ ? The answer is yes. We next present an intuitive explanation and postpone the rigorous proof of the convergence to Section 6.4.5.

In particular, since

the SGD algorithm in (6.13) can be rewritten as

Therefore, the SGD algorithm is the same as the regular gradient descent algorithm except that it has a perturbation term $\alpha_{k}\eta_{k}$ . Since $\{x_{k}\}$ is i.i.d., we have $\mathbb{E}_{x_k}[\nabla_w f(w_k,x_k)] = \mathbb{E}_X[\nabla_w f(w_k,X)]$ . As a result,

Therefore, the perturbation term $\eta_{k}$ has a zero mean, which intuitively suggests that it may not jeopardize the convergence property. A rigorous proof of the convergence of

SGD is given in Section 6.4.5.

6.4.1 Application to mean estimation

We next apply SGD to analyze the mean estimation problem and show that the mean estimation algorithm in (6.4) is a special SGD algorithm. To that end, we formulate the mean estimation problem as an optimization problem:

where $f(w,X) = \| w - X\| ^2 /2$ and the gradient is $\nabla_wf(w,X) = w - X$ . It can be verified that the optimal solution is $w^{*} = \mathbb{E}[X]$ by solving $\nabla_wJ(w) = 0$ . Therefore, this optimization problem is equivalent to the mean estimation problem.

The gradient descent algorithm for solving (6.14) is

This gradient descent algorithm is not applicable since $\mathbb{E}[w_k - X]$ or $\mathbb{E}[X]$ on the right-hand side is unknown (in fact, it is what we need to solve).

The SGD algorithm for solving (6.14) is

where $x_{k}$ is a sample obtained at time step $k$ . Notably, this SGD algorithm is the same as the iterative mean estimation algorithm in (6.4). Therefore, (6.4) is an SGD algorithm designed specifically for solving the mean estimation problem.

6.4.2 Convergence pattern of SGD

The idea of the SGD algorithm is to replace the true gradient with a stochastic gradient. However, since the stochastic gradient is random, one may ask whether the convergence speed of SGD is slow or random. Fortunately, SGD can converge efficiently in general. An interesting convergence pattern is that it behaves similarly to the regular gradient descent algorithm when the estimate $w_{k}$ is far from the optimal solution $w^{*}$ . Only when $w_{k}$ is close to $w^{*}$ , does the convergence of SGD exhibit more randomness.

An analysis of this pattern and an illustrative example are given below.

Analysis: The relative error between the stochastic and true gradients is

For the sake of simplicity, we consider the case where $w$ and $\nabla_w f(w,x)$ are both scalars. Since $w^*$ is the optimal solution, it holds that $\mathbb{E}[\nabla_w f(w^*,X)] = 0$ . Then, the relative error can be rewritten as

where the last equality is due to the mean value theorem [7, 8] and $\tilde{w}_k \in [w_k, w^*]$ . Suppose that $f$ is strictly convex such that $\nabla_w^2 f \geq c > 0$ for all $w, X$ . Then, the denominator in (6.15) becomes

Substituting the above inequality into (6.15) yields

distance to the optimal solution

The above inequality suggests an interesting convergence pattern of SGD: the relative error $\delta_{k}$ is inversely proportional to $|w_{k} - w^{*}|$ . As a result, when $|w_{k} - w^{*}|$ 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^{*}$ . When $w_{k}$ is close to $w^{*}$ , the relative error $\delta_{k}$ may be large, and the convergence exhibits more randomness.

Example: A good example for demonstrating the above analysis is the mean estimation problem. Consider the mean estimation problem in (6.14). When $w$ and $X$ are both scalar, we have $f(w, X) = |w - X|^2 / 2$ and hence

Thus, the relative error is

The expression of the relative error clearly shows that $\delta_{k}$ is inversely proportional to

Figure 6.5: An example for demonstrating stochastic and mini-batch gradient descent algorithms. The distribution of $X \in \mathbb{R}^2$ is uniform in the square area centered at the origin with a side length as 20. The mean is $\mathbb{E}[X] = 0$ . The mean estimation is based on 100 i.i.d. samples.

$\left|w_{k} - w^{*}\right|$ . As a result, when $w_{k}$ is far from $w^{*}$ , the relative error is small, and SGD behaves like gradient descent. In addition, since $\delta_{k}$ is proportional to $|\mathbb{E}[X] - x_k|$ , the mean of $\delta_{k}$ is proportional to the variance of $X$ .

The simulation results are shown in Figure 6.5. Here, $X \in \mathbb{R}^2$ represents a random position in the plane. Its distribution is uniform in the square area centered at the origin and $\mathbb{E}[X] = 0$ . The mean estimation is based on 100 i.i.d. samples. Although the initial guess of the mean is far away from the true value, it can be seen that the SGD estimate quickly approaches the neighborhood of the origin. When the estimate is close to the origin, the convergence process exhibits certain randomness.

6.4.3 A deterministic formulation of SGD

The formulation of SGD in (6.13) involves random variables. One may often encounter a deterministic formulation of SGD without involving any random variables.

In particular, consider a set of real numbers $\{x_{i}\}_{i = 1}^{n}$ , where $x_{i}$ does not have to be a sample of any random variable. The optimization problem to be solved is to minimize the average:

where $f(w, x_i)$ is a parameterized function, and $w$ is the parameter to be optimized. The gradient descent algorithm for solving this problem is

Suppose that the set $\{x_{i}\}_{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:

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 $\{x_{i}\}_{i = 1}^{n}$ .

The algorithm in (6.16) 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 $\{x_{i}\}_{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 $\{x_{i}\}_{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:

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

6.4.4 BGD, SGD, and mini-batch GD

While SGD uses a single sample in every iteration, we next introduce mini-batch gradient descent (MBGD), which uses a few more samples in every iteration. When all samples are used in every iteration, the algorithm is called batch gradient descent (BGD).

In particular, suppose that we would like to find the optimal solution that can minimize $J(w) = \mathbb{E}[f(w,X)]$ given a set of random samples $\{x_{i}\}_{i = 1}^{n}$ of $X$ . The BGD, SGD, and MBGD algorithms for solving this problem are, respectively,

In the BGD algorithm, all the samples are used in every iteration. When $n$ is large, $(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)]$ . In the MBGD al-

gorithm, $\mathcal{I}_k$ is a subset of $\{1,\ldots ,n\}$ obtained at time $k$ . The size of the set is $|\mathcal{I}_k| = m$ . The samples in $\mathcal{I}_k$ are also assumed to be i.i.d. In the SGD algorithm, $x_{k}$ is randomly sampled from $\{x_{i}\}_{i = 1}^{n}$ at time $k$ .

MBGD can be viewed as an intermediate version between SGD and BGD. 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 using all the samples in every iteration, making it more flexible. If $m = 1$ , then MBGD becomes SGD. However, if $m = n$ , MBGD may not become SGD. This is because MBGD uses $n$ randomly fetched samples, whereas BGD uses all $n$ numbers. These $n$ randomly fetched samples may contain the same number multiple times and hence may not cover all $n$ numbers in $\{x_i\}_{i=1}^n$ .

The convergence speed of MBGD is faster than that of SGD in general. This is because SGD uses $\nabla_{w}f(w_{k},x_{k})$ to approximate the true gradient, whereas MBGD uses $(1 / m)\sum_{j\in \mathcal{I}_k}\nabla_{w}f(w_k,x_j)$ , which is closer to the true gradient because the randomness is averaged out. The convergence of the MBGD algorithm can be proven similarly to the SGD case.

A good example for demonstrating the above analysis is the mean estimation problem. In particular, given some numbers $\{x_i\}_{i=1}^n$ , our goal is to calculate the mean $\bar{x} = \sum_{i=1}^n x_i / n$ . This problem can be equivalently stated as the following optimization problem:

whose optimal solution is $w^{*} = \bar{x}$ . The three algorithms for solving this problem are, respectively,

where $\bar{x}_k^{(m)} = \sum_{j\in \mathcal{I}_k}x_j / m$ . Furthermore, if $\alpha_{k} = 1 / k$ , the above equations can be solved

as follows:

The derivation of the above equations is similar to that of (6.3) and is omitted here. It can be seen that the estimate given by BGD at each step is exactly the optimal solution $w^{*} = \bar{x}$ . MBGD converges to the mean faster than SGD because $\bar{x}_k^{(m)}$ is already an average.

A simulation example is given in Figure 6.5 to demonstrate the convergence of MBGD. Let $\alpha_{k} = 1 / k$ . It is shown that all MBGD algorithms with different mini-batch sizes can converge to the mean. The case with $m = 50$ converges the fastest, while SGD with $m = 1$ is the slowest. This is consistent with the above analysis. Nevertheless, the convergence rate of SGD is still fast, especially when $w_{k}$ is far from $w^{*}$ .

6.4.5 Convergence of SGD

The rigorous proof of the convergence of SGD is given as follows.

Theorem 6.4 (Convergence of SGD). For the SGD algorithm in (6.13), if the following conditions are satisfied, then $w_{k}$ converges to the root of $\nabla_w\mathbb{E}[f(w,X)] = 0$ almost surely.

(a) $0 < c_{1} \leq \nabla_{w}^{2}f(w,X) \leq c_{2}$ ;
(b) $\sum_{k=1}^{\infty} a_k = \infty$ and $\sum_{k=1}^{\infty} a_k^2 < \infty$ ;
(c) $\{x_{k}\}_{k = 1}^{\infty}$ are i.i.d.

The three conditions in Theorem 6.4 are discussed below.

$\diamond$ Condition (a) is about the convexity of $f$ . It requires the curvature of $f$ to be bounded from above and below. Here, $w$ is a scalar, and so is $\nabla_w^2 f(w,X)$ . This condition can be generalized to the vector case. When $w$ is a vector, $\nabla_w^2 f(w,X)$ is the well-known Hessian matrix.
$\diamond$ Condition (b) is similar to that of the RM algorithm. In fact, the SGD algorithm is a special RM algorithm (as shown in the proof in Box 6.1). In practice, $a_{k}$ is often selected as a sufficiently small constant. Although condition (b) is not satisfied in this case, the algorithm can still converge in a certain sense [24, Section 1.5].
Condition (c) is a common requirement.

Box 6.1: Proof of Theorem 6.4

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

The problem to be solved by SGD is to minimize $J(w) = \mathbb{E}[f(w,X)]$ . This problem can be converted to a root-finding problem. That is, finding the root of $\nabla_wJ(w) = \mathbb{E}[\nabla_wf(w,X)] = 0$ . Let

Then, SGD aims to find the root of $g(w) = 0$ . This is exactly the problem solved by the RM algorithm. The quantity that we can measure is $\tilde{g} = \nabla_w f(w,x)$ , where $x$ is a sample of $X$ . Note that $\tilde{g}$ can be rewritten as

Then, the RM algorithm for solving $g(w) = 0$ is

which is the same as the SGD algorithm in (6.13). As a result, the SGD algorithm is a special RM algorithm. We next show that the three conditions in Theorem 6.1 are satisfied. Then, the convergence of SGD naturally follows from Theorem 6.1.

Since $\nabla_w g(w) = \nabla_w \mathbb{E}[\nabla_w f(w, X)] = \mathbb{E}[\nabla_w^2 f(w, X)]$ , it follows from $c_1 \leq \nabla_w^2 f(w, X) \leq c_2$ that $c_1 \leq \nabla_w g(w) \leq c_2$ . Thus, the first condition in Theorem 6.1 is satisfied.
The second condition in Theorem 6.1 is the same as the second condition in this theorem.
$\diamond$ The third condition in Theorem 6.1 requires $\mathbb{E}[\eta_k|\mathcal{H}_k] = 0$ and $\mathbb{E}[\eta_k^2 |\mathcal{H}_k] < \infty$ . Since $\{x_{k}\}$ is i.i.d., we have $\mathbb{E}_{x_k}[\nabla_w f(w,x_k)] = \mathbb{E}[\nabla_w f(w,X)]$ for all $k$ . Therefore,

Since $\mathcal{H}_k = \{w_k, w_{k-1}, \ldots\}$ and $x_k$ is independent of $\mathcal{H}_k$ , the first term on the right-hand side becomes $\mathbb{E}[\nabla_w f(w_k, x_k) | \mathcal{H}_k] = \mathbb{E}_{x_k}[\nabla_w f(w_k, x_k)]$ . The second term becomes $\mathbb{E}[\mathbb{E}[\nabla_w f(w_k, X)] | \mathcal{H}_k] = \mathbb{E}[\nabla_w f(w_k, X)]$ because $\mathbb{E}[\nabla_w f(w_k, X)]$ is

a function of $w_{k}$ . Therefore,

Similarly, it can be proven that $\mathbb{E}[\eta_k^2 |\mathcal{H}_k] < \infty$ if $|\nabla_w f(w,x)| < \infty$ for all $w$ given any $x$ .

Since the three conditions in Theorem 6.1 are satisfied, the convergence of the SGD algorithm follows.