Stochastic gradient descent

Stochastic gradient descent (often abbreviated SGD) is an iterative method for optimizing an objective function with suitable smoothness properties (e.g. differentiable or subdifferentiable). It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient (calculated from the entire data set) by an estimate thereof (calculated from a randomly selected subset of the data). Especially in big data applications this reduces the computational burden, achieving faster iterations in trade for a slightly lower convergence rate.

While the basic idea behind stochastic approximation can be traced back to the Robbins–Monro algorithm of the 1950s, stochastic gradient descent has become an important optimization method in machine learning.

Background

Main article: M-estimation

See also: Estimating equation

Both statistical estimation and machine learning consider the problem of minimizing an objective function that has the form of a sum:

$Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),$

where the parameter $w$ that minimizes $Q(w)$ is to be estimated. Each summand function $Q_{i}$ is typically associated with the $i$-th observation in the data set (used for training).

In classical statistics, sum-minimization problems arise in least squares and in maximum-likelihood estimation (for independent observations). The general class of estimators that arise as minimizers of sums are called M-estimators. However, in statistics, it has been long recognized that requiring even local minimization is too restrictive for some problems of maximum-likelihood estimation. Therefore, contemporary statistical theorists often consider stationary points of the likelihood function (or zeros of its derivative, the score function, and other estimating equations).

The sum-minimization problem also arises for empirical risk minimization. In this case, $Q_{i}(w)$ is the value of the loss function at $i$-th example, and $Q(w)$ is the empirical risk.

When used to minimize the above function, a standard (or "batch") gradient descent method would perform the following iterations:

$w:=w-\eta \nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w),$

where $\eta$ is a step size (sometimes called the learning rate in machine learning).

In many cases, the summand functions have a simple form that enables inexpensive evaluations of the sum-function and the sum gradient. For example, in statistics, one-parameter exponential families allow economical function-evaluations and gradient-evaluations.

However, in other cases, evaluating the sum-gradient may require expensive evaluations of the gradients from all summand functions. When the training set is enormous and no simple formulas exist, evaluating the sums of gradients becomes very expensive, because evaluating the gradient requires evaluating all the summand functions' gradients. To economize on the computational cost at every iteration, stochastic gradient descent samples a subset of summand functions at every step. This is very effective in the case of large-scale machine learning problems.

Iterative method

Fluctuations in the total objective function as gradient steps with respect to mini-batches are taken.

In stochastic (or "on-line") gradient descent, the true gradient of $Q(w)$ is approximated by a gradient at a single example:

$w:=w-\eta \nabla Q_{i}(w).$

As the algorithm sweeps through the training set, it performs the above update for each training example. Several passes can be made over the training set until the algorithm converges. If this is done, the data can be shuffled for each pass to prevent cycles. Typical implementations may use an adaptive learning rate so that the algorithm converges.

In pseudocode, stochastic gradient descent can be presented as follows:

• Choose an initial vector of parameters $w$ and learning rate $\eta$.
• Repeat until an approximate minimum is obtained:
  • Randomly shuffle examples in the training set.
  • For $i=1,2,...,n$, do:
    • $\!w:=w-\eta \nabla Q_{i}(w).$

A compromise between computing the true gradient and the gradient at a single example is to compute the gradient against more than one training example (called a "mini-batch") at each step. This can perform significantly better than "true" stochastic gradient descent described, because the code can make use of vectorization libraries rather than computing each step separately. It may also result in smoother convergence, as the gradient computed at each step is averaged over more training examples.

The convergence of stochastic gradient descent has been analyzed using the theories of convex minimization and of stochastic approximation. Briefly, when the learning rates $\eta$ decrease with an appropriate rate, and subject to relatively mild assumptions, stochastic gradient descent converges almost surely to a global minimum when the objective function is convex or pseudoconvex, and otherwise converges almost surely to a local minimum. This is in fact a consequence of the Robbins-Siegmund theorem.

Example

Let's suppose we want to fit a straight line ${\hat {y}}=\!w_{1}+w_{2}x$ to a training set with observations$(x_{1},x_{2},\ldots ,x_{n})$ and corresponding estimated responses $({\hat {y_{1}}},{\hat {y_{2}}},\ldots ,{\hat {y_{n}}})$ using least squares. The objective function to be minimized is:

$Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y_{i}}}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\right)^{2}.$

The last line in the above pseudocode for this specific problem will become:

${\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}{\frac {\partial }{\partial w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\{\frac {\partial }{\partial w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\\2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.$

Note that in each iteration (also called update), only the gradient evaluated at a single point $x_{i}$ instead of evaluating at the set of all samples.

The key difference compared to standard (Batch) Gradient Descent is that only one piece of data from the dataset is used to calculate the step, and the piece of data is picked randomly at each step.

Notable applications

Stochastic gradient descent is a popular algorithm for training a wide range of models in machine learning, including (linear) support vector machines, logistic regression (see, e.g., Vowpal Wabbit) and graphical models. When combined with the backpropagation algorithm, it is the de facto standard algorithm for training artificial neural networks. Its use has been also reported in the Geophysics community, specifically to applications of Full Waveform Inversion (FWI).

Stochastic gradient descent competes with the L-BFGS algorithm, which is also widely used. Stochastic gradient descent has been used since at least 1960 for training linear regression models, originally under the name ADALINE.

Another stochastic gradient descent algorithm is the least mean squares (LMS) adaptive filter.

Extensions and variants

Many improvements on the basic stochastic gradient descent algorithm have been proposed and used. In particular, in machine learning, the need to set a learning rate (step size) has been recognized as problematic. Setting this parameter too high can cause the algorithm to diverge; setting it too low makes it slow to converge. A conceptually simple extension of stochastic gradient descent makes the learning rate a decreasing function η_t of the iteration number t, giving a learning rate schedule, so that the first iterations cause large changes in the parameters, while the later ones do only fine-tuning. Such schedules have been known since the work of MacQueen on k-means clustering. Some practical guidance on choosing the step size in several variants of SGD is given in Sects. 4.4, 6.6, and 7.5 of Spall (2003).

Implicit updates (ISGD)

As mentioned earlier, classical stochastic gradient descent is generally sensitive to learning rate η. Fast convergence requires large learning rates but this may induce numerical instability. The problem can be largely solved by considering implicit updates whereby the stochastic gradient is evaluated at the next iterate rather than the current one:

$w^{new}:=w^{old}-\eta \nabla Q_{i}(w^{new}).$

This equation is implicit since $w^{new}$ appears on both sides of the equation. It is a stochastic form of the proximal gradient method since the update can also be written as:

$w^{new}:=\arg \min _{w}\{Q_{i}(w)+{\frac {1}{2\eta }}||w-w^{old}||^{2}\}.$

As an example, consider least squares with features $x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}$ and observations $y_{1},\ldots ,y_{n}\in \mathbb {R}$. We wish to solve:

$\min _{w}\sum _{j=1}^{n}(y_{j}-x_{j}'w)^{2},$

where $x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}$ indicates the inner product. Note that $x$ could have "1" as the first element to include an intercept. Classical stochastic gradient descent proceeds as follows:

$w^{new}=w^{old}+\eta (y_{i}-x_{i}'w^{old})x_{i}$

where $i$ is uniformly sampled between 1 and $n$. Although theoretical convergence of this procedure happens under relatively mild assumptions, in practice the procedure can be quite unstable. In particular, when $\eta$ is misspecified so that $I-\eta x_{i}x_{i}'$ has large absolute eigenvalues with high probability, the procedure may diverge numerically within a few iterations. In contrast, implicit stochastic gradient descent (shortened as ISGD) can be solved in closed-form as:

$w^{new}=w^{old}+{\frac {\eta }{1+\eta ||x_{i}||^{2}}}(y_{i}-x_{i}'w^{old})x_{i}.$

This procedure will remain numerically stable virtually for all $\eta$ as the learning rate is now normalized. Such comparison between classical and implicit stochastic gradient descent in the least squares problem is very similar to the comparison between least mean squares (LMS) and normalized least mean squares filter (NLMS).

Even though a closed-form solution for ISGD is only possible in least squares, the procedure can be efficiently implemented in a wide range of models. Specifically, suppose that $Q_{i}(w)$ depends on $w$ only through a linear combination with features $x_{i}$, so that we can write $\nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}$, where $q()\in \mathbb {R}$ may depend on $x_{i},y_{i}$ as well but not on $w$ except through $x_{i}'w$. Least squares obeys this rule, and so does logistic regression, and most generalized linear models. For instance, in least squares, $q(x_{i}'w)=y_{i}-x_{i}'w$, and in logistic regression $q(x_{i}'w)=y_{i}-S(x_{i}'w)$, where $S(u)=e^{u}/(1+e^{u})$ is the logistic function. In Poisson regression, $q(x_{i}'w)=y_{i}-e^{x_{i}'w}$, and so on.

In such settings, ISGD is simply implemented as follows. Let $f(\xi )=\eta q(x_{i}'w^{old}+\xi ||x_{i}||^{2})$, where $\xi$ is scalar. Then, ISGD is equivalent to:

$w^{new}=w^{old}+\xi ^{\ast }x_{i},~{\text{where}}~\xi ^{\ast }=f(\xi ^{\ast }).$

The scaling factor $\xi ^{\ast }\in \mathbb {R}$ can be found through the bisection method since in most regular models, such as the aforementioned generalized linear models, function $q()$ is decreasing, and thus the search bounds for $\xi ^{\ast }$ are $[\min(0,f(0)),\max(0,f(0))]$.

Momentum

Further proposals include the momentum method, which appeared in Rumelhart, Hinton and Williams' seminal paper on backpropagation learning. Stochastic gradient descent with momentum remembers the update Δ w at each iteration, and determines the next update as a linear combination of the gradient and the previous update:

$\Delta w:=\alpha \Delta w-\eta \nabla Q_{i}(w)$

$w:=w+\Delta w$

that leads to:

$w:=w-\eta \nabla Q_{i}(w)+\alpha \Delta w$

where the parameter $w$ which minimizes $Q(w)$ is to be estimated, and $\eta$ is a step size (sometimes called the learning rate in machine learning).

The name momentum stems from an analogy to momentum in physics: the weight vector $w$, thought of as a particle traveling through parameter space, incurs acceleration from the gradient of the loss ("force"). Unlike in classical stochastic gradient descent, it tends to keep traveling in the same direction, preventing oscillations. Momentum has been used successfully by computer scientists in the training of artificial neural networks for several decades.

Averaging

Averaged stochastic gradient descent, invented independently by Ruppert and Polyak in the late 1980s, is ordinary stochastic gradient descent that records an average of its parameter vector over time. That is, the update is the same as for ordinary stochastic gradient descent, but the algorithm also keeps track of

${\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}$.

When optimization is done, this averaged parameter vector takes the place of w.

AdaGrad

AdaGrad (for adaptive gradient algorithm) is a modified stochastic gradient descent algorithm with per-parameter learning rate, first published in 2011. Informally, this increases the learning rate for sparser parameters and decreases the learning rate for ones that are less sparse. This strategy often improves convergence performance over standard stochastic gradient descent in settings where data is sparse and sparse parameters are more informative. Examples of such applications include natural language processing and image recognition. It still has a base learning rate η, but this is multiplied with the elements of a vector {G_j,j} which is the diagonal of the outer product matrix

$G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}$

where $g_{\tau }=\nabla Q_{i}(w)$, the gradient, at iteration τ. The diagonal is given by

$G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}$.

This vector is updated after every iteration. The formula for an update is now

$w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\circ g$

or, written as per-parameter updates,

$w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.$

Each {G_(i,i)} gives rise to a scaling factor for the learning rate that applies to a single parameter w_i. Since the denominator in this factor, ${\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}$ is the ℓ₂ norm of previous derivatives, extreme parameter updates get dampened, while parameters that get few or small updates receive higher learning rates.

While designed for convex problems, AdaGrad has been successfully applied to non-convex optimization.

RMSProp

RMSProp (for Root Mean Square Propagation) is also a method in which the learning rate is adapted for each of the parameters. The idea is to divide the learning rate for a weight by a running average of the magnitudes of recent gradients for that weight. So, first the running average is calculated in terms of means square,

$v(w,t):=\gamma v(w,t-1)+(1-\gamma )(\nabla Q_{i}(w))^{2}$

where, $\gamma$ is the forgetting factor.

And the parameters are updated as,

$w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)$

RMSProp has shown excellent adaptation of learning rate in different applications. RMSProp can be seen as a generalization of Rprop and is capable to work with mini-batches as well opposed to only full-batches.

Adam

Adam (short for Adaptive Moment Estimation) is an update to the RMSProp optimizer. In this optimization algorithm, running averages of both the gradients and the second moments of the gradients are used. Given parameters $w^{(t)}$ and a loss function $L^{(t)}$, where $t$ indexes the current training iteration (indexed at $0$), Adam's parameter update is given by:

$m_{w}^{(t+1)}\leftarrow \beta _{1}m_{w}^{(t)}+(1-\beta _{1})\nabla _{w}L^{(t)}$

$v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+(1-\beta _{2})(\nabla _{w}L^{(t)})^{2}$

${\hat {m}}_{w}={\frac {m_{w}^{(t+1)}}{1-\beta _{1}^{t+1}}}$

${\hat {v}}_{w}={\frac {v_{w}^{(t+1)}}{1-\beta _{2}^{t+1}}}$

$w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac {{\hat {m}}_{w}}{{\sqrt {{\hat {v}}_{w}}}+\epsilon }}$

where $\epsilon$ is a small scalar used to prevent division by 0, and $\beta _{1}$ and $\beta _{2}$ are the forgetting factors for gradients and second moments of gradients, respectively. Squaring and square-rooting is done elementwise.

Second-Order Methods

It is known that a stochastic analogue of the standard (deterministic) Newton–Raphson algorithm (a “second-order” method) provides an asymptotically optimal or near-optimal form of iterative optimization in the setting of stochastic approximation. A method that uses direct measurements of the Hessian matrices of the summands in the empirical risk function was developed by Byrd, Hansen, Nocedal, and Singer. However, directly determining the required Hessian matrices for optimization may not be possible in practice. Practical and theoretically sound methods for second-order versions of SGD that do not require direct Hessian information are given by Spall and others. (A less efficient method based on finite differences, instead of simultaneous perturbations, is given by Ruppert.) These methods not requiring direct Hessian information are based on either values of the summands in the above empirical risk function or values of the gradients of the summands (i.e., the SGD inputs). In particular, second-order optimality is asymptotically achievable without direct calculation of the Hessian matrices of the summands in the empirical risk function.

See also

• Coordinate descent – changes one coordinate at a time, rather than one example
• Linear classifier
• Online machine learning
• Stochastic hill climbing

Further reading

• Bertsekas, Dimitri P. (1999), Nonlinear Programming (2nd ed.), Cambridge, MA.: Athena Scientific, ISBN 978-1-886529-00-7.

• Bertsekas, Dimitri (2003), Convex Analysis and Optimization, Athena Scientific.

• Bottou, Léon (2004), "Stochastic Learning", Advanced Lectures on Machine Learning, LNAI, vol. 3176, Springer, pp. 146–168, ISBN 978-3-540-23122-6.

• Davidon, W.C. (1976), "New least-square algorithms", Journal of Optimization Theory and Applications, 18 (2): 187–197, doi:10.1007/BF00935703, MR 0418461.

• Duda, Richard O.; Hart, Peter E.; Stork, David G. (2000), Pattern Classification (2nd ed.), Wiley, ISBN 978-0-471-05669-0.

• Kiwiel, Krzysztof C. (2004), "Convergence of approximate and incremental subgradient methods for convex optimization", SIAM Journal on Optimization, 14 (3): 807–840, doi:10.1137/S1052623400376366, MR 2085944. (Extensive list of references)

• Snyman, Jan A.; Wilke, Daniel N. (2018), Practical Mathematical Optimization - Basic Optimization Theory and Gradient-Based Algorithms, Springer Optimization and Its Applications Vol. 133 (2 ed.), Springer, pp. xxvi+372, ISBN 978-3-319-77585-2. (Python module pmo.py)

• Spall, James C. (2003), Introduction to Stochastic Search and Optimization, Wiley, ISBN 978-0-471-33052-3.

External links

• Using stochastic gradient descent in C++, Boost, Ublas for linear regression
• Machine Learning Algorithms
• "Gradient Descent, How Neural Networks Learn". 3Blue1Brown. October 16, 2017 – via YouTube.